“Depth-presorted triangle lists”
Conference:
Type(s):
Title:
- Depth-presorted triangle lists
Session/Category Title: GPU's and Rendering
Presenter(s)/Author(s):
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.
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.
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.
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.
4. Bavoil, L. and Myers, K. 2008. Order independent transparency with dual depth peeling. NVIDIA whitepaper.
5. Berkelaar, M., Eikland, K., and Notebaert, P. 2004. lp_solve 5.5, open source (mixed-integer) linear programming system. Software.
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.
7. Carpenter, L. 1984. The A-buffer, an antialiased hidden surface method. Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3):103–108.
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.
9. Catmull, E. 1974. A Subdivision Algorithm for Computer Display of Curved Surfaces. PhD thesis, Dept. Computer Science.
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.
11. DX10 SDK. 2010. Microsoft Corporation. February 2010 release.
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.
13. Everitt, C. 2001. Interactive order-independent transparency. NVIDIA whitepaper.
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.
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.
16. Fukushige, S. and Suzuki, H. 2006. Voronoi diagram depth sorting for polygon visibility ordering. In Proceedings of GRAPHITE ’06, 461–467.
17. Goad, C. 1982. Special purpose automatic programming for hidden surface elimination. Computer Graphics (Proceedings of ACM SIGGRAPH 1982), 16(3):167–178.
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.
19. Jansen, J. and Bavoil, L. 2010. Fourier opacity mapping. In Proceedings of Symposium on Interactive 3D Graphics and Games (I3D), 165–172.
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.
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.
22. Kim, T.-Y. and Neumann, U. 2001. Opacity shadow maps. In Proceedings of the Eurographics Workshop on Rendering Techniques, 177–182.
23. Laine, S. and Karras, T. 2011. Stratified sampling for stochastic transparency. Computer Graphics Forum (Proceedings of Eurographics Symposium on Rendering 2011), 30(4).
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.
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.
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.
27. Mammen, A. 1989. Transparency and antialiasing algorithms implemented with the virtual pixel maps technique. IEEE Computer Graphics and Applications, 9(4):43–55.
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.
29. Meshkin, H. 2007. Sort-independent alpha blending. GDC Talk.
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.
31. Myers, K. and Bavoil, L. 2007. Stencil routed A-buffer. ACM SIGGRAPH Technical Sketch.
32. Myers, K. and Bavoil, L. 2007. Stencil routed k-buffer. NVIDIA whitepaper.
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.
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.
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.
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.
37. Porter, T. and Duff, T. 1984. Compositing digital images. Computer Graphics (Proceedings of ACM SIGGRAPH 1984), 18(3): 253–259.
38. Salvi, M., Montgomery, J., and Lefohn, A. 2011. Adaptive transparency. In Proceedings of the ACM Symposium on High Performance Graphics, 119–126.
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.
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.
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.
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.
43. Skiena, S. S. 2008. The Algorithm Design Manual, chapter 15.2. Springer, 2nd edition.
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.
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.
46. Williams, P. L. 1992. Visibility-ordering meshed polyhedra. ACM Transactions on Graphics, 11(2):103–126.
47. Wittenbrink, C. M. 2001. R-buffer: a pointerless A-buffer hardware architecture. In Proceedings of Graphics Hardware, 73–80.
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.
49. Yuksel, C. and Keyser, J. 2008. Deep opacity maps. Computer Graphics Forum (Proceedings of Eurographics 2008), 27(2):675–680.
