An illustration of the possible different types of triangles might help here:
A row-scanning rasterizer first sorts the three vertices according to the y coordinates. There are six types of triangles, based on the y coordinates:
- y1 == y2 == y3: A horizontal line. Draw from min(x1,x2,x3) to max(x1,x2,x3) on that row. Not included in above illustration.
- y2 < y2 == y3: A "diverging" triangle (opens downwards). Leftmost in above illustration.
- y1 == y2 < y3: A "converging" triangle (opens upwards). Second from left in above illustration.
- y1 < y2 < y3 with xM = x1 + (x3 - x1)*(y2 - y1)/(y3 - y1) < x2: Second vertex is on the right side. Third from left in above illustration.
- y1 < y2 < y3 with xM = x1 + (x3 - x1)*(y2 - y1)/(y3 - y1) > x2: Second vertex is on the left side. Rightmost in above illustration.
- y1 < y2 < y3 with xM = x1 + (x3 - x1)*(y2 - y1)/(y3 - y1) == x2: Triangle is just a straight line. Not included in above illustration, can be handled by either of the two previous cases.
If you use two Bresenham lines in parallel, you must remember the minimum
x on each row
y for the left side, and the maximum
x on each row
y for the right side, and draw the horizontal line between those (including the end points).
A filler loop that can draw a single triangle of the red or blue type above, but not a combination of both, is the simplest to implement. Many triangles then involve running the filler loop twice, for
y1 <= y < y2 and for
y2 <= y <= y3.
Note that the filler loop could allow y coordinates smaller than the viewport minimum, and x coordinates outside the viewport. Then, it can draw triangles partially outside the viewport without issues. You simply avoid drawing any horizontal lines when
y is smaller than the viewport minimum
y coordinate, and draw only the part of the horizontal line that is within the viewport.
If you write a filler that can draw any triangle, you'll simply switch the error and delta terms in the inner loop if it enters
x == x2, y == y2.
If you use fixed-point arithmetic, you should include an adjustment term for the left and right sides, for calculating the starting and ending x coordinates for the horizontal line for each
y coordinate. (This corresponds to finding the minimum x included on the line on the left side, and maximum x included on the line on the right side.)
For the left side, the adjustment is zero if the slope is positive, and half a step if the slope is negative.
For the right side, the adjustment is zero if the slope is negative, and half a step if the slope is positive.
The slope itself, or the change in x coordinate whenever y changes, for the side from (xA, yA) to (xB, yB) is
dx = (xB - xA) / (yB - yA)Here's an example Python floating-point implementation:
x_min = 0
y_min = 0
x_max = 79
y_max = 39
def HLine(y, left, right):
line = [ ]
for x in range(x_min, x_max + 1):
if x >= left and x <= right:
line.append('#')
else:
line.append('.')
print('%3d: %s (%d)' % (y, ''.join(line), len(line)))
def Fill(x1,y1, x2,y2, x3,y3):
# Sort the points with increasing y
if y1 > y2:
x1,y1, x2,y2 = x2,y2, x1,y1
if y1 > y3:
x1,y1, x3,y3 = x3,y3, x1,y1
if y2 > y3:
x2,y2, x3,y3 = x3,y3, x2,y2
# Completely outside the viewport?
if y1 > y_max or y3 < y_min:
return
if min(x1, x2, x3) > x_max or max(x1, x2, x3) < x_min:
return
# Slope from (x1,y1) to (x2,y2)
if y1 < y2:
dx12 = (x2 - x1) / (y2 - y1)
else:
dx12 = 0
# Slope from (x1,y1) to (x3,y3)
if y1 < y3:
dx13 = (x3 - x1) / (y3 - y1)
else:
dx13 = 0
# Slope from (x2,y2) to (x3,y3)
if y2 < y3:
dx23 = (x3 - x2) / (y3 - y2)
else:
dx23 = 0
# Start at x1,y1
y,xL,xR = y1,x1,x1
if dx12 >= dx13:
# (x2,y2) is on the right side of the triangle
dxL, dxL2 = dx13, dx13
dxR, dxR2 = dx12, dx23
else:
# (x2,y2) is on the left side of the triangle
dxL, dxL2 = dx12, dx23
dxR, dxR2 = dx13, dx13
# Left adjustments
if dxL < 0:
axL = dxL/2
else:
axL = 0
if dxL2 < 0:
axL2 = dxL2/2
else:
axL2 = 0
# Right adjustments
if dxR > 0:
axR = dxR/2
else:
axR = 0
if dxR2 > 0:
axR2 = dxR2/2
else:
axR2 = 0
# Do not progress outside the viewport.
if y3 > y_max:
y3 = y_max
# Blitter loop
while y <= y3:
# Changeover point?
if y == y2:
dxL, axL = dxL2, axL2
dxR, axR = dxR2, axR2
# y within the viewport?
if y >= y_min:
# Adjust edges.
iL = int(xL + axL)
iR = int(xR + axR)
# Any part of horizontal line within viewport?
if iR >= x_min and iL <= x_max:
HLine(y, max(x_min, iL), min(iR, x_max))
# y step.
y = y + 1
xL = xL + dxL
xR = xR + dxR
if __name__ == '__main__':
# Fill(-35,-13, 75,13, 43,57)
# Fill(99,-2, 17,15, -12,43)
Fill(1,1, 78,15, 39,38)
There are three divisions (a fixed-point/float value divided by an integer) to get the slopes, and four halving of a fixed-point/float value. Lots of comparisons in the inner loop, though.
Home
Help
Search
Login
Register
