arrow
Return

An improved Marching Cube algorithm for 3D data segmentation

delete2013-03-01
delete35
PRE
AI
G
Giovanni Luca Masala *
B
Bruno Golosio
P
P. Oliva
DOI:10.1016/j.cpc.2012.09.030delete
deleteOriginal
deleteShare
deleteSave
Abstract

Abstract

En 中文
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: TRIANGULATE 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 mu(x, y, z) sampled on a 3D regular grid, build a discrete model of the isosurface associated to the isovalue mu(lso), which is defined as the set of points that satisfy the equation mu(x, Y, z) = mu(lso). 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. (C) 2012 Elsevier B.V. All rights reserved.
Keywords:
3D imaging
Surface triangulation

Journal

Computer Physics Communications cover
Computer Physics Communications
IF:
3.4
Papers:
1.2W
Citations:
4.7W

Organization

U
University of Sassari
Scholars:
290
Papers: 112
Citations: 2.8K
Cited Papers

Cited Papers

Primary Lithium Air Batteries
err2014-02-27
err0
PREAI
errJi-Guang Zhang; Jie Xiao; Wu Xu
errShare
errSave
Biomarkers for Sepsis
err2014-01-01
err0
errOAAI
errCesar Henriquez-Camacho; Juan Losa
errShare
errSave
errShare
errSave
A novel and efficient implementation of the marching cubes algorithm
err2001-07-01
err64
PREAI
errDelibasis, KS; Matsopoulos, GK; Mouravliansky, NA; Nikita, KS
errShare
errSave
A novel multithreshold method for nodule detection in lung CT
err2009-07-06
err73
PREAI
errGolosio, Bruno; Masala, Giovanni Luca; Piccioli, Alessio; Oliva, Piernicola; Carpinelli, Massimo; Cataldo, Rosella; Cerello, Piergiorgio; De Carlo, Francesco; Falaschi, Fabio; Fantacci, Maria Evelina; Gargano, Gianfranco; Kasae, Parnian; Torsello, Massimo
errShare
errSave
errShare
errSave
err
IF0
err
err0
PREAI
err
errShare
errSave
researcher View more