按程序生成“blob”的好方法二维图形

Question

我希望以计算快速的方式创建一个“blob”。这里的斑点被定义为可以是任何形状但全部相连的像素的集合。示例：

.ooo....  
..oooo..  
....oo..  
.oooooo.
..o..o..  

...ooooooooooooooooooo...  
..........oooo.......oo..  
.....ooooooo..........o..  
.....oo..................  


......ooooooo....  
...ooooooooooo...  
..oooooooooooooo.  
..ooooooooooooooo  
..oooooooooooo...  
...ooooooo.......  
....oooooooo.....  
.....ooooo.......  
.......oo........  

哪里 .是死区，o 是标记像素。我只关心“二进制”生成 - 像素要么打开，要么关闭。例如，这些看起来像一些想象中的番茄酱或虚构的细菌或任何有机物质。

什么样的算法可以实现这一点？我真的很茫然

Answer 1

David Thonley 的评论是正确的，但我假设你想要一个具有“有机”形状和光滑边缘的斑点。为此，您可以使用元球。元球是一种作用于标量场的幂函数。标量场可以通过行进立方体算法有效地渲染。通过改变球的数量、位置和半径可以形成不同的形状。

有关 2D 元球的介绍，请参阅此处：https://web.archive.org/web/20161018194403/https://www.niksula.hut.fi/~hkankaan/Homepages/metaballs.html

这里有一个介绍行进立方体算法： https://web.archive.org/web/20120329000652/http://local.wasp.uwa.edu.au/~pbourke/geometry/polygonise/

请注意，交叉点的 256 种组合3D 中的组合只有 2D 中的 16 种组合。它很容易实现。

编辑：

我用 GLSL 着色器编写了一个快速示例。这是使用 50 个斑点以及 hkankaan 主页上的能量函数得到的结果。

这是实际的 GLSL 代码，尽管我评估了每个片段。我没有使用行进立方体算法。您需要渲染一个全屏四边形才能工作（两个三角形）。 vec3 统一数组只是通过 glUniform3fv 传递的各个斑点的 2D 位置和半径。

/* Trivial bare-bone vertex shader */
#version 150
in vec2 vertex;
void main()
{
    gl_Position = vec4(vertex.x, vertex.y, 0.0, 1.0);
}

/* Fragment shader */
#version 150
#define NUM_BALLS 50
out vec4 color_out;
uniform vec3 balls[NUM_BALLS]; //.xy is position .z is radius

bool energyField(in vec2 p, in float gooeyness, in float iso)
{
    float en = 0.0;
    bool result = false;
    for(int i=0; i<NUM_BALLS; ++i)
    {
        float radius = balls[i].z;
        float denom =  max(0.0001, pow(length(vec2(balls[i].xy - p)), gooeyness));
        en += (radius / denom);
    }
    if(en > iso)
        result = true;
    return result;
}
void main()
{
    bool outside;
    /* gl_FragCoord.xy is in screen space / fragment coordinates */
    outside = energyField(gl_FragCoord.xy, 1.0, 40.0);
    if(outside == true)
        color_out = vec4(1.0, 0.0, 0.0, 1.0);
    else
        discard;
}

Answer 2

这是一种方法，我们首先生成分段仿射马铃薯，然后通过插值对其进行平滑。插值思想基于采用 DFT，然后保留低频不变，在高频处用零填充，并采用逆 DFT。

以下代码仅需要标准 Python 库：

import cmath
from math import atan2
from random import random

def convexHull(pts):    #Graham's scan.
    xleftmost, yleftmost = min(pts)
    by_theta = [(atan2(x-xleftmost, y-yleftmost), x, y) for x, y in pts]
    by_theta.sort()
    as_complex = [complex(x, y) for _, x, y in by_theta]
    chull = as_complex[:2]
    for pt in as_complex[2:]:
        #Perp product.
        while ((pt - chull[-1]).conjugate() * (chull[-1] - chull[-2])).imag < 0:
            chull.pop()
        chull.append(pt)
    return [(pt.real, pt.imag) for pt in chull]


def dft(xs):
    pi = 3.14
    return [sum(x * cmath.exp(2j*pi*i*k/len(xs)) 
                for i, x in enumerate(xs))
            for k in range(len(xs))]

def interpolateSmoothly(xs, N):
    """For each point, add N points."""
    fs = dft(xs)
    half = (len(xs) + 1) // 2
    fs2 = fs[:half] + [0]*(len(fs)*N) + fs[half:]
    return [x.real / len(xs) for x in dft(fs2)[::-1]]

pts = convexHull([(random(), random()) for _ in range(10)])
xs, ys = [interpolateSmoothly(zs, 100) for zs in zip(*pts)]   #Unzip.

这会生成类似以下内容（初始点和插值）：

这是另一种尝试：

pts = [(random() + 0.8) * cmath.exp(2j*pi*i/7) for i in range(7)]
pts = convexHull([(pt.real, pt.imag ) for pt in pts])
xs, ys = [interpolateSmoothly(zs, 30) for zs in zip(*pts)]

这些偶尔会有扭结和凹陷。这就是这个斑点家族的本质。

请注意，SciPy 具有凸包和 FFT，因此上述函数可以用它们代替。

Answer 3

您可以设计算法来执行此操作，这些算法是一系列随机迷宫生成算法的较小变体。我会建议一种基于 union-find 方法。

联合查找的基本思想是，给定一组被划分为不相交（不重叠）子集的项目，快速识别特定项目属于哪个分区。 “并集”是将两个不相交的集合组合在一起形成一个更大的集合，“查找”是确定特定成员属于哪个分区。这个想法是，集合的每个分区都可以由集合的特定成员来标识，因此您可以形成树结构，其中指针从成员指向根。您可以通过首先查找每个分区的根，然后修改一个根的（以前为空）指针以指向另一个根，来合并两个分区（为每个分区指定一个任意成员）。

您可以将您的问题表述为不相交的并集问题。最初，每个单独的细胞都是它自己的一个分区。您想要的是合并分区，直到获得少量（不一定是两个）连接单元格的分区。然后，您只需选择一个分区（可能是最大的）并绘制它。

对于每个单元格，您将需要一个指针（最初为空）来进行合并。您可能需要一个位向量来充当一组相邻单元格。最初，每个单元都有一组四个（或八个）相邻单元。

对于每次迭代，您随机选择一个单元格，然后沿着指针链找到其根。在根的详细信息中，您可以找到其邻居集。从中选择一个随机成员，然后找到它的根，以识别相邻区域。执行并集（将一个根指向另一个根等）以合并两个区域。重复此操作，直到您对其中一个区域感到满意为止。

合并分区时，新根的新邻居集将是前两个根的邻居集的集合对称差（异或）。

当您增加每个根元素中的分区时，您可能需要维护其他数据（例如大小）。您可以使用它来更有选择性地继续某个特定的联盟，并帮助决定何时停止。分区中细胞分散的某些测量可能是相关的 - 例如，小的偏差或标准偏差（相对于大的细胞计数）可能表明密集的大致圆形斑点。

完成后，您只需扫描所有单元格来测试每个单元格是否是您选择的分区的一部分，以构建单独的位图。

在这种方法中，当您在迭代开始时随机选择一个单元格时，会强烈倾向于选择较大的分区。当您选择邻居时，也会倾向于选择较大的相邻分区。这意味着您往往会很快获得一个明显占主导地位的斑点。