“Efficient traversal of mesh edges using adjacency primitives”
Conference:
Type(s):
Title:
- Efficient traversal of mesh edges using adjacency primitives
Session/Category Title: Mesh processing
Presenter(s)/Author(s):
Abstract:
Processing of mesh edges lies at the core of many advanced realtime rendering techniques, ranging from shadow and silhouette computations, to motion blur and fur rendering. We present a scheme for efficient traversal of mesh edges that builds on the adjacency primitives and programmable geometry shaders introduced in recent graphics hardware. Our scheme aims to minimize the number of primitives while maximizing SIMD parallelism. These objectives reduce to a set of discrete optimization problems on the dual graph of the mesh, and we develop practical solutions to these graph problems. In addition, we extend two existing vertex cache optimization algorithms to produce cache-efficient traversal orderings for adjacency primitives. We demonstrate significant runtime speedups for several practical real-time rendering algorithms.
References:
1. Andrade, D., Resende, M. G. C., and Werneck, R. 2008. Fast local search for the maximum independent set problem. In Proceedings of Workshop on Experimental Algorithms, LNCS 5038, pages 220–234. Google ScholarDigital Library
2. Assarsson, U. and Akenine-Möller, T. 2003. A geometry-based soft shadow volume algorithm using graphics hardware. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003), 22(3):511–520. Google Scholar
3. Bahnassi, H. and Bahnassi, W. 2007. Micro-beveled edges. In ShaderX5: Advanced Rendering Techniques. Charles River Media.Google Scholar
4. Blythe, D. 2006. The Direct3D 10 system. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003), 25(3):724–734. Google Scholar
5. Brennan, C. 2002. Shadow volume extrusion using a vertex shader. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware.Google Scholar
6. Card, D. and Mitchell, J. 2002. Non-photorealistic rendering with pixel and vertex shaders. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware.Google Scholar
7. Chhugani, J. and Kumar, S. 2007. Geometry engine optimization: cache friendly compressed representation of geometry. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), pages 9–16. Google Scholar
8. Chow, M. M. 1997. Optimized geometry compression for realtime rendering. In IEEE Visualization, pages 347–354. Google Scholar
9. Crow, F. C. 1977. Shadow algorithms for computer graphics. In Proceedings of ACM SIGGRAPH 77, pages 242–248. Google Scholar
10. DeCarlo, D., Finkelstein, A., Rusinkiewicz, S., and Santella, A. 2003. Suggestive contours for conveying shape. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003), 22(3):848–855. Google Scholar
11. Deering, M. 1995. Geometry compression. In Proceedings of ACM SIGGRAPH 95, pages 13–20. Google Scholar
12. Edmonds, J. and Johnson, E. L. 1973. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88–129.Google ScholarDigital Library
13. Estkowski, R., Mitchell, J. S. B., and Xiang, X. 2002. Optimal decomposition of polygonal models into triangle strips. In Proceedings of Symposium on Computational Geometry, pages 254–263. Google Scholar
14. Evans, F., Skiena, S., and Varshney, A. 1996. Optimizing triangle strips for fast rendering. In IEEE Visualization, pages 319–326. Google ScholarDigital Library
15. Gabow, H. N. 1974. Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs. PhD thesis, Stanford University. Google Scholar
16. Garey, M. R. and Johnson, D. S. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826–834.Google ScholarDigital Library
17. Gooch, B. and Gooch, A. 2001. Non-photorealistic rendering. A. K. Peters, Ltd. Google Scholar
18. Grosso, A., Locatelli, M., and Pullan, W. 2007. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics, on-line. Google Scholar
19. Hall, P. 1935. On representatives of subsets. Journal of the London Mathematical Society, 10:26–30.Google ScholarCross Ref
20. Heidmann, T. 1991. Real shadows real time. Iris Universe, 18: 28–31.Google Scholar
21. Hertzmann, A. 1999. Silhouettes and outlines. In Introduction to 3D Non-Photorealistic Rendering, chapter 7. ACM SIGGRAPH Course Notes.Google Scholar
22. Hopcroft, J. E. and Karp, R. M. 1973. An n
5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225–231.Google ScholarCross Ref
23. Hoppe, H. 1999. Optimization of mesh locality for transparent vertex caching. In Proceedings of ACM SIGGRAPH 99, pages 269–276. Google Scholar
24. Karypis, G. and Kumar, V. 1995. METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0.Google Scholar
25. Lengyel, J., Praun, E., Finkelstein, A., and Hoppe, H. 2001. Real-time fur over arbitrary surfaces. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), pages 227–232. Google Scholar
26. Lin, G. and Yu, T. P.-Y. 2006. An improved vertex caching scheme for 3D mesh rendering. IEEE Transactions on Visualization and Computer Graphics, 12(4):640–648. Google ScholarDigital Library
27. McGuire, M. and Hughes, J. 2004. Hardware-determined feature edges. In Proceedings of Symposium on Non-Photorealistic Animation and Rendering (NPAR), pages 35–47. Google Scholar
28. Microsoft Corp. 2007. DirectX 10 SDK.Google Scholar
29. Rothberg, E. 1985. MATHPROG. http://elib.zib.de/pub/Packages/mathprog/matching/weighted.Google Scholar
30. Sander, P. V., Nehab, D., and Barczak, J. 2007. Fast triangle reordering for vertex locality and reduced overdraw. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2007), 26(3):89. Google Scholar
31. Tariq, S. 2007. Fur (using shells and fins). Technical Report WP-03021-001-v01, NVIDIA Corp.Google Scholar
32. Wloka, M. M. and Zeleznik, R. C. 1996. Interactive real-time motion blur. The Visual Computer, 12(6):283–295.Google ScholarCross Ref
33. Xiang, X., Held, M., and Mitchell, J. S. B. 1999. Fast and effective stripification of polygonal surface models. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), pages 71–78. Google Scholar
