实时阴影绘制方法研究及GPU加速
|
摘要
作为增加虚拟场景真实感的关键技术——阴影的实时绘制技术,在三维游戏、动画影视、三维地理信息系统、计算机辅助设计和制造等多方面得到广泛的应用。阴影效果既在真实感图形的生成方面扮演了重要的角色,又在物体位置的判断方面发挥重要的作用,它对于人们理解三维场景的影响非常巨大。但是传统的实现方法中,无论是图像空间算法还是物体空间算法,都由CPU完成图形流水线的所有变换操作计算,算法的性能受到极大的约束,不能保证生成的阴影在物理上的精确性的同时,又保证达到实时绘制的效果。在研究国内外众多论文的基础上,本文对体积阴影生成算法进行改进,结合图像空间轮廓线检测方法,利用GPU加速技术实现阴影实时绘制。主要研究和创新性体现在以下两个方面：
改进了阴影体算法,添加一个二维数组,保存深度测试值和状态向量,这样既解决了传统阴影体算法中Z-PASS和Z-FAIL存在的问题,可以根据场景和视点位置自由选择两种方法,又解决了阴影体算法自身存在的缺陷。同时结合图像空间轮廓线检测算法,可以方便快捷的实现阴影体积的绘制,解决了阴影体积算法不能绘制复杂的大场景。
研究了基于图像空间轮廓线检测阴影绘制算法的GPU加速模型。本文利用GPU的流水线编程处理器和可并行性处理的特性,加速阴影绘制的速度,减少阴影绘制中CPU的负担,解决了传统阴影绘制算法中的实时性难题,从而平衡了阴影绘制的精度和绘制效率之间的矛盾。
As a key technology to increase the realism of the virtual scene----the shadow of the real-time rendering technology, in 3D games, animation, film and television, three-dimensional geographic information systems, computer-aided design and manufacturing and many other fields was widely used. The effect of shadow played an important role in the generation of realistic graphics and determining the location of objects. it had very large effect for people to understand the impact of three-dimensional scene. However, in the realization of the traditional methods, either image space or object space algorithms, all the transformation operation calculation of graphics pipeline were completed by the CPU, so the performance of algorithms was greatly constrained. It could not guarantee the resulting shadows on the physical accuracy, as the same time, guarantee the achievement of real-time rendering results. On the basis of examining a number of papers at home and abroad, we had improved the volume shadow generation algorithm in this paper, combining with image space contour detection methods and using GPU Accelerated technology to deliver real-time shadow rendering. Major research and innovation is reflected in the following two aspects:
We improved shadow volume algorithm, adding a two-dimensional array that save the depth test value and the state vector, then it will solve the traditional shadow volume algorithm, Z-PASS and the Z-FAIL problems, according to the scene and the viewpoint position of free choice of two kinds of methods, at the same time solve their own shortcoming of shadow volume algorithm. Combining with image space contour detection algorithm could be convenient and efficient to achieve a shadow volume rendering, and solve the problem shadow volume algorithm can not solve large and complex scene rendering
We studied the GPU acceleration model based on contour detection image space shadow rendering algorithm. In this paper, we used the pipeline GPU programming processor and processing characteristics of parallelism to accelerate the speed of shadow rendering, to reduce the burden of the CPU in shadow rendering. At the same time, we solved the real-time problem existed in the traditional shadow rendering algorithm. So it could strike a balance between the accuracy and efficiency of shadow rendering.
改进了阴影体算法,添加一个二维数组,保存深度测试值和状态向量,这样既解决了传统阴影体算法中Z-PASS和Z-FAIL存在的问题,可以根据场景和视点位置自由选择两种方法,又解决了阴影体算法自身存在的缺陷。同时结合图像空间轮廓线检测算法,可以方便快捷的实现阴影体积的绘制,解决了阴影体积算法不能绘制复杂的大场景。
研究了基于图像空间轮廓线检测阴影绘制算法的GPU加速模型。本文利用GPU的流水线编程处理器和可并行性处理的特性,加速阴影绘制的速度,减少阴影绘制中CPU的负担,解决了传统阴影绘制算法中的实时性难题,从而平衡了阴影绘制的精度和绘制效率之间的矛盾。
As a key technology to increase the realism of the virtual scene----the shadow of the real-time rendering technology, in 3D games, animation, film and television, three-dimensional geographic information systems, computer-aided design and manufacturing and many other fields was widely used. The effect of shadow played an important role in the generation of realistic graphics and determining the location of objects. it had very large effect for people to understand the impact of three-dimensional scene. However, in the realization of the traditional methods, either image space or object space algorithms, all the transformation operation calculation of graphics pipeline were completed by the CPU, so the performance of algorithms was greatly constrained. It could not guarantee the resulting shadows on the physical accuracy, as the same time, guarantee the achievement of real-time rendering results. On the basis of examining a number of papers at home and abroad, we had improved the volume shadow generation algorithm in this paper, combining with image space contour detection methods and using GPU Accelerated technology to deliver real-time shadow rendering. Major research and innovation is reflected in the following two aspects:
We improved shadow volume algorithm, adding a two-dimensional array that save the depth test value and the state vector, then it will solve the traditional shadow volume algorithm, Z-PASS and the Z-FAIL problems, according to the scene and the viewpoint position of free choice of two kinds of methods, at the same time solve their own shortcoming of shadow volume algorithm. Combining with image space contour detection algorithm could be convenient and efficient to achieve a shadow volume rendering, and solve the problem shadow volume algorithm can not solve large and complex scene rendering
We studied the GPU acceleration model based on contour detection image space shadow rendering algorithm. In this paper, we used the pipeline GPU programming processor and processing characteristics of parallelism to accelerate the speed of shadow rendering, to reduce the burden of the CPU in shadow rendering. At the same time, we solved the real-time problem existed in the traditional shadow rendering algorithm. So it could strike a balance between the accuracy and efficiency of shadow rendering.
引文
1. Woo, A., poulin, P., and Fournier, A.1990. A survey of shadow algorithms. IEEE Computer Graphics and Application 10(6):13-32.
2. Jean-Marc Hasenfratz, Marc Lapierre, Nicolas Holzschuch, and Francois Sillion. A survey of real-time soft shadows algorithms. In Eurographics State-of-the-Art Reports,2003
3. 陈志全,党岗,金士尧.真实感实时绘制技术综述.计算机工程与科学.2006,28(9)：41-44.
4. Reshetov, A., Soupikov, A., and Hurley, J. Multi-level ray tracing algorithm. ACM Trans. Graph.2005,24,3,1176-1185.
5. Thrane, N. and Simonsen, L.O. A comparison of acceleration structures of GPU assisted ray tracing. M. S. thesis, University of Aarhus.2005.
6.宫文,樊养余,张胜超,李胜亮.一种基于光线跟踪的软阴影算法.计算机工程与应用.2008,44(5)：46-48.
7. P Sloan, J Kautz, J Snyder. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. ACM Trans on Graphics, 2002,21(3):527-536.
8.王京,王莉莉,李帅.一种基于GPU的预计算辐射度传递全频阴影算法计算机研究与发展.2006,43(9)：1505-1510.
9.陈彦云,吴恩华,孙家广.可大规模应用的辐射度计算的自动网格化方法.软件学报.1999,10(5)：449-454.
10. Franklin Crow. Shadow algorithms for computer graphics. Computer Graphics (Proc. ACM SIGGRAPH 77), vol.11, no.2,1977:242-248.
11. Tomas Akenine-MOller, Ulf Assarsson Approximate Soft Shadows on Arbitrary Surfaces using Penumbra Wedges. Computer Graphics (Proc. ACM SIGGRAPH 78), vol.12, no.3,1978:270-274.
12. T. Whitted. An Improved Illumination Model for Shaded Display Communication of the ACM, vol.23, no.6,1980:343-349.
13. Timo Aila. Survey of Texture Mapping. IEEE Computer Graphics and Applications, 1986,6(11):56-67.
14.王长波,谢步瀛,彭群生.建筑物阴影的实时模拟.武汉大学学报(工学版).2006,39(4)：122-126.
15.谭同德,许绘香,赵红领,余晓霞.大规模虚拟环境中实时阴影生成技术.计算机应用.2008,28(7)：1717-1720.
16. Stamminger, M., and Drettakis, G. 2002. Perspective shadow maps. In Proceedings of SIGGRAPH'02, ACM Press,575-562.
17. Brabec, S., Annen, T., and Seidel, H.-P.2002. Practical shadow mapping. J. Graph. Tools 7,4,9-8.
18. IvicaKoli.2004. Light space perspective shadow maps. In the Eurographics Symposium on Rendering 2004, Eurographics, Eurographics Association.
19.周国民,卢涤非,张其前.一种梯形结构的软阴影锥生成方法,浙江大学学报(理学版).2007,34(6)：628-632.
20. Martin, T., and Tan, T.-S. Anti-aliasing and continuity with trapezoidal shadow maps. In the Eurographics Symposium on Rendering 2004, Eurograpics, Eurographics Association.
21. Forsyth,T 2004.Practical Shadows. In Game Developers Conference. http://www. eelpi. gotdns. org/papers/papers.html.
22. Lloyd, B., Yoon, S., Tuft, D., and Manocha, D.2005. Subdivided shadow maps. Tech. rep. TR05-024, University of North Carolina at Chapel Hill.
23. Chan E and Durand F. "An efficient hybrid shadow rendering algorithm ". In Rendering Techniques 2004:15th Eurographics Workshop on Rendering, 2004:.185-196.
24. Lance Williams. Casting curved shadows on curved surfaces. Computer Graphics (Proc. ACM SIGGRAPH 78), vol.12, no.3,1978:270-274..
25. Samuel Homus. Silhouette maps for improved texture magnification. In Graphics Hardware.2004,65-74.
26. Fernando R., Fernandez S, Bala K and Greenberg D. P Adaptive shadow maps. In Proceedings of ACM SIGGRAPH. Computer Graphics Proceedings, Annual Conference Series,2001:387-390.
27. Chong, H. Y., and Gortler S. J A lixel for every pixel, In the Eurographics Symposium on Rendering 2004, Eurographics, Eurographics Association,2004: 167-172.
28. Arvo J Tiled shadow maps. In Proceedings of Computer Graphics International 2004, IEEE Computer Society,2004:240-247.
29. Donnelly, W. and Samuli Laine, A. Variance shadow maps. In Proceedings of ACM SIGGRAPH 2006 Symposium on Interactive 3D Graphics and Games, ACM Press, New York, NY, USA,2006:161-165.
30. Brandon Lloyd, David Tuft, Sung-eui Yoon, and Dinesh Manocha. Warping and partitioning for low error shadow maps. In Proceedings of the Eurographics Symposium on Rendering 2006, Eurographics Association,2006.215-226.
31. Aila T, and Laine S Alias-free shadow maps. In Rendering Techniques 2004: 15th Eurographics Workshop on Rendering,2004:161-166.
32. Gregory S. Johnson, Juhyun Lee, Christopher A. Burns, and William R. Mark. The irregular z-buffer:Hardware acceleration for irregular data structures. ACM Trans. Graph.,24(4):1462-1482,2005.
33.杨兵,战守义,李凤霞,郑福仁.图形硬件加速的实时阴影生成方法.北京理工大学学报.2005,25(7)：594-598.
34.杨兵,李凤霞,战守义,胡敏勇.GPU在复杂场景的阴影绘制中的应用.计算机工程.2006,32(2)：220-222.
35.刘力,马利庄.基于GPU的水底阴影.计算机辅助设计与图形学学报.2008,20(4)：494-498.
36. Krisch, Florian, and Jurgen Dollner. "Real-Time Soft Shadows Using a Single Light Sample [J]". WSCG 11(1), pp.255-262.2003.
37. Reeves, W. T., Salesin, D. H., and Cook, R. L.1987. Rendering antialiased shadow with depth maps. In Proceedings of SIGGRAPH'87, ACM Press,283-291.
38. Lokovic, T., and Veach, E.2000. Deep shadow maos. In Proceedings of SIGGRAPH'00, ACM Press,385-392.
39.刘列明,吴恩华.一种基于点光源的三维阴影的实时生成算法.软件学报.2000,11(6)：785-790.
40. Tadamura, K., Qin, X., Jiao, G, and Nakamae, E.. Rendering optimal solar shadows with plural sunlight depth buffers. The Visual Computer 17,2,2001: 76-90.
41. Govindaraju, N. K., Lloryd, B., Yoon, S.-E., Sud, A., and Manocha, D.. Interactive shadow generation in complex environments. ACM Trans. Graph.22,3,2003: 501-510.
42.吴恩华,柳有权.基于图形处理器的通用计算.计算机辅助设计与图形学报,2004.601-612.
43. Govindaraju N K, Gray J, Kumar R, and Manocha D. "GPUTeraSort:High performance graphics coprocessor sorting for large database management". In proceedings of the 2006 ACM SIGMOD International Conference on Management of Data,2006:325-336.
44.赵乃良,陈艳军,潘志庚.基于数据修正的实时阴影反走样算法.计算机辅助
设计与图形学学报.2006,18(8)：1130-1135.
45. Nguyen Hubert Huu. Casting shadows on volumes. Game Developer,6(3):44 —53,1999.
46. WYMAN, C., AND HANSEN, C.2003. Penumbra maps:Approximate softshadows in real-time. In Euro. Symp. on Rendering,202-207.
47. J. F. Blinn. Jim Blinn'S Comer:Me and my(fake)shadow. IEEE Computer Graphics&Applications,8(1):82-86, January 1988.
48. N. Chin and S. Feiner. Near real—time shadow generation using BSP trees. ACM53山东大学硕士学位论文Computer Graphics,23(3):99-106,1989.
49. Brabec, S., and Seidel, H. P. Single sample soft shadows using depth maps. Graphics hatefface(GI 2002 Proceedings),219—228, May 2002.
50. Kilgard, M. J. (edit00. NVidia OpenGL extension specifications for the CineFXArchitecture(NV30). Nvi 山 a Corporation, August 2002.
51.彭群生,鲍虎军,金小刚.计算机真实感图形的算法基础[M].北京：科学出版社,2002.
52. Mason WOO, Jackie Neider, Tom Davis, Dave Shreiner. OpenGL编程权威指南(第三版)[M].北京：中国电力出版社,2001.
53. M. Berger, Geometry Ⅱ, Springer,1987.
54. Yang Xiao, Jin Yicheng, Yin Yong, Wu Zhuoyu. GPU Based Real—timeShadow Research. Proceedings of the International Conference on ComputerGraphics, Imaging and Visualisation
55. H. G Eggleston, Convexi纱, Cambridge University Press,1958.
56. F. Durand, G Drettakis, and C. Puech, The visibility skeleton:a powerful and efficient multi—purpose global visibility tool, Proceedings of SIGG1 认 PH'97, 1997, PP.89·100.
57. H. Pottmann and J. Wallner, Approximation algorithms for developable surfaces, Computer AidedGeometric Design, v01.16,1999, PP.539-556.
58. C. Soler and F. X. Sillion, Fast calculation of soft shadow textures using convolution, Proceedings ofSIGGRAPH'98,1998, PP.321-332
59. H. Edelsbrunner,Algorithms in Combinatorial Geometry, Monographs onTheoretical Computer Science, Springer—Verlag,1987.
60. W. Wang,B.Joe, and R Goldman, Computing the intersection curve oftwo quadrics based on an analysis of aplane cubic curve, submitted to Graphical Models, Aug., 2000.
2. Jean-Marc Hasenfratz, Marc Lapierre, Nicolas Holzschuch, and Francois Sillion. A survey of real-time soft shadows algorithms. In Eurographics State-of-the-Art Reports,2003
3. 陈志全,党岗,金士尧.真实感实时绘制技术综述.计算机工程与科学.2006,28(9)：41-44.
4. Reshetov, A., Soupikov, A., and Hurley, J. Multi-level ray tracing algorithm. ACM Trans. Graph.2005,24,3,1176-1185.
5. Thrane, N. and Simonsen, L.O. A comparison of acceleration structures of GPU assisted ray tracing. M. S. thesis, University of Aarhus.2005.
6.宫文,樊养余,张胜超,李胜亮.一种基于光线跟踪的软阴影算法.计算机工程与应用.2008,44(5)：46-48.
7. P Sloan, J Kautz, J Snyder. Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments. ACM Trans on Graphics, 2002,21(3):527-536.
8.王京,王莉莉,李帅.一种基于GPU的预计算辐射度传递全频阴影算法计算机研究与发展.2006,43(9)：1505-1510.
9.陈彦云,吴恩华,孙家广.可大规模应用的辐射度计算的自动网格化方法.软件学报.1999,10(5)：449-454.
10. Franklin Crow. Shadow algorithms for computer graphics. Computer Graphics (Proc. ACM SIGGRAPH 77), vol.11, no.2,1977:242-248.
11. Tomas Akenine-MOller, Ulf Assarsson Approximate Soft Shadows on Arbitrary Surfaces using Penumbra Wedges. Computer Graphics (Proc. ACM SIGGRAPH 78), vol.12, no.3,1978:270-274.
12. T. Whitted. An Improved Illumination Model for Shaded Display Communication of the ACM, vol.23, no.6,1980:343-349.
13. Timo Aila. Survey of Texture Mapping. IEEE Computer Graphics and Applications, 1986,6(11):56-67.
14.王长波,谢步瀛,彭群生.建筑物阴影的实时模拟.武汉大学学报(工学版).2006,39(4)：122-126.
15.谭同德,许绘香,赵红领,余晓霞.大规模虚拟环境中实时阴影生成技术.计算机应用.2008,28(7)：1717-1720.
16. Stamminger, M., and Drettakis, G. 2002. Perspective shadow maps. In Proceedings of SIGGRAPH'02, ACM Press,575-562.
17. Brabec, S., Annen, T., and Seidel, H.-P.2002. Practical shadow mapping. J. Graph. Tools 7,4,9-8.
18. IvicaKoli.2004. Light space perspective shadow maps. In the Eurographics Symposium on Rendering 2004, Eurographics, Eurographics Association.
19.周国民,卢涤非,张其前.一种梯形结构的软阴影锥生成方法,浙江大学学报(理学版).2007,34(6)：628-632.
20. Martin, T., and Tan, T.-S. Anti-aliasing and continuity with trapezoidal shadow maps. In the Eurographics Symposium on Rendering 2004, Eurograpics, Eurographics Association.
21. Forsyth,T 2004.Practical Shadows. In Game Developers Conference. http://www. eelpi. gotdns. org/papers/papers.html.
22. Lloyd, B., Yoon, S., Tuft, D., and Manocha, D.2005. Subdivided shadow maps. Tech. rep. TR05-024, University of North Carolina at Chapel Hill.
23. Chan E and Durand F. "An efficient hybrid shadow rendering algorithm ". In Rendering Techniques 2004:15th Eurographics Workshop on Rendering, 2004:.185-196.
24. Lance Williams. Casting curved shadows on curved surfaces. Computer Graphics (Proc. ACM SIGGRAPH 78), vol.12, no.3,1978:270-274..
25. Samuel Homus. Silhouette maps for improved texture magnification. In Graphics Hardware.2004,65-74.
26. Fernando R., Fernandez S, Bala K and Greenberg D. P Adaptive shadow maps. In Proceedings of ACM SIGGRAPH. Computer Graphics Proceedings, Annual Conference Series,2001:387-390.
27. Chong, H. Y., and Gortler S. J A lixel for every pixel, In the Eurographics Symposium on Rendering 2004, Eurographics, Eurographics Association,2004: 167-172.
28. Arvo J Tiled shadow maps. In Proceedings of Computer Graphics International 2004, IEEE Computer Society,2004:240-247.
29. Donnelly, W. and Samuli Laine, A. Variance shadow maps. In Proceedings of ACM SIGGRAPH 2006 Symposium on Interactive 3D Graphics and Games, ACM Press, New York, NY, USA,2006:161-165.
30. Brandon Lloyd, David Tuft, Sung-eui Yoon, and Dinesh Manocha. Warping and partitioning for low error shadow maps. In Proceedings of the Eurographics Symposium on Rendering 2006, Eurographics Association,2006.215-226.
31. Aila T, and Laine S Alias-free shadow maps. In Rendering Techniques 2004: 15th Eurographics Workshop on Rendering,2004:161-166.
32. Gregory S. Johnson, Juhyun Lee, Christopher A. Burns, and William R. Mark. The irregular z-buffer:Hardware acceleration for irregular data structures. ACM Trans. Graph.,24(4):1462-1482,2005.
33.杨兵,战守义,李凤霞,郑福仁.图形硬件加速的实时阴影生成方法.北京理工大学学报.2005,25(7)：594-598.
34.杨兵,李凤霞,战守义,胡敏勇.GPU在复杂场景的阴影绘制中的应用.计算机工程.2006,32(2)：220-222.
35.刘力,马利庄.基于GPU的水底阴影.计算机辅助设计与图形学学报.2008,20(4)：494-498.
36. Krisch, Florian, and Jurgen Dollner. "Real-Time Soft Shadows Using a Single Light Sample [J]". WSCG 11(1), pp.255-262.2003.
37. Reeves, W. T., Salesin, D. H., and Cook, R. L.1987. Rendering antialiased shadow with depth maps. In Proceedings of SIGGRAPH'87, ACM Press,283-291.
38. Lokovic, T., and Veach, E.2000. Deep shadow maos. In Proceedings of SIGGRAPH'00, ACM Press,385-392.
39.刘列明,吴恩华.一种基于点光源的三维阴影的实时生成算法.软件学报.2000,11(6)：785-790.
40. Tadamura, K., Qin, X., Jiao, G, and Nakamae, E.. Rendering optimal solar shadows with plural sunlight depth buffers. The Visual Computer 17,2,2001: 76-90.
41. Govindaraju, N. K., Lloryd, B., Yoon, S.-E., Sud, A., and Manocha, D.. Interactive shadow generation in complex environments. ACM Trans. Graph.22,3,2003: 501-510.
42.吴恩华,柳有权.基于图形处理器的通用计算.计算机辅助设计与图形学报,2004.601-612.
43. Govindaraju N K, Gray J, Kumar R, and Manocha D. "GPUTeraSort:High performance graphics coprocessor sorting for large database management". In proceedings of the 2006 ACM SIGMOD International Conference on Management of Data,2006:325-336.
44.赵乃良,陈艳军,潘志庚.基于数据修正的实时阴影反走样算法.计算机辅助
设计与图形学学报.2006,18(8)：1130-1135.
45. Nguyen Hubert Huu. Casting shadows on volumes. Game Developer,6(3):44 —53,1999.
46. WYMAN, C., AND HANSEN, C.2003. Penumbra maps:Approximate softshadows in real-time. In Euro. Symp. on Rendering,202-207.
47. J. F. Blinn. Jim Blinn'S Comer:Me and my(fake)shadow. IEEE Computer Graphics&Applications,8(1):82-86, January 1988.
48. N. Chin and S. Feiner. Near real—time shadow generation using BSP trees. ACM53山东大学硕士学位论文Computer Graphics,23(3):99-106,1989.
49. Brabec, S., and Seidel, H. P. Single sample soft shadows using depth maps. Graphics hatefface(GI 2002 Proceedings),219—228, May 2002.
50. Kilgard, M. J. (edit00. NVidia OpenGL extension specifications for the CineFXArchitecture(NV30). Nvi 山 a Corporation, August 2002.
51.彭群生,鲍虎军,金小刚.计算机真实感图形的算法基础[M].北京：科学出版社,2002.
52. Mason WOO, Jackie Neider, Tom Davis, Dave Shreiner. OpenGL编程权威指南(第三版)[M].北京：中国电力出版社,2001.
53. M. Berger, Geometry Ⅱ, Springer,1987.
54. Yang Xiao, Jin Yicheng, Yin Yong, Wu Zhuoyu. GPU Based Real—timeShadow Research. Proceedings of the International Conference on ComputerGraphics, Imaging and Visualisation
55. H. G Eggleston, Convexi纱, Cambridge University Press,1958.
56. F. Durand, G Drettakis, and C. Puech, The visibility skeleton:a powerful and efficient multi—purpose global visibility tool, Proceedings of SIGG1 认 PH'97, 1997, PP.89·100.
57. H. Pottmann and J. Wallner, Approximation algorithms for developable surfaces, Computer AidedGeometric Design, v01.16,1999, PP.539-556.
58. C. Soler and F. X. Sillion, Fast calculation of soft shadow textures using convolution, Proceedings ofSIGGRAPH'98,1998, PP.321-332
59. H. Edelsbrunner,Algorithms in Combinatorial Geometry, Monographs onTheoretical Computer Science, Springer—Verlag,1987.
60. W. Wang,B.Joe, and R Goldman, Computing the intersection curve oftwo quadrics based on an analysis of aplane cubic curve, submitted to Graphical Models, Aug., 2000.