kDet: Parallel Constant Time Collision Detection for Polygonal Objects
|Debowski-Weller-Zachmann_kDet-ConstantTimeCollisionDetection_accepted-version_PDF-A.pdf||3.79 MB||Adobe PDF||View/Open|
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|
checked on Sep 29, 2023
checked on Sep 29, 2023
Items in Media are protected by copyright, with all rights reserved, unless otherwise indicated.