Cache-Oblivious Mesh Layouts

by Sung-Eui Yoon, Peter Lindstrom, Valerio Pascucci, and Dinesh Manocha.

New Software Announcement: OpenCCL

OpenCCL: Cache-Coherent Layouts of Graphs and Meshes




Video encoded with QuickTime Viewer (42MB)

(You can download QuickTime from QuickTime)

Scan of Michelangelo's St. Matthew: We precompute a cache-oblivious layout of this 9.6GB scanned model with 372M triangles. Our novel metric results in a cache-oblivious layout and at runtime reduces the vertex cache misses by more than a factor of four for interactive view-dependent rendering. As a result, we improve frame rate by almost five times. We achieve a throughput of 106M tri/sec (at 82 fps) on an NVIDIA GeForce 6800 GPU.

We present a novel method for computing cache-oblivious layouts of large meshes that improve the performance of interactive visualization and geometric processing algorithms. In our approach we make only general assumptions on the locality of geometric algorithms and make no assumption with regard to the particular data access pattern or cache parameters of the memory hierarchy involved in the computation. Furthermore, our formulation extends directly to computing layouts of multi-resolution and bounding volume hierarchies of large meshes. We develop a simple and practical cache-oblivious metric to estimate cache misses. Computing a coherent mesh layout is reduced to a combinatorial optimization problem. We designed and implemented an out-of-core multilevel minimization algorithm and tested its performance on unstructured meshes composed of tens or hundreds of millions of triangles. Our layouts can significantly reduce the number of cache misses. We have observed 2-20 times speedups in view-dependent rendering, collision detection and isocontour extraction without any modification of the algorithms or runtime applications.

A Cache-Oblivious Layout of the Bunny Model: All edges that join two consecutive vertices in the layout are drawn with black line segments to visualize edges that have smallest edge span. We use a smooth ramp from orange (first triangle) to white (last triangle) to visualize the ordering of triangles.

Contents

Paper:
Talk slides: Powerpoint slides, SIGGRAPH talk
Powerpoint slides, Visualization 06 talk


Related Links

Cache-Oblivious Layouts of Bounding Volume Hierarchies

Quick-VDR: Interactive View-dependent Rendering of Massive Models

UNC Walkthru Group

UNC Gamma Group

CB #3175, Department of Computer Science
University of North Carolina
Chapel Hill, NC 27599-3175
919.962.1749
geom@cs.unc.edu