algorithm - 分辨率提高时如何计算网格点的位置？

Question

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

_{（来源：sonic.net）}

显然，这种网格由一组点表示，它们之间的线实际上是使用该组点确定的（可能以某种方式插值）。该仪器还具有增加网格分辨率的按钮。

我的问题如下——这类事情是如何计算的？假设我有一组实际代表网格的点（为简单起见，我们甚至假设“边界”上的点是静态的并且不能移动）。我想增加网格分辨率，例如 4 倍（这样网格点的数量实际上变成了4 * initial_points_count）。

如果我拥有的唯一数据是初始点矩阵，我应该如何计算新点的位置？

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

谢谢你。

Answer 1

对现有答案的评论：

在我看来，Mau 和 martient 的回答描述了用多边形网格逼近已知形式的问题的解决方案（而且你没有已知的形式）。

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

如果您查看您的答案，您会发现新点来自点之间的线性插值，如果这对您来说足够好，那么所有解决方案都是可比较的（戴夫的除外）。

网格密度的这种增加不会使生成的网格看起来“更好”——更类似于原始形式。如果这还不够好，那么您首先必须确定您尝试用网格表示的实际形式/形状是什么（如果您可以扩展您的示例，它可能会更明显；这个工具是否只创建圆形网格或者它可以采用任何形状并“填充”它？）。

此外，您应该注意到您不使用多边形网格，而是使用曲线网格（可能是bezier），这是某些答案不会直接适用于您的问题的另一个原因。

编辑： 在仔细研究 corel 如何做到这一点并假设您实际上不仅知道曲线（！）之后：

• 你从一组曲线开始，在我看来你有水平和垂直曲线开始
• 如果你想提高分辨率（例如水平分辨率），你可以取两条连续的垂直曲线并将它们通过的水平曲线的每一段在中点分开，从而创建一组定义新曲线的点；您还可以插入曲线通过该点的角度

替代文字 http://img706.imageshack.us/img706/5693/path5818.png

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

注意：根据您准备网格的算法，将网格线视为曲线可能会或可能不会有任何好处（红色和蓝色解决方案之间的差异对于某些算法可能可以忽略不计，而对于其他算法很重要）。如果算法只是期望点，那么您还应该查看如何用点近似贝塞尔曲线（通读这可能会有所帮助；尽管您不需要像素精度）。

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

Answer 2

你看过 细分吗？应该适用于这样的细化网格。

Answer 3

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

编辑

这是实现网格平滑的几种方法/算法的简短摘要：http ://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_surf3.pdf

Answer 4

我将首先通过插值在所有线上添加中间点（图中的曲线很可能是某种贝塞尔曲线，所以我会像这样对它们进行插值，或者按照 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

Answer 5

听起来像是双线性插值的工作（坐标系在球体表面上）。