Filling in a triangle by drawing lines in pygame

Question

My ultimate goal is the fill in the triangles making up a 3d mesh. To figure out how to do this, i decided to generate a random triangle and fill it in. After some articles and youtube videos later, i figured that it is usually done by calculating the x and y between different lines of the triangle and filling those pixels. But in my case pygame already has a draw line function, so i can simply calculate all the points between the 2 points making up the longest side and draw lines from those points to the third point, or so i thought. Here is the copy-and-paste code:

import pygame
from random import randint
from math import sqrt
pygame.init()

D = pygame.display.set_mode((1200, 600))

class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def genTriangle():
    point1 = Pos(randint(50, 1000), randint(50, 550))
    point2 = Pos(randint(50, 1000), randint(50, 550))
    point3 = Pos(randint(50, 1000), randint(50, 550))
    return [point1, point2, point3]

tri = genTriangle()

def getLength(p1, p2):
    x = p1.x - p2.x
    y = p1.y - p2.y
    return sqrt(x**2 + y**2)
    
def fill(tri):
    len01 = getLength(tri[0], tri[1]) #Length between tri[0] and tri[1]
    len12 = getLength(tri[1], tri[2]) #Length between tri[1] and tri[2]
    len20 = getLength(tri[2], tri[0]) #Length between tri[2] and tri[0]

    # Assinging the points making up the longest side to p1 and p3 
    # and the third point to p2 becasue that is how the calculation is carried
    # out later (i feel like this is now the best way to figure out the longest side
    # so any help with this would be appreciated as well)
    if len01 > len12 and len20:
        p1 = tri[0]
        p2 = tri[2]
        p3 = tri[1]

    elif len12 > len20 and len01:
        p1 = tri[1]
        p2 = tri[0]
        p3 = tri[2]

    elif len20 > len01 and len12:
        p1 = tri[2]
        p2 = tri[1]
        p3 = tri[0]

    # calculates all the points along the longest side of the triangle
    # and draws lines from those points to  the third point of the triangle
    for x in range(p1.x, p3.x+1):
        m = ((p1.y - p3.y)/ (p1.x - p3.x)) # slope
        y = m*(x - p3.x) + p3.y # rearranged point-slope formula 
        pygame.draw.line(D, (255, 0, 0), (int(x), int(y)), (p2.x, p2.y), 1) 


while True:
    pygame.event.get()
    D.fill((255, 255, 255))
    fill(tri)
    points = [(point.x, point.y) for point in tri]
    pygame.draw.lines(D, (0, 0, 0), True, points, 1)
    pygame.display.flip()

The result is that sometimes the triangle is filled in properly with no problem at all. Sometimes the triangle is filled but there are some unfilled pixels as well and sometimes the triangles is not filled at all. Thanks for helping.

