Fast Isosurface Extraction from Regular Volume Datasets - The DiscMC
System
by Claudio Montani, Riccardo Scateni, and Roberto Scopigno
DiscMC (Discrete Marching Cubes) is a prototypal system for the fast
extraction of approximated isosurfaces from regular volume datasets developed
jointly by the Visual Computing Group of CNR in Pisa, and the Scientific
Visualization Group of CRS4 (Center for Advanced Studies, Research and Development)
in Cagliari, Sardinia. DiscMC adopts a fitting algorithm that considerably
reduces the number of polygons generated by a Marching Cubes-like scheme
while presenting lower running times. The system has been implemented in
a Unix environment, using XForms for the GUI specification and OpenGL for
the visualization and rendering.
The Marching Cubes (MC) algorithm, a technique originally proposed by W.
Lorensen and H. Cline, is nowadays considered the standard approach to the
problem of extracting isosurfaces from a regular volume dataset. MC is a
very practical and simple algorithm, and many implementations are available
both as part of commercial systems or as public domain software.
Despite its extensive use in many applications, shortcomings of the approach
have been pointed out regarding topological ambiguities, algorithm computational
efficiency, and excessive output data fragmentation. DiscMC is an attempt
to overcome these shortcomings.
The DiscMC algorithm is a derivation of MC; it assumes discrete dataset
space and replaces cell edge interpolation by midpoint selection. In a number
of applications where approximated isosurfaces are acceptable, linear interpolation
is not critical to extract meaningful isosurfaces since the maximal approximation
error involved in midpoint choice rather than interpolation is 1/2 of the
cell size. This implies that the generated facets can lie only on a finite
number of distinct plane incidences and, for each incidence, the algorithm
generates a limited number of different facets. The coplanar adjacent facets
are then effectively merged into larger triangular primitives.
The DiscMC approach leads to a fast approximated fitting, drastic reductions
in output fragmentation, and lower running times, when compared with classical
MC. Moreover, the use of an unambiguous triangulation scheme allows the
extraction of isosurfaces without topological anomalies.
A well known problem in isosurface fitting is that a large percentage of
the processing time is spent on analyzing and classifying cells not crossed
by the isosurface (empty cells). DiscMC adopts a simple but effective representation
- a pyramid of regular volumes - in order to speed-up the isosurface fitting.
Our pyramid consists of a set of 3D arrays whose elements contain min-max
intervals of the corresponding underlying block of cells.
In our implementation, the pyramid data structure is also used to realize
a multiple level of resolution fitting. We can stop the visit of the data
structure at a user-defined level and extract approximated representations.
A view of the DiscMC system's graphic interface. The isosurfaces in the
graphic window
were extracted from the 128x128x128 regular Bucky dataset, representing
the electron
density around a molecule of C-60, courtesy of AVS International Centre.
The DiscMC algorithm is at the very base of our isosurface fitting system.
The system has been designed to run on Unix workstations, rendering the
extracted isosurfaces with the OpenGL graphics library and having a graphical
user interface based on a portable toolkit, XForms, built over X11.
The main characteristics of the DiscMC system can be summarized as follows:
