Hermite與Bezier曲線繪製方法研究 |
|
axsoft
版主 ![]() ![]() ![]() ![]() ![]() ![]() 發表:681 回覆:1056 積分:969 註冊:2002-03-13 發送簡訊給我 |
********************************************************************** * Hermite與Bezier曲線繪製方法研究 * * 作者:邱奕南 (Chi'u I-Nan) * * 版權聲明:以下文章內容本人僅同意供BBS 站上流傳學習,但必須完整流傳 * * (含版權聲明及程式),其餘權利一概保留。任何未經本人同意 * * ,將本文販賣、刊登、節錄、或其他一切侵害本人著作權之行為 * * 者,皆需負擔刑事責任及民事賠償責任。 * ********************************************************************** Hermite及Bezier曲線為三度空間曲線的常用表示法,以下我們先說明一 下這兩個曲線的定義: 1.Hermite曲線 Hermite曲線為給定兩端點及兩端點向量所得的三次曲線。令三次曲線: 3 2 x(t) = Ax * t Bx * t Cx * t d 3 2 y(t) = Ay * t By * t Cy * t d 且令給定的兩端點為(x1,y1)、(x2,y2),以及兩端點向量(xr1,yr1)、(xr2,yr2), 則: x(0) = x1, y(0) = y1 x(1) = x2, y(1) = y2 x'(0) = xr1, y'(0) = yr1 x'(1) = xr2, y'(1) = yr2 繪出(x(t),y(t)),0<=t<=1,即為Hermite曲線。 2.Bezier曲線 Bezier曲線為給定兩端點及另兩參考點所得的三次曲線,它可說是Hermite 曲線的另一種表示方式。假設兩端點為P1、P2,以及兩參考點Pr1、Pr2,則 Bezier曲線換算成Hermite曲線的方式為: R1 = 3*(Pr1-P1) R2 = 3*(P2-Pr2) R1、R2即為Hermite曲線的兩端點向量。 由於Bezier曲線和Hermite曲線可以說是相同的,因此以下之說明我們便以 Hermite曲線為主。由Hermite曲線的定義,首先我們必須求出Ax,Bx...等值。 由定義中的條件: x(0) = x1, x(1) = x2, x'(0) = xr1, x'(1) = xr2 以及 2 x'(t) = 3 * Ax * t 2 * Bx * t Cx 可得: ┌ 0 0 0 1 ┐┌ Ax ┐ ┌ x1 ┐ │ 1 1 1 1 ││ Bx │=│ x2 │ │ 0 0 1 0 ││ Cx │ │ xr1 │ └ 3 2 1 0 ┘└ Dx ┘ └ xr2 ┘ 解之得: ┌ Ax ┐ ┌ 2 -2 1 1 ┐┌ x1 ┐ │ Bx │=│ -3 3 -2 1 ││ x2 │ │ Cx │ │ 0 0 1 0 ││ xr1 │ └ Dx ┘ └ 1 0 0 0 ┘└ xr2 ┘ 因此 x(t) = (2*t^3 - 3*t^2 1) * x1 (-2*t^3 3*t^2) * x2 (t^3 - 2*t^2 t) * xr1 (t^3 - t^2) * xr2 同理 y(t) = (2*t^3 - 3*t^2 1) * y1 (-2*t^3 3*t^2) * y2 (t^3 - 2*t^2 t) * yr1 (t^3 - t^2) * yr2 上述的公式中,由於t的值是介於0與1之間,這對於我們在實際繪圖上較不 方便,而且運算速度也比較慢。因此假設我們以n條直線來模擬Hermite曲線, 則我們必須將t值化成整數,使它成為0<=t<=n(注意n條連續直線需有n 1個點)。 令i=n*t代入上述公式,化簡後可得: x(i) = (m1*x1 m2*x2 m3*xr1 m4*xr2) / n^3 y(i) = (m1*y1 m2*y2 m3*yr1 m4*yr2) / n^3 其中 m1 = 2*i^3 - 3*n*i^2 n^3 , 0 <= i <= n m2 = -2*i^3 3*n*i^2 m3 = i^3 - 2*n*i^2 n^2*i m4 = i^3 - n*i^2 如此我們便能很方便地求出模擬直線的各端點。然而上述公式中的乘法仍相當 多,對於m1~m4的計算上至少需5次乘法、2次移位乘法和6次加法(或4次乘法、 3次移位乘法和7次加法),在計算上仍然會浪費相當多時間(PC上的乘法約為 加法的近20倍,移位乘法則和加法相當),因此有必要再予以化簡。如何簡化 呢?由上述公式可發現,主要的乘法來自於i^3的計算,因此欲將之簡化的最簡 單的方式便是由前一個m1~m4值來求得後一個m1~m4值,藉此消減掉這個三次 方值的運算: m1(i 1) = m1(i) 6*i^2 6*i 2 - 3*n*(2*i 1) m2(i 1) = m2(i) - 6*i^2 - 6*i - 2 3*n*(2*i 1) m3(i 1) = m3(i) 3*i^2 3*i 1 - 2*n*(2i 1) n^2 m4(i 1) = m4(i) 3*i^2 3*i 1 - n*(2*i 1) 現在便是要化簡各式中後面的計算項次。由於這些項次有相當多的重複,故可 將之寫成: m1(i 1) = m1(i) a m2(i 1) = m2(i) - a m3(i 1) = m3(i) d - c n^2 m4(i 1) = m4(i) d a = 2*b - 3*c b = 3*i^2 3*i 1 c = n*(2*i 1) d = b-c 再進一步簡化為: e = 2*i 1 c = n*e b = 3*i^2 3*i 1 = (3*i 1)*i (2*i 1) = (e i)*i e 整理一下成為(依計算順序): e = 2*i 1 b = (e i)*i e c = n*e d = b-c m4 = m4 d f = d-c m3 = m3 f n^2 a = d f m2 = m2 - a m1 = m1 a 共計2次乘法、1次移位乘法和11次加法,等於是以兩次加法代替了兩次乘法, 其速度必然較快。記得m1~m4的初值為: m1(0) = n^3 m2(0) = m3(0) = m4(0) = 0 接下來我們要探討一下模擬線數n的問題。倒底取多少模擬線數較為恰當? 採用的模擬線數太少,曲線將不夠平滑,但若模擬線數太多,曲線繪製速度又 會太慢。據作者實際的測試,一般取n=20以上曲線便已相當平滑,但對於彎度 太大的曲線,其轉折處仍約略可見,不過並不嚴重。由於在繪製曲線時,大都 以整數來運算(為求速度),因此模擬線數最好不要超出32,以避免運算結果 超出整數運算的值域。以下便是Hermite曲線和Bezier曲線的繪製程式: #define Iterative 24 /* 曲線模擬的線數(必須小於32) */ #define Iterative2 (Iterative*Iterative) #define Iterative3 (Iterative2*Iterative) void DrawHermiteCurve(int x1,int y1,int x2,int y2,int xr1,int yr1, int xr2,int yr2) { /* ------------------------------------------------------------ 作用:畫出Hermite曲線 輸入:x1,y1,x2,y2 = 曲線端點 xr1,yr1,xr2,yr2 = 曲線兩參考向量 作者:邱奕南 Chi'u I-Nan ------------------------------------------------------------ */ int i, oldx, oldy, m1, m2, m3, m4, x, y, k1, k2; oldx = x1; oldy = y1; m1 = Iterative3; m2 = m3 = m4 = 0; for (i=0; i |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |