Determine if a Point is Inside a Mesh #28173

New Issue

Andrew Hale · 2011-08-07T14:48:15+02:00

Andrew Hale commented

2011-08-07 14:48:15 +02:00

%%%This patch adds the functionality to determine if a point lies inside a given mesh. It makes the assumption the mesh has normals calculated "outside" and that the point is in object space. Clearly inside/outside only makes sense if the mesh is closed, no check is made of this and it will still return a result if the mesh is open.

The code determines which side of the nearest face the given point lies on by comparing the displacement from the nearest point to the normal at the nearest point. If this is negative, then the point lies "behind" the face and is therefore inside the mesh if the above assumption is made. Hence, if the mesh is open, and the point in question lies behind the nearest face, it will still return true.%%%

%%%This patch adds the functionality to determine if a point lies inside a given mesh. It makes the assumption the mesh has normals calculated "outside" and that the point is in object space. Clearly inside/outside only makes sense if the mesh is closed, no check is made of this and it will still return a result if the mesh is open. The code determines which side of the nearest face the given point lies on by comparing the displacement from the nearest point to the normal at the nearest point. If this is negative, then the point lies "behind" the face and is therefore inside the mesh if the above assumption is made. Hence, if the mesh is open, and the point in question lies behind the nearest face, it will still return true.%%%

Andrew Hale commented

2011-08-07 14:48:15 +02:00

Changed status to: 'Open'

Andrew Hale commented

2011-09-01 06:58:36 +02:00

%%%Updated to r39834

This new patch fixes a problem which may occur due to precision errors and only finding the closest point on the meshes faces. The new method works as follows, the closest vertex on the mesh is found, its position and normal are stored. The distance to the nearest point is then decreased by 0.000001f to account for precision errors and the test is run again using the mesh edges this time. This process is repeated from edges to faces. By ensuring that the nearest subsequent point is at least a precision increment closer we can account for any errors that enter the calculations.

Cheers,
Andrew%%%

%%%Updated to r39834 This new patch fixes a problem which may occur due to precision errors and only finding the closest point on the meshes faces. The new method works as follows, the closest vertex on the mesh is found, its position and normal are stored. The distance to the nearest point is then decreased by 0.000001f to account for precision errors and the test is run again using the mesh edges this time. This process is repeated from edges to faces. By ensuring that the nearest subsequent point is at least a precision increment closer we can account for any errors that enter the calculations. Cheers, Andrew%%%

Andrew Hale commented

2011-09-01 07:00:46 +02:00

%%%Attached the file.%%%

Peter K.H. Gragert commented

2011-09-02 10:27:05 +02:00

%%%Hi Truman,

I tested like this with c = default-cube : for i in range(10): c.point_inside_mesh(Vector((0,0, 1.5 - i/10)))

> False * 6 True * 4

Looks good ;-)
BUT if I move the cube out ot fthe way nothing changes.
Suggestion: a next parameter to use world coordinates and not the local ones?

    Peter%%%

%%%Hi Truman, I tested like this with c = default-cube : for i in range(10): c.point_inside_mesh(Vector((0,0, 1.5 - i/10))) ## > False * 6 True * 4 Looks good ;-) BUT if I move the cube out ot fthe way nothing changes. Suggestion: a next parameter to use world coordinates and not the local ones? ``` Peter%%%

Campbell Barton commented

2015-03-25 16:33:07 +01:00

Changed status from 'Open' to: 'Archived'

Campbell Barton closed this issue

2015-03-25 16:33:07 +01:00

Campbell Barton self-assigned this 2015-03-25 16:33:07 +01:00

Campbell Barton commented

2015-03-25 16:33:07 +01:00

While this patch is reasonable. Lukas is looking into having a Python KD-Tree module,

I'd rather expose more functionality though this. So you would get a KD-Tree from a mesh, then perform queries on it.

See: D133, archiving

While this patch is reasonable. Lukas is looking into having a Python KD-Tree module, I'd rather expose more functionality though this. So you would get a KD-Tree from a mesh, then perform queries on it. See: [D133](https://archive.blender.org/developer/D133), archiving

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Determine if a Point is Inside a Mesh #28173

> False * 6 True * 4