More Web Proxy on the site http://driver.im/

Article

Fast triangle reordering for vertex locality and reduced overdraw

Authors:

Pedro V. Sander,

Joshua BarczakAuthors Info & Claims

SIGGRAPH '07: ACM SIGGRAPH 2007 papers

Pages 89 - es

https://doi.org/10.1145/1275808.1276489

Published: 29 July 2007 Publication History

Abstract

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.

Supplementary Material

JPG File (pps088.jpg)

Download
16.92 KB

MP4 File (pps088.mp4)

Download
34.87 MB

References

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

Digital Library

[2]

Akeley, K., Haeberli, P., and Burns, D. 1990. The tomesh. c program. Available on SGI computers and developers toolbox CD.

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

[4]

Bar-Yehuda, R. and Gotsman, C. 1996. Time/space tradeoffs for polygon mesh rendering. ACM Transactions on Graphics, 15 (2): 141--152.

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

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

[7]

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

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

[9]

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

Digital Library

[10]

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

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

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

Digital Library

[13]

Dillencourt, M. B. 1996. Finding hamiltonian cycles in delaunay triangulations is NP-complete. Discrete Applied Mathematics, 64(3):207--217.

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

Digital Library

[15]

Estkowski, R., Mitchell, J., and Xi-ang., X. 2002. Optimal decomposition of polygonal models into triangle strips. In SCG, pages 254--263.

Digital Library

[16]

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

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

Digital Library

[18]

Gopi, M. 2004. Controllable single-strip generation for triangulated surfaces. In PG'04, pages 61--69.

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

Digital Library

[20]

Greene, N., Kass, M., and Miller, G. 1993. Hierarchical z-buffer visibility. In Proc. of ACM SIGGRAPH 93, pages 231--238.

Digital Library

[21]

Gumhold, S. and Strasser, W. 1998. Real time compression of triangle mesh connectivity. In Proc. of ACM SIGGRAPH 98, pages 133--140.

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

[23]

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

Digital Library

[24]

Lin, G. and Yu, T. P.-Y. 2006. An improved vertex caching scheme for 3d mesh rendering. TVCG, 12(4): 640--648.

Digital Library

[25]

Mitra, T. and Chiueh, T. 1998. A breadth-first approach to efficient mesh traversal. In HWWS'98, pages 31--38.

Digital Library

[26]

Nehab, D., Barczak, J., and Sander, P. V. 2006. Triangle order optimization for graphics hardware computation culling. In I3D, pages 207--211.

Digital Library

[27]

Ramos, J. and Chover, M. 2004. Lodstrips: Level of detail strips. Lecture Notes in Computer Science, 3039:107--114.

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

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

[30]

Shafae, M. and Pajarola, R. 2003. Dstrips: Dynamic triangle strips for real-time mesh simplification and rendering. In PG'03, pages 271--280.

Digital Library

[31]

Speckmann, B. and Snoeyink, J. 1997. Easy triangle strips for tin terrain models. In Canadian Conference on Computational Geometry, pages 91--100.

[32]

Stewart, A. J. 2001. Tunneling for triangle strips in continuous level-of-detail meshes. In Graphics Interface, pages 91--100.

Digital Library

[33]

Taubin, G. and Rossignac, J. 1998. Geometric compression through topological surgery. ACM Transactions on Graphics, 17 (2): 84--115.

Digital Library

[34]

Teller, S. J. and Sequin, C. H. 1991. Visibility preprocessing for interactive walkthroughs. In Proc. of ACM SIGGRAPH 91, pages 61--70.

Digital Library

[35]

Touma, C. and Gotsman, C. 1998. Triangle mesh compression. In Proceedings of Graphics Interface, pages 26--34.

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

[37]

Velho, L., de Figueiredo, L. H., and Gomes, J. 1999. Hierarchical generalized triangle strips. The Visual Computer, 15(1): 21--35.

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

Digital Library

[39]

Yoon, S.-E. and Lindstrom, P. 2006. Mesh layouts for block-based caches. TVCG, 12(5):1213--1220.

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

Digital Library

Cited By

