光柵圖形學(xué)教學(xué)演示系統(tǒng)的設(shè)計與實現(xiàn)

1、光柵圖形學(xué)教學(xué)演示系統(tǒng)的設(shè)計與實現(xiàn)學(xué) 院專 業(yè)班 級學(xué) 號姓 名指導(dǎo)教師負(fù)責(zé)教師摘 要計算機圖形學(xué)是一種使用數(shù)學(xué)算法將二維或三維圖形轉(zhuǎn)化為計算機顯示器的柵格形式的科學(xué)。由于計算機圖形學(xué)技術(shù)本身的長足進(jìn)步及其應(yīng)用的日益廣泛，計算機圖形學(xué)已成為計算機科學(xué)技術(shù)與其他應(yīng)用學(xué)科之間的一個橋梁，也已成為許多本科生專業(yè)的必修課之一。本文實現(xiàn)了一個光柵圖形學(xué)教學(xué)演示系統(tǒng)，該系統(tǒng)在windows xp平臺下實現(xiàn)，采用visual c+ 6.0作為編程工具。本文對光柵圖形學(xué)教學(xué)演示系統(tǒng)進(jìn)行了詳細(xì)分析，確定了相應(yīng)的結(jié)構(gòu)和主要功能，以及實際開發(fā)中所采取的技術(shù)。教學(xué)演示系統(tǒng)能夠形象的展示各種算法的工作過程，如直線掃描轉(zhuǎn)

2、換算法、圓弧的掃描轉(zhuǎn)換算法、多邊形的掃描轉(zhuǎn)換、區(qū)域填充、直線和多邊形的裁減算法以及曲線、曲面的生成算法等。該系統(tǒng)操作簡潔，能夠在模擬的光柵區(qū)域上按照算法的原理將圖形的光柵化過程展示出來，便于老師在教學(xué)中更形象的展示各種算法的工作過程，也便于學(xué)生在學(xué)習(xí)過程中能夠更好的理解基本圖形生成算法。同時，本文也介紹了系統(tǒng)開發(fā)設(shè)計的全過程，對算法原理做了詳細(xì)的闡述，也對系統(tǒng)的功能進(jìn)行了測試。本系統(tǒng)實現(xiàn)了大部分的基本圖形生成算法，可以應(yīng)用于計算機圖形學(xué)的教學(xué)中，以達(dá)到提高教學(xué)質(zhì)量的目的。關(guān)鍵詞：計算機圖形學(xué)；光柵；教學(xué)；基本圖形生成算法design and implementation of raster g

3、raphics teaching demonstration system abstractcomputer graphics is a science which translates two-dimensional or three-dimensional computer graphics into the display grid in mathematical algorithm. as the remarkable progress and the widespread application of computer graphics, it has become a bridge

4、 between the computer science and other application disciplines, and it is one of the required courses of many undergraduate professionals.this paper implements a raster graphics teaching demonstration system, which under the windows xp platform and visual c + + 6.0. this paper analyzes the system i

5、n detail, and determines the appropriate structure and main functions, as well as the technology adopted in actual development. the teaching demonstration system can show the visual working process of various algorithms, such as the line scan conversion algorithm, the arc scan conversion algorithms,

6、 the polygon scan conversion algorithms, the area fill algorithms, the line and polygon reduction algorithm and curve, surface generation algorithm. the system operation is simple and can display the raster process in the simulate raster area in accordance with the principles of these algorithms, wh

7、ich not only can more vivid display the working process of various algorithms in teaching, but also could facilitate students to better understand the basic pattern generation algorithm in the learning process. meanwhile, this paper describes the whole process of system development and design. it do

8、es a detail expression of the algorithm principle and tests the function of the system. the system implements most of the basic pattern generation algorithms, and it could be applied in the teaching of computer graphics to improve the quality of teaching.keywords: computer graphics; raster; teaching

9、; basic pattern generation algorithm目 錄1 緒 論11.1 計算機圖形學(xué)的重要性11.2 計算機圖形學(xué)的發(fā)展情況21.2.1 autocad概述21.2.2 計算機美術(shù)與設(shè)計31.2.3 計算機動畫藝術(shù)41.2.4 科學(xué)計算可視化41.2.5 虛擬現(xiàn)實51.3 課題的研究意義62 需求分析72.1 光柵圖形學(xué)概述72.2 任務(wù)概述72.3 任務(wù)分析72.3.1 直線掃面轉(zhuǎn)換算法82.3.2 圓弧的掃描轉(zhuǎn)換算法82.3.3 多邊形的掃描轉(zhuǎn)換與區(qū)域填充82.3.4 直線和多邊形的裁減算法92.3.5 曲線與曲面的生成算法93 系統(tǒng)詳細(xì)設(shè)計103.1 總體設(shè)計1

10、03.2 界面設(shè)計113.2.1 窗口的設(shè)計123.2.2 菜單的設(shè)計123.3 直線模塊設(shè)計133.3.1 數(shù)值微分（dda）法133.3.2 中點畫線法143.3.3 bresenham算法163.4 圓形模塊設(shè)計183.4.1 中點畫圓法183.5 區(qū)域填充模塊設(shè)計193.5.1 區(qū)域填充的遞歸算法和掃描線算法203.6 裁剪圖形模塊設(shè)計223.6.1 直線段裁剪223.6.2 多邊形裁剪253.7 曲線曲面模塊設(shè)計263.7.1 bezier曲線263.7.2 bezier曲面283.8 小結(jié)294 系統(tǒng)實現(xiàn)和測試304.1 實驗環(huán)境304.2 運行結(jié)果30參考文獻(xiàn)34致 謝351 緒

11、 論隨著網(wǎng)絡(luò)和多媒體技術(shù)的發(fā)展和應(yīng)用，計算機圖形學(xué)成為當(dāng)代幾乎所有科學(xué)和工程技術(shù)領(lǐng)域用來加強信息理解和傳遞的技術(shù)和工具。計算機圖形學(xué)的硬件和軟件應(yīng)用本身已發(fā)展成為一個巨大的產(chǎn)業(yè)，有著廣泛的發(fā)展前景，必將在人們的生活中起著越來越重要的作用。因此，計算機圖形學(xué)的應(yīng)用是重要的研究內(nèi)容。1.1 計算機圖形學(xué)的重要性計算機圖形學(xué)是利用計算機研究圖形的表示、生成、處理，顯示的一門重要的計算機學(xué)科分支。經(jīng)過30多年的發(fā)展，計算機圖形學(xué)已成為計算機科學(xué)中最為活躍的分支之一，并得到廣泛的應(yīng)用。1950年，第一臺圖形顯示器作為美國麻省理工學(xué)院（mit）旋風(fēng)一號（whirlwind）計算機的附件誕生。該顯示器用一個

