I've got a question about a good way to find the quickest algorithm for my problem:

problem: I've got a 3D cubical grid containing voxels that are either 1 or 0. It is stored as a flattened array. If multiple 1-voxels are neighboring each other, they form a cluster together. I want to detect clusters smaller than a given size (n).

current solution (slow):

For each 1-voxel, I'm doing a breadth first search to find how many neighbors it has, and how many neighbors the neighbors have, etc, until reaching a certain amount of neighbors (n).

this is horribly slow when setting n to my preferred amount n>50, because the total cube edge size is 64

Any different ways to do this that are not breadth first search? Everything is open: could even be something from computer vision like 3d pooling or whatever, but I'm a little stuck. Or am I better off trying to optimize my current approach? If interested, I posted my c# code in code review

Thanks a bunch in advance!

  • 1
    $\begingroup$ I know that octrees are sometimes used for this purpose but unfortunately I am not aware of any non-industrial documents about it. $\endgroup$ – Abdullah Ali Sivas Mar 12 '20 at 22:09
  • $\begingroup$ @AbdullahAliSivas sounds interesting and relevant. Will do some research and post findings here if any $\endgroup$ – SumakuTension Mar 13 '20 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.