PDA

View Full Version : Closest point on surface?


martinB
01-25-2008, 11:56 PM
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

soulburn3d
01-26-2008, 12:28 AM
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

Caprier
01-26-2008, 02:57 AM
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
)

Bobo
01-26-2008, 06:15 AM
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 (http://forums.cgsociety.org/showthread.php?f=6&t=586328) - 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.

martinB
01-26-2008, 09:45 AM
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

martinB
01-26-2008, 09:50 AM
As I see it, the workflow would be:
1- find the closest vertex.
[/CODE]

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

martinB
01-26-2008, 10:08 AM
Hi Bobo,

Hi Martin,
Check out this thread from a couple of days ago (http://forums.cgsociety.org/showthread.php?f=6&t=586328) - 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.


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.


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.

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

Caprier
01-26-2008, 11:24 AM
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?

martinB
01-26-2008, 03:48 PM
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

drdubosc
01-26-2008, 05:07 PM
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.

Caprier
01-26-2008, 05:07 PM
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 !!!

Caprier
01-26-2008, 05:36 PM
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?

Bobo
01-26-2008, 07:24 PM
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.

Bobo
01-26-2008, 07:27 PM
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... :)

Caprier
01-26-2008, 08:17 PM
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.

http://img508.imageshack.us/img508/9418/shinthf0.jpg

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.

Bobo
01-26-2008, 08:39 PM
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...

Caprier
01-26-2008, 09:04 PM
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.



Well, I'm aware of that. But I wouldn't miss a chance to learn from you, hehe.

martinB
01-26-2008, 11:10 PM
Thanks a lot for your interest, guys!

Maybe we first can ignore the "efficient" bit and settle on an algorithm that is guaranteed to find the closest point, even for tricky surfaces?

What would be the theoretical way to solve this?

-- MartinB

Bobo
01-27-2008, 12:06 AM
Thanks a lot for your interest, guys!

Maybe we first can ignore the "efficient" bit and settle on an algorithm that is guaranteed to find the closest point, even for tricky surfaces?

What would be the theoretical way to solve this?

-- MartinB


The original condition for my code was "find the point whose ORTHOGONAL projection on the surface is closest". Under this condition, my code works flawlessly. The closest vertex mentioned above is NOT measured orthogonal from our point. There can be many points that are closer to our point but whose normal does not hit our point, including the vertices.

If these points had to be taken into account, we would have to evaluate EVERY normal based on vertex normals, which is out of the question in this case. My use of the TurboSmooth brought the surface closer to the ideal isosurface (while remaining an approximation) and that's why it fixed the "problem".

But if the curvature of the surface has to be taken into account, it is a completely different situation that requires a different approach.

Bobo
01-27-2008, 12:27 AM
But if the curvature of the surface has to be taken into account, it is a completely different situation that requires a different approach.

Ok, it was mentioned previously in this thread that the point would have to be inside the prism defined by the face and its normal. If we expand this notion to being in the volume defined by the face and its VERTEX NORMALS, then we have covered the whole volume around the surface that would include our point (similar to how the shell modifier pushes the surface along the normals). So we take the triangle as the base of the volume and mathematically "extrude" each vertex along its normal so that the second base (another triangle with a different area unless the vertices use the face norma = no smoothing) passes through our point. Now we can look for the barycentric coordinates of our point within this projected face and calculate the averaged normal that is the surface normal for that point. Then project back onto the surface along this interpolated normal and we should have the point on the CURVED surface approximated by the mesh. Unless I am mistaken...

Caprier
01-27-2008, 08:12 AM
There can be many points that are closer to our point but whose normal does not hit our point, including the vertices.

Bobo, if I understand you correctly, then I disagree with you.
I think either the closest point is the orthogonal projection of 'The Point' on a face or one of the vertices. I mean that if it's not one of the vertices, then it's on a face and in this case the closest point is always the orthogonal projection. Looking at it in 2D with a broken line makes it easier to picture.

The fact that 'The Point' can be orthogonally projected on one or several faces (e.g. it is in the orthogonally extruded prism of one or several faces) doesn't guarantee that the projected point is the closest. In the case of a concave surface, 'The Point' could be in the prism of a face in the hollow and still be closer to some vertices.

As I see it, without regard for the speed, the script should compute the distance and position of intersection points along normals if they exist and store the pos and dist in arrays. Then add the pos and dist of each vertex in the same arrays, no matter if they're empty or not after the first part. Then look for the shortest distance, which can bring several equidistant points in some special cases.

Again, the only situation in which it doesn't work is if there is a hole in the surface and 'The Point' is closer to a face on the other side (facing away) than to a point on the surface on this side of the model. And of course, if the point is inside the object, it doesn't work either.
The only way around I can think of would be to copy the surface and flip the normals, which would simply double the time to compute. Unless there is a way to make the intersectRay() and intersectRayEx() methods work when the normal is facing the other way.

martinB
01-27-2008, 10:42 AM
What do you think of this:

Input: Mesh M and query point Q
Output: Point P on M with minimal distance PQ

Pseudocode

0: mindist = MAXFLOAT; closestPoint=undefined
1: for each face F in the mesh M do (
2: P := orthogonal projection of Q onto the plane that contains F
3: If P is outside of F, then P := closest point on F to P
4: d := distance between P and Q
5: if d < mindist then ( mindist := d; closestPoint := P )
6: )
7: return closestPoint and mindist
Would that work?

I do not know yet how to do step #3 but since we are effectively in 2D (on the plane of the face) it should not be hard. Maybe there is a trick with barycentric coordinates?

Also it is unclear to me whether there is an opportunity to optimize/use some acceleration structure.

Any comments?
-- MartinB

Bobo
01-27-2008, 04:47 PM
Bobo, if I understand you correctly, then I disagree with you.
I think either the closest point is the orthogonal projection of 'The Point' on a face or one of the vertices.

I am not goint to argue about it. I was asked to write a controller by a user here (on another thread) and he explicitly wanted the closest point ORTHOGONAL to the surface, not to a vertex. So in the case of a mesh with few faces with large angles between them and very few possible normals, the code would simply miss the surface as you noticed.

I did not come up with the condition for orthogonality, the original requester did, so I implemented that.

If you DO want the vertices to be considered the closest point, adding that is trivial and you are free to do so. I am just explaining why I did not take them into account - I was not supposed to! :)

