2

I want to create a function that can quickly 'paint' a volume in a 3D binary array.

The first approach I tried was extending a standard flood-fill algorithm into 3D, which was easy to do but I was interested in making it faster. I read into how to optimize the flood-fill algorithm and found the 'scanline' flood-fill algorithm. Implementing this into 2D gave me great results. I wanted to extend this into 3D but it was not clear to me how to do this while maintaining the spirit of scanline by minimising the number of voxel checks.

I have searched for an existing implementation or explanation of scanline in 3D, but found nothing on it. I managed to extend the algorithm by essentially splitting the 3D grid into 2D planes and performing the scanline 2D function on each slice. This is an improvement but I feel like there's a better way.

Can scanline be extended into 3D, or is there a better approach entirely to all of this?

A B
  • 21
  • 1
  • 2
    My first hunch would be that it is exactly like the 2D version. Just instead of only checking the top and bottom row for new seeds, you additionally check front and back row. – Nico Schertler Jul 09 '20 at 19:09
  • I implemented this, and can confirm that it works! But there is no apparent performance increase, which is disappointing, and leads me to believe that I need to be using a kind of 'scanbox' algorithm? What I mean by this is, seeding 2D areas instead of 1D.. though I'll admit I haven't entirely figured out how to do this or whether it would perform better! – A B Jul 12 '20 at 18:23

0 Answers0