From: Steve Baker <sjbaker1@ai...>  20040326 18:47:30

Andy Ross wrote: > Steve Baker wrote: > >>As I pointed out before, it is utterly CRUCIAL that whatever >>replacement algorithm we use handles the special cases in such a way >>that every point ends up either hitting a triangle or it's neighbour >>and NEVER falling through between two triangles that share an edge  >>or between a bunch of triangles that completely surround a point. >>Ideally, it should only ever return one of the two triangles as a hit >>in those circumstances. > > Exactly. To be fair, though, that behavior is sort of a holy grail. > I'm not aware of any implementations that return hits for exactly one > adjoining triangle in a mesh. Well, it's certainly possible. I have implemented such algorithms. They are very important for rendering polygons on a raster display. You (essentially) need to decide whether each pixel is either inside or outside of a triangle in order to know whether to render it or not. You don't want holes in objects made of tesselated triangles  but you can't have overlaps either because triangles could be translucent and you'd get bright 'beads' along all the edges that get hit twice. This is (in essence) the same problem as the pointinpolygon problem  and the solution is the same. The trick is that your algorithm can measure the signed distance from the 'test' point to each edge of the triangle  if all three distances are positive  then the triangle is cleanly inside  if all three are negative  then it's cleanly outside  if one distance is zero then the point is exactly on the edge (to the precision of your computer) and if two distances are zero then you are exactly on a vertex. There are two things that make this algorithm go wrong. 1) If that distance computes to EXACTLY zero then you have to decide whether to include the point in the triangle or exclude it. Always including it results in triangles overlapping when they shouldn't, always excluding it results in gaps between triangles that are actually perfectly touching. Neither are acceptable to rasterizing algorithms. For collisiondetection, overlaps are by far preferable to gaps because otherwise things driving or walking over surfaces tend to fall through these microscopic holes. 2) In order to get *signed* edge distances, you need to compute the line equation for the edge in a consistent direction (eg clockwise around the triangle). If you do that then 'Bad Things Happen'. There is obviously a roundoff error inherent in the line equation calculation. For two vertices 'A' and 'B', computing the distance from the test point to the line A==>B may produce a sligthly different answer than from B==>A (other than just the sign difference). So even if you solve (1) by letting polygons overlap slightly, then this problem will still bite you when both polygons have roundoff error in the negative direction. The fix for both of these problems is to sort the vertices of the edge before computing the line equation so that the calculation for the edge distance produces EXACTLY the same answer for both triangles no matter what. Deciding which vertex is first and which is second is a slightly tricky matter. One way is to make the vertex with the largest X coordinate be the first into the calculations  and the one with the smallest X be the second. If the X coordinates are the same  then sort them by Y coordinate, and if the Y coordinates are the same, sort by the Z coordinate. If your vertices are guaranteed to be literally shared in memory, then the vertex with the largest memory address is a good trick for sorting them. You can also do things like computing a hash code from the bytes of the X,Y,Z coords and using the result as the sort criteria. It's not 100% bullet proof  but it's definitely "good enough". So, having sorted the vertices, if you had to swap the vertices in order to do that, flip the sign of the distance result  if you didn't have to swap them then don't. If the result calculates out as EXACTLY zero  then arbitarily choose to make that point be 'inside' only if you DIDN'T swap the vertex order. This algorithm is utterly perfect for points on triangle edges. You *STILL* have to do something special when a point goes exactly through a vertex of the triangle because it can still show up as being inside multiple triangles that share that vertex. Choosing one of (potentially) dozens of triangles that share that point is possible  but tricky. You have to do something like reducing the test to two dimensions by looking at it from the 'dominant' axis direction. Now you can say something like 'whichever polygon covers the X==0 axis owns the point'. This is a *nasty* subject  and one that has resulted in at least one $200,000 integrated circuit design having to be redone! > What most algorithms do is simply add a fudge factor to the triangle > size to make sure that they overlap. The problem is that the fudge > factor ends up being coordinatesystem dependant, and thus the > algorithm won't work generically. Yes  that really doesn't work. It's not just coordinate system dependent  you also don't know which direction to fudge it in for generalised 3D surfaces.  Steve Baker  HomeEmail: <sjbaker1@...> WorkEmail: <sjbaker@...> HomePage : http://www.sjbaker.org Projects : http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net http://prettypoly.sf.net BEGIN GEEK CODE BLOCK GCS d s:+ a+ C++++$ UL+++$ P L++++$ E W+++ N o+ K? w !O M V PS++ PE Y PGP t+ 5 X R+++ tv b++ DI++ D G+ e++ h() r+++ y++++ END GEEK CODE BLOCK 