Flood filling of 3-dimensional polygon

Question

here is a problem for you ;)

I have a 3-dimensional array filled with 1s and 0s. The 1s represent 3 dimensional complex polygons ( not simple polygons ). Only the boundaries of the polygons have the value 1, the inside is filled with 0s. Now here is the problem:

I need a fast algorithm to flood-fill these polygons with 1s. The arrays usually have a dimension of approx. 512x512x100.

Thanks in advance!

Here is an example in 2d:

0000111110000
0000100010000
0000100010000
0000111110000

should result in

0000111110000
0000111110000
0000111110000
0000111110000

---

is this the correct 3 dimensional solution for @Mikolas algorithm?

    void scan_polygon(int frames, int rows, int cols, char data[][][], char result[][][]){
for(int f=0; f < frames; ++f)
for(int r=0; r<rows; ++r)
for(int s = 0, c=0; c<cols-1; ++c)
{
    s ^= s ? ( data[f][r][c] && !data[f][r][c+1]) :
             (!data[f][r][c] &&  data[f][r][c-1]);

    result[f][r][c] = s;
}

for(int f=0; f < frames; ++f)
for(int c=0; c<cols; ++c)
for(int s = 0, r=0; r<rows-1; ++r)
{
    s ^= s ? ( data[f][r][c] && !data[f][r+1][c]) :
             (!data[f][r][c] &&  data[f][r-1][c]);

    result[f][r][c] &= s;
}

}

Best regards,

stef

Answer 1

You can do it in a single for loop, if you assume that your polygon is manifold. Just start at the upper left corner, and keep track of the parity as you cross an edge.

A simple 2D version (with transpose case added in):

void scan_polygon(int rows, int cols, char** data, char** result)
{
    for(int r=0; r<rows; ++r)
    for(int s = 0, c=0; c<cols-1; ++c)
    {
        s ^= s ? ( data[r][c] && !data[r][c+1]) :
                 (!data[r][c] &&  data[r][c-1]);

        result[r][c] = s;
    }


    for(int c=0; c<cols; ++c)
    for(int s = 0, r=0; r<rows-1; ++r)
    {
        s ^= s ? ( data[r][c] && !data[r+1][c]) :
                 (!data[r][c] &&  data[r-1][c]);

        result[r][c] &= s;
    }
}

Where this can break down is if you have a dangling pixel or edge poking out along a scan line, for example:

00000000000000000000        
00000000*11111111111   <--- Whoops!
000000*111*000000000
00000*11111*00000000

To fix this, you can just repeat the process on a transposed array, then AND all the results together. A similar approach has been used by Sud et al to voxelize meshes on the GPU. It isn't flawless, since you can have configurations of multiple non-manifold vertices where the noisy cones from them intersect, but if you can guarantee that won't happen (or else if it only happens rarely), it is one of the simplest methods that I know of to get a quick result.

EDIT: Modified solution to show how to AND the arrays back together after doing the iteration.