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)


Dietmar Saupe

Jürgen Toelke


  1. Eugene L. Allgower, Kurt Georg:
    Numerical Continuation Methods,
    Springer-Verlag, New York, 1990
  2. Chandrajit L. Bajaj, Valerio Pascucci, Daniel R. Schikore:
    Accelerated IsoContouring of Scalar Fields,
    Data Visualization Techniques, chap. 3
  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
  4. 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
  5. Udeepta D. Bordoloi, Han-Wei Shen:
    Space Efficient Fast Isosurface Extraction for Large Datasets
    IEEE Visualization 2003
  6. Yi-Jen Chiang, Claudio T. Silva:
    I/O Optimal Isosurface Extraction,
    IEEE Visualization 97, pp. 293-300, 1997
  7. Yi-Jen Chiang, Claudio T. Silva, William J. Schroeder:
    Interactive Out-Of-Core Isosurface Extraction,
    Proc. IEEE Visualization `98, pp. 167-174
  8. 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
  9. 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)
  10. 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
  11. 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)
  12. 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
  13. 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)
  14. 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
  15. 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
  16. Paul Ning, Jules Bloomenthal:
    An evaluation of implicit surface tilers,
    IEEE Comp. Graphics and Appl. 13,6 (1993), 33-41
  17. D. Saupe, J. Toelke:
    Optimal Memory Constrained Isosurface Extraction,
    Vision Modeling and Visualization 2001, pp. 351-358
  18. 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
  19. Han-Wei Shen, Christopher R. Johnson:
    Sweeping Simplices: A fast iso-surface extraction algorithm for unstructured grids,
    Proc. IEEE Visualization `95, pp. 143-150
  20. 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
  21. Chris Weigle, David C. Banks:
    Complex-Valued Contour Meshing,
    IEEE Visualization `96, ISBN 0-89791-864-9
  22. Jane Wilhelms, Allen Van Gelder: Topological Considerations in Isosurface Generation,
    ACM Transactions on Graphics, 1994, vol.13, no.4, pp.337-375
  23. Jane Wilhelms, Allen Van Gelder:
    Octrees for Faster Isosurface Generation,
    ACM Transactions on Graphics, 1992, vol.11, no.3, pp.201-227
  24. 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