Find shortest distance between point and a mesh?

[f97ao]

Is there a way to find the distance between a point and a seperate mesh without using a normal/direction?

I have the point3 position and a mesh. I would like to find the closest point on the mesh as a point3 value.

Cheers

I think you would have to look through all the points in the mesh and check each of them if they are the closest.
It's not gonna be that fast I'm afriad :)
/Andreas

[fabman]

Well, I know this won't work with non-convex meshes, but if it's a convex mesh, could you use the vector that goes from the point to the center of the object as direction ray and then use distance between the point in the surface and the first point?.
it's a quick and dirty method, I know. :)

[joconnell]

I think what andreas was saying was to loop through the mesh and get the position of each vert in the mesh then do a distance calculation between the point and each of the verts. If you save each of these test values into an array you can use amin(arrayname) to find out the smallest value so it'd return the shortest distance between the point and any of the verts in the mesh.

[HalfVector]

Something like this, I guess:

fn closestDistanceToObject pt obj = (
local msh = snapshotAsMesh obj

local closestDist = distance pt (getVert msh 1)

for i = 2 to msh.numVerts do (
local dist = distance pt (getVert msh i)
if dist < closestDist do closestDist = dist
)

delete msh

return closestDist
)

[Bobo]

Something like this, I guess:

fn closestDistanceToObject pt obj = (
local msh = snapshotAsMesh obj

local closestDist = distance pt (getVert msh 1)

for i = 2 to msh.numVerts do (
local dist = distance pt (getVert msh i)
if dist < closestDist do closestDist = dist
)

delete msh

return closestDist
)


In addition, record the index of the vertex that returned the closest distance. Then get all faces shared by that vertex and project the point onto the surface of each face along the negative face normal using IntersectRay(). Chances are the closest point on the surface lies inside one of these faces and not on the vertex...

[HalfVector]

In addition, record the index of the vertex that returned the closest distance. Then get all faces shared by that vertex and project the point onto the surface of each face along the negative face normal using IntersectRay(). Chances are the closest point on the surface lies inside one of these faces and not on the vertex...
That's right!.

fn closestDistanceToObject pt obj = (
local msh = snapshotAsMesh obj

local closestVert = 1
local closestDist = distance pt (getVert msh 1)

for i = 2 to msh.numVerts do (
local dist = distance pt (getVert msh i)
if dist < closestDist do (
closestDist = dist
closestVert = i
)
)

local faces = meshOp.getFacesUsingVert msh #{closestVert}

if faces != undefined do (
for f in faces do (
local rayDir = -(getFaceNormal msh f)
local intInfo = intersectRay obj (Ray pt rayDir)

if intInfo != undefined do (
local dist = distance pt intInfo.pos
if dist < closestDist do
closestDist = dist
)
)
)

delete msh

return closestDist
)

I think it's right... :hmm:

[HalfVector]

By the way. Exists an obvious optimization. We can avoid the square root used by the distance function by comparing squared distances.

-- Returns the squared distance between two points
fn distanceSq pt1 pt2 = (
return ( (pt2.x - pt1.x)^2 + (pt2.y - pt1.y)^2 + (pt2.z - pt1.z)^2 )
)

-- Returns the closest distance to an object
fn closestDistanceToObject pt obj = (
local msh = snapshotAsMesh obj

local closestVert = 1
local closestDistSq = distanceSq pt (getVert msh 1)

for i = 2 to msh.numVerts do (
local distSq = distanceSq pt (getVert msh i)
if distSq < closestDistSq do (
closestDistSq = distSq
closestVert = i
)
)

local faces = meshOp.getFacesUsingVert msh #{closestVert}

if faces != undefined do (
for f in faces do (
local rayDir = -(getFaceNormal msh f)
local intInfo = intersectRay obj (Ray pt rayDir)

if intInfo != undefined do (
local distSq = distanceSq pt intInfo.pos
if distSq < closestDistSq do
closestDistSq = distSq
)
)
)

delete msh

return (sqrt closestDistSq)
)

Obviously, at the end we return the real distance.

Greets.

[Gibbz]

This is basically what im doing in my script currently(tho unoptimised).

Problem is if u use the inverse normal of the faces to case a ray from my original position it does not hit the target object due to the shape im working with.

