Video encoded with QuickTime Viewer (18M)
(You can download QuickTime from QuickTime)
|
Ray Tracing the Lucy model: We apply a standard kd-tree based ray tracing algorithm to the Lucy model consisting of 28 million triangles. A reflective plane is placed behind the Lucy model and the scene also has shadows. We compute a cache-efficient layout of the kd-tree of the Lucy model using our algorithm. Our layout improves the performance of ray tracing by up to two times over tested layouts, without any change to the underlying algorithm.
Abstract: We present a novel algorithm to compute cache-efficient layouts of bounding volume hierarchies (BVHs) of polygonal models. We 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 working set. Also, our algorithm works well with 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.
|
Collision Detection between Hugo and 1M Power Plant Models: The hugo robot model is placed inside the power plant model, whose overall shape is shown on the right. We are able to achieve 35%--2600% performance improvement in collision detection by using our cache-efficient layouts of the OBBTree over other tested layouts.
R-LODs: Fast LOD-based Ray Tracing of Massive Models
CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175