136.參數(shù)曲線的快速生成算法畢業(yè)設計

1、 畢業(yè)論文：參數(shù)曲線的快速生成算法 江 南 大 學畢 業(yè) 設 計 論 文論文題目：參數(shù)曲線的快速生成算法姓 名： 學 院：信息工程學院專 業(yè)：計算機科學與技術指導老師： 日 期：2003年6月摘 要本畢業(yè)設計主要研究參數(shù)曲線的直接快速生成，要直接生成參數(shù)曲線就需對參數(shù)方程x=f(t),y=g(t),(0t1)的參數(shù)t每次增加一個步長，然后計算該點的x和y坐標值并繪制該點。要逐點地生成參數(shù)曲線，就要求參數(shù)t每次增加的步長要使曲線前進的幅度不得超過一個象素長度，否則有可能跨過一個中間象素而產生斷點。為了提高曲線生成算法的速度，本畢業(yè)設計針對如何選擇最佳的步長進行比較討論，以使曲線前進的幅度在不超過

2、一個象素的前提下，選擇盡量大的步長。為了進一步提高算法的速度，在前面討論的最佳步長的基礎上又采用了雙步逐點曲線生成算法，即將上述得到的步長增加一倍，以使算法的循環(huán)次數(shù)減少一半。由于步長增加一倍，這樣當曲線前進一步時，其幅度有時會大于一個象素的長度，這時我們通過插值的方法來確定跨過的那個中間象素。通過上述討論的算法能夠比較快速的逐點生成曲線，為了實現(xiàn)上述算法，本畢業(yè)設計使用visual c+6.0為工具并以三次bezier曲線、普通參數(shù)曲線x=f(t)=x3t3+x2t2+x1t+x0, y=g(t)=y3t3+y2t2+y1t+y0，以及導師所給的一個特殊的曲線方程為例編程實現(xiàn)上述算法。關鍵詞

3、：參數(shù)曲線，逐點，雙步，visual c+6. 0 作者： 二零零三年 六月abstract this graduation project main reseach the direct born of the parameter curve x=f(t),y=g(t),0= t loadstandcursor(idc_cross)初始化該變量，該語句的作用是取得windows標準鼠標形狀句柄并賦給m_hcross，然后就可以通過classwizard添加鼠標動作的消息處理函數(shù)。例如，要為程序添加鼠標左鍵單擊消息處理函數(shù)，首先在打開的classwizard對話框中的class name組合框

4、中選擇view類，然后在object ids列表框選中第一行，并在message列表框中選中wm_lbuttondown一行，最后單擊add function按鈕即可。類似的還可以為程序添加wm_rbuttondown（鼠標右鍵單擊）消息處理函數(shù)。因為需要逐點地生成曲線，因此在程序中需要使用到mfc（microsoft fundation class）中的cdc（設備上下文）類的成員函數(shù)setpixel（）來實現(xiàn)在屏幕上畫點，cdc類主要用于在指定設備上下文上（如窗口客戶區(qū)、打印機）進行繪圖、顯示文本等操作。第二章 計算機圖形學中常用的算法2.1 常用直線的算法 畫直線的算法有很多，例如數(shù)值微