12、類似示波器的陰極射線管（crt）來顯示一些簡單的圖形。在整個50年代，只有電子管計算機，用機器語言編程，主要應(yīng)用于科學(xué)計算，為這些計算機配置的圖形設(shè)備僅具有輸出功能。計算機圖形學(xué)處于準(zhǔn)備和醞釀時期，并稱之為：“被動式”圖形學(xué)。1963年，伊凡蘇澤蘭(ivan sutherland)在麻省理工學(xué)院發(fā)表了名為畫板的博士論文，它標(biāo)志著計算機圖形學(xué)的正式誕生。至今已有三十多年的歷史。此前的計算機主要是符號處理系統(tǒng)，自從有了計算機圖形學(xué)，計算機可以部分地表現(xiàn)人的右腦功能了，所以計算機圖形學(xué)的建立具有重要的意義。計算機圖形學(xué)的研究內(nèi)容非常廣泛，如圖形硬件、圖形標(biāo)準(zhǔn)、圖形交互技術(shù)、光柵圖形生成算法、曲線曲面

13、造型、實體造型、真實感圖形計算與顯示算法、非真實感繪制，以及科學(xué)計算可視化、計算機動畫、自然景物仿真、虛擬現(xiàn)實等。隨著網(wǎng)絡(luò)和多媒體技術(shù)的發(fā)展和應(yīng)用，體現(xiàn)在應(yīng)用軟件中的是一些更具有“現(xiàn)代感”的應(yīng)用，例如，支持各種常用圖形、raw原始圖片、flash動畫的快速瀏覽、編輯、保存、導(dǎo)入、導(dǎo)出，甚至還可以提供一些趣味涂鴉、字符素描之類的應(yīng)用，以體現(xiàn)人的個性。圖形與圖像處理是計算機最早應(yīng)用的領(lǐng)域之一，從簡單的圖形顯示到復(fù)雜的圖像分析、模式識別，使得圖形與圖像處理技術(shù)不斷走向成熟，也涌現(xiàn)出了大量的軟件。例如，acdsee、photoshop、coreldraw等，這些軟件提供了一般顯示、特殊顯示、特技處理等

14、大量復(fù)雜的功能。圖形處理技術(shù)得益于圖形學(xué)的發(fā)展，而從目的上可以將圖像處理技術(shù)分為兩類，分別是圖像識別技術(shù)和圖像處理技術(shù)。針對圖像處理技術(shù)，可以是旋轉(zhuǎn)、亮度、對比度、飽和度、rgb調(diào)節(jié)、調(diào)節(jié)圖像尺寸等屬性方面的處理技術(shù)和添加文字、圖像增強、弱化、水印、特效、鏤空等處理方法。甚至為了達(dá)到更精微的處理效果，這些軟件還使用了圖層。隨著計算機系統(tǒng)的硬件、軟件的迅速發(fā)展，計算機已經(jīng)具有強大的圖形處理功能，目前計算機圖形學(xué)已無所不在，從cad設(shè)計到廣告設(shè)計、從影視娛樂到計算機動畫，都使人們感受到計算機圖形技術(shù)獨特的魅力。同時，由于計算機圖形學(xué)技術(shù)本身的長足進(jìn)步及其應(yīng)用的日益廣泛，計算機圖形學(xué)已成為計算機科學(xué)

15、技術(shù)與其他應(yīng)用學(xué)科之間的一個橋梁，也成為許多本科生專業(yè)的必修課程之一。1.2 計算機圖形學(xué)的發(fā)展情況計算機促進(jìn)高科技技術(shù)不斷發(fā)展，計算機圖形學(xué)成為當(dāng)代幾乎所有科學(xué)和工程技術(shù)領(lǐng)域用來加強信息理解和傳遞的技術(shù)和工具。近年來，計算機圖形學(xué)在如下幾方面有了長足的進(jìn)展。1.2.1 autocad概述cad 的發(fā)展也顯現(xiàn)出智能化的趨勢，就目前流行的大多數(shù)cad軟件來看，主要功能是支持產(chǎn)品的后續(xù)階段一一工程圖的繪制和輸出，產(chǎn)品設(shè)計功能相對薄弱，利用autocad 最常用的功能還是交互式繪圖，如果要想進(jìn)行產(chǎn)品設(shè)計，最基本的是要其中的autolisp語言編寫程序，有時還要用其他高級語言協(xié)助編寫，很不方便。而新一

16、代的智能cad系統(tǒng)可以實現(xiàn)從概念設(shè)計到結(jié)構(gòu)設(shè)計的全過程。例如，德國西門子公司開發(fā)的sigraph design軟件可以實現(xiàn)如下功能：從一開始就可以用計算機設(shè)計草圖，不必耗時費力的輸入精確的坐標(biāo)點，能隨心所欲的修改，一旦結(jié)構(gòu)確定，給出正確的尺寸即得到滿意的圖紙；這個軟件中具有關(guān)系數(shù)據(jù)結(jié)構(gòu)，當(dāng)你改變圖紙的局部，相關(guān)部分自動變化，在一個視圖上的修改，其他視圖自動修改，甚至改變一個零件圖，相關(guān)的其它零件圖以及裝配圖的相關(guān)部分自動修改：在各個專業(yè)領(lǐng)域中，有一些常用件和標(biāo)準(zhǔn)件，因此，希望有一個參數(shù)化圖庫。而sigraph不用編程只需畫一遍圖就能建成自己的圖庫；sigraph還可以實現(xiàn)產(chǎn)品設(shè)計的動態(tài)模擬用于

17、觀察設(shè)計的裝置在實際運行中是否合理等等。智能cad的另一個領(lǐng)域是工程圖紙的自動輸入與智能識別，隨著cad技術(shù)的迅速推廣應(yīng)用，各個工廠、設(shè)計院都需將成千上萬張長期積累下來的設(shè)計圖紙快速而準(zhǔn)確輸入計算機，作為新產(chǎn)品開發(fā)的技術(shù)資料。多年來，cad中普遍采用的圖形輸入方法是圖形數(shù)字化儀交互輸入和鼠標(biāo)加鍵盤的交互輸入方法。很難適應(yīng)工程界大量圖紙輸入的迫切需要。因此，基于光電掃描儀的圖紙自動輸入方法已成為國內(nèi)外cad工作者的努力探索的新課題。但由于工程圖的智能識別涉及到計算機的硬件、計算機圖形學(xué)、模式識別及人工智能等高新技術(shù)內(nèi)容，使得研究工作的難點較大。工程圖的自動輸入與智能識別是兩個密不可分的過程，用掃

