Here's the issue: suppose I want to find whether a point is inside or outside a 3D shape (or right on the surface). Theoretically, I can just extend a ray from that point in any direction, and count how many times it intersects with any triangles. If the number is even, then it was outside (because it must cross in then out each time), and if it's odd, then it's inside (because it must cross once to get out, then an even number of times after that).

The problem is this: first of all, suppose that it crosses through at an edge between 2 triangles to enter or exit the shape. It would count twice, because it's intersecting both polygons. Or suppose it intersects at a vertex, then it will count for however many triangles share that vertex.

Also, suppose I just graze an edge of the boundary of the 3D shape, so it only intersects once to go all the way through, when I'm expecting it to intersect twice. Actually, in the case of grazing an edge, that would work, because it would count twice, but if the previous problem were fixed, it would cause this to only count once, producing a new problem. And if it intersects a vertex, all bets are off!

So what's the right way to do this?

This looks to be a popular reference:

http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#3D Polygons

If the polygon is closed, you can just project it onto a plane.

I assume your "3D shape" is a set of triangles that form an oriented manifold (so triangles don't intersect except along edges, every edge belongs to exactly two triangles, and no Klein-bottle shenanigans). I don't know about the right way to do it, but I can try to give you something that will be more robust [and slow]: Compute the solid angle from the current point to each triangular face in your manifold, with a sign given by the orientation. You can use the formula in this Wikipedia page. The sum should be a multiple of 4*pi, which is 0 if the point is outside of the manifold.

I don't think you should worry about detecting when a point is on the surface exactly, because code that depends on that is bound to be very brittle.

This looks to be a popular reference:

http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#3D Polygons

If the polygon is closed, you can just project it onto a plane.

I think he is asking about polyhedra, not polygons. I'm not sure how much of that page will help. What I suggested is the 3D version of the section "Inclusion Testing by Subtended Angles".

EDIT: I see there is a section "Testing Point Inclusion in a Polyhedron" at the end, but it doesn't seem very informative.

This looks to be a popular reference:

http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#3D Polygons

If the polygon is closed, you can just project it onto a plane.

I think he is asking about polyhedra, not polygons. I'm not sure how much of that page will help. What I suggested is the 3D version of the section "Inclusion Testing by Subtended Angles".

EDIT: I see there is a section "Testing Point Inclusion in a Polyhedron" at the end, but it doesn't seem very informative.

I saw that after posting.

Glass_Knife, yes I'm talking about 3D shapes, and they may also be concave.

Alvaro, it follows all the rules you specified about triangles, edges, etc. But how can I check if it's a multiple of 4pi? Wouldn't a round-off error cause it to never be exact (especially since pi isn't rational).

But now that I think about it, it seems like any time the point is outside, the sum of all solid angles would be 0, and whenever it's inside, the sum would be 4pi, but not any arbitrary multiple, just 4pi, right? How could it be a different number than that?

Edit: I may have misinterpreted what you said. To clarify, did you mean it's always a multiple of 4pi, and more specifically, always 0 if outside and always 4pi if inside, and never any other number than those two?

P.S.: I also just realized, would it create a problem if the point is exactly on the surface? Because whatever polygon it's on, how would it know whether to count the angle positively or negatively? In any case, I guess the angle would always be half the sphere, right?

Sorry, one more thing: do you happen to have a proof of this? I absolutely never trust any math formula until I know exactly how and why it works the way it does.

Depending on the orientation, the result could be -4*pi.

If the point is exactly on the surface, I think you'll end up trying to compute 0/0 or something. I don't have time to think about it carefully right now, sorry.

You could also do points in BSP tree. This works because the construction of a plane-BSP tree in and of itself constructs a valid convex decomposition. You can query a point against the tree for inclusion. Conceptually this is very similar to a ray test.

The problem with ray tests is you have to be very careful about how you form the test. You should ensure that you share calculations across triangles (somehow). This makes it such that if a ray pierces very near to an edge shared by two triangles, the result is always TRUE/FALSE or FALSE/TRUE. There can also be issues with a ray hitting very near to a vertex. These numeric problems can be difficult to deal with.

If you have vertices as you seem to imply, you probably have normals. Just look at the normal. If not, then look up 'left turns' to find how to do it the hard way.