2010-01-05 105 views
2

在网络搜索之后,我看到各种论坛中的各种人物暗指以二次方近似三次曲线。但我找不到配方。如何将三次曲线的2个控制点转换为二次曲线的单个控制点?

我想是这样的:

输入:startx的,startY,control1X,control1Y,control2X,control2Y,endX,恩迪 输出:运行startx,startY,controlX,controlY,endX,恩迪

其实,因为起点和终点是一样的,我真正需要的是...

输入:startx的,startY,control1X,control1Y,control2X,control2Y,endX,恩迪 输出:controlX,controlY

回答

0

我可能会绘制一系列曲线,而不是试图使用不同的alg绘制一条曲线。有点像绘制两个半圆组成一个整圆。

5

如前所述,从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被类似地计算 - 尺寸是独立的,所以这个工程的三维(或n-d)。

这将是一个近似值。如果你需要更好的近似,一种方法是通过使用deCastlejau算法对初始立方体进行细分,然后对每个细分进行度数减少。如果你需要更好的连续性,还有其他的近似方法不那么快速和肮脏。

+0

+1。你能建议一个贝塞尔曲线的参考吗? – denis 2010-01-10 17:02:01

+1

我使用的主要参考文献来自我使用的CAGD类:http://tom.cs.byu.edu/~557/text/第2章介绍了贝塞尔曲线。 – tfinniga 2010-01-11 17:39:25

+0

请问,你有这个'P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3'吗?它工作得很好... – 2012-10-26 15:26:58

2

tfinniga的回答的另一个推导:
首先看到维基百科Bezier curve 的公式为二次和三次贝塞尔曲线(也不错动画):

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. 

希望这是有道理的 - 画出几个例子)

0

尽量寻找开源Postcript字体的TrueType字体转换器。我确定他们有。 Postscript使用三次贝塞尔曲线,而Truetype使用二次贝塞尔曲线。祝你好运。

3

约定/术语

  • 立方由下式定义:P1/2 - 锚点,C1/C2的控制点
  • | X |是x的欧几里得范数x的中间点约为立方的四分之一,与三次方具有相同的锚并且具有在C =(3·C2-P2 + 3·C1-P1)/ 4的控制点的四分之一

算法

  1. 挑绝对精度(PREC
  2. 计算Tdiv如(立方)方程的sqrt(3)/ 18·根| P2 - 3·C2 + 3·C1-P1 |/2·Tdiv^3 = prec
  3. 如果Tdiv < 0.5在Tdiv中划分立方。第一段[0..Tdiv]可以通过二次方近似,缺陷小于prec,通过中点近似。重复步骤2和第二个结果段(对应于1-Tdiv)
  4. 0.5 < = Tdiv < 1-简单地将立方分为两部分。两个半部可通过中点近似来近似
  5. Tdiv> = 1 - 整个立方可以通过中点近似

“神奇式”,在步骤2被证明来近似(带互动示例)on this page

1

我应该注意到,阿德里安的解决方案对于单立方体来说非常棒,但是当立方体是光滑立方样条的线段时,则使用他的中点近似方法会导致节点节点的斜率连续性丢失。因此,如果您使用字体字形或出于其他任何需要保留曲线平滑性的原因(最可能是这种情况),则在http://fontforge.org/bezier.html#ps2ttf中描述的方法会更好。

即使这是一个老问题,很多像我这样的人会在搜索结果中看到它,所以我在这里发布这个。

3

立方体可以有循环和尖角,这是二次方不可能有的。这意味着几乎没有简单的解决方案。如果三次方已经是二次方,那么存在简单的解。通常情况下,你必须将立方分为二次方。而且你必须决定细分的关键点。我在网上看到的其他消息来源表明,检查三次样条曲线的拐点(二次样条不能有),并迫使它在那里突破。在我看来,这实际上导致了结果变差,它使用更多的观点和近似看起来并不像忽略拐点那么接近,所以我忽略它们。“

确实如此,拐点(立方的二阶导数)是不够的。但是,如果考虑到三次函数的一阶导数局部极值(最小值,最大值),以及这些全部的力断裂,那么子曲线都是二次的,并且可以用二次方程来表示。

我测试了下面的函数,它们按预期工作(找到立方体的所有临界点并将立方体划分为向下立方体)。当绘制这些子曲线时,曲线与原始立方体完全相同,但由于某些原因,当子曲线绘制为二次曲线时,结果几乎是正确的,但不完全正确。

所以这个答案不是对问题的严格帮助,但这些函数为立方到二次转换提供了一个起点。

要找到当地的极端和拐点,以下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; 
}; 

而当你有那些临界吨值(它们是从范围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相交处。