使用泛洪法创建二维圆
Creating a 2D circle with a flood approach
我正在尝试生成如下所示的地形等高线:
我的最终目标是根据几个用户定义的点生成等高线(例如:这座山海拔 100 米,坡度为 X)。
目前,我生成高度图的算法是一种径向洪水填充,其中每个点设置其当前高度,然后将其 8 个邻居(包括对角线)排入队列以将其高度设置为当前高度 -斜率的值。 heightmap 是一个二维双精度数组,表示地图上每个 x/y 点的高度。 sqrt_2是2的平方根的值,我们乘以对角线邻居的斜率值来表示它们到当前点的真实距离。每个点也向外传播它的斜率(高度向默认高度移动的速率。EnqueueIfValidPoint 只是向 points_to_assign 队列添加一个点。这个想法是从我们知道高度的某些点开始,并且慢慢地 slope/gradient 达到默认高度(在本例中为 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 之间,则将其分配为浅绿色,等等。
不幸的是,这段代码并没有生成圆,而是生成了一个八边形。我想这个问题与编码对角线邻居值有关
有谁知道如何使用我的填充策略生成一个圆而不是八边形?
问题是当您混合使用两种步进类型(对角线和正交)时,您得到的距离是错误的。例如,正交步长 + 对角线步长导致实际距离 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)
。但这可能不值得付出努力。
我正在尝试生成如下所示的地形等高线:
我的最终目标是根据几个用户定义的点生成等高线(例如:这座山海拔 100 米,坡度为 X)。
目前,我生成高度图的算法是一种径向洪水填充,其中每个点设置其当前高度,然后将其 8 个邻居(包括对角线)排入队列以将其高度设置为当前高度 -斜率的值。 heightmap 是一个二维双精度数组,表示地图上每个 x/y 点的高度。 sqrt_2是2的平方根的值,我们乘以对角线邻居的斜率值来表示它们到当前点的真实距离。每个点也向外传播它的斜率(高度向默认高度移动的速率。EnqueueIfValidPoint 只是向 points_to_assign 队列添加一个点。这个想法是从我们知道高度的某些点开始,并且慢慢地 slope/gradient 达到默认高度(在本例中为 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 之间,则将其分配为浅绿色,等等。
不幸的是,这段代码并没有生成圆,而是生成了一个八边形。我想这个问题与编码对角线邻居值有关
有谁知道如何使用我的填充策略生成一个圆而不是八边形?
问题是当您混合使用两种步进类型(对角线和正交)时,您得到的距离是错误的。例如,正交步长 + 对角线步长导致实际距离 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)
。但这可能不值得付出努力。