Cache-oblivious mesh layouts
Open Access
- 1 July 2005
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 24 (3) , 886-893
Abstract
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 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 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.Keywords
This publication has 30 references indexed in Scilit:
- Single‐Strip Triangulation of Manifolds with Arbitrary TopologyComputer Graphics Forum, 2004
- Multiresolution indexing of triangulated irregular networksIEEE Transactions on Visualization and Computer Graphics, 2004
- External memory management and simplification of huge meshesIEEE Transactions on Visualization and Computer Graphics, 2003
- Out-of-core compression for gigantic polygon meshesACM Transactions on Graphics, 2003
- Towards a theory of cache-efficient algorithmsJournal of the ACM, 2002
- Universal Rendering Sequences for Transparent Vertex Caching of Progressive MeshesComputer Graphics Forum, 2002
- External memory algorithms and data structuresACM Computing Surveys, 2001
- Partitioning and Handling Massive Models for Interactive Collision DetectionComputer Graphics Forum, 1999
- Digital halftoning with space filling curvesACM SIGGRAPH Computer Graphics, 1991
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976