Cache-Oblivious Mesh Layouts

We present a novel method for computing cache-oblivious layouts of large meshes that improve the performance of interactive visual- ization 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 volume 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 modi cation 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. Ef cient algorithms for processing large meshes utilize the com- putational 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 improve 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:...

Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 8
Download Cache-Oblivious Mesh Layouts - Science Reference.pdf