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

1、<p>　　畢 業(yè) 設(shè) 計 論 文</p><p>　　論文題目：參數(shù)曲線的快速生成算法</p><p><b>　　摘 要</b></p><p>　　本畢業(yè)設(shè)計主要研究參數(shù)曲線的直接快速生成，要直接生成參數(shù)曲線就需對參數(shù)方程{x=f(t),y=g(t),(0t1)}的參數(shù)t每次增加一個步長，然后計算該點的x和y坐標值并繪制該點。要

2、逐點地生成參數(shù)曲線，就要求參數(shù)t每次增加的步長要使曲線前進的幅度不得超過一個象素長度，否則有可能跨過一個中間象素而產(chǎn)生斷點。</p><p>　　為了提高曲線生成算法的速度，本畢業(yè)設(shè)計針對如何選擇最佳的步長進行比較討論，以使曲線前進的幅度在不超過一個象素的前提下，選擇盡量大的步長。為了進一步提高算法的速度，在前面討論的最佳步長的基礎(chǔ)上又采用了雙步逐點曲線生成算法，即將上述得到的步長增加一倍，以使算法的循環(huán)次數(shù)減少

3、一半。由于步長增加一倍，這樣當曲線前進一步時，其幅度有時會大于一個象素的長度，這時我們通過插值的方法來確定跨過的那個中間象素。</p><p>　　通過上述討論的算法能夠比較快速的逐點生成曲線，為了實現(xiàn)上述算法，本畢業(yè)設(shè)計使用Visual C++6.0為工具并以三次Bezier曲線、普通參數(shù)曲線{x=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3+Y2t2+Y1t+Y0}，以及導(dǎo)師所給的一個

4、特殊的曲線方程為例編程實現(xiàn)上述算法。</p><p>　　關(guān)鍵詞：參數(shù)曲線，逐點，雙步，Visual C++6. 0</p><p><b>　　作者： </b></p><p><b>　　二零零三年 六月</b></p><p><b>　　Abstract</b><

5、/p><p>　　This graduation project main reseach the direct born of the parameter curve {x=f(t),y=g(t),0<= t <=1,}quickly.To direct born of the parameter curve it need to increase the parameter ‘t’ a step le

6、ngth each time,then caculate this point’s coordinates value of x and y and draw this point.For drawing the parameter curve by point to point it orde to the parameter t’s step length of increased make the progress range o

7、f the curve can not large than the length of one pels, otherwise the curve may step o</p><p>　　For speeding up the arithmetic of the drawing of the curve, this graduation project have discussed the choice of

8、 the best step length, so as to choose the biggst step length on the premise that the progress range is not large than one ples. To speeding up the arithmetic more, before the base of discussion about the best step lengt

9、h just now,we take the arithmetic of double step form of the curve by point to point ,and it double the step length that it be caculated just now to lessen the time of </p><p>　　It can draw the curve quickly

10、 that used the arithmetic we have discussed.To achive the arithmetic,I have used the Visual C++6.0 and take example for the three time Bezier parameter curve ,a common parameter curve{x=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3

11、+Y2t2+Y1t+Y0, 0t1} and a curve that my teacher gived to me to complete the program.</p><p>　　Keywords：curve，point to point，double step，Visual C++6. 0 </p><p><b>　　Author: <

12、;/b></p><p><b>　　July 2003</b></p><p><b>　　目 錄</b></p><p>　　摘 要………………………………………………………………………….…1</p><p>　　第一章 與本畢業(yè)設(shè)計相關(guān)的Visual C++內(nèi)容介紹</p>

13、;<p>　　1.1 Visual C++6.0簡介…………………………………………………………………4</p><p>　　1.2 與本畢業(yè)設(shè)計有關(guān)的Visual C++內(nèi)容介紹……………………………………….5</p><p>　　第二章 計算機圖形學(xué)中常用的算法</p><p>　　2.1 常用直線的繪制算法…………………………………………

14、……………………6</p><p>　　2.2 常用的參數(shù)曲線的繪制算法……………………………………………………...7</p><p>　　第三章 參數(shù)曲線的快速生成算法及實現(xiàn)</p><p>　　3.1 普通參數(shù)曲線生成算法的介紹…………………………………………………..11</p><p>　　3.2 最佳的步長值……………………

15、……………………………………………..…13</p><p>　　3.3 雙步逐點曲線生成算法…………………………………………………………..14</p><p>　　3.4 以三次Bezier曲線為例編程實現(xiàn)該算法………………………………………..16</p><p>　　3.5 普通參數(shù)曲線方程的編程實現(xiàn)…………………………………………………..28<

16、;/p><p>　　3.6 使用雙步逐點曲線生成算法需要注意的一個問題……………………………..31</p><p>　　第四章 導(dǎo)師所給的參數(shù)方程的研究</p><p>　　4.1 通過在屏幕上鼠標點擊若干點然后繪制曲線………………………………….32</p><p>　　4.2 通過在對話框中輸入控制點的坐標繪制曲線…………………………

17、……….36</p><p>　　第五章 結(jié)論………………………………………………………………………………38</p><p>　　第六章 個人小結(jié)……………………………………………………………...39</p><p><b>　　第七章 附錄</b></p><p>　　英文資料翻譯……………………………………………

18、………………………...40</p><p>　　參考文獻…………………………………………………………………………...48</p><p>　　第一章 與本畢業(yè)設(shè)計相關(guān)的Visual C++的內(nèi)容介紹</p><p>　　1.1 Visual C++簡介</p><p>　　Visual C++6.0是美國Mcrosoft公司在多年使用過