This thread is about a GENERAL alogithm though, so you are probably right in that context. But I was right in the context of the other thread.

PEACE.

Caprier
01-27-2008, 11:54 PM
@Bobo: I apologize. It seems it came out wrong again. I didn't mean to criticize your script or anything. I'm very far from having the expertise to do that. I didn't know my words had such a strong meaning. Please don't let what I said stop your from helping someone else.
And I was wrong anyway, I missed some other possibilities.

@Martin: in your code, it's the third point that seems to be hard to figure correctly. So I asked a friend who teaches maths (to kids, but still). He changed the problem to something simpler: finding the closest point on a triangular surface (our faces, including vertices and edges) from a point in 3D space.

First, if the orthogonally projected point is in the triangle, that's the closest.
This is the part done by the intersectRayEx() method in Bobo's script.

Second, if the projection misses the triangle, then try an orthogonal projection on each of the three edges.
This is the part I missed. I don't know if there is a method in MXS to do that. The implementation he explained to me uses trigonometry but there might be some shortcuts with the matrices.

Third, if the second projection misses the edges, then the closest point is one of the three points defining the triangle (our vertices).
This part is the easiest.

The guy knows nothing about programming or 3D modeling. When I told him how 3d models had their surface made of triangles, his opinion was that there were too many possible configurations for the surface and that the best way would be to do the above for each face, then pick the best result (or results if some points are equidistant).

The second part - the orthogonal projection on an edge - is probably the one that would slow down the process the most.
I'll ask him the next time I see him - that would be wednesday - if there is a general method to find the closest point in a triangle ABC from a point P, no matter the projections. This might be much faster than going through three different processes.

What do you think?

drdubosc
01-28-2008, 02:03 AM
He changed the problem to something simpler: finding the closest point on a triangular surface (our faces, including vertices and edges) from a point in 3D space.

