Simple and Efficient Mesh Layout with Space-Filling Curves

Abstract

We present a simple and efficient algorithm to compute cache-friendly layouts of unstructured geometric data. Coherent mesh layouts minimize cache misses and page faults by laying out vertices, triangles, or tetrahedra in a spatially structured manner. Recently, Yoon et al. have shown that it is possible to construct an optimal cache-oblivious mesh layout (COML) for surface and volume data. However, their approach is based on an NP-Hard optimization problem and is thus very computationally expensive. We present a mesh layout based on space-filling curves that has comparable performance to COML and is orders of magnitude faster to compute. We also discuss extending our algorithm to handle extremely large datasets through an out-of-core approach. Finally, we include an analysis that examines a number of different mesh layouts, highlighting their strengths and weaknesses. Our evaluation indicates that space-filling curve layouts can be an order of magnitude faster and less memory intensive to compute while, in every application, being able to maintain a performance within 5% of the best layout, including those that are specifically tuned for GPU hardware vertex caches [Lin and Yu 06, Sander et al. 07].

Acknowledgments

We would like to thank the Stanford University Computer Graphics Laboratory and XYZ RGB Inc. for the scanned models. We also thank Jason Shepherd for the Rbl and Mito datasets, NASA for the Langley Fighter dataset, and Rob MacLeod at the University of Utah for the Torso dataset. We thank Sung-Eui Yoon, Peter Lindstrom, and Pedro Sander for providing their layout source codes. This work was supported in part by an NVIDIA Fellowship, the National Science Foundation awards CNS-1153503, IIS-1153728, OCI-0904631, OCI-0906379, IIS-1045032, IIS-0844572, CNS-0751152, and CCF-0702817, the U.S. Department of Energy BER and ASCR.