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

发布于 2024-09-08 15:07:21 字数 761 浏览 5 评论 0 原文

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

_{（来源：sonic.net）}

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

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

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

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

谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

你的呼吸 2024-09-15 15:07:21

对现有答案的评论：

在我看来，Mau 和 martient 的答案描述了使用多边形网格（并且您没有已知的形式）。

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

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

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

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

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

您从一组曲线开始，在我看来，您可以从水平和垂直曲线开始
如果您想要要提高分辨率（例如水平分辨率），您可以采用两条连续的垂直曲线，并在中点处划分它们经过的水平曲线的每一段，从而创建一组定义新曲线的点;您还可以插入曲线通过点

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

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

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

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

Comments on existing answers:

It seems to me that Mau's and martient's answer describe a solution to problem of approximating a known form with polygon mesh (and you don't have a known form).

Algorithm that Dave mentions would smooth any form, but not necessarily in the intended way.

If you look at You's answer you will see that the new points come from linear interpolation between the points, and if that is good enough for you all solutions are comparable (except Dave's).

Such increase in the mesh density will not make the resulting mesh look any 'nicer' - more similar to original form. If that's not good enough then you first have to decide what is the actual form/shape that you are trying to represent with the mesh (if you could expand on your example it might be a bit more obvious; is this tool creating only circle meshes or it can take any shape and 'mesh fill' it?).

Also, you should notice that you don't work with a polygon mesh, but with mesh of curves (probably bezier), which is another reasons why some of the answers would not directly apply to your problem.

EDIT:
After looking more closely on how corel does this and assuming that you actually know the curves not only the points(!):

You begin with set of curves, and it seems to me that you have horizontal and vertical curves to begin with
If you want to increase the resolution (for example horizontal resolution), you could take two consecutive vertical curves and divide every segment of the horizontal curves they pass through at mid point thus creating a set of points that define the new curve; you could also interpolate the angle at which the curve passes through the point

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

The above (manually drawn) picture shows tries to illustrate
a) adding of the new curve (red) that you would generate in this way.
b) adding the linearly interpolated polyline (blue), that goes more towards polygon mesh approach (so you can judge if that is acceptable for you)

Note: Depending on the algorithm for which you are preparing the mesh you might or might not have any benefits in considering the mesh lines to be curves (difference between red and blue solutions might be negligible for certain algorithm and important for other). If the algorithm simply expect points then you should also look at how to approximate bezier curves with points (reading through this might help; though you don't need pixel precision).

For highest precision/best results you should first increase the density of curves and the approximate them with lines.

回复收藏 0 原文

帥小哥 2024-09-15 15:07:21

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

I would start by adding halfway points on all lines by interpolating (the curves in the illustration are most likely Bézier curves of some sort, so I would interpolate them as such, or use biliniear interpolation as Mau suggested) and placing new points halfway between the old ones, giving me 3 times the resolution. I would then interpolate between these new points (both ways if precision is key) and place a new point at the intersection (or halfway). See "illustration" below.

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

回复收藏 0 原文