Skip navigation
SuUB logo
DSpace logo

  • Home
  • Institutions
    • University of Bremen
    • City University of Applied Sciences
    • Bremerhaven University of Applied Sciences
  • Sign on to:
    • My Media
    • Receive email
      updates
    • Edit Account details

Citation link: https://doi.org/10.26092/elib/2367

Publisher DOI: https://doi.org/10.1111/cgf.13113
Debowski-Weller-Zachmann_kDet-ConstantTimeCollisionDetection_accepted-version_PDF-A.pdf
OpenAccess
 
copyright

kDet: Parallel Constant Time Collision Detection for Polygonal Objects


File Description SizeFormat
Debowski-Weller-Zachmann_kDet-ConstantTimeCollisionDetection_accepted-version_PDF-A.pdf3.79 MBAdobe PDFView/Open
Authors: Weller, René 
Debowski, Nicole 
Zachmann, Gabriel  
Abstract: 
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.
Keywords: Computer Graphics; Computational geometry; Object Modeling; Geometric algorithms, languages, and systems
Issue Date: 2017
Publisher: Wiley
Project: Creative Unit – Intra-Operative Information 
Funders: German Federal Ministry of Economics and Technology (BMWi)
Grant number: 16KN036252
Journal/Edited collection: Computer Graphics Forum 
Start page: 131
End page: 141
Type: Artikel/Aufsatz
ISSN: 0167-7055
Secondary publication: yes
Document version: Postprint
DOI: 10.26092/elib/2367
URN: urn:nbn:de:gbv:46-elib70466
Institution: Universität Bremen 
Faculty: Fachbereich 03: Mathematik/Informatik (FB 03) 
Appears in Collections:Forschungsdokumente

  

Page view(s)

27
checked on Sep 29, 2023

Download(s)

5
checked on Sep 29, 2023

Google ScholarTM

Check


Items in Media are protected by copyright, with all rights reserved, unless otherwise indicated.

Legal notice -Feedback -Data privacy
Media - Extension maintained and optimized by Logo 4SCIENCE