Meaning of input?

[LuckyOne09]

Hello, could you give more detailed documentation about sc.marching_cubes.

I am wondering the meaning of the input to sc.marching_cubes. The array of shape (N, 3) is something's 3d coordinates or something else?

[schlegelp]

The input are xyz voxel coordinates which is effectively the same as a sparse matrix in COOrdinate format.

A quick example in 2D to keep things easy:

Consider this 4 x 4 dense matrix with two "filled" voxels

0 0 0 0
0 0 1 0 
0 1 0 0
0 0 0 0

The sparse COO version of this would be

[[1, 2],
  2, 1]]

(using Python indexing)

In my use case, I'm starting with the x/y/z voxel coordinates but if you have a dense 3d matrix, you can use np.where to produce the (N, 3) input.

[LuckyOne09]

Thank you for your quick reply. But I still can not imagine the relationship between input and output.
when I give inputs like:

    voxels = np.array([[0, 0, 0],
                       [1, 0.5, 0.5]])
    m = sc.marching_cubes(voxels)

The output is

Could you explain why gives this output?

And I am also wondering how could you do marching sparse cubes only given sparse coordinates?
I think you must have sparse coordinates and their signed distance like what skimage.measure.marching_cubes does

[schlegelp]

Your input has two voxels which is why you get a mesh consisting of two cubes. Hard to say from the still but the second one looks distorted. The voxel xyz coordinates are the indices of the filled voxels in a dense matrix, and as such should be integers - the integer thing is not actively enforced but I suspect your 0.5 floats are the issue here.

As to the implementation: in a nutshell, it uses some fast sorting to find left, right, top, bottom, front and back surface voxels and then reconstructs a mesh from it. Please see the code for details - it's fairly small.

[LuckyOne09]

So, the sc.marching_cubes is just to visualize sparse voxels? not to do stuff like Marching cubes
I had thought what you did is implementing sparse version of skimage.measure.marching_cubes

[schlegelp]

As advertised, sparse-cubes produce a proper surface mesh just like skimage.measure.marching_cubes!

Check out this toy example:

>>> import numpy as np
>>> # A dense, fully filled 2 x 2 x 2 matrix
>>> dense = np.ones((2, 2, 2))
>>> # Turn the dense matrix into indices of filled voxels 
>>> voxels = np.vstack(np.where(dense)).T
>>> voxels.shape
(8, 3)
>>> mesh = sc.marching_cubes(voxels)

If you plot/inspect the resulting mesh, you will find that there are no internal faces.

[LuckyOne09]

Yeah, I found that there are no internal faces. What I mean is it looks like sparse-cubes can not do things like extracting iso-surface from sdf sparse volume

[schlegelp]

What is a "sdf sparse volume"? Signed-distance?

[LuckyOne09]

Yes. By "sdf sparse volume", I mean a sparse data structure saving signed-distance of each sparse coordinates.
In skimage.measure.marching_cubes, it requires a dense 3d volume saving signed-distance of each 3d points and extracts iso-surface from this sdf dense volume

[schlegelp]

What data structure are you using? Scipy sparse matrices/arrays are 2d only, right?

[LuckyOne09]

I don't use scipy sparse matrices. Since I want to do marching cubes in 3d space. So I define an array of shape (N, 4) and each line of it specify a 3d points and its sdf value.
I am looking for an existing library which could extract iso-surface based on this 4D array. The sdf of points which are not in the array should be positive.

[schlegelp]

In that case, you should be able to just pass the x/y/z component of your array to sc.marching_cubes. You probably want to threshold too, so it should look something like this:

>>> # Find a sensible threshold 
>>> th = 10
>>> # `arr` is your (x, y, z, value) array 
>>> voxels_xyz = arr[arr[:, 3] >=  th, :3].astype('uint32')
>>> mesh = sc.marching_cubes(voxels_xyz)

This really should work unless I'm misunderstanding your data. If you don't mind sharing some example array (perhaps as npy file), I'm happy to have a look.

[LuckyOne09]

Thank you for your kindness and quick reply.
However, what I want is extract mesh like

I think your repo only could "voxelize" signed distance field and generate mesh like:

What I expect is to extract mesh like this

I know if voxel size is sufficiently small it will produce similar results, but it is just not what i want.
Whatever, thank you for your great work and kind support again!

[schlegelp]

I am fully aware of how marching cubes works including the cube configurations but thanks for the reminder. As mentioned in the README, sparse-cubes does not currently do half-edges. That's mainly because the way we're getting the surface mesh would make parsing these configurations very expensive. Perhaps I'll add it in the future but I wouldn't hold my breath.

I have no clue what that psychedelic second screenshot is supposed to show but I stand by my earlier statement that you can produce a perfectly decent surface mesh (with a bit of smoothing after meshing). Without you sharing an examaple of your data though, I feel like we're at an impasse and I can't help you.