[Closed] Strange behavior of RayMeshGridIntersect

do I use any K-d Tree or Grid algorithms to acceleration? No. I just search all faces for every point to find the closest.

so for N points the search process will be ~N times slower then for a single point. If you have any idea about ‘smarter’ search algorithm, it will be welcome.

but I still have no idea idea about this task any useful utilization.

no. i don’t cache anything. i’m simply using only Math. (point-to-plane, point-to-segment, bary-coords).
but i pass a mesh pointer only ones to the function, and sdk gives very fast access to face and vert mesh data.

the only way to speeding it up i see now is to discard all not process faces if their point-to-projection distance already far then previously found. for an average case it might give ~3-4 times acceleration. but anyway i have to find projection point for every face

technically we can make k-d tree.

lets say we will pack faces using center of circumscribed circle for every face and maximum available radius. so for situation where the mesh has many compatibly equal faces the k-d tree gives very big performance improvement.

Sorry, I measured MeshProjIntersect wrong.
It seems it does use an O(N) algorithm after the initial setup. Even though, it is pretty fast.

It might use some space partitioning to speed it up.

Using the following test code I get large differences using pos=[0,0,0] and pos=[0,-1000,10000]

(
	gc()
	delete objects

	obj = converttomesh (teapot radius:30 segs:34 wirecolor:green isselected:on)
	addmodifier obj (turbosmooth())
		
	pos = [0,0,0]
-- 	pos = [0,-1000,10000]

	st0 = timestamp(); sh0 = heapfree
	
	meshIntersect = MeshProjIntersect()
	meshIntersect.SetNode obj
	meshIntersect.Build()

	format "build: %ms faces:% ram:%

" (timestamp()-st0) obj.numfaces (sh0-heapfree)

	st = timestamp(); sh = heapfree
	meshIntersect.ClosestFace pos doubleSided:true
	format "	1: %ms	%ms	ram:%
" (timestamp()-st) (timestamp()-st0) (sh-heapfree)
	
	st = timestamp(); sh = heapfree
	for j = 1 to 10 do meshIntersect.ClosestFace pos doubleSided:true
	format "   10: %ms	%ms	ram:%
" (timestamp()-st) (timestamp()-st0) (sh-heapfree)

	st = timestamp(); sh = heapfree
	for j = 1 to 100 do meshIntersect.ClosestFace pos doubleSided:true
	format "  100: %ms	%ms	ram:%
" (timestamp()-st) (timestamp()-st0) (sh-heapfree)

	st = timestamp(); sh = heapfree
	for j = 1 to 1000 do meshIntersect.ClosestFace pos doubleSided:true
	format " 1000: %ms	%ms	ram:%
" (timestamp()-st) (timestamp()-st0) (sh-heapfree)

	st = timestamp(); sh = heapfree
	for j = 1 to 10000 do meshIntersect.ClosestFace pos doubleSided:true
	format "10000: %ms	%ms	ram:%
" (timestamp()-st) (timestamp()-st0) (sh-heapfree)
	
	meshIntersect.Free()
	

-----------------------------------------	
-- 	pos = pos = [0,0,0]
-- 	build: 238ms faces:295392 ram:520L

-- 		1:   0ms	239ms	ram:216L
-- 	   10:   0ms	240ms	ram:128L
-- 	  100:   5ms	246ms	ram:128L
-- 	 1000:  57ms	304ms	ram:128L
-- 	10000: 570ms	875ms	ram:128L
-----------------------------------------

-----------------------------------------	
-- 	pos = [0,-1000,10000]	
-- 	build: 247ms faces:295392 ram:520L

-- 		1:	1ms	250ms	ram:216L
-- 	   10:	8ms	258ms	ram:128L
-- 	  100:   77ms	336ms	ram:128L
-- 	 1000:  726ms	1063ms	ram:128L
-- 	10000: 7222ms	8286ms	ram:128L
-----------------------------------------	
)

all is fast and already implemented in mxs. no needs to reinvent the wheel

it seems like the option dir doesn’t work for ClosestFace and IntersectRay does’n really work

(
	gc()
	delete objects

	global s = converttomesh (teapot name:#s radius:30 segs:34 wirecolor:green isselected:off)
	addmodifier s (turbosmooth())
		
	pos = [0,0,50]
	global p = point name:#p pos:pos wirecolor:green isselected:on
	global t = point name:#t wirecolor:yellow

	global mi = MeshProjIntersect()
	mi.SetNode s
	mi.Build()

	global hnd = when transform $p change do
	(
		mi.ClosestFace $p.pos dir:-z_axis doubleSided:on
		try($t.pos = mi.GetHitPos()) catch() 	
		--mi.IntersectRay $p.pos -z_axis doubleSided:on
		--try($t.pos = mi.GetHitPos()) catch()  -- CRASH inside	
	)
)
/*
mi.Free()
deleteChangeHandler hnd
*/

also i have ** system exception ** on Build() for some meshes i tried. MeshProjIntersect looks not trustworthy in general case

Yes, there are two warnings in the help file:

WARNING! – ClosestFace()
Currently, you have to call the IntersectRay() method AT LEAST ONCE before calling the ClosestFace() method – some internal structures required for closest face calculations are only initialized when performing intersections!
The results from the IntersectRay() call should not be trusted though. See warning further on this page.

WARNING! – IntersectRay()
This method is currently considered broken and should not be used to perform actuall intersections. Under some circumstances it can return incorrect results.

but there is no warning that ClosestFace doesn’t support dir

Honestly, I am not sure how the <dir> argument should work. But I see different results if you change it.

In the following example, using –z_axis or z_axis gives different results,a s well as if you use any other direction.

When I use –z_axis and move the point around the box in front view, the position is never detected inside the top triangles. If the dir is z_axis the bottom faces seems to be avoided.

Unfortunately there is no much documentation about this, nor examples I could find.

(
gc()
delete objects

try (mi.Free()) catch()
try (deleteChangeHandler hnd) catch()

global s = converttomesh (box name:#s wirecolor:green)

pos = [0,0,50]
global p = point name:#p pos:pos wirecolor:green isselected:on
global t = point name:#t wirecolor:yellow

global mi = MeshProjIntersect()
mi.SetNode s
mi.Build()

global hnd = when transform $p change do
(
	if (mi.ClosestFace $p.pos dir:-z_axis doubleSided:off) do $t.pos = mi.GetHitPos()
)
)

anyway. do you have any idea where closest face can be used? (projection or ray-face intersection are both useful for sure)