How to check if a point is inside a closed mesh?

[Anonymous]

Hi everyone,

Is there a way to determine if a given 3d point lies inside a closed convex mesh? Thank you!

[denisT.MaxDoctor]

the solution is very simple and straightforward ... if you cast a ray from this point in any direction and:
#1 ray doesn't intersect mesh faces - OUTSIDE
#2 ray intersects but the first hit face's normal is opposite to ray direction - OUTSIDE
#3 ray intersects and the first hit face's normal has the same direction of the ray - INSIDE

[denisT.MaxDoctor]

---

@denisT.MaxDoctor wrote:

the solution is very simple and straightforward ... if you cast a ray from this point in any direction and:
#1 ray doesn't intersect mesh faces - OUTSIDE
#2 ray intersects but the first hit face's normal is opposite to ray direction - OUTSIDE
#3 ray intersects and the first hit face's normal has the same direction of the ray - INSIDE

---

if the mesh is closed but not convex there is another rule...
(still cast a ray from the point to any direction):
#1 no hit - OUSIDE
#2 even number of hits - OUTSIDE
#3 odd number of hits - INSIDE

[miauuuu]

You can use the code in post 6 in this thread: https://forums.cgsociety.org/t/find-verts-inside-other-mesh/1456824/6

and following denisT advices you can build your tool.

[denisT.MaxDoctor]

---

@miauuuu wrote:

You can use the code in post 6 in this thread

---

today is 2021 ... let's do something smarter:

fn isPointInsideGeometry node pt = 
(
	rm = RayMeshGridIntersect() 
	rm.Initialize 10 
	rm.addnode node
	rm.buildGrid()

	numhits = rm.intersectRay pt z_axis on
	hitpoints = #() 
	for index = 1 to numhits do appendifunique hitpoints (rm.getHitPoint index)  
	
	res = mod hitpoints.count 2 == 1
	rm.free()
	res
)

fn arePointsInsideGeometry node pts = 
(
	rm = RayMeshGridIntersect() 
	rm.Initialize 10 
	rm.addnode node
	rm.buildGrid()

	res = for pt in pts collect
	(
		numhits = rm.intersectRay pt z_axis on
		hitpoints = #() 
		for index = 1 to numhits do appendifunique hitpoints (rm.getHitPoint index)  
		mod hitpoints.count 2 == 1
	)
	rm.free()
	res
)

🙂

[istan]

---

@denisT.MaxDoctor wrote:

---

---

if the mesh is closed but not convex there is another rule...
(still cast a ray from the point to any direction):
#1 no hit - OUSIDE
#2 even number of hits - OUTSIDE
#3 odd number of hits - INSIDE

---

As you wrote about "not convex". Concave objects won't work with a test ray in any direction..

[denisT.MaxDoctor]

---

@istan wrote:

As you wrote about "not convex". Concave objects won't work with a test ray in any direction..

---

why not? the odd / even solution works for any "closed" mesh (both convex and concave). it must be not a self-intersecting mesh, a single-element or its elements must not overlap.

[denisT.MaxDoctor]

---

@denisT.MaxDoctor wrote:

---

@istan wrote:

As you wrote about "not convex". Concave objects won't work with a test ray in any direction..

---

why not? the odd / even solution works for any "closed" mesh (both convex and concave). it must be not a self-intersecting mesh, a single-element or its elements must not overlap.

---

fn arePointsInsideGeometry node pts = 
(
	rm = RayMeshGridIntersect() 
	rm.Initialize 10 
	rm.addnode node
	rm.buildGrid()

	res = for pt in pts collect
	(
		numhits = rm.intersectRay pt z_axis on
		hitpoints = #() 
		for index = 1 to numhits do appendifunique hitpoints (rm.getHitPoint index)  
		mod hitpoints.count 2 == 1
	)
	rm.free()
	res
)

delete objects
gc()
	
t = torus_Knot radius:20 radius2:6 wirecolor:green
pp = for k=1 to 1000 collect 
(
	point pos:(random t.min t.max) size:5 wirecolor:brown
)
pts = for p in pp collect p.pos 
cc = arePointsInsideGeometry t pts
for k=1 to pp.count do pp[k].wirecolor = if cc[k] then red else gray  

[Anonymous]

Thank you all guys! I solved my problem by following the example:

3ds Max 2016 Help: RayMeshGridIntersect : ReferenceTarget (autodesk.com)

I needed it for a very basic application and that works well. 

@denisT.MaxDoctor I'll look at your script too, maybe I can optimize what I wrote. Thanks 🙂

[denisT.MaxDoctor]

---

@Anonymous wrote:

