I'm working on a 3D game which is still in the beginning stages of development. The game uses perspective projection.
The problem is, I need a way to fill 3-dimensional quadrilaterals, specifically rectangles, although in the game they can be viewed from angles that make them appear trapezoidal. I tried using scanlines and clipping each line individually, but that was too slow.
The fastest triangle filling algorithm I know of on Scratch is @TheLogFather's “Faster Triangle Filler”:
https://scratch.mit.edu/projects/24828481/
But if a triangle goes past the boundaries of the screen or goes behind the camera, it has to be clipped. It could then appear to be a quadrilateral or pentagon. (It could be a hexagon, too, but I don't have to worry about that.)
I need to use XY and Z clipping to determine the vertex coordinates of the quadrilateral/pentagon from the triangle's vertex coordinates.
How can I clip the triangle and then divide the resulting shape into triangles to be filled efficiently?

For a quadrilateral, drawing a line between two corners divides it into two triangles, which you can fill from there. (use the line as one of the sides of the triangle when filling) For a pentagon, drawing a line between two corners yields a triangle and a quadrilateral, which you can then treat as their own shapes and fill accordingly. Hopefully that helps!

nyankatpro wrote:

For a quadrilateral, drawing a line between two corners divides it into two triangles, which you can fill from there. (use the line as one of the sides of the triangle when filling) For a pentagon, drawing a line between two corners yields a triangle and a quadrilateral, which you can then treat as their own shapes and fill accordingly. Hopefully that helps!

Thank you for that! However, the part I'm really stuck on is clipping the triangle. How do I figure out the vertex coordinates of the quadrilateral and pentagon from the triangle with XY clipping and Z clipping?
I'm sorry, I really didn't make this clear. Editing the post now.

Since the filler uses sets of 2d points, we can use an out-of-bounds vertex and an in-bounds vertex of the triangle to find the point of intersection with the boundary. Assuming the clipping happens before the rendering, we can divide the in-bounds vertex's distance to the clipping plane (on one axis) by the respective coordinate of the out-of-bounds vertex to get the ratio between the intersection point and the vertex. we can then multiply the x, y, and z distances between each vertex by this ratio to find the coordinates of the intersection, which you can then feed into the renderer. Repeat this as necessary for each intersection, and you'll have yourself the coordinates for a quadrilateral/pentagon. (hopefully my explanation doesn't stink and this made sense!)

nyankatpro wrote:

Since the filler uses sets of 2d points, we can use an out-of-bounds vertex and an in-bounds vertex of the triangle to find the point of intersection with the boundary. Assuming the clipping happens before the rendering, we can divide the in-bounds vertex's distance to the clipping plane (on one axis) by the respective coordinate of the out-of-bounds vertex to get the ratio between the intersection point and the vertex. we can then multiply the x, y, and z distances between each vertex by this ratio to find the coordinates of the intersection, which you can then feed into the renderer. Repeat this as necessary for each intersection, and you'll have yourself the coordinates for a quadrilateral/pentagon. (hopefully my explanation doesn't stink and this made sense!)

Thank you! Your explanation is very clear and this is exactly what I was looking for.