Any ideas how to efficiently find the closest point on a surface for a given point in world coordinates?
What I mean by this is not the closest vertex but actually the closest point on a mesh, which could be somehwere between vertices.
So basically, a function that takes a mesh M and some arbitrary point P in space and returns the point on the surface of the mesh that has the shortest distance to P. Ideally, I would like both the world coordinates of that closest point as well as the triangle and the barycentric coordinates that correspond to this closest point.
Any ideas or pointers to algorithms would be appreciated!
Thanks
– MartinB
Hi Martin,
Check out this thread from a couple of days ago – I posted a demo scene with the code inside a Scale Scripted Controller – it finds the closest point on surface, then reads its UV and scales the object based on the color value of the diffuse map. You can use the closest point on surface approach found there, but please read the rest of the thread regarding speed issues as this is a brute force implementation.
If the surface is static, using RayMeshGridIntersect might be a good acceleration approach. Another approach would be to encode the whole mesh into a voxel grid yourself and compare the position of your point only with vertices/faces in adjacent voxels to reduce the number of intersectRay calls.
This isn’t exactly what you want, but it may get you started…
rayPosition = [x,y,z]
r = intersectray object (ray rayPosition [0,0,-1])
So this takes a position you define (your point), and shoots a ray from that point towards an object, and the ray returns the point of intersection in world space. That gets you part of the way there, the problem is that you need to define a direction to look in. So it doesn’t guarantee you the shortest distance, it just provides you the intersection point in a particular direction. But maybe the info will get you started, or who knows, maybe that will be enough info to handle what you’re trying to write. Good luck.
- Neil
Thanks Neil!
Unfortunately, the trick here is in which direction to shoot the ray. One could use the pivot point, or the center of mass, center of bounding box or the first vertex or other such heuristics, but any of these intersections could be arbitrarily far away from where I want to go, which really is the precise point on the mesh that has the shortest distance to my given point.
– MartinB
As I see it, the workflow would be:
1- find the closest vertex.
2- put the faces that share that vertex in an array.
3- use the normal of each face to shoot a ray from your point and see if it intersects with the face whose normal was used.
4- it’s eitheir the closest of the intersection points if there are several, THE intersection point if there’s only one, or the closest vertex if there is no intersection point.
Someone correct me if I’m wrong. :shrug:
Here I’ve done the first part (the easiest!):
refVert = [1,2,3]
minLength = amin(for v in $.verts collect length(refVert - v.pos))
for v in $.verts do
if length(refVert - v.pos) == minLength do
(
print v.index
print v.pos
)
Caprier, thanks a lot for the suggestion and code. First searching for the closest vertex and then checking it’s triangles is unfortunately not guaranteed to find the closest point. Imagine the query point sits almost in the center of a very large triangle. So the vertices of that triangle are very far away and would not be used, and some other vertex nearby could easily be the closest vertex but not be the closest point, and neither would any point on it’s triangles.
– MartinB
Hi Bobo,
Thanks very much, I will definitely have a look at this, and get back to you on that!
What I am eventually trying is to write some MAXScript that will create Attachment controllers for a set of existing objects such that they do not change their current position but are attached to the picked surface. And a modified way to create Attachment controllers in general, as right now, the function simply moves the attached object to Face #1. So, in a nutshell, I want “attach this object to that, but optionally keep the current position and/or rotation as an offset”
But general code to find the closest point on a TriMesh would be quite helpful in other cases, too. So this would be a nice exercise at computational geometry inside 3ds Max.
I have had several attempts at using that structure in the past as some sort of generalized octree for finding closest objects, but I believe that some of the non-ray intersecting functions are broken. It works fine for intersecting rays, but simply querying a point in space did not work when I last tried it. Maybe I just used it incorrectly, though?
– MartinB
Martin, thanks for stopping me going to far in a wrong direction. I see your point (an almost flat tetraedron, for example).
I was wondering if it was possible to use some light/render algorithm. Like the closest point from a light on an unsmoothed surface would be the brightest, right?
Interesting idea! One could even try to use Texture Baking for this…
But since surface brightness is also dependent on angle between surface and light source, this might also fail in certain cases; not sure.
I looked at Bobo’s other thread and it sure looks interesting, but it seems to fail in some cases, too. I found at least one situation where his scripted controller did not find the right point on the surface, although I am not sure why exactly.
– MartinB
I think I’m right here, slap me down if I’m not…
Bobo’s method does not find the closest point on a surface, generally. It finds the closest point A on any face of a surface to a point B where B is inside the prism created by projecting the face along its own normal.
Trivially, imagine a surface of a single triangular face in the XY plane (normal up Z), and a point above it, which in the Top View, is outside the face. No intersection will be found, although there is, obviously, a closest point.
A ‘rendering’ method would involve shooting some sort of spherical Z-depth map from the point? Wouldn’t that be very inefficient, and dependant on the resolution of the render? I’d be inclined to Bobo’s suggestion of making a quickly-searchable subdivision of the space enclosing the surface, if you have to test many points against it.
I though about the light approach because someone was telling me how fast the shading algorithms were compared to similar scripted ones. For the angle, if point, light and camera are all at the same position, maybe…?
Another way could be to use a growing sphere and some collision detection. Though I have no idea how to implement something like that, nor what tools are available.
About Bobo’s script, there are still a few points that are not clear to me. I need to work on it some more.
off topic: I’m actually following one of Bobo’s video tuts. The english is perfect and the accent is terrible. I love it! As for the content, it’s simply awesome. His crystal-clear explanations make me feel a lot smarter! Thanks Bobo !!!
LOL! English is historically speaking my 4th language (3rd foreign). I have been told my accent has more German in it than Bulgarian. While I don’t like the word “terrible” much, I must admit I have a very strong accent indeed.
Thus I prefer writing…
Guys, I might be wrong again (my geometry sucks) but if the ‘point’ is in none of the prisms projected by each face along their normals, shouldn’t the closest point on the surface in this case be the closest vertex?
The trouble (as illustrated in the other thread by Martin) is that if the angle between faces is very large, a point could fall between the prisms. With extreme curvatures, the brute force solution is subdividing the surface to smooth out the angles (introducing new faces with in-between normals that would catch the point where the coarse version would miss). Obviously, this leads to slower evaluation times…
The upcoming Krakatoa 1.1 features methods to cull particles by surface distance both in the PRT Loader and in a dedicated PFlow Operator. It uses a KdTree structure and finds the closest point to the surface really fast. We have exposed the KdTree-related functionality to MAXScript internally, but at this point it is not part of Krakatoa. No idea whether it will ever be.
Sorry for the word ‘terrible’, Bobo. English is not my natural language either, so I tend to get the nuances wrong sometimes. I meant ‘quite’ pronounced. But it’s perfectly understandable and not unpleasant at all.
About our topic, the actual script effectively returns the wrong value sometimes. The pic below is taken at frame 3. The intersection point returned by the scrip is at 115.79 units from the target while the vertex a little above is at 107.403 units.
I added the plane’s vertices infos (pos and distance) to the respective arrays and it returned either the closest vertex or the closest intersection point, apparently when it’s appropriate. But this addition probably slows down the process a little more.
On my slow machine (AMD Athlon 3200+), there is a slightly noticeable delay. Running the scrip on a model with heavy polycount might take a while.
There is also a problem in some cases when the model has a large hole, the ‘Point’ is somewhere near that hole and the face on the other side is near. The intersectRay() method returned undefined because that face on the other side of the model is facing away and reversing the ray’s direction didn’t change anything. So I got the closest vertex instead of the closest point on that face.
A vertex can be closer to the point than a point on a face. The reason is that the normal at the vertex is an average of the adjacent faces (as long as the surface is smooth), so it is exactly that missing normal that I was attempting to add by subdividing the surface more.
But we are going into extreme deformations here, the original script was written to find the closest point to relatively regular surfaces, mostly for mapping purposes.
EDIT: Oops, as mentioned further in this thread, the vertex is NOT closer according to the orthogonal rule imposed by the original posted when I wrote the code. The closest point has to be measured along a surface normal, assuming only face normals will be used (no surface curvature/smoothing taken into account). The vertex’ normal points somewhere else completely…