18、描儀將手繪圖紙輸入到計算機后，形成的是點陣圖象。cad中只能對矢量圖形進(jìn)行編輯，這就要求將點陣圖象轉(zhuǎn)化成矢量圖形。而這些工作都讓計算機自動完成，這就帶來了許多的問題。如圖象的智能識別；字符的提取與識別；圖形拓?fù)浣Y(jié)構(gòu)的建立與圖形的理解；實用化的后處理方法等等。國家自然科學(xué)基金會和863計劃基金都在支持這方面的研究，國內(nèi)外已有一些這方面的軟件付諸實用，如美國的rvmaster，德國的vpmax，以及清華大學(xué)，東北大學(xué)的產(chǎn)品等。但效果都不很理想，還未能達(dá)到人們企盼的效果。1.2.2 計算機美術(shù)與設(shè)計1952年美國的ben laposke用模擬計算機做的波型圖電子抽象畫預(yù)示著電腦美術(shù)的開始(比計算機圖

19、形學(xué)的正式確立還要早)。計算機美術(shù)的發(fā)展可分為三個階段：(1)早期探索階段(19521968年)主創(chuàng)人員大部分為科學(xué)家和工程師，作品以平面幾何圖形為主。1963年美國計算機與自動化雜志開始舉辦年度“計算機美術(shù)比賽”。代表作品：1960年wiuiam ferrter為波音公司制作的人體工程學(xué)實驗動態(tài)模擬，模擬飛行員在飛機中各種情況；1963年kenneth know iton的打印機作品裸體。1967年日本gtg小組的回到方塊。(2)中期應(yīng)用階段(1968年1983年)以1968年倫敦第一次世界計算機美術(shù)大展一“控制論珍寶”為標(biāo)志，進(jìn)入世界性研究與應(yīng)用階段；計算機與計算機圖形技術(shù)逐步成熟，一些大

20、學(xué)開始設(shè)置相關(guān)課題，出現(xiàn)了一些cad應(yīng)用系統(tǒng)和成果，三維造型系統(tǒng)產(chǎn)生并逐漸完善。代表作品：1983年美國ibm研究所richerd voss設(shè)計出分形山。(3)應(yīng)用與普及階段(1984年現(xiàn)在)以微機和工作站為平臺的個人計算機圖形系統(tǒng)逐漸走向成熟，大批商業(yè)性美術(shù)軟件面市；以蘋果公司的mac機和圖形化系統(tǒng)軟件為代表的桌面創(chuàng)意系統(tǒng)被廣泛接受，cad成為美術(shù)設(shè)計領(lǐng)域的重要組成部分。代表作品：1990年jefrey shaw的交互圖形作品“易讀的城市（the legible city）”。計算機設(shè)計學(xué)包括三個方面：環(huán)境設(shè)計、視覺傳達(dá)設(shè)計、產(chǎn)品設(shè)計。cad對藝術(shù)的介入，分三個應(yīng)用層次：(1)計算機圖形作為

21、系統(tǒng)設(shè)計手段的一種強化和替代；效果是這個層次的核心(高精度、高速度、高存儲)。(2)計算機圖形作為新的表現(xiàn)形式和新的形象資源。(3)計算機圖形作為一種設(shè)計方法和觀念。1.2.3 計算機動畫藝術(shù)計算機動畫技術(shù)的發(fā)展是和許多其它學(xué)科的發(fā)展密切相關(guān)的。計算機圖形學(xué)、計算機繪畫、計算機音樂、計算機輔助設(shè)計、電影技術(shù)、電視技術(shù)、計算機軟件和硬件技術(shù)等眾多學(xué)科的最新成果都對計算機動畫技術(shù)的研究和發(fā)展起著十分重要的推動作用50年代到60年代之間，大部分的計算機繪畫藝術(shù)作品都是在打印機和繪圖儀上產(chǎn)生的。一直到60年代后期，才出現(xiàn)利用計算機顯示點陣的特性，通過精心地設(shè)計圖案來進(jìn)行計算機藝術(shù)創(chuàng)造的活動。70年代開

22、始計算機藝術(shù)走向繁榮和成熟1973年，在東京索尼公司舉辦了“屆國際計算機藝術(shù)展覽會”80年代至今，計算機藝術(shù)的發(fā)展速度遠(yuǎn)遠(yuǎn)超出了人們的想象，在代表計算機圖形研究最高水平的歷屆siggraph年會上，精彩的計算機藝術(shù)作品層出不窮。另外，在此期間的奧斯卡獎的獲獎名單中，采用計算機特技制作電影頻頻上榜，大有舍我其誰的感覺。在中國，首屆計算機藝術(shù)研討會和作品展示活動于1995年在北京舉行，它總結(jié)了近年來計算機藝術(shù)在中國的發(fā)展，對未來的工作起到了重要的推動作用。計算機動畫的一個重要應(yīng)用就是制作電影特技，可以說電影特技的發(fā)展和計算機動畫的發(fā)展是相互促進(jìn)的。我國的計算機動畫技術(shù)起步較晚。1990年的第11屆

23、亞洲運動會上，首次采用了計算機三維動畫技術(shù)來制作有關(guān)的電視節(jié)目片頭。從那時起，計算機動畫技術(shù)在國內(nèi)影視制作方面得到了訊速的發(fā)展，繼而以3d studio為代表的三維動畫微機軟什和以photostyler、photoshop等為代表的微機二維平面設(shè)計軟件的普及，對我國計算機動畫技術(shù)的應(yīng)用起到了推波助讕的作用。計算機動畫的應(yīng)用領(lǐng)域十分寬廣，除了用來制作影視作品外，在科學(xué)研究、視覺模擬、電子游戲、工業(yè)設(shè)計、教學(xué)訓(xùn)練、寫真仿真、過程控制、平面繪畫、建筑設(shè)計等許多方面都有重要應(yīng)用，如軍事戰(zhàn)術(shù)模擬。1.2.4 科學(xué)計算可視化科學(xué)計算的可視化是發(fā)達(dá)國家八十年代后期提出并發(fā)展起來的一門新興技術(shù)，它將科學(xué)計算過

24、程中及計算結(jié)果的數(shù)據(jù)轉(zhuǎn)換為幾何圖形及圖象信息在屏幕上顯示出來并進(jìn)行交互處理，成為發(fā)現(xiàn)和理解科學(xué)計算過程中各種現(xiàn)象的有力工具?？茖W(xué)計算可視化將圖形生成技術(shù)圖象理解技術(shù)結(jié)合在一起，它即可理解送入計算機的圖象數(shù)據(jù)，也可以從復(fù)雜的多維數(shù)據(jù)中產(chǎn)生圖形。它涉及到下列相互獨立的幾個領(lǐng)域：計算機圖形學(xué)、圖象處理、計算機視覺、計算機輔助設(shè)計及交互技術(shù)等?？茖W(xué)計算可視按其實現(xiàn)的功能來分，可以分為三個檔次：(1)結(jié)果數(shù)據(jù)的后處理；(2)結(jié)果數(shù)據(jù)的實時跟蹤處理及顯示；(3)結(jié)果數(shù)據(jù)的實時顯示及交互處理。國外科學(xué)計算可視化的現(xiàn)狀，(1)分布式虛擬風(fēng)洞，這是美國國家宇航局(ames)研究中心的研究項目，包括連接到一臺超能

