I have a little problem with a new rasterization algorithm...
Rasterization of triangles is usually done using scan conversion, but I recently discovered a more advanced approach: Triangle Scan Conversion using 2D Homogeneous Coordinates. I actually knew that paper for quite some time, but never really understood the advantages. What they do is simply scan through the bounding rectangle of a triangle, and for each pixel determine whether it is inside the triangle. For each edge of the triangle, a 'half-space' function is computed, which is positive on the inside of the triangle and negative on the other side. So when all three are positive, the point can be drawn. The implementation is surprisingly efficient, because the formula can be evaluated incrementally for every pixel. It's also easy to determine whether a block of pixels is (partially) covered by the triangle or not.
So it turned out to be really useful for processing pixels in parallel. More specifically, I can now have 'quad' pipelines. They process 2x2 pixels using MMX and SSE instructions. The half-space functions very conveniently provide a mask that can be used to determine which of the four pixels has to be written to the screen.
Now the problem... When a pixel is on the edge of a polygon, the half-space functions are neither positive or negative, they are zero. But there are quite strict rules to determine whether such a pixel should be drawn or not. DirectX and OpeGL have the top-left convention: Rasterization Rules. These rules are very important to avoid gaps between triangles and drawing pixels on the edges twice.
So, does anyone have an idea how to implement the fill convention for the half-space functions algorithm? It's obviously inefficient (and quite complex) to check whether to use > or >= for every edge, for every pixel. Ideally I would like to handle this in the setup stage, like shifting the edges slightly. But this does not work correctly either. I don't think it's easy to solve, but all ideas are welcome!