Isosurface generation

[mrbuche]

Is your feature request related to a problem? Please describe.

None of our dualization plans will change the fact that exterior and interior boundaries will still be stair-stepped.

Describe the solution you'd like

An interior (possibly exterior) surface smoothing scheme is required, possibly something like marching cubes?

Describe alternatives you've considered

Dualization of the segmentation will mostly place cells-as-voxels along boundaries, which will become elements, which will leave us with approximately the same stair-stepped boundary as if we directly meshed the segmentation (in comparison, the only new thing we can is interior adaptivity).

Additional context

This might be more important in the short term.

It also could be useful to just have the option to return the reconstructed surfaces as STL etc. files.

[mrbuche]

Some discussion related to video game rendering:

https://www.reddit.com/r/VoxelGameDev/comments/qxi0u3/cubical_marching_squares_vs_dual_contouring_which/?rdt=44360

[mrbuche]

Marching cubes, dual marching cubes, dual contouring, manifold dual contouring; what are the differences?

Seems like these methods use octrees, and balancing/pairing do not matter!

https://www.cs.carleton.edu/cs_comps/0405/shape/marching_cubes.html

https://paulbourke.net/geometry/polygonise/

https://www.cs.rice.edu/~jwarren/papers/dmc.pdf

https://people.engr.tamu.edu/schaefer/research/dualsimp_tvcg.pdf

[mrbuche]

Marching cubes seems relatively easy compared to something like dual contouring. @hovey maybe we can start with marching cubes in order to get something faster for us to play with when working on other features (STL writing, surface smoothing, volume meshing, etc.) and get something faster to users? And work on a more robust isosurface generator afterwards?

[mrbuche]

Seems that neither balancing nor pairing are necessary, but it might be necessary to ensure that all cells touching materials other than themselves are fully refined to ensure that all interfaces consist of only voxel-sized cells. Hence #284.

[hovey]

Marching cubes seems relatively easy compared to something like dual contouring. @hovey maybe we can start with marching cubes in order to get something faster for us to play with when working on other features (STL writing, surface smoothing, volume meshing, etc.) and get something faster to users? And work on a more robust isosurface generator afterwards?

@mrbuche yes MC first sounds like a great next step, then DC.

[mrbuche]

@hovey maybe we cannot apply marching cubes, at least directly. In those cases they have point fields, which for us would be if the vertices in the segmentation were the materials rather than the voxels. So we could treat the voxels as vertices (their centers) and apply marching cubes to that, which might be like applying it to the dual of the segmentation.

Or we could start with dual marching cubes, placing an isosurface point at the center of cells where the boundary lies. Since we would not really want them right at the center of cells (would be shrinking volumes), dual contouring lets you move them away from the centers based on some rules. Probably things like the actual shape and maybe something for smoothness?

So maybe it would actually be easier to do dual marching cubes from the start? Not sure, still learning. This seems to think that then going to dual contouring is even easier:

https://github.com/andygeers/DualMarchingCuboids/

And then I guess the manifold dual contouring is just more rules to ensure everything is manifold?

I also don't see how to keep the octree around without refining near the boundaries, these papers seem to indicate you don't need to do that.

But then apply regular marching cubes to the dual of the segmentation (whether or not you actually construct a dual segmentation) seems to lend itself more naturally to reproducing the boundaries without shrinking, and even smoothing them a little? (One argument for dual marching cubes in place of marching cubes seems to be the representation of sharp features, but it seems like we want to blunt those sharp features at the end of the day).

I think we have some homework and discussion ahead of us! Probably can do a lot in 2D.

[mrbuche]

here are some plane thoughts:

all these options seem more relevant for a SCALAR point field, not a discrete segmentation

dual marching cubes in this case seems equivalent to just faces on the existing boundaries between materials in the segmentation

the octree gives us a way to adaptively form the iso surfaces

if the octree is balanced, the quads creating a interior surfaces should form a balanced quadtree manifold

we can then apply the rules for tri meshing a quadtree to form the STL

and then hopefully our low pass filter can produce nice smooth surfaces

our original problem of smoothing stair-stepped boundaries with hierarchical smoothing is gone since we dont have volume element qualities to worry about

[hovey]

Notes and links:

• https://www.boristhebrave.com/2018/04/15/dual-contouring-tutorial/ Boris the Brave tutorial on MC and DC.
• https://github.com/Lin20/isosurface implementation to solve the manifold problem with DC.
• https://www.mattkeeter.com/projects/contours/ DC with an octree
• https://docs.blender.org/manual/de/dev/modeling/modifiers/generate/remesh.html Blender remesh

[hovey]

@mrbuche great questions, and I hope we can discuss in video soon.

[hovey]

the octree gives us a way to adaptively form the iso surfaces

if the octree is balanced, the quads creating a interior surfaces should form a balanced quadtree manifold

we can then apply the rules for tri meshing a quadtree to form the STL

and then hopefully our low pass filter can produce nice smooth surfaces

@mrbuche is this workflow then as follows:

oct -> quad -> stl

then taubin(stl) -> stl'

I also made some notes

[mrbuche]

Yes I think that workflow sums up what I was thinking, it seems that since we already have a segmentation a lot of the complications are already gone, right?

We can have a parallel effort that looks at how smoothing performs on these surfaces too. We can make a few in Cubit or something and see how the results behave, I imagine it's going to be mostly a function of how nice the initial segmentation interfaces look.