kDet: Parallel Constant Time Collision Detection for Polygonal Objects
Veröffentlichungsdatum
2017
Zusammenfassung
We define a novel geometric predicate and a class of objects that enables us to prove a linear bound on the number of intersecting polygon pairs for colliding 3D objects in that class. Our predicate is relevant both in theory and in practice: it is easy to check and it needs to consider only the geometric properties of the individual objects – it does not depend on the configuration of a given pair of objects. In addition, it characterizes a practically relevant class of objects: we checked our predicate on a large database of real-world 3D objects and the results show that it holds for all but the most pathological ones.
Our proof is constructive in that it is the basis for a novel collision detection algorithm that realizes this linear complexity also in practice. Additionally, we present a parallelization of this algorithm with a worst-case running time that is independent of the number of polygons. Our algorithm is very well suited not only for rigid but also for deformable and even topology-changing objects, because it does not require any complex data structures or pre-processing.
We have implemented our algorithm on the GPU and the results show that it is able to find in real-time all colliding polygons for pairs of deformable objects consisting of more than 200k triangles, including self-collisions.
Our proof is constructive in that it is the basis for a novel collision detection algorithm that realizes this linear complexity also in practice. Additionally, we present a parallelization of this algorithm with a worst-case running time that is independent of the number of polygons. Our algorithm is very well suited not only for rigid but also for deformable and even topology-changing objects, because it does not require any complex data structures or pre-processing.
We have implemented our algorithm on the GPU and the results show that it is able to find in real-time all colliding polygons for pairs of deformable objects consisting of more than 200k triangles, including self-collisions.
Schlagwörter
Computer Graphics
;
Computational geometry
;
Object Modeling
;
Geometric algorithms, languages, and systems
Verlag
Wiley
Institution
Fachbereich
Dokumenttyp
Artikel/Aufsatz
Zeitschrift/Sammelwerk
Startseite
131
Endseite
141
Zweitveröffentlichung
Ja
Dokumentversion
Postprint
Lizenz
Sprache
Englisch
Dateien![Vorschaubild]()
Lade...
Name
Debowski-Weller-Zachmann_kDet-ConstantTimeCollisionDetection_accepted-version_PDF-A.pdf
Size
3.7 MB
Format
Adobe PDF
Checksum
(MD5):f63e46e9b8a016fd682a1f2c8a95397d