Defeaturing

[mrbuche]

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

Segmentations sometimes contain small volumes (small groups of voxels) that should optionally be defeatured.

Describe the solution you'd like

Option to defeature volumes that contain less than <num, default=5 or 10> voxels.

• Volumes with less than voxels are reassigned to the 'predominant neighboring material'.
• Similarly for voxels surrounded by 4 or 5 voxels of other material(s).
• Would multiple defeaturing iterations be needed?
• Can you exactly match results from Sculpt as a test?

NOTE: Could the octree implementation help with this? No balancing or pairing required!

Describe alternatives you've considered

Something like recon3d might take care of this beforehand, but possibly not.

Additional context

Is generally useful to pre-process the segmentation this way before meshing.

[mrbuche]

• Read segmentation file.
• Construct octree.
  • Do not pair, but do weakly balance.
    • Otherwise looking at neighboring faces gets too complicated?
  • Every leaf is a single material thanks to Octree::from_voxels().
• Construct volumes.
  • A volume is a set of sequence of face-sharing leaves.
    • Is my neighbor a leaf?
      • Yes: is it same material or not?
      • No: check the 4 children that share the same face.
        • Since the octree is weakly balanced, those should be leaves.
      • Need to make sure it already isn't in the current volume somehow!
  • Make a Vec of the leaves within the octree called Leaves.
  • Pop a leaf from Leaves into a new volume Vec.
  • Use neighboring faces to find neighbor leaves, moving them from Leaves into the volume.
    • Moving rather than copying ensures that volumes aren't repeated by starting from different leaves within the same volume. Also prevents volumes from sharing leaves, but that should happen anyway.
  • Once done with a leaf in the volume, repeat for each leaf in the volume.
    • Pushing them to the back will facilitate this naturally.
  • Once done with volume, start a new one with the next leaf in Leaves, repeat the above.
• Defeature the volumes.
  • If any volume has less than specified minimum voxels:
    • Every leaf is homogeneous, so the number of voxels is 8^k.
    • .iter().map(|leaf| 8.powi(max_levels - 1 - leaf.level)).sum() on the volume Vec.
    • Change the volume material to "predominant neighboring material".
      • What does that mean exactly?
  • Does this have to be iterated on, similar to balancing?
• Mesh the volumes. Either:
  • The octree is dualized.
  • The octree is converted back into a segmentation, which is meshed.
    • Need to implement Voxels::from_octree().

Can you ignore the larger leaves from the beginning, unless there is a good reason to always do all the volumes? What else could they be useful for? Option for separate blocks for all non-contiguous volumes? Option to generate nodesets and sidesets? Surface reconstruction algorithms? Thickening? Something else?

[mrbuche]

https://github.com/autotwin/automesh/tree/defeature

[mrbuche]

Seems that strong balancing is needed for an unknown reason...

[mrbuche]

Iterations are necessary due to 2 schemes for adding cells to the clusters, meaning both schemes have to be performed without adding anything new before moving on to the next volume. Definitely slow, but not as slow as sculpt, due to Octree and Rust.

Option to remove blocks (like block 0, the void) before constructing clusters saves time and effort. First iteration for a given cluster takes the longest as it tends to get most of the voxels into the cluster.

Without removing void:

     Reading book/examples/spheres_cont/spheres_resolution_4.npy
        Done 6.378369ms
           ⤷ Octree initialization 384.9458ms 
             Balancing iteration 1 56.9696ms 
             Balancing iteration 2 15.969627ms 
             Balancing iteration 3 13.708178ms 
             Balancing iteration 4 13.337893ms 
             Balancing iteration 5 13.051105ms 
             Block 0 cluster 1 iteration 1 10.772669086s 
             Block 0 cluster 1 iteration 2 83.833904ms 
             Block 1 cluster 2 iteration 1 4.922562022s 
             Block 1 cluster 2 iteration 2 55.622806ms 
             Block 3 cluster 3 iteration 1 8.209509445s 
             Block 3 cluster 3 iteration 2 147.689936ms 
             Block 2 cluster 4 iteration 1 1.73404119s 
             Block 2 cluster 4 iteration 2 36.041421ms

With removing void:

