时间戳

首页 > 解决方案 > 使用泛洪方法创建 2D 圆

unity3d - 使用泛洪方法创建 2D 圆

问题描述

我正在尝试生成看起来像这样的地形轮廓线： 在此处输入图像描述

我的最终目标是根据一些用户定义的点生成等高线（例如：这座山海拔 100m，坡度为 X）。

目前，我生成高度图的算法是一种径向洪水填充，其中每个点设置其当前高度，然后将其 8 个邻居（包括对角线）排入队列以将其高度设置为当前高度 - 坡度的值。heightmap 是一个二维数组，表示地图上每个 x/y 点的高度。sqrt_2 是 2 的平方根的值，我们乘以对角线邻居的斜率值来表示它们与当前点的真实距离。每个点还向外传播其斜率（高度向默认高度移动的速率。EnqueueIfValidPoint 只是将一个点添加到 points_to_assign 队列中。这个想法是从我们知道高度的某些点开始，然后慢慢倾斜/梯度朝向默认高度（在这种情况下为 0）。points_to_assign 是一个常规的 FIFO 队列。

这段代码是在 Unity 中用 C# 编写的，但语言并没有改变其背后的逻辑。

// Continue the flood fill until we're out of points to assign
while (points_to_assign.Count > 0)
{

    PointToAssign p = points_to_assign.Dequeue();

    // Check if we have already assigned a height to this point
    if (heightmap[p.x_pos, p.y_pos] == unassigned_height)
    {
        assigned_points++;
        // Assign a height to this point
        heightmap[p.x_pos, p.y_pos] = p.height;


        // Height to assign neighbours to, moved towards default floor value
        double slope = p.slope;//GetRandomSlope(p.x_pos, p.y_pos, p.slope);

        double orthogonal_heights = 0;
        if (p.height >= 0)
            orthogonal_heights = Math.Max(0, p.height - (slope));
        else
            orthogonal_heights = Math.Min(0, p.height + (slope));
        // Enqueue neighbours of this point to assign a new height to
        // Below
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos, orthogonal_heights, p.slope);
        // Above
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos, orthogonal_heights, p.slope);
        // Left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos - 1, orthogonal_heights, p.slope);
        // Right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos + 1, orthogonal_heights, p.slope);

        double diagonal_heights = 0;
        if (p.height >= 0)
            diagonal_heights = Math.Max(0, p.height - (slope * sqrt_2));
        else
            diagonal_heights = Math.Min(0, p.height + (slope * sqrt_2));
        // Below and left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos - 1, diagonal_heights, p.slope);
        // Below and right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos - 1, diagonal_heights, p.slope);
        // Above and left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos + 1, diagonal_heights, p.slope);
        // Above and right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos + 1, diagonal_heights, p.slope);
    }
}

然后将高度值传递给分配颜色的颜色函数，例如：如果高度在 0 和 1 之间，则将其分配为白色，如果在 1 和 2 之间，则将其分配为浅绿色，等等。

不幸的是，这段代码并没有完全产生圆形，而是产生了一个八边形。我想这个问题与编码对角相邻值有关 在此处输入图像描述

有谁知道如何使用我的洪水填充策略制作一个圆圈而不是八边形？

标签： unity3dgeometrycontourterrain

解决方案

问题是，当您混合两种步长类型（对角线和正交）时，您会得到错误的距离。例如，正交步长 + 对角线步长导致实际距离为sqrt(5) ~ 2.24。但是你的算法给了你1 + sqrt(2) ~ 2.41。这就是圆被切断的原因。

您需要做的是计算与种子点的实际距离。只需将种子点与队列中的项目一起存储（或者如果只有一个，则使用这个）并根据距离计算高度。伴随着一些东西：

heightmap[p.x_pos, p.y_pos] = distance(p.seedPoint, p) * p.slope + p.seedPoint.height;

您还可以在外部存储种子点及其斜率，并在队列中引用它以节省一些内存。

也可以通过累积 x-difference 和 y-difference 来增量计算欧几里得距离，然后只计算sqrt(x-difference^2 + y-difference^2). 但这可能不值得付出努力。

推荐阅读