Point in mesh scripts not working

Truman,
I’ll post a .blend demonstrating the problem.

Abidos,

You are correct, I only suggested it if you do NOT need 100% accuracy. For a quick method to find the nearest vertex, here’s what I came up with.

import bpy
from mathutils import Vector

# Get the active object and mesh
ob = bpy.context.active_object
me = ob.data

# Set the position to find the closest vertex to
position = Vector((0, 0, 0))

# Find the nearest vertex
min_dist_vert = min(me.vertices, key=lambda vert: (position - vert.co).length_squared)

# Print the nearest vertex's index
print(min_dist_vert.index)

Truman and Liero, here is a .blend file that demonstrates the routines you provided failing. Maybe you can figure out why.

Atom’s routine, can be made to fail also, but in general it is more accurate.

Let me know what you think.

Attachments

testInside.blend (1.07 MB)

Hi terrachild,

Not sure what’s going on inside your script, because I wrote this one (which I think is equivalent) and it works fine.

mytest.blend (439 KB)

You can generate some cubes and then test them with any of the algorithms. To use it selected all the little cubes and hit “Run Script” on the TestInside text. Let me know how this goes.

Cheers,
Truman

I tried your .blend and yes it does work, but you are generating a small number of cubes.
To come up with those incorrect results in my .blend file above, I generated hundreds, if not thousands of cubes.
Also, this is a very easy test with a simple cube for the mesh.
On more complex meshes, differences between the routines is more apparent.
You have to generate a lot of points to see the problems with the routines.

If you open my .blend, select a red cube and hit test, do you also get an incorrect result?

terrachild,

OK I’ve figured out where the issue lies. The problem can occur when the closest point the mesh lies on an edge or a vert. In this case the closest point on mesh will return as the normal, the normal of a face which contains the vert or edge. However, this may lead to the dot product being negative when the point is outside, due to Blender’s precision in floating point numbers. If instead of

if dot < 0.0:

you use

if dot < -0.005:

Then it will work, I’ll investigate if this can be fixed in a better way, perhaps the C implementation can avoid this.

Cheers for finding this!
Truman

You’re welcome.
Sometimes I feel like I’m chasing ghosts when I try to explain a bug I’ve found.
Glad I caught one this time!

Hahaha, yeah it can feel that way. If I can get the C version into Blender by default I’ll let you know, we might be able to increase the accuracy.

Cheers,
Truman

Well, I just performed thousands of tests, 10’s of thousands actually.
Here’s what I found:
One number won’t work for every mesh.

As the number get’s smaller, from -0.005 to -0.0005, (larger actually since it’s negative) the routine will find points closer to the mesh’s surface, but have more false “Inside” results.

Also, your value of -0.005 will work for simple meshes, but I had to change it to -0.05 to work with a more complex mesh. The problem with moving the number in this direction is it cause more false “outside” results if the mesh has areas in it that that are close together.

Why am I doing all this you ask?
I’m about to release an addon I think people will really like, and I’ve been testing and tweaking several routines to find the best one.

Hi terrachild,

The issue with the function closest_point_on_mesh was due to the fact that only the closest point on a face was found. It’s possible also to find the closest vertex and edge which would allow the problem to be fixed. I’m working on this now.

Cheers,
Truman

Yea, go Truman!
I’ll credit you in my Addon for helping me.

Truman did a patch to find out if a point is inside a mesh and that works fine (at least the examples I checked).
But now a drawback: Moving or resizing the object has no effect on … that function obj.point_inside_mesh([x,y,z])
(take the cube and (x,y,z) = (0,0,2)] and S 3 the cube ==> outside
Why? because object coordinates are used …

Trying to find a work around I did not have success yet see my try:


import bpy
from add_utils import AddObjectHelper, add_object_data
#from mathutils import Vector
obj = bpy.context.active_object
obj.point_inside_mesh([0,0,2])
bpy.ops.transform.resize(value=(3, 3, 3))

mat = obj.matrix_world
obj_vertices = obj.data.vertices
obj_faces = obj.data.faces
obj_edges = obj.data.edges

new_vertices = [mat * vert.co for vert in obj_vertices]
new_edges = [edge.vertices[:] for edge in obj_edges]
new_faces = [faces.vertices[:] for faces in obj_faces]

#print(new_faces,new_edges,new_vertices)
mesh = bpy.data.meshes.new(name='New Object Mesh Worldsize')
mesh.from_pydata(new_vertices, new_edges, new_faces)
mesh.update(calc_edges=True)
    # useful for development when the mesh may be invalid.
    # mesh.validate(verbose=True)
add_object_data(bpy.context, mesh, operator=None)
new_obj = bpy.context.active_object
new_obj.location = (0,0,0)
bpy.ops.transform.resize(value=(1/3, 1/3, 1/3))

new_obj.point_inside_mesh([0,0,2])

Idea make a copy of the object using matrix_world to adjust for changes … but not yet ok … something is missing …

File “\make_global.py”, line 24, in <module>
RuntimeError: Error: object “New Object Mesh W.000” has no mesh data to be used for finding nearest point.

EDIT:
Truman gave the correct ‘easy’ solution
transfer the point to check by the inverse of the objects martrix_world!

The reason why I see failures is that the test code is only passing the location origin of the object. It should be passing the points from the bounding box for the initial culling test.

Here is my modification the TrumanBlending test with the < 0.005 modification applied.


print("Begin.")
obs = bpy.context.selected_objects

inside_ob = bpy.data.objects['Cube']

good = bpy.data.materials['Good']
bad = bpy.data.materials['Bad']

for ob in obs:
    results =[]
    if ob.name != inside_ob.name:
        print ("Reviewing collision candidate [" + ob.name + "].")
        bb = ob.bound_box
        for pnt in bb:    #Should only be 8 points.
            x = pnt[0]
            y = pnt[1]
            z = pnt[2]
            loc = ob.matrix_world.copy() * Vector((x,y,z))
            if point_inside_mesh2(loc, inside_ob) == True:
                results.append(True)
            else:
                results.append(False)
                
        # Default to not intersecting until we examine the array of results.
        matFlag = False
        for r in results:
            print (r)
            if r == True:
                matFlag = True
        if matFlag == True:
            ob.material_slots[0].material = good
        else:
            ob.material_slots[0].material = bad
        
print("End.")

This gets more cubes to turn green than any other current option. Once you have a bounding box intersection then you have a candidate for further examination for mesh based collision. You could just break on the first True in the bounding box loop as well.

Attachments

25_Point_In_Mesh_Revisted.blend (83.1 KB)

Atom,

I tried your bounding box routine with the file you posted, but as you can see in the following image, the two cubes are intersecting, although no vertices from either cube is inside the other. Red means the cube is not intersecting.


It doesn’t work.

Is there a way to detect this type of intersection.

Thanks

Some advance? (to 100% precise)