Premium
Cache‐Efficient Layouts of Bounding Volume Hierarchies
Author(s) -
Yoon SungEui,
Manocha Dinesh
Publication year - 2006
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2006.00970.x
Subject(s) - computer science , cache , parallel computing , bounding volume , cache oblivious algorithm , bounding overwatch , cache algorithms , block (permutation group theory) , probabilistic logic , cpu cache , algorithm , theoretical computer science , collision detection , collision , programming language , mathematics , artificial intelligence , geometry
We present a novel algorithm to compute cache‐efficient layouts of bounding volume hierarchies (BVHs) of polygonal models. Our approach does not make any assumptions about the cache parameters or block sizes of the memory hierarchy. We introduce a new probabilistic model to predict the runtime access patterns of a BVH. Our layout computation algorithm utilizes parent‐child and spatial localities between the accessed nodes to reduce both the number of cache misses and the size of the working set. Our algorithm also works well for spatial partitioning hierarchies including kd‐trees. We use our algorithm to compute layouts of BVHs and spatial partitioning hierarchies of large models composed of millions of triangles. We compare our cache‐efficient layouts with other layouts in the context of collision detection and ray tracing. In our benchmarks, our layouts consistently show better performance over other layouts and improve the performance of these applications by 26% – 300% without any modification of the underlying algorithms or runtime applications. Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Hierarchy and Geometric Transformations