Point in mesh scripts not working

I’ve tried several scripts that attempt to determine whether a point is inside of a closed mesh. I can’t get any to work.

Here is one from Atom:

def pointInsideMesh(point,ob):
    # provided by aothms.
    # axes = [ mathutils.Vector((1,0,0)), mathutils.Vector((0,1,0)), mathutils.Vector((0,0,1))  ]
    # @Abel, ok just one then
    axes = [ mathutils.Vector((1,0,0)) ]
    outside = False
    for axis in axes:
        # @Atom you're right, ray_cast is in object_space
        # http://www.blender.org/documentation/250PythonDoc/bpy.types.Object.html#bpy.types.Object.ray_cast
        mat = mathutils.Matrix(ob.matrix_world).invert()
        orig = mat*point
        count = 0
        while True:
            location,normal,index = ob.ray_cast(orig,orig+axis*10000.0)
            if index == -1: break
            count += 1
            orig = location + axis*0.00001
        if count%2 == 0:
            outside = True
            break
    return not outside

This throws an error at “orig = mat*point”
The console says: "Vector multiplication: not supported between ‘NoneType’ and ‘mathutils.Vector’ types.

So I tried another script from: Wikibooks

from Blender import *

def pointInsideMesh(ob, pt):
        Intersect = Mathutils.Intersect # 2 less dict lookups.
        Vector = Mathutils.Vector
        
        def ptInFaceXYBounds(f, pt):
                        
                co= f.v[0].co
                xmax= xmin= co.x
                ymax= ymin= co.y
                
                co= f.v[1].co
                xmax= max(xmax, co.x)
                xmin= min(xmin, co.x)
                ymax= max(ymax, co.y)
                ymin= min(ymin, co.y)
                
                co= f.v[2].co
                xmax= max(xmax, co.x)
                xmin= min(xmin, co.x)
                ymax= max(ymax, co.y)
                ymin= min(ymin, co.y)
                
                if len(f.v)==4: 
                        co= f.v[3].co
                        xmax= max(xmax, co.x)
                        xmin= min(xmin, co.x)
                        ymax= max(ymax, co.y)
                        ymin= min(ymin, co.y)
                
                # Now we have the bounds, see if the point is in it.
                return xmin <= pt.x <= xmax and \
                        ymin <= pt.y <= ymax
        
        def faceIntersect(f):
                isect = Intersect(f.v[0].co, f.v[1].co, f.v[2].co, ray, obSpacePt, 1) # Clipped.
                if not isect and len(f.v) == 4:
                        isect = Intersect(f.v[0].co, f.v[2].co, f.v[3].co, ray, obSpacePt, 1) # Clipped.
                                
                return bool(isect and isect.z > obSpacePt.z) # This is so the ray only counts if its above the point. 
        
        
        obImvMat = Mathutils.Matrix(ob.matrixWorld)
        obImvMat.invert()
        pt.resize4D()
        obSpacePt = pt* obImvMat
        pt.resize3D()
        obSpacePt.resize3D()
        ray = Vector(0,0,-1)
        me= ob.getData(mesh=1)
        
        # Here we find the number on intersecting faces, return true if an odd number (inside), false (outside) if its true.
        return len([None for f in me.faces if ptInFaceXYBounds(f, obSpacePt) if faceIntersect(f)]) % 2

# Example, see if the cursor is inside the mesh.
if __name__ == '__main__':
        scn= Scene.GetCurrent()
        ob= scn.getActiveObject()
        pt= Mathutils.Vector(Window.GetCursorPos())
        print 'Testing if cursor is inside the mesh',
        inside= pointInsideMesh(ob, pt)
        print inside

I tried to convert this to 2.59, but as close as I got, I just couldn’t get it to run properly.

Can either of these be made to work in 2.59?

or

Does anyone have a working script that will do this, and work for complex meshes not just for boxes and spheres?

Thanks.

your problem is not to know the difference about invert and inverted and the like :wink:

This works


import bpy
import mathutils
def pointInsideMesh(point,ob):
    # provided by aothms.
    # axes = [ mathutils.Vector((1,0,0)), mathutils.Vector((0,1,0)), mathutils.Vector((0,0,1))  ]
    # @Abel, ok just one then
    axes = [ mathutils.Vector((1,0,0)) ]
    outside = False
    for axis in axes:
        # @Atom you're right, ray_cast is in object_space
        # http://www.blender.org/documentation/250PythonDoc/bpy.types.Object.html#bpy.types.Object.ray_cast
        mat = ob.matrix_world
        mat.invert()
