Fully de-duplicate vertices in MarchingCube algorithm

[empet]

Recently I started using Meshing.isosurface(), with MarchingCubes as method. The docs say that setting reduceverts=true (default: true) will merge vertices within a voxel to reduce mesh size by around 30% and with slight performance improvement. I called both Meshing.isosurface() and skimage.measure.marching_cubes_lewiner(), a Python function from scikit-image, to extrude a brain within a volumetric data of size (91, 109, 91). The number of vertices of the corresponding mesh, returned by Meshing function is (345752) almost 4 times greater than that returned by skimage function (86473). 345752/86473 = 3.99, i.e. it is exaggerated.

Here are the two blocks of code:

using Meshing
using NPZ           
brain_vol = npzread("MNI152.npy") # https://github.com/empet/Datasets/blob/master/MNI152.npy
verts, triangles =  isosurface(brain_vol, MarchingCubes(iso=1.25, reduceverts=true, eps=1e-05))
length(verts),  length(triangles)
(345752, 172932) 
            
#unique vertices:
uni_verts = unique(i -> verts[i], 1:length(verts))
length(uni_verts)
89264 

respectively:

import numpy as np
from skimage import measure            
brain_vol= np.load("MNI152.npy")
verts, triangles = measure.marching_cubes_lewiner(brain_vol, 1.25)[:2] 
len(verts), len(triangles)
(86473, 173070)

The corresponding Jupyter Notebook has the size of 111MB, vs 25MB, when using Python scikit-image. Otherwise the mesh plot is great in both cases:

[sjkelly]

Cool render, thanks for sharing!

This is expected behavior for MarchingCubes. reduceverts is only merging vertices where it is computationally cheap to do so. I assume scikit is merging vertices across the whole mesh, which requires additional memory during computation, but saves on the vertex count in the end. A simple approach to accomplish the de-duplication of vertex references is through a dictionary. This should be okay for simple meshes, but performance would likely scale poorly with Julia's Dict. Erizo has a fast implementation of this.

MarchingTetrahedra does assure the uniqueness property, but it generates far more triangles. This may be an approach if you need connectivity information, but be aware that it generates far more triangles.

[sjkelly]

To be clear, I think this should be a supported feature, so reopening.