当分辨率增加时，如何计算网格点的位置？

Question

假设我们有一些网格（请参见CorelDraw的说明图片，该软件使用相同的技术在“网格填充”工具中）。

_{(来源：sonic.net)}

显然，这种类型的网格是由一组点表示的，它们之间的线条实际上是使用这组点（可能在某种程度上插值）确定的。此工具还有增加网格分辨率的按钮。

我的问题是 - 这样的算法是如何计算的？假设我有一些点集，实际上代表一个网格（为了简单起见，甚至可以假设“边界”上的点是静态的且不能移动）。 我想增加网格分辨率，例如4倍（因此网格点数实际上变为4 * initial_points_count）。

如果我只有初始点矩阵，应该如何计算新点的位置？

最快的（即使是近似的）方法都适合我，但我不知道在哪里搜索或如何开发这种算法。

谢谢。

- Yippie-Ki-Yay

---

这个“网格填充”功能适用于任何形状吗？还是只能为圆形创建网格？我不清楚它的工作原理。此外，颜色的意义是什么？ - Unreason

@Unreason 任何形状。在我的当前情况下，我实际上正在寻找一种增加矩形网格分辨率的方法。可能这个圆不是最好的例子... 实际上，我本可以在没有那张图片的情况下提出问题。 - Yippie-Ki-Yay

@Unreason 或许有一种方法可以实现这个“网格分辨率增加”（可以通过“平滑”来实现吗？）当我只有点坐标时，或者我是否必须构建某种这些曲线等，然后使用它们来插值新点的坐标？ - Yippie-Ki-Yay

关于矩形情况 - 考虑这样的情况，即点没有以直角方式定位（基本上，矩形内部的点可以采取任何位置，因此构建复杂曲线）。如果我有一个包含这些点的矩阵，我应该怎么做才能使我的网格分辨率更高（例如每平方英寸的点数）？ - Yippie-Ki-Yay

@Unreason 还有一点要提的是，据我现在的理解，网格平滑不是我要寻找的东西。我不想让我的网格“看起来更好”，我只是想实现更大的点密度（实际上是为了另一个算法）。 - Yippie-Ki-Yay

Answer 1

针对现有答案的评论：

我认为Mau和martient的答案描述了如何使用多边形网格来近似已知形状（而你没有已知形状）的解决方案。

Dave提到的算法可以平滑任何形状，但不一定以预期的方式。

如果您看一下You的答案，您会发现新点是从点之间的线性插值中得出的，如果这对您足够好，那么所有解决方案都是可比较的（除了Dave的方案）。

增加网格密度并不会使得结果网格看起来更“漂亮”或更接近原始形状。如果这还不够好，那么您首先必须确定您正在尝试用网格表示哪个实际的形状/图案（如果您可以扩展您的示例，它可能会更明显；这个工具只创建圆形网格还是可以采取任何形状并进行“网格填充”？）。

此外，您应该注意您不是在处理多边形网格，而是曲线网格（可能是贝塞尔曲线），这是为什么一些答案不能直接应用于您的问题。

编辑： 在更仔细地查看Corel如何执行此操作并假设您实际上不仅知道点，还知道曲线的情况下：

• 您从一组曲线开始，我认为您有水平和垂直曲线
• 如果要增加分辨率（例如水平分辨率），则可以取两个连续的垂直曲线，并将它们穿过的每个水平曲线段在中间点处分割，从而创建定义新曲线的一组点；您还可以插值曲线通过该点时的角度

alt text http://img706.imageshack.us/img706/5693/path5818.png

上面（手动绘制的）图片试图说明 a) 以这种方式生成的新曲线（红色）的添加。 b) 添加线性插值折线（蓝色），更接近多边形网格方法（因此您可以判断是否可以接受）

注意：根据您正在准备的网格算法，考虑网格线为曲线可能有利也可能无益（红色和蓝色解决方案的差异对于某些算法可能是微不足道的，而对于其他算法则可能很重要）。如果算法只需要点，则您还应查看如何使用点近似贝塞尔曲线（阅读此文可能会有所帮助；尽管您不需要像素精度）。

为了获得最高的精度/最佳结果，您应该先增加曲线的密度，然后用直线来近似它们。

- Unreason

---

@Dave，是的，我知道 - 需要等待OP澄清某些问题。 - Unreason

Answer 2

你看过细分曲面吗？它可以用于像这样细化网格的工作。

- martiert

Answer 3

你需要的是一个网格平滑算法。不幸的是，我手头没有任何资源，所以我只能建议你在谷歌上搜索“网格平滑”。这是一个巨大的领域。

以下是一些实现网格平滑的方法/算法的简短概述：http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf

- Dave O.

---

@HardCoder1986：我认为这不会得到你想要的结果-看一下http://en.wikipedia.org/wiki/Laplacian_smoothing，看看你能否实现它。 - Unreason

但是拉普拉斯平滑只是网格平滑的许多实现之一。我承认，我的提示对于初学者来说并不那么有价值。欢迎在这个主题上发布好的资源。 - Dave O.

@Dave：这只是一个例子，用来展示平滑算法会使轮廓/边缘退化。 - Unreason

@Unreason 并不是每个算法都会这样做。有一些方法将输入网格的顶点视为特征并保留它们。 - Dave O.

@Dave，它仍然会使轮廓/边缘线性退化（或以其他方式）。我想指出给OP知道他从形状/轮廓的完美信息开始（贝塞尔曲线段），而平滑方法将使其退化。另一方面，OP确实指定可用输入仅为“网格点矩阵”，因此您的答案尊重了这一点，只是我认为OP实际上并不想要 - 所以我是主观的，但OP同意（目前）。 - Unreason

@Unreason 是的，你说得对。即使是保留特征的方法也会退化为平滑的凸壳，但需要进行很多次迭代才能实现。 - Dave O.

Answer 4

我会从在所有线条上添加一半的点开始，通过插值（插图中的曲线很可能是某种Bézier曲线，所以我会用这种方式进行插值，或者像Mau建议的那样使用双线性插值），并将新点放置在旧点之间的一半处，从而使分辨率增加3倍。然后我会在这些新点之间插值（如果精度关键则两种方式都需要），并在交点（或一半处）放置一个新点。请参见下面的“插图”。

Initial state  =>  Interpolate  =>  Place points  =>  Interpolate => Final state
  x       x         x-------x        x   x   x         x   x   x      x   x   x
                    |       |                              |    
                    |       |        x       x         x---+---x      x   x   x
                    |       |                              |
  x       x         x-------x        x   x   x         x   x   x      x   x   x

- You

Answer 5

好像需要使用双线性插值（其中坐标系在球面表面上）来完成。

- Mau