research-article

Efficient traversal of mesh edges using adjacency primitives

Authors:

Pedro V. Sander,

Hugues HoppeAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 27, Issue 5

Article No.: 144, Pages 1 - 9

https://doi.org/10.1145/1409060.1409097

Published: 01 December 2008 Publication History

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.

Supplementary Material

JPG File (a144-sander-mp4_hi.jpg)

Download
20.81 KB

MOV File (a144-sander-mp4_hi.mov)

Download
378.98 MB

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.

Digital 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.

[3]

Bahnassi, H. and Bahnassi, W. 2007. Micro-beveled edges. In ShaderX5: Advanced Rendering Techniques. Charles River Media.

[4]

Blythe, D. 2006. The Direct3D 10 system. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003), 25(3):724--734.

[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]

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.

[8]

Chow, M. M. 1997. Optimized geometry compression for realtime rendering. In IEEE Visualization, pages 347--354.

[9]

Crow, F. C. 1977. Shadow algorithms for computer graphics. In Proceedings of ACM SIGGRAPH 77, pages 242--248.

[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.

[11]

Deering, M. 1995. Geometry compression. In Proceedings of ACM SIGGRAPH 95, pages 13--20.

[12]

Edmonds, J. and Johnson, E. L. 1973. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88--129.

Digital 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.

[14]

Evans, F., Skiena, S., and Varshney, A. 1996. Optimizing triangle strips for fast rendering. In IEEE Visualization, pages 319--326.

Digital Library

[15]

Gabow, H. N. 1974. Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs. PhD thesis, Stanford University.

[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.

Digital Library

[17]

Gooch, B. and Gooch, A. 2001. Non-photorealistic rendering. A. K. Peters, Ltd.

[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.

[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.

Digital Library

[23]

Hoppe, H. 1999. Optimization of mesh locality for transparent vertex caching. In Proceedings of ACM SIGGRAPH 99, pages 269--276.

[24]

Karypis, G. and Kumar, V. 1995. METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0.

[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.

[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.

Digital 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.

[28]

Microsoft Corp. 2007. DirectX 10 SDK.

[29]

Rothberg, E. 1985. MATHPROG. http://elib.zib.de/pub/Packages/mathprog/matching/weighted.

[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.

[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]

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.

Cited By

BAI TXIAO M(2024)Exact algorithms for maximum independent set problem on hypergraphsSCIENTIA SINICA Informationis10.1360/SSI-2024-012954:12(2709)Online publication date: 15-Nov-2024
https://doi.org/10.1360/SSI-2024-0129
Großmann ELamm SSchulz CStrash DSilva SPaquete L(2023)Finding Near-Optimal Weight Independent Sets at ScaleProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590353(293-302)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590353
Bhore SLi GNöllenburg M(2022)An Algorithmic Study of Fully Dynamic Independent Sets for Map LabelingACM Journal of Experimental Algorithmics10.1145/351424027(1-36)Online publication date: 7-Jul-2022
https://dl.acm.org/doi/10.1145/3514240
Show More Cited By

Index Terms

Efficient traversal of mesh edges using adjacency primitives
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics processors
    2. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models
  2. Parallel computing methodologies
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Efficient traversal of mesh edges using adjacency primitives
SIGGRAPH Asia '08: ACM SIGGRAPH Asia 2008 papers

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 ...
Tessellation-Independent Smooth Shadow Boundaries

We propose an efficient and light-weight solution for rendering smooth shadow boundaries that do not reveal the tessellation of the shadow-casting geometry. Our algorithm reconstructs the smooth contours of the underlying mesh and then extrudes shadow ...
Dynamic stylized shading primitives
NPAR '11: Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Non-Photorealistic Animation and Rendering

Shading appearance in illustrations, comics and graphic novels is designed to convey illumination, material and surface shape characteristics at once. Moreover, shading may vary depending on different configurations of surface distance, lighting, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 27, Issue 5

December 2008

552 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1409060

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2008

Published in TOG Volume 27, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Research Grants Council, University Grants Committee, Hong Kong

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
1,284
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

BAI TXIAO M(2024)Exact algorithms for maximum independent set problem on hypergraphsSCIENTIA SINICA Informationis10.1360/SSI-2024-012954:12(2709)Online publication date: 15-Nov-2024
https://doi.org/10.1360/SSI-2024-0129
Großmann ELamm SSchulz CStrash DSilva SPaquete L(2023)Finding Near-Optimal Weight Independent Sets at ScaleProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590353(293-302)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590353
Bhore SLi GNöllenburg M(2022)An Algorithmic Study of Fully Dynamic Independent Sets for Map LabelingACM Journal of Experimental Algorithmics10.1145/351424027(1-36)Online publication date: 7-Jul-2022
https://dl.acm.org/doi/10.1145/3514240
Alkhouri IAtia GVelasquez A(2022)A Differentiable Approach to the Maximum Independent Set Problem Using Graph-Based Neural Network Structures2022 IEEE 32nd International Workshop on Machine Learning for Signal Processing (MLSP)10.1109/MLSP55214.2022.9943476(1-6)Online publication date: 22-Aug-2022
https://doi.org/10.1109/MLSP55214.2022.9943476
Xu PBenvenuti D(2022)Towards Rendering the Style of 20th Century Cartoon Line Art in 3D Real-TimeAdvances in Computer Graphics10.1007/978-3-031-23473-6_19(239-251)Online publication date: 12-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-23473-6_19
Mukundan RMukundan R(2022)Mesh Processing Basics3D Mesh Processing and Character Animation10.1007/978-3-030-81354-3_2(5-32)Online publication date: 15-Mar-2022
https://doi.org/10.1007/978-3-030-81354-3_2
Xiao MHuang SZhou YDing B(2021)Efficient Reductions and a Fast Algorithm of Maximum Weighted Independent SetProceedings of the Web Conference 202110.1145/3442381.3450130(3930-3940)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3442381.3450130
Goubier TRakowsky NHarig S(2020)Fast Tsunami Simulations for a Real-Time Emergency Response Flow2020 IEEE/ACM HPC for Urgent Decision Making (UrgentHPC)10.1109/UrgentHPC51945.2020.00008(21-26)Online publication date: Nov-2020
https://doi.org/10.1109/UrgentHPC51945.2020.00008
Hespe DSchulz CStrash D(2019)Scalable Kernelization for Maximum Independent SetsACM Journal of Experimental Algorithmics10.1145/335550224(1-22)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1145/3355502
Nguyen TDahl VBærentzen J(2017)Cache-mesh, a Dynamics Data Structure for Performance OptimizationProcedia Engineering10.1016/j.proeng.2017.09.807203(193-205)Online publication date: 2017
https://doi.org/10.1016/j.proeng.2017.09.807
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents