參數(shù)曲線的快速生成算法畢業(yè)論文+外文文獻(xiàn)翻譯.doc
約48頁DOC格式手機(jī)打開展開
參數(shù)曲線的快速生成算法畢業(yè)論文+外文文獻(xiàn)翻譯,摘 要本畢業(yè)設(shè)計(jì)主要研究參數(shù)曲線的直接快速生成，要直接生成參數(shù)曲線就需對參數(shù)方程{x=f(t),y=g(t),(0 t 1)}的參數(shù)t每次增加一個(gè)步長，然后計(jì)算該點(diǎn)的x和y坐標(biāo)值并繪制該點(diǎn)。要逐點(diǎn)地生成參數(shù)曲線，就要求參數(shù)t每次增加的步長要使曲線前進(jìn)的幅度不得超過一個(gè)象素長度，否則有可能跨過一個(gè)中間象素而產(chǎn)生斷點(diǎn)。為了...
內(nèi)容介紹
此文檔由會(huì)員 wanli1988go 發(fā)布
摘 要
本畢業(yè)設(shè)計(jì)主要研究參數(shù)曲線的直接快速生成，要直接生成參數(shù)曲線就需對參數(shù)方程{x=f(t),y=g(t),(0 t 1)}的參數(shù)t每次增加一個(gè)步長，然后計(jì)算該點(diǎn)的x和y坐標(biāo)值并繪制該點(diǎn)。要逐點(diǎn)地生成參數(shù)曲線，就要求參數(shù)t每次增加的步長要使曲線前進(jìn)的幅度不得超過一個(gè)象素長度，否則有可能跨過一個(gè)中間象素而產(chǎn)生斷點(diǎn)。
為了提高曲線生成算法的速度，本畢業(yè)設(shè)計(jì)針對如何選擇最佳的步長進(jìn)行比較討論，以使曲線前進(jìn)的幅度在不超過一個(gè)象素的前提下，選擇盡量大的步長。為了進(jìn)一步提高算法的速度，在前面討論的最佳步長的基礎(chǔ)上又采用了雙步逐點(diǎn)曲線生成算法，即將上述得到的步長增加一倍，以使算法的循環(huán)次數(shù)減少一半。由于步長增加一倍，這樣當(dāng)曲線前進(jìn)一步時(shí)，其幅度有時(shí)會(huì)大于一個(gè)象素的長度，這時(shí)我們通過插值的方法來確定跨過的那個(gè)中間象素。
通過上述討論的算法能夠比較快速的逐點(diǎn)生成曲線，為了實(shí)現(xiàn)上述算法，本畢業(yè)設(shè)計(jì)使用Visual C++6.0為工具并以三次Bezier曲線、普通參數(shù)曲線{x=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3+Y2t2+Y1t+Y0}，以及導(dǎo)師所給的一個(gè)特殊的曲線方程為例編程實(shí)現(xiàn)上述算法。
關(guān)鍵詞：參數(shù)曲線，逐點(diǎn)，雙步，Visual C++6. 0
Abstract
This graduation project main reseach the direct born of the parameter curve {x=f(t),y=g(t),0LoadStandCursor(IDC_CROSS)初始化該變量，該語句的作用是取得Windows標(biāo)準(zhǔn)鼠標(biāo)形狀句柄并賦給m_hCross，然后就可以通過ClassWizard添加鼠標(biāo)動(dòng)作的消息處理函數(shù)。例如，要為程序添加鼠標(biāo)左鍵單擊消息處理函數(shù)，首先在打開的ClassWizard對話框中的Class name組合框中選擇View類，然后在Object Ids列表框選中第一行，并在Message列表框中選中WM_LBUTTONDOWN一行，最后單擊Add Function按鈕即可。類似的還可以為程序添加WM_RBUTTONDOWN（鼠標(biāo)右鍵單擊）消息處理函數(shù)。因?yàn)樾枰瘘c(diǎn)地生成曲線，因此在程序中需要使用到MFC（Microsoft Fundation Class）中的CDC（設(shè)備上下文）類的成員函數(shù)SetPixel（）來實(shí)現(xiàn)在屏幕上畫點(diǎn)，CDC類主要用于在指定設(shè)備上下文上（如窗口客戶區(qū)、打印機(jī)）進(jìn)行繪圖、顯示文本等操作。
第二章 計(jì)算機(jī)圖形學(xué)中常用的算法
2.1 常用直線的算法
畫直線的算法有很多，例如數(shù)值微分法，中點(diǎn)畫線法，Bresenham化線算法等。在這里只介紹一個(gè)比較方便常用的中點(diǎn)畫線法。
為了討論方便，本小節(jié)假定直線斜率在0、1之間。其他情況可參照下述討論進(jìn)行處理。如圖所示，若直線在x方向增加一個(gè)單位，則在y方向上的增量只能在0、1之間。假設(shè)x坐標(biāo)為xp的各象素點(diǎn)中，與直線最近者已確定，為(xp,yp)，用實(shí)心小圓表示。那么，下一個(gè)與直線最近的象素只能是正右方的P1(xp+1,yp)或右上方的P2(xp+1,yp+1)兩者之一，用空心小圓表示。再以M 表示P1、P2的中點(diǎn)，即M=(xp+1,yp+0.5）。又設(shè)想Q是理想直線與垂直直線x=xp+1的交點(diǎn)。顯然，若M在Q的下方，則P2離直線近，應(yīng)取為下一個(gè)象素；否則應(yīng)取P1。這就是中點(diǎn)畫線法的基本原理。
中點(diǎn)畫線算法每步迭代涉及的象素和中點(diǎn)示意圖
下面來討論上述算法的實(shí)現(xiàn)。假設(shè)直線的起點(diǎn)和終點(diǎn)分別是(x0,y0)，(x1,y1)。則直線的方程為
F(x,y) = ax + by + c=0
其中，a = y0-y1，b = x1-x0，c = x0yi-x1y0。對于直線上的點(diǎn)，F(xiàn)(x,y)=0；對于直線上方的點(diǎn)，F(xiàn)(x,y)>0；而對于直線下方的點(diǎn)F(x,y)0時(shí)，則應(yīng)取正右方的P1。當(dāng)d=0時(shí)，二者一樣合適，可以隨便取一個(gè)。我們約定取正右方的P1。
對每一個(gè)象素計(jì)算判別式d，根據(jù)它的符號確定下一個(gè)象素。至此可以寫出完整的算法。但是注意到d是xp和yp的線形函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。在d 0的情況下，取正右方象素P1，欲判斷再下一個(gè)象素應(yīng)取哪個(gè)，應(yīng)計(jì)算
d1=F(xp+2，yp+0.5) =a(xp+2) + b(yp+0.5)+ c= d + a
故d 的增量為a。而若d<0，則右上方的象素P2，欲判斷再下一個(gè)象素，則要計(jì)算
d2=F(xp+2，yp+1.5)=a(xp+2)+b(yp+1.5)+ c = d + a + b
故在第二種情況，d 的增量為a+b。
再看d的初值。顯然，第一個(gè)象素應(yīng)取左端點(diǎn)(x0,y0)，相應(yīng)的判別式為
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ù)的算法：
本畢業(yè)設(shè)計(jì)主要研究參數(shù)曲線的直接快速生成，要直接生成參數(shù)曲線就需對參數(shù)方程{x=f(t),y=g(t),(0 t 1)}的參數(shù)t每次增加一個(gè)步長，然后計(jì)算該點(diǎn)的x和y坐標(biāo)值并繪制該點(diǎn)。要逐點(diǎn)地生成參數(shù)曲線，就要求參數(shù)t每次增加的步長要使曲線前進(jìn)的幅度不得超過一個(gè)象素長度，否則有可能跨過一個(gè)中間象素而產(chǎn)生斷點(diǎn)。
為了提高曲線生成算法的速度，本畢業(yè)設(shè)計(jì)針對如何選擇最佳的步長進(jìn)行比較討論，以使曲線前進(jìn)的幅度在不超過一個(gè)象素的前提下，選擇盡量大的步長。為了進(jìn)一步提高算法的速度，在前面討論的最佳步長的基礎(chǔ)上又采用了雙步逐點(diǎn)曲線生成算法，即將上述得到的步長增加一倍，以使算法的循環(huán)次數(shù)減少一半。由于步長增加一倍，這樣當(dāng)曲線前進(jìn)一步時(shí)，其幅度有時(shí)會(huì)大于一個(gè)象素的長度，這時(shí)我們通過插值的方法來確定跨過的那個(gè)中間象素。
通過上述討論的算法能夠比較快速的逐點(diǎn)生成曲線，為了實(shí)現(xiàn)上述算法，本畢業(yè)設(shè)計(jì)使用Visual C++6.0為工具并以三次Bezier曲線、普通參數(shù)曲線{x=f(t)=X3t3+X2t2+X1t+X0, y=g(t)=Y3t3+Y2t2+Y1t+Y0}，以及導(dǎo)師所給的一個(gè)特殊的曲線方程為例編程實(shí)現(xiàn)上述算法。
關(guān)鍵詞：參數(shù)曲線，逐點(diǎn)，雙步，Visual C++6. 0
Abstract
This graduation project main reseach the direct born of the parameter curve {x=f(t),y=g(t),0LoadStandCursor(IDC_CROSS)初始化該變量，該語句的作用是取得Windows標(biāo)準(zhǔn)鼠標(biāo)形狀句柄并賦給m_hCross，然后就可以通過ClassWizard添加鼠標(biāo)動(dòng)作的消息處理函數(shù)。例如，要為程序添加鼠標(biāo)左鍵單擊消息處理函數(shù)，首先在打開的ClassWizard對話框中的Class name組合框中選擇View類，然后在Object Ids列表框選中第一行，并在Message列表框中選中WM_LBUTTONDOWN一行，最后單擊Add Function按鈕即可。類似的還可以為程序添加WM_RBUTTONDOWN（鼠標(biāo)右鍵單擊）消息處理函數(shù)。因?yàn)樾枰瘘c(diǎn)地生成曲線，因此在程序中需要使用到MFC（Microsoft Fundation Class）中的CDC（設(shè)備上下文）類的成員函數(shù)SetPixel（）來實(shí)現(xiàn)在屏幕上畫點(diǎn)，CDC類主要用于在指定設(shè)備上下文上（如窗口客戶區(qū)、打印機(jī)）進(jìn)行繪圖、顯示文本等操作。
第二章 計(jì)算機(jī)圖形學(xué)中常用的算法
2.1 常用直線的算法
畫直線的算法有很多，例如數(shù)值微分法，中點(diǎn)畫線法，Bresenham化線算法等。在這里只介紹一個(gè)比較方便常用的中點(diǎn)畫線法。
為了討論方便，本小節(jié)假定直線斜率在0、1之間。其他情況可參照下述討論進(jìn)行處理。如圖所示，若直線在x方向增加一個(gè)單位，則在y方向上的增量只能在0、1之間。假設(shè)x坐標(biāo)為xp的各象素點(diǎn)中，與直線最近者已確定，為(xp,yp)，用實(shí)心小圓表示。那么，下一個(gè)與直線最近的象素只能是正右方的P1(xp+1,yp)或右上方的P2(xp+1,yp+1)兩者之一，用空心小圓表示。再以M 表示P1、P2的中點(diǎn)，即M=(xp+1,yp+0.5）。又設(shè)想Q是理想直線與垂直直線x=xp+1的交點(diǎn)。顯然，若M在Q的下方，則P2離直線近，應(yīng)取為下一個(gè)象素；否則應(yīng)取P1。這就是中點(diǎn)畫線法的基本原理。
中點(diǎn)畫線算法每步迭代涉及的象素和中點(diǎn)示意圖
下面來討論上述算法的實(shí)現(xiàn)。假設(shè)直線的起點(diǎn)和終點(diǎn)分別是(x0,y0)，(x1,y1)。則直線的方程為
F(x,y) = ax + by + c=0
其中，a = y0-y1，b = x1-x0，c = x0yi-x1y0。對于直線上的點(diǎn)，F(xiàn)(x,y)=0；對于直線上方的點(diǎn)，F(xiàn)(x,y)>0；而對于直線下方的點(diǎn)F(x,y)0時(shí)，則應(yīng)取正右方的P1。當(dāng)d=0時(shí)，二者一樣合適，可以隨便取一個(gè)。我們約定取正右方的P1。
對每一個(gè)象素計(jì)算判別式d，根據(jù)它的符號確定下一個(gè)象素。至此可以寫出完整的算法。但是注意到d是xp和yp的線形函數(shù)，可采用增量計(jì)算，提高運(yùn)算效率。在d 0的情況下，取正右方象素P1，欲判斷再下一個(gè)象素應(yīng)取哪個(gè)，應(yīng)計(jì)算
d1=F(xp+2，yp+0.5) =a(xp+2) + b(yp+0.5)+ c= d + a
故d 的增量為a。而若d<0，則右上方的象素P2，欲判斷再下一個(gè)象素，則要計(jì)算
d2=F(xp+2，yp+1.5)=a(xp+2)+b(yp+1.5)+ c = d + a + b
故在第二種情況，d 的增量為a+b。
再看d的初值。顯然，第一個(gè)象素應(yīng)取左端點(diǎn)(x0,y0)，相應(yīng)的判別式為
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ù)的算法：
