c++ - 3维多边形的洪水填充

Question

这是给你的问题;)

我有一个用 1 和 0 填充的 3 维数组。 1 代表 3 维复杂多边形(不是简单多边形)。只有多边形的边界值为 1，内部填充为 0。现在问题来了:

我需要一个快速的算法来用 1 填充这些多边形。阵列通常具有大约的尺寸。 512x512x100。

提前致谢!

这是一个二维的例子:

0000111110000
0000100010000
0000100010000
0000111110000

应该导致

0000111110000
0000111110000
0000111110000
0000111110000

---

这是@Mikolas 算法的正确 3 维解决方案吗？

    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;
}

最好的问候，

牛

Answer 1

如果您假设您的多边形是多边形的，则可以在单个 for 循环中完成。只需从左上​​角开始，并在越过边缘时跟踪奇偶校验。

一个简单的 2D 版本(添加了转置大小写):

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;
    }
}

如果你有一个悬垂的像素或沿扫描线突出的边缘，这可能会崩溃，例如:

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

要解决此问题，您只需在转置数组上重复该过程，然后将所有结果加在一起。 Sud 等人已使用类似的方法在 GPU 上对网格进行体素化。它不是完美无缺的，因为您可以配置多个非流形顶点，其中来自它们的嘈杂锥体相交，但如果您可以保证不会发生(或者如果它很少发生)，它就是其中之一我所知道的可快速获得结果的最简单方法。

编辑:修改后的解决方案，以展示如何在进行迭代后将数组重新组合在一起。