5

因此，我有一个 3D 三次贝塞尔曲线和一个沿曲线任意位置的起点，并且需要在曲线下方找到第二个点，该点与第一个点相距特定的世界空间距离（不是弧长距离）。

另一个问题是，如果第二个点到达曲线的末端并且仍然不在所需的世界空间距离，在这种情况下，我希望它沿着切线继续，直到达到距离。

有任何想法吗？

4

2 回答 2

2

唉，我不知道任何封闭形式的方程给你你想要的点。近似该点的最简单技术可能是使用de Casteljau 算法将贝塞尔曲线递归地切割成 2 条较小的贝塞尔曲线 。当 (a) 曲线的所有边界点都离给定点太近或太远，或 (b) 曲线的所有边界点“足够接近”以等于所需的距离（也许它们都适合同一个像素）。

我很确定给定贝塞尔曲线上与某个给定点的给定线性距离的最大点数是 4 个点。（当给定的贝塞尔曲线具有自相交时，就会发生这种情况）。

编辑：

也许我应该在回答之前阅读整个问题，是吗？标准的“四点”贝塞尔曲线段可以看作是一条无限长的三次曲线。在一个位置可能存在弯曲、环或尖点，但距离该尖锐曲线足够远，路径会变平以接近 2 条直线，每条直线都指向某个任意方向。唉，上面的解决方案只能找到短贝塞尔曲线段上的点。我假设您想要沿无限长三次曲线的点，这些点距给定点的给定距离，即使它们不在短贝塞尔曲线段上。

== de Casteljau 反向 ==

您可以反向运行（递归中点）de Casteljau 算法，在每次迭代中生成一条新的四点贝塞尔曲线，将最​​后一条贝塞尔曲线的大小“加倍”，直到获得一个足够大以包含所需点的曲线。（当所有4个初始点都“太接近”给定点时，那么加倍保证最终产生一个起点“太近”，终点“太远”的曲线段，然后你可以使用上面的算法收敛到与给定点相距所需距离的点上）。这种方法仅依赖于加法、减法、乘以 2 和平均，因此原则上它应该在数值上相对稳健。（它从未实际评估任何位置 t 的三次公式）。

== 找零 ==

您可以从四点表示转换为三次多项式表示，并使用任何求根算法收敛于所需点之一。牛顿的方法应该工作得很好，因为贝塞尔曲线的一小段几乎是笔直的。我们能否将牛顿法方程从 寻找点和三次样条之间的最小距离中调整 到这个问题？为了描述的简单，我将使用二等分算法，尽管它比牛顿法运行得慢。

与往常一样，三次贝塞尔曲线段可以描述为

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3.

（不幸的是，这个方程在数值上并不总是稳健的——这就是为什么许多人使用 de Casteljau 的算法来使用递归减半的原因）。

我假设您有（或可以找到）给定点的 t_given 值，

x_given = B(t_given).x
y_given = B(t_given).y

给定点与曲线上其他点之间的距离由勾股定理给出，

distance2(t) = ( x_given - B(t).x )^2 + ( y_given - B(t).y )^2.
distance(t) = sqrt(distance2(t)).

您要查找的点位于函数的零点

given_distance2 = given_distance^2.
f(t) = distance2(t) - given_distance2.

假设给定距离不为零，并且给定点的 t_given < 1，二等分算法将运行类似

left = t_given
right = 1 // the endpoint of the given Bezier curve segment
while( distance2(right) < given_distance2 ){
    right = right*2
}

此时，t_left 比所需距离更接近给定点，而 t_right 比所需距离更远（或者可能完全相等）。由于我们有一个点太近，另一个点太远，所以二分算法应该可以工作。

while( (abs(f(right) is too big) AND (abs(left - right) is too big) ){
    // find midpoint
    midpoint = (t_left + t_right)/2

接下来我们检查：第一段 left...midpoint 是否包含零，或者 midpoint...right ？

    if( f(left)*f(midpoint) < 0 ) then
        // throw away right half
        right = midpoint
    else
        // throw away left half
        left = midpoint
}

return( right )

此时，“右”值为t的值，B(right)为对应点，使得该点到原始给定点的距离为（近似）给定距离。

于 2010-09-13T17:03:41.560 回答
1

您的问题陈述需要更细化。具体来说，当您要求距离起点 A 有 N 个单位的某个点 B 时，您受到的约束不足。可能有多个点与 A 的距离为 N。

除了阻止您沿曲线以设定的间隔对曲线进行采样，然后计算返回到 A 的线性距离之外，这不是最佳的，但它会起作用。要处理 N 距离之外的多个点，您必须想出一个规则。可能就像找到的第一点一样简单。

于 2010-09-12T20:01:51.900 回答