• 12
• 12
• 9
• 10
• 13

Tetrahedral volume ray - tri

This topic is 4872 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

So, I read this paper on using tetrahedral volumes of a ray segment wrt triangle to compute whether a ray intersects a triangle. So I wrote a simple implementation, and I have a few questions... First, in the paper (you'd have to use that as a reference), given a ray QQ' and triangle ABC, if QQ' "sees" the triangle such that it winds CCW, then the signs of the volumes of the tetrahedra formed by the segment and each pair of verts are the same (i.e. all positive if front-facing, or all negative if back-facing). Now, that makes sense. However, in the code he gives in section 5:
int i=sign3D(Q,Q’,A,C);
int j=sign3D(Q,Q’,B,C);
int k=sign3D(Q,Q’,A,B);

He computes i and k both with (Q,Q',A..) then C and B last. It doesn't work for me to compute this sign... if instead I use i = sign3D(Q,Q',C,A), then it works fine. It also makes more sense to me to wind around each pair of verts in the same direction... but that's just intuition, not mathematics. However I can't believe there would be an error in the paper, especially because I've seen this same ordering duplicated in works that reference this paper. And no one else has a problem :) Can anyone explain this difference? Seperately, he says in the Lemma in section 4, "Let ABC be a triangle in R³ and Q and Q’ be two points that determine a segment in R³, placed on different sides of the plane determined by ABC" What if Q and Q' are on the same side of ABC? In my experiments, the result is correct for the ray QQ' intersecting ABC... not necessarily the segment defined by QQ'. Is this accurate? I.e. this test makes a good rejection test, but you can't conclude that segment QQ' intersects ABC with just this test alone. Anyway, I wrote an SSE implementation that blasts through triangles in 65 cycles apiece! Pretty good result, I think. (and I did my timing with CodeAnalyst in pipeline simulation mode, so it's very accurate. And that's 65 AMD XP cycles, no idea about P4).