Eg.



| |
| |
| |____ <-target mesh
\.______ <- first vert here is my example(marked as a dot)



Ok now if we use the fist vert ive listed in the example. The normals from the target mesh are down, and left(so we invert these).
Problem here is if we cast a ray from the vert using the face normals from the low poly target mesh, we get not "hit".

Any ideas on this problem?

Edit: im trying to get the target position on the tragetmesh.(ie where the shortest distance meets the other mesh). So i need either the position and the face, or a direction so I can use a raycast to test for the face/position.

[Bobo]

This is basically what im doing in my script currently(tho unoptimised).

Problem is if u use the inverse normal of the faces to case a ray from my original position it does not hit the target object due to the shape im working with.

Eg.



| |
| |
| |____ <-target mesh
\.______ <- first vert here is my example(marked as a dot)



Ok now if we use the fist vert ive listed in the example. The normals from the target mesh are down, and left(so we invert these).
Problem here is if we cast a ray from the vert using the face normals from the low poly target mesh, we get not "hit".

Any ideas on this problem?

Edit: im trying to get the target position on the tragetmesh.(ie where the shortest distance meets the other mesh). So i need either the position and the face, or a direction so I can use a raycast to test for the face/position.

I don't see the problem. The ray casting we added is IN ADDITION to measuring the distance to the vertices. If no ray hits, the closest distance to a vertex IS the closest distance to the mesh. If the point happens to be closer to a surface than to a vertex, then we overrule the closest vertex distance.
But in your example the intersectRay() would return undefined because your point IS closer to the corner vertex than to any of the faces, and we ignore the intersection attempts...

[Gibbz]

Ok thats fair. What if the example both of those were extruded towards the camera, but my point had no matching point on the low poly mesh, the closest point would then be on the line of the low poly mesh, not on the actual vertex itself....Correct?

[exerion]

Hey guys :)

I think I'm having similar problems with this as Gibbz. I'm relatively new to maxscript but I'm pretty sure I understand everything that is going on in this function.

I'm rotating helper 1 around a cube and positioning the helper 2 at the closest point on the surface. As helper 1 passes over an edge of the cube intersectRay returns undefined so it places helper 2 at closest vertex which isn't the closest point on the surface. This causes helper 2 to jump all over the place.

Is their a better way? Do I need to also some how check the closest point on an edge?

[focomoso]

Chances are the closest point on the surface lies inside one of these faces and not on the vertex...
Not necessarily. The further away the point is from the mesh, the more likely a vert will be closest. Also, the rougher the surface, the more likely a vert is closest. Depending on how accurate this distance measurement needs to be, you might just want to skip the face detection altogether.

[exerion]

I just thought I would post an image to illustrate my problem. I want to find the point on the cube that is closest to the white helper. The yellow helper is the position the above solution finds. Obviously the blue end of the tape helper is where the yellow helper should be.

http://www.users.on.net/%7Eexerion/_/CGTalk/point_to_surface_v01.gif

[PEN]

How about taking the three closest verts and use a weighted average of those? I can see one problem with it if a face is folded between two of the verts. You could then fire a ray at that point and see if it is closer then one of the verts.

[PEN]

I hate it when you guys post stuff like this as it is far more interesting then what I'm working on and I just waisted a half hour playing with it.

[d3coy]

Hi guys,

I had this problem when figuring out particle detections on mesh objects so I could draw trails from the particles on the UV's of the mesh. I ended up writing a routine that would shoot a sphere of rays out from the point, and out of all the successful collisions with the object, take the intersection that had the shortest hit distance. This works but it is not fast. You can shoot more and more rays spherically from your point to achieve a finer approximation of the closest part of the mesh, or you could shoot more rays radially from a successful intersection to refine the point. This is all very brute force and if you absolutely cannot use intersections and must find the point purely without rays, I apologize. This is the method I used though, after being disatisfied with some of the other methods previously mentioned.

[oatz]

I hate it when you guys post stuff like this as it is far more interesting then what I'm working on and I just waisted a half hour playing with it.

Quoted for agreement.

Khye

[exerion]

Thanks for your input guys. I'll give the brute force approach a go :)

[CGTalk Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.