Simple and Efficient Mesh Layout with Space-Filling Curves

We present a simple and e cient 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. How- ever, their

approach is based on an NP-Hard optimization problem, and is thus very computationally expensive. We present a mesh layout based on space- lling curves that has comparable performance to COML and is orders of magnitude faster to com- pute. 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 di erent mesh layouts, highlighting their strengths and weaknesses. Our evaluation indicates that space- lling curve layouts can be an order of magni- tude 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 speci cally tuned for GPU hardware vertex caches in [Lin and Yu 06, Sander et al. 07]. © A K Peters, Ltd. 1 1086-7651/06 $0.50 per page i i paper" | 2012/4/5 | 23:05 | page 2 | #2 i i i i i i 2 journal of graphics tools 1. Introduction In the past few years, advances in 3D data acquisition technology, as well as improvements in simulation algorithms, have made very large datasets avail- able to the computer graphics community. Currently, the size of these models can vary from a few tens of thousands to hundreds of millions of polygons. Many challenges arise from this notable increase in size and complexity, and recently much attention has been given to the problem of computing high quality memory layouts for geometric datasets. Such layouts aim to mini- mize the cache miss and page fault penalty incurred by applications. This can be done by de ning a cache coherence metric and then optimizing the layout according to this metric. Yoon et al. [Yoon and Lindstrom 06, Yoon et al. 05] have investigated this problem and proposed a cache-oblivious mesh layout (COML) that generates near optimal results for any cache con gu- ration. One of this work’s major ndings is that by optimizing a dataset’s layout in memory, it is possible to improve the performance of many mesh processing applications without modifying the applications themselves. Our technique is similar to COML in the sense that it can also naturally improve the performance of other applications, but it is based on a space- lling curve approach, and is thus much faster to compute. Space lling curves are well known for their memory coherence character- istics and high spatial locality...

Website: vgc.poly.edu | Filesize: -
No of Page(s): 15
Download Simple and Efficient Mesh Layout with Space-Filling Curves.pdf