5、分法，中點畫線法，bresenham化線算法等。在這里只介紹一個比較方便常用的中點畫線法。為了討論方便，本小節(jié)假定直線斜率在0、1之間。其他情況可參照下述討論進行處理。如圖所示，若直線在x方向增加一個單位，則在y方向上的增量只能在0、1之間。假設x坐標為xp的各象素點中，與直線最近者已確定，為(xp,yp)，用實心小圓表示。那么，下一個與直線最近的象素只能是正右方的p1(xp+1,yp)或右上方的p2(xp+1,yp+1)兩者之一，用空心小圓表示。再以m 表示p1、p2的中點，即m=(xp+1,yp+0.5）。又設想q是理想直線與垂直直線x=xp+1的交點。顯然，若m在q的下方，則p2離直線近

6、，應取為下一個象素；否則應取p1。這就是中點畫線法的基本原理。 p2qmp1p=（xp，yp）中點畫線算法每步迭代涉及的象素和中點示意圖下面來討論上述算法的實現(xiàn)。假設直線的起點和終點分別是(x0,y0)，(x1,y1)。則直線的方程為 f(x,y) = ax + by + c=0其中，a = y0-y1，b = x1-x0，c = x0yi-x1y0。對于直線上的點，f(x,y)=0；對于直線上方的點，f(x,y)0；而對于直線下方的點f(x,y)0。因此，欲判斷前述q在m的上方還是下方，只要把m代入f(x,y)，并判斷它的符號。構成判別式 d=f(m)=f(xp+1,yp+0.5)=a(xp

7、+1) + b(yp+0.5) + c當d0時，則應取正右方的p1。當d=0時，二者一樣合適，可以隨便取一個。我們約定取正右方的p1。對每一個象素計算判別式d，根據(jù)它的符號確定下一個象素。至此可以寫出完整的算法。但是注意到d是xp和yp的線形函數(shù)，可采用增量計算，提高運算效率。在d0的情況下，取正右方象素p1，欲判斷再下一個象素應取哪個，應計算 d1=f(xp+2，yp+0.5) =a(xp+2) + b(yp+0.5)+ c= d + a故d 的增量為a。而若d0，則右上方的象素p2，欲判斷再下一個象素，則要計算d2=f(xp+2，yp+1.5)=a(xp+2)+b(yp+1.5)+ c =

8、 d + a + b故在第二種情況，d 的增量為a+b。再看d的初值。顯然，第一個象素應取左端點(x0,y0)，相應的判別式為 d0=f(x0+1,y0+0.5)=a(x0+1)+ b(y0+0.5) + c = ax0+by0+a+c+0.5b = f(x0，y0)+ a+0.5b但由于(x0,y0)在直線上，故f(x0,y0)=0。因此，d的初值為d0= a+0.5b。 由于使用的只是d 的符號，而且d的增量都是整數(shù)，只是其初值包含小數(shù)。因此我們可以使用2d代替d，來擺脫小數(shù)，寫出僅包含整數(shù)的算法：midpointline(x0,y0,x1,y1,color)int x0,y0,x1,y1

9、,color; int a,b,delta1,delta2,d,x,y; a= x0- y1; b=x1- x0; delta1=2*a; delta2=2*(a+b); x= x0; y=y0 ; drawpixel(x,y,color); while(x x1) if(d0) x+;y+;d+= delta2;elsex+;d+= delta1;drawpixel(x,y,color); 2.2 常用的參數(shù)曲線的繪制算法常用的參數(shù)曲線有許多，如bezier，b樣條，非均勻有理b樣條、圓錐曲線等。本小節(jié)將以bezier曲線為代表，講解其繪制算法。bezier曲線的公式 ：給定空間n+1個點的

10、位置矢量pi，bezier曲線上各點坐標的插值公式是：c(t) =, 0t1pi構成該曲線的特征多邊形，是bernstein基函數(shù)，也是曲線上各點位置矢量的調和函數(shù)。=ti(1-t)n-i=cti(1-t)n-i i=0,1,2,n首先，討論三次bezie曲線的繪制由上述公式可以推出三次bezier曲線形式：當n=3時,c(t)= = p0(1t)3 + 3p1t (1t)2 + 3p2 t2 (1t) + p3t3 0t1可以將其改寫為如下的形式：c3(t) = ( cs p0+ ct p1)s+ct2 p2 )s+ ct3p3其中，s=1-t，則可以通過如下程序繪制曲線：float hor

