The main results of the Group in the field of the Surface Fitting Techniques can be summarized as follows:
| Marching Cubes (MC), the most common algorithm for the reconstruction of faceted isosurfaces from volume data, has been studied and slightly modified in order to solve the problem of topological inconsistencies. A new triangulation scheme has been proposed which gives continuous surfaces and avoids postprocessing disambiguation by replacing the ambiguous configurations with three new non-ambiguous ones. | |
| Rendering times for surfaces fitted by MC on small machines (lacking in hardware Z-Buffer) are usually not interactive. We have proposed a solution, based on canonical depth-sorting, which processes cells in depth order and reduces visibility to a number of independent (local to the cell) subproblems. | |
| We also developed a new speed-up method which supports the isosurface
fitting from both unstructured and structured volume data, 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. 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. This research is carried out in cooperation with Enrico Puppo of IMA-CNR, Genova, ITALY. |
|
| Discrete Marching Cubes (DiscMC) is an algorithm which considerably
reduces the number of polygons returned by a Marching Cubes-like approach. Reducing the
complexity of the surfaces fitted is a key problem when high resolution data (e.g.
256x256x256 or higher) are processed. DiscMC assumes discretization of the dataset space
and replaces cell edge interpolation with midpoint selection. The returned facets thus lie
on a finite number of incidences, allowing simple merging into larger coplanar polygons. A software prototype, Surfactor, now implements a regular Marching Cubes algorithm, a Discrete Marching Cubes, and a Precise Discrete Marching Cubes. The packet is freeely downlodable. Most of the research regarding isosurface fitting on regular data is carried out in cooperation with Riccardo Scateni of the University of Cagliari ITALY. |
|
Marching
Cubes |
We have developed a method to obtain a high accuracy of the fitted isosurface by adaptive refinements. The method requires that the starting geometric configuration inside each cell be topologically correct. For this reason we designed a new, Exhaustive Marching Cubes Look Up Table (ELUT) which encodes multy-entry patterns for each ambiguous configuration. |
| Surface fitting has also been implemented in the framework of the TAn v.1 and TAn v.2 systems (two prototipal systems for the management and visualization of volume datasets represented with tetrahedral decompositions). See the Direct Volume Rendering page for more detail. |
|
Surfactor 1.2 |
| Download Surfactor 1.2 | ||
| Browse Surfactor's HTML User Manual | Download Surfactor's HTML User Manual (~400 Kb) | See Surfactor's Numeric and Visual Results |
Surfactor represents a sort of compendium of our results in
isosurface extraction from regular datasets. The packet provides increased efficiency,
correct management of T-vertices, hierarchical representation of the volume dataset,
output of efficient triangle strips and fans, etc. Surfactor
(version 1.2, SGI executables only, Operating System Irix 6.3) is also described in this paper.
Surfactor is an interactive prototypal system for the extraction of
isosurfaces from regular volume datasets. Surfactor let the user:
Surfactor's main characteristics can be summarized as follows:
The Exhaustive Look Up Table is a multi-entry Marching Cubes LUT which provides, for each MC ambiguous configuration, different geometric patches. Each pattern has to be selected according to the value(s) of some of the face saddle points and/or body saddle point of the cell. The basic assumption of our MC ELUT is a trilinear interpolant inside each cell.
Abstract
Since the introduction of techniques for isosurface extraction from
volumetric datasets, one of the hardest problems has been to reduce the number of
generated triangles (or polygons).
This paper presents an algorithm that considerably reduces the number of triangles
generated by a Marching Cubes algorithm, while presenting very close or shorter running
times. The algorithm first assumes discretization of the dataset space and replaces cell
edge interpolation by midpoint selection. Under these assumptions the extracted surfaces
are composed of polygons lying within a finite number of incidences, thus allowing simple
merging of the output facets into large coplanar triangular facets. Lastly, the vertices
which survived the decimation process are located on their exact positions and normals are
computed.
An experimental evaluation of the proposed approach on datasets relevant to biomedical
imaging and chemical modeling is reported.
Adaptively adjusting Marching Cubes output to fit a trilinear
reconstruction filter
F. Allamandri, P. Cignoni, C.
Montani, R. Scopigno
EG Workshop on Scientific Visualization '98 Conf. Proc.,
D. Bartz ed., Springer Wien 1998, pp 25-34
Reconstruction of Topologically
Correct and Adaptive Trilinear Isosurfaces
P. Cignoni, F. Ganovelli, C. Montani, R. Scopigno
Computers & Graphics, Elsevier
Scienc, Vol. 24, no. 3, June 2000, pp 399-418.
Speeding Up Isosurface Extraction using
Interval Trees
Abstract
P. Cignoni, P. Marino, C. Montani, E. Puppo and R. Scopigno
IEEE Trans. on Visualization and Computer Graphics, Vol.3(2), June 1997,
pp.158-170
The interval tree is an optimally efficient search structure proposed by
Edelsbrunner to retrieve intervals of the real line that contain a given query value.
We propose the application of such a data structure to the fast location of cells
intersected by an isosurface in a volume dataset. The resulting search method can be
applied to both structured and unstructured volume datasets, and it can be applied
incrementally to exploit coherence between isosurfaces. We also address issues about
storage requirements, and operations other than the location of cells, whose impact is
relevant in the whole isosurface extraction task.
In the case of unstructured grids, the overhead due to the search structure is compatible
with the storage cost of the dataset, and local coherence in the computation of isosurface
patches is exploited through a hash table. In the case of a structured dataset, a new
conceptual organization is adopted, called the chess-board approach, which exploits
the regular structure of the dataset to reduce memory usage and to exploit local
coherence. In both cases, efficiency in the computation of surface normals on the
isosurface is obtained by a pre-computation of the gradients at the vertices of the mesh.
Experiments on different kinds of input show that the practical performance of the method
reflects its theoretical optimality.
Optimal Isosurface Extraction from Irregular Volume Data
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.
Optimal Isosurface Extraction from Irregular Volume Data: An Addendum
Abstract
This addendum reports some late results about a new implementation of the
technique described in our 1996 VolVis Symp. paper.
Discretized Marching Cubes
Abstract
Since the introduction of standard techniques for isosurface extraction
from volumetric datasets, one of the hardest problems has been to reduce the number of
triangles (or polygons) generated.
This paper presents an algorithm that considerably reduces the number of polygons
generated by a Marching Cubes-like scheme without excessively increasing the overall
computational complexity. The algorithm assumes discretization of the dataset space and
replaces cell edge interpolation by midpoint selection. Under these assumptions, the
extracted surfaces are composed of polygons lying within a finite number of incidences,
thus allowing simple merging of the output facets into large coplanar polygons.
An experimental evaluation of the proposed approach on datasets related to biomedical
imaging and chemical modelling is reported.
Using Marching Cubes on small machines
Abstract
A simple technique to visualize the isosurfaces extracted from a
cell-based volumetric dataset using the Marching Cubes algorithm is proposed. The
technique exploits the intrinsic ordering of the triangles produced by the surface
extraction algorithm by adopting a Back-to-Front visualization technique. The use of the
technique together with the adoption of a simple shading algorithm permits the rendering
of high resolution volumetric datasets in computational environments with limited
capabilities in terms of memory and graphics hardware.
