Non ordered triangle rasterisation

Question

I'm doing a triangle rasteriser and it all works but now I want to use parallel computing to draw a bunch of triangles.

This means that the triangles can be drawn in any random order each frame, the problem is this disordered drawing is causing artifacts.

As a test case, let's consider two triangles that share two vertices, like so:

If we look at a grid of pixels the vertices will look like this:

The filling convention I'm using is just ceil()
So if we draw the blue triangle it will look like this

The problem that now becomes apparent is that if we now draw the yellow triangle, because they share the two vertices, the yellow triangle will be drawn over the blue one:

This isn't a problem on it's own, the problem is IF we draw them in the reverse order (yellow first, blue second) then the blue one will be drawn over instead:

This causes obvious artifacts because in any frame the order can be random so you will see a flickering line as one triangle is drawn over another and vise versa.

Is there any thing that can be done to ensure that the final image will look identical no matter the order the triangles are drawn in?

Answer 1

Always truncate to integer device pixels, and always do it the same way. This could be floor or ceiling or even rounding (if your sure both triangles get numerically identical inputs then they should round the same).

And define the boundaries of the triangle to include the lowest endpoint but exclude the highest, ie., min(x0,x1) <= x < max(x0,x1) and similarly for the y range.