# check two meshes ...

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

## 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 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 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 on other sites
Quote:
 Original post by ZoombyWhat 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 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 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 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.

1. 1
2. 2
3. 3
4. 4
frob
15
5. 5

• 10
• 12
• 20
• 12
• 13
• ### Forum Statistics

• Total Topics
632148
• Total Posts
3004450

×