“Cache-oblivious mesh layouts” by Yoon, Pascucci, Lindstrom and Manocha

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.

1. Arge, L., Brodal, G., and Fagerberg, R. 2004. Cache oblivious data structures. Handbook on Data Structures and Applications.Google Scholar
2. Bartholdi, J., and Goldsman, P. 2004. Multiresolution indexing of triangulated irregular networks. In IEEE Transaction on Visualization and Computer Graphics, 484–495. Google ScholarDigital Library
3. Bogomjakov, A., and Gotsman, C. 2002. Universal rendering sequences for transparent vertex caching of progressive meshes. In Computer Graphics Forum, 137–148.Google Scholar
4. Cignoni, P., Montani, C., Rocchini, C., and Scopigno, R. 2003. External memory management and simplification of huge meshes. In IEEE Transaction on Visualization and Computer Graphics, 525–537. Google ScholarDigital Library
5. Coleman, S., and McKinley, K. 1995. The size selection using cache organization and data layout. SIGPLAN Conference on Programming Language Design and Implementation, 279–290. Google ScholarDigital Library
6. Corrêa, W. T., Klosowski, J. T., and Silva, C. T. 2003. Visibility-based prefetching for interactive out-of-core rendering. In Proceedings of PVG 2003 (6th IEEE Symposium on Parallel and Large-Data Visualization and Graphics), 1–8. Google ScholarDigital Library
7. Deering, M. F. 1995. Geometry compression. In SIGGRAPH 95 Conference Proceedings, Addison Wesley, R. Cook, Ed., Annual Conference Series, ACM SIGGRAPH, 13–20. held in Los Angeles, California, 06-11 August 1995. Google ScholarDigital Library
8. Diaz, J., Petit, J., and Serna, M. 2002. A survey on graph layout problems. ACM Computing Surveys 34, 313–356. Google ScholarDigital Library
9. Franquesa-Niubo, M., and Brunet, P. 2003. Collision prediction using mktrees. Proc. CEIG, 217–232.Google Scholar
10. Frigo, M., Leiserson, C., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. Symposium on Foundations of Computer Science, 285–297. Google ScholarDigital Library
11. Garey, M. R., Johnson, D., and Stockmeyer, L. 1976. Some simplified np-complete graph problems. Theoretical Computer Science 1, 237–267.Google ScholarCross Ref
12. Gopi, M., and Eppstein, D. 2004. Single-strip triangulation of manifolds with arbitrary topology. In EUROGRAPHICS, 371–379.Google Scholar
13. Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph’96, 171–180. Google ScholarDigital Library
14. Heber, G., Biswas, R., and Gao, G. 2000. Self-avoiding walks over adaptive unstructured grids. In Concurrency: Practice and Experience, 85–109.Google Scholar
15. Hoppe, H. 1999. Optimization of mesh locality for transparent vertex caching. Proc. of ACM SIGGRAPH, 269–276. Google ScholarDigital Library
16. Isenburg, M., and Gumhold, S. 2003. Out-of-core compression for gigantic polygon meshes. In ACM Trans. on Graphics (Proc. of ACM SIGGRAPH), vol. 22, 935–942. Google ScholarDigital Library
17. Isenburg, M., and Lindstrom, P. 2004. Streaming meshes. Tech. Rep. UCRL-CONF-201992, LLNL.Google Scholar
18. Kannan, R., Lovasz, L., and Simonovits, M. 1997. Random walks and an O(n5) time algorithm for volumes of convex sets. Random Structures and Algorithms, 1–50. Google ScholarDigital Library
19. Karni, Z., Bogomjakov, A., and Gotsman, C. 2002. Efficient compression and rendering of multi-resolution meshes. In IEEE Visualization, 347–354. Google ScholarDigital Library
20. Karypis, G., and Kumar, V. 1998. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 96–129. Google ScholarDigital Library
21. Lasserre, J. B., and Zeron, E. S. 2001. A laplace transform algorithm for the volume of a convex polytope. Journal of the ACM, 1126–1140. Google ScholarDigital Library
22. Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
23. Lindstrom, P., and Pascucci, V. 2001. Visualization of large terrains made easy. IEEE Visualization, 363–370. Google ScholarDigital Library
24. Oliker, L., Li, X., Husbands, P., and Biswas, R. 2002. Effects of ordering strategies and programming paradigms on sparse matrix computations. In SIAM Review, 373–393. Google ScholarDigital Library
25. Pascucci, V., and Frank, R. J. 2001. Global static indexing for real-time exploration of very large regular grids. Super Computing, 225–241.Google Scholar
26. Rusinkiewicz, S., and Levoy, M. 2000. Qsplat: A multiresolution point rendering system for large meshes. Proc. of ACM SIGGRAPH, 343–352. Google ScholarDigital Library
27. Sagan, H. 1994. Space-Filling Curves. Springer-Verlag.Google Scholar
28. Sen, S., Chatterjee, S., and Dumir, N. 2002. Towards a theory of cache-efficient algorithms. Journal of the ACM 49, 828–858. Google ScholarDigital Library
29. Silva, C., Chiang, Y.-J., Correa, W., El-Sana, J., and Lindstrom, P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. Visualization’02 Course Notes.Google Scholar
30. van Kreveld, M., van Oostrum, R., Bajaj, C., Pascucci, V., and Schikore, D. R. 1997. Contour trees and small seed sets for isosurface traversal. In Proceedings of the 13th International Annual Symposium on Computational Geometry (SCG-97), ACM Press, New York, 212–220. Google ScholarDigital Library
31. Velho, L., and Gomes, J. D. 1991. Digital halftoning with space filling curves. In Computer Graphics (SIGGRAPH ’91 Proceedings), T. W. Sederberg, Ed., vol. 25, 81–90. Google ScholarDigital Library
32. Vitter, J. 2001. External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 209–271. Google ScholarDigital Library
33. Wilson, A., Larsen, E., Manocha, D., and Lin, M. C. 1999. Partitioning and handling massive models for interactive collision detection. Computer Graphics Forum (Proc. of Eurographics) 18, 3, 319–329.Google ScholarCross Ref
34. Yoon, S.-E., and Manocha, D. 2005. Cache-Oblivious Layouts of Bounding Volume Hierarchies. Tech. rep., University of North Carolina-Chapel Hill.Google Scholar
35. Yoon, S., Salomon, B., Lin, M. C., and Manocha, D. 2004. Fast collision detection between massive models using dynamic simplification. Eurographics Symposium on Geometry Processing, 136–146. Google ScholarDigital Library
36. Yoon, S.-E., Salomon, B., Gayle, R., and Manocha, D. 2004. Quick-VDR: Interactive View-dependent Rendering of Massive Models. IEEE Visualization, 131–138. Google ScholarDigital Library