25、計算機上的兩個虛擬屏幕。(2)phthfinder，這是美國國家超級計算機應(yīng)用中心(ncsa)的研究項目，是在交互分布環(huán)境下研究大氣流體的軟件。(3)狗心臟ct數(shù)據(jù)的動態(tài)顯示，這也是ncsa的研究項目，它利用遠(yuǎn)程的并行計算資源，用體繪制技術(shù)實現(xiàn)ct掃描三維數(shù)據(jù)場動態(tài)顯示。(4)燃燒過程動態(tài)模型的可視化，這是美國西北大學(xué)的研究項目，可以顯示發(fā)生在非燒熱的氣體燃燒中復(fù)雜的空問瞬態(tài)圖象。(5)胚胎的可視化，依利諾大學(xué)芝加哥分校研制了一個在工作站和超級計算機上實現(xiàn)的可視億應(yīng)用軟件。科學(xué)計算可視化技術(shù)在美國的著名國家實驗室及大學(xué)中已經(jīng)從研究走向應(yīng)用，應(yīng)用范圍涉及天體物理、生物學(xué)、氣象學(xué)、空氣動力學(xué)、數(shù)學(xué)

26、、醫(yī)學(xué)圖象等領(lǐng)域?？茖W(xué)計算可視化的技術(shù)水平正在從后處理向?qū)崟r跟蹤和交互控制發(fā)展。美國在實現(xiàn)科學(xué)計算可視化時，已經(jīng)將超級計算機、光纖高速網(wǎng)、高性能工作站及虛擬環(huán)境四者結(jié)合起來，顯示了這一領(lǐng)域技術(shù)發(fā)展的重要方向。就三維數(shù)據(jù)場的顯示算法而言，當(dāng)數(shù)據(jù)場分布密集而規(guī)則時(如ct掃描數(shù)據(jù))多采用體繪制技術(shù)，這種算法效果好，但計算費時。對于數(shù)據(jù)場分布稀疏，或分布不規(guī)則的應(yīng)用領(lǐng)域，如天體物理、氣象學(xué)多采用構(gòu)造中間幾何圖象的方法，這種方法生成圖象速度快，較易作到實時交互處理。1.2.5 虛擬現(xiàn)實“虛擬現(xiàn)實”(virbual remity)一詞是由美國噴氣推動實驗室(vpl)的創(chuàng)始人拉尼爾(jaron lanie

27、r)首先提出的，在克魯格(myren kruege)70年代中早期實驗里，被稱為“人工現(xiàn)實”(artificial reality)；而在吉布森(william gibson)l984年出版的科幻小說neuremanccr里，又被稱為“可控空間”(cyberspaee)。虛擬現(xiàn)實，也育人稱之為虛擬環(huán)境(virtual environment)是美國國家航空和航天局及軍事部門為模擬而開發(fā)的一門高新技術(shù)，它利用計算機圖形產(chǎn)生器，位置跟蹤器，多功能傳感器和控制器等有效地模擬實際場景和情形，從而能夠使觀察者產(chǎn)生一種真實的身臨其境的感覺虛擬環(huán)境由硬件和軟件組成。用戶界面是計算機系統(tǒng)中人與計算機之間相互通

28、訊的重要組成部分。八十年代以wimp為基礎(chǔ)的圖形用戶界面gud極大地改善了計算機的可用性、可學(xué)性和有效性，迅速代替了命令行為代表的字符界面，成為當(dāng)今計算機用戶界面的主流。窗口是虛擬存在的一個屏幕，在屏幕上看到的圖形是視口。windows在繪制圖形時，并不是把圖形直接繪制到屏幕上，而是繪制到特定的映射模式下的邏輯坐標(biāo)系虛擬的窗口中，然后將這個圖形映射到一個視圖中，即視口中。而當(dāng)前的設(shè)備（如屏幕，打印機）顯示出來的就是該視圖的一部分。以用戶為中心的系統(tǒng)設(shè)計思想，增進(jìn)人機交互的自然性，提高人機交互的效率和帶寬是用戶界面的研究方向。于是提出了多通道用戶界面的思想。可以這樣說人體的表面就是人機界面。虛擬

29、現(xiàn)實顯示是關(guān)鍵所在，這不僅要求軟件來實現(xiàn)，更主要的是硬件上的實現(xiàn)。計算機圖形學(xué)中各個領(lǐng)域的發(fā)展各有各自的特點，但總起來說是以虛擬現(xiàn)實為導(dǎo)向和目的的。虛擬現(xiàn)實的發(fā)展要求必將帶動計算機圖形學(xué)各學(xué)科的發(fā)展。同樣虛擬現(xiàn)實的發(fā)展也將依賴于其他學(xué)科的發(fā)展，計算機圖形前景誘人。形勢逼人，我國還比較落后，但通過努力還是可以縮短差距的。 1.3 課題的研究意義本題目的目的是設(shè)計并實現(xiàn)一個光柵圖形學(xué)教學(xué)演示系統(tǒng)。課題實現(xiàn)基本圖形元素如直線、圓、曲線和曲面等的繪制，對圖形元素的基本操作如填充、擦除和裁剪等，來演示數(shù)值微分（dda）算法、中點畫線算法和bresenham算法，中點畫圓法，區(qū)域填充的遞歸算法，區(qū)域填充的

30、掃描線算法，cohen-sutherland法，梁友棟-barskey剪裁算法，sutherland-hodgman算法，de casteljau算法等。目前已有種類繁多的圖形圖像處理專用軟件工具，如autocad、和photoshop等，利用這些圖形圖像處理軟件可以實現(xiàn)同樣的功能。即便如此，研究這些圖形圖像處理技術(shù)仍具有一定使用價值。利用一個設(shè)計良好的簡單的小圖形處理程序可以用于教學(xué)演示的目的，教學(xué)演示系統(tǒng)能夠更形象的展示各種算法的工作原理，操作簡潔，有利于分析和理解算法，而且便于在學(xué)習(xí)過程中能夠更好的掌握基本圖形生成的理論知識點。其次，在很多應(yīng)用中需要提供自己的圖形圖像處理功能。例如，在一

