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?
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?
a triangle only renders if a pixel-center is contained in the triangle
thanks avoozl
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.
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.
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.
I don't know how it is in theory, but in practice I think most rasterizers always draw at least a pixel.
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.
xernobyl: I think very few rasterisers always draw one pixel. In fact I can't imagine how that would be.
It's one those very easy to see with a little code things.
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.
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.
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.
Quote:
without the diagonal ending up brighter than the rest
*sigh*
*bad opengl souvenirs, bad bad bad souvenirs...*
I've just found this php code I did some time ago. The function returns if a dot is inside a closed polygon.
$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...
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...
are you trolling or merely stupid?
shiva: ban.
Didn't thought of that. I forgot to think about the rest of the polys :P
Quote:
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
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.
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.
what Michael Abrash said
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.
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.
* Watertight in this case meaning you'd get an unbroken square.
So it's true what they say about Spanish people coding in spanish.
battle droid: i guess you mean LOD? that's a good solution idd
Doom: ...But raytracing is the ideal model of the real world! Everything automatically becomes correct! RAY-TRAY-CING! RAY-TRAY-CING! RAY-TRAY-CIIIING!
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.
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.
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.
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.
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...
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...