在實體資料的呈像(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.

[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.