Scan-line algorithm to fill in a triangle

Question

I wrote the following script to fill a Triangle.

import pygame
import random
pygame.init()
WIN = pygame.display
D = WIN.set_mode((1200, 600))
p1 = (200, 50)
p2 = (1000, 600)
class Vec2:
 def __init__(self, x, y):
 self.x = x
 self.y = y
def getLine(start, end):
 # RETURNS ALL THE PIXELS THAT NEEDS TO BE FILLED TO FORM A LINE
 x1, y1 = int(start.x), int(start.y)
 x2, y2 = int(end.x), int(end.y)
 dx = x2 - x1
 dy = y2 - y1
 is_steep = abs(dy) > abs(dx)
 if is_steep:
 x1, y1 = y1, x1
 x2, y2 = y2, x2
 swapped = False
 if x1 > x2:
 x1, x2 = x2, x1
 y1, y2 = y2, y1
 swapped = True
 dx = x2 - x1
 dy = y2 - y1
 error = int(dx / 2.0)
 ystep = 1 if y1 < y2 else -1
 y = y1
 points = []
 for x in range(x1, x2 + 1):
 coord = Vec2(y, x) if is_steep else Vec2(x, y)
 points.append(coord)
 error -= abs(dy)
 if error < 0:
 y += ystep
 error += dx
 if swapped:
 points.reverse()
 return points
RED = (255, 0, 0)
BLUE = (0, 105, 255)
GREEN = (0, 255, 0)
def drawLine(p1, p2):
 # DRAWS A LINE BY FILLING IN THE PIXELS RETURNED BY getLine
 points = getLine(p1, p2)
 color = (0, 0, 0)
 pixels = len(points)
 for i in range(pixels):
 # COLOR BLEDNING
 r0 = i/pixels* RED[0]
 b1 = (abs(pixels-i)/ pixels) * BLUE[1]
 b2 = (abs(pixels-i)/ pixels) * BLUE[2]
 color = (r0, b1, b2)
 D.set_at((points[i].x, points[i].y), color)
# TRIANGLE
v1 = Vec2(500, 500)
v2 = Vec2(100, 100)
v3 = Vec2(1000, 200)
def fillFlatBottom(v1, v2, v3):
 # FILL IN TRIANGLE WITH A FLAT BOTTOM 
 invm1 = (v1.x - v2.x)/(v1.y - v2.y)
 invm2 = (v1.x - v3.x)/(v1.y - v3.y)
 curx1 = v1.x
 curx2 = v1.x
 for y in range(int(v1.y), int(v2.y+1)):
 drawLine(Vec2(curx1, y), Vec2(curx2, y))
 curx1 += invm1
 curx2 += invm2
def fillFlatTop(v1, v2, v3):
 # FILL IN TRIANGLE WITH A FLAT TOP
 invm1 = (v3.x - v2.x)/ (v3.y - v2.y)
 invm2 = (v3.x - v1.x)/ (v3.y - v1.y)
 curx1 = v3.x
 curx2 = v3.x
 for y in range(int(v3.y), int(v1.y), -1):
 drawLine(Vec2(curx1, y), Vec2(curx2, y))
 curx1 -= invm1
 curx2 -= invm2
def drawTriangle(v1, v2, v3):
 # DRAWS ANY TRIANGLE BY SPLITTING THEM INTO FLAT TOP AND 
 # FLAT BOTTOM
 v = [v1, v2, v3]
 for i in range(0, len(v)): 
 for j in range(i+1, len(v)): 
 if(v[i].y > v[j].y): 
 tempy = v[i].y 
 v[i].y = v[j].y 
 v[j].y = tempy
 tempx = v[i].x
 v[i].x = v[j].x 
 v[j].x = tempx
 v1, v2, v3 = v[0], v[1], v[2]
 if v1.y == v2.y == v3.y:
 drawLine(v1, v2)
 elif v2.y == v3.y:
 fillFlatBottom(v1, v2, v3)
 elif v1.y == v2.y:
 fillFlatTop(v1, v2, v3)
 else:
 v4 = Vec2(v1.x + ((v2.y - v1.y)/ (v3.y - v1.y))* (v3.x - v1.x), v2.y)
 fillFlatBottom(v1, v2, v4)
 fillFlatTop(v2, v4, v3)