#        mat = mathutils.Matrix(ob.matrix_world).invert()
        orig = mat*point
        count = 0
        while True:
            location,normal,index = ob.ray_cast(orig,orig+axis*10000.0)
            if index == -1: break
            count += 1
            orig = location + axis*0.00001
        if count%2 == 0:
            outside = True
            break
    return not outside
print(pointInsideMesh( mathutils.Vector((3,0,0)),bpy.context.active_object))

I checked with the default Cube and (0,0,0) and (3,0,0) got True and False

Edit:
I did not check if this algorithm is the most intelligent one http://bafull.cgcookie.netdna-cdn.com/images/smilies/sago/eyebrowlift.gif

It seems to be working with simple meshes at least, but it is doing something strange to the ob mesh passed to it.
I think the line “mat.invert()” is changing the scale of the mesh, then when you run the script again, the mesh returns to normal.
How to avoid this?

Also, can anyone comment on whether the approach used in the second example I provided is more accurate for complex meshes?

Thanks.

Your second example will not run (unchanged) in Bl 2.59
what I see is wrong e.g.
ob.matrix_world
mathutils (not MathUtils)
vector * matrix must be matrix * vector
getData becomes mesh = obj.data

OH I see just now it is old Blender
Why did’nt you give YOUR translation?
waiting for it … (late afternoon) …

EDIT:
just seeing ‘cursor-position’ and that is NOT 3D but some 2D coordinates,
That means, that the cursor is only by chance 0 (ZERO) inside a face.
So you need to describe what you really want! An orthogonal projection??? (and that is too dependent on
which screen you are looking at(Nump 1 3 7 with or without nump 5 !!))

Your correction to the first example does make it work, even with odd shapes like a torus, but the correction is changing the size of the object passed to the function.

I added another invert to reverse the change like this:

mat = ob.matrix_world
        mat.invert()
        #mat = mathutils.Matrix(ob.matrix_world).invert()
        orig = mat*point
        mat.invert()

I’m just wondering if there isn’t away to do this without actually changing the object mesh passed to the routine?

That way the second “mat.invert” wouldn’t be necessary.

Thanks.

PS my translation of the second example to 2.59 was incomplete. That’s why I didn’t submit it. But I am wondering if it is a better approach?

there is a new closest_point_on_mesh method…
tried this simple script and seems to work fine:


## normals should be pointing out
## and no object transformations

import bpy, math

obj = bpy.context.object
cur = bpy.context.scene.cursor_location

cpom = obj.closest_point_on_mesh(cur)
vec = cpom[0] - cur
ang = math.degrees(cpom[1].angle(vec))

if ang < 90: print (ang, 'inside')
else: print (ang, 'outside')

1 Like

Hi terrachild,

