Fast isocontouring for improved interactivity
Published 23 December 2002
Chandrajit Bajaj, Valerio Pascucci, D.R. Schikore
Citations76
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
An isocontouring algorithm which is near-optimal for real-time interaction and modification of isovalues in large datasets and a specialized algorithm suitable for meshes of regular topology, including rectilinear and curvilinear meshes is described.
Abstract
We present an isocontouring algorithm which is near-optimal for real-time interaction and modification of isovalues in large datasets. A preprocessing step selects a subset S of the cells which are considered as seed cells. Given a particular isovalue, all cells in S which intersect the given isocontour are extracted using a high-performance range search. Each connected component is swept out using a fast isocontour propagation algorithm. The computational complexity for the repeated action of seed point selection and isocontour propagation is O(log n'+k), where n' is the size of S and k is the size of the output. In the worst case, n'=O(n), where n is the number of cells, while in practical cases, n' is smaller than n by one to two orders of magnitude. The general case of seed set construction for a convex complex of cells is described, in addition to a specialized algorithm suitable for meshes of regular topology, including rectilinear and curvilinear meshes.
Keywords
Computer ScienceEngineering
ACM SIGGRAPH Computer GraphicsMarching cubes: A high resolution 3D surface construction algorithm
8,540 Citations1987William E. Lorensen, H. E. Cline
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).
Computational geometry : an introduction through randomized algorithms
544 Citations1994Ketan Mulmuley
A comparison of quick-sort and search problems, Voronoi diagrams of Hyperplanes, and the model of randomness: The number of faces and the expected structural and conflict change.
SIAM Journal on ComputingPriority Search Trees
491 Citations1985Edward M. McCreight
A new data structure that is called a priority search tree, of which two variants are introduced, operations (1), (2), and (3) can be implemented in $O(\log n)$ time, where n is the cardinality of D.
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.
The asymptotic decider: resolving the ambiguity in marching cubes
253 Citations2002Gregory M. Nielson, Bernd Hamann
A method for computing isovalue or contour surfaces of a trivariate function is discussed, a modification that is intended to correct a problem with a previous method.
The Visual ComputerOn generating topologically consistent isosurfaces from uniform samples
151 Citations1994B. K. Natarajan
This paper provides an efficient algorithm for the case in whichf is the piecewise trilinear interpolant; for this case existing methods fail to satisfy all three of the above conditions simultaneously.
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.
Topological considerations in isosurface generation extended abstract
101 Citations1990Jane Wilhelms, Allen Van Gelder
It is shown that disambiguation methods, to be at all accurate, need to consider sampl e values in the neighborhood outside the cell, and introduces two gradient-consistency heuristics thatdisambiguate a t reasonable computational cost and give correct topology.
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.
Isosurfacing in span space with utmost efficiency (ISSUE)
66 Citations2002Han‐Wei Shen, Charles Hansen +2 more
The performance of the sequential algorithm to locate the cell elements intersected by isosurfaces is faster than the Kd tree searching method originally used for the Span Space algorithm, which can achieve high load balancing for massively parallel machines with distributed memory architectures.
Computer Graphics ForumThe Mesh Propagation Algorithm for Isosurface Construction
36 Citations1994C.T. Howic, Edwin Blake
A new algorithm, Mesh Propagation, is presented for the generation of isosurfaces from three‐dimensional discrete data sets using connected strips of dynamically triangulated polygons that speeds up surface construction and reduces surface storage requirements.
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.
International Journal of Geographical Information SystemsEfficient methods for Isoline extraction from a TIN
27 Citations1996Marc van Kreveld
A data structure is presented to store a triangulated irregular network digital elevation model, from which isolines can be extracted very efficiently, and in all three cases, the required data structure has only linear size.
ACM SIGGRAPH Computer GraphicsThe theory, design, implementation and evaluation of a three-dimensional surface detection algorithm
26 Citations1980Ehud Artzy, Gideon Frieder +1 more
In many three-dimensional imaging applications the three- dimensional scene is represented by aThree-dimensional array of volume elements, or voxels for short, and a subset Q of the voxELs is specified.