## 2D Primatives

Toby Opferman http://www.opferman.net toby@opferman.net 2D Primatives In this section we introduce some code and we introduce some more theory on 2D. Then in the next section, we introduce 3D using the 2D primatives. Lines, Circles, Rectangles, Triangles, and pixels are all graphics primatives. Everything can be made up of these primatives, even 3D graphics. Let us start out with Lines. A line in computer graphics is really a line segment. It has a start point, an end point and a slope. Now, we need a way to draw a line on the screen. Well, if the line is horizontal, that is from (X1, Y1) to (X2, Y2) Y1 = Y2, we have a horizontal line. We can determine the length of this line is X2 - X1 and draw it such that: FOR X = X1 to X2 PutPixel(X, Y1) END FOR In a general pesudo code. If a line is Verticle, that is X1 = X2 for (X1, Y1) - (X2, Y2) we can draw it such that FOR Y = Y1 to Y2 PutPixel(X1, Y) END FOR Now, when we work with graphics, we are going to be dealing with linear memory. That is, Y is defined as Y*MaxX. This is because in order to get to the line we need, we have to Multiply Y by the length of the width of the screen. Then, we add X. Let's say we have this screen: 8x5: (All screens mxn are indexed 0 to (m-1), 0 to (n-1)) 0 1 2 3 4 5 6 7 0 1 2 3 4 And let's say it's actualy a linear screen. That is, the values to get to a position are: 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 8 9 10 11 12 13 14 15 2 16 17 18 19 20 21 22 23 3 24 25 26 27 28 29 30 31 4 32 33 34 35 36 37 38 39 Now, to get a location on the screen, you have "Screen". You need to add 1 number to it go to go to the location. That is, this matrix is just imaginary, arbitrary, we only like to picture it as a matrix, really, it's just a straight buffer from 0 to 39. If Y = 0 and X = 0 then Screen + Y + X = 0 Now, the max X is 8. So, Screen + Y*8 + X = Location. Let's see: Y = 3, X = 4 Y*8 + X = (3)*8 + 4 = 24 + 4 = 28 Look back above or at this lower simplified graph. 0 1 2 3 4 5 6 7 0 1 2 3 28 4 That is the correct linear combination. 8 = 2^3 So Y (Bit Shift Left 3) is the same thing. Let us look at that way: Y = 3, X = 4 Now, instead of multiplying 8, we will bitshift. Y<<3 + X 3 in Binary = 00000011 Shift if left 3 places 00011000 2^4+2^3 = 16 + 8 = 24 24 + X = 24 + 4 = 28 there's your answer. Why show you this? Well, graphics is usually very computational and processor consuming. Bit shifting is faster than multiplication on a computer especially. This tutorial is NOT going to teach you how to do this, I am just showing you that it is your best interest to look at things in different lights and learn certain optimizations. If you don't know about binary, you should learn. There is a tutorial under DOX that has Base Conversions on it (Assembly tutorial 1) that you should read. Second thing I want to mention is a Double Buffer. Video memory is slow and plus you don't want to be drawing on it while someone is viewing it. You want to have an offscreen linear buffer the same size as the screen. That way, you can draw on that and just blast that to the screen all at once. And it's faster, video memory is always being accessed by the video card. Ok, back to drawing lines. If we want to draw a diaginal line, it's a bit of work, but a guy named Bresenham came up with an algorithm to draw lines. To draw a line, you want to get the change in X and the change in Y. Here is the theory behind the algorithm. You have a line (X1, Y1) to (X2, Y2) For our example we will use (10, 4) to (20, 10) We get a Delta X and a Delta Y (Delta means change, so Change in Y and Change in X) Delta X = 20 - 10 = 10 Delta Y = 10 - 4 = 6 The Delta X is greater than Delta Y so we will plot along the X axis. That way, we have more room to adjust the error for Y's descent. So, we want a loop from 0 to 10. At first, we just plot at (10, 4), the starting point. 10 11 12 13 14 15 16 17 18 19 20 4 * 5 6 7 8 9 10 Now, we have an error counter. Which we will start off at 0, but now every time we plot we will add the change of the variable that is NOT being plotted against. Hence, we are moving along the X acess. What we want to do is divide up Y so that it is evenly divided amonst the delta of X. Error = Error + Delta Y Error is now 6. We now increment X1 by 1 (Positive since we are going in the positive direction) X1 is now 11. Second time thru the loop we are at (11, 4) We plot: 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 6 7 8 9 10 We add the error Error = Error + Delta Y Error = 6 + 6 = 12 Now, Error > Delta X. So, we need to do some adjusting of the line. We want to subtract DeltaX FROM the error to reset it to a correct error position. Error = Error - Delta X Error = 12 - 10 = 2 Error = 2 Now, we want to increment Y1 by it's direction (Which is Positive) so we add 1. Y1 = Y1 + 1 And again, we add 1 to X1. Now, we have (12, 5) We plot 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * 6 7 8 9 10 We add the error Error = Error + Delta Y Error = 2 + 6 = 8 Error is less than Delta X Add 1 to X1 Now we have (13, 5) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 7 8 9 10 We add the error Error = Error + Delta Y Error = 8 + 6 = 14 Now, Error > Delta X. So, we need to do some adjusting of the line. Error = Error - Delta X Error = 14 - 10 = 4 Error = 4 Now, we want to increment Y1 by it's direction (Which is Positive) so we add 1. Y1 = Y1 + 1 And again, we add 1 to X1. Now we have (14, 6) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 8 9 10 We add the error Error = Error + Delta Y Error = 4 + 6 = 10 Error is equal to Delta X So, we need to do some adjusting of the line. Error = Error - Delta X Error = 10 - 10 = 0 Error = 0 Add 1 to Y1 Add 1 to X1 Now we have (15, 7) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 * 8 9 10 We add the error Error = Error + Delta Y Error = 0 + 6 = 6 And again, we add 1 to X1. Now we have (16, 7) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 * * 8 9 10 We add the error Error = Error + Delta Y Error = 6 + 6 = 12 Error is greater than Delta X Error = Error - Delta X = 2 Y1 = Y1 + 1 Add 1 to X1 Now we have (17, 8) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 * * 8 * 9 10 We add the error Error = Error + Delta Y Error = 2 + 6 = 8 +++ And again, we add 1 to X1. Now we have (18, 8) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 * * 8 * * 9 10 We add the error Error = Error + Delta Y Error = 8 + 6 = 14 Error > Delta X Error = Error - Delta X = 4 Y1 = Y1 + 1 And again, we add 1 to X1. Now we have (19, 9) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 * * 8 * * 9 * 10 We add the error Error = Error + Delta Y Error = 4 + 6 = 10 Error = Delta X Error = Error - Delta X = 0 Y1 = Y1 + 1 And again, we add 1 to X1. Now we have (20, 10) 10 11 12 13 14 15 16 17 18 19 20 4 * * 5 * * 6 * 7 * * 8 * * 9 * 10 * And now X = 10, so the loop is done and so is the line. As you can see, it's a pretty good algorithm. Here is the Pseudo Code: Delta X = X2 - X1 Delta Y = Y2 - Y1 IF Delta X < 0 THEN Sign Delta X = -1 ELSE Sign Delta X = 1 END IF IF Delta Y < 0 THEN Sign Delta Y = -1 ELSE Sign Delta Y = 1 END IF Delta X = Sign Delta X * Delta X + 1 Delta Y = Sign Delta Y * Delta Y + 1 ERROR = 0 IF Delta X >= Delta Y THEN FOR X = 0 TO Delta X - 1 Plot(X1, Y1) ERROR = ERROR + Delta Y IF ERROR >= Delta X THEN ERROR = ERROR - Delta X Y1 = Y1 + Sign Delta Y END IF X1 = X1 + Sign Delta X END FOR ELSE FOR Y = 0 TO Delta Y - 1 Plot(X1, Y1) ERROR = ERROR + Delta X IF ERROR >= Delta Y THEN ERROR = ERROR - Delta Y X1 = X1 + Sign Delta X END IF Y1 = Y1 + Sign Delta Y END FOR END IF The next thing you will want to learn is how to make a triangle. Since any polygon is just a bunch of triangles formed together, you get a fast triangle drawing function you can draw them all. Now, obviously when I say draw a triangle I'm not talking just connecting 3 lines. I am talking about drawing the real solid triangle. You will laugh at this, but not only do we have to split polygons up into triangles, but we have to split triangles up into triangles! See, we want to be able to draw horizontal lines very easily. So, we make that we have 2 types of triangles. Flat Top and Flat bottom. If a triangle isn't one of those two, we make it one. Exmaple: Take this triangle: |\ | \ | \ | \ | \ | \ | / | / | / | / | / |/ Divide it like so: |\ | \ | \ | \ | \ |_____\ | / | / | / | / | / |/ Now you have 2 seperate triangles: |\ | \ | \ | \ | \ |_____\ _____ | / | / | / | / | / |/ A flat bottom and a flat top. How do you split it? You just need 1 more point. First thing, you want to sort the points. You have 3 points. (X1, Y1), (X2, Y2), (X3, Y3) This is how you sort them: IF Y1 > Y2 THEN Swap(Y1, Y2) Swap(X1, X2) END IF IF Y1 > Y3 THEN Swap(Y1, Y3) Swap(X1, X3) END IF IF Y2 > Y3 THEN Swap(Y2, Y3) Swap(X2, X3) END IF To test for a Flat Top Triangle: IF Y1 = Y2 THEN FlatTop END IF To Test For A Flat Bottom Triangle: IF Y2 = Y3 THEN FlatBottom END IF Also, Remeber: IF Y1 = Y2 AND Y2 = Y3 THEN This is a line END IF IF X1 = X2 AND X2 = X3 THEN This is a line END IF Also, if Any 2 Vertexs are Equal, Then that is a line as well. IF X1 = X2 AND Y1 = Y2 THEN This is a line END IF IF X2 = X3 AND Y3 = Y2 THEN This is a line END IF Y3 Cannot Equal Y1 unless Y2 Equals Y1 since you sorted them. Now, you have them sorted, say you have these triangles: (5, 10), (5, 15), (10, 15) Flat Bottom (5, 10), (5, 10), (10, 15) Flat Top (5, 8), (6, 12), (15, 15) Irregular Well, on an irregular triangle, the middle point, (X2, Y2) has to create the new point to split the triangle. We will call this point (NewX, NewY) For Obvious reasons, NewY = Y2. We are splitting these Horizontally. So, NewY will be the same as Y2. Now, we need to computer NewX. Here is our triangle: 5 6 7 8 9 10 11 12 13 14 15 8 * 9 10 11 12 * 13 14 15 * I can't put the lines in so you are going to have to imagine. Now, you know that the NewX should be on line 12 and on the line between X1 and X3. 5 6 7 8 9 10 11 12 13 14 15 8 * 9 10 11 12 * 13 14 15 * (5, 8), (6, 12), (15, 15) Irregular (X3 - X1) = Delta X (10) Now, you can divide 10 by 15. (Delta X)/Y3 10/15 = 0.666666666666666666666666666666667 That is the change in X from X1 to X3 So, .6666 * Y2 = NewX That's .6666 * 12 = 8 NewX = 8 5 6 7 8 9 10 11 12 13 14 15 8 * 9 10 11 12 * * 13 14 15 * Now, the triangle is split. Split Triangles are drawn like so: FlatBottom (X1, Y1), (X2, Y2), (NewX, Y2) FlatTop (X2, Y2), (NewX, Y2), (X3, Y3) Now, you want to draw a triangle with a flat bottom. What we need to do is the same thing as the line algorithm did. (X1, Y1) (X2, Y2) (NewX, Y2) We start at (X1, Y1). We plot a dot. Now, we need to change the Length of our drawing gradually so the Right side will end up at (NewX, Y2). AND, we also need to change the start position of our drawing so the Left side ends up at (X2, Y2). NewX and X2 in Ascending order. IF X2 > NewX THEN Swap(X2, NewX) END IF Next, you want to find out Delta X2 and Delta NewX Delta Y = (Y2 - Y1) Delta X2 = (X1 - X2)/(Delta Y) Delta NewX = (NewX - X1)/(Delta Y) Just like the line. We make it porportional. We get the distance from X1 to X2 (And X1 to NewX) And we make it porportional. i.e., every New Y, it goes up a portion. This is what we need. (Now, triangles NEED to work with floats. But, the Line aglorithm I showed you works fine with integers.) (5, 8), (6, 12), (15, 15) Was our triangle. We now have: (5, 8), (6, 12), (8, 12) Flat Bottom (6, 12), (8, 12), (15, 15) Flat Top Delta Y = (12 - 8) = 4 Delta X2 = (6 - 5)/4 = 1/4 = .25 Delta NewX = (8 - 5)/4 = 3/4 = .75 Get an End X. EndX = Delta NewX + X1 + .50 = .75 + 5.50 = 6.25 Add on .50 to round up. Length = 1 Now, we start the loop. Now, as you can see, if we every line do the following: Plot(X1, Y1) Length 1 Y1 = Y1 + 1 = 9 X1 = X1 + Delta X2 = 5.25 Length = EndX - X1 = 6.25 - 5.25 = 1 (Add on 1 so you plot 2 pixels) +1 = 2 EndX = EndX + Delta NewX = 5.75 + .75 = 6.50 Next round: Plot(X1, Y1) Length 2 These are rounded to integers so, Plot(5, 9) Y1 = Y1 + 1 = 10 X1 = X1 + Delta X2 = 5.25 + .25 = 5.50 Length = EndX - X1 = 6.50 - 5.50 = 1 (Add on 1 so you plot 2 pixels) + 1 = 2 EndX = EndX + Delta NewX = 6.50 + .75 = 7.25 Next Round: Plot(6, 10) Length 2 Y1 = Y1 + 1 = 11 X1 = X1 + Delta X2 = 5.50 + .25 = 5.75 Length = EndX - X1 = 7.25 - 5.75 = 2 (Add on 1 so you plot 2 pixels) + 1 = 3 EndX = EndX + Delta NewX = 7.25 + .75 = 8 Next Round: Plot(6, 11) Length 3 Y1 = Y1 + 1 = 12 X1 = X1 + Delta X2 = 5.75 + .25 = 6 Length = EndX - X1 = 8 - 6 = 2 (Add on 1 so you plot 2 pixels) + 1 = 3 EndX = EndX + Delta NewX = 8 + .75 = 8.75 Plot(6, 12) Length 3 And it looks like this: 5 6 7 8 9 10 11 12 13 14 15 8 * 9 * * 10 * * 11 * * * 12 * * * 13 14 15 * Here is pseudo code: IF X2 > X3 THEN Swap(X2, X3) END IF Delta X = (X2 - X1)/(Y2 - Y1) NewDelta = (X3 - X1)/(Y2 - Y1) BegX = X1 EndX = NewDelta + X1 + .5 Length = 1 FOR Y = Y1 TO Y2 Plot(BegX, Y, Length) BegX = BegX + Delta X Length = (EndX - BegX) + 1 EndX = EndX + NewDelta END FOR Seems simple enough. But something is missing. If you do run that, you do see that some bigger triangles look ok and some triangles look a little messed up. We need to perfect this so the triangle will be more perfect. Can you think of any ideas? Sure, we can try the .5 to .75 with a little bit of difference, but not what we want. These triangles are pretty rigid, see if you can figure out a way to make them more accurate. These triangles need to be pretty decent together because, we are supposed to be able to fit triangles together to make polygons. If they aren't working propertly, you will see holes in them, pixels missing. The next would be to do the flat top triangles and as you figured it's pretty much the same as the flat bottom triangles. Well, we have A line from (X1, Y1) to (X2, Y2). We want these to merge to (X3, Y3). But, instead of wasting my time telling you how to do this, I will now go into another method. First thing first, like always, get deltas. The change of X as Y changes by 1. That is how we work things. Just like I stated in the line drawing and in the flat top. We want how much X changes as we change Y by 1 so we can appropriately increment X. Now, if it is not 1:1 (That is, Delta X = 1, which means for every Y + 1 you have X + 1 (A perfect situation!)), we don't have .5 of a pixel, so we must approximate and round. That is why the .5 was added onto DeltaX of the one above. We need to figure out a good approximation. But, I am not going to show you bottom triangle code. Instead, we are going to step up a bit and try to fix the problem. I only made the crap code above for better visualization. What if we forget about creating a middle X. What if we forget about checking for bottom and top triangles? Well, let's see this better Pseudo Code. * First, like above, we sort. IF Y1 > Y2 THEN Swap(Y1, Y2) Swap(X1, X2) END IF IF Y1 > Y3 THEN Swap(Y1, Y3) Swap(X1, X3) END IF IF Y2 > Y3 THEN Swap(Y2, Y3) Swap(X2, X3) END IF * And again, we need the deltas, but instead of splitting the triangle, let us * get the deltas for each line. Delta X1 = X2 - X1 Delta X2 = X3 - X2 Delta X3 = X3 - X1 Delta Y1 = Y2 - Y1 Delta Y2 = Y3 - Y2 Delta Y3 = Y3 - Y1 * Now, Let use create the Deltas to be used in the loops IF Delta Y1 IS NOT 0 THEN D1 = Delta X1 / Delta Y1 ELSE D1 = 0 END IF * Now, you can't divide by 0, so we need a check in. IF Delta Y2 IS NOT 0 THEN D2 = Delta X2 / Delta Y2 ELSE D2 = 0 END IF IF Delta Y3 IS NOT 0 THEN D3 = Delta X3 / Delta Y3 ELSE D3 = 0 END IF * Now, we have the loops. We want to loop to where we WOULD have split, then * change how we create the lines and loop again. * The Flat Bottom Triangle FOR V = Y1 TO Y2 * You start at X1 and you Add the current Y value subtracted by Y1. Then you multiply * The change in X as Y approcahes the maximum. PlotX1 = X1 + (V - Y1)*D1; PlotX2 = X1 + (V - Y1)*D3; HorizontalLine(PlotX1, PlotX2, V) END FOR * The Flat Top Triangle FOR V = Y2 TO Y3 * You start at X2 and you Add the current Y value subtracted by Y2. Then you multiply * The change in X as Y approcahes the maximum. PlotX1 = X2 + (V - Y2)*D2; PlotX2 = X1 + (V - Y1)*D3; HorizonalLine(PlotX, V) END FOR NOTE: The parameters for this arbitrary Horizontal Line Function are: HorizontalLine(X1, X2, Y) If you don't FULLY understand this, it is ok. With modern APIs you don't have to anyway. And even with no APIs, you can just use the psuedo code I gave. I made the first one, with the shitty right side, in ten minutes for this tutorial. But, the above version I did not make myself, but it is a better version. I leave optimizations up to you now however. The above works on the same principal as the one I came up with, but it works better. For primative 3D beginnings a circle function is not needed. If you want to draw a circle, A SIMPLE function would just be: FOR THETHA = 0 TO 360 PlotPixel(Radius*COS(THETA), Radius*SIN(THETA)) END FOR (Notice in my examples I ignore a "color" parameter, these are arbitrary functions, so they are omitted.) There is a more optimized way to do a circle, with integers. As you also could tell, that will only plot 360 pixels. If your circle has a radius that on a computer screen would need > 360 pixels, you would see start to see spaces between the pixels of the circle. This tutorial has served it's purpose and theory on drawing a circle is irrevevant and is left up to your own research if you are interested. Or, you could think of how to do it on your own. For the basics of 3D, A line drawing function and a triangle drawing function are definately what you need. You need to get really familar with the triangle function. Since, not only is it used to draw a solid surface, but texture mapping needs to be drawn in combination with it, and so does lighting. It's pretty much the most important primative. Now, yes, once you get to graphics APIs like DirectX and OpenGL you don't have to worry about it anymore since most things are done for you. This is behind the scenes tho, you should know how things work so you have a better understanding even if you just use an API. Also remeber, these routines are NOT optimized, they are even just pseudo code. Another important aspect of 3D and game programming alone is speed. I would always look for faster and better methods.