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.
|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.|
|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.
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
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
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
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
This addendum reports some late results about a new implementation of the technique described in our 1996 VolVis Symp. paper.
Discretized Marching Cubes
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.
A modified look-up table for implicit
disambiguation of Marching Cubes Abstract
C. Montani, R. Scateni, and R. Scopigno
The Visual Computer, 10(6):353-355, 1994
A new triangulation scheme for the Marching Cubes algorithm is proposed. The scheme allows the extraction of continuous isosurfaces from volumetric data without the need to use disambiguation techniques.
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.