11、nbez(degree,coeff,t)/* input:degree:曲線的次數(shù)coeff:保存曲線的系數(shù)t: 參數(shù)的值 output: 該參數(shù)的坐標值*/int degree;float coeff;float t; int i,n_choose_i; float fact,t1,aux; t1=1.0-t; fac=1.0; n_choose_i=1; aux=coeff0*t1; /*開始循環(huán)計算坐標值*/ for(i=1idegree;i+) fact = fact*t;n_choose_i= n_choose_i*(degree-i+1)/i;aux=(aux+fact* n_ch

12、oose_i*coeffi*t1; aux=aux+fact*t*coeffdegree; return aux;下面來討論n次bezier曲線的繪制。在前面我們介紹了一個程序用于計算相應曲線上的諸點，但其只適用于三次bezie曲線，既不通用而且計算量較大。用如下cas-teljau算法產生曲線上的點列相對要簡單許多。cas-teljau算法：給定空間n+1個點pi(i=0,1,2,n)及參數(shù)t，則有：(t)=(1-t)(t)+ t(t)r=1,2.n, i=0,1.n-r, 0t1其中(t)即為pi, (t)是曲線上具有參數(shù)t的點。 當n=3時，用cas-teljau算法遞推出的(t)呈直角

13、三角形，對應如下所示： 該三角形垂直邊上的點p0，p1，p2， p3是曲線p(t)在0t1內的控制點，斜邊上的點是p(t)在0t1/2內的控制點，水平直角邊上的點是p(t)在1/2t1內的控制點。這種用分割bezier曲線控制多邊形的方法為離散化的曲線提供了方便。用cas-teljau算法繪制bezier曲線的程序如下：void bez_to_points(degree,npoints,coeff,points)/*input :degree:曲線的次數(shù)npoint:控制點的數(shù)目coeff:控制點的坐標output: 曲線上點的坐標*/int degree,npointes; float co

14、eff,points; float t,delt; int i; float decas(); delt=1.0/(float)npoints; /*步長*/ t=0.0; for(i=0;i=npoints;i+) pointsi=decas(degree,coeff,t);t=t+delt; float decas(degree,coeff,t)float coeff;float t;int degree; int r,i; float t1; float coeffa10; t1=1.0-t; for(i=1;i=degree;i+) coeffai=coeffi; /*計算(t)地值

15、for(r=1;r=degree;r+) for(i=1;r=degree-r;i+) coeffai=t1*coeffai+t*coeffat+1; return(coeffa0); 第三章 參數(shù)曲線的快速生成算法及實現(xiàn)3.1 普通參數(shù)曲線生成算法的介紹本畢業(yè)設計所研究的參數(shù)曲線生成算法要具備直接、逐點、快速的特點。要直接生成參數(shù)曲線就需要對曲線的參數(shù)每次增加一個步長，然后計算該點的坐標值x和y并繪制該點。要逐點地生成參數(shù)曲線，就要求參數(shù)每次增加的步長要使曲線前進的幅度不得超過一個象素的長度，否則有可能跨過一個中間象素而產生斷點。要快速生成曲線則要求在不產生斷點的情況下盡量減少畫點次數(shù)以及不

16、重復畫一個象素點來達到加快曲線的生成速度。根據(jù)參考文獻可以得到一個滿足上述要求的逐點生成參數(shù)曲線的整數(shù)算法。設曲線的參數(shù)方程為：首先討論第一個方程x=f( t ),首先把曲線分成n 段（限定t取i/n，其中0in。）根據(jù)拉格朗日中值定理：f(x+x)f( x )=f()(x)，當n 滿足n時，可以得到如下公式：=1 （3.1）根據(jù)公式3.1，可以使得算法中每次循環(huán)，即每步前進不超過1個象素，從而保證了曲線的連續(xù)性。為了只使用整數(shù)運算，可將方程x=f(t)乘一正整數(shù)n，使其轉換成整數(shù)方程： nxi =( i ) + zi ， 其中( i )=nf(),它和xi (x坐標的整數(shù)位置)及其余數(shù)zi

17、()均為整數(shù)。各個量的含義如下圖所示。xi表示與計算出的值f()最近的象素點的x坐標。余數(shù)zi 表示xif(i/n)xixi f(i/n)(a) (b) 圖1-1 xi與 f()兩者的關系 與f()的差距（當然為了整數(shù)化，也乘了一個n值）。若是圖（a）的情況，則zi為負值，即取曲線左邊的象素點；若是圖（b）的情況，則 zi為正值，即取曲線右邊的象素點。算法逐點計算曲線上的象素。設當前象素點的x坐標是xi，則下一點的x坐標xi+1應該滿足 n xi+1 = (i+1) + zi+1，其中 (i+1)=( i )+( i )=nxizi +( i )根據(jù)3.1式有：=nn，而，所以n。因此，xi+

18、1的可能取值為xi1，xi 或xi +1。這樣就得到了xi+1和zi+1的計算公式：xi+1 zi+1這樣，就得到了x坐標和余數(shù)z的遞推計算公式。y坐標的計算公式可以根據(jù)以上的討論同理得到。步長大?。?/n）的確定是非常重要的。確定步長的標準是：在使曲線前進的幅度不超過一個象素長度的前提下，選擇盡量大的步長（即小的n值），以便算法提高速度。如果步長選得太小，則在繪制曲線時造成取點過密，因而重復繪制了很多象素點，浪費了大量的計算也降低了算法的速度。在參考文獻提出的算法中，取n的值為： n = max (nx，ny)其中nx和ny分別對于x坐標和y坐標選擇的n的值，為nx= m ny= m 其中

19、m為曲線的次數(shù)。而該參考文獻又對nx和ny值進行了進一步的優(yōu)化，減小了n 的值，?。?nx= m ny= m 其中x和y是曲線第i個控制點的坐標?？梢宰C明這樣選擇的n值滿足上述的條件n。3.2 最佳的步長值根據(jù)參考文獻中對上述算法進行編程和分析運行結果，發(fā)現(xiàn)該算法在繪制曲線時每次循環(huán)使曲線前進的幅度的最大值往往不能接近于1（多數(shù)在0.6至0.8之間）。這說明在上一小節(jié)介紹的算法中的n的取值并沒有達到最佳值。從理論上分析，我們的目標是要找到滿足條件n的最小的n值，即尋找的最小上界。上述的m 雖然是的一個上界，但并不是其最小上界。下面將討論如何求出的最小上界以及最佳的n值。的最小上界顯然應該出現(xiàn)在

20、f(t)的極值點處或曲線的端點處，即當參數(shù)t = 0或 t =1處，因此應該以在曲線的兩端點處和其在兩端點之間的極值點處的函數(shù)值中的最大者作為其最小上界。由于我們采用了求函數(shù)的最大極值作為其上界，因此它是最小上界，因為該上界就在曲線上，如果它再小一點則必有曲線上的一點大于它。下面我們將以三次bezier曲線為例描述最佳n的計算過程。對于三次bezier曲線：f( t ) = x0(1t)3 + 3x1t (1t)2 + 3x2 t2 (1t) + x3t3對其求導,得 f ( t )=3(x1x0)(1t)2 + 2(x2 x1)(1t)t + (x3x2) t2=3x3x22(x2x1)+x

21、1x0 t2+2(x22x1+x0) t + x1x0，要求f(t)的極值點就要將其對t 再次求導并另其導函數(shù)為0，得：6x33(x2x1)x0 t + x22x1 + x0= 0 設v= x22x1 + x0，w= x33(x2x1)x0；由上式得，當t=時，f( t )取到極值3x1x0。顯然，在端點處( t = 0 和t = 1)的值分別為3和3。所以，nx的取值為當0，1時 nx = 3）當0，1時，nx = 3）同理，根據(jù)ny來求得ny 的值。最后取 n = max(nx,ny)，從而得到了最佳的n值。 由上面的討論可知，n值決定了算法的循環(huán)次數(shù)，n值愈小，算法的速度愈快。在上面計算

22、得到的n值已經比較理想了，那么，是否還可以再進一步減小n值呢？下面提出一個雙步逐點曲線生成算法來進一步減小n值。3.3 雙步逐點曲線生成算法從上一小節(jié)的描述可知，新算法通過求極值已經找到了滿足條件n的最小n值。如果再進一步減小n的值，則在曲線上可能出現(xiàn)斷點，即曲線前進的幅度大于了一個象素的長度，從而漏過了一個中間的象素。在前面求得的最小n值的基礎上，本小節(jié)提出雙步逐點曲線生成算法，其基本思想是，將n 值減小二分之一（即將步長增加一倍）。這樣當曲線前進一步時，其幅度有時會大于一個象素的長度。為了不使曲線出現(xiàn)漏點，我們通過插值的方法來確定跨過的那個中間象素。用此方法可使上一小節(jié)提出的算法的循環(huán)次數(shù)

23、減少一半，并大大提高了參數(shù)曲線的生成速度。下面將具體描述雙步逐點曲線生成算法的思想。設n 仍是上節(jié)計算出的單步算法的n 值。為了保證算法的雙步特性，將3.1式（拉格朗日中值定理）=1乘2，得= 2該式保證了雙步算法在將步長增加一倍（即n值減小二分之一）時，曲線每次前進的幅度不會大于兩個象素的長度。我們還是先討論x坐標的情況，y坐標與x坐標同理。設當前點坐標xi已經確定，則下一點的x 坐標xi+1應該滿足nxi+1 = (i+1) + zi+1 ,其中 (i+1)=( i ) +( i )= nxizi +( i )由第一小節(jié)中的等式=nn可知：= n=（）2n，而，所以 n可以看出，xi+1的

24、可能取值為xi2，xi1，xi，xi +1和xi +2。由上面的討論就得到了xi+1的計算公式： 當 (k)n (i)zi fillrect(&rect,&brush);long u=3,n,n;long f0,f1,f2,f3,g0,g1,g2,g3;long a1,a2,a3,b1,b2,b3;long v,w,m,t; /計算nx的值long nx=labs(x1-x0)labs(x3-x2)?labs(x1-x0):labs(x3-x2);v=x2-2*x1+x0;w=x3+3*(x1-x2)-x0;t=-v/w;if(t0 & t1)m=x1-x0+v*t;if(mnx) nx=m;

25、 /計算ny的值long ny=labs(y1-y0)labs(y3-y2)?labs(y1-y0):labs(y3-y2);v=y2-2*y1+y0;w=y3+3*(y1-y2)-y0;t=-v/w;if(t0 & t1)m=y1-y0+v*t;if(mny) ny=m;nx=u*nx;ny=u*ny;n=nxny?nx:ny;/將n的值減小1/2n=n1;/使f0, f1, f2, f3,g0,g1,g2,g3都為整數(shù)n=n*n*n;/計算當t=0，t=1/n，t=2/n，t=3/n時f與g的值f0=n*x0;f1=x0*(n-1)*(n-1)*(n-1)+3*x1*(n-1)*(n-1)

26、+3*x2*(n-1)+x3;f2=x0*(n-2)*(n-2)*(n-2)+6*x1*(n-2)*(n-2)+12*x2*(n-2)+8*x3;f3=x0*(n-3)*(n-3)*(n-3)+9*x1*(n-3)*(n-3)+27*x2*(n-3)+27*x3;g0=n*y0;g1=y0*(n-1)*(n-1)*(n-1)+3*y1*(n-1)*(n-1)+3*y2*(n-1)+y3;g2=y0*(n-2)*(n-2)*(n-2)+6*y1*(n-2)*(n-2)+12*y2*(n-2)+8*y3;g3=y0*(n-3)*(n-3)*(n-3)+9*y1*(n-3)*(n-3)+27*y2*

27、(n-3)+27*y3;/ a1，a2，a3和b1，b2，b3分別表示f和g的一、二、三階差分a1=f1-f0;a2=f2-2*f1+f0;a3=f3-3*f2+3*f1-f0;b1=g1-g0;b2=g2-2*g1+g0;b3=g3-3*g2+3*g1-g0;long x=x0,y=y0;long z1=0,z2=0; /畫曲線的第一個點int fx=0,fy=0;pdc-setpixel(x,y,rgb(10,20,20); /循環(huán)畫點for(int i=0;i=n;i+)/xi+1=xi-2時的情況 if(2*(a1-z1)-n)if(2*(a1-z1)setpixel(x,y,rgb(

28、10,20,20);fx=0; /xi+1=xi-2時yi+1=yi-2的情況 if(2*(b1-z2)-n) if(2*(b1-z2)setpixel(x,y,rgb(10,20,20); pdc-setpixel(x-1,y-1,rgb(10,20,20); pdc-setpixel(x-2,y-2,rgb(10,20,20); y=y-2; z2=z2-b1-2*n; else /xi+1=xi-2時yi+1=yi-1的情況 if(b1-2*z2-n) /*b1-2*z2-n即b1/2-z2setpixel(x,y,rgb(10,20,20); pdc-setpixel(x-1,y-1,rgb(10,20,20); fx=1; els