Marching Cubes using Tetrahedrons Method

[Goal] Overcome an ambiguity problem of basic Marching Cubes algorithm

• Example pointcloud

1. Prerequisites

1.1 Dependencies

OpenCV 3.2.0, C++ 11 version

1.2. OpenCV Installation

Follow OpenCV

• Install appropriate OpenCV version: Here.

1.3. Basic Marching Cubes Github

Follow this repo → Marching Cubes

2. Changing Parameters

Parameters in "parameters.h"

// random grid (READ_FILE = 0) or read from file (READ_FILE = 1)
#define READ_FILE 1 

// Maximum Grid Size
#define GRID_MAX 400

// Number of Voxel  
#define NUM_VOXEL 400

// Set ISOVALUE
#define ISOVALUE 0.5

3. Descriptions

(1) save_ply.h from https://github.com/nihaljn/marching-cubes/blob/main/src/utilities.cpp
(2) Input file format → .ply & .txt
(3) If you don't have input files, then you can create random grid → generate_random_grid() in utility.h
(4) Output file format → .ply & .txt
(5) Visualized pointcloud or mesh → viz3DMesh() & viz3DPoints() in viz_mesh.h
(6) Visualization python code also provided in example folder → viz_ply.py
(7) Convert PLY format Binary to ASCII in example folder → cvt_binary2ascii.py

4. Build and Run

Clone the repository and build and run simultaneously:

   $ cd ${workspace}
   $ git clone https://github.com/SungJaeShin/Marching_tetrahedrons.git
   $ cd Marching_tetrahedrons
   $ sh start.sh

In start.sh file, there must write the file (PLY or TXT) location and output file (PLY or TXT) location !!

g++ ./src/main.cpp -L /usr/local/include/opencv2 -lopencv_viz -lopencv_highgui -lopencv_imgcodecs -lopencv_imgproc -lopencv_core -lopencv_features2d -o ./marching
./marching <INPUT_FILE_LOCATION> <OUTPUT_SAVE_LOCATION>

5. Setting Rules between Vertices and Edges !!

    Tables and conventions from:
    http://paulbourke.net/geometry/polygonise/

                      + 0
                     /|\
                    / | \
                   /  |  \
                  /   |   \
                 /    |    \
                /     |     \
               +-------------+ 1
              3 \     |     /
                 \    |    /
                  \   |   /
                   \  |  /
                    \ | /
                     \|/
                      + 2


    Vertex : p0, p1, p2, p3
    Edge : a, b, c, d, e, f
    
    Total case : 2^4 = 16
    
    // Not Make Any plane
    {0, 0, 0, 0} <-----> {0, 0, 0, 0, 0, 0} 
    {1, 1, 1, 1} <-----> {0, 0, 0, 0, 0, 0} 

    // Make Triangle
    {1, 0, 0, 0} <-----> {1, 1, 1, 0, 0, 0}
    {0, 1, 1, 1} <-----> {1, 1, 1, 0, 0, 0}
    {0, 1, 0, 0} <-----> {1, 0, 0, 1, 0, 1}
    {1, 0, 1, 1} <-----> {1, 0, 0, 1, 0, 1}
    {0, 0, 1, 0} <-----> {0, 1, 0, 1, 1, 0}
    {1, 1, 0, 1} <-----> {0, 1, 0, 1, 1, 0}
    {0, 0, 0, 1} <-----> {0, 0, 1, 0, 1, 1}
    {1, 1, 1, 0} <-----> {0, 0, 1, 0, 1, 1}

    // Make Square
    {1, 1, 0, 0} <-----> {0, 1, 1, 1, 0, 1}
    {0, 0, 1, 1} <-----> {0, 1, 1, 1, 0, 1}
    {1, 0, 0, 1} <-----> {1, 1, 0, 0, 1, 1}
    {0, 1, 1, 0} <-----> {1, 1, 0, 0, 1, 1}
    {0, 1, 0, 1} <-----> {1, 0, 1, 1, 1, 0}
    {1, 0, 1, 0} <-----> {1, 0, 1, 1, 1, 0}

Case 1 : Not Make Any Figures
Case 2 : Make Triangles
Case 3 : Make Squares

Voxel Size Calculation Time:

6. Results

• Time consumption

  • Example PLY: sphere.txt (# of pointcloud: 16926)

    NUM VOXEL	# of triangles	Pointcloud read time (ms)	Voxel calculation (ms)	Marching Tetrahedrons (ms)
    200	183000	10.3349 ms	0.640087 ms	303081 ms

• Marching cube results

  ISOVALUE	0.5
  ISOVALUE	1

7. References

[1] https://github.com/SungJaeShin/Marching_cubes.git
[2] https://paulbourke.net/geometry/polygonise/
[3] https://paulbourke.net/geometry/polygonise/source1.c