在多個點處拆分三次貝塞爾曲線

Question

我正在寫一個算法將三次貝塞爾曲線拆分爲多個曲線（最多4個）。我從一開始就對每個想要分裂的點都有t值。我也有一個算法已經一次分割曲線：

SubdivPoints subdivideBezier(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t) 
{ 
    Vector2 p11 = (p1 - p0) * t + p0; 
    Vector2 p21 = (p2 - p1) * t + p1; 
    Vector2 p31 = (p3 - p2) * t + p2; 

    Vector2 p12 = (p21 - p11) * t + p11; 
    Vector2 p22 = (p31 - p21) * t + p21; 

    Vector2 p13 = (p22 - p12) * t + p12; 

    return SubdivPoints(p11, p12, p22, p31, p13); 
} 

我的問題是，是否有擴大這種分裂多次一個簡單的方法？我想在每次分割之後，我想重新計算t值;我想知道的一件事是如果簡單的算術在這裏工作。例如。假設我有0.2和0.6的值。我在t = 0.2時分割曲線，給我兩條曲線。第二條曲線涵蓋來自原始的t值0.2 < t < 1。如果我通過除法重新計算0.6的第二個t值：（0.6 - 0.2）/（1 - 0.2）= 0.5，那麼將第二個曲線除以t = 0.75，這樣做會起作用嗎？或者我需要以其他方式重新計算它？

Answer 1

很難說，即使您目前的方法工作，因爲我們沒有看到SubdivPoints背後是什麼。我能想到的方法2本：

1. 代數

   如果你看一下你的問題作爲參數t縮放多項式那麼它變得更清晰。例如，您需要控制點的部分t = <0.25,0.5>。這意味着我們需要形成代表與參數u=<0.0,1.0>相同曲線的新控制點。怎麼做？

   1. 寫入BEZIER作爲多項式

   每個軸可以分別以相同的方式S DONE讓我們集中於僅x - 軸。我們有4個BEZIER控制點，x座標爲(x0,x1,x2,x3)。如果我們將伯恩斯坦polynoms以形成三次多項式，我們得到：

   x(t)=  (       ( x0)) 
       + t*(     (3.0*x1)-(3.0*x0)) 
       + t*t*(  (3.0*x2)-(6.0*x1)+(3.0*x0)) 
       +t*t*t*(( x3)-(3.0*x2)+(3.0*x1)-( x0)) 
   

   通過替代，如此

使用線性內插

重新調整參數：

t0=0.25 -> u0=0.0 
t1=0.50 -> u1=1.0 
t=t0+(t1-t0)*(u-u0)/(u1-u0) 
t=0.25+0.5*u 

現在使用u而不是t重寫多項式

x(t)=    (       ( x0)) 
    +(0.25+u/2) *(     (3.0*x1)-(3.0*x0)) 
    +(0.25+u/2)^2*(  (3.0*x2)-(6.0*x1)+(3.0*x0)) 
    +(0.25+u/2)^3*(( x3)-(3.0*x2)+(3.0*x1)-( x0)) 

變化的多項式形式再次

現在需要對u^0,u^1,u^2,u^3分離多項式的術語和改革每個匹配BEZIER樣式匹配貝塞爾方程（從＃1 ）。從中提取新的控制點。

例如術語u^3是這樣的。越來越u的唯一可能性^ 3是從

(1/4+u/2)^3= (1/8)*u^3 + (3/16)*u^2 + (3/32)*u + (1/64) 

所以分離u^3任期將是：

u*u*u*(( x3)-(3.0*x2)+(3.0*x1)-( x0))/8 

別人會更復雜一些，因爲你需要所有線路結合在一起......之後簡化你將需要分離新的座標。正如你可以看到它是輕微的瘋狂，但有代數解決的那裏像Derive for Windows ...

對不起，我沒有時間/心情/肚子來作出所有條款的完整例子，但你會看到它會是一個相當瘋狂多項式...

曲線擬合

這是基於你發現你的控制點的座標，並檢查它是如何遠離你想要的曲線。因此，測試「所有可能的」點並記住目標範圍和原來的曲線之間的匹配關係，因爲有無數的控制點可能是不可能的，所以我們需要通過利用某些東西將這些點控制在可控範圍內。例如，我們現在的控制點不會遠離原始控制點，所以我們可以使用它來限制每個點的面積。您可以使用approximation search來實現這個或任何其他最小化技術。

您也可以獲得更多如果使用插值立方更好的開始點，這個顯示BEZIER vs Interpolation cubics所以：。

1. 計算4新的插值立方控制婆從您的貝塞爾曲線整數

   所以如果我們有相同的範圍，然後

   X0 = BEZIER(t0-(t1-t0)) 
   X1 = BEZIER(t0) 
   X2 = BEZIER(t1) 
   X3 = BEZIER(t1+(t1-t0)) 
   

   之前這些都是立方插值控制點不BEZIER。它們應該均勻分散。 X1,X2是曲線的端點和X0,X3是之前和之後他們儘可能

2. transfrom (X0,X1,X2,X3)保護當地的外形和參數的線性回Bézier控制點(x0,x1,x2,x3)

   您可以從上面的鏈接用我的公式：

   // input: X0,Y0,..X3,Y3 ... interpolation control points 
   // output: x0,y0,..x3,y3 ... Bezier control points 
       double x0,y0,x1,y1,x2,y2,x3,y3,m=1.0/9.0; 
       x0=X1;    y0=Y1; 
       x1=X1+((X1-X0)*m); y1=Y1+((Y1-Y0)*m); 
       x2=X2+((X2-X3)*m); y2=Y2+((Y2-Y3)*m); 
       x3=X2;    y3=Y2; 
   

   正如你可以看到每個軸的計算以同樣的方式...

3. 應用pproximation搜索BEZIER控制點

   新的(x0,x1,x2,x3)並不精確，但通過盲目改變控制點我們可能會略微錯過曲線扭曲形狀的局部極端。所以我們需要尋找真正的。幸運的是，新的控制點(x0',x1',x2',x3')將非常接近這些點，所以現在我們必須搜索每個點，只在它的櫃檯部分附近有一些合理的半徑（比如邊界框size/8或其他...你會看到結果並且可以調整。 ..

[注意事項]

如果您需要確切的精度結果則只有＃1方法是可用的。方法＃2將總是有一些錯誤。如果形狀不需要精確，有時插值立方轉換成BEZIER而沒有最終擬合就足夠了（如果在切割區域/附近形狀不太複雜）。

正如我以前寫的不知道該原則在SubdivPoints使用是不可能回答重複使用它的結果會是怎樣？

還沒有指定的一樣的精度解決方案的約束結果，速度/運行時間限制......如果範圍是固定的（恆定的）或可能在運行時變化（這會使＃1方法極端複雜化，因爲您需要將範圍作爲變量處理直到結束）

Answer 2

由於您的細分Bezier （）函數確實遵循De Casteljau算法，我假設它可以在參數t處細分三次Bezier曲線。所以，是的，要繼續細分不同的參數（比如說t2），你需要做的就是找出t2落在哪條細分曲線上，根據這條曲線計算新的t2 *並進行細分。在你想要在t = 0.2和0.6處細分的例子中，0.6的新參數應該是（0.6-0.2）/（1-0.2）= 0.5。所以，你可以在t = 0.5時簡單地細分第二條曲線。