Show simple item record

dc.contributor.authorSerpa, Ygor Rebouçasen_US
dc.contributor.authorRodrigues, Maria Andréia Formicoen_US
dc.contributor.editorChen, Min and Benes, Bedrichen_US
dc.date.accessioned2019-03-17T09:56:54Z
dc.date.available2019-03-17T09:56:54Z
dc.date.issued2019
dc.identifier.issn1467-8659
dc.identifier.urihttps://doi.org/10.1111/cgf.13529
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13529
dc.description.abstractRealistic computer simulations of physical elements such as rigid and deformable bodies, particles and fractures are commonplace in the modern world. In these simulations, the broad‐phase collision detection plays an important role in ensuring that simulations can scale with the number of objects. In these applications, several degrees of motion coherency, distinct spatial distributions and different types of objects exist; however, few attempts have been made at a generally applicable solution for their broad phase. In this regard, this work presents a novel broad‐phase collision detection algorithm based upon a hybrid SIMD optimized KD‐Tree and sweep‐and‐prune, aimed at general applicability. Our solution is optimized for several objects distributions, degrees of motion coherence and varying object sizes. These features are made possible by an efficient and idempotent two‐step tree optimization algorithm and by selectively enabling coherency optimizations. We have tested our solution under varying scenario setups and compared it to other solutions available in the literature and industry, up to a million simulated objects. The results show that our solution is competitive, with average performance values two to three times better than those achieved by other state‐of‐the‐art AABB‐based CPU solutions.Realistic computer simulations of physical elements such as rigid and deformable bodies, particles and fractures are commonplace in the modern world. In these simulations, the broad‐phase collision detection plays an important role in ensuring that simulations can scale with the number of objects. In these applications, several degrees of motion coherency, distinct spatial distributions and different types of objects exist; however, few attempts have been made at a generally applicable solution for their broad phase. In this regard, this work presents a novel broad‐phase collision detection algorithm based upon a hybrid SIMD optimized KD‐Tree and sweep‐and‐prune, aimed at general applicability. Our solution is optimized for several objects distributions, degrees of motion coherence and varying object sizes. These features are made possible by an efficient and idempotent two‐step tree optimization algorithm and by selectively enabling coherency optimizations.en_US
dc.publisher© 2019 The Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectcollision detection
dc.subjectanimation
dc.subjectComputer Graphics [Computing Methodologies]: Animation‐Collision detection
dc.titleFlexible Use of Temporal and Spatial Reasoning for Fast and Scalable CPU Broad‐Phase Collision Detection Using KD‐Treesen_US
dc.description.seriesinformationComputer Graphics Forum
dc.description.sectionheadersArticles
dc.description.volume38
dc.description.number1
dc.identifier.doi10.1111/cgf.13529
dc.identifier.pages260-273


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record