Cache-Oblivious Mesh Layouts - Geometric Algorithms for Modeling

We present a novel method for computing cache-oblivious layouts of large meshes that improve the performance of interactive visualization and geometric processing algorithms. Given that the mesh is accessed in a reasonably coherent manner, we assume no particular data access patterns or cache parameters of the memory hierarchy involved in the computation. Furthermore, our formulation extends directly to computing layouts of multi-resolution and bounding vol- ume hierarchies of large meshes. We develop a simple and practical cache-oblivious metric for estimating 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 to hundreds of millions of triangles. Our layouts can signicantly 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. 1 Introduction Over the last few years, advances in model acquisition, computer- aided design, and simulation technologies have resulted in massive databases of complex geometric models. Meshes composed of tens or hundreds of millions of triangles are frequently used to represent CAD environments, terrains, isosurfaces, and scanned models. Efficient algorithms for processing large meshes utilize the computational power of CPUs and GPUs for interactive visualization and geometric applications. A major computing trend over the last few decades has been the widening gap between processor speed and main memory speed. As a result, system architectures increasingly use caches and memory hierarchies to avoid memory latency. The access times of different levels of a memory hierarchy typically vary by orders of magnitude. In some cases, the running time of a pro- gram is as much a function of its cache access pattern and efficiency as it is of operation count [Frigo et al. 1999; Sen et al. 2002]. Our goal is to design cache efficient algorithms to process large meshes. The two standard techniques to reduce cache misses are: 1. Computation Reordering: Reorder the computation to im- prove program locality. This is performed using compiler optimizations or application specific hand-tuning. 2. Data Layout Optimization: Compute a cache-coherent layout of the data in memory according to the access pattern. In this paper, we focus on data layout optimization of large meshes to improve cache coherence. A triangle mesh is represented by linear sequences of vertices and triangles. Therefore, the problem becomes one of computing a cache efficient layout of the vertices and triangles. Figure 1: 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 the frame rate by almost ve times. We achieve a throughput of 106M tri/sec (at...

Website: gamma.cs.unc.edu | Filesize: -
No of Page(s): 8
Download Cache-Oblivious Mesh Layouts - Geometric Algorithms for Modeling ....pdf