Optimal isosurface extraction from irregular volume data
Published 23 December 2002
Paolo Cignoni, C. Montani, Enrico Puppo, Roberto Scopigno
Citations43
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Tests have shown that the proposed method supports the extraction of isosurfaces from irregular volume data, represented by tetrahedral decomposition, in optimal time, and its practical performance reflects the theoretical optimality.
Abstract
A method is proposed which supports the extraction of isosurfaces from irregular volume data, represented by tetrahedral decomposition, in optimal time. The method is based on a data structure called interval tree, which encodes a set of intervals on the real line, and supports efficient retrieval of all intervals containing a given value. Each cell in the volume data is associated with an interval bounded by the extreme values of the field in the cell. All cells intersected by a given isosurface are extracted in O(m+log h) time, with m the output size and h the number of different extreme values (min or max). The implementation of the method is simple. Tests have shown that its practical performance reflects the theoretical optimality.
Keywords
Computer ScienceEngineering
ACM SIGGRAPH Computer GraphicsMarching cubes: A high resolution 3D surface construction algorithm
8,540 Citations1987William E. Lorensen, H. E. Cline
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
ACM Transactions on GraphicsOctrees for faster isosurface generation
573 Citations1992Jane Wilhelms, Allen Van Gelder
A new space-efficient design is introduced for octree representations of volumes whose resolutions are not conveniently a power of two; octrees following this design are called branch-on-need octrees (BONOs).
IEEE Transactions on Visualization and Computer GraphicsA near optimal isosurface extraction algorithm using the span space
283 Citations1996Yarden Livnat, Han‐Wei Shen +1 more
Using the span space, a new representation of the underlying domain, an isosurface extraction algorithm with a worst case complexity of o(/spl radic/n+k) for the search phase, where n is the size of the data set and k is the number of cells intersected by the isOSurface.
ACM Transactions on GraphicsVisibility-ordering meshed polyhedra
195 Citations1992Peter L. Williams
It is shown how the ordering algorithms used for domain decomposition of finite element meshes for parallel processing, and how the data structures used by these algorithms can be used to solve the spatial point location problem.
IEEE Transactions on Visualization and Computer GraphicsAutomatic isosurface propagation using an extrema graph and sorted boundary cell lists
131 Citations1995Takayuki Itoh, Koji Koyamada
The algorithm is efficient, since it visits only cells that are intersected by an isosurface and cells whose IDs are included in the guides, and it is especially efficient when many isOSurfaces are interactively generated in a huge volume.
Computing Systems in EngineeringAdvanced interactive visualization for CFD
89 Citations1990Michael B. Giles, Robert Haimes
New ideas are presented for the visualization of computational fluid dynamics data that include both unsteady two-dimensional and steady three-dimensional data on either structured or unstructured grids.
Volume probes: interactive data exploration on arbitrary grids
82 Citations1990D. E. Speray, Steve Kennon
A taxonomy of computational grids used in scientific and engineering practice is presented and a technique for cutting them by, and displaying data on, 2D surfaces is developed and this means of slicing grids is utilized in an effective visualization tool.
Discretized Marching Cubes
74 Citations2002C. Montani, Riccardo Scateni +1 more
An algorithm is presented that considerably reduces the number of polygons generated by a Marching Cubes-like scheme without excessively increasing the overall computational complexity.
Sweeping simplices: a fast iso-surface extraction algorithm for unstructured grids
34 Citations2002Han‐Wei Shen, Chris R. Johnson
An algorithm that accelerates the extraction of iso-surfaces from unstructured grids by avoiding the traversal of the entire set of cells in the volume by reducing the cell traversal time by more than 90% over the naive iso-surface extraction algorithm.
Span filtering: an optimization scheme for volume visualization of large finite element models
27 Citations2002R.S. Gallagher
An inexpensive, straightforward method is discussed for reducing the number of elements searched for isovalues of scalar fields within a solid finite-element model, particularly well suited to optimizing real-valued continuum field results such as those found in finite- element data.
CVGIP Graphical Models and Image ProcessingFast generation and display of iso-surface wireframes
8 Citations1992Michael Laszlo
The method is efficient enough to form the basis for an interactive software system for visualizing iso-surfaces and supports efficient generation and display of the iso-surface wireframe corresponding to any selected threshold value.
EurographicsDiscMc: An Interactive System for Fast Fitting Isosurfaces on Volume Data
7 Citations1996Paola Criscione, C. Montani +2 more
The architecture of DiscMC, an interactive system which supports isosurfacing on regular volume datasets, adopts a discretized fitting algorithm that considerably reduces the number of polygons generated by a Marching Cubes-like scheme while presenting shorter running times.
OpenGrey (Institut de l'Information Scientifique et Technique)Multiresolution modeling and visualization of volume data
7 Citations1995Paolo Cignoni, C. Montani +3 more
A multiresolution model for the representation and visualization of volume data that is based on a decomposition of the three-dimensional domain into tetrahedra is presented.