31、個正在連接網(wǎng)絡(luò)的任務(wù)中可能就希望顯示一幅示意性的動畫，此時，不能依賴一個圖形軟件來實現(xiàn)。因此，通過對獨立功能的封裝，可以為今后需要的圖形圖像的應(yīng)用奠定基礎(chǔ)。此外，借助visual c+語言能夠充分挖掘硬件的潛能，得到性能優(yōu)良的程序代碼，同時通過編寫算法實現(xiàn)程序加深對圖形學(xué)基本內(nèi)容的理解，提高用理論指導(dǎo)實踐的能力。2 光柵圖形學(xué)理論2.1 光柵圖形學(xué)概述光柵圖形學(xué)顯示器可以看作一個像素的矩陣。在光柵顯示器上顯示的任何一種圖形，實際上都是一些具有一種或多種顏色的像素集合。確定最佳逼近圖形的像素集合，并用指定屬性寫像素的過程稱為圖形的掃描轉(zhuǎn)換或光柵化。對于一維圖形，在不考慮線寬時，用一個像素寬的直、

32、曲線來顯示圖形；二維圖形的光柵化必須確定區(qū)域?qū)?yīng)的像素集，并用指定的屬性或圖案顯示，即區(qū)域填充。任何圖形進(jìn)行光柵化時，必須顯示在熒屏的一個窗口里，超出窗口的圖形不予顯示。確定一個圖形的哪些部分在窗口內(nèi)必須顯示；哪些在窗口外，不該顯示的過程叫裁剪。裁剪通常在掃描轉(zhuǎn)換之前進(jìn)行，從而可以不必對那些不可見的圖形進(jìn)行掃描轉(zhuǎn)換。對圖形進(jìn)行光柵化時，由于顯示器的空間分辨率有限，對于非水平、垂直、45度的直線，因像素逼近誤差，使所畫圖形產(chǎn)生畸變（臺階、鋸齒）的現(xiàn)象稱之為走樣（aliasing）。用于減少或消除走樣的技術(shù)稱為反走樣（antialiasing)。提高顯示器的空間分辨率可以減輕走樣程度，但這是以提高

33、設(shè)備成本為代價的。實際上，當(dāng)顯示器的像素可以用亮度顯示時，通過調(diào)整圖形上各像素的亮度也可以減輕走樣程度。當(dāng)不透光的物體阻擋了來自某些物體部分的光線，使其無法到達(dá)觀察者時，這些物體部分就是隱藏部分。隱藏部分是不可見的，如果不刪除隱藏的線或面，就可能發(fā)生對圖的錯誤理解。為了使計算機圖形能夠真實地反映這一現(xiàn)象，必須把隱藏的部分從圖中刪除，習(xí)慣上稱做消除隱藏線和隱藏面，或簡稱為消隱。2.2 任務(wù)概述本題目實現(xiàn)一個光柵圖形學(xué)教學(xué)演示系統(tǒng)。教學(xué)演示系統(tǒng)能夠更形象的展示各種算法的工作原理，該系統(tǒng)操作簡潔能夠在模擬的光柵區(qū)域上按照算法的原理將圖形的光柵化過程展示出來，有利于分析和理解算法，能夠更形象的展示各種

34、算法的工作原理，便于在學(xué)習(xí)過程中能夠更好的掌握基本圖形生成的算法。2.3 任務(wù)分析教學(xué)演示系統(tǒng)能夠更形象的展示各種算法的工作原理，便于學(xué)生在學(xué)習(xí)過程中能夠更好的掌握基本圖形生成算法。這就要求體現(xiàn)以下內(nèi)容：（1）掌握vc+語言和opengl編程技術(shù)。（2）設(shè)計簡單的圖形用戶界面，以便于展現(xiàn)算法的實現(xiàn)。（3）掌握光柵圖形學(xué)中相關(guān)算法的原理，這是本課題主要研究的內(nèi)容。根據(jù)設(shè)計目標(biāo)，分析出具體要實現(xiàn)繪制直線，繪制圓形，繪制矩形，裁剪圖形，區(qū)域填充，畫曲線，畫曲面的功能，來實現(xiàn)直線掃描轉(zhuǎn)換算法、圓弧的掃描轉(zhuǎn)換算法、多邊形的掃描轉(zhuǎn)換與區(qū)域填充以及直線和多邊形的裁減算法與生成曲線的算法等。2.3.1 直線掃

35、描轉(zhuǎn)換算法在數(shù)學(xué)上，理想的直線是沒有寬度的，它是由無數(shù)個點構(gòu)成的集合。對直線進(jìn)行光柵化時，只能在顯示器所給定的有限個像素組成的矩陣中，確定最佳逼近于該直線的一組像素，并且按掃描線順序。對這些像素進(jìn)行操作，就是通常所說的用光柵顯示器繪制直線或直線的掃描轉(zhuǎn)換。由于一個圖中可能包含成千上萬條直線，所以要求繪制算法盡可能快。直線掃面轉(zhuǎn)換算法有三個常用算法：數(shù)值微分（dda）法、中點畫線法和bresenham算法。2.3.2 圓弧的掃描轉(zhuǎn)換算法圓的特征，圓被定義為到給定中心位置的距離為定長的點集。圓心位于遠(yuǎn)點的圓有4條對稱軸x=0，y=0，x=y和x=y。若已知圓弧上一點(x,y)，可以得到其關(guān)于4條對

36、稱軸的其他7個點，這種性質(zhì)稱為八對稱性。因此，只要掃描轉(zhuǎn)換1/8圓弧，就可以用八對稱性求出整個圓弧的像素集。圓弧的掃描轉(zhuǎn)換算法的常用算法是中點畫圓法。2.3.3 多邊形的掃描轉(zhuǎn)換與區(qū)域填充在計算機圖形學(xué)中，多邊形有兩種重要的表示方法：頂點表示和點陣表示。頂點表示是用多邊形的定點序列來表示多邊形。這種表示直觀、幾何意義強、占內(nèi)存少，易于進(jìn)行幾何變換。但由于它沒有明確指出哪些像素在多邊形內(nèi)，故不能直接用于面著色。點陣表示是用位于多邊形內(nèi)的像素集合來刻畫多邊形，這種表示丟失了許多幾何信息，但便于幀緩沖器表示圖形，是面著色所需要的圖形表示形式。光柵圖形學(xué)的一個基本問題是把多邊形的頂點表示轉(zhuǎn)換為點陣表示

37、，這種轉(zhuǎn)換稱為多邊形的掃描轉(zhuǎn)換。多邊形的掃描轉(zhuǎn)換算法的常用算法是掃描線算法和邊界標(biāo)志算法。區(qū)域填充，這里討論的區(qū)域是指已經(jīng)表示成點陣形式的填充圖形，它是像素的集合。區(qū)域可采用內(nèi)點表示和邊界表示兩種表示形式。在內(nèi)點表示中，區(qū)域內(nèi)的所有像素著同一顏色；在邊界表示中，區(qū)域的邊界點著同一顏色。區(qū)域填充是指先將區(qū)域的一點賦予指定顏色，然后將該顏色擴(kuò)展到整個區(qū)域的過程。區(qū)域填充算法要求區(qū)域是連通的，因為只有在連通區(qū)域中，才可能將種子點的顏色擴(kuò)展到區(qū)域內(nèi)的其他點。區(qū)域可分為四連通區(qū)域和八連通區(qū)域。多邊形的區(qū)域填充的算法有區(qū)域填充的遞歸算法和區(qū)域填充的掃描線算法。2.3.4 直線和多邊形的裁減算法直線段剪裁算

