RACBVHs: random-accessible compressed bounding volume hierarchies

Tae-Joon Kim 1 , Bochang Moon 1 , Duk-Su Kim 1 , Sung-Eui Yoon 1


IEEE Transactions on Visualization and Computer Graphics (TVCG), 2010

The left and middle images show results of ray tracing using our random-accessible compressed bounding volume hierarchies (RACBVHs) of St. Matthew model consisting of 128 M triangles and an iso-surface model consisting of 102 M triangles. The right image shows a frame during a rigid-body simulation using collision detection between two models including the Lucy model consisting of 28 M triangles. By using RACBVHs, we can reduce the storage requirement by a factor of 10:1 and, more importantly, improve the performance of ray tracing and collision detection by more than a factor of four over using uncompressed data.


We present a novel compressed bounding volume hierarchy (BVH) representation, random-accessible compressed bounding volume hierarchies (RACBVHs), for various applications requiring random access on BVHs of massive models. Our RACBVH representation is compact and transparently supports random access on the compressed BVHs without decompressing the whole BVH. To support random access on our compressed BVHs, we decompose a BVH into a set of clusters. Each cluster contains consecutive bounding volume (BV) nodes in the original layout of the BVH. Also, each cluster is compressed separately from other clusters and serves as an access point to the RACBVH representation. We provide the general BVH access API to transparently access our RACBVH representation. At runtime, our decompression framework is guaranteed to provide correct BV nodes without decompressing the whole BVH. Also, our method is extended to support parallel random access that can utilize the multi-core CPU architecture. Our method can achieve up to a 12:1 compression ratio and, more importantly, can decompress 4.2M BV nodes (= 135 MB) per second by using a single CPU-core. To highlight the benefits of our approach, we apply our method to two different applications: ray tracing and collision detection. We can improve the runtime performance by more than a factor of 4 as compared to using the uncompressed original data. This improvement is a result of the fast decompression performance and reduced data access time by selectively fetching and decompressing small regions of the compressed BVHs requested by applications.

Video (available to download in the last section)


Related Links