c++ - 从轮廓线生成高度图的算法是什么？

Question

我正在寻找插入一些轮廓线以生成 3D 视图。轮廓不存储在图片中，轮廓的每个点的坐标都简单地存储在 std::vector 中。

对于凸轮廓：

，似乎（我自己没有检查）通过使用两个最近轮廓的两个最近点之间的距离可以轻松计算高度（线性插值）。

我的轮廓不一定是凸的：

，所以它更棘手......实际上我不知道我可以使用什么样的算法。

更新：2013 年 11 月 26 日

我写完了一个离散拉普拉斯例子：

你可以在这里得到代码

Answer 1

你所拥有的基本上是经典的狄利克雷问题：

给定空间区域边界上的函数值，将值分配给区域内部的函数，使其满足特定方程（例如拉普拉斯方程，它本质上要求函数没有任意“凸点” “）在内部的任何地方。

有很多方法可以计算 Dirichlet 问题的近似解。一种应该非常适合您的问题的简单方法是从离散化系统开始；也就是说，您采用有限的高度值网格，为位于等高线上的那些点分配固定值，然后为剩余点求解拉普拉斯方程的离散版本。

现在，拉普拉斯方程实际上明确规定的是，每个点的值都应该等于其邻居的平均值。 在方程的数学公式中，当邻域的半径趋于零时，我们要求它在极限内成立，但由于我们实际上是在有限格上工作，所以我们只需要选择一个合适的固定邻域。一些合理的社区选择包括：

• 围绕中心点的四个正交相邻点（又名冯诺依曼邻域），
• 八个正交和对角相邻的网格点（又名摩尔邻域），或
• 八个正交和对角相邻的网格点，加权使得正交相邻的点被计算两次（本质上是上述两个选择的总和或平均值）。

（在上面的选择中，最后一个通常产生最好的结果，因为它最接近高斯核，但前两个通常几乎一样好，并且计算速度可能更快。）

一旦你选择了一个邻域并定义了固定的边界点，就该计算解决方案了。为此，您基本上有两种选择：

1. 定义一个线性方程组，每个（无约束）网格点一个，说明每个点的值是其邻居的平均值，然后求解。如果您可以使用良好的稀疏线性系统求解器，这通常是最有效的方法，但从头开始编写一个可能具有挑战性。

2. 使用迭代方法，您首先为每个不受约束的网格点分配任意初始猜测（例如，按照您的建议，使用线性插值），然后在网格上循环，用其邻居的平均值替换每个点的值。然后继续重复此操作，直到值停止变化（很大）。

Answer 2

您可以生成描述轮廓的顶点和线段的约束 Delaunay 三角剖分，然后使用在每个顶点处定义的高度作为 Z 坐标。

然后可以像任何其他三角形汤一样渲染生成的三角剖分。

尽管名称如此，但您可以使用TetGen来生成三角测量，尽管设置起来需要一些工作。