如何将三次曲线的两个控制点转换为二次曲线的单个控制点?

4

在搜索网络时,我看到各种人在各种论坛中提到用二次曲线来近似三次曲线。但是我找不到公式。

我想要的是:

输入:startX,startY,control1X,control1Y,control2X,control2Y,endX,endY 输出:startX,startY,controlX,controlY,endX,endY

实际上,由于起点和终点相同,我只需要...

输入:startX,startY,control1X,control1Y,control2X,control2Y,endX,endY 输出:controlX,controlY


顺便提一下,如果你想要手动近似,可以在这里尝试:http://lib.ivank.net/?p=demos&d=bezier - Ivan Kuckir
8个回答

9

如前所述,从4个控制点到3个控制点通常会是一种近似。只有在立方贝塞尔曲线实际上是一个度数提高的二次贝塞尔曲线时,才会有一种情况是精确的。

您可以使用度数提高方程来得出近似值。这很简单,结果通常相当不错。

我们将立方体贝塞尔曲线的控制点称为Q0..Q3,二次贝塞尔曲线的控制点称为P0..P2。那么,对于度数提高,方程式为:

Q0 = P0
Q1 = 1/3 P0 + 2/3 P1
Q2 = 2/3 P1 + 1/3 P2
Q3 = P2

在您的情况下,您有Q0..Q3,并且您正在解决P0..P2的问题。根据上述方程式,计算P1有两种方法:
P1 = 3/2 Q1 - 1/2 Q0
P1 = 3/2 Q2 - 1/2 Q3

如果这是一个阶升三次方程,那么两个方程将会给P1相同的答案。但由于很可能不是,你最好的选择是将它们平均起来。因此,

P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3

为了让您更易理解:

controlX = -0.25*startX + .75*control1X + .75*control2X -0.25*endX

Y的计算方式类似 - 维度是独立的,所以在3D(或n-D)中也适用。

这将是一个近似值。如果您需要更好的近似值,一种方法是使用deCastlejau算法对初始立方体进行细分,然后降低每个线段的次数。如果您需要更好的连续性,则有其他逼近方法,但它们较为缓慢且不够简洁。


1
我主要参考的是我上过的CAGD课程:http://tom.cs.byu.edu/~557/text/ 第2章涵盖了Bezier曲线。 - tfinniga
请问,你是从哪里获得了这个 P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3 的公式?它运行得非常好... - Ecir Hana
@EcirHana 我通过对P1的另外两个方程取平均得到了这个方程。换句话说,如果我定义P1a = 3/2 Q1 - 1/2 Q0和P1b = 3/2 Q2 - 1/2 Q3,那么P1 = 1/2 (P1a + P1b)。如果我简化一下,就可以得到P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3。P1a和P1b是从上面的度数升高方程中推导出来的。 - tfinniga
你正在逼近一个“曲线函数”,而不是“曲线图像”。请参见此处:https://jsfiddle.net/o15qky2r/1/。有两个三次曲线(红色),根据你的公式计算的二次曲线(黄色)和更好的二次曲线(黑色)。 - Ivan Kuckir
是的,在几何和参数化方面,立方体距离升高一次的二次函数越远,这种简单近似就会越差。有很多逼近技术,它们各有优缺点 - 如果您将所使用的方法作为答案添加到此问题中,将会很有帮助。 - tfinniga

