容積成像 (Volume Rendering) 需要耗費大量計算時間及記憶體, 如何克服這兩大問題來加速繪製是目前一大挑戰。要解決這種龐大資料集的問題, 較常運用的方法便是: 集合一群工作站的力量合力來完成計算工作, 並利用業界標準的平行化技術來達到即時繪製。裁剪-彎曲因子分解法 (Shear-Warp Factorization) 是目前廣泛應用且效率高的容積成像演算法, 已能實現相當高的畫面更新率; 本論文修改其軟體實作版VolPack函式庫, 加入OpenMP及MPI平行化以提高VolPack的繪製速率。實驗方向計有以下三種: 純OpenMP平行化、純MPI平行化以及混合MPI / OpenMP模式的平行化, 並分析、比較這三種平行處理的加速程度。
裁剪-彎曲因子分解法之特性指出: 在裁剪體積上的voxel資料與影像平面上的像素資料皆以掃描線順序對齊排列, 這代表體積與影像資料結構可以同時間以掃描線順序來瀏覽。基於這種特性, 以掃描線為基礎的一致性 (coherence) 資料結構便可直接派上用場, 例如: 連續長度編碼表示法 (Run-Length Encoded Representation; RLE)。這種資料結構包含兩種型態的runs: 透明與不透明, 它允許我們在繪製期間快速跳過透明的voxels, 只需針對不透明部份的體積來進行處理即可。針對RLE這部份, 本研究論文另提出一套改良過的RLE演算法, 可編碼出更少的runs以節省記憶體空間, 且繪製時間亦可得到少許的增速。

Volume Rendering needs to waste a great deal of calculation time and memory, how overcome these two greatest problems to accelerate to design is one big challenge currently. To solve the problem of this kind of huge data set, the method that often make use of most would be: The strength that gathers a group of work stations is cooperated to complete the calculation work. So must lead first can parallel and calculating algorithm, then make use of the parallelism of the industry standard to turn the technique to reach to design immediately. The hybrid MPI / OpenMP mode can provide to gather the environment most high-efficiency parallelism to turn the strategy to the SMP cluster, also allowing in lone SMP environment, making use of two kinds of characteristics of different standards to reach the most high-performance, this is currently in SMP cluster gathering environment a newly arisen program design trend.
Shear-warp factorization is applied currently most extensively and efficiency high algorithm, have already canned carry out the rather high appearance renewal rate; It a characteristic points out: The voxel scan the line and will scan the line method to arrange with the pixel in cutting the physical volume in the image, this represents the physical volume and the image data structure and can browse by scanning the line sequence meantime. According to this kind of characteristic, taking scanning the line as the basal consistency data structure
iii
can be used directly then, for instance, the continuous length codes to indicate the method (the run-length encoded representation). This kind of data structure includes two kinds of runses of types: Transparent and opaque, it allows us to jump the transparent vox quickly during the period of design, only need the physical volume of aiming at the opacity part to carry on the processing then. Aim at RLE this part, this research thesis puts forward another a set of RLE algorithm that improvement leads, can code the less runs with the economical memory space, and design time and also can get to increase fewly soon.

誌謝 i
中文摘要 ii
英文摘要 iii
目錄 v
表目錄 vi
圖目錄 vii
1. 簡介 1
2. 背景知識 3
3. 問題背景 9
3.1 VolPack: 體積繪製函式庫 13
3.2 改善RLE演算法 19
4. 研究結果與效能評估 23
4.1 平行環境 24
4.2 混合MPI / OpenMP模式 25
4.3 實作方法 27
4.4 研究數據 32
5. 結論及未來工作 40
參考文獻 41

