Binary Ostensibly-Implicit Trees for Fast Collision Detection

Simple item page
dc.contributor.authorChitalu, Floyd M.en_US
dc.contributor.authorDubach, Christopheen_US
dc.contributor.authorKomura, Takuen_US
dc.contributor.editorPanozzo, Daniele and Assarsson, Ulfen_US
dc.date.accessioned2020-05-24T12:53:59Z
dc.date.available2020-05-24T12:53:59Z
dc.date.issued2020
dc.description.abstractWe present a simple, efficient and low-memory technique, targeting fast construction of bounding volume hierarchies (BVH) for broad-phase collision detection. To achieve this, we devise a novel representation of BVH trees in memory. We develop a mapping of the implicit index representation to compact memory locations, based on simple bit-shifts, to then construct and evaluate bounding volume test trees (BVTT) during collision detection with real-time performance. We model the topology of the BVH tree implicitly as binary encodings which allows us to determine the nodes missing from a complete binary tree using the binary representation of the number of missing nodes. The simplicity of our technique allows for fast hierarchy construction achieving over 6x speedup over the state-of-the-art. Making use of these characteristics, we show that not only it is feasible to rebuild the BVH at every frame, but that using our technique, it is actually faster than refitting and more memory efficient.en_US
dc.description.number2
dc.description.sectionheadersSpatial Queries
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume39
dc.identifier.doi10.1111/cgf.13948
dc.identifier.issn1467-8659
dc.identifier.pages509-521
dc.identifier.urihttps://doi.org/10.1111/cgf.13948
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13948
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.rightsAttribution 4.0 International License
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectComputing methodologies
dc.subjectCollision detection
dc.titleBinary Ostensibly-Implicit Trees for Fast Collision Detectionen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
v39i2pp509-521.pdf
Size:
11.46 MB
Format:
Adobe Portable Document Format
Download
Collections
39-Issue 2