Point inside polyedra

I talk about this here (at the bottom). You can easily extend the algorithm from triangles to polys of any # of vertices, and use that in a crossings test with the faces of the polyhedron.

Do you need to just test convex polyhedra?

Thanks,

Very interesting method!. So now I summarize to see if I understand it right.

I use your equations for every face of my poliedra and then I check if there
is any intersection. Since I'm not just interested in convex poliedra I have
to check if therere are more intersections among the ray and the faces,.. finally I will know if the point is inside or outside depending if the
number is even or odd.

Then from your equation for "t" I can get the lenght of the segments.

Just one question: In order to extend your first equation beyond triangles,..
i.e. for any polygonal faces. I should check for 8,9,.. and 0 instesad of
7 and 0. and I should add to "sign" the corresponding signs of cosines
in order to check if the ray falls inside?,....

I think I understand,.. Thanks a lots!!!

/JoseMalo.

:)

to extend beyond triangles: It's easy to understand the method if you think of it geometrically. Basically, if you imagine a segment passing through a triangle, and you're at one end of the segment looking at the other end. The sign of the determinant is the direction you see (clockwise, ccw) each pair of vertices. So if they are all going the same direction (i.e. the sign of each pair is the same) then the segment indeed passes through the triangle.

Do you see that the 'sign += ?' and 'if(sign == ?' stuff is simply way to test all the signs at once? It's just the C equivalent of the way I wrote my assembly version, but you could easily re-write in other ways as long as it verifies that the signs of all determinants are the same. This means it's important that your polyhedral faces have a consistent winding -- as you go through and test det(R1, v0, v1), det(R1, v1, v2),..., det(R1, vn, v0) (for an n-gon for example).

So, it should also make sense that a determinant of 0 means that the segment passes exactly through an edge. This case is obviously very rare, but it will cause the crossings test to fail (because the 2 polygons sharing the edge could both return "true" on intersection, messing up the even/odd thing). In that case you would need to select a different ray to test with. To test for that case, you will definitely need to alter the code I posted.

By the same token, if the point you're testing lies on an edge of a polygon, then the test will never resolve (any test aganist one of the polygons sharing the edge will have a 0 determinant).

I guess your algorithm to test r0 would be like

0. verify r0 does not lie on a polygon edge.
1. select a point r1 outside the bounding sphere of P
2. test intersection against all polygons in P
3. if any determinants in any tests return 0.0, goto step 1
4. calculate t for each intersecting polygon.
5. if # of results with 0.0f <= t <= 1.0f is odd then r0 is in interior.
6. else r0 in exterior.

That's totally something I just made up, so it could have some serious flaws :)