[1]Allen Van Gelder, Kawnsik Kim., „Direct Volume Rendering with Shading via Three-Dimensional Textures”, University of California, Santa Cruz
[2]Cameron, G. G. & Undrill, P. E., “Rendering Volumetric Medical Image Data on a SIMD-Architecture Computer”, 1992
[3]Catmull, E. & Smith, A. R., “3D transformations of images in scanline order”, Computer Graphics (SIGGRAPH ’80 Proceedings), Vol. 14, pp. 279-285, 1980
[4]Craig M. Wittenbrink, Kwansik Kim., “Data Dependent Optimizations for Permutation Volume Rendering”, Computer Systems Laboratory, HPL-97-59 (R.1), 1988
[5]Foley, J. D., van Dam, A., Feiner, S. K. & Hughes, J. F., “Computer Graphics: Principles and Practice, second ed.”, Addison-Wesley, New York, 1990
[6]Gabriel Mateescu , “Parallel Computing with OpenMP on Distributed Shared Memory Platforms”, National Research Council Canada, 2002
[7]J. Czernin, “Dual-Modality PET / CT: An Imaging Technology That Changes the Care of Cancer Patients”, Applied Radiology Online, Applied Imaging, Application in PET, Vol. 1 No. 2, November 2002
[8]J. Hoeflinger, “A Performance Comparison of Fortan 90 with MPI and OpenMP on the Origin 2000”, Center for Simulation of Advanced Rockets
[9]J. P. Schulze, R. Niemeier, and U. Lang., “The Perspective Shear-Warp Algorithm in a Virtual Environment”, IEEE Visualization ’01 Proceedings, pp. 207-213, 2001.
[10]John Clyne and John M. Dennis., “Interactive Direct Volume Rendering of Time-Varying Data”, Scientic Computing Division, National Center for Atmospheric Research
[11]Jurgen P. Schulze and Ulrich Lang., “The Parallelization of the Perspective Shear-Warp Volume Rendering Algorithm”, High Performance Computing Center Stuttgart (HLRS), Germany, 2002.
[12]Laur, D. & Hanraham, P., “Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering”, Computer Graphics, 1991
[13]Levoy, M., “Display of surfaces from volume data”, IEEE Computer Graphics & Applications 8(3): 29-37, 1988
[14]Lorna Smith and Mark Bull, “Development of Mixed Mode MPI / OpenMP Applications”, University of Edinburgh, 2001
[15]M. Amin, A. Grama, and V. Singh, “Fast Volume Rendering using an Efficient, Scalable Parallel Formulation of the Shear-Warp Algorithm”, Proc. 1995 Symposium on Parallel Rendering, pp. 7-14
[16]Nieh, J. & Levoy, M., “Volume Rendering on Scalable Shared-Memory MIMD Architecture”, 1992
[17]Novins, K. L., Sillion, F. X. & Greenberg, D. P., “An Efficient Method for Volume Rendering Using Perspective Projection”, Computer Graphics, 1990
[18]OpenMP Architecture Review Board. “OpenMP C and C++ Application Program Interface”, Version 2.0, March 2002
[19]P. Lacroute and M. Levoy, “Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation”, Proc. SIGGRAPH ’94, Orlando, Florida, July 24-29, 1994
[20]P. Lacroute, “Real-time volume rendering on shared memory multiprocessors using the Shear-Warp factorization”, Proc. 1995 Parallel Rendering Symposium, ACM
[21]Philippe G. Lacroute, “Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation”, Computer Systems Laboratory, Stanford University, 1995
[22]R. Drebin, L. Carpenter, P. Hanrahan, Volume Rendering, Proc. SIGGRAPH ’88, pp. 65-74
[23]Roger Crawfix, Nelson Max, Barry Becker, Brian Cabral., “Volume Rendering of 3D Scalar and Vector Fields at LLNL”
[24]Stander, B. T. & Hart, J. C., “A Lipschitz method for accelerated volume Rendering”, Symposium on Volume Visualiztion, 1994
[25]Upson, C. & Keeler, M., V-BUFFER, “Visible volume rendering”, Computer Graphics (SIGGRAPH ’88 Proceedings), Vol. 22, Atlanta, pp. 59-64, 1988
[26]Westover, L., “Footprint evaluation for volume rendering”, Computer Graphics (SIGGRAPH ’90 Proceedings), Vol. 24, Dallas, pp. 367-376, 1990
[27]Westover, L., “Interactive Volume Rendering”, Chapel Hill Workshop on Volume Visualization, Chapel Hill, NC, pp. 9-16, 1989
[28]Wilhelms, J. & Van Gelder, A., “Octrees for Faster Isosurface Generation”, Computer Graphics, 1990
[29]Yoo, T. S., Neumann, U., Fuchs, “Direct Visualization of Volume Data”, IEEE Computer Graphics & Applications, 1992
[30]Yun He and Chris H.Q. Ding, “MPI and OpenMP Paradigms on Cluster of SMP Architectures: the Vacancy Tracking Algorithm for Multi-Dimensional Array Transposition”, University of California, Berkeley, CA 94720, 2002