4
这个三次函数可以有环和尖点,而二次函数则不行。这意味着几乎没有简单的解决方案。如果三次函数已经是二次函数,则存在简单的解决方案。通常你需要将三次函数分成二次函数的部分,并决定哪些是用于细分的关键点。 http://fontforge.org/bezier.html#ps2ttf上说:“我在网上阅读的其他资料建议检查三次样条曲线的拐点(二次样条曲线不能有拐点),并在那里强制断点。但在我看来,这实际上使结果更糟糕了,它使用了更多的点,而且近似值看起来不如忽略拐点时那么接近。所以我忽略了它们。”
这是正确的,拐点(三次函数的二阶导数)是不够的。但是,如果你也考虑到局部极值(最小值、最大值),它们是三次函数的一阶导数,并在这些点上强制断点,那么所有的子曲线都是二次的,可以用二次函数表示。
我测试了下面的函数,它们按预期工作(找到三次函数的所有关键点并将其分为下降和上升的三次函数)。当这些子曲线被绘制时,曲线与原始的三次函数完全相同,但出于某种原因,当这些子曲线被绘制为二次函数时,结果接近正确,但并不完全正确。
因此,这个答案并不是严格解决问题的帮助,但这些函数提供了将三次函数转换为二次函数的起点。
为了找到局部极值和拐点,以下get_t_values_of_critical_points()应该能够提供它们。
function compare_num(a,b) {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

function find_inflection_points(p1x,p1y,p2x,p2y,p3x,p3y,p4x,p4y)
{
  var ax = -p1x + 3*p2x - 3*p3x + p4x;
  var bx = 3*p1x - 6*p2x + 3*p3x;
  var cx = -3*p1x + 3*p2x;

  var ay = -p1y + 3*p2y - 3*p3y + p4y;
  var by = 3*p1y - 6*p2y + 3*p3y;
  var cy = -3*p1y + 3*p2y;
  var a = 3*(ay*bx-ax*by);
  var b = 3*(ay*cx-ax*cy);
  var c = by*cx-bx*cy;
  var r2 = b*b - 4*a*c;
  var firstIfp = 0;
  var secondIfp = 0;
  if (r2>=0 && a!==0)
  {
    var r = Math.sqrt(r2);
    firstIfp = (-b + r) / (2*a);
    secondIfp = (-b - r) / (2*a);
    if ((firstIfp>0 && firstIfp<1) && (secondIfp>0 && secondIfp<1))
    {
      if (firstIfp>secondIfp)
      {
        var tmp = firstIfp;
        firstIfp = secondIfp;
        secondIfp = tmp;
      }
      if (secondIfp-firstIfp >0.00001)
        return [firstIfp, secondIfp];
      else return [firstIfp];
    }
    else if (firstIfp>0 && firstIfp<1)
      return [firstIfp];
    else if (secondIfp>0 && secondIfp<1)
    {
      firstIfp = secondIfp;
      return [firstIfp];
    }
    return [];
  }
  else return [];
}

function get_t_values_of_critical_points(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y) {
    var a = (c2x - 2 * c1x + p1x) - (p2x - 2 * c2x + c1x),
    b = 2 * (c1x - p1x) - 2 * (c2x - c1x),
    c = p1x - c1x,
    t1 = (-b + Math.sqrt(b * b - 4 * a * c)) / 2 / a,
    t2 = (-b - Math.sqrt(b * b - 4 * a * c)) / 2 / a,
    tvalues=[];
    Math.abs(t1) > "1e12" && (t1 = 0.5);
    Math.abs(t2) > "1e12" && (t2 = 0.5);
    if (t1 >= 0 && t1 <= 1 && tvalues.indexOf(t1)==-1) tvalues.push(t1)
    if (t2 >= 0 && t2 <= 1 && tvalues.indexOf(t2)==-1) tvalues.push(t2);

    a = (c2y - 2 * c1y + p1y) - (p2y - 2 * c2y + c1y);
    b = 2 * (c1y - p1y) - 2 * (c2y - c1y);
    c = p1y - c1y;
    t1 = (-b + Math.sqrt(b * b - 4 * a * c)) / 2 / a;
    t2 = (-b - Math.sqrt(b * b - 4 * a * c)) / 2 / a;
    Math.abs(t1) > "1e12" && (t1 = 0.5);
    Math.abs(t2) > "1e12" && (t2 = 0.5);
    if (t1 >= 0 && t1 <= 1 && tvalues.indexOf(t1)==-1) tvalues.push(t1);
    if (t2 >= 0 && t2 <= 1 && tvalues.indexOf(t2)==-1) tvalues.push(t2);

    var inflectionpoints = find_inflection_points(p1x, p1y, c1x, c1y, c2x, c2y, p2x, p2y);
    if (inflectionpoints[0]) tvalues.push(inflectionpoints[0]);
    if (inflectionpoints[1]) tvalues.push(inflectionpoints[1]);

    tvalues.sort(compare_num);
    return tvalues;
};

当你拥有那些关键的 t 值(范围在 0-1 之间)时,你可以将立方体分成几部分:

function CPoint()
{
  var arg = arguments;
  if (arg.length==1)
  {
    this.X = arg[0].X;
    this.Y = arg[0].Y;
  }
  else if (arg.length==2)
  {
    this.X = arg[0];
    this.Y = arg[1];
  }
}

function subdivide_cubic_to_cubics()
{
    var arg = arguments;
    if (arg.length!=9) return [];
    var m_p1 = {X:arg[0], Y:arg[1]};
  var m_p2 = {X:arg[2], Y:arg[3]};
  var m_p3 = {X:arg[4], Y:arg[5]};
  var m_p4 = {X:arg[6], Y:arg[7]};
  var t = arg[8];
  var p1p = new CPoint(m_p1.X + (m_p2.X - m_p1.X) * t,
                       m_p1.Y + (m_p2.Y - m_p1.Y) * t);
  var p2p = new CPoint(m_p2.X + (m_p3.X - m_p2.X) * t,
                       m_p2.Y + (m_p3.Y - m_p2.Y) * t);
  var p3p = new CPoint(m_p3.X + (m_p4.X - m_p3.X) * t,
                       m_p3.Y + (m_p4.Y - m_p3.Y) * t);
  var p1d = new CPoint(p1p.X + (p2p.X - p1p.X) * t,
                       p1p.Y + (p2p.Y - p1p.Y) * t);
  var p2d = new CPoint(p2p.X + (p3p.X - p2p.X) * t,
                       p2p.Y + (p3p.Y - p2p.Y) * t);
  var p1t = new CPoint(p1d.X + (p2d.X - p1d.X) * t,
                       p1d.Y + (p2d.Y - p1d.Y) * t);
  return [[m_p1.X, m_p1.Y, p1p.X, p1p.Y, p1d.X, p1d.Y, p1t.X, p1t.Y],
          [p1t.X, p1t.Y, p2d.X, p2d.Y, p3p.X, p3p.Y, m_p4.X, m_p4.Y]];
}

以上代码中的subdivide_cubic_to_cubics()通过值t将原始三次曲线分为两部分。由于get_t_values_of_critical_points()返回按t值排序的t值数组,因此您可以轻松遍历所有t值并获得相应的子曲线。当您拥有这些分割曲线时,您必须通过下一个t值来分割第二个子曲线。
当所有分裂完成后,您就拥有了所有子曲线的控制点。现在只剩下将三次控制点转换为二次控制点。因为所有子曲线现在都是低阶三次曲线,所以相应的二次控制点很容易计算出来。二次控制点的第一个和最后一个与三次曲线(子曲线)的第一个和最后一个控制点相同,中间的控制点位于P1-P2和P4-P3交叉处的点上。

由于某种原因,当子曲线被绘制为二次曲线时,结果几乎正确,但并非完全正确。原因很明显:每个子曲线仍然是三次曲线,因此只能用二次曲线来近似表示,而不能完全表示。 - bubba

3

术语/约定

  • 由P1/2 - 锚点,C1/C2控制点定义的立方体
  • |x|是x的欧几里德范数
  • 立方体的中点近似值:一个与立方体共享相同锚点并将控制点设置为C =(3·C2-P2 + 3·C1-P1)/ 4的四边形

算法

  1. 选择绝对精度(prec
  2. 将Tdiv计算为(cubic)方程的根sqrt(3)/18 · |P2-3·C2+3·C1-P1| / 2 · Tdiv ^ 3 = prec
  3. 如果Tdiv <0.5,则在Tdiv处分割立方体。 第一段[0..Tdiv]可以通过中点近似值用二次函数来近似,缺陷小于prec。从第二个结果段(对应于1-Tdiv)重复步骤2
  4. 0.5≤Tdiv<1-只需将立方体分成两半。 这两个部分可以通过中点近似来近似
  5. Tdiv>= 1-整个立方体可以通过中点近似来近似

第2步的“神奇公式”在此页面上演示(带有交互式示例)。


2

tfinniga的答案还有另一种推导方法:
首先请参考维基百科贝塞尔曲线,其中包含二次和三次贝塞尔曲线的公式(同时还有漂亮的动画效果):

Q(t) = (1-t)^2 P0 + 2 (1-t) t Q + t^2 P3
P(t) + (1-t)^3 P0 + 3 (1-t)^2 t P1 + 3 (1-t) t^2 P2 + t^3 P3

要求这些在中间匹配,t = 1/2:

(P0 + 2 Q + P3) / 4 = (P0 + 3 P1 + 3 P2 + P3) / 8  
=> Q = P1 + P2 - (P0 + P1 + P2 + P3) / 4  

“Q” 在几何上有如下解释:

Pmid = middle of P0 P1 P2 P3  
P12mid = midway between P1 and P2  
draw a line from Pmid to P12mid, and that far again: you're at Q.  

希望这有意义——画几个例子。

1

1
我应该指出,Adrian的解决方案对于单个三次曲线非常好,但当这些三次曲线是平滑三次样条的一部分时,使用他的中点近似方法会导致在段的节点处失去斜率连续性。因此,如果您正在处理字体字形或任何其他原因需要保留曲线的平滑性(这很可能是情况),则在http://fontforge.org/bezier.html#ps2ttf描述的方法要好得多。
尽管这是一个旧问题,但像我这样的许多人都会在搜索结果中看到它,所以我在这里发布了这篇文章。

0

我可能会画一系列的曲线,而不是尝试使用不同的算法来绘制一条曲线。就像画两个半圆来组成一个整圆。


0

尝试寻找开源的Postscript字体转换为Truetype字体的工具。我相信他们会有这个工具。Postscript使用三次贝塞尔曲线,而Truetype使用二次贝塞尔曲线。祝你好运。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接