Detecting if a point is inside a mesh? 2.5 API

(Atom) #1

Hi All,

I am wondering if anyone has any code to detect if a given point is inside a given mesh, using the 2.5 API?

The pointInside function from the 2.49 API was not ported over to 2.5.

Even a simple solution like is point inside a bounding box would be a good start.

Thanks!

(aothms) #2
      ^                  ^
  +---+---+    +-------+ |
  |   |   |    |       | |
  |   |   |    |       | |
<-+---x   |  <-+-------+-x
  |       |    |       |  
  |       |    |       |  
  +-------+    +-------+  

I think you’ll have to count the number of ray-intersections with the mesh originating from the point. If the number of intersections is even, the point is outside the mesh.

(Abidos) #3

@ aothms - You should have mentioned that your explained tacktics works for completely closed figures. If there is a hole, even a small one, perhaps the smallest hole in the World, you would never be sure!!! In fact, if there is a small hole, one can think of a point or another relatively small object being inside the bigger one BUT the problem is in the criteria… The criterion you’re explaning is calid for figures (bodies) without holes, i.e. such that the Euler formula is valid: V - E + F = 2

I think one should first check if the Euler’s formula is valid for the body, then do what ever he/she wishes to do else. As per the math, the Euler’s formula is TRUE for convex polyhedra. May be it is valid for some concave bodies w/o holes too. Soooo… one should be careful with that :wink:

Regards,

(Atom) #4

Dang, I understand the concept, I was hoping for code. For my implementation I can assume no holes in the mesh.

But doesn’t that odd even approach rely on the length of the cast being long enough to pass through the mesh?

I am not strong on math, but logic. To cast a ray in 3D I have an origin.I read you need to cast in 6 directions and evaluate each ray for odd even. If any of the rays have a result of even, then the point is outside the mesh.

So I guess it is the 3D raycasting/raytracing code that I need to get going?

(aothms) #5

That’s a good addition abidos. As for the code, this should do the trick:

def pointInsideMesh(point,ob):
    axes = [ Vector((1,0,0)) , Vector((0,1,0)), Vector((0,0,1))  ]
    outside = False
    for axis in axes:
        orig = 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
(RickyBlender) #6

if you make a more complete example let us know

and is this working in 2.5 also ?

like the Point is it specified as a float or list ?

happy 2.5

(abelabel) #7

You won’t need to cast the ray in six directions, one should be enough (assuming the point is not exactly on one of the faces or their extensions). ideasman42 provides some insight here: http://blenderartists.org/forum/showthread.php?t=101122, another implementation (in 2.4x) can be found here: http://en.wikibooks.org/wiki/Blender_3D:_Blending_Into_Python/Cookbook#Point_inside_a_Mesh.

If the bounding box would suffice, you could just iterate through all vertices and store the extremes to get the bounding box, then check if the point lies inside.

(RickyBlender) #8

the one from ideasman i written in C not a python code
but would be interesting to see this in python code!

but you can find face intersect in geom tool

http://www.hybird.org/~guiea_7/scripts/geomtool.zip

also did a tst with last one but by changing location of cursor does not seems to give if inside or not
always same answer = 0 ?

anybody knows hwy it 's not working>?

salutations

(Atom) #9

I am trying out aothms code:

I have modified it slightly to add the includes. Here is what I have…


import bpy
import mathutils

def fetchIfObject (passedName= ""):
    try:
        result = bpy.data.objects[passedName]
    except:
        result = None
    return result

    
def pointInsideMesh(point,ob):
    axes = [ mathutils.Vector((1,0,0)) , mathutils.Vector((0,1,0)), mathutils.Vector((0,0,1))  ]
    outside = False
    for axis in axes:
        orig = 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

myPoint = fetchIfObject("Empty")
myMesh = fetchIfObject("Cube")
if myPoint != None:
    result = pointInsideMesh(myPoint.location,myMesh)
    print (result)
else:
    print ("myPoint does not exist.")

It seems to return a False if the Empty is inside or outside the Cube.

Do world matricies need to be taken into account?

(aothms) #10
def pointInsideMesh(point,ob):
    # 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

(Atom) #11