First, if the orthogonally projected point is in the triangle, that's the closest.
This is the part done by the intersectRayEx() method in Bobo's script.

Second, if the projection misses the triangle, then try an orthogonal projection on each of the three edges.
This is the part I missed. I don't know if there is a method in MXS to do that. The implementation he explained to me uses trigonometry but there might be some shortcuts with the matrices.

Third, if the second projection misses the edges, then the closest point is one of the three points defining the triangle (our vertices).
This part is the easiest.




The most-often-described method is pretty much as you quote here, but it starts by projecting the point orthogonally onto the (unbounded) plane defined by the triangle, and then testing the projected point against the extended edges of the triangle, in 2D, in the way you describe. Point>plane and Point>line are both in the sticky at the top of this forum.

These are pretty expensive operations, though, so you would ideally need to cull most of the triangles first, more cheaply, by using something like an octree division of the space enclosing the surface.

Alex Morris
01-28-2008, 11:12 AM
getting back to a render based solution is there any mileage in the near/far falloff map or even a z-depth pass to reduce the search parameters before raycasting?

martinB
01-28-2008, 10:53 PM
Second, if the projection misses the triangle, then try an orthogonal projection on each of the three edges. This is the part I missed. I don't know if there is a method in MXS to do that. The implementation he explained to me uses trigonometry but there might be some shortcuts with the matrices.

I know how to project a point onto a line, but how do I test whether that point is on the edge of the triangle?

The second part - the orthogonal projection on an edge - is probably the one that would slow down the process the most.

Interesting that you say that. I would expect a full ray-mesh intersection to be slower.

I'll ask him the next time I see him - that would be wednesday - if there is a general method to find the closest point in a triangle ABC from a point P, no matter the projections. This might be much faster than going through three different processes.
What do you think?

Sounds fairly good to me (and quite similar to what I suggested). I still wonder how I could project a point on a plane onto a triangle on the same plane without testing all the different possibilities explicitly. The idea would be to compute barycentric coordinates for that point and then somehow clamp these to the area of the triangle itself (0 <= barycentric coordinate <= 1) but I have not found a way to do that yet.

-- MartinB

Caprier
01-29-2008, 12:09 AM
Hi Martin.

I'm actually trying to figure how to test the possibility of an orthogonal projection on a face before any calculation of the projected point, by only using distances (or better, squared distances, to avoid square roots).
The idea is that there should be a lot more faces on which the orthogonal projection is not possible than the other way around.

Testing for an edge is simple. Two verts: A and B, a point somewhere: P.
If abs(PA*PA - PB*PB) > AB*AB, then the orthogonal projection misses the edge [AB]. This is derived from the pythagorean theorem. (Correct me if I'm wrong, it's getting late here.)
I'm trying to find something similar with a face instead of an edge.

Using squared distances calculated with the XYZ coordinates should be faster, as the length and distance methods calculate the square root. On the other hand, accessing the coordinates with the .pos property through MAXScript might take more time, while the dist and length methods might have some faster 'internal' access. I don't know.
This needs to be tested.

What drdubosc said about projecting P on the plane (ABC) is a very good point. I don't know if it's faster to do it first or later. Quite basically, I'm counting additions, multiplications and variable accesses in the formulas. I'll make some tests when I'm back home (I don't have max on this computer).

drdubosc
01-29-2008, 05:16 AM
Take a look at
http://www.blackpawn.com/texts/pointinpoly/default.html
the barycentric method. Even though it's only concerned with finding if a point is inside a triangle, it's easily extended to the 6 other zones outside it:

u<0 & v<0, closest to A,
u<0 & v<1, on AB,
u<0 & v>1, closest to B,
u<1 & v<0, on AC,
u>1 & v<0, closest to C,
u>0 & v>0 & u+v>1, on BC

furthermore, the dot products for finding the positions on AB, AC or BC if needed, have already been calculated in the process.

BTW, I've been having a fair amount of luck with MaxScript: MeshProjIntersect.

1st set up the data structure:

