Sign in to follow this  

How to find minimum distance?

This topic is 4111 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

I have a shape made up of many triangles (3D model of a hand). The user controls a Reference Point in 3d space using the mouse and keyboard. How can I find the minimum distance between the 3D model and the Reference Point? If I know the minimum distance I can then do collision detection.

Share this post


Link to post
Share on other sites
Quote:
Original post by mmakrzem
I have a shape made up of many triangles (3D model of a hand). The user controls a Reference Point in 3d space using the mouse and keyboard. How can I find the minimum distance between the 3D model and the Reference Point?
I googled using the search string 'closest point non convex objects' and got some seemingly relevant hits, so you might give that a try. Unless you absolutely positively need an exact result though, I'd represent the hand as a collection of capsules and lozenges and take the minimum distance to these primitives. Closest-point tests for these shapes are fairly straightforward and are well documented.

Other than that, some more info might be useful. Is the hand animated? (Other than moving around rigidly, that is.) If so, is it a hierarchy of linked meshes, or a single deformed mesh, say, skeletally animated? These details would help to define the problem a bit more.

Share this post


Link to post
Share on other sites
there are things that track the minimum distance calculations between frames, like GJK and V-Clip, but it's quite tricky to implement. Simplifying the shapes to cylinders, capsules and boxes will go a long way.

Share this post


Link to post
Share on other sites
Quote:
Original post by mmakrzem
GJK... hmmm I'll look into this. not sure what it is. Unfortunately I can't simplify my geometry because of the nature of my simulation.
Unless there's some aspect of these algorithms I'm not aware, GJK, V-Clip, or what have you will require that your mesh be represented as a collection of individual convex objects.

As a side note, I recall seeing a video online demonstrating one of these techniques (V-clip or something related, I think) using such a hand model. The video shows the closest-point tracking between the moving hand and the object in the environment in action. Maybe someone here is familiar with this video and could post a link, as it might of interest to you.

Anyway, would it be reasonable to ask why you can't simplify the geometry? You say 'because of the nature of the simulation', but that doesn't tell us much. I mention this only because using simplified bounding volumes or polytopes would be much more practical than the alternatives. Just thinking about the form of the human hand, it seems unlikely that the difference in accuracy between the actual mesh and a representation based on capsules, lozenges, cylinders, spheres, OBBs, or polytopes would be noticable in a practical application.

Also, you mention that you need this for collision detection. Keep in mind that a non-convex object such as a hand could have multiple closest points to a query point, and/or intersect another object in multiple places. So that's something to keep in mind as well.

[Edit: If you're intent on an exact solution, again I recommend googling 'non convex closest point' and 'non convex minimum distance'. Each of these turns up links to relevant papers or references.]

Share this post


Link to post
Share on other sites
Thanks for all your help. I'll check out those suggestions that you made.

What I am doing in my simulation is working with haptics. So imagine the reference point being a point controlled by a 3D mouse / haptic device. As soon as this point touches my model (or any 3D model), I generate a force to resist the users motion. I need to know the exact solution so that the haptics match the graphics on the screen.

If you are interested in learning more about haptics check out my companies website www.handshakevr.com


I am very interested in seeing these video tutorials that you mentioned. Let me know if you are able to find them.

Share this post


Link to post
Share on other sites
google for GJK and V-Clip (or Voronoi Clip), These libs have been done with precisely what you have in mind (VR, haptic), and it's university research stuff (you should undersatnd the docs and maths way better than I can :)).

As form an haptic system for a hand, you can definitely limit your representation to a few simplices, capsules and spheres would be the easiest.

You can process distance queries with loads of sphere and capsules very very quickly, and very simply. That stuff could be coded in a matter of 1/2 a day, it's so simple my 6 month old niece could code it, especially if you have skeleton data available (i.e. you dont have to fit the simplices into the polygon data every frames).

I would at least start with that, and if you want some fancy stuff, move towards more complicated and painful systems. I can't deny it would look good in a PhD thesis to sub-contract a thrid party library from Stanford or MIT and the likes, or even better, design your own.

Share this post


Link to post
Share on other sites

This topic is 4111 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this