Point inside a 3d closed volume

Question

I have a 3d closed volume defined by 6 surfaces, every surface has 4 vertices.

So, I want to check if a given point is inside the volume or outside it. A solution which I thought of was:

1. Draw a random line from the given point and check where it intersects the surfaces which enclose the volume. Since I am using vector algebra for calculating the intersection of the line and surface the intersection point can lie anywhere on the 3d infinite surface.

2. Now I check if this intersection point happens to lie on that face which lies on the infinite plane and encloses the volume.

For this I again want to draw a random ray from my point of intersection to the respective face of the volume and check if point lies on the face or not.

But I don't know how to check this feature of locating if it is on the surface  
or not. Can someone please suggest how can I do it.



P.S. One way of doing this was extending ray casting to 3d but that involves 
comparison of slopes to check the orientation. So how can I check orientation 
of 3 points in 3d space. I have 4 vertices which make up that face, I know the 
point under consideration. How can I check if this point lies clockwise or   
counter clockwise to the surface. 

Answer 1

To consider your problem, we must first consider what the meaning of inside or outside is. With a four surfaces solid, each surface divides the space in exactly two sides, and in general, the four surfaces divide the space in 9 regions, only one of which is bounded, delimiting a tetrahedron (but if we select carefully the surfaces we can reach to even no bounded region ---for example making two of them parallel). So, in general you have to decide which of the sides of the planes mark the inside or the outside (well, it doesn't matter also, as being outside is the same as not being inside).

With more faces, the problem complicates (and complicates much further), as you can have several bounded regions that also define solids, so you need more information that only the planes that delimit it. The problem even complicates more if the region results in a non convex region, because your point can be in some part of your region that matches the in one side for some planes and in the wrong side for others, and continue to be inside your solid. Just see a delimited polygon like this

and the possibilities of making bounded regions

The first thing you need is to adequately define your solid, delimiting the faces with edges and somewhat establishing the edges and vertex that delimit one face, how faces connect themselves to form your solid.

Once you have this situation, you have a set of faces, and vectors pointing to the outside for each face (in a continous manner, so you don't end with a face normal pointing upwards, and the next pointing downwards). The next thing you need to do is to divide your solid into a convex solid. It can be demonstrated that for a 3d solid made of plain faces, it can be subdivided into a finite set of convex solids.

I will try to illustrate the same problem in 2D, but essentially is the same in 3D:

First, we have the initial poligon, let's suppose it is convex (this is an important property for this purpose I shall mention later):

Let's imagine it is a 3D asteroid and you are somebody walking on its surface. If you begin walking, you'll pass through all the lines poined in yellow. These are the normals and for that you need to know from each face which faces are reachable and construct a map of normals to these surfaces as I have made. As you walk on the asteroid, you mark the normals to know where the interior of the asteroid is, and you are delimiting it. Now, we have a map of our asteroid with all the normals. Let's draw the semispace below us (one side of the surface that is below us) In geometry, this can be represented by a plane (a plane has the property that all its points are orthogonal to a vector, so X*V=0 where * represents the dot product. If we take the center of our poligon and the normal vector as the yellow vector in our drawing, we'll get (X - P)*N = 0, where X is the position of a point in the plane, P is our position (the center of the face) and N is a vector normal to the plane, pointing upwards (to the outside of the asteroid)

Well, this equation has the property that if we substitute X by any position in the space, all the points X below the plane have a value (X - P)*N < 0 and all the sky values have it > 0.

If I do the same for the four normals, I get to this: ... dealing to and the point in question X will be buried into the asteroid only if the four planes give (X - X_face)*(N_face) < 0 where now, X_face is the center of the face, and N_face is the face normal pointing outwards of our asteroid. The point will be inside the asteroid only if the four conditions apply.

But what happens if the asteroid is not convex?

If you draw the normals, this will not help... as there are points that are inside the asteroid and fail some of the tests (remember, the point has to be below all the surfaces, but isn't (as shown below):

The problem is that the polygon (or the polyhedron) is not convex, and we cannot apply the algorithm there. So first we have to solve the problem of making it convex.

If you begin to follow all the surface of the asteroid (conserving the normals) when you cross an edge, you'll get to another plane that increases or decreases slope, so if it increases slope, you will mark that edge (vertex in our polygon) as anomalous (we have marked them in red) and if it decreases, we'll mark them as normal (we have marked them in green):

When all edges are normal, no problem, as our asteroid will be convex, but when any of them is anomalous, we have to continue in that plane (digging in the asteroid on all the plane) until we get to another surface (we have prolonged the plane up to divide our poligon) as such:

as we have a finite number of edges, and only some of them have been marked as anomalous, this process is warranted to finish (remember that you can get the other side trying to find a face (side) of your polyhedron (polygon) that has vertex up and vertex down (in the sense we explained before))

so you have divided your polyhedron into a finite set of convex polyhedra that can be applied the first algorithm.