Improving SDF segmentation...

[tyson...@gmail.com]

I'm using the existing tools::segmentSDF function to split disjoint areas of an SDF into multiple SDFs, however the result isn't very good....for areas in the SDF's isosurface that are clearly disjoint, the segmentation function may fail to separate them due to the separate isosurface areas sharing narrow band voxels...in other words, even if there is visible isosurface separation, the SDF may not be segmented in an area if the voxels of the 'separate' areas are too close together. I'm assuming this is due to how the mask for the segmentation function is generated from active voxels.

I wonder if anyone has tried any other approaches to segment SDFs in a way that is consistent with how their isosurfaces are formed?

I'm imagining an alternative scenario where you take a random point with a negative value inside an SDF, use some kind of flood fill technique to mask out all voxels connected to it with values up to and including 0 and then detach those voxels to a separate grid and remove the voxels from the original grid...and repeat until there are no voxels left in the original grid. In my mind that would overcome the existing problem of the segmentation algorithm. However, I'm not really sure how to set something like that up....

Any thoughts or help is appreciated.

[tyson...@gmail.com]

I've had some luck by doing the following:

1) Erode SDF

2) Segment eroded SDF

3) Dilate segments

4) Perform CSG intersection between original SDF and eroded/dilated segments.

Have to tune the erosion/dilation pretty carefully to avoid losing sharp edges after the intersection operation...but this gets better results than the raw segmentSDF function...however, it's also a lot slower due to the added erosion/dilation function calls...

Would still like to know if there's a way to collect contiguous negative cells in a grid....that would skip this whole workaround and allow me to extract disjoint SDF areas with perfect accuracy. If anyone knows how to do that I'd appreciate any pointers in the right direction....

[Nick Avramoussis]

Hi,

I think the easiest solution here is to base the segment result purely on the inside narrow band rather than the zero crossing. Something like this:

https://github.com/Idclip/openvdb/tree/feature/segmentsdf

The diff: https://github.com/AcademySoftwareFoundation/openvdb/commit/da32a87b394e61cc339c5f81a1958f76cc6ab21d

I very quickly tried this out and it seems to solve the issue. I think I may also need to dilate the inside band at least once (which this diff currently doesn't do) to account for issues where the band sits on a leaf node's boundary, but otherwise I think this would work.

Cheers,

Nick

[tyson...@gmail.com]

Thanks for taking a look at this Nick,

I copied your diff over and the result is....interesting to say the least. This image speaks for itself...no post-segment artifacts are visible prior to your changes:

Any ideas why this is happening? I haven't yet added the dilation you mentioned, but this seems like a bigger issue than that.

[Nick Avramoussis]

Oof well that's not good. I see the issue though, the algorithm which determines active mask segmentation only considers face neighbours. By removing the zero crossing and only considering the inside band we end up with some voxels whose only neighbours are diagonal. The active mask segmentation then proceeds to make hundreds of unique grids.

To fix this properly I would prefer that extractActiveVoxelSegmentMasks() took a neighbour pattern - for now I've just dilated the inside band to ensure faces are captured. I've updated the branch.

One note; even if we can get this to work perfectly there won't be enough exterior narrow band information to represent each level set. Currently all this algorithm does it detect the zero crossing and copy relevant distance data into each segment. If you consider a boundary like this: [I][O][I] (which I=inside and O=outside) then, even though we can split this into two segments, we will be outputting somewhat invalid levelsets if the input band is > 1. You'll have to follow this up with a rebuild/renormalization to ensure the SDFs are valid.

Cheers,

Nick

[tyson...@gmail.com]

Thanks Nick, I appreciate you iterating on this so quickly.

With large gaps between segments I now get expected results (equivalent to what I was getting before your changes).

With small gaps however, I still get a lot of artifacts that are not solved by an SDF rebuild....

[Nick Avramoussis]

Just to check, you're at least now getting two segments when they are close, but each segment has various visible artifacts? I believe this is to do with the logic in ExpandNarrowbandMask() which attempts to re-activate the relevant narrow band topology relative to each segment. This logic doesn't take into account neighbouring signs, so as long as the absolute value of a neighbouring distance is larger it is included in the segment. This can result in values which belong to a different segment ending up in others.

I've fixed this up and am getting cleaner results - but it's still not guaranteed to give you completely valid SDFs out the box when the boundary sizes are less than 2xthe half width - you will have to continue to rely on a renormalize/rebuild/narrow-band-resize. I think there are more improvements that can be made but at this point I'm considering re-writing it. The way I'd approach this would be:

 1) Same as the current algorithm: compute the inside iso surface band masks from the input SDF and topologically split them.
 2) Compute the expected narrow band size of our new segments based on the input. Alternatively a desired size could be provided.
 3) For each mask:
   3a) dilate (by the narrow band size)
   3b) Re activate the interior of our mask where the input SDF is active
   3c) Union a+b masks into a new float grid and copy over values. For the exterior narrow band, only copy POSITIVE values. If the value isn't positive, set it to positive background and deactivate it.
   3d) Flood fill.

Not something I'm able to do at the moment but hope these changes and suggestions help

[tyson...@gmail.com]

Hey Nick,

Whatever you did in this latest update did the trick! It's working absolutely flawlessly in my tests now (even in much more complex tests featuring many tiny details and very irregularly shaped segments). Thanks for taking the time to look further into this issue and provide a working solution!

[Nick Avramoussis]

Great to hear! I've also tested this on some more complex geo and observed the many smaller details - I think these are coming from what I originally observed with regards to how the active mask segment code only considers face neighbours. So if you have something like (sorry about the formatting):

[O][ I ][ I ][ I ]
[O][O][ I ][O]
[O][ I ][O][O]

[O][O][O][O]

It'll create two pieces (top right/bottom left). There's not enough resolution in the surface for point sampling to determine if they should be connected or not so this behaviour is somewhat expected (otherwise we'd have to do more complicated sampling) - but it might be useful to be able to specify a neighbourhood pattern or tolerance for when these smaller pieces should be considered connected. I'll consider tidying this up and making a PR anyway.