基于距另一点的距离在贝塞尔曲线上找到点

Sae*_*bin 5 3d bezier distance spline

因此,我有一个3D立方贝塞尔曲线和沿曲线任意位置找到的起点,需要找到曲线下方的第二个点,即距离第一个点的特定世界空间距离(不是弧长距离).

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

有任何想法吗?

Dav*_*ary 2

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

我非常确定给定贝塞尔曲线上与某个给定点的给定线性距离的最大点数是 4 个点。(当给定的贝塞尔曲线具有自相交时,可能会发生这种情况)。

编辑:

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

== de Casteljau 反过来 ==

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

== 找零 ==

您可以将四点表示转换为三次多项式表示,并使用任何求根算法收敛到所需点之一。牛顿方法应该效果很好,因为贝塞尔曲线的短段几乎是直的。我们能否将查找点与三次样条之间的最小距离中的牛顿法方程应用于 这个问题?为了简化描述,我将使用二分算法,尽管它的运行速度比牛顿方法慢。

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

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3.
Run Code Online (Sandbox Code Playgroud)

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

我假设您有(或可以找到)给定点的 t_given 值,

x_given = B(t_given).x
y_given = B(t_given).y
Run Code Online (Sandbox Code Playgroud)

给定点与曲线上其他点之间的距离由毕达哥拉斯定理给出,

distance2(t) = ( x_given - B(t).x )^2 + ( y_given - B(t).y )^2.
distance(t) = sqrt(distance2(t)).
Run Code Online (Sandbox Code Playgroud)

您正在寻找的点位于函数的零点处

given_distance2 = given_distance^2.
f(t) = distance2(t) - given_distance2.
Run Code Online (Sandbox Code Playgroud)

假设给定距离不为零,并且给定点的 t_given < 1,二分算法将运行如下所示

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

此时,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
Run Code Online (Sandbox Code Playgroud)

接下来我们检查:第一段 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 )
Run Code Online (Sandbox Code Playgroud)

此时,“right”值为t的值,B(right)为对应点,这样该点到原始给定点的距离就是(近似)给定距离。