Memory effective flood fill

[Antharon]

Hello people, from selfish reason, first feature from voxel filters, that I want to implement is hole filling algoritm.

I already canibalised robs script for extraction of voxel box from file and started to play with it. First problem is, that I need to implement flood fill. There is a huge problem. I quickly written 3d version of it, run program and of course I overflown call stack with recursive calls (every pixel produced six more calls recursivelly).

Is there a efective memory safe implementation?

[X3msnake]

@Reonarudo @Rob2048 @NardJ @Andoryuuta Any ideas om this Masters?

[NardJ]

@Antharon How did you implement flood fill? Recursive or stack based?

[Antharon]

standard recursion

BinaryVoxelCube.prototype.flood = function(x,y,z,color,keepOldVoxel){
  if(z<0 || x<0 || y<0 || x>=this.sizeX || y>=this.sizeY || z>=this.sizeZ) {
    return;
  }
  if(keepOldVoxel){
    ret=this;
  } else {
    ret=new BinaryVoxelCube(this.sizeX,this.sizeY,this.sizeZ,this.voxelData);
  }
  if(ret.getVoxel(x,y,z-1)!=color){
    ret.flood(x,y,z-1,color,true);
  }
  if(ret.getVoxel(x,y,z+1)!=color){
    ret.flood(x,y,z+1,color,true);
  }
  ret.setVoxel(x,y,z,color);
  if(ret.getVoxel(x-1,y,z)!=color){
    ret.flood(x-1,y,z,color,true);
  }
  if(ret.getVoxel(x+1,y,z)!=color){
    ret.flood(x+1,y,z,color,true);
  }
  if(ret.getVoxel(x,y-1,z)!=color){
    ret.flood(x,y-1,z,color,true);
  }
  if(ret.getVoxel(x,y+1,z)!=color){
    ret.flood(x,y+1,z,color,true);
  }

  return ret;
}

[NardJ]

@Antharon, I think you could benifit from a stack based approach,some prseudocode I found on Dutch wiki page:

floodfill (x, y, choosencolor, substcolor){
    stack.push(x, y)

    while (stack is not empty)    {
        (x, y) = stack.pop

        if (kleur(x, y) == choosencolor)        {
            change_color(x, y, substcolor)
            stack.push(x, y + 1)
            stack.push(x, y - 1)
            stack.push(x + 1, y)
            stack.push(x - 1, y)
        }
    }
}

[Reonarudo]

I think the wiki( https://en.wikipedia.org/wiki/Flood_fill#Large-scale_behaviour) page is quite informative providing a view into data-centric and process-centric approaches.

[NardJ]

@Antharon Did you succeed and may we close this issue?

[Antharon]

I came to my own implementation that does not overflow the memory, but it is very slow (bilions of pixels are too much). I added one more bit array to store information about pixels that are to be flooded. At start I put there first pixel, then I cycle through that array searching for pixels to flood. Each one of them is colored to target color, and then I look at neighbors and if they are to be flooded I put them into pending array. In small scale it works, but in bigger scale I need to improve it a lot. Right now I can parse it at very sad speed :(

next week I want to try put it into octree and use that to optimize it a lot, but it is a lot of work and study. Also, I still do not know how to export it back into photon file.

[X3msnake]

Does #61 help in this?

[NardJ]

Looking at the succes of Ivan's branch with gyroid infill, I think we can close this :-)