Querying of a point is within a mesh maya python api

Question

I'm trying to figure out a way of calculating if a world space point is inside of an arbitrary mesh.

I'm not quite sure of the math on how to calculate it if it's not a cube or sphere.

Any help would be great!

Answer 1

One can use a simple ray tracing trick to test if you are inside or outside of a shape. It turns out that 2D, 3D objects or possibly even higher dimension objects have a neat property. That is if you shoot an arbitrary ray in any direction you are inside the shape if, and only if you hit the boundaries of your shape and odd number of times. No need to know the normal direction or anything. Just know how many intersections you have. This is easy to visualize in 2D, and since 3D is just many 2D slices same applies to 3D too.

figure 1: Shooting a ray from a point in an arbitrary direction produces an odd number of hits if inside and an even if outside, So O₁ is inside and O₂ is not. As a special case glancing hits need to be tested for curves because they make 2 hits coincide in one place (O₃).

figure 2: Meshed surfaces have a better boundary condition as only vertex hits are glancing However most tracing engines ignore glancing hits as totally perpendicular hits (O₄) would be problematic so they behave right for purposes of this test. Maya tracer is no exception.

Please note this method does not need the surface to be closed, it works none the less it just closes the gap in direction of the ray and open surfaces can report weird results. But can be acceptable in some cases.

Admittedly ray tracing is pretty heavy operation without acceleration routines, however it becomes quite fast once acceleration is in place. Maya API provides a method for this. Note the accelerator is built first then each subsequent call is much cheaper. Here is a quickly written scaffold without acceleration see docs for MFnMesh for more info on how to accelerate:

import maya.cmds as cmd
import maya.OpenMaya as om 

def test_if_inside_mesh(point=(0.0, 0.0, 0.0), dir=(0.0, 0.0, 1.0)):
    sel = om.MSelectionList()
    dag = om.MDagPath()

    #replace torus with arbitrary shape name
    sel.add("pTorusShape1")
    sel.getDagPath(0,dag)

    mesh = om.MFnMesh(dag)

    point = om.MFloatPoint(*point)
    dir = om.MFloatVector(*dir)
    farray = om.MFloatPointArray()

    mesh.allIntersections(
            point, dir,
            None, None,
            False, om.MSpace.kWorld,
            10000, False,
            None, # replace none with a mesh look up accelerator if needed
            False,
            farray,
            None, None,
            None, None,
            None
        ) 
    return farray.length()%2 == 1   

#test
cmd.polyTorus()
print test_if_inside_mesh()
print test_if_inside_mesh((1,0,0))

In your specific case this may be overkill. I assume your doing some kind of rejection sampling. It is also possible to build the body out of prisms and randomize with barycentric like coordinates. This has the advantage of never wasting results. But the tracing code is much easier to generally use.

Answer 2

If you're attempting to solve this problem for any mesh, you'll have trouble, because not every arbitrary mesh is closed. If your mesh can be assumed closed and well-formed, then you might have to do something like a 3D flood-fill algorithm to determine whether there's a path to a point that can see outside the object from the point you're testing.

If you're willing to take a looser approach that gives you an approximate answer, and assumes that normals are all uniformly pointed outward, there's a code example on this page, written in MEL, that you might be able to convert to Python.

http://forums.cgsociety.org/archive/index.php/t-747732.html