19、程中不斷改進的基礎(chǔ)上推出的，用于支持Win32、Windows95/98和Windows NT平臺的應(yīng)用程序、服務(wù)和控件開發(fā)的工具。</p><p>　　隨著計算機多媒體技術(shù)和圖形圖象技術(shù)的蓬勃發(fā)展，特別是Windows操作系統(tǒng)在微機中的大量使用，可視化技術(shù)得到了人們的廣泛的重視，越來越多的計算機專業(yè)人員和非專業(yè)人員都開始研究并應(yīng)用可視化技術(shù)。一般來說，可視化技術(shù)包含兩個方面的含義。一是可視化編程，也就是軟件開發(fā)

20、階段的可視化，可視化編程使得工作輕松愉快、饒有趣味，給軟件開發(fā)人員以一種全新的感受?？梢暬夹g(shù)的另一含義就是利用計算機圖形學(xué)的方法和技術(shù)，對收集到的大量數(shù)據(jù)進行處理，并用圖形圖象的方式直觀而具體的顯示出來。</p><p>　　要支持可視化編程，就需要有相應(yīng)的可視化開發(fā)環(huán)境，而Visual C++6.0就是目前使用極為廣泛的支持可視化編程的集成環(huán)境。</p><p>　　像其他的可視化集成

21、開發(fā)環(huán)境（如Visual Basic、Delphi、C++ Build）一樣，VC6集程序的代碼編輯、編譯、連接、調(diào)試等于一體，給編程人員提供了一個完整而又方便的開發(fā)界面和許多有效的輔助開發(fā)工具。VC++6.0的AppWizard可以為很大一部分類型的程序提供框架代碼，用戶不需要書寫代碼，只需要按幾個按鈕就可以生成一個完整的可以運行的程序。</p><p>　　和其他可視化集成開發(fā)環(huán)境比較，用VC6做一些普通常見

22、的界面可能體現(xiàn)不出什么優(yōu)勢，甚至有時候還很麻煩，需要書寫更多的代碼，但用VC6做界面更加靈活，尤其當用戶需要定制一些特別的界面時用VC6更加方便。因為VC6基于C++語言，又來自Windows操作系統(tǒng)，所以在眾多的可視化集成開發(fā)環(huán)境中，VC6是Windows底層編程的最佳選擇。</p><p>　　Visual C++6. 0在它前一版本的基礎(chǔ)上做了很大改進，提供了許多新的特點，如下所述：</p>

23、<p>　　· 編譯器較前一版得到了很大的改進，不但可以支持ANSI C++新標準，現(xiàn)在也可以支持布爾類型，并且對于摸板的支持也得到了相當?shù)母纳啤?lt;/p><p>　　· Visual C++6. 0開發(fā)環(huán)境Developer Studio是由Windows95/98或Windows NT環(huán)境下運行的一套集成工具所組成，The Developer Studio編輯器有了很大的改善，

24、它具有允許編輯器為你自動完成通用語句編輯的特點。使用Developer Studio，不僅可以創(chuàng)建由Visual C++6. 0使用的源文件和其它文檔，而且可以創(chuàng)建、查看和編輯與任何與ActiveX部件有關(guān)的項目和項目配置，可以使用工作區(qū)窗口來查看和訪問項目中的各種元素。</p><p>　　· 這個開發(fā)系統(tǒng)包括一些增加的MFC庫的新功能。增加了用于Internet Explore和Windows98中

25、編程的新的通用控件。</p><p>　　· Visual C++6. 0提供了快速的集成數(shù)據(jù)苦訪問，允許用戶建立強有力的數(shù)據(jù)庫應(yīng)用程序，可以使用ODBC類和高性能的32位ODBC驅(qū)動程序來訪問各種數(shù)據(jù)庫管理系統(tǒng)，也可以使用DAO（數(shù)據(jù)訪問對象）類通過編程語言來訪問和操縱數(shù)據(jù)庫中的滬劇并管理數(shù)據(jù)庫、數(shù)據(jù)庫對象與結(jié)構(gòu)。</p><p>　　· Visual C++6. 0

26、對Internet提供了強有力的支持，Win32 Internet API使Internet成為應(yīng)用程序的一部分并簡化了對Internet服務(wù)（FTP、HTTP和Gopher）的訪問。ActiveX控件可以用在Internet和桌面應(yīng)用程序中，其文檔可以顯示在整個Web瀏覽器中，同時，可以使用ChttpServer，ChttpFilter，ChttpServerContext，ChttpFilterContext和ChttpStream

27、類來創(chuàng)建動態(tài)連接庫以便添加功能到Internet服務(wù)器和Web頁中。</p><p>　　· 一個增強型的在線幫助系統(tǒng)使得Visual C++6. 0變的容易學(xué)習(xí)，只須單擊鼠標即可實現(xiàn)。若你在機器上安裝了MSDN，再線幫助系統(tǒng)將自動使用最新的MSDN版本。</p><p>　　1.2 與本畢業(yè)設(shè)計有關(guān)的Visual C++的內(nèi)容介紹</p><p>　　在

28、本次畢業(yè)設(shè)計中，為了能夠方便的顯示生成的參數(shù)曲線，主要通過使用Visual C++6.0生成基于Doc/View結(jié)構(gòu)的單文檔應(yīng)用程序來實現(xiàn)參數(shù)曲線的生成算法，并在程序運行后的視圖窗口上顯示該曲線。</p><p>　　在基于Doc/View結(jié)構(gòu)的應(yīng)用程序中，Cview類的主要作用是用來管理視圖包括處理用戶（鍵盤或鼠標）輸入和在視圖窗口上顯示文檔的數(shù)據(jù)等；CDocument類負責(zé)管理程序的數(shù)據(jù)并提供程序數(shù)據(jù)的文件I

