kDet: Parallel Constant Time Collision Detection for Polygonal Objects

dc.contributor.authorWeller, Renéen_US
dc.contributor.authorDebowski, Nicoleen_US
dc.contributor.authorZachmann, Gabrielen_US
dc.contributor.editorLoic Barthe and Bedrich Benesen_US
dc.date.accessioned2017-04-22T16:25:53Z
dc.date.available2017-04-22T16:25:53Z
dc.date.issued2017
dc.description.abstractWe 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.number2
dc.description.sectionheadersMorphing and Interaction
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume36
dc.identifier.doi10.1111/cgf.13113
dc.identifier.issn1467-8659
dc.identifier.pages131-141
dc.identifier.urihttps://doi.org/10.1111/cgf.13113
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13113
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectI.3.5 [Computer Graphics]
dc.subjectComputational Geometry and Object Modeling
dc.subjectGeometric algorithms
dc.subjectlanguages
dc.subjectand systems
dc.titlekDet: Parallel Constant Time Collision Detection for Polygonal Objectsen_US
Files
Collections