38、法比較簡單，但非常重要，是復(fù)雜圖元剪裁的基礎(chǔ)。因為復(fù)雜的曲線可以通過折線段來近似，從而剪裁問題也可以化為直線段的剪裁問題。常用的線段剪裁方法有三種，即cohen-sutherland法和梁友棟-barskey剪裁算法。對于一個多邊形，可以把它分解為邊界的線段逐段進(jìn)行剪裁，但這樣做會使原來封閉的多邊形變成不封閉或者一些離散的線段。當(dāng)多邊形作為實區(qū)域考慮時，封閉的多邊形裁剪后仍應(yīng)當(dāng)是封閉的多邊形，以便進(jìn)行填充。為此，可以使用sutherland-hodgman算法，該算法的基本思想是一次用窗口的一條邊裁剪多邊形。2.3.5 曲線與曲面的生成算法幾何造型技術(shù)是一項研究在計算機中如何表示物體模型形狀的

39、技術(shù)。在幾何造型系統(tǒng)中，有三種描述物體的三維模型，即線框模型、曲面模型和實體模型。曲面模型在線框模型的基礎(chǔ)上，正加了物體中面的信息，但并沒給出物體在面的哪一側(cè)，則無法計算和分析物體的整體性質(zhì)。雖然三維曲面模型表示三維物體的信息并不完整，但能夠表達(dá)復(fù)雜的雕刻曲面，在幾何造型中具有重要的地位。曲線、曲面可以用顯式、隱式和參數(shù)表示，由于參數(shù)表示的曲線、曲面具有幾何不變性等優(yōu)點，計算機圖形學(xué)中常用參數(shù)形式描述曲線、曲面。1962年，法國雷諾汽車公司的p.e.bezier構(gòu)筑了一種已逼近為基礎(chǔ)的參數(shù)曲線和曲面的設(shè)計方法，并用這種方法完成了一個稱為unisurf的曲線和曲面設(shè)計系統(tǒng)。1972年，該系統(tǒng)被投

40、入應(yīng)用。bezier曲線常用的生成算法為de casteljau算法。3 光柵圖形學(xué)教學(xué)演示系統(tǒng)的詳細(xì)設(shè)計3.1 總體設(shè)計根據(jù)上一章的分析以及，本文將該光柵圖形學(xué)教學(xué)演示系統(tǒng)劃分為五個功能塊模塊。分別是：直線模塊，圓形模塊，區(qū)域填充模塊，裁剪圖形模塊和曲線曲面模塊。圖3.1 系統(tǒng)總體模塊圖系統(tǒng)總體模塊圖如圖3.1所示。(1) 該系統(tǒng)的直線模塊完成了繪制直線的功能，實現(xiàn)直線掃面轉(zhuǎn)換算法包括數(shù)值微分（dda）法、中點畫線法和bresenham算法；(2) 該系統(tǒng)的圓形模塊完成了繪制圓形的功能，實現(xiàn)圓弧的掃描轉(zhuǎn)換算法的中點畫圓法；(3) 該系統(tǒng)的區(qū)域填充模塊完成了圖形填充的功能，實現(xiàn)區(qū)域填充的遞歸算

41、法和區(qū)域填充的掃描線算法；(4) 該系統(tǒng)的裁剪圖形模塊實現(xiàn)了直線段剪裁的演示和多邊形裁剪的演示，完成了直線段剪裁的cohen-sutherland法和梁友棟-barskey剪裁算法和多邊形裁剪的sutherland-hodgman算法；(5) 該系統(tǒng)的曲線曲面模塊完成了繪制曲線和曲面的功能，實現(xiàn)了曲線的de casteljau算法。該系統(tǒng)能夠在模擬的光柵區(qū)域上按照算法的原理將圖形的光柵化過程展示出來，有利于分析和理解算法，能夠更形象的展示各種算法的工作原理，便于在學(xué)習(xí)過程中能夠更好的掌握基本圖形生成的算法。其次根據(jù)該光柵圖形學(xué)教學(xué)演示系統(tǒng)的總體模塊以及功能結(jié)構(gòu)，可以設(shè)計出系統(tǒng)的總流程，具體系統(tǒng)

42、總流程圖如圖3.2所示。該系統(tǒng)以菜單的方式工作，一旦選中某算法，按照算法的原理將圖形的光柵化過程展示出來。圖3.2 系統(tǒng)總流程圖3.2 界面設(shè)計好的開端是從設(shè)計用戶界面開始。首先，你要決定什么樣的用戶能使用該程序并根據(jù)需要來設(shè)置相應(yīng)的用戶界面對象。windows用戶界面有一些標(biāo)準(zhǔn)的控制，如按鈕、菜單、滾動條和列表等，這對那些 windows用戶已經(jīng)是很熟悉了。要記住的是，作為程序員必須選擇一組控制并決定如何把它們安排到屏幕上。傳統(tǒng)上，你需要在紙上做一下用戶界面的草圖，直到對各元素感到滿意為止。這對于一些比較小的項目，以及一些大項目的早期原型階段是可以的。3.2.1 窗口的設(shè)計windows支持

43、應(yīng)用程序窗口，一個典型的應(yīng)用程序應(yīng)該活動在稱為“框架窗口”中。一個框架窗口是一個全功能的主窗口，用戶可以改變尺寸、最小化、最大化等。最簡單的windows應(yīng)用程序是使用單文檔界面，只有一個框架窗口。在應(yīng)用程序中要完成某個功能，都是以函數(shù)調(diào)用的形式實現(xiàn)的，同樣，應(yīng)用程序也是以函數(shù)調(diào)用的方式來通知操作系統(tǒng)執(zhí)行相應(yīng)的功能的。操作系統(tǒng)所能夠完成的每一個特殊功能通常都有一個函數(shù)與其對應(yīng)，也就是說，操作系統(tǒng)把它所能夠完成的功能以函數(shù)的形式提供給應(yīng)用程序使用，應(yīng)用程序?qū)@些函數(shù)的調(diào)用就叫做系統(tǒng)調(diào)用，這些函數(shù)的集合就是windows操作系統(tǒng)提供給應(yīng)用程序編程的接口(application programmin

44、g interface)，簡稱windows api。如createwindow就是一個api函數(shù)，應(yīng)用程序中調(diào)用這個函數(shù)，操作系統(tǒng)就會按照該函數(shù)提供的參數(shù)信息產(chǎn)生一個相應(yīng)的窗口。visual c+不僅僅是一個編譯器，還是一個全面的應(yīng)用程序開發(fā)環(huán)境，使用它可以利用具有面向?qū)ο筇匦缘腸+來開發(fā)出專業(yè)級的windows應(yīng)用程序。為了能充分利用這些特性，你必須理解c+程序設(shè)計語言。掌握了c+，你就必須掌握 microsoft基本類庫(mfc)的層次結(jié)構(gòu)，該層次結(jié)構(gòu)包容了windows api中的用戶界面部分，并使你能夠很容易地以面向?qū)ο蟮姆绞浇indows應(yīng)用程序。這種層次結(jié)構(gòu)適用于所有版本的w

