臺灣博碩士論文加值系統

在實體資料的呈像(volume rendering)中，擷取等值面(iso-surface extraction)是相當重要的方法，而在擷取等值面的方法中以同值擴展(iso-contouring)演算法最有效率。同值擴展演算法不似其他方法需在整個實體資料(volume data)中進行搜尋，而僅需搜尋其某一子集合即可完整地找到所有等值面(iso-surface)，我們稱此子集合為種子集(seed-set)，其特性為實體資料內的所有等值面皆會與此種子集相交，而且此種子集是在前置處理時間(preprocessing time)內即可建立完成。
當我們在執行階段(run time)時給定一個等值(iso-value)，同值擴展演算法即可開始執行，從種子集中有包含等值的單元格子(cells)開始逐漸擴展而形成整個等值面。如果我們在前置處理時間內所找到的種子集愈小，則在執行階段所花的搜尋時間也將會減少。因此在其他探討同值擴展演算法的論文中，大都將焦點關注於如何找到較小的種子集。
本研究中我們提出一個新穎且有效率的方法來建立種子集，此方法不但能降低種子集的大小，而且也能提昇擷取等值面的速度。

Iso-surface extraction is one of the most important approaches for volume rendering, and iso-contouring algorithm is one of the most effective methods for iso-surface extraction. Unlike most other methods having their search domain to be the whole data-set, iso-contouring algorithm does its search only on a relatively small subset of the original data-set. This subset, called a seed-set, has the property that every iso-surface must intersect with it, and it could be built at the preprocessing time.
When an iso-value is given at the run time, iso-contouring algorithm starts from the intersected cells in the seed-set, and gradually propagates to form the whole iso-surface. As smaller seed-sets offer less cell searching time, most existing iso-contouring algorithms concentrate on how to identify an optimal seed-set.
In this paper, we propose a new and efficient approach for seed-set construction. This algorithm could reduce the size of the seed-set and speed up the performance for iso-surface extraction.

中文摘要 I
英文摘要 II
誌謝 III
目錄索引 IV
圖表索引 VI
第一章 導論 1
1.1 前言 1
1.2 研究目的 1
1.3 論文架構 3
第二章 相關工作 4
2.1 科學視覺化(SCIENTIFIC VISUALIZATION) 4
2.2 實體資料(VOLUME DATA) 6
2.2.1 規則實體資料在三維空間中的定義 7
2.2.2 實體資料的取得 8
2.3 實體資料的呈像(VOLUME RENDERING) 10
2.3.1 實體資料呈像方法的分類 10
2.3.2 比較直接式呈像與非直接式呈像方法的優缺點 11
2.4 等值面的擷取(ISO-SURFACE EXTRACTION) 12
2.4.1 單元格子的三角化(cell triangulation) 13
2.4.1.1 Marching Cubes演算法 13
2.4.2 單元格子的搜尋(cell searching) 17
2.4.2.1 Domain Search 18
2.4.2.2 Range Search 20
2.4.3 種子集(seed-set) 21
2.4.4 同值擴展演算法(iso-contouring algorithm) 22
2.4.5 Volume Thinning 演算法 24
2.4.6 Contour Tree 演算法 28
第三章 新種子集演算法 36
3.1 概述 36
3.2 想法的起源 37
3.3 單元格子的分群 39
3.4 擷取種子集程序 41
3.4.1 Whole1 Pass 42
3.4.2 Whole2 Pass 44
3.4.3 Minimum Cover演算法 48
3.4.4 透過離散集合(Disjoint Set)來增進效能 51
第四章 實驗結果及分析 55
4.1 實驗環境 55
4.2 實驗結果 56
4.2.1 新種子集演算法的實驗結果 57
4.2.2 實作Volume Thinning演算法的實驗結果 62
4.2.3 新種子集演算法與其它種子集擷取方法之比較 64
第五章 結論 66
參考文獻 67

