[Open-graphics] The quiz answers

[Nicolas Capens]

Hi all,

Ok, here are the answers to the 'quizzes' I introduced here: http://lists.duskglow.com/open-graphics/2004-November/000648.html. Sorry for those who were on the break of finding the answers themselves and trying so hard...

The first one was about 8x8 blocks flashing on the horizon. They are caused by the half-space function (inequality to be exact): (x2 - x1) * (y - y1) - (y2 - y1) * (x - x1) > 0. This function silently assumes the differences are not all zero. If however they both do become zero, which happens when two points of the triangle coincide (and thus the line between them doesn't exist), the function becomes something different. However, it becomes 0 > 0 which is always false, which would result in no pixels being drawn. The real problem is caused by the corrections for the fill convention. When an edge is 'top-left', it means pixels with their center exactly on the edge should also be rendered, and this is done by subtracting 1 from the left-hand side. This is equivalent to 0 >= 0 which is always true. So for this edge (which isn't an edge), all pixels pass. Since the smallest area that I scan is 8x8 pixels, this is the size of the artifacts. It happens at the horizon because the far clipping plane makes the polygons become so small the vertices coincide when mapped to fixed-point integers.

The second one was about weird colors seen on very tilted polygons. The explanation is simple. I use 4.12 fixed-point numbers for interpolating diffuse colors and fog. Normally they are in the 0.000000h to 0.FFFF00h range. The way interpolation works is like this: for every 8x8 block I determine the values for the upper-left corner, then I use linear interpolation for the other pixels, by adding dc/dx and dc/dy gradients. The trouble starts when the upper-left corner of the block is outside the triangle. In this situation the starting value might be outside the usual range. There are still four bits above the decimal though, and a small calculation shows that the polygons has to be quite thin and very tilted to get a big gradient inside the 8x8 block. But in this rare situation the starting value can be outside the range of the 4.12 fixed-point number, causing all colors of the rainbow to be visible on the triangle.

Now that your brains are still warmed up, here are some very closely related new and simpler quizzes:

To fix the first bug, why doesn't is suffice to check whether the polygon has a zero size and skip those at the vertex processing stage? Why doesn't it suffice to check for really small polygons smaller than a sub-pixel? And why doesn't it suffice to check whether all points in sub-pixel coordinates coincide? Notice my use of the word 'suffice', in the sense that it should fix the bug, not be the most efficient fix.

What is the most efficient fix of the second bug? You might notice I didn't mention the whole story about the cause of the bug.

All the best,

Nicolas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.duskglow.com/open-graphics/attachments/20041211/8b5308a7/attachment.html