45、indows并彼此兼容。所以，創(chuàng)建mfc可執(zhí)行程序mfc appwizard exe來完成界面的設(shè)計。3.2.2 菜單的設(shè)計用戶與應(yīng)用程序的交互通常是從菜單欄中選擇命令，因此，菜單的資源在vc+編程中是很重要的。在windows中，菜單可以分為3大類：設(shè)計時用菜單資源編輯器定義的靜態(tài)菜單，在運行時添加的動態(tài)菜單，還有前兩種菜單的組合，快捷菜單是靜態(tài)設(shè)計動態(tài)顯示。根據(jù)該光柵圖形學(xué)教學(xué)演示系統(tǒng)的總體模塊以及功能結(jié)構(gòu)，設(shè)計一個靜態(tài)菜單。創(chuàng)建菜單最簡單的方法是先在mfc中借助應(yīng)用程序向?qū)ё詣由蓱?yīng)用程序的基本框架，然后利用菜單資源編輯器進(jìn)行加工設(shè)計。每個菜單項有兩個基本要素，菜單項名和一個整數(shù)類型的命

46、令id號。通過給菜單的選項編寫代碼來完成應(yīng)用程序的編程，使菜單id與應(yīng)用程序主窗口連接起來，使應(yīng)用程序的主窗口中顯示菜單，來完成菜單操作設(shè)計的實現(xiàn)。3.3 直線模塊設(shè)計該模塊的主要功能是負(fù)責(zé)繪制直線段，實現(xiàn)了直線掃面轉(zhuǎn)換算法包括數(shù)值微分（dda）法、中點畫線法和bresenham算法，直線模塊的流程圖如圖3.3所示。理想直線是由無數(shù)個點構(gòu)成，繪制直線段即需要確定最佳逼近于該直線的一組像素，再對這些像素進(jìn)行寫操作。首先要確定線段端點的坐標(biāo)（即起始點與結(jié)束點的坐標(biāo)），從起始點開始，按照算法運算出下一個像素點的坐標(biāo)，再從此像素點開始，繼續(xù)算出下一個像素點的坐標(biāo)，直到像素點為結(jié)束點為止，逐一繪制像素點

