3d - 根据与另一点的距离在贝塞尔曲线上查找点

Question

所以我有一个 3D 三次贝塞尔曲线和一个沿着曲线的任何地方找到的起点，需要在曲线下方找到第二个点，该点距离第一个点是特定的世界空间距离(不是弧长距离)。

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

有任何想法吗？

Answer 1

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

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

编辑:

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

== de Casteljau 反过来 ==

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

==找零==

您可以从四点表示转换为三次多项式表示，并使用任何求根算法收敛到所需点之一。
Newton 的方法应该很有效，因为 Bezier 曲线的一小段几乎是直的。
我们可以从
Finding the Minimum Distance Between a Point and a Cubic Spline
这个问题？
为简单起见，我将使用二分算法，尽管它比牛顿方法运行得慢。

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

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)为对应点，这样该点到原给定点的距离为(近似)给定距离。