Simple and Efficient Mesh Layout with Space-Filling Curves
Huy T. Vo, Claudio T. Silva, Luiz F. Scheidegger, Valerio Pascucci · Journal of Graphics Tools · 2012
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 Lin, G. and Yu, T. P. 2006. An Improved Vertex Caching Scheme for 3D Mesh Rendering. IEEE Transactions on Visualization and Computer Graphics, 12: 640–648. [Lin and Yu 06] [Google Scholar], Sander et al. 07 Sander, P. V., Nehab, D. and Barczak, J. Fast Triangle Reordering for Vertex Locality and Reduced Overdraw. ACM Transactions on Graphics, 26:3 [Sander et al. 07] [Google Scholar]].