kDet: Parallel Constant Time Collision Detection for Polygonal Objects
| dc.contributor.author | Weller, René | en_US |
| dc.contributor.author | Debowski, Nicole | en_US |
| dc.contributor.author | Zachmann, Gabriel | en_US |
| dc.contributor.editor | Loic Barthe and Bedrich Benes | en_US |
| dc.date.accessioned | 2017-04-22T16:25:53Z | |
| dc.date.available | 2017-04-22T16:25:53Z | |
| dc.date.issued | 2017 | |
| dc.description.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. | en_US |
| dc.description.number | 2 | |
| dc.description.sectionheaders | Morphing and Interaction | |
| dc.description.seriesinformation | Computer Graphics Forum | |
| dc.description.volume | 36 | |
| dc.identifier.doi | 10.1111/cgf.13113 | |
| dc.identifier.issn | 1467-8659 | |
| dc.identifier.pages | 131-141 | |
| dc.identifier.uri | https://doi.org/10.1111/cgf.13113 | |
| dc.identifier.uri | https://diglib.eg.org:443/handle/10.1111/cgf13113 | |
| dc.publisher | The Eurographics Association and John Wiley & Sons Ltd. | en_US |
| dc.subject | I.3.5 [Computer Graphics] | |
| dc.subject | Computational Geometry and Object Modeling | |
| dc.subject | Geometric algorithms | |
| dc.subject | languages | |
| dc.subject | and systems | |
| dc.title | kDet: Parallel Constant Time Collision Detection for Polygonal Objects | en_US |