{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T08:24:03Z","timestamp":1774599843791,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,12,1]],"date-time":"2008-12-01T00:00:00Z","timestamp":1228089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["619008"],"award-info":[{"award-number":["619008"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1409060.1409097","type":"journal-article","created":{"date-parts":[[2008,12,3]],"date-time":"2008-12-03T21:56:04Z","timestamp":1228341364000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Efficient traversal of mesh edges using adjacency primitives"],"prefix":"10.1145","volume":"27","author":[{"given":"Pedro V.","family":"Sander","sequence":"first","affiliation":[{"name":"Hong Kong UST"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diego","family":"Nehab","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eden","family":"Chlamtac","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugues","family":"Hoppe","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,12]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"220","volume-title":"Proceedings of Workshop on Experimental Algorithms, LNCS 5038","author":"Andrade D.","unstructured":"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 . 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."},{"key":"e_1_2_2_2_1","volume-title":"ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH","author":"Assarsson U.","year":"2003","unstructured":"Assarsson , U. and Akenine-M\u00f6ller , 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. 10.1145\/882262.882300 Assarsson, U. and Akenine-M\u00f6ller, 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. 10.1145\/882262.882300"},{"key":"e_1_2_2_3_1","unstructured":"Bahnassi H. and Bahnassi W. 2007. Micro-beveled edges. In ShaderX5: Advanced Rendering Techniques. Charles River Media.  Bahnassi H. and Bahnassi W. 2007. Micro-beveled edges. In ShaderX5: Advanced Rendering Techniques. Charles River Media."},{"key":"e_1_2_2_4_1","volume-title":"ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003","author":"Blythe D.","year":"2006","unstructured":"Blythe , D. 2006 . The Direct3D 10 system . ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003 ), 25(3):724--734. 10.1145\/1179352.1141947 Blythe, D. 2006. The Direct3D 10 system. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003), 25(3):724--734. 10.1145\/1179352.1141947"},{"key":"e_1_2_2_5_1","unstructured":"Brennan C. 2002. Shadow volume extrusion using a vertex shader. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware.  Brennan C. 2002. Shadow volume extrusion using a vertex shader. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware."},{"key":"e_1_2_2_6_1","unstructured":"Card D. and Mitchell J. 2002. Non-photorealistic rendering with pixel and vertex shaders. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware.  Card D. and Mitchell J. 2002. Non-photorealistic rendering with pixel and vertex shaders. In ShaderX: Vertex and Pixel Shader Tips and Tricks. Wordware."},{"key":"e_1_2_2_7_1","first-page":"9","volume-title":"Proceedings of Symposium on Interactive 3D Graphics and Games (I3D)","author":"Chhugani J.","unstructured":"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 . 10.1145\/1230100.1230102 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. 10.1145\/1230100.1230102"},{"key":"e_1_2_2_8_1","first-page":"347","volume-title":"IEEE Visualization","author":"Chow M. M.","year":"1997","unstructured":"Chow , M. M. 1997 . Optimized geometry compression for realtime rendering . In IEEE Visualization , pages 347 -- 354 . Chow, M. M. 1997. Optimized geometry compression for realtime rendering. In IEEE Visualization, pages 347--354."},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1145\/563858.563901","volume-title":"Proceedings of ACM SIGGRAPH 77","author":"Crow F. C.","year":"1977","unstructured":"Crow , F. C. 1977 . Shadow algorithms for computer graphics . In Proceedings of ACM SIGGRAPH 77 , pages 242 -- 248 . 10.1145\/563858.563901 Crow, F. C. 1977. Shadow algorithms for computer graphics. In Proceedings of ACM SIGGRAPH 77, pages 242--248. 10.1145\/563858.563901"},{"key":"e_1_2_2_10_1","volume-title":"ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003","author":"DeCarlo D.","year":"2017","unstructured":"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. 10.1145\/1 2017 75.882354 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. 10.1145\/1201775.882354"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/218380.218391","volume-title":"Proceedings of ACM SIGGRAPH 95","author":"Deering M.","year":"1995","unstructured":"Deering , M. 1995 . Geometry compression . In Proceedings of ACM SIGGRAPH 95 , pages 13 -- 20 . 10.1145\/218380.218391 Deering, M. 1995. Geometry compression. In Proceedings of ACM SIGGRAPH 95, pages 13--20. 10.1145\/218380.218391"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580113"},{"key":"e_1_2_2_13_1","first-page":"254","volume-title":"Proceedings of Symposium on Computational Geometry","author":"Estkowski R.","unstructured":"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 . 10.1145\/513400.513431 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. 10.1145\/513400.513431"},{"key":"e_1_2_2_14_1","first-page":"319","volume-title":"IEEE Visualization","author":"Evans F.","unstructured":"Evans , F. , Skiena , S. , and Varshney , A . 1996. Optimizing triangle strips for fast rendering . In IEEE Visualization , pages 319 -- 326 . Evans, F., Skiena, S., and Varshney, A. 1996. Optimizing triangle strips for fast rendering. In IEEE Visualization, pages 319--326."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_2_17_1","doi-asserted-by":"crossref","unstructured":"Gooch B. and Gooch A. 2001. Non-photorealistic rendering. A. K. Peters Ltd.   Gooch B. and Gooch A. 2001. Non-photorealistic rendering. A. K. Peters Ltd.","DOI":"10.1201\/9781439864173"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-007-9055-x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_2_20_1","first-page":"28","article-title":"Real shadows real time","volume":"18","author":"Heidmann T.","year":"1991","unstructured":"Heidmann , T. 1991 . Real shadows real time . Iris Universe , 18 : 28 -- 31 . Heidmann, T. 1991. Real shadows real time. Iris Universe, 18: 28--31.","journal-title":"Iris Universe"},{"key":"e_1_2_2_21_1","volume-title":"Introduction to 3D Non-Photorealistic Rendering","author":"Hertzmann A.","unstructured":"Hertzmann , A. 1999. Silhouettes and outlines . In Introduction to 3D Non-Photorealistic Rendering , chapter 7. ACM SIGGRAPH Course Notes . Hertzmann, A. 1999. Silhouettes and outlines. In Introduction to 3D Non-Photorealistic Rendering, chapter 7. ACM SIGGRAPH Course Notes."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/311535.311565","volume-title":"Proceedings of ACM SIGGRAPH 99","author":"Hoppe H.","year":"1999","unstructured":"Hoppe , H. 1999 . Optimization of mesh locality for transparent vertex caching . In Proceedings of ACM SIGGRAPH 99 , pages 269 -- 276 . 10.1145\/311535.311565 Hoppe, H. 1999. Optimization of mesh locality for transparent vertex caching. In Proceedings of ACM SIGGRAPH 99, pages 269--276. 10.1145\/311535.311565"},{"key":"e_1_2_2_24_1","volume-title":"METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0.","author":"Karypis G.","year":"1995","unstructured":"Karypis , G. and Kumar , V . 1995 . METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0. Karypis, G. and Kumar, V. 1995. METIS: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 2.0."},{"key":"e_1_2_2_25_1","first-page":"227","volume-title":"Proceedings of Symposium on Interactive 3D Graphics and Games (I3D)","author":"Lengyel J.","unstructured":"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 . 10.1145\/364338.364407 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. 10.1145\/364338.364407"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.59"},{"key":"e_1_2_2_27_1","first-page":"35","volume-title":"Proceedings of Symposium on Non-Photorealistic Animation and Rendering (NPAR)","author":"McGuire M.","unstructured":"McGuire , M. and Hughes , J . 2004. Hardware-determined feature edges . In Proceedings of Symposium on Non-Photorealistic Animation and Rendering (NPAR) , pages 35 -- 47 . 10.1145\/987657.987663 McGuire, M. and Hughes, J. 2004. Hardware-determined feature edges. In Proceedings of Symposium on Non-Photorealistic Animation and Rendering (NPAR), pages 35--47. 10.1145\/987657.987663"},{"key":"e_1_2_2_28_1","unstructured":"Microsoft Corp. 2007. DirectX 10 SDK.  Microsoft Corp. 2007. DirectX 10 SDK ."},{"key":"e_1_2_2_29_1","unstructured":"Rothberg E. 1985. MATHPROG. http:\/\/elib.zib.de\/pub\/Packages\/mathprog\/matching\/weighted.  Rothberg E. 1985. MATHPROG. http:\/\/elib.zib.de\/pub\/Packages\/mathprog\/matching\/weighted."},{"key":"e_1_2_2_30_1","volume-title":"ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH","author":"Sander P. V.","year":"2007","unstructured":"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. 10.1145\/1276377.1276489 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. 10.1145\/1276377.1276489"},{"key":"e_1_2_2_31_1","volume-title":"Technical Report WP-03021-001-v01","author":"Tariq S.","unstructured":"Tariq , S. 2007. Fur (using shells and fins). Technical Report WP-03021-001-v01 , NVIDIA Corp . Tariq, S. 2007. Fur (using shells and fins). Technical Report WP-03021-001-v01, NVIDIA Corp."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01782290"},{"key":"e_1_2_2_33_1","first-page":"71","volume-title":"Proceedings of Symposium on Interactive 3D Graphics and Games (I3D)","author":"Xiang X.","unstructured":"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 . 10.1145\/300523.300531 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. 10.1145\/300523.300531"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1409060.1409097","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1409060.1409097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:29:49Z","timestamp":1750285789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1409060.1409097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,12]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["10.1145\/1409060.1409097"],"URL":"https:\/\/doi.org\/10.1145\/1409060.1409097","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,12]]},"assertion":[{"value":"2008-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}