29、/0功能以及存儲Cview類所要觀察和處理的信息。在生成參數(shù)曲線的實現(xiàn)程序中使用到了有關(guān)CView類的視圖窗口響應(yīng)鼠標輸入和在視圖窗口中畫點的相關(guān)知識，以及CDocument類的有關(guān)視圖窗口內(nèi)容重繪的相關(guān)知識，并在程序中添加了對話框資源以能夠?qū)崿F(xiàn)在對話框中手動輸入方程的系數(shù)來完成繪制不同的參數(shù)曲線。</p><p>　　為了能夠在屏幕上畫點和改變鼠標形狀，首先需要在程序中為視圖類增加有關(guān)的數(shù)據(jù)成員。首先在View

30、類的頭文件中加入HCURSOR類型的變量m_hCross，數(shù)據(jù)變量m_hCros是鼠標句柄，然后在View類實現(xiàn)文件中的構(gòu)造函數(shù)中通過語句m_hCross=AfxGetApp()->LoadStandCursor(IDC_CROSS)初始化該變量，該語句的作用是取得Windows標準鼠標形狀句柄并賦給m_hCross，然后就可以通過ClassWizard添加鼠標動作的消息處理函數(shù)。例如，要為程序添加鼠標左鍵單擊消息處理函數(shù)，首先在

31、打開的ClassWizard對話框中的Class name組合框中選擇View類，然后在Object Ids列表框選中第一行，并在Message列表框中選中WM_LBUTTONDOWN一行，最后單擊Add Function按鈕即可。類似的還可以為程序添加WM_RBUTTONDOWN（鼠標右鍵單擊）消息處理函數(shù)。因為需要逐點地生成曲線，因此在程序中需要使用到MFC（Microsoft Fundation Class）中的CDC（設(shè)備上下文

32、）類的成員函數(shù)SetPixel（</p><p>　　第二章 計算機圖形學(xué)中常用的算法</p><p>　　2.1 常用直線的算法</p><p>　　畫直線的算法有很多，例如數(shù)值微分法，中點畫線法，Bresenham化線算法等。在這里只介紹一個比較方便常用的中點畫線法。</p><p>　　為了討論方便，本小節(jié)假定直線斜率在0、1之間。其他

