贝塞尔曲线评估

Question

我在这里使用 de Casteljau 算法http://www.cgafaq.info/ wiki/B%C3%A9zier_curve_evaluation 并且我尝试使用主题 在 C++、OpenGL 中使用 De Casteljau 算法绘制贝塞尔曲线 提供帮助。没有成功。

我的贝塞尔曲线在评估时看起来像这样

正如你所看到的，即使它没有达到我想要的效果，所有点确实都在曲线上。我不认为这个算法因此就不准确。

以下是我在该图像顶部曲线上的观点： (0,0) (2,0) (2,2) (4,2) 第二条曲线使用同一组点，但第三个点是 (0,2)，即比第一个点高两个单位，形成更陡的曲线。

有问题。我应该为 t 输入 0.25，它应该为 X 值输出 1.0，而 .75 应始终返回 3。假设 t 是时间。它应该以恒定的速度进步，是吗？恰好 25% 处，X 值应为 1.0，然后 Y 应与该值关联。

有没有适当的方法来评估贝塞尔曲线？有谁知道这是怎么回事？

感谢您的帮助！ :)

编辑------

我在谷歌搜索中找到了这本书http://www.tsplines.com/resources/class_notes/Bezier_curves.pdf 这是我在显式/非参数贝塞尔曲线上找到的页面曲线。它们是表示为贝塞尔曲线的多项式，这就是我在这里想要的。这是书中的页面：

有人知道如何将贝塞尔曲线转换为参数曲线吗？我现在可能会打开一个不同的线程...

自 2011 年 11 月 1 日起再次编辑------

我意识到我只问了这个问题一半的问题。我正在尝试构建类似于 Maya 的动画图形编辑器，例如 http: //www.youtube.com/watch?v=tckN35eYJtg&t=240 其中用于修改曲线的贝塞尔控制点较多就像等长度的切线修饰符一样。老实说，我不记得它们的长度相等。通过强制使用这样的系统，您可以 100% 确保结果是一个函数并且不包含重叠的段。

我找到了这个，这可能有我的答案 http://create.msdn .com/en-US/education/catalog/utility/curve_editor

Answer 1

在这里，您可以按照链接中的命名法查看 Mathematica 中实现的算法，以及你的两个图：

(*Function Definitions*)

lerp[a_, b_, t_] := (1 - t) a + t b;
pts1[t_] := {
   lerp[pts[[1]], pts[[2]], t],
   lerp[pts[[2]], pts[[3]], t],
   lerp[pts[[3]], pts[[4]], t]};
pts2[t_] := {
   lerp[pts1[t][[1]], pts1[t][[2]], t],
   lerp[pts1[t][[2]], pts1[t][[3]], t]};
pts3[t_] := {
   lerp[pts2[t][[1]], pts2[t][[2]], t]};

(*Usages*)

pts = {{0, 0}, {2, 0}, {2, 2}, {4, 2}};
Framed@Show[ParametricPlot[pts3[t], {t, 0, 1}, Axes -> True], 
            Graphics[{Red, PointSize[Large], Point@pts}]]

pts = {{0, 0}, {2, 0}, {0, 2}, {4, 2}};
Framed@Show[ParametricPlot[pts3[t], {t, 0, 1}, Axes -> True], 
            Graphics[{Red, PointSize[Large], Point@pts}]]

顺便说一句，曲线由以下参数定义方程，它们是上面代码中的函数 pts3[t]：

c1[t_] := {2 t (3 + t (-3 + 2 t)), (* <- X component *)
                 2 (3 - 2 t) t^2}  (* <- Y component *)

并

c2[t_] := {2 t (3 + t (-6 + 5 t)), (* <- X component *)
               , 2 (3 - 2 t) t^2}  (* <- Y component *)

尝试绘制它们！

采用任何这些曲线方程，并通过求解三次多项式，在这些情况下您可以得到 y[x] 的表达式，这当然并不总是可能的。只是为了让您体验一下它，从您得到的第一条曲线（C 语法）：

y[x]= 3 - x - 3/Power(-2 + x + Sqrt(5 + (-4 + x)*x),1/3) + 
              3*Power(-2 + x + Sqrt(5 + (-4 + x)*x),1/3)

