臺灣博碩士論文加值系統

科學顯像的應用常含有大量資料，用來表示實驗或測量結果的數量或向量函數值，多維度容積資料的顯像有兩種主要的方法，稱為直接容積成像法和等值面法，兩種方法都含有處理大量資料檔，需要大量執行時間，因而妨礙了對談式的應用。在這篇論文中，我們針對容積資料顯像中的資料儲存、傳輸、和成像等問題提出解決的演算法，首先，我們研究 Marching Cubes (MC) 等值面的壓縮問題，並且提出一個幾何壓縮演算法以減少 MC 等值面建立的三角片資料所需的位元數目，我們所提出的演算法將每個三角片頂點依照它所在立方塊的索引、它所在立方塊邊的編號、以及它在邊上的相對位置加以編碼，再者，一個立方塊內各三角片頂點間的連接關係，是以立方塊頂點數值相較於等值面臨界值的正負號加以編碼，然後，我們將這個幾何壓縮演算法擴充到一個以八元樹為基礎的有適應性的降低精度 MC 等值面建構演算法，使用一個八元樹資料結構將多層級立方塊的索引加以編碼，使得三角片數目以及表示一個三角片所需的資料位元數目都同時減少，最後，我們提出一個新的方法以改良一個傳統的以光線投射為基礎的直接容積成像演算法，基本的構想是將一致性的概念納入於光線投射演算法的重新取樣程序，使得耗時的三角函數呼叫與矩陣相乘運算可以顯著地減少。

Applications in scientific visualization often involve extensive data sets, which represent scalar or vector valued functions resulting from experimental measurements. There are two major approaches for visualizing a set of multi-dimensional volume data, namely, the direct volume rendering (DVR) and the isosurface method. However, both approaches involve manipulating a large size of data files and usually require extensive execution time, which may disrupt interactive applications. In this study, we propose algorithms to cope with the storing, transmitting, and rendering problems in visualizing volume data. First, we study the compression problem of Marching Cubes (MC) isosurfaces, and introduce a geometry compression algorithm to reduce the number of bits of generated triangle data. The introduced algorithm encodes each triangle-vertex according to the index of its containing cube, the index of its containing cube-edge, and its relative position on the cube-edge. Furthermore, the connectivity among triangle-vertices in a cube is encoded by the signs of its vertices, computed by comparing their values to the isosurface threshold. Both theoretical analysis and experimental results show that the introduced algorithm can achieve an excellent compression ratio. Then, we extend the geometry compression algorithm to an octree-based adaptive MC algorithm such that both the number of triangles and the number of bits required to represent a triangle can be reduced simultaneously. Finally, we propose a novel approach to improve a ray-casting based DVR algorithm. The basic idea of our approach is to incorporate the notion of coherence in the resampling process so that the time consuming invocations of trigonometric functions and matrix multiplication calculations can be reduced significantly.

封面
摘要
誌謝
目錄
第一章　序論
第二章　壓縮Marching Cubes演算法建構的等值面
第三章　壓縮有適應性的降低精度等值面
第四章　一個改良的光線投射容積顯像演算法
第五章　結論
附錄
Abstract
Contents
List of Figurs
List of Tables
Chapter 1 Introduction
Chapter 2 Compressing isosurfaces generated with marching cubes
2.1 Overveiw
2.2 Encoding schemes and related tables
2.2.1 Cube-index encoding
2.2.2 Edge-index encoding
2.2.3 Vertex-coordinate encoding
2.3 Compression and decompression algorithms
2.3.1 compression algorithm
2.3.2 Decompression algorithm
2.4 Experimental results
2.5 Analysis
2.5.1 Volume size
2.5.2 Time complexity
2.6 Discussion
Chapter 3 Compressing adaptive isosurfaces
3.1 Related work
3.2 Ecoding schemes
3.2.1 Overveiw
3.2.2 Hierarchical cube-indexing
3.2.3 Edge-indexing
3.2.4 Linear-coordinate encoding
3.3 Algorithms
3.3.1 Compression algorithms
3.3.2 Decompression and isosurface reconstruction algorithms
3.4 Experimental results
3.5 Discussion
Chapter 4 An mproved ray-castng algorithm for volume visualization
4.1 Related work
4.2 Overview
4.3 Algorithm
4.3.1 Conventional ray-casting algorithm
4.3.2 The improved algorithm
4.4 Ray step sizes
4.5 Experimental results
4.6 Discussion
4.6.1 Equation derivations for ray step sizes
Chapter 5 Conclusion
Reference

