基于GPU的器官体数据光线投射算法研究
|
摘要
医学图像三维可视化技术为医生提供直观、逼真和具有真实感的三维器官体数据,从而有效的提高诊断效率,帮助医生明确诊断并指导手术,因此已经成为近年来的研究热点。本文在对可视化技术进行研究基础上,围绕国家自然科学基金项目《基于三维统计变形和有限元混合模型的颌骨手术计划和仿真》中的三维医学图像的体重建及体数据可视化展开工作,主要研究内容如下：
1.采用预合成体绘制积分技术分析体绘制原理,对体绘制的光照模型、光学模型和体绘制的加速技术进行了系统研究。重点介绍了三种经典的体绘制算法,并对传统的抛雪球法做了仿真实验。
2.针对传统光线投射算法绘制速度慢、精度差等缺点,提出一种改进的基于GPU编程的光线投射算法。算法采用新的采样合成函数,结合经典的Blinn-Phong光照模型,采用不透明度提前截止判断光线终止,算法使用Cg语言编写顶点程序和片段程序来实现。实验结果表明该算法既可以增强传统光线投射算法的绘制效果,也可以加快算法的速度。
3.针对传统的GPU光线投射算法绘制效果差、效率低等问题,提出一种基于八叉树编码的CUDA光线投射算法。首先,采用八叉树对体数据进行编码,有效地剔除体数据中对重建图像无贡献的部分；其次,将体数据绑定到三维纹理上,根据体数据大小分配线程,每条光线与体数据求交时采用并行计算；最后,在CUDA内核中实现光线投射算法。实验结果证明该算法不仅可以增强传统的GPU光线投射算法的绘制效果,而且可以加快算法的绘制速度。
本文所提出的算法在医生进行辅助检测、术前分析、术中监测等方面提供了良好的可视化工具。
Three-dimensional Visualization technologies of medical images can provide intuitive、distinct and realistic volume data of anatomical structures. They can increase the efficiency of diagnosis effectively, and can help doctors confirm the diagnosis, as well as guide the surgery. Therefore, they have become the hotspot in medical fields in recent years. In this thesis, based on the research on the technologies of visualization, and under grant of the National Natural Science Fund Project "An orthognathic surgical planning and simulation based on 3D statistical deformation and finite element hybrid model", we focus on the subject of Volumeric rendering of 3D medical images. The main contents of this thesis are listed as follows:
1. The principle of volumetric rendering is analyzed by the pre-integral synthesis, and Optical models、Ⅲumination models and the acceleration technique of volumetric rendering have been studied systematically. We introduce three classical algorithms of the volume rendering, and simulate the Splatting algorithm.
2. To improve low sampling and poor sampling efficiency in the traditional ray casting algorithm, an improved ray casting algorithm based on GPU is proposed. The algorithm combines Blinn-Phong illumination model with a new sample synthesis function and early opacity termination condition, which is implemented by vertex programs and fragment programs in Cg language. The experimental results show that the algorithm can not only enhance the visualization effect of traditional ray-casting algorithm, but also accelerate the speed of volumetric rendering.
3. To improve the low efficiency and poor visualization results in the traditional ray casting algorithm based on GPU, an Octree Encoding based ray casting algorithm is proposed in CUDA, First, in this algorithm, the volume data is structured by Octree, which can eliminate a part of voxels that have no contribution to the reconstructed image efficiently. Secondly, the voxels are bound to 3D texture, and the threads are distributed according to the size of Volume data, parallel computing is used when finding out the intersection of each of the light and the volume data. Finally, the ray casting algorithm is implemented in CUDA kernel. The experimental results show that the proposed algorithm can not only enhance the visualization effect of GPU based traditional ray-casting algorithm, but also accelerate the speed of volumetric rendering.
The algorithm proposed in this thesis provide a good visualization tool in helping doctors adjutant detection、pre-operative analysis and intra-operative monitor.
1.采用预合成体绘制积分技术分析体绘制原理,对体绘制的光照模型、光学模型和体绘制的加速技术进行了系统研究。重点介绍了三种经典的体绘制算法,并对传统的抛雪球法做了仿真实验。
2.针对传统光线投射算法绘制速度慢、精度差等缺点,提出一种改进的基于GPU编程的光线投射算法。算法采用新的采样合成函数,结合经典的Blinn-Phong光照模型,采用不透明度提前截止判断光线终止,算法使用Cg语言编写顶点程序和片段程序来实现。实验结果表明该算法既可以增强传统光线投射算法的绘制效果,也可以加快算法的速度。
3.针对传统的GPU光线投射算法绘制效果差、效率低等问题,提出一种基于八叉树编码的CUDA光线投射算法。首先,采用八叉树对体数据进行编码,有效地剔除体数据中对重建图像无贡献的部分；其次,将体数据绑定到三维纹理上,根据体数据大小分配线程,每条光线与体数据求交时采用并行计算；最后,在CUDA内核中实现光线投射算法。实验结果证明该算法不仅可以增强传统的GPU光线投射算法的绘制效果,而且可以加快算法的绘制速度。
本文所提出的算法在医生进行辅助检测、术前分析、术中监测等方面提供了良好的可视化工具。
Three-dimensional Visualization technologies of medical images can provide intuitive、distinct and realistic volume data of anatomical structures. They can increase the efficiency of diagnosis effectively, and can help doctors confirm the diagnosis, as well as guide the surgery. Therefore, they have become the hotspot in medical fields in recent years. In this thesis, based on the research on the technologies of visualization, and under grant of the National Natural Science Fund Project "An orthognathic surgical planning and simulation based on 3D statistical deformation and finite element hybrid model", we focus on the subject of Volumeric rendering of 3D medical images. The main contents of this thesis are listed as follows:
1. The principle of volumetric rendering is analyzed by the pre-integral synthesis, and Optical models、Ⅲumination models and the acceleration technique of volumetric rendering have been studied systematically. We introduce three classical algorithms of the volume rendering, and simulate the Splatting algorithm.
2. To improve low sampling and poor sampling efficiency in the traditional ray casting algorithm, an improved ray casting algorithm based on GPU is proposed. The algorithm combines Blinn-Phong illumination model with a new sample synthesis function and early opacity termination condition, which is implemented by vertex programs and fragment programs in Cg language. The experimental results show that the algorithm can not only enhance the visualization effect of traditional ray-casting algorithm, but also accelerate the speed of volumetric rendering.
3. To improve the low efficiency and poor visualization results in the traditional ray casting algorithm based on GPU, an Octree Encoding based ray casting algorithm is proposed in CUDA, First, in this algorithm, the volume data is structured by Octree, which can eliminate a part of voxels that have no contribution to the reconstructed image efficiently. Secondly, the voxels are bound to 3D texture, and the threads are distributed according to the size of Volume data, parallel computing is used when finding out the intersection of each of the light and the volume data. Finally, the ray casting algorithm is implemented in CUDA kernel. The experimental results show that the proposed algorithm can not only enhance the visualization effect of GPU based traditional ray-casting algorithm, but also accelerate the speed of volumetric rendering.
The algorithm proposed in this thesis provide a good visualization tool in helping doctors adjutant detection、pre-operative analysis and intra-operative monitor.
引文
*本章研究内容发表于：一种改进的基于GPU编程的光线投射算法.计算机工程与应用.已录用.
[1]唐泽圣,等.三维数据场可视化[M].北京：清华大学出版社,1999
[2]石教英,蔡文立.科学计算可视化算法与系统[M].北京：科学出版社,1996
[3]Keppel E.. Approximating complex surface by triangulation of contour lines[J]. IB-M Journal of research and development,1975,19(1):2-11
[4]Chen G., Herman R., Reynolds A., Udupa J. K.. Surface shading in the cuberille E-nvironment[J].1985,5(12):33-43
[5]Lorensen W. E., Cline H. E.. MarchingCubes:A High Resolution 3D Surface Const-ruction Algorithm[J]. Computer&Graphics,1987,21(4):163-169
[6]Chen T., Serra L., Ng H.. Surface extraetion:dividing voxels[A]. International Cong-ressSeries[C].2004:225-230
[7]钟少君.基于体绘制的医学三维可视化技术研究[D].福州：福州大学,2006
[8]Levoy MI. Display of surfaces from volume data[A]. IEEE Computer Graphics and Applications[C].1988,8(5):29-37
[9]Westover L. A.. Interactive volume rendering[A]. Proceedings of the Chapel Hill o-n Workshop Volume Visualization[C].1989:9-16
[10]Lacroute P.. Analysis of a parallel volume rendering system based on the shear-w arp factorization[A]. IEEE Transactions of Visualization and Computer Graphics [C].1996,2(3):218-231
[11]康玉之.GPU编程与CG语言之阳春白雪下里巴人[M].2009
[12]WESTOVER L.. Interactive Volume Rendering[A]. ACM.SIGGRAPH Computer G-raphics[C]. New York,1989:9-16.
[13]Mas N., Hnarahan P.. area and volume cohenrenee firefficient visualization of 3D Scalarfunctions[J]. Computer&Graphics,1990,24(5):27-33
[14]Doi A., Koide A.. An Efficient Method of Triangularing Equi-Valued Surfaces by Using Tetrahedral Cells[A]. IEEE Transactions[C].1991,74(1):214-224
[15]张浩,李利军,林岚.GPU的通用计算研究[J].计算机与数字工程,2005,33(12)：60-61
[16]Krueger J., Westermann R.. Acceleration techniques for GPU-based volume render-ing[A]. Proceedings of IEEE Visualization[C]. Seattle,2003:38-45
[17]宋涛,欧宗瑛,王瑜等.八叉树编码体数据的快速体绘制算法[J].计算机辅助设计与图形学学报,2005,17(9)：1990-1996
[18]Bruckner S., GrEller M. E.. VolumeShop:an interactive system for direct volume illustration[A]. Proceedings of the IEEE Visualization 2005[C]. Minneapolis,2005, 671-678
[19]邹华,高新波,吕新荣.层次包围盒与GPU实现相结合的光线投射算法[J].计算机辅助设计与图形学学报,2009,21(2)：172-178
[20]梁承志,高新波,邹华等.空间跳跃加速的GPU光线投射算法[J].中国图象图形学报,2009,8：1684-1688
[21]张怡,孙济洲,张加万.基于片段的光线投射算法[J].中国图象图形学报,2007,8：1418-1422
[22]Marsalek L., Armin Hauber, Philipp Slusallek. High-speed volume ray casting wi-th CUDA[A]. IEEE/EG Symposium on Interactive Ray Tracing[C].2008:185.
[23]胡英,徐心和.基于光线相关性的快速光线投射算法[J].中国图象图形学报,2004,2：234-240
[24]Schulze J. P., Kraus M., Lang U., et al. Integrating pre-integration into the Shear-Warp algorithm[A]. Proceedings of the 2003 Eurographics/IEEE TVCG Workshop on Volume Graphics[C]. Tokyo:ACM Press,2003:92-118
[25]Markus Hadwiger, Patric Ljung, Christof Rezk Salama, et al. Advanced Illuminati-on Techniques for GPU-Based Volume Raycasting[A]. ACM SIGGRAPH 2009[C]. 2009:70-140
[26]彭群生,鲍虎军,金小刚.计算机真实感图形的算法基础[M].北京：科学出版社,1999：229-245
[27]孙志刚,张加万,孙济洲.一种改进的splatting体绘制方法[J].天津大学学报,2003,36(5)：626-630
[28]Xue D., Crawfis R.. Efficient splatting using moden graphics hardware[J]. Journal of Graphics Tools,2004,8(3):1-21
[29]陈为,夏佳志,张龙等.一种统一的硬件加速自适应EWA Splatting算法[J].计算机学报,2009,32(8)：1571-1581
[30]Laur D., Hanrahan P.. Hierarchical splatting:a progressive refinement algorithm for volume rendering[J]. Computer Graphics,1991,25(4):285-288
[31]胡增海SHEAR-WARP算法的改进[D].山东：山东大学,2009
[32]Songxiang Gu. http://web.cs.wpi.edu/-sxgu/
[33]李彬,田联房,陈萍等.基于Shear-warp的交互式海量数据场体绘制算法[J].计算 机应用与软件,2007,24(9)：145-146
[34]Sweeney J., Mueller K.. Shear-Warp deluxe:the Shear-Warp algorithm revisited [A].Proceedings of the Symposium on Data Visualizati on Barcel ona:Eurograph-ics Association[C].2002:95-104
[35]Schulze J.P., Kraus M., Lang U.. Integrating pre-integration into the Shear-Warp a-lgorithm[A]. Proceedings of the 2003 Eurographics/IEEE TVCG Workshop on Vo-lume Graphics[C].2003:92-118
[36]任继成,袁晓君,李华等.基于动态数据分布的并行Shear-Warp体绘制算法[J].计算机辅助设计与图形学学报,2000,12(4)：241-244
[37]Meagher D. J.. Efficient synthetic image generation of arbitrary 3-Dobjects[A]. Pr-oceedings of the IEEE Conference on Pattern Recognition and Image Processing [C].1982:473-478
[38]Kreylos Oliver, Weber, Gunther H.. Remote interactive direct volume rendering of AMR data[C]. http://escholarship.org/uc/item/5c40m75k.
[39]Wei Li, Klaus Mueller, Arie Kaufman. Empty Space Skipping and Occlusion Clip-ping for Texture-based Volume Rendering[A]. Proceedings of the 14th IEEE Visu-alization Conference (VIS'03)[C].2003:317-324
[40]Bruckner S., GrEller M. E. VolumeShop:an interactive system for direct volume i-llust ration[A]. Proceedings of the IEEE Visualization 2005s[C].2005:671-678
[41]NVIDIA CUDA SDK. http://www.nvidia.com/object/cudahome.html
[42]Rezk-Salama C., Kolb A.. Opacity peeling for direct volume rendering[J]. Compu-ter Graphics Forum,2006,25(3):597-606
[43]张尤赛,陈福民.基于纹理映射与光照模型的体绘制加速算法[J].中国图象图形学报,2003,8(9)：1048-2054
[44]Blinn J.. Models of light reflection for computer synthesized pictures[A]. Proceedi-ngs of ACM SIGGRAPH'77[C]. New York,1977:192-198
[45]Blinn J. F. Light reflection functions for simulation of clouds and dusty surfaces [A].Proceedings of SIGGRAPH[C].1982:21-29
[46]Nelson Max. Optical models for direct volume rendering[A]. IEEE Transactions on Visualization and Computer Graphics[C].1995:99-108
[47]Max N.. Light diffusion through clouds and haze[A]. Computer Vision,Graphics, and Image Processing[C].1986:280-292
[48]Stefan Roettger, Stefan Guthe, Daniel Weiskopf. Smart Hardware-Accelerated Volu -me Rendering[A]. IEEE TCVG Symposium on Visualization[C].2003:231-236
[49]Ding Zhongming, Takuma Kawamura, Naohisa Sakamoto, et al. Particle-based mu-ltiple irregular volume rendering on CUDA[J]. Simulation Modelling Practice and Theory,2010,18:1172-1183
[50]NVDIA CUDA programming guide 2.0 beta. NVIDIA,2008
[51]http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm
[52]Roerdink, JOS B.T.M., Westenberg MA. Wavelet-based volume visualization[J]. Ni-euw Archief voor Wiskunde,1999,17(2):149-158
[1]唐泽圣,等.三维数据场可视化[M].北京：清华大学出版社,1999
[2]石教英,蔡文立.科学计算可视化算法与系统[M].北京：科学出版社,1996
[3]Keppel E.. Approximating complex surface by triangulation of contour lines[J]. IB-M Journal of research and development,1975,19(1):2-11
[4]Chen G., Herman R., Reynolds A., Udupa J. K.. Surface shading in the cuberille E-nvironment[J].1985,5(12):33-43
[5]Lorensen W. E., Cline H. E.. MarchingCubes:A High Resolution 3D Surface Const-ruction Algorithm[J]. Computer&Graphics,1987,21(4):163-169
[6]Chen T., Serra L., Ng H.. Surface extraetion:dividing voxels[A]. International Cong-ressSeries[C].2004:225-230
[7]钟少君.基于体绘制的医学三维可视化技术研究[D].福州：福州大学,2006
[8]Levoy MI. Display of surfaces from volume data[A]. IEEE Computer Graphics and Applications[C].1988,8(5):29-37
[9]Westover L. A.. Interactive volume rendering[A]. Proceedings of the Chapel Hill o-n Workshop Volume Visualization[C].1989:9-16
[10]Lacroute P.. Analysis of a parallel volume rendering system based on the shear-w arp factorization[A]. IEEE Transactions of Visualization and Computer Graphics [C].1996,2(3):218-231
[11]康玉之.GPU编程与CG语言之阳春白雪下里巴人[M].2009
[12]WESTOVER L.. Interactive Volume Rendering[A]. ACM.SIGGRAPH Computer G-raphics[C]. New York,1989:9-16.
[13]Mas N., Hnarahan P.. area and volume cohenrenee firefficient visualization of 3D Scalarfunctions[J]. Computer&Graphics,1990,24(5):27-33
[14]Doi A., Koide A.. An Efficient Method of Triangularing Equi-Valued Surfaces by Using Tetrahedral Cells[A]. IEEE Transactions[C].1991,74(1):214-224
[15]张浩,李利军,林岚.GPU的通用计算研究[J].计算机与数字工程,2005,33(12)：60-61
[16]Krueger J., Westermann R.. Acceleration techniques for GPU-based volume render-ing[A]. Proceedings of IEEE Visualization[C]. Seattle,2003:38-45
[17]宋涛,欧宗瑛,王瑜等.八叉树编码体数据的快速体绘制算法[J].计算机辅助设计与图形学学报,2005,17(9)：1990-1996
[18]Bruckner S., GrEller M. E.. VolumeShop:an interactive system for direct volume illustration[A]. Proceedings of the IEEE Visualization 2005[C]. Minneapolis,2005, 671-678
[19]邹华,高新波,吕新荣.层次包围盒与GPU实现相结合的光线投射算法[J].计算机辅助设计与图形学学报,2009,21(2)：172-178
[20]梁承志,高新波,邹华等.空间跳跃加速的GPU光线投射算法[J].中国图象图形学报,2009,8：1684-1688
[21]张怡,孙济洲,张加万.基于片段的光线投射算法[J].中国图象图形学报,2007,8：1418-1422
[22]Marsalek L., Armin Hauber, Philipp Slusallek. High-speed volume ray casting wi-th CUDA[A]. IEEE/EG Symposium on Interactive Ray Tracing[C].2008:185.
[23]胡英,徐心和.基于光线相关性的快速光线投射算法[J].中国图象图形学报,2004,2：234-240
[24]Schulze J. P., Kraus M., Lang U., et al. Integrating pre-integration into the Shear-Warp algorithm[A]. Proceedings of the 2003 Eurographics/IEEE TVCG Workshop on Volume Graphics[C]. Tokyo:ACM Press,2003:92-118
[25]Markus Hadwiger, Patric Ljung, Christof Rezk Salama, et al. Advanced Illuminati-on Techniques for GPU-Based Volume Raycasting[A]. ACM SIGGRAPH 2009[C]. 2009:70-140
[26]彭群生,鲍虎军,金小刚.计算机真实感图形的算法基础[M].北京：科学出版社,1999：229-245
[27]孙志刚,张加万,孙济洲.一种改进的splatting体绘制方法[J].天津大学学报,2003,36(5)：626-630
[28]Xue D., Crawfis R.. Efficient splatting using moden graphics hardware[J]. Journal of Graphics Tools,2004,8(3):1-21
[29]陈为,夏佳志,张龙等.一种统一的硬件加速自适应EWA Splatting算法[J].计算机学报,2009,32(8)：1571-1581
[30]Laur D., Hanrahan P.. Hierarchical splatting:a progressive refinement algorithm for volume rendering[J]. Computer Graphics,1991,25(4):285-288
[31]胡增海SHEAR-WARP算法的改进[D].山东：山东大学,2009
[32]Songxiang Gu. http://web.cs.wpi.edu/-sxgu/
[33]李彬,田联房,陈萍等.基于Shear-warp的交互式海量数据场体绘制算法[J].计算 机应用与软件,2007,24(9)：145-146
[34]Sweeney J., Mueller K.. Shear-Warp deluxe:the Shear-Warp algorithm revisited [A].Proceedings of the Symposium on Data Visualizati on Barcel ona:Eurograph-ics Association[C].2002:95-104
[35]Schulze J.P., Kraus M., Lang U.. Integrating pre-integration into the Shear-Warp a-lgorithm[A]. Proceedings of the 2003 Eurographics/IEEE TVCG Workshop on Vo-lume Graphics[C].2003:92-118
[36]任继成,袁晓君,李华等.基于动态数据分布的并行Shear-Warp体绘制算法[J].计算机辅助设计与图形学学报,2000,12(4)：241-244
[37]Meagher D. J.. Efficient synthetic image generation of arbitrary 3-Dobjects[A]. Pr-oceedings of the IEEE Conference on Pattern Recognition and Image Processing [C].1982:473-478
[38]Kreylos Oliver, Weber, Gunther H.. Remote interactive direct volume rendering of AMR data[C]. http://escholarship.org/uc/item/5c40m75k.
[39]Wei Li, Klaus Mueller, Arie Kaufman. Empty Space Skipping and Occlusion Clip-ping for Texture-based Volume Rendering[A]. Proceedings of the 14th IEEE Visu-alization Conference (VIS'03)[C].2003:317-324
[40]Bruckner S., GrEller M. E. VolumeShop:an interactive system for direct volume i-llust ration[A]. Proceedings of the IEEE Visualization 2005s[C].2005:671-678
[41]NVIDIA CUDA SDK. http://www.nvidia.com/object/cudahome.html
[42]Rezk-Salama C., Kolb A.. Opacity peeling for direct volume rendering[J]. Compu-ter Graphics Forum,2006,25(3):597-606
[43]张尤赛,陈福民.基于纹理映射与光照模型的体绘制加速算法[J].中国图象图形学报,2003,8(9)：1048-2054
[44]Blinn J.. Models of light reflection for computer synthesized pictures[A]. Proceedi-ngs of ACM SIGGRAPH'77[C]. New York,1977:192-198
[45]Blinn J. F. Light reflection functions for simulation of clouds and dusty surfaces [A].Proceedings of SIGGRAPH[C].1982:21-29
[46]Nelson Max. Optical models for direct volume rendering[A]. IEEE Transactions on Visualization and Computer Graphics[C].1995:99-108
[47]Max N.. Light diffusion through clouds and haze[A]. Computer Vision,Graphics, and Image Processing[C].1986:280-292
[48]Stefan Roettger, Stefan Guthe, Daniel Weiskopf. Smart Hardware-Accelerated Volu -me Rendering[A]. IEEE TCVG Symposium on Visualization[C].2003:231-236
[49]Ding Zhongming, Takuma Kawamura, Naohisa Sakamoto, et al. Particle-based mu-ltiple irregular volume rendering on CUDA[J]. Simulation Modelling Practice and Theory,2010,18:1172-1183
[50]NVDIA CUDA programming guide 2.0 beta. NVIDIA,2008
[51]http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm
[52]Roerdink, JOS B.T.M., Westenberg MA. Wavelet-based volume visualization[J]. Ni-euw Archief voor Wiskunde,1999,17(2):149-158