Graphics Programming Principles and Algorithms

1 Graphics ProgrammingPrinciples and AlgorithmsZongli ShiMay 27, 2017 AbstractThis paper is an introduction to Graphics Programming . This is a computer science fieldtrying to answer questions such as how we can model 2D and 3D objects and have them displayedon screen. Researchers in this field are constantly trying to find more efficient Algorithms forthese tasks. We are going to look at basic Algorithms for modeling and drawing line segments,2D and 3D polygons. We are also going to explore ways to transform and clip 2D and 3 Dpolygons. For illustration purpose, the Algorithms presented in this paper are implemented inC++ and hosted at GitHub. Link to the GitHub repository can be found in the IntroductionComputer Graphics has been playing a vital role in communicating computer-generated informationto human users as well as providing a more intuitive way for users to interact with computers.

2 Al-though nowadays, devices such as touch screens are everywhere, the effort of developing graphicssystem in the first place and beauty of efficient Graphics rendering Algorithms should not be underes-timated. Future development in Graphics hardware will also bring new challenges, which will requireus to have a thorough understanding of the fundamentals. This paper will mostly investigate thevarious problems in Graphics Programming and the Algorithms to solve them. All of the algorithmsare also presented in the book Computer Graphics by Steven Harrington [Har87]. This paper willalso serve as a tutorial, instructing the readers to build a complete Graphics system from scratch. Atthe end we shall have a program manipulating basic bits and bytes but capable of generating 3-Danimation all by itself.

3 To better assist the reader in implementing the Algorithms presented in thispaper, the writer s implementation in C++ can be found in the following GitHub link: Basic Problems in GraphicsThe basic problems in Graphics Programming are similar to those in any task of approximation. Thenotion of shapes such as polygons and lines are abstract, and by their definitions, continuous intheir nature. A line can extend to both directions forever. A polygon can be made as large as wewant. However, most display devices are represented as a rectangle holding finitely many individualdisplaying units called pixels. The size of the screen limits the size of our shapes and the amountof pixels limit how much detail we can put on screen. Therefore, we are trying to map somethingcontinuous and infinite in nature such as lines and polygons to something discrete and finite.

4 In thisprocess, some information has to be lost but we should also try to approximate the best we will first look at how to draw a line on screen to illustrate the process of building a discreterepresentation and how to recover as much lost information as we Drawing a Line SegmentSince a line is infinite in its nature, we have to restrict ourselves to drawing line segments, which willa be reasonable representation of infinite line when going from one side of a screen to another. Thesimplest way to represent a line segment is to have the coordinates of its two end points. One wayof drawing a line segment will be simply starting with one end point and on the way of approachingthe other, turning on approach resembles our experience of drawing a line segment on paper, but it poses twoquestions.

5 First, on what criterion should we select a pixel? And second, if the criterion is set, howdo we efficiently select the required pixels? For the first question, let us defineXas the pixel onrowrand columnc, and the linesy=randx=crunning throughXand intersecting at its also denoteLas the line segment with end points (x1,y1) and (x2,y2) wherex1 x2. We thenwill have a criterion when|m|<1/2 (mis the slope) as follows:PixelXwill be turned on ify1< r < y2,x1< c < x2and if the intersecting point ofx=candLis within the boundaries ofX. We shall not be concerned with when the linecrossesx=cat one of the boundaries of pixelX, because choosing either pixel adjacentto this boundary has no effect on our line that we are using the typical mathematical coordinate system with origin at the lower leftcorner despite most device manufacturers putting the origin at the upper left corner of a screen.

6 Alsowe are going to use indices starting from 0 instead of 1. This is the typical approach in is for the case|m|<1/2. For future reference, we call it the gentle case. For the steepercase when|m|>1/2, we simply re-label thex-axis as they-axis andy-axis as thex-axis. Whenlabels are interchanged, those two cases are basically the same. They both have the absolute valueof slope smaller than 1 why do we bother to divide into two cases? We will see in a moment that this division intocases dramatically simplifies our problem of selecting pixels. When looking at Figure 1, we see thatpixel at (1,1) is selected and turned as well as the pixel at (2,2). The pixel at (0,0) is not selectedeven though the line segment starts within its boundaries.

7 The pixel at (2,1) is not selected eithereven though there is a portion of the line segment running through The First algorithm : DDAThe first algorithm we are going to introduce is DDA. It stands for Digital Differential we start to see how the algorithm works, let s first answer why we need to divide linedrawing into two cases and restrict ourselves only to the gentle case. Referring to Figure 1 andonly considering positive slope, notice that when the line segment starts from the pixel at (0,0), itfaces two choices. If it is gentle enough, it will enter the pixel at (1,0) and crossesx= 1 beforeleaving it. Otherwise, it will go into pixel (1,1) and cross its linex= 1 before leaving it. However,it will never be able to reach the pixel (1,2), because its slope is no larger than 1/2.

8 Therefore weonly need to choose one out of the two possible pixels. Furthermore, we already know where the twopixels are located. If the pixel where the line segment starts is at rowy0and columnx0, the twopixels we need to choose from will both be in the next columnx0+ 1. One of them will be in rowx0,same as the original pixel. The other will be in rowx0+ 1, only one level above the original our algorithm can be described as starting with one pixel, and scanning each column of pixelsfrom left to right. Every time when we are entering the next column, we either choose the pixel inthe same row as the pixel in the previous column, or we choose the pixel in the row one level abovethe pixel in the previous column. When the slope is negative, we still only have two pixels to choosefrom.

9 If the pixel we start from is at (x0y0), then the pixels we choose from are (x0+ 1,y0) and(x0+ 1,y0 1). For future explanations, we are going to use the grid in Figure 2 as representationof a screen. Notice the origin in the grid is the lower left corner of a rectangular screen. The pixelsbelowx-axis and the pixels to the left ofy-axis are not shown on screen. For simplicity, the upperand right boundaries of the screen are not 0y= 1y= 2x= 0x= 1x= 2 Figure 1: Criterion on how to select a pixelxyFigure 2: A Screen of Pixels3B0P0xyFigure 3: An Example of DDA AlgorithmB1P1xyFigure 4: The state of the program right after coloring a pixel in the second columnTo understand an algorithm , it is always helpful to have a sense of the idea behind it.

10 ForDDA, when we are scanning the columns one by one, the movement from one column to another isessentially the same as adding 1 each time to thex-coordinate. Since a straight line has a constantrate of change, we can exploit this property by addingm, the value of slope, to they-coordinateeach time we move to a new column. This is the idea behind DDA. To describe the implementationdetails, we define a crossing point to be the point where the line segment of interest crosses thecenter line of a column. We obtain the coordinates of first crossing pointP0as (x0,y0) and distancehbetweenP0andB0, which is the central point of the row boundary right belowP0. We usehtodetermine if we want to color subsequent pixels. When we move to the columnx0+ 1, we addmtoh.