[ODE] Distance between two objects

Anton kronos at mtcelestia.net
Wed Apr 21 13:04:47 MST 2004


> In the native traversal, to get the minimum
> distance, you need to turn "collision" (which can be "greedy" or "locally
> optimizing") into "minimum of all"; turning off the greedy part of the
> traversal is what turns log(N) into N/2.

i believe if one has two bounding volumes and a test object (a triangle or
another bounding volume), one of these volumes can be skipped entirely if
the minimum distance between it and the test object is more than the miminum
distance between *triangles* in another bounding volume and *triangles* in
the test object. in order to check this, one doesn't need to iterate through
all triangle pairs inside, it's sufficient to have a conservative estimate,
which is "the minimum distance between triangles placed inside the objects
in such a way that the shapes of the bounding objects are preserved while
the minimum distance between them [triangles] is *maximized*" (it seems that
this can boil down to computing "spanning" vertex sets for the bounding
volumes that maximize the minimum distance between them). this can give
"expected" O(log(N)) performance, and O(N) worst-case performance.




More information about the ODE mailing list