Logo des Repositoriums
Zur Startseite
  • English
  • Deutsch
Anmelden
  1. Startseite
  2. SuUB
  3. Forschungsdokumente
  4. kDet: Parallel Constant Time Collision Detection for Polygonal Objects
 
Zitierlink DOI
10.26092/elib/2367
Verlagslink DOI
10.1111/cgf.13113

kDet: Parallel Constant Time Collision Detection for Polygonal Objects

Veröffentlichungsdatum
2017
Autoren
Weller, René  
Debowski, Nicole  
Zachmann, Gabriel  
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.
Schlagwörter
Computer Graphics

; 

Computational geometry

; 

Object Modeling

; 

Geometric algorithms, languages, and systems
Verlag
Wiley
Institution
Universität Bremen  
Fachbereich
Fachbereich 03: Mathematik/Informatik (FB 03)  
Dokumenttyp
Artikel/Aufsatz
Zeitschrift/Sammelwerk
Computer Graphics Forum  
Startseite
131
Endseite
141
Zweitveröffentlichung
Ja
Dokumentversion
Postprint
Lizenz
Alle Rechte vorbehalten
Sprache
Englisch
Dateien
Lade...
Vorschaubild
Name

Debowski-Weller-Zachmann_kDet-ConstantTimeCollisionDetection_accepted-version_PDF-A.pdf

Size

3.7 MB

Format

Adobe PDF

Checksum

(MD5):f63e46e9b8a016fd682a1f2c8a95397d

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Datenschutzbestimmungen
  • Endnutzervereinbarung
  • Feedback schicken