Weller, RenéRenéWellerDebowski, NicoleNicoleDebowskiZachmann, GabrielGabrielZachmann2023-08-022023-08-0220170167-7055https://media.suub.uni-bremen.de/handle/elib/704610.26092/elib/2367We 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.enAlle Rechte vorbehaltenAlle Rechte vorbehaltenComputer GraphicsComputational geometryObject ModelingGeometric algorithms, languages, and systems0Artikel/Aufsatzurn:nbn:de:gbv:46-elib70466