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.