[1] Duff, T. and Porter, T., “Compositing digital images,” Computer Graphics(SIGGRAPH'84 Proceddings), Volume 18, pp.253-259, July 1984.
[2] Levoy, M. , “Display of Surface from Volume Data,” IEEE Computer Graphics and Applications, Volume 8, Number 3, pp.29-37, May 1988.
[3] Levoy, M. , “Volume Rendering, A Hybrid Ray Tracer for Rendering Polygon and Volume Data,” IEEE Computer Graphics and Applications, Volume 10, Number 2, pp.33-40, March 1990.
[4] Levoy, M. , “Efficient Ray Tracing of Volume Data,” ACM Transactions on Graphics, Volume 9, Number 3, pp.245-261, July 1990.
[5] Westtover, L., “Footprint Evaluation for Volume Rendering,” Computer Graphics, Volume 24, Number 4, pp.367-376, August 1990.
[6] Upson, C. and Keeler, M., “V-Buffer: Visible Volume Rendering,” Computer Graphics, Volume 24, Number 4, pp.59-64, August 1988.
[7] Wilhelms, J. and Van Gelder, A., “A Coherent Projection Approach for Direct Volume Rendering,” Computer Graphics, Volume 25, Number 4, pp.275-284, August 1991.
[8] Lorensen, W.E. and Cline, H.E., “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” Proceedings of SIGGRAPH’87 Conference, Volume 21, number 4, pp. 163-169, July 1987.
[9] Schroeder, W.J., Zarge, J.A., and Lorensen, W.E., “Decimation of triangle meshes,” Proceedings of SIGGRAPH’92 Conference, Volume 26, Number 2, pp. 65-70, July 1992.
[10] Dürst M.J., “Letters: Additional Reference to Marching Cubes,” ACM Computer Graphics, Volume 22, number 4, pp. 72-73, July 1988.
[11] Wilhelms, J. and Van Gelder, A., “Octrees for Faster Isosurface Generation,” ACM Transactions on Graphics, Volume 11, Number 3, pp. 201-227, July 1992.
[12] Chuang, J.H. and Lee, W.C., “Efficient generation of isosurfaces in volume rendering,” Computers & Graphics, Vol. 19, No. 6, pp. 805-813, 1995.
[13] Jianping Li, Pan Agathoklis, “An efficiency enhanced isosurface generation algorithm for volume visualization,” The Visual Computer, No. 13, pp. 391-400, 1997.
[14] Cignoni P, Marino P, Montani C, Puppo E, Scopigno R, “Speeding up isosurface extraction using interval trees,” IEEE Transaction on Visualization and Computer Graphics, Vol. 3, No. 2, pp. 158-170, 1997.
[15] Wyvill, B., McPheeters, C. and Wyvill, G., “Data Structure for Soft Objects,” The Visual Computer, Volume 2, Number 4, pp.227-234, August 1986.
[16] Nielson, G.M. and Hamann B., “The Asymptotic Decider: Removing the Ambiguity in Marching Cubes,” Proceedings of IEEE Visualization '91 Conference, San Diego, pp. 83-91, 1991.
[17] Wilhelms J and Van Gelder A, “Topological considerations in isosurface generation,” Extended abstract in ACM Computer Graphics, Volume 24, number 5, pp. 79-86, November 1990.
[18] Wilhelms, J. and Van Gelder, A., “Topological considerations in isosurface generation,” ACM Transactions on Graphics, Volume 13, Number 4, pp. 337-375, October 1994.
[19] Montani C., Scateni R. and Scopigno R., “A modified look-up table for implicit disambiguation of Marching Cubes,” The Visual Computer, Volume 10, Number 6, pp. 353-355, 1994.
[20] Eck M, DeRose T, Duchamp T, Hoppe H, Lounsbery M, Stuetzle W, “Multiresolution analysis of arbitrary meshes,” Proceedings of SIGGRAPH’95 Conference, Vol. 29, pp. 173-182, August 1995.
[21] Heinrich, M. and Michael, S. “Adaptive generation of surface in volume data,” The Visual Computer, pp. 182-199, September 1993.
[22] Hoppe, H. DeRose T. and Duchamp, T., “Mesh optimization,” Proceedings of SIGGRAPH’93 Conference, Vol. 27, pp. 19-26, August 1993.
[23] Hoppe, H, “Progressive meshes,” Proceedings of SIGGRAPH’96 Conference, Vol. 30, pp. 99-108, August 1996.
[24] Montani C., Scateni R., Scopigno R., “Discretized marching cubes,” Proceedings of IEEE Visualization’94 Conference, pp. 281-287, 1994.
[25] Shekhar R., Fayyad E., Yagel R., and Cornhill J. F., “Octree-based decimation of marching cubes surfaces,” Proceedings of IEEE Visualization '96 conference, October 1996, pp. 335-342
[26] Monhan S, Kankanhalli Renben Shu, Chen Zhou, “Adaptive marching cubes,” The Visual Computer, 11:202-217, 1995.
[27] Tim Poston, Tien-Tsin Wong, Pheng-Ann Heng, "Multiresolution Isosurface Extraction with Adaptive Skeleton Climbing," Proceedings of EUROGRAPHICS’98 conference, Volume 17, Number 3, pp. C137-C-146, 1998.
[28] Deering M, "Geometry compression," Proceedings of SIGGRAPH’95 Conference, Los Angeles, California, Vol 29, pp. 13-20, 1995.
[29] Chow MM, "Optimized geometric compression for real-time rendering," Proceedings of IEEE Visualization’97 Conference, 1997.
[30] Gumhold S, Straßer W, " Real time compression of triangle mesh connectivity," Proceedings of SIGGRAPH’98 Conference, Orlando, Florida, pp. 133-140, 1998.
[31] Taubin G, Rossignac J, "Geometrical compression through topological surgery," ACM Transactions on Graphics, Volume 17, pp. 84-115, 1998.
[32] Li JK, Kuo CCJ, "A dual graph approach to 3D triangular mesh compression," University of Southern California, Los Angeles, 1999.
[33] Turk, G., “Re-tiling polygonal surface,” Proceedings of SIGGRAPH’92 Conference, Volume 26, Number 2, pp.55-64, July 1992.
[34] James D. Foley, Andries van Dam, Steven K. Feiner and John F. Hughes “Computer Graphics Principles and Practice,” second edition, pp. 217-222, 1990.
[35] Lacroute, P., “Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation,” Computer Graphics Proc., Ann. Conf. Series (SIGGRAPH ’94), pp. 451-458, Orlando, Florida, July 1994.
[36] Insung Ihm and Rae Kyoung Lee “Indexing Data Structures for Faster Volume Rendering,” Computers & Graphics, VOL. 21, No. 4, pp.497-506, 1997.
[37] Lacroute, P., “Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation,” PhD dissertation, Stanford Univ., 1995.
[38] Lacroute, P., “Analysis of a Parallel Volume Rendering System Based on the Shear-Warp Factorization,” IEEE Transaction on Visualization and Computer Graphics, vol2, no. 3, pp. 218-231, September 1996.
[39] Serge Lang “Linear Algebra,” second edition, pp. 118-129, 1970.
[40] Serge Lang “Linear Algebra,” second edition, pp. 69-74, 1970.
[41] Cignoni P., Ganovelli F., Montani C., Scopigno R., “Reconstruction of topologically correct and adaptive trilinear isosurfaces,” Computers & Graphics 2000; 24(3):399-418.
[42] Cohen J., Olano M., Manocha D., “Appearance-Preserving Simplification,” Proceedings of SIGGRAPH’98, Orlando, Florida, July 1998; 32:115-122.
[43] Crosnier A., Rossignac J., “Tribox bounds for three-dimensional objects,” Computers & Graphics 1999;23(3):429-437.
[44] Garland M., Heckbert P.S., “Surface Simplification Using Quadric Error Metrics,” Proceedings of SIGGRAPH’97, Los Angeles, California 1997; Volume 31.
[45] Popović J., Hoppe H., “Progressive Simplicial Complexes,” Proceedings of SIGGRAPH’97, Los Angeles, California 1997; Volume 31.
[46] Ronfard R., Rossignac J., “Full-range approximations of triangulated polyhedra,” Proceedings of Eurographics'96, Computer Graphics Forum 1996;15(3):C-67-C-76.
[47] Rossignac J., Borrel P., “Multi-resolution 3D approximations for rendering complex scenes,” Geometric Modeling in Computer Graphics, Springer Verlag, Eds. B. Falcidieno and T.L. Kunii, Genova, Italy, 1993;455-465.
[48] Cignoni P., Montani C., Scopigno R., “A comparison of mesh simplification algorithms,” Computers and Graphics 1998;22(1):37-54.
[49] King D., Rossignac J., Szymczak A., “An Edgebreaker-based efficient compression scheme for regular meshes,” The 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, August 16-19, 2000.
[50] King D., Rossignac J., “Optimal Bit Allocation in Compressed 3D Models,” Journal of Computational Geometry, Theory and Applications 1999;14(Issue 1-3):91-118.
[51] King D., Rossignac J., “Guaranteed 3.67V bit encoding of planar triangle graphs,” The 11th Canadian Conference on Computational Geometry (CCCG99), Vancouver, CA, 1999:146-149.
[52] Pajarola R., Rossignac J., “Squeeze: Fast and Progressive Decompression of Triangle Meshes,” Computer Graphics International conference, Switzerland, June 2000.
[53] Taubin G., Guéziec A., Horn W., Lazarus F., “Progressive Forest Split Compression,” Proceedings of SIGGRAPH’98, Orlando, Florida, 1998;32:123-132.
[54] Taubin G., Horn W., Lazarus F., Rossignac J., “Geometry coding and VRML,” Proceedings of the IEEE, 1998;96(6):1228-1243.
[55] Rossignac J., “Edgebreaker: Connectivity compression for triangle meshes,” IEEE Transactions on Visualization and Computer Graphics 1999;5(1):47-61.
[56] Rossignac J., Szymczak A., “Wrap&Zip decompression of the connectivity of triangle meshes compressed with Edgebreaker,” Journal of Computational Geometry, Theory and Applications, 1999;14(Issue 1-3):119-135
[57] Jae Jeong Choi, Byeong-Seok Shin, Yeong Gil Shin and Kevin Cleary, “Efficient volumetric ray casting for isosurface rendering,” Computers and Graphics 2000;24(5):661-670
[58] Shi-Nine Yang and Tian-Sheng Wu, “Compressing isosurfaces generated with marching cubes,” Accepted for The Visual Computer journal.
[59] Shi-Nine Yang and Tian-Sheng Wu, “Compressing adaptive sosurfaces,” Submitted to the Computers & Graphics journal.
[60] Shi-Nine Yang and Tian-Sheng Wu, “An improved ray-casting algorithm for volume visualization,” Submitted to the SPIE 2002 Conference on Visualization and Data Analysis (VDA 2002), San Jose, California, 20-25 January, 2002.