Efficient Implementation of Marching Cubes’ Cases with Topological Guarantees

Thomas Lewiner
Pontifical Catholic University of Rio de Janeiro

Hélio Lopes, Antônio Wilson Vieira, and Geovan Tavares
Departamento de Matemática, Pontifical Catholic University of Rio de Janeiro

This paper appears in issue Volume 8, Number 2.
Purchase this issue from the akpeters.com web site.

Abstract

Marching Cubes methods first offered visual access to experimental and theoretical data. The implementation of this method usually relies on a small look-up table; many enhancements and optimizations of Marching Cubes still use it. However, this look-up table can lead to cracks and inconsistent topology. This paper introduces a full implementation of Chernyaev’s technique to ensure a topologically correct result, i.e., a manifold mesh, for any input data. It completes the original paper for the ambiguity resolution and for the feasibility of the implementation. Moreover, the cube interpolation provided here can be used in a wider range of methods. The source code is available online.

Author Information

Thomas Lewiner, Departamento de Matemática, Pontifical Catholic University of Rio de Janeiro, Rua Marques de Sao Vicente, 225, Gavea22543-900 Rio de Janeiro, Brazil tomlew@ifrance.com

Hélio Lopes, Departamento de Matemática, Pontifical Catholic University of Rio de Janeiro, Rua Marques de Sao Vicente, 225, Gavea22543-900 Rio de Janeiro, Brazil lopes@mat.puc-rio.br

Antônio Wilson Vieira, Departamento de Matemática, Pontifical Catholic University of Rio de Janeiro, Rua Marques de Sao Vicente, 225, Gavea22453-900 Rio de Janeiro, Brazil awilson@mat.puc-rio.br

Geovan Tavares, Departamento de Matemática, Pontifical Catholic University of Rio de Janeiro, Rua Marques de Sao Vicente, 225, Gavea22453-900 Rio de Janeiro, Brazil tavares@mat.puc-rio.br

Source Code

A C++ implementation of the algorithm is available here: MarchingCubes.zip (116K Zip archive)

• 6 May 2004. Added simple CSG parsing and external volumetric data I/O and some GUI improvements (window trackball, image export, …)

• 17 September 2004. Modified lookup table to orient each triangle, based on suggestion of Jonathan Chin; improved handling of 7th case; code cleaned up and lookup table subdivided; (simple) Doxygen comments added.

• 20 June 2006. Improvement of the robustness in the test_interior, forcing a manifold output even when the input isosurface should not be a manifold; incorporation of non-zero already in the MarchingCubes class.

Tables

The following are the tables used by the algorithm.

Case Tables

The classical 256-lookup table (click to enlarge)
The enhanced 730-lookup table (click to enlarge)

---

Tiling Table

Case 0 Subcase 0 Case 1 Subcase 0 Case 2 Subcase 0 Case 3 Subcase 0 Subcase 1 Case 4 Subcase 0 Subcase 1 Case 5 Subcase 0 Case 6 Subcase 0 Subcase 1 Subcase 2 Case 7 Subcase 0 Subcase 1 Subcase 2 Subcase 3 Subcase 4 Subcase 5 Subcase 6 Subcase 7 Subcase 8 Case 8 Subcase 0 Case 9 Subcase 0 Case 10 Subcase 0 Subcase 1 Subcase 2 Subcase 3 Subcase 4 Case 11 Subcase 0 Case 12 Subcase 0 Subcase 1 Subcase 2 Subcase 3 Subcase 4

Case 13 Subcase 0 Subcase 1 Subcase 2 Subcase 3 Subcase 4 Subcase 5 Subcase 6 Subcase 7 Subcase 8 Subcase 9 Subcase 10 Subcase 11 Subcase 12 Subcase 13 Subcase 14 Subcase 15 Subcase 16 Subcase 17 Subcase 18 Subcase 19 Subcase 20 Subcase 21 Subcase 22 Subcase 23 Subcase 24 Subcase 25 Subcase 26 Subcase 27 Subcase 28 Subcase 29 Subcase 30 Subcase 31 Subcase 32 Subcase 33 Subcase 34 Subcase 35 Subcase 36 Subcase 37

Case 13 Subcase 38 Subcase 39 Subcase 40 Subcase 41 Subcase 42 Subcase 43 Subcase 44 Subcase 45 Subcase 46 Subcase 47 Subcase 48 Subcase 49 Case 14 Subcase 0

---

Test Table

Case	Face tests						Interior Test	Subcase	# triangles
	1st	2nd	3rd	4th	5th	6th
0									0
1									1
2									2
3	-							3.1	2
	+							3.2	4
