question about accelerated triangle rendering
category: general [glöplog]
let me guess... tie-breaking? (pixels exactly at the edge, some work must be done to make sure only one polygon per edge gets pixels exactly at the edge)
At the edges work fine, the problem is when I have a pixel exactly in a vertex. I've solved it right now for triangles wich are concave, but with convex polygons it looks it needs more work... The thing is that I have it working for triangles... so my question is solved right now. Thanks :)
texel: a vertex lie exactly at two edges, dummy ;)
yes, and I wrote also wrong concave and convex (I think I did it the opposite I should)... sorry, I'm getting old and my mind doesn't work as always :P
The pasted algorithm attempts to intersect a horizontal line from (-infinity, punto_y) to (punto_x, punto_y) with each edge in the supplied polygon.
Each iteration through the loop intersects the line against the polygon edge from $n to $n+1.
Each time an intersection is detected, the $cont counter is increased.
Now, let's assume that the polygon is not self-intersecting.
If the point is outside the polygon, then the line will have entered the polygon X times and exited it X times.
If the point is inside the polygon, then the line will have entered the polygon X+1 times and exited it X times.
Thus, if $cont is odd, the point is inside the polygon.
The occasional errors are because of problems with the tie-breaking rules. It will be easier to fix those tie-breaking rules if the algorithm is simplified a bit. Here's a suggestion, off the top of my head:
The description below assumes that the vertex has its vertices given in counter-clockwise order.
I can't guarantee that it is water-tight, but I think so. It should handle both concave & convex polygons well.
Each iteration through the loop intersects the line against the polygon edge from $n to $n+1.
Each time an intersection is detected, the $cont counter is increased.
Now, let's assume that the polygon is not self-intersecting.
If the point is outside the polygon, then the line will have entered the polygon X times and exited it X times.
If the point is inside the polygon, then the line will have entered the polygon X+1 times and exited it X times.
Thus, if $cont is odd, the point is inside the polygon.
The occasional errors are because of problems with the tie-breaking rules. It will be easier to fix those tie-breaking rules if the algorithm is simplified a bit. Here's a suggestion, off the top of my head:
The description below assumes that the vertex has its vertices given in counter-clockwise order.
Code:
- Start off by assuming that $cont = 0 -- that means, the point is outside of the polygon.
For each edge in the polygon, do:
- read vertex $n into $x0,$y0 and vertex $n+1 into $x1,$y1.
- If $y0 == $y1, the edge is horizontal -- ignore this edge.
- If $y0 < $y1, the edge is on the left-hand side of the polygon.
- If $y0 > $y1, the edge is on the right-hand side of the polygon. Swap ($x0,$y0) with ($x1,$y1), so that $y1 > $y0 in all following calculations.
- If $punto_y < $y0, or $punto_y >= $y1, the line misses the edge entirely -- ignore this edge.
^------------------^^ vertical tie-break rule
- Calculate the X coordinate where the line intersects with the edge: $x = ($x1-$x0) / ($y1 - $y0) * ($punto_y - $y0) + $x0.
- If $punto_x < $x, the line is to the left of the edge and they do not intersect -- ignore this edge.
^ horizontal tie-break rule
- You now know that the line crosses the edge. Increase $cont.
Afterward, if cont is odd, the point is inside the polygon. Otherwise, it is outside.I can't guarantee that it is water-tight, but I think so. It should handle both concave & convex polygons well.
yeahZ...Kalms is still coding on Amiga...and as we all know the Standard Lo-Res is 320*256 ( Hi-Res = 640*512 ) Pixels...so i guess he ran into that problem quite often ;)
but if its watertight i can´t say...but looks alike...!
but if its watertight i can´t say...but looks alike...!
c0c00n: Actually, the amount of issues due to lack of tie-breaking increase with the resolution, so low-res engines suffer less from this.
now that you say it...
...i guess i´m just NOT there yet...after beeing homeless/without ComputerZ for several yearZ i still lag-behind somehow...
...and as i´m only designing sth that COULD get a Demo somewhen atm,instead of learning to code on PC (last Time i released sth was in 1995 i think...on Amiga) ,i just should keep-my-mouth-shut/not post in theZe coderZ-ThreadZ...!!
but on the other Hand...: Thiz iz Pouet.! :)
maybe i just need more of theZe ThreadZ and thats why i posted here...there WILL BE a Point when i´ll dive into Coding completely again i guess...but for noW i´m happy to learn via ThreadZ-like-this-one..!!
so,thanxbye :) (reading only....c0c00n.: selfBAN 4 coderZ-ThreadZ.! )
P.S.: yeZz,me drunk and tired-out.! (always the time when i start trolling...lol)
...i guess i´m just NOT there yet...after beeing homeless/without ComputerZ for several yearZ i still lag-behind somehow...
...and as i´m only designing sth that COULD get a Demo somewhen atm,instead of learning to code on PC (last Time i released sth was in 1995 i think...on Amiga) ,i just should keep-my-mouth-shut/not post in theZe coderZ-ThreadZ...!!
but on the other Hand...: Thiz iz Pouet.! :)
maybe i just need more of theZe ThreadZ and thats why i posted here...there WILL BE a Point when i´ll dive into Coding completely again i guess...but for noW i´m happy to learn via ThreadZ-like-this-one..!!
so,thanxbye :) (reading only....c0c00n.: selfBAN 4 coderZ-ThreadZ.! )
P.S.: yeZz,me drunk and tired-out.! (always the time when i start trolling...lol)
drunk at this time of the morning? good going.
kusma: I think that depends on how you look at it. The number of tie-breaking situations increases with the number of faces, but the effect of each decreases with high resolution. Transparency adds new issues of course. But the thing that would make Amiga coders run into the issue more often would probably be the need for software rendering in the first place. ;)
Of course, you need perfect conventions for raytracing too. And in some other cases. Maybe when coding shaders? See I don't really have a point to make. ._.
Of course, you need perfect conventions for raytracing too. And in some other cases. Maybe when coding shaders? See I don't really have a point to make. ._.
Doom: AMIGAAAH.
smashing: No Friday morning without boozing before noon.
drank all night long...! ;) ..still cant find NO sleep...
...and what Doom said is about what i would have said next...if i wouldn´t have posted that other stuff...but when i think hard enuff about it i know,its true...i HAVE to LEARN a LOT...even relearn @some points.!
first thing to learn is.: don´t post when selfBANned.!! if you do so twiCe.: PermaSelfBAN.! rofl.!
(but how could i learn by not-beeing-selfallowed-to-ask-questions-here-and-there...!!??? ;) )
/unSelfBAN <-- hope that does the job...rofl.!
the original problem was about millionZ-of-verteXes in a small 50by50-piXel-aRea...and sth about subpixels beeing draWn or nOt...and thatZ the point where i have no clue anymore...if there´s no piXel to be AntiAliased,i guess you have to trick around a bit more...thatZ materia(shaderZ) i didn´t read ANYTHING about yet...and as i´m not a coder (again) yet....
...i´ll troll myself and let you guys get into it again.! :)
sry 4 the-lot-to-read,hehe ;)
...and what Doom said is about what i would have said next...if i wouldn´t have posted that other stuff...but when i think hard enuff about it i know,its true...i HAVE to LEARN a LOT...even relearn @some points.!
first thing to learn is.: don´t post when selfBANned.!! if you do so twiCe.: PermaSelfBAN.! rofl.!
(but how could i learn by not-beeing-selfallowed-to-ask-questions-here-and-there...!!??? ;) )
/unSelfBAN <-- hope that does the job...rofl.!
the original problem was about millionZ-of-verteXes in a small 50by50-piXel-aRea...and sth about subpixels beeing draWn or nOt...and thatZ the point where i have no clue anymore...if there´s no piXel to be AntiAliased,i guess you have to trick around a bit more...thatZ materia(shaderZ) i didn´t read ANYTHING about yet...and as i´m not a coder (again) yet....
...i´ll troll myself and let you guys get into it again.! :)
sry 4 the-lot-to-read,hehe ;)
AFAIK, with raytracing you also have issues at edges between triangles, depending on your ray-triangle intersection test's precision.
yes and no. there are precision issues too, but they're somewhat different. in ray tracing, you want your intersection test to err slightly on the conservative side (i.e. report an intersection even when you're very slightly outside your primitive; this is to compensate for roundoff error and avoids cracks). for solid objects, you only ever use one intersection (the closest one) per (sub)pixel anyway, so it's not a big issue if triangles overlap each other slightly. and for reflection/refraction/diffraction, you usually need to spawn secondary rays some small distance behind the original intersection anyway - otherwise you may end up hitting the same surface again (again, due to roundoff error). this prevents the "edges of transparent triangles get drawn twice" problem - of course, if you hit the edge exactly, you usually can't tell which of the two triangles will be hit beforehand - but that's not much of an issue as long as it's only ever one. you certainly don't normally need to worry about tie-breaking.
ryg, in RT is a very similar problem... if your ray hits an edge, and if you have textures with alpha, it is needed to choose only one triangle. And it is possible to know which will be hit beforehand... since you have to sort by distance, you can discard hits with the same z. If your sort algorithm is stable, you will know beforehand wich triangle will be select and wich discarded by the mesh definition.
Other problem is if you have a mesh with overlaping triangles in the same plane or with crossing objects... with alpha textures too. Then all textures should be rendered in a concrete order.
To avoid expensive vertex intersection problem solving, sometimes I've done the dirty trick of adding an small enough epsilon to vertex values... it solves some problems but add other numerical methods round-off errors...
Other problem is if you have a mesh with overlaping triangles in the same plane or with crossing objects... with alpha textures too. Then all textures should be rendered in a concrete order.
To avoid expensive vertex intersection problem solving, sometimes I've done the dirty trick of adding an small enough epsilon to vertex values... it solves some problems but add other numerical methods round-off errors...
Raytracing has NO PROBLEMS WHATSOEVER. It's the equation of life.
..at least as long as you're not doing something silly, like tracing 2-sided surfaces.
texel, please read my whole post before replying. kthxbye :)
6^3, if you render something else than nicely artist prepared syntethic models, I can tell you you better trace double sided polys, take care of coplanar tris, and almost degenerated ones. Really.
hem... pff ... no ok; .... ok;.... a(all have been said...)
Arrara weelll it woukld be long to explain... but welll ,; what the fuck... therze are question that ... Cwezll I mean, they should be assked of course but ?.... well....
... MY BOY.... LIFE WILL TEACH YOU .... AND .... MAYBE .... WHEN THE TIME WILL COME ..... BUT ONLY THEN , HEY ? ...... Y0OU 'LL UNDERSTAND..... MAYBE ....
hem... pff ... no ok; .... ok;.... a(all have been said...)
Arrara weelll it woukld be long to explain... but welll ,; what the fuck... therze are question that ... Cwezll I mean, they should be assked of course but ?.... well....
... MY BOY.... LIFE WILL TEACH YOU .... AND .... MAYBE .... WHEN THE TIME WILL COME ..... BUT ONLY THEN , HEY ? ...... Y0OU 'LL UNDERSTAND..... MAYBE ....