@aothms: Thank you, the revised function works!

(RickyBlender) #12

can someone port this to 2.5

might be usefull in futur !

Thanks and happy 2.5

(Atom) #13

It is 2.5 already.

Notice the import bpy, not import Blender at the top of the script. Also, objects do not have the ray_cast function in 2.49.

(RickyBlender) #14

there is a BPY in 2.29 if i remember well

can this work also with the location of the cursor for instance
as shown in example in link which is one way to do this

or you use any object location to determine if inside or not ?

how do you select your OB here ?

Thanks

(Atom) #15

Just look at my extension code up above.

myPoint = fetchIfObject("Empty")
myMesh = fetchIfObject("Cube")

You can use any object with a location. You don’t even have to use an object’s location, you can just pass any vector, I believe? Doesn’t the 3D cursor have location in 2.5?

result = pointInsideMesh(myPoint.location,myMesh)
(RickyBlender) #16

there was in mathutil a cursor location command
but it’s not there anymore!

but i have to look how to get cursor location

i have one command to re locate object at the cursor location
but not certain if i can get the XYZ of the cursor from that one
i’ll check that tomorrow

salutations

(aothms) #17

@Atom, glad it works now. The unrevised code must have worked in my project because all the meshes were already centered at the origin.
@RickyBlender

bpy.context.scene.cursor_location

should do the trick?

(Abidos) #18

In case of a 3D body with valid Euler’s formula (i.e. a closed one), checking a ray at just one direction is sufficient. :wink:

@ ALL - Im happy that you have already procs working fine for practical purposes. :spin: You should account though that these are NOT correct from a mathematical point of view… :eek: Firstly, if your object is snake-like with sine-like shape on X, you will need to check a lot of faces… Secondly, you’re limited to 10000 - I sayd this is OK for mathematical purposes. Another potential problem may be if the face that the ray is to intersect is really parallel to it, i.e. the ray lying in face’s geometrical plane. There may be division by 0 error of such… Finally, you’re iterating with a multiplication by 10000 and division by 0.00001 and it is well known from the IT theory (and practice) that doing such operations many times results in deviations of the vector (in our case), i.e. after some iterations your ray wont point the same direction as the starting one. This may be after 100-th or 1000-th iteration - depending on the Blender internal calcs (which are NOT known to be amongst the very precise ones) - sooo there is a need of correction as soon as the deviation is higher than a threshold established before-hand. In case of 2-3 to 10 intersections there is no such a need, I think… But I havent checked that :wink:

Regards,

(aothms) #19

Abidos, we’re not sending rockets to the moon here ;). Besides, I think the first-most concern with this implementation is not the iterative ray generation, but the fact that the ray intersection test is executed multiple times, needlessly checking all faces of the mesh again after each found intersection. While the implementation is suboptimal, but originates from the building blocks the api supplies (ray-triangle intersection has disappeared from the api, only ray-mesh remained, furthermore, usually rays are described by origin+direction instead of start+end, thus the need for a fixed-length ray), I believe the algorithm itself is the de facto way of doing these sorts of tests, but normally one would create one ray and test that with all faces just once.

(Abidos) #20

That’s what I am saying - your code’s working on meshes under several conditions! I.e. NOT on every mesh (unknown)…

Checking beyond 10000 is the least problem. You’re NOT checking if your body is closed… The cheapest way to do so is checking the Euler’s formula! If it say “OK”, then it is “OK”… If not - a whole bunch of problems may be in place.

Shown is the default cube, subdivided twice, and one internal face added:

http://www.mediafire.com/imgbnc.php/e60e5fd13d215b5424983fb6f01585566g.jpg

So for a point (0.25, 0.25, 0.25) which is obviously INSIDE, using the ray along (1,0,0) will give you the faulty result cause the ray will intersect 3 faces. While using the ray (0,1,0). for example, will give you the correct result!

Frankly, in such a situation I woulnd rely very much on THAT algorithm…

If Euler’s formula isnt TRUE, in addition to holes, you may expect overlapped faces, orphan verts and edges, etc. Which you also dont check as well…

In conclusion - again - your code is pretty good and working under some conditions to the mesh examined.

Regards,