4	-							4.1	2
	+							4.2	6
5									3
6	-						-	6.1.1	3
	-						+	6.1.2	7
	+							6.2	5
7	-	-	-					7.1	3
	+	-	-					7.2	5
	-	+	-					7.2	5
	-	-	+					7.2	5
	+	+	-					7.3	9
	+	-	+					7.3	9
	-	+	+					7.3	9
	+	+	+				+	7.4.1	9
	+	+	+				-	7.4.2	9
8									2
9									4
10	+	+						10.1.1	4
	-	-					-	10.1.1	4
	-	-					+	10.1.2	8
	+	-						10.2	8
	-	+						10.2	8
11									4
12	+	+						12.1.1	4
	-	-					-	12.1.1	4
	-	-					+	12.1.2	8
	+	-						12.2	8
	-	+						12.2	8
13	-	-	-	-	-	-		13.1	4
	-	-	-	-	-	+		13.2	6
	-	-	-	-	+	-		13.2	6
	-	-	-	-	+	+		impossible	0
	-	-	-	+	-	-		13.2	6
	-	-	-	+	-	+		13.3	10
	-	-	-	+	+	-		13.3	10
	-	-	-	+	+	+		impossible	0
	-	-	+	-	-	-		13.2	6
	-	-	+	-	-	+		13.3	10
	-	-	+	-	+	-		13.3	10
	-	-	+	-	+	+		impossible	0
	-	-	+	+	-	-		13.3	10
	-	-	+	+	-	+		13.4	12
	-	-	+	+	+	-	-	13.5.1	6
	-	-	+	+	+	-	+	13.5.2	10
	-	-	+	+	+	+		13.3	10
	-	+	-	-	-	-		13.2	6
	-	+	-	-	-	+		13.3	10
	-	+	-	-	+	-		13.3	10
	-	+	-	-	+	+		impossible	0
	-	+	-	+	-	-		impossible	0
	-	+	-	+	-	+		impossible	0
	-	+	-	+	+	-		impossible	0
	-	+	-	+	+	+		impossible	0
	-	+	+	-	-	-		13.3	10
	-	+	+	-	-	+	-	13.5.1	6
	-	+	+	-	-	+	+	13.5.2	10
	-	+	+	-	+	-		13.4	12
	-	+	+	-	+	+		13.3	10
	-	+	+	+	-	-		impossible	0
	-	+	+	+	-	+		13.3	10
	-	+	+	+	+	-		13.3	10
	-	+	+	+	+	+		13.3	10
	+	-	-	-	-	-		13.2	6
	+	-	-	-	-	+		13.3	10
	+	-	-	-	+	-		13.3	10
	+	-	-	-	+	+		impossible	0
	+	-	-	+	-	-		13.3	10
	+	-	-	+	-	+	-	13.5.1	6
	+	-	-	+	-	+	+	13.5.2	10
	+	-	-	+	+	-		13.4	12
	+	-	-	+	+	+		13.3	10
	+	-	+	-	-	-		impossible	0
	+	-	+	-	-	+		impossible	0
	+	-	+	-	+	-		impossible	0
	+	-	+	-	+	+		impossible	0
	+	-	+	+	-	-		impossible	0
	+	-	+	+	-	+		13.3	10
	+	-	+	+	+	-		13.3	10
	+	-	+	+	+	+		13.2	6
	+	+	-	-	-	-		13.3	10
	+	+	-	-	-	+		13.4	12
	+	+	-	-	+	-	-	13.5.1	6
	+	+	-	-	+	-	+	13.5.2	10
	+	+	-	-	+	+		13.3	10
	+	+	-	+	-	-		impossible	0
	+	+	-	+	-	+		13.3	10
	+	+	-	+	+	-		13.3	10
	+	+	-	+	+	+		13.2	6
	+	+	+	-	-	-		impossible	0
	+	+	+	-	-	+		13.3	10
	+	+	+	-	+	-		13.3	10
	+	+	+	-	+	+		13.2	6
+	+	+	+	-	-		impossible	0
+	+	+	+	-	+		13.2	6
+	+	+	+	+	-		13.2	6
+	+	+	+	+	+		13.1	4
14									4

BibTeX Entry

@article{LewinerEtAl03,
  author = "Thomas Lewiner and Hélio Lopes and Antônio Wilson Vieira and Geovan Tavares",
  title = "Efficient Implementation of Marching Cubes' Cases with Topological Guarantees",
  journal = "journal of graphics, gpu, and game tools",
  volume = "8",
  number = "2",
  pages = "1-15",
  year = "2003",
}