KDet: Parallel Constant Time Collision Detection for Polygonal Objects. (23rd May 2017)

• Record Type: Journal Article
• Authors: Weller, René; Debowski, Nicole; Zachmann, Gabriel
• Is Part Of: Computer graphics forum. Volume 36:Number 2(2017)
• Page Start: 131
• Page End: 141
• Publication Date: 2017-05-23
• Subjects: Categories and Subject Descriptors (according to ACM CCS) -- I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Geometric algorithms, languages, and systems; Computer graphics -- Periodicals; 006.605
• DOI: 10.1111/cgf.13113
• Languages: English
• ISSNs: 0167-7055

Abstract

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.