Sign in to follow this  
Zoomby

check two meshes ...

Recommended Posts

hi, I'm wondering if there is a trick/algorithm to check: a) the exact shortest distance between two meshes b) if a mesh is exactly inside another mesh that runs faster than O(n*m) (i.e case a: check every point of mesh A if it's inside every faces plane of mesh B ), and has a benefit if the meshes have only a few faces? (With "exact" I mean that no bounding boxes should be involved) bye, Chris

Share this post


Link to post
Share on other sites
You might take a look at the Lin-Canny closest feature algorithm. You would be able to get the closest distance and detect collisions. It requires some non-trivial setup, but it's near O(1) in practice.

Share this post


Link to post
Share on other sites
Thanks,

but if I understood it, Lin-Canny only brings benefits when the objects are moving. I have a static scene of objects.

What I search (if it exists) is a trick to quickly check if two meshes intersect,
But I can't use bounding boxes (too coarse) or oriented bounding boxes (precaluclation too expensive, don't understand the algo right now).
Does such a trick exist?

Share this post


Link to post
Share on other sites
Quote:
Original post by Zoomby
What I search (if it exists) is a trick to quickly check if two meshes intersect...
There are various algorithms for this, but most are designed to work with convex objects only; are your meshes convex? Also, keep in mind that determining distance, testing for containment, and testing for intersection are different (although related) tests, so for more specific advice you might specify exactly what test you want to perform and what its purpose is (e.g. for spatial partitioning, provide data to feed to a physics simulator, etc.).

Share this post


Link to post
Share on other sites
Hi,
yeah, the meshes are convex. I'm mainly interested in checking the distance between two meshes.
The purpose is to aggregate nearby small objects (using the convex hull). Then you can click on such a hull to view the details (some kind of LOD).
I already use a qudatree to speed things up, but if there is a enormous number of objects, checking these meshes distances simply takes a long time, despite the quadtree. Hence I search a trick to quicker check distances.

Share this post


Link to post
Share on other sites
Have you tried the method of separating axes? You can check it out HERE at Dave Eberly's website. That should give you some form of speed up in the triangle to triangle type tests.

However, you may want to consider using a mixed type of test where you test with an OBB or a bounding sphere as a top level test to cull the objects that are far apart, then fall back to a finer test for the ones that are closer. It sounds like your quadtree would be a good start for the coarse level tests.

Share this post


Link to post
Share on other sites
If you're finding that bounding volumes only is too imprecise and you really need the exact distance, you might look into GJK. It's not trivial to implement, but for an intersection/distance query only it's not too bad.

Share this post


Link to post
Share on other sites

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