ERCIM News No.27 - October 1996
Fast Isosurface Extraction from Regular Volume Datasets - The DiscMC
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
were extracted from the 128x128x128 regular Bucky dataset, representing
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:
The DiscMC system is faster than standard MC (on an SGI Indigo2 R4400 workstation,
it extracts an average of 22K - 24K triangles per second) and, in Draft
(Proof) modality, it reduces the number of triangles to 20%-40% (25%-45%)
of those returned by the MC algorithm.
- interactive selection of the threshold value (iso-level) ­p; to
help the user in selecting the desired threshold, an Image Browser allows
a slice-by-slice analysis of the dataset
- two output modalities ­p; Draft (less triangles in output, faster
execution, imprecise rendering) and Proof (more triangles, slower execution,
- use of a pyramidal data structure to speed-up the marching step of
the algorithm and to allow the extraction of isosurfaces at multiple level
- rendering of the fitted geometries through an OpenGL viewer, a very
simple tool providing a single light source, Gouraud shaded or wire-frame
representation, and a basic control of the viewpoint
- saving of the fitted geometries in the SGI Open Inventor format.
The DiscMC system is currently available as public domain software at the
Visual Computing Group Web site of the CNUCE and IEI (CNR) Institutes in
homepage.html. This release is for SGI workstations running Irix 5.3.
Claudio Montani - IEI-CNR
Tel: +39 50 593451
or Riccardo Scateni - CRS4
Tel: +39 70 2796293
or Roberto Scopigno - CNUCE-CNR
Tel: +39 50 593304
return to the contents page