Rapid Collision Detection by Dynamically Aligned DOP-Trees
Paper
Abstract
Based on a general hierarchical data structure,
we present a fast algorithm for exact collision detection
of arbitrary polygonal rigid objects.
Objects consisting of hundreds of thousands of polygons can be checked
for collision at interactive rates.
The pre-computed hierarchy is a tree of
discrete oriented polytopes (DOPs).
An efficient way of re-aligning DOPs during traversal of such trees
allows to use simple interval tests for determining overlap
between DOPs.
The data structure is very efficient in terms of memory and
construction time.
Extensive experiments with synthetic and
real-world CAD data have been carried out to analyze the performance
and memory usage of the data structure.
A comparison with OBB-trees indicates that
DOP-trees as efficient in terms of collision query time,
and more efficient in memory usage
and construction time.
BibTeX entry
@INPROCEEDINGS{Zach98b
, author = "Gabriel Zachmann"
, title = "Rapid Collision Detection by Dynamically Aligned {DOP}-Trees"
, booktitle = "Proc. of IEEE Virtual Reality Annual International
Symposium; VRAIS '98"
, pages = "90--97"
, year = 1998
, month = mar
, address = "Atlanta, Georgia"
}
In case of problems
In case of problems, please don't hesitate to
contact me.
(For instance, if your host is not registered by the world-wide Domain
Name Service (DNS), then you will not be able to ftp ...)
Gabriel Zachmann
Last modified:
Fri Mar 10 13:29:40 MET 2006