while True:
 pygame.event.get()
 D.fill((255, 255, 255))
 drawTriangle(v1, v2, v3)
 WIN.flip() 

It uses bresenham's line algorithm and scan line algorithm to draw lines and fill triangle respectively. My goal is to fill in triangles that make up a 3d mesh. I tried implementing the code shown above to fill in a mesh (made of only 2 triangles). When i tried to rotate the mesh, it causes heavy lag, so it is clearly of no use in rendering bigger models(by bigger models, i mean a cube. That's my goal for now).

I can see a couple of things which might be causing problems. Firstly, in getLine function, it converts the points it receives as arguments from float to int.

x1, y1 = int(start.x), int(start.y)
x2, y2 = int(end.x), int(end.y)

I read that the whole point of bresenham's algorithm is to avoid this rounding off, but in my case i couldn't avoid it. It is called like this(drawLine calls getLine)

drawLine(Vec2(curx1, y), Vec2(curx2, y))
curx1 += invm1
curx2 += invm2

invm1 and invm2 are inverse of slopes of 2 sides making up a triangle, which are always floating point numbers. This is passed to getLine, which forced me to convert them to int, otherwise it causes error as for loop in getLine function expects int.

Secondly, in fillFlatBottom and fillFlatTop functions, in for loops for both the functions, the upper and lower bound of range is converted to int because vertices of triangle making a mesh use floating point numbers, which might be avoidable through techniques i might not be aware of.

Answer 1

Avoid storing points unnecessarily

The function getLine() creates a list of pixel coordinates, and then drawLine() iterates over it once, drawing each individual pixel, and then discards the list. Consider changing the function getLine() to be a generator instead, so it returns a point at a time. It is quite easy to modify the function to be a generator; instead of adding a coordinate pair to points, yield it instead:

def getLine(start, end):
 # Setup
 ...
 y = y1
 for x in range(x1, x2 + 1):
 yield Vec2(y, x) if is_steep else Vec2(x, y)
 error -= abs(dy)
 if error < 0:
 y += ystep
 error += dx

The are two issues to deal with though. First, you can no longer do points.reverse() inside getLine(), so you have to modify your function a bit to always yield coordinates in the right order. Second, drawLine() wants to get the length of the line in order to interpolate the pixel colors. Either you have to have some function to calculate and return the line length separately, or you can modify getLine() to yield a tuple of both the pixel coordinates and a floating point value between 0 and 1 that drawLine() can use directly for the interpolation. For example:

yield (Vec2(y, x) if is_steep else Vec2(x, y), x / abs(x2 + x1 + 1))

With this in place, you can change drawLine() as follows:

def drawLine(p1, p2):
 for point, t in getLine(p1, p2):
 r0 = t * RED[0]
 b1 = (1 - t) * BLUE[1]
 b2 = (1 - t) * BLUE[2]
 color = (r0, b1, b2)
 D.set_at(point, color)

Drawing filled triangles

The idea to split the triangle into two parts is a good one. However, there are some issues. First, you have two functions that basically do exactly the same thing, except with some variables swapped and a sign flipped. I would try to write a single function that handles both a flat bottom and a flat top. If you ever need to modify the algorithm, it's easier to change it in one place than to have to do the same thing in two places.

But there is another issue: you assume that you can iterate over the y-coordinate, or to put otherwise, that the lines involved are steep. But I can easily create a set of coordinates where none of the lines are steep, for example:

v1 = Vec2(100, 100)
v2 = Vec2(500, 200)
v3 = Vec2(900, 300)

This will result in a dotted line instead of a solid line. Just like Bresenham's algorithm itself, you need to distinguish between steep and non-steep.

Use sort()

You implemented your own bubble-sort algorithm to sort v in drawTriangle(). But Python comes with a sorting function that can take an optional function to tell it what to sort on, so you can replace your own algorithm with:

v = [v1, v2, v2]
v.sort(key=lambda p: p.y)