Reading book/examples/spheres_cont/spheres_resolution_4.npy
        Done 5.951297ms
           ⤷ Octree initialization 405.498922ms 
             Balancing iteration 1 55.87287ms 
             Balancing iteration 2 14.828948ms 
             Balancing iteration 3 13.072569ms 
             Balancing iteration 4 12.942921ms 
             Balancing iteration 5 12.452673ms 
             Block 1 cluster 1 iteration 1 4.596145742s 
             Block 1 cluster 1 iteration 2 52.282313ms 
             Block 3 cluster 2 iteration 1 7.687706485s 
             Block 3 cluster 2 iteration 2 140.031461ms 
             Block 2 cluster 3 iteration 1 1.687660183s 
             Block 2 cluster 3 iteration 2 34.605832ms 

[mrbuche]

It may be advantageous to make separate Vecs for leaves of different blocks instead of one Vec of all the leaves, if the binary search is the bottleneck. @hovey see how long these are taking (tens of seconds), definitely the new bottleneck. Hopefully we can find some fancy ways to speed it up, although it should already be a lot faster than sculpt.

[mrbuche]

With separate Vecs of leaves for each block, the total time gets cut from about 24s to about 6s, a 75% reduction.

     Reading book/examples/spheres_cont/spheres_resolution_4.npy
        Done 6.075673ms
           ⤷ Octree initialization 402.018848ms 
             Balancing iteration 1 56.410447ms 
             Balancing iteration 2 14.793795ms 
             Balancing iteration 3 12.667263ms 
             Balancing iteration 4 12.206972ms 
             Balancing iteration 5 11.974126ms 
             Clusters creation instigation 66.578018ms 
             Block 0 cluster 1 iteration 1 1.314191846s 
             Block 0 cluster 1 iteration 2 24.347942ms 
             Block 1 cluster 2 iteration 1 368.035936ms 
             Block 1 cluster 2 iteration 2 14.583754ms 
             Block 2 cluster 3 iteration 1 1.660781625s 
             Block 2 cluster 3 iteration 2 36.971809ms 
             Block 3 cluster 4 iteration 1 2.359477663s 
             Block 3 cluster 4 iteration 2 82.919263ms

[mrbuche]

Need to actually implement defeaturing the clusters, as well as converting Octrees back into Voxels for either segmentation output or meshing it directly.

Also need to understand (4,5) rule and reassigning materials nearby

https://cubit.sandia.gov/files/cubit/16.10/help_manual/WebHelp/mesh_generation/meshing_schemes/parallel/sculpt_improvement.htm#defeature

[mrbuche]

Octree is too expensive (memory) for very large segmentations (1 billion voxels), usually when it cannot remove the void.

Either need more memory on machine, or avoid those cases, or have internal option to use a new voxel-based defeaturing implementation that is probably what sculpt uses.

[mrbuche]

Some questions regarding what defeaturing iterations mean.

[mrbuche]

@hovey here is the defeaturing example you thought of, works now with that missing part added. The goopy part becomes skull, the color change is misleading.

Before:

After:

[hovey]

@mrbuche that looks awesome! Nice work! Is this example simple enough that it could be included as a test? It would be nice to have this example in the documentation too, just with the colors updated. Thanks!

[mrbuche]

We can probably get some dummy microstructures from the open source world to test on and put in the docs

[hovey]

@mrbuche that sounds promising, maybe as a backup if our friend AP doesn't have an open source example already that we can use :-)

[mrbuche]

@hovey the Cells within Octree now have 4 numbers (min_(x,y,z) and length) in place of the original 7 (min(x,y,z), max(x,y,z), level). They also all use u16 (2 bytes) instead of f64 (8 bytes), which still gets us to about 10 trillion voxels max, which should be more than enough. The integer operations seem to offer some moderate overall speedups (maybe like 5%) compared to the floats. The changes only reduced the size of a Cell in memory by 20%, but it seems to be enough to build the octree for 1 billion voxels without running out of memory.

It's actually quite surprising, before it would max out my memory (134 GB) when building the octree for 1 billion voxels. With the changes, it needs less than 20 GB. So even though the memory-per-cell savings were small, Rust seems to need far less memory for some reason.

The expensive parts of Cell are the 6 usizes in faces and the 8 usizes in cells. We might be able to make them references to Cells which seems to get to about %50 total reduction from before.