Thank you all guys! I solved my problem by following the example...

---

in that case, please show your solution

[MartinBeh]

Hey @denisT.MaxDoctor 

thanks for sharing, found this quite useful - just a short note that your code seems not to work for a teapot.

[denisT.MaxDoctor]

---

@MartinBeh wrote:

Hey @denisT.MaxDoctor 

thanks for sharing, found this quite useful - just a short note that your code seems not to work for a teapot.

---

A teapot geometry is not a "closed" mesh. As I remember the solution works for a "closed" mesh only. You can "cap" the teapot and try the solution again.

[MartinBeh]

I did try adding a Cap modifier but still getting some points outside the teapot reported as "inside", e.g. below the spout.

Have not tried to debug it yet, just wanted to let you know.

Teapot is special anyway...

[denisT.MaxDoctor]

try to increase the ray-to-mesh intersection grid size to 1000 and number segments for the teapot. It has to work with the example below:

fn arePointsInsideGeometry node pts = 
(
	rm = RayMeshGridIntersect() 
	rm.Initialize 1000 
	rm.addnode node
	rm.buildGrid()

	res = for pt in pts collect
	(
		numhits = rm.intersectRay pt z_axis on
		hitpoints = #() 
		for index = 1 to numhits do appendifunique hitpoints (rm.getHitPoint index)  
		hitpoints.count > 0 and (mod hitpoints.count 2 == 1)
	)
	rm.free()
	res
)

delete objects
gc()
	
t = teapot radius:20 segs:100 wirecolor:green
addmodifier t (cap_holes())
	
pp = for k=1 to 1000 collect 
(
	point pos:(random t.min t.max) size:2 wirecolor:gray
)
pts = for p in pp collect p.pos 
cc = arePointsInsideGeometry t pts
xp = for k=1 to pp.count collect 
(
	if cc[k] then 
	(
		pp[k].wirecolor = red
		dontCollect
	)
	else pp[k]
)
-- select xp

The algorithmic logic is correct, but the built-in RayMeshGridIntersect methods are probably buggy (not working correctly) for some values.

[MartinBeh]

---

@denisT.MaxDoctor wrote:

try to increase the ray-to-mesh intersection grid size to 1000 and number segments for the teapot.

---

Makes sense! If RayMeshGridIntersect does not work precisely, the rest cannot do a good job, either.

Unfortunately, adding a Cap_Holes modifier and increasing the grid size to 1000 still generates a few false positives. In fact, there is no difference between 10 and 1000 (aside from calculation times...).

FWIW: I am testing with code that generates the test points in a regular grid within the bounding box, not random points.

[denisT.MaxDoctor]

We can do it faster with a smaller grid but test all three directions. (or more than three, the rule is the same - odd number of intersections)

fn arePointsInsideGeometry node pts = 
(
	fn _odd x = (mod x 2 > 0) 
	
	rm = RayMeshGridIntersect() 
	rm.Initialize 100 
	rm.addnode node
	rm.buildGrid()

	res = for pt in pts collect
	(
		x = rm.intersectRay pt x_axis on
		y = rm.intersectRay pt y_axis on
		z = rm.intersectRay pt z_axis on
			
		_odd z and _odd y and _odd z   	
	)
	rm.free()
	res
)


delete objects
gc()
seed 100	
t = teapot radius:20 segs:10 wirecolor:green
	
pp = for k=1 to 1000 collect 
(
	point pos:(random t.min t.max) size:2 wirecolor:gray
)
pts = for p in pp collect p.pos 
cc = arePointsInsideGeometry t pts
xp = for k=1 to pp.count collect 
(
	if cc[k] then 
	(
		pp[k].wirecolor = red
		dontCollect
	)
	else pp[k]
)

[denisT.MaxDoctor]

there are mistakes anyway... well, add negative directions

[MartinBeh]

Adding a cap_holes() and also testing for negative directions still leaves some questionable points:

Here is a simple fail case:

arePointsInsideGeometry t #([3,13,24], [0,13,24])
#(true, true)

Not 100% certain though - maybe those points are exactly on the teapot surface...?

[denisT.MaxDoctor]

The main issue in your case appears to be algorithmic.

The "method of parity of intersections" only works for a single closed figure, regardless of whether it is convex or not.

In the classic case of the teapot, we are dealing with several elements, and they are not closed. If we apply the Cap modifier, we can close the shapes (elements), but since there are still multiple elements, this contradicts the algorithm's conditions. Therefore, to determine a point's position relative to the entire teapot (inside or outside) we must check for mutual intersections among all elements.

One possible solution could be to use a Boolean (Union) operation on all elements. However, this may be a computationally heavy operation in general.