47、，即完成繪制線寬為一個像素的直線。其中根據(jù)不同直線掃描轉(zhuǎn)換算法，算出下一個像素點坐標(biāo)的方法不相同，每個算法都有各自的優(yōu)點。圖3.3 直線模塊的流程圖3.3.1 數(shù)值微分（dda）法已知過端點p0(,)，p1(,)的直線段l(p0,p1)；直線斜率為k=。畫線過程為：從x的左端點開始，向x右端點步進(jìn)，步長為=1（像素），按y=kx+b計算相應(yīng)的y坐標(biāo)，并取像素點(x,round(y)作為當(dāng)前點的坐標(biāo)。但這樣做，計算每一個點需要做一個乘法、一個加法。設(shè)步長為x，有x=x+x， （3.1）用式（3.1）計算，當(dāng)x=1時，則有。即x每遞增1，y遞增k（即直線斜率）。這樣，計算就由一個乘法和一個加法減少

48、為一個加法。dda畫線算法流程圖如圖3.4所示。應(yīng)當(dāng)注意的是，上述算法僅適用于情形。在這種情況下，x每增加1，y最多增加k.當(dāng)時，必須把x，y的地位互換，y每增加1，x相應(yīng)增加。同理，中點畫線法，bresenham算法，也是如此。在這個算法中，y與k必須用浮點數(shù)表示，而且每一步都要對y進(jìn)行四舍五入后取整，這使得該算法不利于硬件實現(xiàn)。圖3.4 dda畫線算法流程圖3.3.2 中點畫線法通過觀察可以發(fā)現(xiàn)，畫直線段的過程中，當(dāng)前像素點為(,)下一個像素點有兩種可選擇點p1(+1,)或p2(+1,+1)。若m=(+1,+0.5)為p1與p2的中點，q為理想直線與垂線的交點。當(dāng)m在q的下方時，p2應(yīng)為下

49、一個像素點；當(dāng)m在q的上方時，應(yīng)取p1為下一點。這就是中點畫線法的基本原理（見圖3.5）。圖3.5 中點畫線法每步迭代涉及的像素和中點示意圖中點畫線算法流程圖如圖3.6所示。圖3.6 中點畫線算法流程圖對直線段l，采用方程表示，其中，。于是有下述點與l的關(guān)系：因此，預(yù)判斷m在q點的上方還是下方，只要把m帶入f(x,y)，并判斷它的符號即可。構(gòu)造下述判別式： （3.2）當(dāng)d0時，m在l（q點）上方，取p1為下一個像素；當(dāng)d=0時，選p1或p2均可，約定取p1為下一個像素。用式（3.2）計算符號時，需做4個加法和2個乘法。事實上，d是的線性函數(shù)，因此可采用增量計算，提高運算效率。方法如下。（1）

50、若，則取正右方像素p1(+1,)。判斷下一個像素的位置時，應(yīng)計算，增量為a。（2） 若d0，則取右上方像素p2(+1，+1)。要判斷下一個像素的位置，應(yīng)計算，增量為a+b。設(shè)從點(,)開始畫線，d的初值。因f(,)=0，則。由于使用的只是d的符號，而d的增量都是整數(shù)，只是初始值包含小數(shù)。因此，可以用2d代替d來擺脫浮點運算，寫出僅包含整數(shù)運算的算法。3.3.3 bresenham算法bresenham算法是在計算機圖形學(xué)領(lǐng)域內(nèi)使用最廣泛的直線掃描轉(zhuǎn)換算法。該方法類似于中點法，由誤差項符號決定下一個像素取右邊點還是右上點。圖3.7 bresenham算法所用誤差項的幾何意義如圖3.7所示，設(shè)直線

51、方程為y=kx+b，則有,其中k為直線的斜率。假設(shè)x列的像素坐標(biāo)已經(jīng)確定為，其行坐標(biāo)，那么下一個像素的列坐標(biāo)為+1，而行坐標(biāo)要么仍為，要么遞增1為+1。是否增1，取決于圖3.6所示誤差項d的值。因為直線的起始點在像素中心，所以誤差項d的初值=0。x下標(biāo)每增加1，d的值相應(yīng)遞增直線的斜率值k，即d=d+k。當(dāng)時，直線與+1列垂直網(wǎng)格的交點最接近于當(dāng)前像素(,)的右上方像素(+1,+1)，該像素在y方向增加1，同時作為下一次計算的新基點，因此d值相應(yīng)減去1；而當(dāng)時，更接近于右方像素(+1,)。為方便計算，令e=d-0.5，e的初值為-0.5，增量為k。當(dāng)時，取當(dāng)前像素(,)的右上方像素(+1,+1

52、)，e減少1；而當(dāng)時，更接近于右方像素(+1,)。圖3.8 bresenham算法流程圖bresenham算法流程圖如圖3.8所示。算法原理如下：過各行各列像素中心構(gòu)造一組虛擬網(wǎng)格線，按直線從起點到終點的順序計算直線與各垂直網(wǎng)格線的交點，然后確定該列像素中與此交點最近的像素。該算法的巧妙之處在于采用增量計算，使得對于每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。3.4 圓形模塊設(shè)計圓形模塊的流程圖如圖3.9所示。該模塊的主要功能是負(fù)責(zé)繪制圓形。繪制圓形的常用算法為中點畫圓法。圖3.9 圓形模塊的流程圖3.4.1 中點畫圓法構(gòu)造函數(shù)，對于圓上的點，；對于圓外的點，；對于圓內(nèi)的點，。

53、圖3.10 當(dāng)前像素與下一個像素的候選者與中點畫線法一樣，構(gòu)造判別式：（1） 若d0，則應(yīng)取p2為下一個像素。而且下一個像素的判別式為。（2） 若，則應(yīng)取p1為下一像素。而且下一個像素的判別式。這里討論的是按順時針方向生成第二個八分圓（見圖3.10），則第一個像素是(0,r)，判別式d的初始值為。中點畫圓算法流程圖如圖3.11所示。圖3.11 中點畫圓算法流程圖3.5 區(qū)域填充模塊設(shè)計該模塊的主要功能是負(fù)責(zé)填充圖形，區(qū)域填充模塊的流程圖如圖3.12所示。區(qū)域填充算法常用的算法有，區(qū)域填充的遞歸算法和區(qū)域填充的掃描線算法。圖3.12 區(qū)域填充模塊的流程圖3.5.1 區(qū)域填充的遞歸算法和掃描線算法

54、種子填充算法假設(shè)在多邊形內(nèi)有一個像素已知，由此出發(fā)利用連通性找到區(qū)域內(nèi)的所有像素。對于內(nèi)點表示和邊界表示的八連通區(qū)域的填充，只要將遞歸填充相鄰的4個像素增加到遞歸填充8個像素即可。區(qū)域填充的遞歸算法原理和程序都很簡單，但由于多次遞歸，費時、費內(nèi)存，效率不高。為了減少遞歸次數(shù)，提高效率，可以采用掃描線算法。掃描線算法的基本過程如下：當(dāng)給定種子點(x,y)時，首先填充種子點所在的掃描線上位于給定區(qū)域的一個區(qū)段，然后確定與這一區(qū)段相連通的上、下兩條掃描線上位于給定區(qū)域內(nèi)的區(qū)段，并依次保存下來。反復(fù)這個過程，直到填充結(jié)束。區(qū)域填充掃描線算法流程圖如圖3.13所示，區(qū)域填充的掃描線算法可由下列四個步驟實

55、現(xiàn)。（1） 初始化。堆棧置空，將種子點(x,y)入棧。（2） 出棧。若?？談t結(jié)束；否則取棧頂元素(x,y)，以y作為當(dāng)前掃描線。（3） 填充并確定種子點所在區(qū)段。從種子點(x,y)出發(fā)，沿當(dāng)前掃描線向左、右兩個方向填充，直到邊界。分別標(biāo)記區(qū)段的左、右端點坐標(biāo)為xl和xr。（4） 確定新的種子點。在區(qū)間中檢查與當(dāng)前掃描線y上、下相鄰的兩條掃描線上的像素。若存在非邊界、未填充的像素，則把每一區(qū)間的最右像素作為種子點壓入堆棧，返回第（2）步。圖3.13 區(qū)域填充掃描線算法流程圖3.6 裁剪圖形模塊設(shè)計3.6.1 直線段裁剪直線段裁剪算法比較簡單，但非常重要，是復(fù)雜原圖的基礎(chǔ)。因為復(fù)雜的曲線可以通過折

56、線段來近似，從而裁剪問題也可以化為直線段的剪裁問題。常用的線段剪裁方法，即cohen-sutherland法和梁友棟-barskey裁剪算法。（1） cohen-sutherland裁剪算法該算法的思想是：對于每條線段分為3種情況處理。第一種，若完全在窗口內(nèi)，則顯示該線段，簡稱“取”之。第二種，若明顯在窗口外，則丟棄該線段，簡稱“棄”之。第三種，若線段既不滿足“取”的條件，也不滿足“棄”的條件，則在交點處把線段分為兩段，其中一段完全在窗口外，可棄之，然后對另一段重復(fù)上述處理。為使計算機能夠快速判斷一條直線段與窗口屬何種關(guān)系，采用如下編碼方法：延長窗口的邊，將二維平面分成9個區(qū)域，每個領(lǐng)域賦予4

57、位編碼，如圖3.14所示，其中各位編碼的定義如下。圖3.14 多邊形裁剪區(qū)域編碼裁剪一條線段時，先求出所在的區(qū)號code1，code2。若code1=0，且code2=0，則線段在窗口內(nèi)，應(yīng)取之。若按位與運算code1&code20，則說明兩個端點同在窗口的上方、下方、左方或右方，可判斷線段完全在窗口外，可棄之；否則，按第三種情況處理，求出線段與窗口某邊的交點，在交點處把線段一分為二，其中必有一段在窗口外，可棄之，在對另一段重復(fù)上述處理。在實現(xiàn)本算法時，不必把線段與每條窗口邊界依次求交，只有按順序檢測到端點的編碼不為0時，才對線段與對應(yīng)的窗口邊界求交。cohen-sutherland裁剪算法流程圖如圖3.15所示 。圖3.15 cohen-sutherland裁剪算法流程圖（2） 梁友棟-barskey裁剪算法梁友棟和barskey提出了更快的參數(shù)化裁剪算法。首先按參數(shù)化形式寫出裁剪條件：這四個不等式可以表示為統(tǒng)一的形式：。