Efficient traversal of mesh edges using adjacency primitives

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.
• 2: Ulf Assarsson , Tomas Akenine-Möller, A geometry-based soft shadow volume algorithm using graphics hardware, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 3: Bahnassi, H. and Bahnassi, W. 2007. Micro-beveled edges. In ShaderX5: Advanced Rendering Techniques. Charles River Media.
• 4: David Blythe, The Direct3D 10 system, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 5: Brennan, C. 2002. Shadow volume extrusion using a vertex shader. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware.
• 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.
• 7: Jatin Chhugani , Subodh Kumar, Geometry engine optimization: cache friendly compressed representation of geometry, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington [doi>10.1145/1230100.1230102]
• 8: Mike M. Chow, Optimized geometry compression for real-time rendering, Proceedings of the 8th conference on Visualization '97, p.347-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 9: Franklin C. Crow, Shadow algorithms for computer graphics, Proceedings of the 4th annual conference on Computer graphics and interactive techniques, p.242-248, July 20-22, 1977, San Jose, California
• 10: Doug DeCarlo , Adam Finkelstein , Szymon Rusinkiewicz , Anthony Santella, Suggestive contours for conveying shape, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 11: Michael Deering, Geometry compression, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.13-20, September 1995 [doi>10.1145/218380.218391]
• 12: Edmonds, J. and Johnson, E. L. 1973. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88--129.
• 13: Regina Estkowski , Joseph S. B. Mitchell , Xinyu Xiang, Optimal decomposition of polygonal models into triangle strips, Proceedings of the eighteenth annual symposium on Computational geometry, p.254-263, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513431]
• 14: Francine Evans , Steven Skiena , Amitabh Varshney, Optimizing triangle strips for fast rendering, Proceedings of the 7th conference on Visualization '96, p.319-326, October 28-29, 1996, San Francisco, California, United States
• 15: Harold Neil Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs., Stanford University, Stanford, CA, 1974
• 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.
• 17: Bruce Gooch , Amy Gooch, Non-Photorealistic Rendering, A. K. Peters, Ltd., Natick, MA, 2001
• 18: Andrea Grosso , Marco Locatelli , Wayne Pullan, Simple ingredients leading to very efficient heuristics for the maximum clique problem, Journal of Heuristics, v.14 n.6, p.587-612, December 2008 [doi>10.1007/s10732-007-9055-x]
• 19: Hall, P. 1935. On representatives of subsets. Journal of the London Mathematical Society, 10:26--30.
• 20: Heidmann, T. 1991. Real shadows real time. Iris Universe, 18: 28--31.
• 21: Hertzmann, A. 1999. Silhouettes and outlines. In Introduction to 3D Non-Photorealistic Rendering, chapter 7. ACM SIGGRAPH Course Notes.
• 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.
• 23: Hugues Hoppe, Optimization of mesh locality for transparent vertex caching, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.269-276, July 1999 [doi>10.1145/311535.311565]
• 24: Karypis, G. and Kumar, V. 1995. METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0.
• 25: Jerome Lengyel , Emil Praun , Adam Finkelstein , Hugues Hoppe, Real-time fur over arbitrary surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.227-232, March 2001 [doi>10.1145/364338.364407]
• 26: Gang Lin , Thomas P. -Y. Yu, An Improved Vertex Caching Scheme for 3D Mesh Rendering, IEEE Transactions on Visualization and Computer Graphics, v.12 n.4, p.640-648, July 2006 [doi>10.1109/TVCG.2006.59]
• 27: Morgan McGuire , John F. Hughes, Hardware-determined feature edges, Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, June 07-09, 2004, Annecy, France [doi>10.1145/987657.987663]
• 28: Microsoft Corp. 2007. DirectX 10 SDK.
• 29: Rothberg, E. 1985. MATHPROG. http://elib.zib.de/pub/Packages/mathprog/matching/weighted.
• 30: Pedro V. Sander , Diego Nehab , Joshua Barczak, Fast triangle reordering for vertex locality and reduced overdraw, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 31: Tariq, S. 2007. Fur (using shells and fins). Technical Report WP-03021-001-v01, NVIDIA Corp.
• 32: Wloka, M. M. and Zeleznik, R. C. 1996. Interactive real-time motion blur. The Visual Computer, 12(6):283--295.
• 33: Xinyu Xiang , Martin Held , Joseph S. B. Mitchell, Fast and effective stripification of polygonal surface models, Proceedings of the 1999 symposium on Interactive 3D graphics, p.71-78, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300531]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors; Parallel processing
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Design, Performance

Keywords:
programmable geometry shader, real-time rendering, shadow volumes, silhouettes, vertex locality