IPM = MeshProjIntersect()
IPM.SetNode $targetSurface
IPM.Build()

Then, having called IPM.ClosestFace [x,y,z], IPM.GetHitPos() returns the closest point on $targetSurface to [x,y,z] .... it really does! Don't know what the hitches are ...:) I guess you have to be careful to call IPM.free()

I did a Bobo-style moving tape test, and one thing that becomes clear, is that (since none of these methods interpolate normals,) unless the point is relatively close to the 'hard' faceted surface, most of the closest points will be vertices.

martinB
01-29-2008, 06:16 PM
Take a look at
http://www.blackpawn.com/texts/pointinpoly/default.html
the barycentric method. Even though it's only concerned with finding if a point is inside a triangle, it's easily extended to the 6 other zones outside it:

u<0 & v<0, closest to A,
u<0 & v<1, on AB,
u<0 & v>1, closest to B,
u<1 & v<0, on AC,
u>1 & v<0, closest to C,
u>0 & v>0 & u+v>1, on BC

furthermore, the dot products for finding the positions on AB, AC or BC if needed, have already been calculated in the process.

Good link, very useful, thanks!

BTW, I've been having a fair amount of luck with MaxScript: MeshProjIntersect.

1st set up the data structure:

IPM = MeshProjIntersect()
IPM.SetNode $targetSurface
IPM.Build()

Then, having called IPM.ClosestFace [x,y,z], IPM.GetHitPos() returns the closest point on $targetSurface to [x,y,z] .... it really does! Don't know what the hitches are ...:) I guess you have to be careful to call IPM.free()

Doh! Thanks very much for pointing that out, I don't know why I haven't tried that myself! I guess I mentally mixed it up with RayMeshGridIntersect, which AFAIK does not work correctly for things other than casting rays. But MeshProjIntersect() is doing exactly what I need, and it does it fast! I get interactive rates on a 66-segment teapot (= 262k faces) as target surface.

And on top of all this, IPM.GetHitFace() gives me the face number and IPM.GetHitBary() the barycentric coordinates, exactly what I need.

Attached is a simple test scene for 3ds Max 2008 that uses this to animate the closest point along the surface. It uses a hacky scripted controller, so you need to enter 'mpi=undefined' whenever you change the teapot, in order for the MeshProjIntersect data structure to be updated.

Thanks a lot!!
-- MartinB

drdubosc
01-29-2008, 06:58 PM
Great! :thumbsup: ... The whole discussion of how to roll your own hasn't been a waste of time; far from it, for me, anyway. Still can't script any better, but it's got my creaky old vector algebra out of the drawer, and given it a good oiling!

I guess the next challenge is to interpolate the normals ....?

martinB
01-29-2008, 10:39 PM
Great! :thumbsup: ... The whole discussion of how to roll your own hasn't been a waste of time; far from it, for me, anyway. Still can't script any better, but it's got my creaky old vector algebra out of the drawer, and given it a good oiling!

I totally agree that this discussion was/is well worth it, even if it is just academic.
I am still interested in clever ways to DIY. I have a working prototype using pure MAXScript but it is very slow compared to the MeshProjIntersect() approach. The prototype first projects the point onto the triangle's plane; then it computes the barycentric coordinates to check whether the point is inside the triangle. If yes, it uses that point to compute the distance and check whether this is shorter than anything it found before. If no, it projects the point onto three lines which contain the triangle's edges and checks whether that projection ends up on an edge our outside. If it is on an edge, it again calculates the distance and keeps the point is the distance is minimal. Finally, it checks the distance for each vertex.

This is highly suboptimal (e.g. I should check each vertex distance only once; also, one could only look at faces "close by") but seems to produce correct results.

So if anyone has a more clever way, I'd be more than happy if he/she could post it.

-- MartinB

drdubosc
01-30-2008, 12:15 AM
... I have a working prototype using pure MAXScript but it is very slow compared to the MeshProjIntersect() approach.

