question about accelerated triangle rendering

category: general [glöplog]
If a triangle size is little than 1 pixel (or subpixel if you are using aa), do it render? Or said in other words, does the "mesh aliasing" occurs?

For example, if I have a mesh in the shape of squares composed of 2 triangles in a grid... let say 1000x1000, 2 million triangles. If I try to render it at a size of... 50x50 pixels, for example, will it dissapear?
added on the 2007-12-05 21:27:32 by texel texel
a triangle only renders if a pixel-center is contained in the triangle
added on the 2007-12-05 21:44:46 by avoozl avoozl
thanks avoozl
added on the 2007-12-05 21:52:10 by texel texel
Well, normaly the triangle rasterizers are following some rasterization rules about what to draw or not.

A common one is:
- Draw (x1-x0) pixels from x0
- Draw (y1-y0) lines from y0

This simple set of rule means that if you have a segment x0-x1-x2, the "x1" pixel will not be drawn twice (it's part of the x1-x2) segment.

You can easily visualize this by using translucent polygons. If you see the edges, it means some pixels are drawn twice. Bad rasterizer.
added on the 2007-12-05 21:53:04 by Dbug Dbug
What avoozl said, although that's an ideal rasteriser with no antialiasing. Many software rasterisers for lesser platforms wouldn't draw a triangle if it spans less than a pixel. In some of those however, triangles that cross pixel boundaries would be drawn with a width of one pixel. Which would fill the 50x50 pixel square.
added on the 2007-12-06 00:32:47 by doomdoom doomdoom
I don't know how it is in theory, but in practice I think most rasterizers always draw at least a pixel.
added on the 2007-12-06 00:55:49 by xernobyl xernobyl
Of course, the topic says "about accelerated triangle rendering". :) So nevermind.

xernobyl: I think very few rasterisers always draw one pixel. In fact I can't imagine how that would be.
added on the 2007-12-06 01:03:31 by doomdoom doomdoom
It's one those very easy to see with a little code things.
added on the 2007-12-06 01:08:00 by xernobyl xernobyl
xernobyl, all hardware and most software rasterizers i know obey sensible fill conventions that guarantee "watertight rasterization" - i.e., when rendering a connected mesh, no pixel is written twice (not from the same triangle/edge, anyway; of course, with e.g. a cube, the front and back faces can cover some of the same pixels, and this may cause pixels to get written twice if the back face gets painted before the front face or z-buffering is off). this isn't about theory, it's required for very basic stuff to work properly - if your triangle rasterizer isn't watertight, you can't even draw things like additive 2D sprites (quads made up from 2 tris) without the diagonal ending up brighter than the rest. watertight rasterization is also necessary for most stencil buffer-based techniques to work.
added on the 2007-12-06 01:15:08 by ryg ryg
xernobyl: I've done loads of rasterisers, mind you :). A simple implementation would simply not draw anything in the case where int(min(y0,y1,y2)) = int(max(y0,y1,y2)). And for each scanline, int(x0)=int(x1) would result in no pixels being drawn on that line, otherwise faces would overlap. Of course a few (poor) implementations always draw x1-x0+1 pixels per scanline. I'm guilty too, it's just such an easy fix if you've got gaps due to precision errors elsewhere and all your faces are opaque anyway. But no good rasteriser will draw anything if a triangle or scanline falls within the centres/edges of neighbouring pixels.

All modern hardware rasterisers AFAIK have a fill convention that says a pixel is included if its centre is within the triangle. Which means a traingle can easily occupy zero pixels if it's small or thin enough.
added on the 2007-12-06 01:34:15 by doomdoom doomdoom
without the diagonal ending up brighter than the rest


*bad opengl souvenirs, bad bad bad souvenirs...*
added on the 2007-12-06 01:35:16 by TomS4wy3R TomS4wy3R
I've just found this php code I did some time ago. The function returns if a dot is inside a closed polygon.

Code: function punto_dentro_poligono($punto_x, $punto_y, $vertices_x, $vertices_y, $num_vertices) { $cont=0; for ($n=0; $n<$num_vertices; $n++) { $x0=$vertices_x[(($n+$num_vertices-1)%$num_vertices)]-$punto_x; $y0=$vertices_y[(($n+$num_vertices-1)%$num_vertices)]-$punto_y; $x1=$vertices_x[$n]-$punto_x; $y1=$vertices_y[$n]-$punto_y; $x2=$vertices_x[(($n+1)%$num_vertices)]-$punto_x; $y2=$vertices_y[(($n+1)%$num_vertices)]-$punto_y; if (($y1==0)&&($y2==0)) { if ($x1>=0) $cont++; } else if (($y1==0)&&($x1>=0)&&(($y0*$y2)<0)) $cont++; else if ((($y2*$y1)<0)&&((((($x2-$x1)*-$y1)/($y2-$y1))+$x1)>=0)) $cont++; } return ($cont%2); }

