An improved Marching Cube algorithm for 3D data segmentation

The marching cube algorithm is one of the most popular algorithms for isosurface triangulation. It is based on a division of the data volume into elementary cubes, followed by a standard triangulation inside each cube. In the original formulation, the marching cube algorithm is based on 15 basic triangulations and a total of 256 elementary triangulations are obtained from the basic ones by rotation, reflection, conjugation, and combinations of these operations.

The original formulation of the algorithm suffers from well-known problems of connectivity among triangles of adjacent cubes, which has been solved in various ways. We developed a variant of the marching cube algorithm that makes use of 21 basic triangulations. Triangles of adjacent cubes are always well connected in this approach. The output of the code is a triangulated model of the isosurface in raw format or in VRML (Virtual Reality Modelling Language) format.

Program summary

Program title: TRIANGOLATE

Catalogue identifier: AENS_v1_0

Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AENS_v1_0.html

Program obtainable from: CPC Program Library, Queen’s University, Belfast, N. Ireland

Licensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.html

No. of lines in distributed program, including test data, etc.: 147558

No. of bytes in distributed program, including test data, etc.: 26084066

Distribution format: tar.gz

Programming language: C.

Computer: Pentium 4, CPU 3.2 GHz and 3.24 GB of RAM (2.77 GHz).

Operating system: Tested on several Linux distribution, but generally works in all Linux-like platforms.

RAM: Approximately 2 MB

Classification: 6.5.

Nature of problem: Given a scalar field sampled on a 3D regular grid, build a discrete model of the isosurface associated to the isovalue , which is defined as the set of points that satisfy the equation .

Solution method: The proposed solution is an improvement of the Marching Cube algorithm, which approximates the isosurface using a set of triangular facets. The data volume is divided into logical volumes where the topology of the triangulation is selected through a look-up table, while the metric is computed by linear interpolation.

Running time: It is dependent on the input data, but the test provided takes 8 seconds.