2d - 将高度图映射到基于网格的轮廓格式

Question

已结束。此问题正在寻求书籍、工具、软件库等的推荐。它不满足 Stack Overflow guidelines 。目前不接受答案。

---

我们不允许提出寻求书籍、工具、软件库等推荐的问题。您可以编辑问题，以便用事实和引文来回答。

已关闭 4 年前。

Improve this question

我有以下格式的 2D 高度图

06 36 39 42 43 55 ... 
37 40 43 43 45 46 ...
40 43 44 45 46 48 ...
44 44 46 47 48 50 ...
41 44 45 47 48 48 ...
...

我需要将其重新映射为基于咧嘴笑的轮廓格式(以便它可以进一步映射为 Sprite )

. . . . | . . 
. . . . \ . . 
. . . / / . . 
. . . | . . . 
. . . | . . . 
. / - / . . . 

这里.意思是平坦面积，|和-笔直的悬崖，/和\悬崖角(每个角代表 2 种不同的可能性)。

我尝试过标准的行进方 block 方法，但发现仅对 3 个邻居进行采样会导致很多问题，因为相邻情况会重载。 (注意下面额外不合适的直悬崖)

. . . . | . \ 
. . . . \ \ .
. . . / / - .
. . . | - . .
. . . | . . .
. / - / . . .

我想要的是一些有助于处理此类事情的算法/方法的引用。我知道使用某种深度优先搜索进行轮廓行走是一种选择，但尚未尝试过，并且更愿意将其作为最后的手段。还有一些特征的表示问题，例如是否包含 1 个元素厚的悬崖山脊或忽略它们。另一种选择是通过生成的轮廓并更改它们，使它们顺利地组合在一起，但这看起来真的很黑客......

Answer 1

创建插值/最佳拟合函数。您的模型应该是一个二维多项式(在 x 和 y 中)，其次数“恰到好处”:不会太高，以免过度拟合所有内容，但也不会太低，以免丢失细节。

您现在有了一个可以切片的数学函数，通过设置 f(x,y) = height 。该方程的解是轮廓。您现在有两个选择，具体取决于您是否可以分析求解。

• 假设您无法解析求解，您仍然可以轻松地找出曲线的近似值:
  • 首先将网格着色为白色，如果 f(x,y)>height和黑色如果 f(x,y)<height 。请注意所有“过渡”区域，其中大约 <1 个网格内有黑白过渡:这些是轮廓所在的正方形。
  • 随机选择一个过渡方 block ，并在大约 <1 网格半径内搜索 f(x,y)==height ，找到轮廓上的点。此时(不一定在网格上)我们计算梯度 ∇f(x,y) = (∂f/∂x, ∂f/∂y) (“上坡向量”)。我们将其向任一方向旋转 90 度:(∂f/∂y, -∂f/∂x) :这种方式沿着轮廓指向。我们非常缓慢地(步长远小于网格)追踪轮廓。这将带我们一路围绕轮廓。
  • 每次我们在此跟踪过程中经过网格框时，我们都会将其标记为 {|,-,/,}，具体取决于梯度平均值指向哪个方向。 (如果尚未标记邻居，我们还必须将它们标记为 .；请参阅 [*]。)
  • 请注意，此后可能仍会留下过渡网格框!例如，如果有两座山，您将填充一个圆圈，但轮廓是两个圆圈。在另一个随机(未标记)“过渡”网格盒上重复上述过程(这就是我们需要 [*] 的原因，否则我们可能会关注我们已经考虑的点的邻居)。重复此操作，直到不再有未标记的“过渡”网格框。
  • 对每个 height 执行此操作-您希望绘制为轮廓的级别，就完成了。
• 您也许能够像求解圆锥曲线一样进行分析求解，但这可能不太可能，并且超出了本问题的范围。如果您可以求解曲线，则可以使用各种技术对其进行“网格化”(例如，对其进行参数化，然后使用可能是半个网格的步长沿着轮廓行走，注意最近的邻居)

(如果您的一个轮廓与另一个轮廓重叠，则轮廓高度之间的间距太小。如果您对给定的轮廓不满意，则可能性集 {-,|,/,} 太小。)