Great! … 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 …?
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
Are you doing this on every triangle?
There are two separate problems aren’t there, if you have more than a few faces?
- A quick way to find the closest point in a triangle.
- 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.
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.
Exactly.
Well in what sense? It surely is much slower. I haven’t really compared the precise results of the two approaches yet.
– MartinB
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…
I think the face number is simply off by 1. It starts counting at zero, whereas MAXScript counts from 1. See attachment.
– MartinB
how do I delete a post?
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…” ?
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.
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.
You write this:
[QUOTE=Caprier]
– MartinB
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.
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!
MB … You can’t delete a post!
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
I see. Too bad, I did not have time to test it.
Excellent find, that PDF looks pretty interesting!
– MartinB
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.
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 )
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
discusses pre-rotating them, so all intersections can then be calculated in YZ.