neilobremski
Experienced Member
I want to explain the results of my month of learning assembler and Bresenham lines by presenting a method of drawing pixel perfect triangles. This will be broken up into three blog posts, this first of which is about the purpose and the algorithm at a high level.
Triangles are the graphics primitive cornerstone of fast, interactive 3D (read: games!). This is the purpose to which I'll be using my triangles and my goal for drawing them is such that they are pixel perfect matches to their outlines. For example, if you drew lines [SUP][1][/SUP] between the three points, there is a single-pixel overlap between those lines and the contents of the triangle. This also means that if you drew an abutted triangle by reusing a pair of coordinates, then there will be a single-pixel overlap there as well.
My method for doing this is to draw two lines down from three sorted points starting at the top tip A and then one down to B (A to B) and the other to C (A to C). At each scanline [SUP][2][/SUP] a horizontal line segment is drawn that encompasses the pixels needed for both lines as well as the intervening space. When the scanline of point B is reached then the first line (1 to 2) is reconfigured towards point C (B to C) and the process continues to the bottom tip, point C.
I don't think this is anything new but I will admit I did no research, because I wanted to figure it out on my own. There were several false starts and a few "almost but not quite" algorithms that were shorter and faster. Of course, leaving out certain technicalities caused the results to be sub par and I couldn't rest until I'd gotten it pixel perfect. Here come the pix stepper!
Let's get more specific, starting with only the top half.
The first things to compute are the distances between the axes on each point: I call these two Side A (A to B) and Side B (A to C). These values are simply the difference between the two Y's and the two X's plus one for inclusiveness. This results in four integers that represent two fractions: XDistA / YDistA and XDistB / YDistB. I also compute the direction of the slope which is always horizontal since we're drawing down from sorted Y coordinates. Going left is -1 and going right is +1.
Now I can start drawing right away, starting at the scanline of point A's Y coordinate and moving down until point B is reached. There are four important values tracked, the first pair are the coordinates of the inner sides of the triangle, XSideA and XSideB, which are both initialized to point A's X. The second pair are the error accumulators for each side, ErrA and ErrB, which is a fancy way of saying the equally fancy "fractional remainder of each side's step".
On each scanline, the X distance is added for both error accumulators and the result is how many pixels to step each inner side coordinate:
If you were to draw a line segment between the two inner side coordinates, XSideA and XSideB, then you would get a filled triangle that does not overlap with its (potential) outline. In this case, however, you'll have to remember that the first scanline of the triangle will always be blank because both values are the same and the length of the segment will be zero. I call these two values the "bones" of the triangle: if you light only these points then you'll have points which on one side would be the fill (flesh) and on the other would be the outline (skin).
But remember my goal is to draw the triangle inclusive of its outline so there is additional processing each scanline to figure out two more values: XBeg and XEnd. To do this I copy the inner side values (that I just stepped) and then add one pixel in the opposite direction if the step was one or greater. This gives AdjSideA and AdjSideB. Now I can decide to use either, both, or none of these side values if they exceed the XBeg and XEnd represented by the current inner side values.
Voila! Drawing a line segment from XBeg to XEnd is now pixel perfect. This process is repeated for the bottom half with one caveat: the first scanline of the bottom half must be skipped because it overlaps the last scanline of the top half. This means it is possible, in the case of a flat bottom triangle, to have no bottom half at all!
Alright, that's enough blabbering on the high level. Next up I'll talk pseudo code ...
Footnotes:
[SUP][1][/SUP] General lines are drawn by lighting the current pixel, stepping by a fractional amount based on X/Y distances, and then repeating until complete. Read more at my post on DDA Lines.
[SUP][2][/SUP] A scanline is a single row of pixels per a particular vertical (Y) coordinate. Thus the first scanline is the first row of pixels, starting at Y=0.
Triangles are the graphics primitive cornerstone of fast, interactive 3D (read: games!). This is the purpose to which I'll be using my triangles and my goal for drawing them is such that they are pixel perfect matches to their outlines. For example, if you drew lines [SUP][1][/SUP] between the three points, there is a single-pixel overlap between those lines and the contents of the triangle. This also means that if you drew an abutted triangle by reusing a pair of coordinates, then there will be a single-pixel overlap there as well.
My method for doing this is to draw two lines down from three sorted points starting at the top tip A and then one down to B (A to B) and the other to C (A to C). At each scanline [SUP][2][/SUP] a horizontal line segment is drawn that encompasses the pixels needed for both lines as well as the intervening space. When the scanline of point B is reached then the first line (1 to 2) is reconfigured towards point C (B to C) and the process continues to the bottom tip, point C.
I don't think this is anything new but I will admit I did no research, because I wanted to figure it out on my own. There were several false starts and a few "almost but not quite" algorithms that were shorter and faster. Of course, leaving out certain technicalities caused the results to be sub par and I couldn't rest until I'd gotten it pixel perfect. Here come the pix stepper!
Let's get more specific, starting with only the top half.
The first things to compute are the distances between the axes on each point: I call these two Side A (A to B) and Side B (A to C). These values are simply the difference between the two Y's and the two X's plus one for inclusiveness. This results in four integers that represent two fractions: XDistA / YDistA and XDistB / YDistB. I also compute the direction of the slope which is always horizontal since we're drawing down from sorted Y coordinates. Going left is -1 and going right is +1.
Now I can start drawing right away, starting at the scanline of point A's Y coordinate and moving down until point B is reached. There are four important values tracked, the first pair are the coordinates of the inner sides of the triangle, XSideA and XSideB, which are both initialized to point A's X. The second pair are the error accumulators for each side, ErrA and ErrB, which is a fancy way of saying the equally fancy "fractional remainder of each side's step".
On each scanline, the X distance is added for both error accumulators and the result is how many pixels to step each inner side coordinate:
XSide += ( Step = ( (Err + XDist) / YDist ) * Dir )
If you were to draw a line segment between the two inner side coordinates, XSideA and XSideB, then you would get a filled triangle that does not overlap with its (potential) outline. In this case, however, you'll have to remember that the first scanline of the triangle will always be blank because both values are the same and the length of the segment will be zero. I call these two values the "bones" of the triangle: if you light only these points then you'll have points which on one side would be the fill (flesh) and on the other would be the outline (skin).
But remember my goal is to draw the triangle inclusive of its outline so there is additional processing each scanline to figure out two more values: XBeg and XEnd. To do this I copy the inner side values (that I just stepped) and then add one pixel in the opposite direction if the step was one or greater. This gives AdjSideA and AdjSideB. Now I can decide to use either, both, or none of these side values if they exceed the XBeg and XEnd represented by the current inner side values.
XBeg = (Dir < 0 && AdjSide < XBeg ? AdjSide : XBeg)
XEnd = (Dir > 0 && AdjSide > XEnd ? AdjSide : XEnd)
XEnd = (Dir > 0 && AdjSide > XEnd ? AdjSide : XEnd)
Voila! Drawing a line segment from XBeg to XEnd is now pixel perfect. This process is repeated for the bottom half with one caveat: the first scanline of the bottom half must be skipped because it overlaps the last scanline of the top half. This means it is possible, in the case of a flat bottom triangle, to have no bottom half at all!
Alright, that's enough blabbering on the high level. Next up I'll talk pseudo code ...
Footnotes:
[SUP][1][/SUP] General lines are drawn by lighting the current pixel, stepping by a fractional amount based on X/Y distances, and then repeating until complete. Read more at my post on DDA Lines.
[SUP][2][/SUP] A scanline is a single row of pixels per a particular vertical (Y) coordinate. Thus the first scanline is the first row of pixels, starting at Y=0.