THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED
On 04/01/2006 at 08:58, xxxxxxxx wrote:
Cinema 4D Version: 8.012
Platform: Windows ; Mac ; Mac OSX ;
Language(s) : C++ ;
As the subject says, what would you consider the best replacement (that handles triangle vertex and edge intersections) for the C++ SDK's GeRayCollider/GeRayColResult?
I have GGII in front of me (V.3: Ray-Triangle Intersection Using Binary Recursive Subdivision) as well as a site with a good algorithm, but only faster than Moller-Trumbore if the triangle normals are precomputed. Of course, there is also the older algorithm of Badouel (on which GGII is based).
Of course, none of these really state that they do handle the triangle vertex and edge cases, but it appears to be so. Any input welcomed!
On 04/01/2006 at 22:27, xxxxxxxx wrote:
Looks like the algorithm on that site works wonders. I can't believe that I shoe-horned it into my 'RayCollider' class, made all of the changes to the algorithm and corresponding changes to the code that uses the RayCollider and it not only compiled, but worked without any crashes or issues - first run! And it does handle ray intersection on triangle vertices and edges. Yippee!
On 30/01/2007 at 03:54, xxxxxxxx wrote:
Heh.. I just found this while trying to figure out why RayCollider doesn't work on edges.
BTW, thanks for the link. His code actually still has problems in some cases (has to do with the normals of the rays being cast straight out along axis, combined with vertex/edge intersections), but it's just a math rounding error that can be fudged into working easily enough.
In particular, here's the line I changed:
if (t < -0.00000022 || ((s + t)-1.0) > 0.00000006) // point is outside T
...that used to test for t < 0.0 and (s+t) > 1.0
Those small numbers take care of the rounding errors in situations where a ray normal has 2 out of 3 zero values and the ray intersects with an edge/vert. There is another case that seems to be when the normal is at exactly 45deg angles that it also fixes.
On 30/01/2007 at 17:35, xxxxxxxx wrote:
How did you come up with the values (epsilons) you are using to workaround the rounding error?
On 30/01/2007 at 18:48, xxxxxxxx wrote:
I had a test-case that I knew was supposed to collide, but wasn't. So I put in some print statements to see what values were coming out and just went slightly above/below those.
So far, this has worked for everything I've thrown at it, but I can't guarantee that will will for every case.
Basically, you get the failure in question when you have a normal that runs along one axis...
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
..(or possibly extremely close to one of those), combined with an intersection along an edge or vertex (of course a vertex is part of the edge, so it's basically an edge problem).
On 30/01/2007 at 21:58, xxxxxxxx wrote:
Ah. Good to know. I've put the code into my RayCollider and will see how this might change things.
On 01/02/2007 at 03:52, xxxxxxxx wrote:
Hmm.. I was testing some other meshes and still having a problem, so I don't have a final answer yet.
On 02/02/2007 at 04:06, xxxxxxxx wrote:
Edit: I take that back... I may still not have the final numbers, but I was wrong about why the most recent tests (my post above) were failing. Those values are still working for me so far.
On 03/02/2007 at 11:34, xxxxxxxx wrote:
Edit again... I have now found cases where the test above that line (the one that just tests s) also needs the correction.