I have a 3d region defined by mesh (points and connectivity). I have a point(x,y,z) . Need to check whether this point is inside/outside or on the surface of the 3d region. Looking for optimized solution as i need to check for millions of points in C++.
I tried using solid angle method but it is very slow. Please suggest any algorithm or approach for this.
Assuming that your mesh is a mesh of tetrahedrons, you could go with this:
Find a subset of tetrahedrons that could possibly bear that point. That is, rule out as much of candidates as possible. You can do that by using structures such as octrees or kd-trees.
For all tetrahedrons left, compute the barycentric coordinates of the point with respect to a given tetrahedron. If any coordinate is negative, it lies outside.
The barycentric coordinates can be computed by computing the volume of the sub-tetrahedrons with respect to that point and then dividing this volume by the total volume. You'll find formulas with a quick search.
edit: Barycentric coordinates of a tetrahedron would be an example.
(That said, there is always a lot of space for optimization - best would be to find a good library that does this for you. For example, if you would want to compute this in parallel, you'd need some experiments to find out the perfect amount of cores to be used for your current processor and given meshes. Usually it's not the maximum.)
If your mesh consists of octahedrons ("uneven cubes"), you'd need to solve a system of linear equations. The more complex the polyhedrons become, the more complex your formulas become. For a convex polyhedron in general, the best way might be to compute for each face a half space so that the polyhedron is the intersection of those half spaces and then see if the points lies in all of them.
