Isosurface Extraction
Isosurface extraction deals with the problem of generating the surface (or, more generally, the point set) defined by the preimage of a scalar function of several variables. More specifically, in 3D an example of such problems is described as follows: We are given a three-dimensional array of scalar values a(x,y,z) with x=0,...,xsize-1, y=0,...,ysize-1, z=0,...,zsize-1 and an "isovalue" v. We consider eight neighbouring data values as vertices of a small cube called a cell. Each of these cells has an interval [min,max) obtained as the minimum and the maximum of the corresponding eight data values. A visualization of the isosurface requires a list of all cells for which the isovalue v is contained in the interval [min,max). The brute force method reports this list by sequentially examining all cells. By using interval trees or kd-trees a much faster approach is possible, however at the expense of auxiliary tree data structures that consume large amounts of memory space. Out-of-core extraction methods can solve the problem with high speed and low memory, but need a large amount of external memory. We have worked on methods of isosurface extraction, that are constrained by a given amount of memory. The techniques developed report the cells containing parts of the isosurface and trade off auxiliary memory against speed in an optimal fashion.
Our work includes
- Interactive extraction and visualization of isosurfaces
- Speed optimization with high or low memory
- Comparison of various data structures for speed optimization
- The ConditionedTree, a parameter-dependent method of speed optimization
- Optimizaton of interval trees (dependent AND independent from isosurface extraction)
Some example methods for isosurface extraction:
- Brute force method
- Volume space methods: Block partitions, Adaptive partition trees (binary or octree)
- Span space methods: Interval tree, K-D-tree, ISSUE
- Seed set methods
- Out-of-core methods
- Conditioned trees (our new method)
Members
Bibliography
- Eugene L. Allgower, Kurt Georg:
Numerical Continuation Methods,
Springer-Verlag, New York, 1990 - Chandrajit L. Bajaj, Valerio Pascucci, Daniel R. Schikore:
Accelerated IsoContouring of Scalar Fields,
Data Visualization Techniques, chap. 3 - Chandrajit L. Bajaj, Valerio Pascucci, Daniel R. Schikore:
Fast Isocontouring For Improved Interactivity,
1996 Volume Visualization Symposium, ISBN 0-89791-741-3, pp. 39-46 - Chandrajit L. Bajaj, Valerio Pascucci, Daniel R. Schikore:
Seed sets and search structures for optimal isocontour extraction,
Technical Report 99-35, Texas Institute of Computational and Applied Mathematics, University of Texas, Austin, 1999 - Udeepta D. Bordoloi, Han-Wei Shen:
Space Efficient Fast Isosurface Extraction for Large Datasets
IEEE Visualization 2003 - Yi-Jen Chiang, Claudio T. Silva:
I/O Optimal Isosurface Extraction,
IEEE Visualization 97, pp. 293-300, 1997 - Yi-Jen Chiang, Claudio T. Silva, William J. Schroeder:
Interactive Out-Of-Core Isosurface Extraction,
Proc. IEEE Visualization `98, pp. 167-174 - Paolo Cignoni, Paola Marino, Claudio Montani, Enrico Puppo, Roberto Scopigno:
Speeding Up Isosurface Extraction using Interval Trees,
IEEE Transactions on Visualization and Computer Graphics, 1997, ISSN 1077-2626, vol.3, no.2 - Hugh Everett:
Generalized Lagrange Multiplier method for solving problems of optimum allocation of resources,
Operations Research 11 (1963), pp. 399-417
(used for getting the optimal Conditioned Tree) - Issei Fujishiro, Yuji Maeda, Hiroshi Sato, Yuriko Takeshima:
Volumetric Data Exploration Using Interval Volume,
IEEE Transactions on Visualization and Computer Graphics, vol. 2, no. 2, pp. 144-155, June 1996 - Allen Gersho, Robert M. Gray:
Vector Quantization And Signal Compression,
Kluwer Academic Publishers, 0-7923-9181-0, sect. 17.5: The Generalized BFOS Algorithm
(used for optimizing a particular extraction method) - Takayuki Itoh, Yasushi Yamaguchi, Koji Koyamada:
Fast Isosurface Generation Using the Volume Thinning Algorithm,
IEEE Transactions on Visualization and Computer Graphics, 2001, Vol. 7, No. 1 - Marc van Kreveld, René van Oostrum, Chandrajit Bajaj, Valerio Pascucci, Dan Schikore:
Contour Tree and Small Seed Sets for Isosurface Traversal,
Proc. ACM Symp. on Comp. Geom. `97, Nice (France) - Yarden Livnat, Hai-Wei Shen, Christopher R. Johnson:
A Near Optimal Isosurface Extraction Algorithm Using The Span Space,
IEEE Transactions on Visualization and Computer Graphics, 1996, ISSN 1077-2626, vol.2, no.1, pp.73-84 - William E. Lorensen, Harvey E. Cline:
Marching Cubes: a high resolution 3D surface construction algorithm,
ACM Computer Graphics, vol. 21, no. 4 (7/1987), pp. 163-196 - Paul Ning, Jules Bloomenthal:
An evaluation of implicit surface tilers,
IEEE Comp. Graphics and Appl. 13,6 (1993), 33-41 - D. Saupe, J. Toelke:
Optimal Memory Constrained Isosurface Extraction,
Vision Modeling and Visualization 2001, pp. 351-358 - H.W. Shen, C.D. Hansen, Y. Livnat and C.R. Johnson:
Isosurfacing in Span Space with Utmost Efficiency (ISSUE),
IEEE Proceedings Visualization `96, pp. 287-294, 1996 - Han-Wei Shen, Christopher R. Johnson:
Sweeping Simplices: A fast iso-surface extraction algorithm for unstructured grids,
Proc. IEEE Visualization `95, pp. 143-150 - Jürgen Toelke, Dietmar Saupe:
Speicher- und Zeitbedarf von Methoden der Isoflächen-Extraktion,
Graphiktag Berlin 2000, Fachausschuß 4.1 der Gesellschaft für Informatik - Chris Weigle, David C. Banks:
Complex-Valued Contour Meshing,
IEEE Visualization `96, ISBN 0-89791-864-9 - Jane Wilhelms, Allen Van Gelder: Topological Considerations in Isosurface Generation,
ACM Transactions on Graphics, 1994, vol.13, no.4, pp.337-375 - Jane Wilhelms, Allen Van Gelder:
Octrees for Faster Isosurface Generation,
ACM Transactions on Graphics, 1992, vol.11, no.3, pp.201-227 - Jane Wilhelms, Allen Van Gelder:
Multi-Dimensional Trees for Controlled Volume Rendering and Compression,
1994 Symposium on Volume Visualization, ISBN 0-89791-741-3, pp.27-34