Li CWu BVajda PLin Y(2024)MixRT: Mixed Neural Representations For Real-Time NeRF Rendering2024 International Conference on 3D Vision (3DV)10.1109/3DV62453.2024.00087(1115-1124)Online publication date: 18-Mar-2024
https://doi.org/10.1109/3DV62453.2024.00087
de Lucas EMarcuello PParcerisa JGonzalez A(2019)Visibility Rendering OrderIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286624630:2(473-485)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2866246
Han SSander PWyman CYuksel C(2016)Triangle reordering for reduced overdraw in animated scenesProceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/2856400.2856408(23-27)Online publication date: 27-Feb-2016
https://dl.acm.org/doi/10.1145/2856400.2856408
Show More Cited By

Index Terms

Fast triangle reordering for vertex locality and reduced overdraw

Recommendations

Triangle reordering for reduced overdraw in animated scenes
I3D '16: Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games

We introduce an automatic approach for optimizing the triangle rendering order of animated meshes with the objective of reducing overdraw while maintaining good post-transform vertex cache efficiency. Our approach is based on prior methods designed for ...
Fast triangle reordering for vertex locality and reduced overdraw

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,...
Image-based fast small triangle rasterization
ICAT'06: Proceedings of the 16th international conference on Advances in Artificial Reality and Tele-Existence

Many graphics and visualization applications require fast rendering and animation of fine detailed objects, which are named atomic primitives here. A primitive is a basic graphics shape such as a line or triangle that is directly rasterized into the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '07: ACM SIGGRAPH 2007 papers

August 2007

1019 pages

ISBN:9781450378369

DOI:10.1145/1275808

Conference Chair:
Marc Levoy

Copyright © 2007 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]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGGRAPH07

Sponsor:

SIGGRAPH

SIGGRAPH07: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 5 - 9, 2007

California, San Diego

Acceptance Rates

SIGGRAPH '07 Paper Acceptance Rate 108 of 455 submissions, 24%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
1,475
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li CWu BVajda PLin Y(2024)MixRT: Mixed Neural Representations For Real-Time NeRF Rendering2024 International Conference on 3D Vision (3DV)10.1109/3DV62453.2024.00087(1115-1124)Online publication date: 18-Mar-2024
https://doi.org/10.1109/3DV62453.2024.00087
de Lucas EMarcuello PParcerisa JGonzalez A(2019)Visibility Rendering OrderIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.286624630:2(473-485)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2866246
Han SSander PWyman CYuksel C(2016)Triangle reordering for reduced overdraw in animated scenesProceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/2856400.2856408(23-27)Online publication date: 27-Feb-2016
https://dl.acm.org/doi/10.1145/2856400.2856408
Peng CTimalsena S(2016)Fast mapping and morphing for genus-zero meshes with cross spherical parameterizationComputers and Graphics10.1016/j.cag.2016.06.00159:C(107-118)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.cag.2016.06.001
Lou ZZhang Y(2016)Research of Mesh Layout Algorithm Based on Greedy Optimization StrategyE-Learning and Games10.1007/978-3-319-40259-8_16(182-192)Online publication date: 4-Jun-2016
https://doi.org/10.1007/978-3-319-40259-8_16
Ponchio FDellepiane MJia JHamza-Lup FSchreck T(2015)Fast decompression for web-based view-dependent 3D renderingProceedings of the 20th International Conference on 3D Web Technology10.1145/2775292.2775308(199-207)Online publication date: 18-Jun-2015
https://dl.acm.org/doi/10.1145/2775292.2775308
Rubin ELevy EBarak ABen-Nun T(2014)MAPSACM Transactions on Architecture and Code Optimization10.1145/268054411:4(1-22)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.1145/2680544
Jiang SSajadi BGopi M(2013)Single-Seek Data Layout for Walkthrough ApplicationsProceedings of the 2013 XXVI Conference on Graphics, Patterns and Images10.1109/SIBGRAPI.2013.44(266-273)Online publication date: 5-Aug-2013
https://dl.acm.org/doi/10.1109/SIBGRAPI.2013.44
Athanasiadis TFudos I(2011)SMI 2011Computers and Graphics10.1016/j.cag.2011.03.02235:3(569-579)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.cag.2011.03.022
Yoon SLindstrom P(2007)Random-Accessible Compressed Triangle MeshesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2007.7058513:6(1536-1543)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1109/TVCG.2007.70585

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents