skip to main content
research-article

Depth-presorted triangle lists

Published:01 November 2012Publication History
Skip Abstract Section

Abstract

We present a novel approach for real-time rendering of static 3D models front-to-back or back-to-front relative to any viewpoint outside its bounding volume. The approach renders depth-sorted triangles using a single draw-call. At run-time, we replace the traditional sorting strategy of existing algorithms with a faster triangle selection strategy. The selection process operates on an extended sequence of triangles annotated by test planes, created by our off-line preprocessing stage. Based on these test planes, a simple run-time procedure uses the given viewpoint to select a subsequence of triangles for rasterization. Selected subsequences are statically presorted by depth and contain each input triangle exactly once. Our method runs on legacy hardware and renders depth-sorted static models significantly faster than previous approaches. We conclude demonstrating the real-time rendering of order-independent transparency effects.

Skip Supplemental Material Section

Supplemental Material

References

  1. Aila, T., Miettinen, V., and Nordlund, P. 2003. Delay streams for graphics hardware. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2003), 22(3):792--800. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 22(4):469--483. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Bavoil, L., Callahan, S. P., Lefohn, A., Comba, J. L. D., and Silva, C. T. 2007. Multi-fragment effects on the GPU using the k-buffer. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 94--104. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Bavoil, L. and Myers, K. 2008. Order independent transparency with dual depth peeling. NVIDIA whitepaper.Google ScholarGoogle Scholar
  5. Berkelaar, M., Eikland, K., and Notebaert, P. 2004. lp_solve 5.5, open source (mixed-integer) linear programming system. Software.Google ScholarGoogle Scholar
  6. Callahan, S. P., Ikits, M., Comba, J. L. D., and Silva, C. T. 2005. Hardware-assisted visibility sorting for unstructured volume rendering. IEEE Transactions on Visualization and Computer Graphics, 11(3):285--295. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Carpenter, L. 1984. The A-buffer, an antialiased hidden surface method. Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):103--108. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Carr, N., Měch, R., and Miller, G. 2008. Coherent layer peeling for transparent high-depth-complexity scenes. In Proceedings of Graphics Hardware, 33--40. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Catmull, E. 1974. A Subdivision Algorithm for Computer Display of Curved Surfaces. PhD thesis, Dept. Computer Science. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Chen, H.-M. and Wang, W.-T. 1996. The feudal priority algorithm on hidden-surface removal. In Proceedings of ACM SIGGRAPH 1996, 55--64. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. DX10 SDK. 2010. Microsoft Corporation. February 2010 release.Google ScholarGoogle Scholar
  12. Enderton, E., Sintorn, E., Shirley, P., and Luebke, D. 2010. Stochastic transparency. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 157--164. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Everitt, C. 2001. Interactive order-independent transparency. NVIDIA whitepaper.Google ScholarGoogle Scholar
  14. Foley, J. D., van Dam, A., Feiner, S. K., and Hughes, J. F. 1990. Computer Graphics: Principles and Practice, chapter 16.5.1. Addison-Wesley, 2nd edition. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Fuchs, H., Kedem, Z. M., and Naylor, B. F. 1980. On visible surface generation by a priori tree structures. Computer Graphics (Proceedings of ACM SIGGRAPH 1980), 14(3):124--133. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. Fukushige, S. and Suzuki, H. 2006. Voronoi diagram depth sorting for polygon visibility ordering. In Proceedings of GRAPHITE '06, 461--467. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Goad, C. 1982. Special purpose automatic programming for hidden surface elimination. Computer Graphics (Proceedings of ACM SIGGRAPH 1982), 16(3):167--178. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Huang, M.-C., Liu, F., Liu, X.-H., and Wu, E.-H. 2010. Multi-fragment effects on the GPU using bucket sort. In W. Engel, editor, GPU Pro: Advanced Rendering Techniques, chapter VIII. 1, 495--508. A K Peters.Google ScholarGoogle Scholar
  19. Jansen, J. and Bavoil, L. 2010. Fourier opacity mapping. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 165--172. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Jouppi, N. P. and Chang, C.-F. 1999. Z3: An economical hardware technique for high-quality antialiasing and transparency. In Proceedings of Graphics Hardware, 85--93. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Karp, R. M. 1972. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Proceedings of Symposium on the Complexity of Computer Computations, 85--103.Google ScholarGoogle ScholarCross RefCross Ref
  22. Kim, T.-Y. and Neumann, U. 2001. Opacity shadow maps. In Proceedings of the Eurographics Workshop on Rendering Techniques, 177--182. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Laine, S. and Karras, T. 2011. Stratified sampling for stochastic transparency. Computer Graphics Forum (Proceedings of Eurographics Symposium on Rendering 2011), 30(4). Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Liu, B.-Q., Wei, L.-Y., and Xu, Y.-Q. 2006. Multi-layer depth peeling via fragment sort. Technical Report MSR-TR-2006-81, Microsoft Research Asia.Google ScholarGoogle Scholar
  25. Liu, F., Huang, M.-C., Liu, X.-H., and Wu, E.-H. 2009. Efficient depth peeling via bucket sort. In Proceedings of the ACM Symposium on High Performance Graphics, 51--57. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Liu, F., Huang, M.-C., Liu, X.-H., and Wu, E.-H. 2010. FreePipe: A programmable parallel rendering architecture for efficient multi-fragment effects. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 75--82. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Mammen, A. 1989. Transparency and antialiasing algorithms implemented with the virtual pixel maps technique. IEEE Computer Graphics and Applications, 9(4):43--55. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Mark, W. R. and Proudfoot, K. 2001. The F-buffer: A rasterization-order FIFO buffer for multi-pass rendering. In Proceedings of Graphics Hardware, 57--64. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. Meshkin, H. 2007. Sort-independent alpha blending. GDC Talk.Google ScholarGoogle Scholar
  30. Mulder, J. D., Groen, F. C. A., and van Wijk, J. J. 1998. Pixel masks for screen-door transparency. In Proceedings of Visualization '98, 351--358. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. Myers, K. and Bavoil, L. 2007. Stencil routed A-buffer. ACM SIGGRAPH Technical Sketch. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. Myers, K. and Bavoil, L. 2007. Stencil routed k-buffer. NVIDIA whitepaper.Google ScholarGoogle Scholar
  33. Nehab, D., Barczak, J., and Sander, P. V. 2006. Triangle order optimization for graphics hardware computation culling. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 207--211. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. Newell, M. E., Newell, R. G., and Sancha, T. L. 1972. A new approach to the shaded picture problem. In Proceedings of the ACM National Conference.Google ScholarGoogle Scholar
  35. Paterson, M. S. and Yao, F. F. 1989. Binary partitions with applications to hidden surface removal and solid modelling. In Symposium on Computational Geometry, 23--32. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. Patney, A., Tzeng, S., and Owens, J. D. 2010. Fragment-parallel composite and filter. Computer Graphics Forum (Proceedings of Eurographics Symposium on Rendering 2010), 29(4): 1251--1258. Google ScholarGoogle ScholarDigital LibraryDigital Library
  37. Porter, T. and Duff, T. 1984. Compositing digital images. Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3): 253--259. Google ScholarGoogle ScholarDigital LibraryDigital Library
  38. Salvi, M., Montgomery, J., and Lefohn, A. 2011. Adaptive transparency. In Proceedings of the ACM Symposium on High Performance Graphics, 119--126. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  40. Schumacker, R. A., Brand, B., Gilliland, M. G., and Sharp, W. H. 1969. Study for applying computer-generated images to visual simulation. Technical Report AFHRL-TR-69-14, US Airforce Human Resources Laboratory.Google ScholarGoogle Scholar
  41. Sintorn, E. and Assarsson, U. 2008. Real-time approximate sorting for self shadowing and transparency in hair rendering. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 157--162. Google ScholarGoogle ScholarDigital LibraryDigital Library
  42. Sintorn, E. and Assarsson, U. 2009. Hair self shadowing and transparency depth ordering using occupancy maps. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 67--74. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. Skiena, S. S. 2008. The Algorithm Design Manual, chapter 15.2. Springer, 2nd edition. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. Thibieroz, N. 2008. Robust order-independent transparency via reverse depth peeling in DirectX 10. In W. Engel, editor, ShaderX6: Advanced Rendering Techniques, chapter 3.7, 211--226. Charles River Media.Google ScholarGoogle Scholar
  45. Wexler, D., Gritz, L., Enderton, E., and Rice, J. 2005. GPU-accelerated high-quality hidden surface removal. In Proceedings of Graphics Hardware, 7--14. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. Williams, P. L. 1992. Visibility-ordering meshed polyhedra. ACM Transactions on Graphics, 11(2):103--126. Google ScholarGoogle ScholarDigital LibraryDigital Library
  47. Wittenbrink, C. M. 2001. R-buffer: a pointerless A-buffer hardware architecture. In Proceedings of Graphics Hardware, 73--80. Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. Yang, J. C., Hensley, J., Grün, H., and Thibieroz, N. 2010. Real-time concurrent linked list construction on the GPU. Computer Graphics Forum (Proceedings of Eurographics Symposium on Rendering 2010), 29(4):1297--1304. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. Yuksel, C. and Keyser, J. 2008. Deep opacity maps. Computer Graphics Forum (Proceedings of Eurographics 2008), 27(2):675--680.Google ScholarGoogle Scholar

Index Terms

  1. Depth-presorted triangle lists

          Recommendations

          Comments

          Login options

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

          Sign in

          Full Access

          • Published in

            cover image ACM Transactions on Graphics
            ACM Transactions on Graphics  Volume 31, Issue 6
            November 2012
            794 pages
            ISSN:0730-0301
            EISSN:1557-7368
            DOI:10.1145/2366145
            Issue’s Table of Contents

            Copyright © 2012 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: 1 November 2012
            Published in tog Volume 31, Issue 6

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader