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.