I recommend to do that not in pygame. If you want to render (raster) meshes, then use a CPU bound approach and switch to [Python Mode for Processing](https://py.processing.org/), [pyglet](http://pyglet.org/), [ModernGL](https://moderngl.readthedocs.io/en/4.1.2/ModernGL.html) or even native OpenGL ([PyOpenGL](http://pyopengl.sourceforge.net/documentation/index.html)). If you what to render on the CPU then write a [Ray tracer](https://en.wikipedia.org/wiki/Ray_tracing_(graphics)). See [PyGameRayTracing](https://github.com/Rabbid76/PyGameRayTracing) — Rabbid76, Aug 31 '20 at 16:33
Please supply the expected [minimal, reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). Show where the intermediate results differ from what you expected. In particular, "sometimes it works, sometimes it doesn't" is not a problem specification. *You* supply those cases, trace the intermediate values causing the gaps, and post the *specific* examples. — Prune, Aug 31 '20 at 16:40
Suggest you try using [`pygame.draw.polygon()` to draw the triangles,](https://www.pygame.org/docs/ref/draw.html#pygame.draw.polygon) _possibly_ in conjunction with [`pygame.draw.aalines()`](https://www.pygame.org/docs/ref/draw.html#pygame.draw.aalines) to draw their outlines. — martineau, Aug 31 '20 at 16:45
@Prune The code i provided is minimal and reproducible. It really does work sometimes and not other times because the triangles generated is random and i don't have anything to add because i have no idea why it is happening. But as Rabbid commented i will probably take a different approach, Sorry for wasting your time. — , Aug 31 '20 at 16:45
Also, what *specific* algorithm are you using? Did you research existing fill algorithms? I'm not sure what you mean by "calculate all the points", as that's an infinite set. If you mean that you get all of the pixels, then (1) you will certainly miss pixels adjacent to the base side, and (2) you will waste time multiply filling in pixels near the apex. See [Bresenham's algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm) and apply it to the triangle (0,0), (0,1), (1,0). — Prune, Aug 31 '20 at 16:45
If your code varies in results from one run to another, it is not reproducible. Also, there is no trace of intermediate values, trying to figure out where you get the gaps. — Prune, Aug 31 '20 at 16:46

Rabbid76 · Accepted Answer · 2020-09-01T09:27:44.167

An obvious mistake is the line

for x in range(p1.x, p3.x+1):

If you don't specify a step argument in the function range, then start has to be less than stop. Compute the minimum and maximum coordinate:

for x in range(min(p1.x, p3.x), max(p1.x, p3.x)+1):
    m = ((p1.y - p3.y)/ (p1.x - p3.x)) # slope
    y = m*(x - p3.x) + p3.y # rearranged point-slope formula 
    pygame.draw.line(D, (255, 0, 0), (int(x), int(y)), (p2.x, p2.y), 1)

Furthermore, the condition if len01 > len12 and len20: does not do what you expect it to do. It has to be if len01 > len12 and len01 > len20:.
See How to test multiple variables against a value?.

You have to evaluate if abs(p3.x-p1.x) > abs(p3.y-p1.y). If the condition is True the iterate along the x axis, else along the y axis:

def fill(tri):
    len01 = getLength(tri[0], tri[1]) #Length between tri[0] and tri[1]
    len12 = getLength(tri[1], tri[2]) #Length between tri[1] and tri[2]
    len20 = getLength(tri[2], tri[0]) #Length between tri[2] and tri[0]

    # Assinging the points making up the longest side to p1 and p3 
    # and the third point to p2 becasue that is how the calculation is carried
    # out later (i feel like this is now the best way to figure out the longest side
    # so any help with this would be appreciated as well)
    if len01 > len12 and len01 > len20:
        p1, p2, p3 = tri[0], tri[2], tri[1]
    elif len12 > len20 and len12 > len01:
        p1, p2, p3 = tri[1], tri[0], tri[2]
    elif len20 > len01 and len20 > len12:
        p1, p2, p3 = tri[2], tri[1], tri[0]

    # calculates all the points along the longest side of the triangle
    # and draws lines from those points to  the third point of the triangle
    if abs(p3.x-p1.x) > abs(p3.y-p1.y):
        for x in range(min(p1.x, p3.x), max(p1.x, p3.x)+1):
            m = ((p1.y - p3.y)/ (p1.x - p3.x)) # slope
            y = m*(x - p3.x) + p3.y # rearranged point-slope formula 
            pygame.draw.line(D, (255, 0, 0), (int(x), int(y)), (p2.x, p2.y), 1) 
    else:
        for y in range(min(p1.y, p3.y), max(p1.y, p3.y)+1):
            m = ((p1.x - p3.x)/ (p1.y - p3.y)) # slope
            x = m*(y - p3.y) + p3.x # rearranged point-slope formula 
            pygame.draw.line(D, (255, 0, 0), (int(x), int(y)), (p2.x, p2.y), 1)

Filling in a triangle by drawing lines in pygame

1 Answers1