33、情況可參照下述討論進行處理。如圖所示，若直線在x方向增加一個單位，則在y方向上的增量只能在0、1之間。假設(shè)x坐標為xp的各象素點中，與直線最近者已確定，為(xp,yp)，用實心小圓表示。那么，下一個與直線最近的象素只能是正右方的P1(xp+1,yp)或右上方的P2(xp+1,yp+1)兩者之一，用空心小圓表示。再以M 表示P1、P2的中點，即M=(xp+1,yp+0.5）。又設(shè)想Q是理想直線與垂直直線x=xp+1的交點。顯然，若M在Q的

34、下方，則P2離直線近，應(yīng)取為下一個象素；否則應(yīng)取P1。這就是中點畫線法的基本原理。</p><p>　　中點畫線算法每步迭代涉及的象素和中點示意圖</p><p>　　下面來討論上述算法的實現(xiàn)。假設(shè)直線的起點和終點分別是(x0,y0)，(x1,y1)。則直線的方程為</p><p>　　F(x,y) = ax + by + c=0</p><p&

35、gt;　　其中，a = y0-y1，b = x1-x0，c = x0yi-x1y0。對于直線上的點，F(xiàn)(x,y)=0；對于直線上方的點，F(xiàn)(x,y)>0；而對于直線下方的點F(x,y)<0。因此，欲判斷前述Q在M的上方還是下方，只要把M代入F(x,y)，并判斷它的符號。構(gòu)成判別式</p><p>　　d=F(M)=F(xp+1,yp+0.5)=a(xp+1) + b(yp+0.5) + c</p

36、><p>　　當d<0時，M在直線下方（即在Q的下方），故應(yīng)取右上方的P2作為下一個象素。而當d>0時，則應(yīng)取正右方的P1。當d=0時，二者一樣合適，可以隨便取一個。我們約定取正右方的P1。</p><p>　　對每一個象素計算判別式d，根據(jù)它的符號確定下一個象素。至此可以寫出完整的算法。但是注意到d是xp和yp的線形函數(shù)，可采用增量計算，提高運算效率。在d0的情況下，取正右方象素

37、P1，欲判斷再下一個象素應(yīng)取哪個，應(yīng)計算</p><p>　　d1=F(xp+2，yp+0.5) =a(xp+2) + b(yp+0.5)+ c= d + a</p><p>　　故d 的增量為a。而若d<0，則右上方的象素P2，欲判斷再下一個象素，則要計算</p><p>　　d2=F(xp+2，yp+1.5)=a(xp+2)+b(yp+1.5)+ c =

38、d + a + b</p><p>　　故在第二種情況，d 的增量為a+b。</p><p>　　再看d的初值。顯然，第一個象素應(yīng)取左端點(x0,y0)，相應(yīng)的判別式為</p><p>　　d0=F(x0+1,y0+0.5)=a(x0+1)+ b(y0+0.5) + c</p><p>　　= ax0+by0+a+c+0.5b</p&g

39、t;<p>　　= F(x0，y0)+ a+0.5b</p><p>　　但由于(x0,y0)在直線上，故F(x0,y0)=0。因此，d的初值為d0= a+0.5b。</p><p>　　由于使用的只是d 的符號，而且d的增量都是整數(shù)，只是其初值包含小數(shù)。因此我們可以使用2d代替d，來擺脫小數(shù)，寫出僅包含整數(shù)的算法：</p><p>　　MidPoin

40、tLine(x0,y0,x1,y1,color)</p><p>　　int x0,y0,x1,y1,color;</p><p><b>　　{</b></p><p>　　int a,b,delta1,delta2,d,x,y;</p><p>　　a= x0- y1;</p><p><

41、;b>　　b=x1- x0;</b></p><p>　　delta1=2*a;</p><p>　　delta2=2*(a+b);</p><p><b>　　x= x0;</b></p><p><b>　　y=y0 ;</b></p><p>　　dr

42、awpixel(x,y,color);</p><p>　　while(x< x1)</p><p><b>　　{ </b></p><p><b>　　if(d<0)</b></p><p>　　{ x++;y++;</p><p>　　d+= delta2

43、;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{x++;</b></p><p>　　d+= delta1;</p><p><b>　　}</b></p

44、><p>　　drawpixel(x,y,color);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　2.2 常用的參數(shù)曲線的繪制算法</p><p>　　常用的參數(shù)曲線有許多，如Bezier，B樣條，非均勻有理B樣條、圓錐

45、曲線等。本小節(jié)將以Bezier曲線為代表，講解其繪制算法。</p><p>　　Bezier曲線的公式 ：給定空間n+1個點的位置矢量Pi，Bezier曲線上各點坐標的插值公式是：</p><p>　　C(t) =, 0t1</p><p>　　Pi構(gòu)成該曲線的特征多邊形，是Bernstein基函數(shù)，也是曲線上各點位置矢量的調(diào)和函數(shù)。</p><

46、p>　　=ti(1-t)n-i=Cti(1-t)n-i i=0,1,2,…n</p><p>　　首先，討論三次Bezie曲線的繪制</p><p>　　由上述公式可以推出三次Bezier曲線形式：</p><p>　　當n=3時,C(t)= = P0(1－t)3 + 3P1t (1－t)2 + 3P2 t2 (1－t) + P3t3 0t1</p

47、><p>　　可以將其改寫為如下的形式：</p><p>　　C3(t) = (( CS P0+ Ct P1)S+Ct2 P2 )S+ Ct3P3</p><p>　　其中，S=1-t，則可以通過如下程序繪制曲線：</p><p>　　float hornbez(degree,coeff,t)</p><p>　　/* I

48、nput:degree:曲線的次數(shù)</p><p>　　coeff:保存曲線的系數(shù)</p><p>　　t: 參數(shù)的值</p><p>　　Output: 該參數(shù)的坐標值</p><p><b>　　*/</b></p><p>　　int degree;</p><p&

49、gt;　　float coeff[];</p><p><b>　　float t;</b></p><p><b>　　{</b></p><p>　　int i,n_choose_i;</p><p>　　float fact,t1,aux;</p><p><b&

50、gt;　　t1=1.0-t;</b></p><p><b>　　fac=1.0;</b></p><p>　　n_choose_i=1;</p><p>　　aux=coeff[0]*t1; /*開始循環(huán)計算坐標值*/</p><p>　　for(i=1i<degree;i++)</p>

51、<p><b>　　{</b></p><p>　　fact = fact*t;</p><p>　　n_choose_i= n_choose_i*(degree-i+1)/i;</p><p>　　aux=(aux+fact* n_choose_i*coeff[i]*t1;</p><p><b&g

52、t;　　}</b></p><p>　　aux=aux+fact*t*coeff[degree];</p><p>　　return aux;</p><p><b>　　}</b></p><p>　　下面來討論n次Bezier曲線的繪制。在前面我們介紹了一個程序用于計算相應(yīng)曲線上的諸點，但其只適用于三次B

53、ezie曲線，既不通用而且計算量較大。用如下Cas-teljau算法產(chǎn)生曲線上的點列相對要簡單許多。</p><p>　　Cas-teljau算法：給定空間n+1個點Pi(i=0,1,2,…n)及參數(shù)t，則有：</p><p>　　(t)=(1-t)(t)+ t(t)</p><p>　　r=1,2….n, i=0,1….n-r, 0t1</p>&l

54、t;p>　　其中(t)即為Pi, (t)是曲線上具有參數(shù)t的點。</p><p>　　當n=3時，用Cas-teljau算法遞推出的(t)呈直角三角形，對應(yīng)如下所示：</p><p>　　該三角形垂直邊上的點P0，P1，P2， P3是曲線P(t)在0t1內(nèi)的控制點，斜邊上的點是P(t)在0t1/2內(nèi)的控制點，水平直角邊上的點是P(t)在1/2t1內(nèi)的控制點。這種用分割Bezier曲線

55、控制多邊形的方法為離散化的曲線提供了方便。用Cas-teljau算法繪制Bezier曲線的程序如下：</p><p>　　void bez_to_points(degree,npoints,coeff,points)</p><p>　　/*Input :degree:曲線的次數(shù)</p><p>　　npoint:控制點的數(shù)目</p><p>

56、;　　coeff::控制點的坐標</p><p>　　Output: 曲線上點的坐標</p><p><b>　　*/</b></p><p>　　int degree,npointes;</p><p>　　float coeff[],points[];</p><p><b>　　{

57、</b></p><p>　　float t,delt;</p><p><b>　　int i;</b></p><p>　　float decas();</p><p>　　delt=1.0/(float)npoints; /*步長*/</p><p><b>　　t=

58、0.0;</b></p><p>　　for(i=0;i<=npoints;i++)</p><p><b>　　{</b></p><p>　　points[i]=decas(degree,coeff,t);</p><p><b>　　t=t+delt;</b></p&g

59、t;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　float decas(degree,coeff,t)</p><p>　　float coeff[];</p><p><b>　　float t;</b></

60、p><p>　　int degree;</p><p><b>　　{</b></p><p><b>　　int r,i;</b></p><p><b>　　float t1;</b></p><p>　　float coeffa[10];</p&

61、gt;<p><b>　　t1=1.0-t;</b></p><p>　　for(i=1;i<=degree;i++)</p><p>　　coeffa[i]=coeff[i];</p><p><b>　　/*計算(t)地值</b></p><p>　　for(r=1;r<

62、;=degree;r++)</p><p>　　for(i=1;r<=degree-r;i++)</p><p><b>　　{</b></p><p>　　coeffa[i]=t1*coeffa[i]+t*coeffa[t+1];</p><p><b>　　}</b></p>

63、<p>　　return(coeffa[0]);</p><p><b>　　}</b></p><p>　　第三章 參數(shù)曲線的快速生成算法及實現(xiàn)</p><p>　　普通參數(shù)曲線生成算法的介紹</p><p>　　本畢業(yè)設(shè)計所研究的參數(shù)曲線生成算法要具備直接、逐點、快速的特點。要直接生成參數(shù)曲線就需要對曲線

64、的參數(shù)每次增加一個步長，然后計算該點的坐標值x和y并繪制該點。要逐點地生成參數(shù)曲線，就要求參數(shù)每次增加的步長要使曲線前進的幅度不得超過一個象素的長度，否則有可能跨過一個中間象素而產(chǎn)生斷點。要快速生成曲線則要求在不產(chǎn)生斷點的情況下盡量減少畫點次數(shù)以及不重復(fù)畫一個象素點來達到加快曲線的生成速度。</p><p>　　根據(jù)參考文獻可以得到一個滿足上述要求的逐點生成參數(shù)曲線的整數(shù)算法。設(shè)曲線的參數(shù)方程為：</p&g

65、t;<p>　　首先討論第一個方程x=f( t ),首先把曲線分成n 段（限定t取i/n，其中0in。）根據(jù)拉格朗日中值定理：f(x+x)－f( x )=f’()(x)，當n 滿足n時，可以得到如下公式：</p><p><b>　　=1 （3.1）</b></p><p>　　根據(jù)公式3.1，可以使得算法中每次循環(huán)，即每步前進不超過1個象素，從而保證

66、了曲線的連續(xù)性。為了只使用整數(shù)運算，可將方程x=f(t)乘一正整數(shù)N，使其轉(zhuǎn)換成整數(shù)方程：</p><p>　　Nxi =( i ) + zi ， </p><p>　　其中( i )=N·f(),它和xi (x坐標的整數(shù)位置)及其余數(shù)zi ()均為整數(shù)。各個量的含義如下圖所示。xi表示與計算出的值f()最近的象素點的x坐標。余數(shù)zi 表示xi</p><p

67、>　　(a) (b)</p><p>　　圖1-1 xi與 f()兩者的關(guān)系 </p><p>　　與f()的差距（當然為了整數(shù)化，也乘了一個N值）。若是圖（a）的情況，則zi為負值，即取曲線左邊的象素點；若是圖（b）的情況，則 zi為正值，即取曲線右邊的象素點。</p><p>　　算法逐點計算曲線上的象素。

68、設(shè)當前象素點的x坐標是xi，則下一點的x坐標xi+1應(yīng)該滿足</p><p>　　N xi+1 = (i+1) + zi+1，</p><p>　　其中 (i+1)=( i )+( i )=Nxi－zi +( i )</p><p><b>　　根據(jù)3.1式有：</b></p><p><b

69、>　　=NN，</b></p><p>　　而，所以N。因此，xi+1的可能取值為xi－1，xi 或xi +1。這樣就得到了xi+1和zi+1的計算公式：</p><p><b>　　xi+1</b></p><p><b>　　zi+1</b></p><p>　　這樣，就得到了

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

71、<p>　　n = max (nx，ny)</p><p>　　其中nx和ny分別對于x坐標和y坐標選擇的n的值，為</p><p><b>　　nx=· m ·</b></p><p><b>　　ny=· m ·</b></p><p>　　其

72、中m為曲線的次數(shù)。</p><p>　　而該參考文獻又對nx和ny值進行了進一步的優(yōu)化，減小了n 的值，取：</p><p><b>　　nx= m ·</b></p><p><b>　　ny= m ·</b></p><p>　　其中X和Y是曲線第i個控制點的坐標?？梢宰C明這

73、樣選擇的n值滿足上述的條件n。</p><p><b>　　最佳的步長值</b></p><p>　　根據(jù)參考文獻中對上述算法進行編程和分析運行結(jié)果，發(fā)現(xiàn)該算法在繪制曲線時每次循環(huán)使曲線前進的幅度的最大值往往不能接近于1（多數(shù)在0.6至0.8之間）。這說明在上一小節(jié)介紹的算法中的n的取值并沒有達到最佳值。從理論上分析，我們的目標是要找到滿足條件n的最小的n值，即尋找的

74、最小上界。上述的m ·雖然是的一個上界，但并不是其最小上界。下面將討論如何求出的最小上界以及最佳的n值。</p><p>　　的最小上界顯然應(yīng)該出現(xiàn)在f’(t)的極值點處或曲線的端點處，即當參數(shù)t = 0或 t =1處，因此應(yīng)該以在曲線的兩端點處和其在兩端點之間的極值點處的函數(shù)值中的最大者作為其最小上界。由于我們采用了求函數(shù)的最大極值作為其上界，因此它是最小上界，因為該上界就在曲線上，如果它再小一點則必

75、有曲線上的一點大于它。下面我們將以三次Bezier曲線為例描述最佳n的計算過程。對于三次Bezier曲線：</p><p>　　f( t ) = X0(1－t)3 + 3X1t (1－t)2 + 3X2 t2 (1－t) + X3t3</p><p><b>　　對其求導(dǎo),得</b></p><p>　　f’ ( t )=3[(X1－X0)(1

76、－t)2 + 2(X2 － X1)(1－t)t + (X3－X2) t2]</p><p>　　=3{[X3－X2－2(X2－X1)+X1－X0] t2</p><p>　　+2(X2－2X1+X0) t + X1－X0}，</p><p>　　要求f’(t)的極值點就要將其對t 再次求導(dǎo)并另其導(dǎo)函數(shù)為0，得：</p><p>　　6{[X3

77、－3(X2－X1)－X0] t + X2－2X1 + X0}= 0 </p><p>　　設(shè)V= X2－2X1 + X0，W= X3－3(X2－X1)－X0；由上式得，當t=－時，f’( t )取到極值3[X1－X0－]。顯然，在端點處( t = 0 和t = 1)的值分別為3和3。所以，nx的取值為</p><p>　　當－[0，1]時 nx = 3）</p><p

78、>　　當－[0，1]時，nx = 3）</p><p>　　同理，根據(jù)ny來求得ny 的值。最后取 n = max(nx,ny)，從而得到了最佳的n值。</p><p>　　由上面的討論可知，n值決定了算法的循環(huán)次數(shù)，n值愈小，算法的速度愈快。在上面計算得到的n值已經(jīng)比較理想了，那么，是否還可以再進一步減小n值呢？下面提出一個雙步逐點曲線生成算法來進一步減小n值。</p>

79、<p>　　3.3 雙步逐點曲線生成算法</p><p>　　從上一小節(jié)的描述可知，新算法通過求極值已經(jīng)找到了滿足條件n的最小n值。如果再進一步減小n的值，則在曲線上可能出現(xiàn)斷點，即曲線前進的幅度大于了一個象素的長度，從而漏過了一個中間的象素。</p><p>　　在前面求得的最小n值的基礎(chǔ)上，本小節(jié)提出雙步逐點曲線生成算法，其基本思想是，將n 值減小二分之一（即將步長增加

80、一倍）。這樣當曲線前進一步時，其幅度有時會大于一個象素的長度。為了不使曲線出現(xiàn)漏點，我們通過插值的方法來確定跨過的那個中間象素。用此方法可使上一小節(jié)提出的算法的循環(huán)次數(shù)減少一半，并大大提高了參數(shù)曲線的生成速度。</p><p>　　下面將具體描述雙步逐點曲線生成算法的思想。設(shè)n 仍是上節(jié)計算出的單步算法的n 值。為了保證算法的雙步特性，將3.1式（拉格朗日中值定理）=1乘2，得</p><p&

81、gt;<b>　　= 2</b></p><p>　　該式保證了雙步算法在將步長增加一倍（即n值減小二分之一）時，曲線每次前進的幅度不會大于兩個象素的長度。</p><p>　　我們還是先討論x坐標的情況，y坐標與x坐標同理。設(shè)當前點坐標xi已經(jīng)確定，則下一點的x 坐標xi+1應(yīng)該滿足</p><p>　　Nxi+1 = (i+1) + zi+

82、1 ,</p><p><b>　　其中</b></p><p>　　(i+1)=( i ) +( i )= Nxi－zi +( i )</p><p>　　由第一小節(jié)中的等式=NN可知：</p><p><b>　　= N=（）2N，</b></p><p><b&g

83、t;　　而，所以</b></p><p><b>　　N</b></p><p>　　可以看出，xi+1的可能取值為xi－2，xi－1，xi，xi +1和xi +2。由上面的討論就得到了xi+1的計算公式：</p><p>　　當 (k－)N (i)－zi < (k+)N時， xi+1 = xi + k。</p>

84、<p>　　其中k=－2,－1,0 ,1,2 。</p><p>　　而由zi+1 =N xi+1－(i+1) 可以得到zi+1的計算公式：</p><p>　　當xi+1 = xi + k時，zi+1= zi－( i ) + kN。其中 k=－2,－1,0 ,1,2。這樣，就得到了xi+1和zi+1的遞推公式，通過它我們就可以計算出下一象素點的x坐標和下一步的余數(shù)z 。<

85、;/p><p>　　下面我們來討論當曲線前進一步時，其幅度大于一個象素的長度的情況。當x坐標增加或減少的幅度大于一個象素長度（即xi+1 = xi + 2 或xi+1 = xi－2）時，就要通過插值的方法來確定被跨過的那個中間象素。這要分幾種情況來考慮，以坐標增加的情況為例：</p><p>　　·如果y坐標沒有增加（即yi+1 = yi），則顯然應(yīng)該選擇中間象素（xi +1, yi

86、</p><p>　?。┤缦聢D（a）的情況；</p><p>　　·如果y坐增加2（即yi+1 = yi + 2），則顯然應(yīng)該選擇中間象素（xi +1, yi + 1</p><p>　?。┤缦聢D（b）的情況；</p><p>　　·如果y坐增加1（即yi+1 = yi + 1），則應(yīng)該選擇中間象素（xi +1, yi）和

87、（xi +1, yi + 1）中距離曲線較近的一個。選擇的方法是將y的坐標的增加的幅度減少一半，然后判斷是否大于N/2（參見上述算法原理）。若大于N/2，則選擇（xi +1, yi + 1），否則選擇（xi +1, yi）。如下圖（c）、（d）的情況</p><p>　　圖（a） 圖（b）</p><p>　　圖（c）

88、 圖（d）</p><p>　　為了提高計算速度，計算過程應(yīng)盡量避免使用乘法運算，因此這里在每次循環(huán)計算下一點的函數(shù)插值時，引入了差分運算，通過降階的方法，就可以用加法來代替乘法運算。</p><p>　　差分的定義：設(shè)函數(shù)f( x )在等距節(jié)點處的函數(shù)值f(xk) = yk (k=0,1,2…) ，則稱兩個節(jié)點xk和xk+1 處函數(shù)值

89、之差yk+1－yk為函數(shù)f( x )在xk處以h為步長的一階差分，記作yk，即</p><p>　　yk =yk+1－yk</p><p>　　稱節(jié)點xk和xk+1 處一階差分之差yk+1－yk為f(x)在xk處二階差分，記作2yk，即</p><p>　　2yk =(yk)=yk+1－yk</p><p>　　一般地，稱m－1階差分的差分&

90、lt;/p><p>　　myk =(m－1yk) =m－1yk+1－m－1yk</p><p>　　為f(x)在xk處的m階差分。</p><p>　　回到上述算法的討論當中，由上述差分公式可得：</p><p>　　k+1( i ) =k(i+1)－k( i )</p><p><b>　　得</b>

91、;</p><p>　　k(i+1)=k( i )－k+1( i ) ，k=0,1…,m.</p><p>　　根據(jù)差分的性質(zhì)可知，m次多項式的m階差分恒為常數(shù)，則當i處的各階差分已知時，用m次加法即可求得i + 1處的各階差分。在計算xi+1和zi+1時，并未用到函數(shù)值(i+1)，而只用到了函數(shù)的一階差分(i+1)，這只需m－1次整數(shù)加法即可求得。</p><p>

92、;　　對于y坐標同理可以得到類似的結(jié)果。我們將在下一小節(jié)編程實現(xiàn)該雙步曲線生成算法。</p><p>　　3.4 以三次Bezier曲線為例編程實現(xiàn)該算法</p><p>　　下面是以三次Bezier為例的算法實現(xiàn)程序，其中(x，y)表示當前象素；a1，a2，a3和b1，b2，b3分別表示f和g的一、二、三階差分k( i )和k( i ) (k=1，2，3)；z1和z2分別表示f和g的余

93、項zi；變量fx和fy用于消除角點象素，fx為1表示前一個象素是通過x坐標加1（y坐標不變）來到當前象素的，fy為1表示前一個象素是通過y坐標加1（x坐標不變）來到當前象素的。所謂角點象素就是如下圖所示的象素。當fx為1時，如果求出的下一個象素是向y軸方向走，則說明當前象素是角點象素，因此不能畫出。fy有同樣的作用?？梢?，在程序中只有求出下一個象素時才能確定是否畫當前象素。</p><p>　　該程序的關(guān)鍵部分為

94、循環(huán)畫點的for語句，在此循環(huán)語句中，分別以xi+1=xi-2，xi+1=xi-1，xi+1=xi，xi+1=xi+1，xi+1=xi+2五種情況，在每種情況中又分別以yi+1=yi-2，yi+1=yi-1，yi+1=yi，yi+1=yi+1，yi+1=yi+2這五種情況來分別討論曲線的畫點情況。</p><p><b>　　角點象素示意圖</b></p><p>　

95、　算法的實現(xiàn)程序如下：</p><p>　　void CBiYeSheJiView::OnBezier() </p><p><b>　　{</b></p><p>　　//初始化控制點坐標的值</p><p>　　int x0=120,x1=300,x2=20,x3=160,y0=40,y1=240,y2=200,y3

96、=40;</p><p>　　CDC *pDC=GetDC();</p><p>　　//定義一個刷子用于刷新屏幕</p><p>　　CBrush brush(RGB(255,255,255));</p><p>　　CRect rect;</p><p>　　GetClientRect(rect);</p&g

97、t;<p>　　pDC->FillRect(&rect,&brush);</p><p>　　long u=3,n,N;</p><p>　　long f0,f1,f2,f3,g0,g1,g2,g3;</p><p>　　long a1,a2,a3,b1,b2,b3;</p><p>　　long V,W,

98、M,T;</p><p><b>　　//計算nx的值</b></p><p>　　long nx=labs(x1-x0)>labs(x3-x2)?labs(x1-x0):labs(x3-x2);</p><p>　　V=x2-2*x1+x0;</p><p>　　W=x3+3*(x1-x2)-x0;</p&

99、gt;<p><b>　　T=-V/W;</b></p><p>　　if(T>0 && T<1)</p><p><b>　　{</b></p><p>　　M=x1-x0+V*T;</p><p>　　if(M<0) M=-M;</p>

100、<p>　　if(M>nx) nx=M;</p><p><b>　　}</b></p><p><b>　　//計算ny的值</b></p><p>　　long ny=labs(y1-y0)>labs(y3-y2)?labs(y1-y0):labs(y3-y2);</p><

101、;p>　　V=y2-2*y1+y0;</p><p>　　W=y3+3*(y1-y2)-y0;</p><p><b>　　T=-V/W;</b></p><p>　　if(T>0 && T<1)</p><p><b>　　{</b></p><

102、;p>　　M=y1-y0+V*T;</p><p>　　if(M<0) M=-M;</p><p>　　if(M>ny) ny=M;</p><p><b>　　}</b></p><p>　　nx=u*nx;ny=u*ny;</p><p>　　n=nx>ny?nx:ny

103、;</p><p>　　//將n的值減小1/2</p><p><b>　　n=n>>1;</b></p><p>　　//使f0, f1, f2, f3,g0,g1,g2,g3都為整數(shù)</p><p><b>　　N=n*n*n;</b></p><p>　　/

104、/計算當t=0，t=1/n，t=2/n，t=3/n時f與g的值</p><p><b>　　f0=N*x0;</b></p><p>　　f1=x0*(n-1)*(n-1)*(n-1)+3*x1*(n-1)*(n-1)+3*x2*(n-1)+x3;</p><p>　　f2=x0*(n-2)*(n-2)*(n-2)+6*x1*(n-2)*(n-

105、2)+12*x2*(n-2)+8*x3;</p><p>　　f3=x0*(n-3)*(n-3)*(n-3)+9*x1*(n-3)*(n-3)+27*x2*(n-3)+27*x3;</p><p><b>　　g0=N*y0;</b></p><p>　　g1=y0*(n-1)*(n-1)*(n-1)+3*y1*(n-1)*(n-1)+3*y2

106、*(n-1)+y3;</p><p>　　g2=y0*(n-2)*(n-2)*(n-2)+6*y1*(n-2)*(n-2)+12*y2*(n-2)+8*y3;</p><p>　　g3=y0*(n-3)*(n-3)*(n-3)+9*y1*(n-3)*(n-3)+27*y2*(n-3)+27*y3;</p><p>　　// a1，a2，a3和b1，b2，b3分別表示

107、f和g的一、二、三階差分</p><p><b>　　a1=f1-f0;</b></p><p>　　a2=f2-2*f1+f0;</p><p>　　a3=f3-3*f2+3*f1-f0;</p><p><b>　　b1=g1-g0;</b></p><p>　　b2=g

108、2-2*g1+g0;</p><p>　　b3=g3-3*g2+3*g1-g0;</p><p>　　long x=x0,y=y0;</p><p>　　long z1=0,z2=0;</p><p>　　//畫曲線的第一個點</p><p>　　int fx=0,fy=0;</p><p>　

109、　pDC->SetPixel(x,y,RGB(10,20,20));</p><p><b>　　//循環(huán)畫點</b></p><p>　　for(int i=0;i<=n;i++)</p><p><b>　　{</b></p><p>　　//xi+1=xi-2時的情況 </p

110、><p>　　if(2*(a1-z1)<-N)</p><p>　　if(2*(a1-z1)<-3*N)</p><p><b>　　{</b></p><p>　　if(fx= =1)</p><p><b>　　{</b></p><p>

111、　　pDC->SetPixel(x,y,RGB(10,20,20));</p><p><b>　　fx=0;</b></p><p><b>　　}</b></p><p>　　//xi+1=xi-2時yi+1=yi-2的情況</p><p>　　if(2*(b1-z2)<-N)<

112、;/p><p>　　if(2*(b1-z2)<-3*N)</p><p><b>　　{</b></p><p>　　if(fy==1) pDC->SetPixel(x,y,RGB(10,20,20));</p><p>　　pDC->SetPixel(x-1,y-1,RGB(10,20,20));<

113、/p><p>　　pDC->SetPixel(x-2,y-2,RGB(10,20,20));</p><p><b>　　y=y-2;</b></p><p>　　z2=z2-b1-2*N;</p><p><b>　　}</b></p><p>　　else //xi+

114、1=xi-2時yi+1=yi-1的情況</p><p><b>　　{</b></p><p>　　if(b1-2*z2<-N)</p><p><b>　　{</b></p><p>　　/*b1-2*z2<-N即b1/2-z2<-N2表示增加</p><p&

115、gt;　　差分b1的一半以確定跨過的中間的象素*/</p><p>　　if(fy==1) pDC->SetPixel(x,y,RGB(10,20,20));</p><p>　　pDC->SetPixel(x-1,y-1,RGB(10,20,20));</p><p><b>　　fx=1;</b></p><

116、p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　pDC->SetPixel(x-1,y,RGB(10,20,20));</p><p>　　pDC->SetPixel(x-2

117、,y-1,RGB(10,20,20));</p><p><b>　　}</b></p><p><b>　　y=y-1;</b></p><p>　　z2=z2-b1-N;</p><p><b>　　}</b></p><p><b>　　

118、else </b></p><p>　　if(2*(b1-z2)<N) //xi+1=xi-2時yi+1=yi的情況</p><p><b>　　{ </b></p><p>　　pDC->SetPixel(x-1,y,RGB(10,20,20));</p><p><b>　　z2

119、=z2-b1;</b></p><p><b>　　fx=1;</b></p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　if(2*(b1-z2)<3*N) //xi+1=xi-2時yi+1=yi+1

120、</p><p><b>　　{ </b></p><p>　　if(b1-2*z2>N)</p><p><b>　　{</b></p><p>　　if(fy= =1) pDC->SetPixel(x,y,RGB(10,20,20));</p><p>　　

121、pDC->SetPixel(x-1,y+1,RGB(10,20,20));</p><p><b>　　fx=1;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b>&

122、lt;/p><p>　　pDC->SetPixel(x-1,y,RGB(10,20,20));</p><p>　　pDC->SetPixel(x-2,y+1,RGB(10,20,20));</p><p><b>　　}</b></p><p><b>　　y=y+1;</b></p