The prototype first projects the point onto the triangle's plane; then it computes the barycentric coordinates to check whether the point is inside the triangle. If yes, it uses that point to compute the distance and check whether this is shorter than anything it found before. If no, it projects the point onto three lines which contain the triangle's edges and checks whether that projection ends up on an edge our outside. If it is on an edge, it again calculates the distance and keeps the point is the distance is minimal. Finally, it checks the distance for each vertex.

This is highly suboptimal (e.g. I should check each vertex distance only once; also, one could only look at faces "close by") but seems to produce correct results.



Are you doing this on every triangle?

There are two separate problems aren't there, if you have more than a few faces?

1. A quick way to find the closest point in a triangle.
2. How not to check most of the triangles.

Your approach to 1 looks very similar to the one on the Blackpawn link, so long as you stash all the results you may have to use later in the calculation. I would have thought it compares quite well? But I also would have thought MeshProjIntersect's speed results chiefly from solving 2, not 1. I'm sure it isn't, but it could afford to be quite sloppy about 1.

Caprier
01-30-2008, 02:15 PM
http://img145.imageshack.us/img145/1861/cf1ko3.jpg

I made a try with a teraedron converted to Editable Mesh. The base vertices are set to Z=0.
getHitFace() returned index 3, which is the face highlighted and obviously wrong.
But getHitPos() did return the correct position of the closest point (with a very small error on the X coordinate).

Could it be that the faces are re-indexed when build() is used?

I also wonder how to know if there are several equidistant closest points and how to find them.
Any idea on how closestFace() does its job?

drdubosc
01-30-2008, 05:22 PM
I made a try with a teraedron converted to Editable Mesh. The base vertices are set to Z=0.
getHitFace() returned index 3, which is the face highlighted and obviously wrong.
But getHitPos() did return the correct position of the closest point (with a very small error on the X coordinate).

Could it be that the faces are re-indexed when build() is used?

I also wonder how to know if there are several equidistant closest points and how to find them.
Any idea on how closestFace() does its job?

True! I've reproduced this.. and like you, I've yet to find another case which fails .. I wonder what makes this excepitonal? Is a tetrahedron a pathological geosphere from the start? It contnues to fail even after it's been moved, converted in and out EPoly, even after it has had faces extruded...

martinB
01-30-2008, 05:32 PM
Are you doing this on every triangle?

Yes. I could in theory use an octree to find the closest vertex and then only search triangles which are closer than that, but I haven't implemented it.

There are two separate problems aren't there, if you have more than a few faces?

1. A quick way to find the closest point in a triangle.
2. How not to check most of the triangles.

Exactly.

Your approach to 1 looks very similar to the one on the Blackpawn link, so long as you stash all the results you may have to use later in the calculation. I would have thought it compares quite well?

Well in what sense? It surely is much slower. I haven't really compared the precise results of the two approaches yet.

-- MartinB

martinB
01-30-2008, 06:18 PM
I made a try with a teraedron converted to Editable Mesh. The base vertices are set to Z=0.
getHitFace() returned index 3, which is the face highlighted and obviously wrong.
But getHitPos() did return the correct position of the closest point (with a very small error on the X coordinate).

Could it be that the faces are re-indexed when build() is used?

I think the face number is simply off by 1. It starts counting at zero, whereas MAXScript counts from 1. See attachment.

-- MartinB

martinB
01-30-2008, 06:20 PM
how do I delete a post?

Caprier
01-30-2008, 06:48 PM
I can't open the file (missing dll). I only have max 9. Sorry.


I think the face number is simply off by 1. It starts counting at zero, whereas MAXScript counts from 1.


Good call, Martin. I checked the four faces of the tetra and it returns index-1.


I could in theory use an octree to find the closest vertex and then only search triangles which are closer than that.


Do you mean to find the closest face by using the closest verts?

Off topic: how do I use 'quote' correctly, so it says "originally posted by..." ?

martinB
01-30-2008, 10:15 PM
I can't open the file (missing dll). I only have max 9. Sorry.

OK, I'll redo the scene in Max9 if you want. It's just a point helper with a script controller that always sits on the closest point to another point helper and also changes the color of the face it sits on.

Do you mean to find the closest face by using the closest verts?

