@BrianHG has pointed out, a diagonal line with an angle less than 45 degrees from horizontal will sometimes have more than one pixel on an edge with the same Y value, creating an overwritten line filling that segment of the triangle.
screen = [[' '] * 79 for y in range(23)]
def fill_triangle(x0, y0, x1, y1, x2):
# Fills a flat-bottomed triangle with apex at (x0, y0) and
# lower vertices at (x1, y1), (x2, y1). Assumes x1 <= x0 <= x2
# and y0 <= y1.
xL = xR = x0
y = y0
dxL = x0 - x1
dxR = x2 - x0
dy = y1 - y0
eL = eR = 0
n = dy
while n > 0:
fill_raster_line(xL, xR, y)
eL += dxL
while eL > 0:
xL -= 1
eL -= dy
eR += dxR
while eR > 0:
xR += 1
eR -= dy
y += 1
n -= 1
def fill_raster_line(x0, x1, y):
x = x0
n = x1 - x0 + 1
while n > 0:
draw_pixel(x, y)
x += 1
n -= 1
def draw_pixel(x, y):
screen[y][x] = '*'
fill_triangle(50, 5, 10, 20, 60)
for row in screen:
print(''.join(row))
Here's some python3 code I wrote to try out the idea. It runs two Bresenham line algorithms in parallel. The outer loop takes one step in y on each iteration, and inner loops advance the left and right x coordinates the appropriate amount. It draws each pixel exactly once.
There may be a more efficient way that avoids the inner loops, but I haven't thought about it very deeply yet.
Sub drawTriangle (ByVal Ax as Integer, byval Ay as Integer, byval Bx as Integer, byval By as Integer, byval Cx as Integer, byval Cy as Integer, byval color_val As UByte)
Dim As Integer new_Ax,new_Ay,new_Bx,new_By,new_Cx,new_Cy
Dim As Integer dx1,dy1,x1,y1,sx1,sy1,errd1,magic1
Dim As Integer dx2,dy2,x2,y2,sx2,sy2,errd2,magic2
Dim As Integer dx3,dy3,x3,y3,sx3,sy3,errd3,magic3
Dim As Boolean is_done
If (Ay > By > Cy ) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Bx
new_By = By
new_Cx = Cx
new_Cy = Cy
Else If (By > Cy > Ay) Then
new_Ax = Bx
new_Ay = By
new_Bx = Cx
new_By = Cy
new_Cx = Ax
new_Cy = Cy
Else If (Cy > Ay > By) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Ax
new_By = Ay
new_Cx = Bx
new_Cy = By
Else If (Ay > Cy > By) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Cx
new_By = Cy
new_Cx = Bx
new_Cy = By
Else If (Cy > By > Ay) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Bx
new_By = By
new_Cx = Ax
new_Cy = Ay
Else If (By > Ay > Cy) Then
new_Ax = Bx
new_Ay = By
new_Bx = Ax
new_By = Ay
new_Cx = Cx
new_Cy = Cy
EndIf
Rem bounding box's width and height for the three line generators
Rem And set the loop's sign
Rem # Line Gen #1
dx1 = new_Cx - new_Ax
dy1 = new_Cy - new_Ay
Rem # Line Gen #2
dx2 = new_Bx - new_Ax
dy2 = new_By - new_Ay
Rem # Line Gen #3
dx3 = new_Cx - new_Bx
dy3 = new_Cy - new_By
If (dx1 < 0) Then
dx1 = -dx1
sx1 = -1
Else
sx1 = 1
End If
If (dy1 > 0) Then
dy1 = -dy1
sy1 = 1
Else
sy1 = -1
End If
If (dx2 < 0) Then
dx2 = -dx2
sx2 = -1
Else
sx2 = 1
End If
If (dy2 > 0) Then
dy2 = -dy2
sy2 = 1
Else
sy2 = -1
End If
If (dx3 < 0) Then
dx3 = -dx3
sx3 = -1
Else
sx3 = 1
End If
If (dy3 > 0) Then
dy3 = -dy3
sy3 = 1
Else
sy3 = -1
End If
magic1 = 0
errd1 = dx1 + dy1
x1 = new_Ax
y1 = new_Ay
magic2 = 0
errd2 = dx2 + dy2
x2 = new_Ax
y2 = new_Ay
magic3 = 0
errd3 = dx3 + dy3
x3 = new_Bx
y3 = new_By
For screen_Y = new_Ay To new_Cy
draw_pixel (x1,y1,color_val)
magic1 = errd1 shl 1
if (magic1 > dy1) Then
errd1 += dy1
x1 += sx1
End If
if (magic1 < dx1) Then
errd1 += dx1
y1 += sy1
End If
draw_pixel (x2,y2,color_val)
magic2 = errd2 shl 1
if (magic2 > dy2) Then
errd2 += dy2
x2 += sx2
End If
if (magic2 < dx2) Then
errd2 += dx2
y2 += sy2
End If
draw_pixel (x3,y3,color_val)
magic3 = errd3 shl 1
if (magic3 > dy3) Then
errd3 += dy3
x3 += sx3
End If
if (magic3 < dx3) Then
errd3 += dx3
y3 += sy3
End If
Next
End Sub
Your other choice is to do M.N style floating point (still integer, just that you use the upper 12 bits as the mantissa) delta-X addition for every Y increment. This means a 24 bit adder and a little additional setup math at the beginning. You will also need to deal with how the edges of each line are filled especially when connecting 2 triangles to generate filled 4 sided polygons. (.N is the err added at every Y step, however, it needs to be per-determined an can now be a value greater than 1 for every Y increment.)
How do you want to proceed.
div = abs( ay - by )
if div = 0 then div=1
delta_x_per_y_increment = ( bx-ax ) / div
xp = ax
For yp = ay to by
draw_pixel ( int(xp),int(yp),color_val)
xp=xp + delta_x_per_y_increment
next yp
There must be a simpler way of ordering the vertices at the start than what I've done?
After the ordering IF..ELSE IF structure, I set up some of the variables for the three line generators, sufficient to run all three in parallel.
we need to make sure y2 has incremented as well, don't we? Or will they both increment at the same time by some weird conjunction of maths and the planets?
The M.N style sounds simpler and perhaps easier for me to grasp,
There must be a simpler way of ordering the vertices at the start than what I've done?You could hard-code a 3-element bubble sort.
Keep in mind that these kinds of setup tasks can be done in software. I'd concentrate on just doing the parts that really need to be fast in hardware, at least initially. You can think about migrating some of the setup into hardware later if you want.
Google "sorting network" for some ideas on how to implement a sort in hardware.QuoteAfter the ordering IF..ELSE IF structure, I set up some of the variables for the three line generators, sufficient to run all three in parallel.You only need to run 2 line generators in parallel. When you reach the middle vertex, switch one of them from doing the upper half to doing the lower half.Quotewe need to make sure y2 has incremented as well, don't we? Or will they both increment at the same time by some weird conjunction of maths and the planets?In my Python code I only have one y variable shared between the two line generators, so this issue doesn't arise.
Despite what I said earlier, I think it's better to think of the triangle filler as its own thing, and not try to make it share hardware with whatever you're using to draw lines. Instead of "liine generators" think of "side generators". There are two of them, but they're not completely independent, they share some state.
At worst, you pixel drawing engine / command may have to draw a few repetitious pixels on a line, but since they are adjacent pixels, you are only talking 1/125 millionth of a second per extra dot.
The M.N style sounds simpler and perhaps easier for me to grasp,It's certainly easier to get one's head around! The only reason I didn't suggest it myself is because of the need for divisions during the setup, but like I said before, you can leave that to software for now.
A nice property of the fixed-point approach is that a step in the y direction can be done in a single clock cycle, instead of potentially requiring multiple cycles to update the x coordinates.
Another benefit is that it may be easier to adapt for more complicated shapes such as circles and bezier curves if you want to go there later.
Another benefit is that it may be easier to adapt for more complicated shapes such as circles and bezier curves if you want to go there later.
Remember, we got it backwards, we want point new_A to have the lowest Ay and point new_Cy to have the highest Cy.
If (Ay > By > Cy ) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Bx
new_By = By
new_Cx = Ax
new_Cy = Ay
ElseIf (By > Cy > Ay) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Cx
new_By = Cy
new_Cx = Bx
new_Cy = By
ElseIf (Cy > Ay > By) Then
new_Ax = Bx
new_Ay = by
new_Bx = Ax
new_By = Ay
new_Cx = Cx
new_Cy = Cy
ElseIf (Ay > Cy > By) Then
new_Ax = Bx
new_Ay = By
new_Bx = Cx
new_By = Cy
new_Cx = Ax
new_Cy = Ay
ElseIf (Cy > By > Ay) Then
new_Ax = Ax
new_Ay = Ay
new_Bx = Bx
new_By = By
new_Cx = Cx
new_Cy = Cy
ElseIf (By > Ay > Cy) Then
new_Ax = Cx
new_Ay = Cy
new_Bx = Ax
new_By = Ay
new_Cx = Bx
new_Cy = By
EndIf
The geo.bas I've uploaded may have the 'divide' method of generating a line in the triangle_filled routine, however, you will erase that little line loop and place in the work you begun. Since we have a working Bresenham's in Verilog, we will use one with with 3 set array which you may increment 1 of 3 at a time. Follow my instructions to generate a proper rasterized fill.
Sub drawFilledTriangle (ByVal x0 as Integer, byval y0 as Integer, byval x1 as Integer, byval y1 as Integer, byval x2 as Integer, byval y2 as Integer, byval color_val As UByte)
Dim As double ax,ay,bx,by,cx,cy,div,xp,yp,delta_x_per_y_increment
Dim As Double x[2],y[2]
If (y0 > y1 > y2 ) Then
x[0] = x2
y[0] = y2
x[1] = x1
y[1] = y1
x[2] = x0
y[2] = y0
ElseIf (y1 > y2 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x2
y[1] = y2
x[2] = x1
y[2] = y1
ElseIf (y2 > y0 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x0
y[1] = y0
x[2] = x2
y[2] = y2
ElseIf (y0 > y2 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x2
y[1] = y2
x[2] = x0
y[2] = y0
ElseIf (y2 > y1 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x1
y[1] = y1
x[2] = x2
y[2] = y2
ElseIf (y1 > y0 > y2) Then
x[0] = x2
y[0] = y2
x[1] = x0
y[1] = y0
x[2] = x1
y[2] = y1
EndIf
div = abs( y[0] - y[2] )
If div = 0 then div = 1
delta_x_per_y_increment = ( x[1] - x[0] ) / div
xp = x[0]
For yp = y[0] to y[2]
draw_pixel ( int(xp),int(yp),color_val )
xp= xp + delta_x_per_y_increment
Next yp
End Sub
Okay, got this far:Code: [Select]Sub drawFilledTriangle (ByVal x0 as Integer, byval y0 as Integer, byval x1 as Integer, byval y1 as Integer, byval x2 as Integer, byval y2 as Integer, byval color_val As UByte)
Dim As double ax,ay,bx,by,cx,cy,div,xp,yp,delta_x_per_y_increment
Dim As Double x[2],y[2]
If (y0 > y1 > y2 ) Then
x[0] = x2
y[0] = y2
x[1] = x1
y[1] = y1
x[2] = x0
y[2] = y0
ElseIf (y1 > y2 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x2
y[1] = y2
x[2] = x1
y[2] = y1
ElseIf (y2 > y0 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x0
y[1] = y0
x[2] = x2
y[2] = y2
ElseIf (y0 > y2 > y1) Then
x[0] = x1
y[0] = y1
x[1] = x2
y[1] = y2
x[2] = x0
y[2] = y0
ElseIf (y2 > y1 > y0) Then
x[0] = x0
y[0] = y0
x[1] = x1
y[1] = y1
x[2] = x2
y[2] = y2
ElseIf (y1 > y0 > y2) Then
x[0] = x2
y[0] = y2
x[1] = x0
y[1] = y0
x[2] = x1
y[2] = y1
EndIf
div = abs( y[0] - y[2] )
If div = 0 then div = 1
delta_x_per_y_increment = ( x[1] - x[0] ) / div
xp = x[0]
For yp = y[0] to y[2]
draw_pixel ( int(xp),int(yp),color_val )
xp= xp + delta_x_per_y_increment
Next yp
End Sub
I'm not entirely sure what I'm doing with the setup near the start of the loop. When setting delta_x_per_y_increment, shouldn't that be x[2] instead of x[1], and aren't I going to have to sort the x array to find the lowest and highest values and use those in the formula to calculate the correct delta_x_per_y_increment?
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.