I submitted a patch to get this functionality into Blender by default (see here http://projects.blender.org/tracker/index.php?func=detail&aid=28173&group_id=9&atid=127) but with 2.59 coming out it hasn’t been accepted yet. The method in the patch is almost exactly the same as liero’s and can be replicated in Python instead of C,


## normals should be pointing out
## and no object transformations

import bpy

obj = bpy.context.object
cur = bpy.context.scene.cursor_location

cpom = obj.closest_point_on_mesh(cur)
vec = cur - cpom[0]
dot = cpom[1].dot(vec)

if dot < 0.0: print(dot, 'inside')
else: print(dot, 'outside')

If you’re doing alot (as in thousands) of these checks it should be a little quicker as it doesn’t actually need to calculate the angle which can be slow, also you don’t need the math module. Hope that’s useful.

Cheers,
Truman

1 Like

very useful, thanks Truman for your work!

Truman,

I tried it, and as advertised, if you move the mesh, it doesn’t work.

Is there some easy way to make it work, even if the mesh has been transformed?

Thanks

Hi terrachild,

Try this:

## normals should be pointing out

import bpy

obj = bpy.context.object
cur = bpy.context.scene.cursor_location.copy()

cur = obj.matrix_world.inverted() * cur

cpom = obj.closest_point_on_mesh(cur)
vec = cur - cpom[0]
dot = cpom[1].dot(vec)

if dot < 0.0: print(dot, 'inside')
else: print(dot, 'outside')

Cheers,
Truman

1 Like

Truman,
That change did make it work with translated and rotated objects.

I am exhaustively testing various routines with thousands of cycles to find one that is foolproof.

The one you provided is not nearly as accurate as the one from Atom.

I can make his goof-up also, with a complex mesh, but even with a simple cube, yours fails far too often. I don’t think this version, as is, is the best candidate for trunk.

I’m not sure what is throwing it off. The strategy seems good. If you’re interested in improving it, I can send you a .blend with a couple of objects that demonstrate the routine failing to work.

Thanks

Hi terrachild,

I’m surprised it’s failing for a cube, it works fine for me and I’ve tried it with several other meshes. If you can post a blend file that would be great. I’d like to make this work.

Cheers,
Truman

I have a couple of questions… mostly to TrumanBlending… (and others who may know the answers)…

closest_point_on_mesh - Is it a new property of the objects in 2.59? Is it available in 2.58 too? (background - it gives me an error when trying Truman’s code @ 2.58) Where can I read about objects’ and meshes’ properties in 2.59???

cur = obj.matrix_world.inverted() * cur gives me an error in 2.58 as well… Why may be that?

Lastly, I assume that closest_point_on_mesh gives you the closest point of the mesh verts… Sooo… if I put my cursor at (5, 1, 0.1) and scale the default cube by 4 on Y axis only (normals remain outside, ok?), then while running Truman’s code, the closest_point_on_mesh would give me (1, 4, 1) thus leading to a dot product of vectors = -31.3546, i.e. telling me the point is inside, which is INCORRECT?!?!? Why’s that so?

Regards,

tested in SVN of today W32 with your (Abidos) input got this:
Vector((5.0, 1.0, 0.10000000149011612))
4.000000000001498 outside

So get 2.59! from ‘today’ :wink: (for w32 to be found in my ‘dropbox’, with numpy and --instrument)

@PKHG - which means that closest_point_on_mesh gives you an intermediate point on the mesh surface, right??? I wonder what would be the result in case of non-planar faces? I wonder what value do you have for the cpom vector? So I get again to my previous question - where can I read more about the new properties/methods of objects, meshes, etc. in 2.59 API? As per my search efforts, on Blender site there is an API page with a lot of sub-pages but only for the operators…

Regards,

Searching in the source for closest_point_on_mesh … if found I will try to explain …

EdIT: found
grep -lr closest_point_on_mesh .
./blender/makesrna/intern/.svn/text-base/rna_object_api.c.svn-base
./blender/makesrna/intern/rna_object_api.c

the relevant part IMHO is this:


        if(BLI_bvhtree_find_nearest(treeData.tree, point_co, &nearest, treeData.nearest_callback, &treeData) != -1) {
            copy_v3_v3(n_location, nearest.co);
            copy_v3_v3(n_normal, nearest.no);
            *index= nearest.index;
            return;
        }
    }

Do not know when and where its description will be found :wink:

Hi Abidos, PKHG,

The closest point on mesh function does indeed return the closest point anywhere on the mesh, that may be a vertex, on an edge or on a face. I wrote the closest point on mesh function for the IvyGen addon, it merely exposes the ability to find the closest point on the mesh as used in other places in Blender such as cursor snapping and particles.

Abidos, the reason for the matrix error in 2.58 is that the multiplication order was reversed for 2.59 as it was incorrect. Also, the closest point on mesh was added for 2.59 and is not available in 2.58.

If someone can post an example of the inside mesh function failing that would be great.

Cheers,
Truman

And is there a function telling you which mesh vertex is the closest to a given point?

Regards,

Abidos,

Nothing that will specifically do that. However, the nearest point on mesh function returns a tuple containing;

  • The coordinates of the closest point on the mesh
  • The surface normal at that point
  • The index of the face on which the closest point lies

Depending on how accurate you need the result to be you have several options.

To get the closest vertex every time, you can loop through all vertices in the mesh but this will be slow. Alternatively, if you do not need to be 100% accurate you could simply check the vertices that are part of the face returned by the closest point function, i.e. check the vertices in the face with index returned by the 3rd tuple entry.

Cheers,
Truman

@TrumanBlending - Ok, ok… but NOT ALWAYS one of the verts of the closest face is the closest vertex of that mesh! To describe it in a very simple way - the closest face can be the widest face too, so even in a convex body it is quite possible NONE of its verts may be the closest vertex to a given point.

Regards,