[1]C. L. Bajaj, V. Pascucci, and D. R. Schikore. Fast Isocontouring for Improved Interactivity. In Proceedings on 1996 Symposium on Volume Visualization, pages 39-46, October 1996.
[2]C. L. Bajaj, V. pascucci, and D. R. Schikore. Fast Isocontouring for Structured and Unstructured Meshes in Any Dimension. In IEEE Visualization ’97 Late Breaking Hot Topics, 1997.
[3]C. L. Bajaj, V. pascucci, and D. R. Schikore. Seed Sets and Search Structures for Accelerated Isocontouring. Technical Report 97-034, Department of Computer Science, Purdue University, 1997.
[4]J. L. Bentley, K. L. Clarkson, and D. H. Levine. Fast Linear Expected-Time Algorithms for Computing Maxima and Convex Hulls. Algorithmica, 9:168-183, 1993.
[5]W. Chen, H. Hwang, and T. Tsai. Efficient Maximal-Finding Algorithms for Random Planar Samples. Discrete Mathematics and Theoretical Computer Science, 6:107-122, 2003.
[6]P. Cignoni, P. Marino, C. Montani, E. Puppo, and R. Scopigno. Speeding Up Isosurface Extraction Using Interval Trees. IEEE Transactions on Visualization and Computer Graphics, 3(2):158-170, April 1997.
[7]H. Edelsbrunner, Dynamic Data Structures for Orthogonal Intersection Queries. Technical Report F59, Inst. Informationsverarb.,Tech. University Graz, 1980.
[8]R. S. Gallagher. Span Filtering: An Optimization Scheme for Volume Visualization of Large Finite Element Models. In IEEE Visualization ’91, pages 68-75, October 1991.
[9]T. Itoh and K. Koyamada. Automatic Isosurface Propagation Using an Extrema Graph And Sorted Boundary Cell Lists. IEEE Transactions on Visualization and Computer Graphics, 1(4):319-327, December 1995.
[10]T. Itoh, Y. Yamaguchi, and K. Koyamada. Volume Thinning for Automatic Isosurface Propagation. In IEEE Visualization ’96, pages 303-310, October 1996.
[11]M. Kreveld, R. Oostrum, C. L. Bajaj, V. Pascucci, and D. Schikore. Contour Trees and Small Seed Sets for Isosurface Traversal. In Symposium on Computational Geometry, pages 212-220, 1997.
[12]M. Lveoy. Display of Surfaces from Volume Data. IEEE Computer Graphics and Applications, 8(3):29-37, March 1988.
[13]M. Lveoy. Efficient Ray Tracing of Volume Data. ACM Transactions on Graphics, 9(3):245-261, 1990.
[14]Y. Livnat, H. Shen, and C. R. Johnson. A Near Optimal Isosurface Extraction Algorithm Using the Span Space. IEEE Transactions on Visualization and Computer Graphics, 2(1):73-84, March 1996.
[15]W. E. Lorensen and H. E. Cline. Marching Cubes: A High Resolution 3D Surface Construction Algorithm. Computer Graphics, 21(4):163-169, July 1987.
[16]H. Shen, C. D. Hansen, Y. Livnat, and C. R. Johnson. Isosurfacing in Span Space with Utmost Efficiency. In IEEE Visualization ’96, pages 287-294, October 1996.
[17]J. Wilhelms and A. V. Gelder. Octrees for Faster Isosurface Generation. ACM Transactions on Graphics, 11(3):201-227, July 1992.
[18]T. Itoh, K. Koyamada, Isosurface Extraction using Extrema Graphs, in Visualization Handbook, editted by Chuck Hansen and Chris Johnson, 2004, to be published.
[19]T. Itoh, Y. Yamaguchi, and K. Koyamada, Fast Isusurface Generation Using the Volume Thinning Algorithm, IEEE Transactions on Visualization and Computer Graphics, Vol. 7, No. 1, pp. 32-46, 2001.
[20]Robert E. Tarjan, and Jan van Leeuwen, Worst-case Analysis of Set Union Algorithm, Journal of the ACM, 31(2):245-281, 1984.