Jump to content
  • Advertisement
Sign in to follow this  

distance to mesh problem or surface constraint problem

This topic is 3973 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone, my first post so bear with me. Hopefully this is right area for this. I am trying to do a surface constraint plugin for a 3d animation program. I've got so far that I get the shortest distance to triangular mesh and while it is good for binding something to surface and then deforming that surface, it is not good for moving something on that surface. To be more precise, on convex parts of surface, my constrain gets "stuck" to vertices. In concave parts it jumps over the vertices. This is quite rational as I am only searching for distances to tris. I tried to do some fancy vector projecting with help of nearest vertex normal to smooth out the boundaries, but no luck (or skill). Also I tried to study splines, but think it's too advanced for me at this stage. So if someone could help me out with this or point me to source suitable for beginner, I'd be grateful. Thank you for reading through.

Share this post

Link to post
Share on other sites
Got an idea and progressed a bit.

p = point we want to find "closest" point on surface

Find nearest vertice
For every tri that vertice belongs to, do following:
1. Find intersections with plane (defined by p and tri normal) and rays (from vertex to direction of vertex normal) for every vertice.
2. These intersections defines new tri.
3. Get barycentric coords for p on this new tri.
4. Get point on original tri with these same barycentric coords.
5. Get distance from p to this point on original tri.

Then just pick the one that is closest.

I have still some problems. Above method works nicely on ball, but when I try it on cube, there is some funny things going on. When I am crossing some edges, it jumps a bit, when crossing others, it just works as expected. About 50% of edges give this jump.

What is your opinion, is this mathematically correct way? Am I missing some vital step with my method or is it that there is probably something wrong in my code?

Thanks for reading.

Share this post

Link to post
Share on other sites
I wouldn't want to suggest an alternative, but either your method is flawed or I am misunderstanding.

First, you can't guarantee that the closest point on the mesh belongs to a triangle that is adjacent to the closest vertex in the mesh. That's a bit of a brain-twister, but here's the picture in my mind's eye:

Consider one pyramid hovering a short distance directly above another. Now if your sample point is directly in the centre of the base of the upper pyramid, then the closest mesh-point is clearly in one of the triangles composing this base. But the closest vertex in the scene is the apex of the lower pyramid, and so the algorithm fails.

Furthermore, if p is incident with more than three triangles, then you'll end up with more than three points, and things get more complicated. The next consideration would be whether these points are necessarily coplanar. If not, things are more complicated again.

Share this post

Link to post
Share on other sites
Thanks for reply.

You are absolutely right with finding closest vertex problem, thanks to your example, I think I grasped that part.

So let me re-phrase what I am doing at the moment (also added step I forgot to mention):

For EVERY tri
1. Find intersections with plane (defined by P and tri normal) and vertex normals for every vertice that defines tri.

2. These intersections defines new tri, lets call it sTri for "scaled" tri

3. Get barycentric coords for P on sTri.

4. Check that P is inside sTri, if it is, continue.

5. Get point on original tri with these same barycentric coords.

6. Get distance from P to this point on original tri.

Whichever of these points is closest to P is the point.

I made a little drawing help me explain what I mean:

For simplicity this is 2d.
N = vertex normal
P = point we want to put on surface
F1 and F2 = adjacent faces
F1S and F2S = planes definec by face normal and P

As you can see I extended vertex normal to other side to visualize the intersection with F2S. As P is on vertex normal, sTris should be nicely aligned.

This seems to work fine on ball, but not on cube. One thing it surely doesn't work on, is when vertex normal is parallel to plane defined by P and tri normal - but I don't need it to work on that.

Share this post

Link to post
Share on other sites
I hate to keep shooting you down, but this won't work as you can't guarantee a closest point (since each triangle may fail at step 4). Consider another pyramid with P directly above the apex for an example.

Since you've resorted to an O(#triangles) algorithm, here's what I would suggest:

Given a mesh {T} and a point P,
For each triangle T in the mesh:
1. Define R to be the line passing through P in the direction of T's face-normal.
2. Compute the intersection Q of R and the unique plane containing T.
3. Evaluate Q in terms barycentric coordinates of T. Call the result Q'.
4. Clamp Q' to T and call the result Q''. (so that if P is outside T, Q'' will be on an edge of T).
5. Evaluate Q'' in Cartesian coordinates, P''.
6. Determine the distance D between P and P''.
Now the P'' corresponding to the shortest D will be the closest point on the mesh to P.

This isn't exactly a lightning-fast algorithm. But unfortunately, I can't see a way to significantly cull {T} without losing some potential hits.

One measure you could take to speed things up, for a closed mesh and external point, is to discard any back-facing triangles from {T}. My intuition tells me that further optimisation can be made for convex meshes, but I can't envisage this any further.

Share this post

Link to post
Share on other sites
Thanks for reply. Don't mind about shooting me down, since I am asking for help.

I've tried earlier the way you suggested and the problem with this was that: on convex parts of mesh it gets "stuck" in to vertices and in concave it jumps over them. When P is on vertice normal, distances from P to planes are equal.


Hopefully that picture explains it better. Especially in concave case it's easy to imagine P crossing vertex normal and how it "jumps" from tri to other tri.

About every tri failing step 4: I am expecting user to react on such things. If no suitable tri found, then no displacement for point P.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!