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 |
發表時間：2002-09-10 09:54:33
IP:61.218.xxx.xxx 未訂閱
系統時間：2024-11-24 8:12:46
聯絡我們 | Delphi K.Top討論版
| 本站聲明 |
|
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！ |