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.
Supplemental Material
Available for Download
Supplemental Materials for Depth-presorted triangle lists
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Bavoil, L. and Myers, K. 2008. Order independent transparency with dual depth peeling. NVIDIA whitepaper.Google Scholar
- Berkelaar, M., Eikland, K., and Notebaert, P. 2004. lp_solve 5.5, open source (mixed-integer) linear programming system. Software.Google Scholar
- 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 ScholarDigital Library
- Carpenter, L. 1984. The A-buffer, an antialiased hidden surface method. Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):103--108. Google ScholarDigital Library
- 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 ScholarDigital Library
- Catmull, E. 1974. A Subdivision Algorithm for Computer Display of Curved Surfaces. PhD thesis, Dept. Computer Science. Google ScholarDigital Library
- 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 ScholarDigital Library
- DX10 SDK. 2010. Microsoft Corporation. February 2010 release.Google Scholar
- 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 ScholarDigital Library
- Everitt, C. 2001. Interactive order-independent transparency. NVIDIA whitepaper.Google Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Fukushige, S. and Suzuki, H. 2006. Voronoi diagram depth sorting for polygon visibility ordering. In Proceedings of GRAPHITE '06, 461--467. Google ScholarDigital Library
- Goad, C. 1982. Special purpose automatic programming for hidden surface elimination. Computer Graphics (Proceedings of ACM SIGGRAPH 1982), 16(3):167--178. Google ScholarDigital Library
- 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 Scholar
- Jansen, J. and Bavoil, L. 2010. Fourier opacity mapping. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 165--172. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- Kim, T.-Y. and Neumann, U. 2001. Opacity shadow maps. In Proceedings of the Eurographics Workshop on Rendering Techniques, 177--182. Google ScholarDigital Library
- Laine, S. and Karras, T. 2011. Stratified sampling for stochastic transparency. Computer Graphics Forum (Proceedings of Eurographics Symposium on Rendering 2011), 30(4). Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Mammen, A. 1989. Transparency and antialiasing algorithms implemented with the virtual pixel maps technique. IEEE Computer Graphics and Applications, 9(4):43--55. Google ScholarDigital Library
- 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 ScholarDigital Library
- Meshkin, H. 2007. Sort-independent alpha blending. GDC Talk.Google Scholar
- 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 ScholarDigital Library
- Myers, K. and Bavoil, L. 2007. Stencil routed A-buffer. ACM SIGGRAPH Technical Sketch. Google ScholarDigital Library
- Myers, K. and Bavoil, L. 2007. Stencil routed k-buffer. NVIDIA whitepaper.Google Scholar
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Porter, T. and Duff, T. 1984. Compositing digital images. Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3): 253--259. Google ScholarDigital Library
- Salvi, M., Montgomery, J., and Lefohn, A. 2011. Adaptive transparency. In Proceedings of the ACM Symposium on High Performance Graphics, 119--126. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Skiena, S. S. 2008. The Algorithm Design Manual, chapter 15.2. Springer, 2nd edition. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- Williams, P. L. 1992. Visibility-ordering meshed polyhedra. ACM Transactions on Graphics, 11(2):103--126. Google ScholarDigital Library
- Wittenbrink, C. M. 2001. R-buffer: a pointerless A-buffer hardware architecture. In Proceedings of Graphics Hardware, 73--80. Google ScholarDigital Library
- 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 ScholarDigital Library
- Yuksel, C. and Keyser, J. 2008. Deep opacity maps. Computer Graphics Forum (Proceedings of Eurographics 2008), 27(2):675--680.Google Scholar
Index Terms
Depth-presorted triangle lists
Recommendations
Image-based fast small triangle rasterization
ICAT'06: Proceedings of the 16th international conference on Advances in Artificial Reality and Tele-ExistenceMany 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 ...
Fast indirect illumination using Layered Depth Images
We present a novel hybrid rendering method for diffuse and glossy indirect illumination. A scene is rendered using standard rasterization on a GPU. In a shader, secondary ray queries are used to sample incident light and to compute indirect lighting. We ...
Per-triangle shadow volumes using a view-sample cluster hierarchy
I3D '14: Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and GamesRendering pixel-accurate shadows in scenes lit by a point light-source in real time is still a challenging problem. For scenes of moderate complexity, algorithms based on Shadow Volumes are by far the most efficient in most cases, but traditionally, ...
Comments