尝试绘制它！

编辑

只是一个娱乐：

Mathematica 是一种非常强大的函数式语言，事实上整个算法可以表示为一行：

f = Nest[(1 - t) #[[1]] + t #[[2]] & /@ Partition[#, 2, 1] &, #, Length@# - 1] &

如

f@{{0, 0}, {2, 0}, {0, 2}, {4, 2}}

上面给出结果，但支持任意数量点。

让我们尝试使用六个随机点：

p = RandomReal[1, {6, 2}];
Framed@Show[
  Graphics[{Red, PointSize[Large], Point@p}],
  ParametricPlot[f@p, {t, 0, 1}, Axes -> True]]

此外，相同的函数也适用于 3D：

p = RandomReal[1, {4, 3}];
Framed@Show[
  Graphics3D[{Red, PointSize[Large], Point@p}],
  ParametricPlot3D[f[p], {t, 0, 1}, Axes -> True]]

Answer 2

贝塞尔曲线可以通过求解 x、y 和 z 坐标的以下参数方程来求解（如果只是 2D，则仅求解 x 和 y）：

Px = (1-t)^3(P1x) + 3t(1-t)^2(P2x) + 3t^2(1-t)(P3x) + t^3(P4x)
Py = (1-t)^3(P1y) + 3t(1-t)^2(P2y) + 3t^2(1-t)(P3y) + t^3(P4y)
Pz = (1-t)^3(P1z) + 3t(1-t)^2(P2z) + 3t^2(1-t)(P3z) + t^3(P4z)

您还可以通过乘以矩阵方程 ABC = X 来求解，其中

1. ： A 是一个 1x4 矩阵，表示 t 矩阵的幂的值
2. B 是 t 幂的系数，是一个下三角 4x4 矩阵
3. 矩阵 C 是一个 4x3 矩阵，表示 3D 空间中的四个贝塞尔点中的每一个（它将是 2D 空间中的 4x2 矩阵），

如下所示：

（更新 - 左下角 1 应该是 -1）

两种形式的方程（参数和矩阵）的重要说明形式）的原因是 t 在 [0, 1] 范围内。

与其尝试求解 t 的值，而是给出 x 和 y 的整数值，这将非常耗时如果您基本上是在求解 3 次多项式的实根，那么最好在您的 t 值中创建一个足够小的微分，这样曲线上任意两点之间的差为小于像素值增量。换句话说，两点 P(t1) 和 P(t2) 之间的距离小于像素值。或者，您可以在 t 中使用更大的差异，并在 P(t1) 和 P(t2) 之间简单地进行线性插值，请记住如果 P(t1) 和 P(t2) 之间的差异对于给定的 t< 范围不够小，则曲线可能不“平滑” /code> 来自 [0, 1]。

从视觉角度来看，找到 t 中必要的微分以创建相当“平滑”的曲线的一个好方法是实际测量定义贝塞尔曲线的四个点之间的距离。测量 P1 到 P2、P2 到 P3 以及 P3 到 P4 的距离。然后取最长距离，并使用该值的倒数作为 t 的微分。您可能仍然需要在点之间进行一些线性插值，但每个“线性”子曲线中的像素数量应该相当小，因此曲线本身会显得相当平滑。您始终可以从该初始值减小 t 上的微分值，使其“更平滑”。

最后回答一下你的问题：

假设 t 是时间。它应该以恒定的速度进步，是吗？恰好 25% 处，X 值应为 1.0，然后 Y 应与该值关联。

不，这是不正确的，原因是向量 (P2 - P1) 和 (P3 - P4) 不仅与 P1 和 P4 处的贝塞尔曲线相切，而且它们的长度定义了速度 也沿着曲线在这些点处。因此，如果向量 (P2 - P1) 距离很短，则意味着在给定的时间 t 内，您不会距离 P1 点很远……这转化为 x对于给定的固定微分t，沿曲线的 y 值非常紧密地组合在一起。当您向 P1 移动时，您的速度实际上“减慢”了。根据矢量的长度 (P3 - P4)，曲线上的 P4 处也会发生相同的效果。沿着曲线的速度是“恒定”的唯一方法，因此 t 的公共微分的任何点之间的距离将是相同的，如果所有三个段的长度（ P2-P1)、(P3-P2)和(P4-P3)相同。这表明沿着曲线的速度没有变化。

