Marching Cubes

[Goal] The implementation Marching Cubes using OpenCV in C++

• 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.

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) Loopup Table from http://paulbourke.net/geometry/polygonise/
(2) save_ply.h from https://github.com/nihaljn/marching-cubes/blob/main/src/utilities.cpp
(3) Input file format → .ply & .txt
(4) If you don't have input files, then you can create random grid → generate_random_grid() in utility.h
(5) Output file format → .ply & .txt
(6) Visualized pointcloud or mesh → viz3DMesh() & viz3DPoints() in viz_mesh.h
(7) Visualization python code also provided in example folder → viz_ply.py
(8) 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_cubes.git
   $ cd Marching_cubes
   $ 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/

       v4--------v5       *---e4---- *
      /|       / |      / |         /|
     / |      /  |     e7 |       e5 |
    /  |     /   |    /   e8     /  e9
  v7--------v6   |   *----e6---*     |
   |   |    |    |   |    |     |    |
   |  v0----|---v1   |    *---e0|--- *
   |  /     |  /     e11 /     e10  /
   | /      | /      |e3        | e1
   |/       |/       |/         |/
 v3--------v2        *---e2---- *


    Vertex : v0, v1, v2, v3, v4, v5, v6, v7
    Edge   : e0, e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11

    Rules  : (1) find cubeIndex (using vertices) and make 16 bits number
             (2) find edgeIndex (using loopup table)
             (3) find edgePoints (using interpolation)
             (4) make triangles

6. Results

• Time consumption

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

    NUM VOXEL	# of triangles	Pointcloud read time (ms)	Voxel calculation (ms)	Marching Cubes (ms)
    200	68096	9.54439 ms	0.684776 ms	272528 ms

• Marching cube results

  ISOVALUE	-0.5
  ISOVALUE	0.5
  ISOVALUE	1

• Time Consumption of Random Grid Generation results (assume: isovalue 0.5)

  Density	1	random	-1
  # of voxel	125000	125000	125000
  # of triangles	36064	321827	17368
  Pointcloud read time (ms)	11.6072	11.9498	13.745
  Voxel calculation (ms)	5.21115	4.86867	6.08164
  Marching Cubes (s)	667.486	701.606	732.627

• Marching cube results

  Density	Results
  1
  random
  -1

7. References

[1] https://github.com/nihaljn/marching-cubes
[2] https://www.volume-gfx.com/volume-rendering/marching-cubes/
[3] http://www.it.hiof.no/~borres/j3d/explain/marching/p-march.html
[4] https://paulbourke.net/geometry/polygonise/