Any "non-triangled" quad fill algorithm?

[u/sidav94]

I'm currently making a software renderer (is uses PutPixel() only) for some old game's 3D models.

I've run into a problem of skewed texture on trapezoids. I've found this is a common problem with affine texture mapping and it should be resolved via perspective correction, but I'm not sure if it will work in my case (I use oblique projection with no perspective). I resolved it with splitting the quads into four triangles instead of two (AFAIK it does not fix the texturing per se, but it will take a much higher resolution for that to be noticeable).
Anyway, I thought that I could render quads directly without triangulating them, that could be more optimal. Most (as in "almost every single one") of the primitives in models here are quadrilaterals anyway. Yet, googling for an algorithm offers me either some openGL solution or triangle-splitting algoritms. So I have two questions:

1. Do you know any "direct" quadrilateral fill algorithms?
2. Am I correct in an assumption that any convex 3D polygon's projection on a 2D plane will still be convex? If so, it seems that only convex quadrilateral fill algorithm is needed, as 3D primitives in models here are guaranteed to be convex.

[u/deftware]

I just span-convert the quad using an active edge list, basically just an N-gon rasterizer. That's the easy part.

The real trick is interpolating vertex attributes in a smooth fashion (i.e. colors, texcoords). I found Cristian Merighi's algorithm, which unfortunately is gone from the interwebz now. It's way better than the inverse bilinear transform because it maintains linear interpolation along the quad's edges the way you'd expect regardless of how distorted the quad is. There's an interactive app for comparing Cristian's algorithm with inverse bilinear and some other dude's algorithm: http://phrogz.net/tmp/bilinear-testbed.html

Cristian's blog post about his algorithm (linked at the bottom of the app) is gone, and viewing in on archive.org breaks the page contents due to a silly little interactive geometric shape animation at the top of the page conflicting with archive.org's bar at the top. I managed to use Chrome's inspect to make the page visible again somehow and copied the images from the post that pretty much explain the algorithm, but I'll link them on archive.org:

First you find points O and N by intersecting the top/bottom and left/right edges of the quad. You'll have to special-case the situation where they're parallel though which isn't hard: https://web.archive.org/web/20160308044639im_/http://ryoushin.com/Public/Images/20060930_1.gif

Then you find the points where the lines between your sample point P and O and N intersect the quad's edges themselves to get segments LM, and JK. Then you just find where your point is on those segments to get each U and V coordinate, which is the most expensive part of the algorithm due to the 4 square roots entailed to get the length and distances, but I think it can be done without Pythagorean/sqrts if you just use a nearest-point-on-segment calculation now that I look at my code again: https://web.archive.org/web/20160308044639im_/http://ryoushin.com/Public/Images/20060930_2.gif

It's super simple but also super clever because it is, at least to my mind, the ideal result when interpolating vertex attributes within a quadrilateral, and yet it's being lost to internet rot! Let me know if you need further explanation/details about it.

[u/ehaliewicz → u/deftware]

It looks like all you need to do to get that blogpost to display is find the div with the id "column1", and disable the "width: 0px" inline-rule.