Answer 3

听起来您实际上只想要一维三次贝塞尔曲线，而不是您拥有的二维贝塞尔曲线。具体来说，您真正想要的只是一个从 0 开始并在 0 到 4 的域上计算时达到 2 的三次多项式段。因此，您可以使用一些基本数学并找到多项式：

f(x) = a + b*x + c*x^2 + d*x^3
f(0) = 0
f(4) = 2

这留下了两个自由度.
取函数的导数：

f'(x) = b + 2*c*x + 3*d*x^2

如果你希望它在开始时很陡峭，然后在最后趋于平稳，你可能会这样说：

f'(0) = 10
f'(4) = 0

然后我们可以插入值。 a 和 b 是免费的，因为我们的评估为零。

a = 0
b = 10

那么我们就有了：

f(4) = 2 = 40 + c*16 + d*64
f'(4) = 0 = 10 + c*8 + d*48

这是一个非常容易解决的线性系统。为了完整起见，我们得到：

16c + 64d = -38
 8c + 48d = -10

因此

1/(16*48 - 8*64)|48 -64||-38| = |c| = |-37/8 |
                |-8  16||-10|   |d|   |  9/16|

f(x) = 10*x - (37/8)*x^2 + (9/16)*x^3

，如果您决定使用 Bezier 控制点，只需选择 4 个 y 值控制点并认识到这一点，即可在 [0 中获得 t ,1]，您只需说 t=x/4 （请记住，如果您还需要导数，则也必须在那里进行更改）。

---

补充：

如果你碰巧知道你想要开始和结束的点和导数，但你想使用贝塞尔曲线控制点P1，P2，P3< /strong> 和 P4，映射就是这样的（假设曲线参数化为 0 到 1）：

P1 = f(0)
P2 = f'(0)/3 + f(0)
P3 = f(1) - f'(1)/3
P4 = f(1)

如果出于某种原因，您想坚持使用 2D Bezier 控制点并希望确保认为随着 t 从 0 前进到 1，x 维度从 0 线性前进到 2，那么您可以使用控制点 (0,y1) (2/3 ，y2）（4/3，y3）（2，y4）。您可以看到，我刚刚将 x 维度设置为从 0 开始，到 2 结束，并且斜率（导数）恒定为 2（相对于 t）。然后你只需将 y 坐标设置为你需要的任何坐标即可。不同的维度本质上是相互独立的。

Answer 4

经过这么长时间，我一直在寻找隐士曲线。 Hermites 很好，因为在一维中，它们可以保证生成一条可以评估为 XY 点的函数曲线。我把 Hermites 和 Bezier 搞混了。

Answer 5

“假设时间到了。”

这就是问题所在——时机未到。曲线有自己的 t 变化率，具体取决于切线的大小。正如 Jason 所说，后续点之间的距离必须相同，t 的顺序才能与时间相同。这正是 Maya 曲线编辑器中的非加权模式（默认使用）。所以这是关于如何解决这个问题的完美答案。要使其适用于任意切线，必须将时间转换为 t。您可以通过计算 x（或时间）方向的贝塞尔方程来找到 t。

Px = (1-t)^3(P1x) + 3t(1-t)^2(P2x) + 3t^2(1-t)(P3x) + t^3(P4x)

Px 是你的时间，所以你了解这里的一切，但是t。您必须解三次方程才能找到根。不过，找到您需要的确切根有一个棘手的部分。然后求解另一个方程以找到 Py（您正在寻找的实际值），现在知道 t：

Py = (1-t)^3(P1y) + 3t(1-t)^2(P2y) + 3t^ 2(1-t)(P3y) + t^3(P4y)

这就是 Maya 中的加权曲线。
我知道这个问题很老了，但是我花了一整天的时间来研究这个简单的事情，而且没有人准确解释发生了什么。否则，计算过程本身就写在很多地方，例如 Maya API 手册。 Maya 开发工具包也有一个源代码来执行此操作。