$punto_x = dot.x
$punto_y = dot.y
$vertices_x = array of ordered vertexs of the polygon (x values)
$vertices_y = array of ordered vertexs of the polygon (y values)
$num_vertices = number of vertexs in the polygon

As far as I remember this algorithm should be watertight, but I've tried to understad the code and I have no idea of how I did it (WTF). I suppose it should render a square in the example I said of the 50x50 pixels... or not? Uh...
added on the 2007-12-06 02:55:02 by texel texel
are you trolling or merely stupid?
added on the 2007-12-06 03:58:52 by shiva shiva
shiva: ban.

when rendering a connected mesh, no pixel is written twice

Didn't thought of that. I forgot to think about the rest of the polys :P
added on the 2007-12-06 04:18:59 by xernobyl xernobyl
if you render sucha complex object at 50x50 it might be more efficient to use raytracing. i never solved issues like this in my software rasteriser. it's relatively easy and efficient to avoid overdraw for larger polys.

but for these small ones.. in any case you'd need sub pixel precision for the vertices. in case of transparancy you'd need to weigh the pixel coverage too.

checking whether a pixel is inside a convex polygon is simple when you know the edge normals.
added on the 2007-12-06 13:52:35 by earx earx
what Michael Abrash said
added on the 2007-12-06 13:58:43 by bigcheese bigcheese
earx: If you render a 1000x1000 face mesh in 50x50 pixels, you need to consider adaptive degradation before you consider raytracing, I think. :)

texel: The method looks very strange to me. Can't work it out just now, but I'm guessing if you rearrange the ((($y2*$y1)<0)&&((((($x2-$x1)*-$y1)/($y2-$y1))+$x1)>=0)) expression, the division goes away and you end up checking the sign of a dot product, which is a textbook fill convention. And it's also watertight.
added on the 2007-12-06 14:10:34 by doomdoom doomdoom
* Watertight in this case meaning you'd get an unbroken square.
added on the 2007-12-06 14:11:38 by doomdoom doomdoom
So it's true what they say about Spanish people coding in spanish.
added on the 2007-12-06 15:16:38 by xernobyl xernobyl
battle droid: i guess you mean LOD? that's a good solution idd
added on the 2007-12-06 15:49:29 by earx earx
Doom: ...But raytracing is the ideal model of the real world! Everything automatically becomes correct! RAY-TRAY-CING! RAY-TRAY-CING! RAY-TRAY-CIIIING!
added on the 2007-12-06 16:32:40 by kusma kusma
texel/doom: didn't work it out explicitly, but unless i'm much mistaken, this code is not watertight. it's not enough to hit all pixels covered, you also may not fill the same pixel twice in a closed mesh (as mentioned above), and the code above looks like it'll fail that criterion. example:

vertex 0: at (0,0)
vertex 1: at (0,1)
vertex 2: at (-1,-0.5)
vertex 3: at (1,-0.5)
tris (vertex indidices): (0,1,2), (0,2,3), (0,3,1)

if i didn't misunderstand the code, the pixel at (0,0) will get filled several times, which is wrong.
added on the 2007-12-06 17:01:33 by ryg ryg
earx: I mean the thing where you adaptively degrade the complexity of the mesh to stay somewhat proportional to the screan area to triangle count ratio. Whatever you want to call it. :)

kusma: But light is particles, not rays!!!! The sun emits 4*10^44 photons per second. You must account for all of them!!! And for the last time, space/time is not cartesian!

texel: If you're interested, an easy fill convention is:

Given a point X and a set of vertices P[0]..P[n] making up a convex polygon (e.g. triangle), calculate d = ^(P[i+1]-P[i]) dot (X-P[i]) for all i. ^V is supposed to mean vector V rotated CCW by 90 degrees. The sign of d then determines if you're to the left or the right of the edge from vertex i to vertex i+1. If your polygon is defined CCW, d>0 puts X on the "inside" side of the edge. If that's the case for all edges, X is inside the face. Otherwise X is outside.

If d=0 for any edge, X is on the exact boundary, a case for which you need a further convention that ensures two neighbouring faces treat the same edge differently, that is, one face must include the edge, the other mustn't. You could choose based on the orientation of the edge on screen since that is necessarily opposite for two neighbouring faces using the same edge. And pay attention to points that occupy two edges in one face (ie. corners).

Of course, having written that last bit I notice it slipped my mind earlier. A dot-product convention (or an obfuscated one as your PHP example seems to use) isn't watertight without it.
added on the 2007-12-06 18:09:00 by doomdoom doomdoom
ryg, I've just test your example with my code, and pixel at (0,0) gets only filled 1 time... I'm going to test de triangle matrix thing now...
added on the 2007-12-06 20:05:50 by texel texel
erm... it is not watertight, the matrix example paints some pixels more than 1 time in few concrete cases... I will need to study the algorithm again...
added on the 2007-12-06 20:31:53 by texel texel