Flood filling of 3-dimensional polygon

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 =开发者_StackOverflow 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

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.

I think that a standard floodfill approach could be used in this case:

active_cells = [seed]
while active_cells:
    new_active_cells = []
    for cell in active_cells:
        for nh in neighbor(cell):
            if not filled(nh):
                fill(nh)
                new_active_cells.append(nh)
    active_cells = new_active_cells

if you are not sure that the interior or the exterior are connected (and therefore it's not possible to find a single "seed") then what you can do is iterating over all cells, and once you find a cell with a zero then you can call the above floodfill code to compute the connected component. Repeating it for other cells found to be zero you will end up with all the connected regions that the faces are partitioning the space in.

Of course for the above code to be working it's required that the faces are tight in respect to the chosen connectivity.