“Fast triangle reordering for vertex locality and reduced overdraw” by Sander, Nehab and Barczak

We present novel algorithms that optimize the order in which triangles are rendered, to improve post-transform vertex cache efficiency as well as for view-independent overdraw reduction. The resulting triangle orders perform on par with previous methods, but are orders magnitude faster to compute.The improvements in processing speed allow us to perform the optimization right after a model is loaded, when more information on the host hardware is available. This allows our vertex cache optimization to often outperform other methods. In fact, our algorithms can even be executed interactively, allowing for re-optimization in case of changes to geometry or topology, which happen often in CAD/CAM applications. We believe that most real-time rendering applications will immediately benefit from these new results.

1. Airey, J. M. 1990. Increasing update rates in the building walk-through system with automatic model-space subdivision and potentially visible set calculations. PhD thesis, UNC-CH. Google ScholarDigital Library
2. Akeley, K., Haeberli, P., and Burns, D. 1990. The tomesh. c program. Available on SGI computers and developers toolbox CD.Google Scholar
3. Arkin, E. M., Held, M., Mitchell, J. S. B., and Skiena, S. 1996. Hamiltonian triangulations for fast rendering. The Visual Computer, 12(9):429–444.Google ScholarCross Ref
4. Bar-Yehuda, R. and Gotsman, C. 1996. Time/space tradeoffs for polygon mesh rendering. ACM Transactions on Graphics, 15 (2): 141–152. Google ScholarDigital Library
5. Belmonte, O., Remolar, I., J. Ribelles, M. C., Rebollo, C., and Fernández, M. 2001. Multiresolution triangle strips. In Proceedings of IASTED VIIP, pages 182–187.Google Scholar
6. Bittner, J., Wimmer, M., and Harald Piringer, W. P. 2004. Coherent hierarchical culling: Hardware occlusion queries made useful. Computer Graphics Forum, 23(3):615–624.Google ScholarCross Ref
7. Blythe, D. 2006. The Direct3D 10 system. ACM Transactions on Graphics (Proc. of ACM SIGGRAPH 2003), 25(3):724–734. Google ScholarDigital Library
8. Bogomjakov, A. and Gotsman, C. 2002. Universal rendering sequences for transparent vertex caching of progressive meshes. Computer Graphics Forum, 21(2):137–148.Google ScholarCross Ref
9. Chow, M. M. 1997. Optimized geometry compression for realtime rendering. In Visualization’97, pages 347–354, 559. Google ScholarDigital Library
10. Deering, M. 1995. Geometry compression. In Proc. of ACM SIGGRAPH 95, pages 13–20. Google ScholarDigital Library
11. Deering, M. F. and Nelson, S. R. 1993. Leo: a system for cost effective 3D shaded graphics. In Proc. of ACM SIGGRAPH 93, pages 101–108. Google ScholarDigital Library
12. Diaz-Gutierrez, P., Bhushan, A., Gopi, M., and Pajarola, R. 2006. Single-strips for fast interactive rendering. The Visual Computer, 22(6):372–386. Google ScholarDigital Library
13. Dillencourt, M. B. 1996. Finding hamiltonian cycles in delaunay triangulations is NP-complete. Discrete Applied Mathematics, 64(3):207–217. Google ScholarDigital Library
14. El-Sana, J. A., Azanli, E., and Varshney, A. 1999. Skip strips: maintaining triangle strips for view-dependent rendering. In Visualization ’99, pages 131–138. Google ScholarDigital Library
15. Estkowski, R., Mitchell, J., and Xi-ang., X. 2002. Optimal decomposition of polygonal models into triangle strips. In SCG, pages 254–263. Google ScholarDigital Library
16. Evans, F., Skiena, S., and Varshney, A. 1996. Optimizing triangle strips for fast rendering. In Visualization ’96, pages 319–326. Google ScholarDigital Library
17. Garey, M. R., Johnson, D. S., and Tarjan, R. E. 1976. The planar hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5(4):704–714.Google ScholarDigital Library
18. Gopi, M. 2004. Controllable single-strip generation for triangulated surfaces. In PG’04, pages 61–69. Google ScholarDigital Library
19. Govindaraju, N. K., Henson, M., Lin, M. C., and Manocha, D. 2005. Interactive visibility ordering and transparency computations among geometric primitives in complex environments. In I3D, pages 49–56. Google ScholarDigital Library
20. Greene, N., Kass, M., and Miller, G. 1993. Hierarchical z-buffer visibility. In Proc. of ACM SIGGRAPH 93, pages 231–238. Google ScholarDigital Library
21. Gumhold, S. and Strasser, W. 1998. Real time compression of triangle mesh connectivity. In Proc. of ACM SIGGRAPH 98, pages 133–140. Google ScholarDigital Library
22. Hillesland, K., A., B. S., D., L., and Manocha. 2002. Fast and simple occlusion culling using hardware-based depth queries. Technical Report TR02-039, Department of Computer Science, UNC-CH.Google Scholar
23. Hoppe, H. 1999. Optimization of mesh locality for transparent vertex caching. In Proc. of ACM SIGGRAPH 99, pages 269–276. Google ScholarDigital Library
24. Lin, G. and Yu, T. P.-Y. 2006. An improved vertex caching scheme for 3d mesh rendering. TVCG, 12(4): 640–648. Google ScholarDigital Library
25. Mitra, T. and Chiueh, T. 1998. A breadth-first approach to efficient mesh traversal. In HWWS’98, pages 31–38. Google ScholarDigital Library
26. Nehab, D., Barczak, J., and Sander, P. V. 2006. Triangle order optimization for graphics hardware computation culling. In I3D, pages 207–211. Google ScholarDigital Library
27. Ramos, J. and Chover, M. 2004. Lodstrips: Level of detail strips. Lecture Notes in Computer Science, 3039:107–114.Google ScholarCross Ref
28. Ribelles, J., López, A., Remolar, I., Belmonte, O., and Chover, M. 2000. Multiresolution modelling of polygonal surface meshes using triangle fans. Lecture Notes in Computer Science, 1953:431–443. Google ScholarDigital Library
29. Ripollés, O., Chover, M., and Ramos, J. F. 2005. Quality strips for models with level of detail. In Proceedings of IASTED VIIP, ACTA Press, pages 268–273.Google Scholar
30. Shafae, M. and Pajarola, R. 2003. Dstrips: Dynamic triangle strips for real-time mesh simplification and rendering. In PG’03, pages 271–280. Google ScholarDigital Library
31. Speckmann, B. and Snoeyink, J. 1997. Easy triangle strips for tin terrain models. In Canadian Conference on Computational Geometry, pages 91–100.Google Scholar
32. Stewart, A. J. 2001. Tunneling for triangle strips in continuous level-of-detail meshes. In Graphics Interface, pages 91–100. Google ScholarDigital Library
33. Taubin, G. and Rossignac, J. 1998. Geometric compression through topological surgery. ACM Transactions on Graphics, 17 (2): 84–115. Google ScholarDigital Library
34. Teller, S. J. and Sequin, C. H. 1991. Visibility preprocessing for interactive walkthroughs. In Proc. of ACM SIGGRAPH 91, pages 61–70. Google ScholarDigital Library
35. Touma, C. and Gotsman, C. 1998. Triangle mesh compression. In Proceedings of Graphics Interface, pages 26–34.Google Scholar
36. Van Kaick, O., da Silva, M., and Pedrini, H. 2004. Efficient generation of triangle strips from triangulated meshes. Journal of WSCG, 12(1–3):475–481.Google Scholar
37. Velho, L., de Figueiredo, L. H., and Gomes, J. 1999. Hierarchical generalized triangle strips. The Visual Computer, 15(1): 21–35.Google ScholarCross Ref
38. Xiang, X., Held, M., and Mitchell, J. S. B. 1999. Fast and effective stripification of polygonal surface models. In Proceedings of the 1999 Symposium on Interactive 3D Graphics, pages 71–78. Google ScholarDigital Library
39. Yoon, S.-E. and Lindstrom, P. 2006. Mesh layouts for block-based caches. TVCG, 12(5):1213–1220. Google ScholarDigital Library
40. Yoon, S.-E., Lindstrom, P., Pascucci, V, and Manocha, D. 2005. Cache-oblivious mesh layouts. ACM Transactions on Graphics (Proc. of ACM SIGGRAPH 2005), 24(3):886–893. Google ScholarDigital Library