ERCIM News No.27 - October 1996

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:

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.

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 Pisa:
homepage.html. This release is for SGI workstations running Irix 5.3.

Please contact:
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