I was thinking of using the distance to the closest vert as an upper bound, to limit the range of triangles that need to be tested.

Off topic: how do I use 'quote' correctly, so it says "originally posted by..." ?

You write this:

[QUOTE=Caprier]

-- MartinB

Caprier
01-30-2008, 10:41 PM
Martin, thanks for the tip about QUOTE.

Don't trouble yourself rewriting the script. I think I got the idea.

Well, I've made tries with every kind of weird configuration I could think of and the meshProjIntersect methods seem to return the correct result every time. The only flaw I've found is the case of several results.


I was thinking of using the distance to the closest vert as an upper bound, to limit the range of triangles that need to be tested.
What do you use for face distances in the test? Each of its vertices? Its center?

For the sake of learning, I'd really like to know how the closestFace() method is implemented.

I was thinking of a similar problem: how to find the shortest distance (and the corresponding points) between two objects? Now THAT should give some serious headaches!

drdubosc
01-31-2008, 12:31 AM
MB ..... You can't delete a post!

martinB
02-02-2008, 01:59 PM
Wasn't there a post in this thread that implemented the method from the blackpawn website? I could swear it was in here, but I cannot find it anymore. Was it removed?

-- MartinB

drdubosc
02-02-2008, 02:15 PM
Wasn't there a post in this thread that implemented the method from the blackpawn website? I could swear it was in here, but I cannot find it anymore. Was it removed?

-- MartinB

yes....hence the reply about not being able to delete a post! Sorry, I thought it was ok, but it was badly flawed, and by the time I'd written the bits to fix it, it would have taken way longer than your way... using the new bases (u,v) for the point doesn't seem to produce the economies I thought it would ... there may be a way... a better maths wiz than me could spot it?

I've been trying to sort this one out, which does use the economies, as far as I can see...
http://www.geometrictools.com/Documentation/DistancePoint3Triangle3.pdf

martinB
02-03-2008, 02:12 PM
yes....hence the reply about not being able to delete a post! Sorry, I thought it was ok, but it was badly flawed, and by the time I'd written the bits to fix it, it would have taken way longer than your way... using the new bases (u,v) for the point doesn't seem to produce the economies I thought it would ... there may be a way... a better maths wiz than me could spot it?

I see. Too bad, I did not have time to test it.


I've been trying to sort this one out, which does use the economies, as far as I can see...
http://www.geometrictools.com/Documentation/DistancePoint3Triangle3.pdf

Excellent find, that PDF looks pretty interesting!

-- MartinB

Caprier
02-04-2008, 01:43 PM
That's pretty much the algorithm described earlier. The link is great!

Would there be a way to determine the closest face before finding the closest point, in order to apply that algorithm only once?
It seems the buid() method in MeshProjIntersect rebuilds data from the original mesh to allow faster calculation. I'm looking for a hint in that direction but have found nothing, so far.

drdubosc
02-05-2008, 10:53 AM
That's pretty much the algorithm described earlier.

It is .. for s,t read u,v. But it avoids explicitly dropping the perpendicular to edges, by using the info. already gained. The link is related to a book:

Geometric Tools for Computer Graphics
Philip J. Schneider and David H. Eberly

which explains it at greater length, for dummies like me, if you can lay your hands on it. ( I can't, ATM )

It seems the build() method in MeshProjIntersect rebuilds data from the original mesh to allow faster calculation. I'm looking for a hint in that direction but have found nothing, so far.

Don't know, but I would imagine build() organises the faces into a tree of subdivisions of the space containing the surface, so that by economically checking the point for proximity to the subdivisions you can (roughly speaking) [eliminate half the faces] > [eliminate half the remaining faces] etc etc. This is cheap if it is justified by repeated use of the (expensive) tree. Hints would be 'Octree'? , 'Kd tree'?.

You could also pre-process the faces themseleves .. for instance

http://www.hiegel.fr/~zavie/Papers/1995%20-%203D%20Distance%20from%20a%20Point%20to%20a%20Triangle.pdf

discusses pre-rotating them, so all intersections can then be calculated in YZ.

CGTalk Moderation
02-05-2008, 10:53 AM
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.