check two meshes ...
Author
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
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.
Author
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?
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?
Quote:Original post by ZoombyThere 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.).
What I search (if it exists) is a trick to quickly check if two meshes intersect...
Author
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.
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
