Binary Ostensibly‐Implicit Trees for Fast Collision Detection

We 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 compac...

Full description

Saved in:
Bibliographic Details
Published in:Computer graphics forum 2020-05, Vol.39 (2), p.509-521
Main Authors: Chitalu, Floyd M., Dubach, Christophe, Komura, Taku
Format: Article
Language:English
Subjects:
CCS Concepts
Computing methodologies → Collision detection
Hierarchies
Mapping
Nodes
Refitting
Representations
Topology
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We 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 6× 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.
ISSN:0167-7055
1467-8659
DOI:10.1111/cgf.13948