計(jì)算機(jī)圖形學(xué)

0.緒論提出問題-1什么是計(jì)算機(jī)圖形學(xué)？計(jì)算機(jī)圖形學(xué)是研究怎樣利用計(jì)算機(jī)來生成、處理和顯示圖形的原理、方法和技術(shù)的一門學(xué)科。-2計(jì)算機(jī)圖形學(xué)研究的對(duì)象是什么？-計(jì)算機(jī)圖形學(xué)的研究對(duì)象一一圖形通常意義下的圖形:-能夠在人的視覺系統(tǒng)中形成視覺印象的客觀對(duì)象都稱為圖形。-計(jì)算機(jī)圖形學(xué)中所研究的圖形-從客觀世界物體中抽象出來的帶有顏色及形狀信息的圖和形。-3計(jì)算機(jī)圖形處理系統(tǒng)的構(gòu)造？L圖形軟件圖形系統(tǒng)圖形應(yīng)用數(shù)據(jù)結(jié)構(gòu)L圖形軟件圖形系統(tǒng)圖形應(yīng)用數(shù)據(jù)結(jié)構(gòu)圖形應(yīng)用軟件圖形支撐軟件圖形硬件圖形計(jì)算機(jī)平臺(tái)—圖形設(shè)備圖1-3計(jì)算機(jī)圖形系統(tǒng)的結(jié)構(gòu)4計(jì)算機(jī)圖形學(xué)的應(yīng)用邊緣性學(xué)科計(jì)算機(jī)圖形學(xué)與傳統(tǒng)理論:交叉、界線模糊、相互滲透CAGD（計(jì)算幾何）逼近論（計(jì)算數(shù)學(xué)）微分幾何形態(tài)學(xué)圖形的表示點(diǎn)陣法是用具有顏色信息的點(diǎn)陣來表示圖形的一種方法，它強(qiáng)調(diào)圖形由哪些點(diǎn)組成，并具有什么灰度或色彩。參數(shù)法是以計(jì)算機(jī)中所記錄圖形的形狀參數(shù)與屬性參數(shù)來表示圖形的一種方法。誦.常把參數(shù)法描述的圖形叫做圖形9叫巾ics）把點(diǎn)陣法描述的圖形叫做圖象Sage）與計(jì)算機(jī)圖形學(xué)相關(guān)的學(xué)科計(jì)算機(jī)圖形學(xué)試圖從非圖象形式的數(shù)據(jù)描述來生成（逼真的）圖象。數(shù)字圖象處理旨在對(duì)圖象進(jìn)行各種加工以改善圖象的視覺效果。計(jì)算機(jī)視覺是研究用計(jì)算機(jī)來模擬生物外顯或宏觀視覺功能的科學(xué)和技術(shù)。數(shù)字圖象處理圖1-1數(shù)字圖象處理圖1-1圖形圖象處理相關(guān)學(xué)科間的關(guān)系0.4.1計(jì)算機(jī)圖形系統(tǒng)的功能廠圖形輸出設(shè)備二: >|輸出!~—―>示交^ ' 一j￡一 一匕一 頃據(jù)庫T : H"輸入「-圖形輸入設(shè)備■"；圖1-2圖形系統(tǒng)基本功能框圖第3章基于光柵掃描的二維圖元生成算法提出問題如何在指定的輸出設(shè)備上根據(jù)坐標(biāo)描述構(gòu)造基本二維幾何圖形（點(diǎn)、直線、圓、橢圓、多邊形域、字符串及其相關(guān)屬性等）。圖形的生成：是在指定的輸出設(shè)備上，根據(jù)坐標(biāo)描述構(gòu)造二維幾何圖形。圖形的掃描轉(zhuǎn)換：在光柵顯示器等數(shù)字設(shè)備上確定一個(gè)最佳逼近于圖形的象素集的過程。直線的繪制要求：?:?1.直線要直?:?2,直線的端點(diǎn)要準(zhǔn)確?:?3.直線的亮度、色澤要均勻?4.畫線的速度要快???5.要求直線具有不同的色澤、亮度、線型等特點(diǎn)：???增量算法，直觀、易實(shí)現(xiàn)、誤差小，不利于用硬件實(shí)現(xiàn)二、直線的Bresenham算法（中點(diǎn)Bresenham算法基本思想：每步一個(gè)坐標(biāo)改變±1,而另一個(gè)坐標(biāo)要看當(dāng)前點(diǎn)與直線上點(diǎn)的誤差e,根據(jù)e的符號(hào)決定是否改變顯然有結(jié)論：當(dāng)di>0時(shí)，因八T小，因此選擇點(diǎn)Ti以逼近理想直線，所以有：當(dāng)di<0時(shí)，因AS小，因此選擇點(diǎn)Si以逼近理想直線，所以有：當(dāng)di=0時(shí)，因AS=AT，規(guī)定此時(shí)選擇點(diǎn)Ti逼近理想直線，所以有：3.3區(qū)域填充實(shí)面積圖形：封閉圖形（或有界表面），在其封閉的面積上（輪廓內(nèi)）具有相同的亮度或色彩，這意味著要讓計(jì)算機(jī)填充光柵掃描圖形顯示器（點(diǎn)陣圖形顯示器）中封閉面積上的每一個(gè)顯示點(diǎn)（像素點(diǎn)）。根據(jù)表示實(shí)面積圖形的方法不同，實(shí)面積圖形的生成可分為兩大類：（1）多邊的填充：即實(shí)面積圖形的輪廓用其封閉多邊形的頂點(diǎn)坐標(biāo)數(shù)據(jù)來描述定義（簡(jiǎn)稱實(shí)面積圖形的圖形表示法），在其封閉的多邊形內(nèi)部填充用戶指定的顏色；（2）種子填充：即用點(diǎn)陣方式描述定義實(shí)面積圖形，這個(gè)圖形的實(shí)面積由用戶指定的點(diǎn)陣顏色包圍或組成（簡(jiǎn)稱實(shí)面積圖形的圖像表示法），在圖形的實(shí)面積上填充用戶指定的顏色，其中這個(gè)指定的第一個(gè)填充點(diǎn)又稱為種子。由于種子填充算法原則上屬圖像處理方法，故不在此討論。多邊形：是一個(gè)由折線段組成的封閉圖形，它由有序頂點(diǎn)的點(diǎn)集 及有向邊的線集定義。n為多邊形的頂點(diǎn)數(shù)或邊數(shù)，且Ei=ViVi+1,i=1，2，…，n。這里Vn+1=V1，用以保證多邊形的封閉性。應(yīng)注意，當(dāng)用多邊形來表示有界平面或?qū)嵜娣e圖形的邊界時(shí)，規(guī)定多邊形每條有向邊的左側(cè)為實(shí)面積圖形的實(shí)面積區(qū)域（或內(nèi)部區(qū)域），因此它不允許多邊形的邊線自相交叉（見圖3?3-1）。環(huán)：因?yàn)槎噙呅蔚挠邢蜻吘€左側(cè)為其實(shí)面積區(qū)域，故沿實(shí)面積圖形外輪廓線多邊形的頂點(diǎn)方向順序環(huán)行時(shí)，要求該多邊形頂點(diǎn)的整個(gè)環(huán)行方向逆時(shí)針旋轉(zhuǎn)；而沿其內(nèi)輪廓線多邊形的頂點(diǎn)方向順序環(huán)行時(shí)，要求該多邊形頂點(diǎn)的整個(gè)環(huán)行方向順時(shí)針旋轉(zhuǎn)。這種定義了環(huán)行方向的多邊形稱為環(huán)。前者為外環(huán)，后者為內(nèi)環(huán)（見圖3?3-2）。帶孔多邊形由一個(gè)外環(huán)和數(shù)個(gè)內(nèi)環(huán)組成的多邊形稱為帶孔多邊形，若多邊形沒有內(nèi)環(huán)即為不帶孔多邊形。凹、凸多邊形的判別方法當(dāng)多邊形的頂點(diǎn)數(shù)據(jù)按環(huán)的要求存放后，判斷外環(huán)上凹、凸點(diǎn)的方法是：定義(3.3-1)定義VVxW(3.3-1)i-1iii+1其中，a的表達(dá)式見公式（3.3-2），向量k與Vi-1Vi，ViVi+1符合右手螺旋法則。?:?若數(shù)值a<0,則Vi點(diǎn)為凹點(diǎn)，否則為凸點(diǎn)。?:?具有凹點(diǎn)的多邊形為凹多邊形，只具有凸點(diǎn)的多邊形為凸多邊形。???外環(huán)的凹點(diǎn)對(duì)應(yīng)的內(nèi)角一定大于180°，凸點(diǎn)的內(nèi)角小于180°，人們一般利用這一性質(zhì)直觀地判別凹凸多邊形，并有如下結(jié)論：任何一個(gè)多邊形，其外形上凸點(diǎn)的個(gè)數(shù)總是多于其凹點(diǎn)的個(gè)數(shù)。這一結(jié)論用于三維空間的有界平面中，就能確定每個(gè)有界平面的朝向（見后述）。二、 多邊形的填充原理找出所有位于封閉圖形內(nèi)的像素點(diǎn)，把這些點(diǎn)置換成所要求的像素值。如果在顯示屏中，采用從上到下、從左到右找出每一個(gè)顯示點(diǎn)，然后通過多邊形的邊界函數(shù)（凸多邊形有邊界函數(shù)且表達(dá)方式簡(jiǎn)單）等方法，判斷其是否位于封閉圖形之內(nèi)后再填充。這種方法原理雖然簡(jiǎn)單，但速度太慢，特別不適合凹多邊形與帶孔多邊形的填充需要。因此有必要尋找一種通用的（適用與凹、凸、帶孔的多邊形）快速判斷像素點(diǎn)位于封閉圖形之內(nèi)的計(jì)算方法，這是多邊形圖形填充的關(guān)鍵。射線的交點(diǎn)計(jì)數(shù)法：判斷像素點(diǎn)位于封閉圖形內(nèi)外的方法如下：從封閉圖形外找一點(diǎn)，引一水平射線（稱為掃描線）與封閉圖形相交。當(dāng)交點(diǎn)計(jì)數(shù)為奇數(shù)時(shí)，掃描線在封閉圖形內(nèi)（射線穿入封閉圖形）；當(dāng)交點(diǎn)計(jì)數(shù)為偶數(shù)時(shí)，掃描線在封閉圖形外，該方法簡(jiǎn)稱交點(diǎn)計(jì)數(shù)法則。如圖3.3-3所示因此在正確計(jì)算掃描線與封閉多邊形的所有交點(diǎn)之后，圖形的填充就成了畫直線的過程。這種逐個(gè)計(jì)算要顯示的各點(diǎn)并顯示的過程又稱掃描轉(zhuǎn)換三、 多邊形的（YX）填充算法（YX）填充算法根據(jù)多邊形填充算法的原理，先求出多邊形各斜邊與掃描線的所有交點(diǎn)并記錄；然后按從上到下、從左到右的次序?qū)λ械慕稽c(diǎn)進(jìn)行排序；最后利用這些交點(diǎn)總是成對(duì)出現(xiàn)并從上到下、從左到右排列的規(guī)律畫直線，畫完所有的直線即完成填充任務(wù)。對(duì)于圖3.3-5(a)所示的多邊形，其掃描線與多邊形各斜邊的交點(diǎn)的排序結(jié)果如圖3.3-5(b)所示。根據(jù)這一結(jié)果，讀者不難完成該多邊形的填充。四、多邊形的Y-X填充算法(YX)填充算法雖然簡(jiǎn)單，?:?但當(dāng)多邊形的形狀復(fù)雜時(shí)，其交點(diǎn)表的容量非常大；?:?而且對(duì)交點(diǎn)進(jìn)行排序很費(fèi)時(shí)，這極大地影響了該算法的使用效果；為了克服這兩個(gè)缺點(diǎn)，可對(duì)該算法進(jìn)行如下改進(jìn)：???改進(jìn)存儲(chǔ)方式。不存儲(chǔ)多邊形上每個(gè)交點(diǎn)的坐標(biāo)，而是存儲(chǔ)其每條斜邊。如果一條斜邊用其2個(gè)頂點(diǎn)坐標(biāo)變量(x1，y1)，(x2,y2)來代替的話，這將比存儲(chǔ)斜邊上的每個(gè)交點(diǎn)坐標(biāo)所需要的存儲(chǔ)容量要少得多；?改進(jìn)交點(diǎn)的計(jì)算方法，并要求斜邊上的每一交點(diǎn)與填充掃描線同步出現(xiàn)，以便畫線填充多邊形；???因多邊形的斜邊總量遠(yuǎn)比其交點(diǎn)總量小，故對(duì)斜邊的排序相對(duì)較快。3.6.2圖形的裁剪在二維觀察中，需要在觀察坐標(biāo)系下對(duì)窗口進(jìn)行裁剪，即只保留窗口內(nèi)的那部分圖形，去掉窗口外的圖形。一、 點(diǎn)與字符的裁剪當(dāng)圖形系統(tǒng)的窗口確定之后，設(shè)被裁剪的點(diǎn)坐標(biāo)為(X,y)，則只有當(dāng)該點(diǎn)的坐標(biāo)滿足下式 JXWx<x[J<J<J該點(diǎn)才位于窗口之切并經(jīng)窗視變換送視區(qū)中顯示，否則該點(diǎn)位于窗口之外而被舍去。二、 直線段的裁剪假定直線段用p1(x1,y1)p2(x2,y2)表示。???直線段和剪裁窗口的可能關(guān)系：椅完全落在窗口內(nèi)椅完全落在窗口外椅與窗口邊界相交???實(shí)交點(diǎn)是直線段與窗口矩形邊界的交點(diǎn)。?虛交點(diǎn)則是直線段與窗口矩形邊界延長線或直線段的延長線與窗口矩形邊界的交點(diǎn)。直線的編碼裁剪算法基本思想：對(duì)每條直線段p1(x1,y1)p2(x2,y2)分三種情況處理：(1)直線段完全可見，“簡(jiǎn)取”之。⑵直線段完全不可見，“簡(jiǎn)棄”之。直線段既不滿足“簡(jiǎn)取”的條件，也不滿足“簡(jiǎn)棄”的條件，需要對(duì)直線段按交點(diǎn)進(jìn)行分段，分段后重復(fù)上述處理。算法的步驟：輸入直線段的兩端點(diǎn)坐標(biāo)：p1(x1,y1)、p2(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。對(duì)p1、p2進(jìn)行編碼：點(diǎn)p1的編碼為code1，點(diǎn)p2的編碼為code2。⑶若code1|code2=0000，對(duì)直線段應(yīng)簡(jiǎn)取之，轉(zhuǎn)(6)；否則，若code1&code2夭0000，對(duì)直線段可簡(jiǎn)棄之，轉(zhuǎn)(7)；當(dāng)上述兩條均不滿足時(shí)，進(jìn)行步驟(4)。確保pl在窗口外部：若pl在窗口內(nèi)，則交換pl和p2的坐標(biāo)值和編碼。按左、右、上、下的順序求出直線段與窗口邊界的交點(diǎn)，并用該交點(diǎn)的坐標(biāo)值替換pl的坐標(biāo)值。也即在交點(diǎn)s處把線段一分為二，并去掉pls這一段?？紤]到pl是窗口外的一點(diǎn)，因此可以去掉pls。轉(zhuǎn)(2)。用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段plp2。算法結(jié)束。特點(diǎn)：在兩類裁剪場(chǎng)合非常高效：大窗口和特別小的窗口中點(diǎn)分割算法基本思想：當(dāng)對(duì)直線段不能簡(jiǎn)取也不能簡(jiǎn)棄時(shí)，簡(jiǎn)單地把線段等分為二段，對(duì)兩段重復(fù)上述測(cè)試處理，直至每條線段完全在窗口內(nèi)或完全在窗口外。算法步驟：(】)輸入直線段的兩端點(diǎn)坐標(biāo)：pl(xl,yl)、p2(x2,y2)，以及窗口的四條邊界坐標(biāo)：wyt、wyb、wxl和wxr。對(duì)pl、p2進(jìn)行編碼：點(diǎn)pl的編碼為codel，點(diǎn)p2的編碼為code2。若code1|code2=0000，對(duì)直線段應(yīng)簡(jiǎn)取之，保留當(dāng)前直線段的端點(diǎn)坐標(biāo)，轉(zhuǎn)(5)；否則，若code1&code2尹0000，對(duì)直線段可簡(jiǎn)棄之，轉(zhuǎn)(5)；當(dāng)上述兩條均不滿足時(shí)，進(jìn)行步驟4)。求出直線段的中點(diǎn)M，將plM、p2M入棧。⑸當(dāng)棧不空時(shí)，從棧中彈出一條直線段，取為p1p2,轉(zhuǎn)⑵進(jìn)行處理。否則，繼續(xù)(6)。(6)當(dāng)棧為空時(shí)，合并保留的直線段端點(diǎn)，得到窗口內(nèi)的直線段p1p2。用直線掃描轉(zhuǎn)換算法畫出當(dāng)前的直線段p1p2，算法結(jié)束。中點(diǎn)分割算法的核心思想是誦過二分逼近來確定直線段與窗口的交點(diǎn)。1.多邊形的逐邊裁剪算法算法實(shí)施策略：?:?為窗口各邊界裁剪的多邊形存儲(chǔ)輸入與輸出頂點(diǎn)表。在窗口的一條裁剪邊界處理完所有頂點(diǎn)后，其輸出頂點(diǎn)表將用窗口的下一條邊界繼續(xù)裁剪。?窗口的一條邊以及延長線構(gòu)成的裁剪線把平面分為兩個(gè)區(qū)域，包含有窗口區(qū)域的一個(gè)域稱為可見側(cè)；不包含窗口區(qū)域的域?yàn)椴豢梢妭?cè)。特點(diǎn)：適用于凸多邊形和裁剪后仍連通的凹多邊形，適于用硬件實(shí)現(xiàn)當(dāng)多邊形的所有頂點(diǎn)都按這種情況處理完畢之后，所保存的頂點(diǎn)與交點(diǎn)就是所組成的數(shù)個(gè)新多邊形的頂點(diǎn)。為使新多邊形封閉，注意還要裁剪VnVl所組成的邊(V1,Vn分別是多邊形的第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn))。在實(shí)現(xiàn)該算法時(shí)，如果保留每次裁剪之后的中間結(jié)果，這一中間結(jié)果會(huì)占用很大的存儲(chǔ)空間，但如果能用遞歸的方式實(shí)現(xiàn)該算法，則不用保留每次裁剪的中間結(jié)果。遞歸算法：???首先按多邊形的頂點(diǎn)次序依次裁剪多邊形的每條邊；???而對(duì)多邊形的每條邊先用窗口的第一條邊框去裁剪；?當(dāng)這條邊通過窗口的第一條邊框裁剪之后；?再用窗口的第二條邊框去裁剪；?如果它通過第二條邊框裁剪之后；???再用窗口的第三、四條邊框去裁剪；?最后通過第四條邊框裁剪輸出的頂點(diǎn)與交點(diǎn)，就是被窗口裁剪之后新多邊形的頂點(diǎn)。?:?不能通過上述四步裁剪的邊線，其頂點(diǎn)與交點(diǎn)自然被舍棄，因而對(duì)應(yīng)的邊線也被裁掉。圖形幾何變換的目的：是用已有的簡(jiǎn)單圖形構(gòu)造復(fù)雜圖形5.1圖形的幾何變換1齊次坐標(biāo)?齊次坐標(biāo)表示就是用n+1維向量表示一個(gè)n維向量。椅二維平面中的一個(gè)點(diǎn)P（x,y），在齊次坐標(biāo)系中可表示成P（w?x,w?y,w）其中W是一個(gè)不為0的常量；反過來，只要能給定一個(gè)點(diǎn)的齊次坐標(biāo)，我們就能得到這個(gè)點(diǎn)的二維直角坐標(biāo)系 。齊次坐標(biāo)的不唯一性規(guī)范化齊次坐標(biāo)表示就是W=1的齊次坐標(biāo)表示。???如何從齊次坐標(biāo)轉(zhuǎn)換到規(guī)范化齊次坐標(biāo)？2幾何變換圖形的幾何變換是指對(duì)圖形的幾何信息經(jīng)過平移、比例、旋轉(zhuǎn)等變換后產(chǎn)生新的圖形，是圖形在方向、尺寸和形狀方面的變換?；編缀巫儞Q都是相對(duì)于坐標(biāo)原點(diǎn)和坐標(biāo)軸進(jìn)行的幾何變換1平移變換平移是指將p點(diǎn)沿直線路徑從一個(gè)坐標(biāo)位置移到另一個(gè)坐標(biāo)位置的重定位過程。平移是一種不產(chǎn)生變形而移動(dòng)物體的剛體變換2比例變換比例變換是指對(duì)p點(diǎn)相對(duì)于坐標(biāo)原點(diǎn)沿x方向放縮Sx倍，沿y方向放縮Sy倍。其中Sx和Sy稱為比例系數(shù)。3旋轉(zhuǎn)變換二維旋轉(zhuǎn)是指將p點(diǎn)繞坐標(biāo)原點(diǎn)轉(zhuǎn)動(dòng)某個(gè)角度（逆時(shí)針為正，順時(shí)針為負(fù)）得到新的點(diǎn)p’的重定位過程。4對(duì)稱變換對(duì)稱變換后的圖形是原圖形關(guān)于某一軸線或原點(diǎn)的鏡像。5錯(cuò)切變換錯(cuò)切變換（主要用于三維圖形變換），也稱為剪切、錯(cuò)位變換，用于產(chǎn)生彈性物體的變形處理。（1）沿x方向錯(cuò)切 （2）沿y方向錯(cuò)切 （3）兩個(gè)方向錯(cuò)切二維圖形幾何變換的計(jì)