[转载] Hermite 与 Bezier 曲线的绘制
发信人:william@cis_nctu(何陋居主),信区:programming标 题:[转载]Hermite与Bezier曲线的绘制
发信站:交大资科_BBS(May2500:32:411995)
转信站:cis_nctu
From:Chi'uI-Nan *Area:90C语言
To:All Date:03May95 22:37:26
Subj:Hermite与Bezier曲线的绘制
**********************************************************************
*Hermite与Bezier曲线绘制方法研究 *
*作者：邱奕南(Chi'uI-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
可得：
┌0001┐┌Ax┐ ┌x1 ┐
│1111││Bx│＝│x2 │
│0010││Cx│ │xr1│
└3210┘└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曲线的绘制程式：
#defineIterative 24 /*曲线仿真的线数(必须小于32)*/
#defineIterative2(Iterative*Iterative)
#defineIterative3(Iterative2*Iterative)
voidDrawHermiteCurve(intx1,inty1,intx2,inty2,intxr1,intyr1,
intxr2,intyr2)
{
/*------------------------------------------------------------
作用：画出Hermite曲线
输入：x1,y1,x2,y2=曲线端点
xr1,yr1,xr2,yr2=曲线两参考向量
作者：邱奕南Chi'uI-Nan
------------------------------------------------------------*/
inti,oldx,oldy,m1,m2,m3,m4,x,y,k1,k2;
oldx=x1;
oldy=y1;
m1=Iterative3;
m2=m3=m4=0;
for(i=0;i<Iterative;i++) /*用Iterative条直线仿真*/
{
k1=(i<<1)+1;
k2=(k1+i)*i+k1;
m4+=(k2-=(k1*=Iterative));
m3+=(k1=k2-k1)+Iterative2;
m2-=(k2+=k1);
m1+=k2;
x=(int)(((long)x1*m1+(long)x2*m2+(long)xr1*m3+
(long)xr2*m4)/Iterative3);
y=(int)(((long)y1*m1+(long)y2*m2+(long)yr1*m3+
(long)yr2*m4)/Iterative3);
DrawLine(oldx,oldy,x,y);
oldx=x;
oldy=y;
}
}
voidDrawBezierCurve(intx1,inty1,intx2,inty2,intxr1,intyr1,
intxr2,intyr2)
{
/*------------------------------------------------------------
作用：画出Bezier曲线
输入：x1,y1,x2,y2=曲线端点
xr1,yr1,xr2,yr2=曲线两参考点
作者：邱奕南Chi'uI-Nan
------------------------------------------------------------*/
DrawHermiteCurve(x1,y1,x2,y2,3*(xr1-x1),3*(yr1-y1),3*(x2-xr2),3*(y2-yr2));
}
＊青衫诗客--小邱＊
--Via中文银版快信V2.28C
!Origin:档案货柜,欢迎您来挖宝,２８８００BPS,04-230-2080;(90:2010/622)
________________________________________
---------------------------- ------------------------
≡何陋居≡中学生以伏案读书为主,大学生则应起而高瞻远瞩。 Whitehead.
---------------------------- ------------------------
页:
[1]