Hello. I have a little problem understanding of how RayMeshGridIntersect works.
Here is a very basic example:
Mesh object (blue) and a point (green) almost touching its surface. I want to find polygon(s) closest to that point. For this I use intersectSphere method (also tried intersectBox with same results)
Now the weird part. While search radius is < 5, it doesn’t find any intersecting polys. Even if its 4.99999. But at radius = 5 it actually finds something. I tried to visualize search radius with sphere (pink) and obviously 4.99999 is big enough to intersect with some faces. Even 1 is enough. So, either this is some strange bug, or I lack fundamental understanding of how it works.
Here is code:
targetMesh = $Sphere001
p = $Point001.pos
rayMeshGridInt = RayMeshGridIntersect()
rayMeshGridInt.initialize 10
rayMeshGridInt.addNode targetMesh
rayMeshGridInt.buildGrid()
s = 4.9999
-- s = 5.0
is = rayMeshGridInt.intersectSphere p s
faceIndex = rayMeshGridInt.getHitFace 1
rayMeshGridInt.free()
Also I’ve attached this scene (2015).
Thanks.
try to make smaller grid size (you use 10, make it 1)
Hi!
Since rayMeshGridIntersect uses a voxel grid to find closest polys it cant be so precise, just if you increase the density of the grid. I don’t know if it uses an octal tree or BSP tree, or just a simple voxel grid to define final result, but if you are interested, google these words.
Isn’t the RayMeshIntersect source code distributed with the SDK?
Guys, thanks for your replies. Unfortunately, playing with grid size changed nothing. I tried setting it from 1 to 1000, and results are same.
Some internal bug or unhandled situation?
Check these two examples out. They are both the same, except that in the first one the sphere has a much larger resolution (5040 faces) and in the second example it has only 440 faces. Even though, the sphere intersection fails with the larger resolution and works with the lower one.
FAILS:
(
delete objects
pos = [39,-62,68]
rad = 4.0
sph1 = sphere radius:100 segments:72 wirecolor:green isselected:on
sph2 = sphere radius:rad segments:32 pos:pos wirecolor:red
rayMeshGridInt = RayMeshGridIntersect()
rayMeshGridInt.initialize 10
rayMeshGridInt.addNode sph1
rayMeshGridInt.buildGrid()
rayMeshGridInt.intersectSphere pos rad
)
WORKS:
(
delete objects
pos = [39,-62,68]
rad = 4.0
sph1 = sphere radius:100 segments:22 wirecolor:green isselected:on
sph2 = sphere radius:rad segments:32 pos:pos wirecolor:red
rayMeshGridInt = RayMeshGridIntersect()
rayMeshGridInt.initialize 10
rayMeshGridInt.addNode sph1
rayMeshGridInt.buildGrid()
rayMeshGridInt.intersectSphere pos rad
)
i met this issue too. but intersectBox usually works
Well, that’s sad. Can you recommend another way of doing that? Basically, I need to find closest polygon to arbitrary point in space, along with its normal at that point.
You could use MeshProjIntersect.
(
gc()
delete objects
max create mode
obj = converttomesh (teapot radius:30 segs:16 wirecolor:green isselected:on)
meshIntersect = MeshProjIntersect()
meshIntersect.SetNode obj
meshIntersect.Build()
faces = #{}
with undo off with redraw off
(
for j = 1 to 100 do
(
-- Get a random position
pos = obj.center + ((normalize (random -[1,1,1] [1,1,1])) * 35)
-- We have a closest face, build preview objects
if (meshIntersect.ClosestFace pos doubleSided:true) do
(
hFace = (meshIntersect.GetHitFace()) + 1 -- Closest Face (0 based index)
hPos = meshIntersect.GetHitPos() -- Hit position
hDist = meshIntersect.GetHitDist() -- Hit distance
hNormal = normalize (pos-hPos) -- Normal to Hit pos
sphere radius:0.5 segments:8 pos:pos wirecolor:red
cylinder radius:0.05 sides:3 height:hDist pos:hPos dir:hNormal wirecolor:yellow
faces[hFace] = true
)
)
)
obj.selectedfaces = faces
meshIntersect.Free()
max modify mode
subobjectlevel = 3
)
using my steps shown above and the found algorithm i’ve written a c++ sdk function: nearestMeshPoint, which finds closest point on the mesh to a specified point in the space.
it’s pretty fast. just as about 50 ms for 300K faces mesh.
now it’s interesting to know how can i use it, and why can it be helpful ?
Is it an O(N) algorithm? How long does it take for 100 random points on the same mesh?
#1 project a point to triangle plane
#2 check if the projection point inside triangle (you can use bary coordinates for it)
#3 if the projection point inside triangle the distance between origin point and projection is a shortest
#4 if the projection point outside triangle
#4.1 project projection point on every edge
#4.2 check if edge projection point inside edge
#4.3 if inside it’s the shortest distance to edge
#4.4 if outside check a distance to both edge side points
find the shortest – it will be a distance to triangle
do it for all faces and find the closest one.
here is a pseudo code which works (i’ve tested it)
http://www.gamedev.net/topic/516608-finding-closest-point-on-tri-to-point/