1、計(jì)算機(jī)圖形學(xué),武漢大學(xué)電子信息學(xué)院 王泉德 ,第五章 圖形生成和計(jì)算,一、 區(qū)域填充,一個(gè)區(qū)域是指一組相鄰而又相連的象素，且具有同樣的屬性。區(qū)域的建立和定義通?？刹捎脙煞N方式： 內(nèi)定義區(qū)域（Interior-Defined）：區(qū)域內(nèi)部所有象素具有同一種顏色或亮度值，而區(qū)域外的所有象素具有其他顏色或亮度值。 邊界定義區(qū)域（Boundary-Defined）：區(qū)域邊界上所有象素均具有特定的顏色或亮度值，而在區(qū)域內(nèi)、外的象素則具有不同于邊界值的顏色或亮度值。,給出一個(gè)區(qū)域的邊界，要求對(duì)邊界范圍內(nèi)的所有象素單元賦予指定的顏色代碼稱為區(qū)域填充。區(qū)域填充算法可分為兩大類： 種子填充算法：假定封閉輪廓線內(nèi)某

2、點(diǎn)是已知的，然后算法開(kāi)始搜索與種子點(diǎn)相鄰且位于輪廓線內(nèi)的點(diǎn)。種子填充算法只適用于光柵掃描設(shè)備。 掃描轉(zhuǎn)換填充算法：按掃描線的順序確定某一點(diǎn)是否位于多邊形或輪廓線范圍之內(nèi)。算法一般從輪廓線的頂部開(kāi)始進(jìn)行到它的底部。 區(qū)域填充的邊界可以是直線也可以是曲線。,1：多邊形區(qū)域的掃描轉(zhuǎn)換 2：多邊形區(qū)域的種子填充 3：光柵圖形的反走樣算法,1.多邊形的掃描轉(zhuǎn)換,1.1 掃描轉(zhuǎn)換 計(jì)算機(jī)生成的物體常常可以用若干多邊形來(lái)描述，有些非多邊形的物體，也可以用多邊形來(lái)逼近。在計(jì)算機(jī)圖形學(xué)中，多邊形有兩種重要的表示方法：頂點(diǎn)表示和點(diǎn)陣表示。 頂點(diǎn)表示是用多邊形的頂點(diǎn)序列來(lái)刻劃多邊形。這種方式直觀，幾何意義強(qiáng)，占用內(nèi)

3、存少，但不能直接用于面著色。 點(diǎn)陣表示是用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。這種方法雖然失去了很多重要的幾何信息，但便于運(yùn)用幀緩沖器表示圖形，是面著色所需要的圖形表示形式。,頂點(diǎn)表示的多邊形,P4,P0,P3,P2,P1,點(diǎn)陣表示的多邊形,光柵圖形的一個(gè)基本問(wèn)題就是把多邊形的頂點(diǎn)表示轉(zhuǎn)換成為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)部的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常這種轉(zhuǎn)換稱為“多邊形的掃描轉(zhuǎn)換”。 多邊形的掃描轉(zhuǎn)換過(guò)程，實(shí)際上就是給多邊形包圍的區(qū)域著色的過(guò)程，因此是一種面著色的方法。,掃描轉(zhuǎn)換的常用算法,逐點(diǎn)判斷算法 掃描線算法 邊緣填充算法

4、 邊界標(biāo)志算法,1.2 逐點(diǎn)判斷算法,思想：逐個(gè)象素判別，確定它們是否在多邊形內(nèi)部，從而給出位于多邊形內(nèi)的點(diǎn)（象素）的集合。 難點(diǎn)：如何確定一個(gè)點(diǎn)是否在多邊形內(nèi)部？,點(diǎn)是否在多邊形內(nèi)部的檢驗(yàn),為了對(duì)多邊形內(nèi)部的象素點(diǎn)賦值，首先要解決如何判斷一個(gè)點(diǎn)是否在多邊形內(nèi)部。 判斷的方法：先在多邊形外部找一個(gè)點(diǎn)，然后用線段連接待判決點(diǎn)和待判決點(diǎn)，計(jì)算出此線段與多邊形邊界相交的次數(shù)，如果交點(diǎn)的數(shù)目為奇數(shù)，則待判決點(diǎn)在多邊形內(nèi)部；如果為偶數(shù)，待判決點(diǎn)在多邊形外部。,1,1,3,2,2,3,P,4,圖例,（1）怎樣才能“在多邊形外部找一個(gè)點(diǎn)”？ 確定多邊形的包圍矩形：即xmin,ymin,xmax,ymax，在

5、包圍矩形外的點(diǎn)肯定是多邊形的外部點(diǎn)； （2）交點(diǎn)計(jì)數(shù)的特殊情況處理,線段和多邊形相交在頂點(diǎn)（奇點(diǎn)的處理）： 當(dāng)線段與多邊形P的交點(diǎn)是P的頂點(diǎn)Pi 時(shí)，則稱該交點(diǎn)為奇點(diǎn); 為了保證線段和多邊形P邊界的交點(diǎn)個(gè)數(shù)為偶數(shù)，現(xiàn)將奇點(diǎn)分為極值點(diǎn)和非極值點(diǎn)兩類：如果相交的兩條邊位于線段同側(cè)，則頂點(diǎn)Pi 為極值點(diǎn)，否則為非極值點(diǎn); 當(dāng)奇點(diǎn)是P的極值點(diǎn)時(shí)，該點(diǎn)按照兩個(gè)交點(diǎn)計(jì)算；否則按照一個(gè)交點(diǎn)計(jì)算。,線段和多邊形邊共線：線段與多邊形相交二次；,算法實(shí)現(xiàn),現(xiàn)設(shè)P=P0P1PnP0為一給定的多邊形。Framebuffer(x,y)是與點(diǎn)(x,y)相對(duì)應(yīng)的幀緩沖器中的元素。則逐點(diǎn)判斷的算法可以表示成為如下的程序： f

6、or y:= ymin to ymax do for x:= xmin to xmax do if inside(p, x, y) then setpixel(framebuffer, x, y, polygon-color) else setpixel(framebuffer, x, y, back-color);,逐點(diǎn)判斷的算法雖然程序簡(jiǎn)單，但是不可取。原因是速度太慢，該算法割斷了各個(gè)象素之間的聯(lián)系，孤立的考察各個(gè)象素和多邊形P的內(nèi)外關(guān)系，使得幾十萬(wàn)甚至幾百萬(wàn)個(gè)象素都要一一判別，每次判別都要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)大量的時(shí)間。,1.3 掃描線算法,掃描線算法是多邊形掃描轉(zhuǎn)換的

7、常用方法。相比起逐點(diǎn)判斷算法，掃描線算法充分利用了象素之間的連貫性，避免的對(duì)象素的逐點(diǎn)判斷和反復(fù)求交的過(guò)程。 掃描線算法綜合利用了區(qū)域的連貫性，掃描線連貫性和邊的連貫性等三種形式的連貫性。,區(qū)域的連貫性,yk+1,yk,掃描線yk和yk+1將多邊形P分割成若干的梯形，它們具有如下的性質(zhì)：,梯形的兩底邊分別在y=yk和y=yk+1兩條掃描線上，腰在多邊形P的邊上和顯示屏幕的邊界上； 這些梯形可以分為兩類，一類在多邊形P的內(nèi)部，一類在多邊形P的外部； 兩類梯形在長(zhǎng)方形區(qū)域yk , yk+1內(nèi)相間的排列，即相鄰的兩個(gè)梯形必有一個(gè)在多邊形P內(nèi)，另一個(gè)在P外； 根據(jù)這些性質(zhì)，實(shí)際上只要知道該長(zhǎng)方形區(qū)域z

8、中任一梯形內(nèi)一點(diǎn)關(guān)于多邊形P的內(nèi)外關(guān)系后，整個(gè)梯形內(nèi)關(guān)于多邊形P的內(nèi)外關(guān)系就可以確定了。,掃描線的連貫性,掃描線yk和多邊形P相交，交點(diǎn)為X1,X2,.XL，它們具有如下的性質(zhì)：,L是偶數(shù)； 該掃描線上，區(qū)段(Xk, Xk+1),k=1,3,5位于多邊形P內(nèi)部，其余區(qū)段都在多邊形P外。兩類區(qū)段沿掃描線相間排列。,邊的連貫性,設(shè)d為一整數(shù)，d=e-1。若多邊形P的邊Pr-1Pr與掃描線y=d和y=e都相交，和兩交點(diǎn)的橫坐標(biāo)xe和xd滿足下面的關(guān)系(mr為斜率)：,因此，可利用多邊形與當(dāng)前掃描線交點(diǎn)的位置及遞推關(guān)系，求得多邊形與下一條掃描線的交點(diǎn)的位置。以上性質(zhì)稱為邊的連貫性，它是區(qū)域的連貫性在兩

9、條相鄰掃描線上的體現(xiàn)。,掃描線和多邊形相交在頂點(diǎn)（奇點(diǎn)的處理）： 當(dāng)掃描線與多邊形P的交點(diǎn)是P的頂點(diǎn)Pi 時(shí)，則稱該交點(diǎn)為奇點(diǎn); 為了保證掃描線和多邊形P邊界的交點(diǎn)個(gè)數(shù)為偶數(shù)，現(xiàn)將奇點(diǎn)分為極值點(diǎn)和非極值點(diǎn)兩類：如果相交的兩條邊位于掃描線同側(cè)，即： (yi+1-yi)*(yi-1-yi)0 則頂點(diǎn)Pi 為極值點(diǎn)，否則為非極值點(diǎn); 當(dāng)奇點(diǎn)是P的極值點(diǎn)時(shí)，該點(diǎn)按照兩個(gè)交點(diǎn)計(jì)算；否則按照一個(gè)交點(diǎn)計(jì)算。,掃描線和多邊形邊共線：線段與多邊形相交二次；,掃描線算法的實(shí)現(xiàn),算法的基本思想： 利用多邊形的邊的連貫性和掃描線的連貫性，對(duì)于一個(gè)給定的多邊形，用一組水平(垂直)的掃描線進(jìn)行掃描 對(duì)每一條掃描線均可求出

10、與多邊形邊的交點(diǎn) 交點(diǎn)將掃描線分割成落在多邊形內(nèi)部的線段和落在多邊形外部的線段，并且二者相間排列 將落在多邊形內(nèi)部的線段上的所有象素點(diǎn)賦以給定的色彩值。,掃描線算法的實(shí)現(xiàn)原理,根據(jù)多邊形內(nèi)部點(diǎn)的連續(xù)性知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。所以，對(duì)所有的掃描線填充入點(diǎn)到出點(diǎn)之間所有的點(diǎn)就可填充多邊形。 判斷掃描線上的點(diǎn)是否在多邊形之內(nèi)根據(jù)多邊形區(qū)域連續(xù)性，分為3個(gè)步驟： 求出掃描線與多邊形所有邊的交點(diǎn)； 把這些交點(diǎn)的x坐標(biāo)值以升序排列； 從奇數(shù)交點(diǎn)出發(fā)到偶數(shù)交點(diǎn)的掃描 線段位于多邊形內(nèi)部。 如右圖，排序x坐標(biāo)得到的交點(diǎn)序列是 (2,4,9,13)，然后對(duì)交點(diǎn)2與

11、4之間、9與13之間的所有象素點(diǎn)進(jìn)行填充。,掃描線算法的實(shí)現(xiàn)原理奇點(diǎn)的處理,p1,p3,p4,p5屬于局部極值點(diǎn)，要把他們兩次存入交點(diǎn)表中。 如掃描線y=7上的交點(diǎn)中，有交點(diǎn)(2,7,13)，按常規(guī)方法填充不正確，而要把頂點(diǎn)(7,7)兩次存入交點(diǎn)表中(2,7,7,13)。p2，p6為非極值點(diǎn)，則不用如上處理。,p1,p2,p3,p4,p5,p6,p1,p2,p3,p4,p5,p6,掃描線算法的實(shí)現(xiàn)步驟,對(duì)于一條掃描線填充過(guò)程可以分為四個(gè)步驟： 求交 排序 配對(duì) 填色,掃描線算法的數(shù)據(jù)結(jié)構(gòu),邊的活化鏈表(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)

12、鏈表中，結(jié)點(diǎn)內(nèi)容 x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo) x：從當(dāng)前掃描線到下一條掃描線間x的增量(邊斜率的倒數(shù)) ymax：該邊所交的最高掃描線號(hào)ymax,邊的分類表(ET)：存放在該掃描線第一次出現(xiàn)的邊。若某邊的較低端點(diǎn)為ymin，則該邊就放在掃描線ymin的新邊表中。,x：邊的下端點(diǎn)的x坐標(biāo)； x：從當(dāng)前掃描線到下一條掃描線間x的增量 ymax：該邊所交的最高掃描線號(hào)ymax,掃描線算法描述,建立ET表，置y為ET表中非空的最小y坐標(biāo)值 置AEL表為空，且按照y值將ET表的邊加入AEL表中 while AEL表非空并且ET表中非空 dobegin 對(duì)AEL表中的xmin值按升序排列 按照AEL表中

13、交點(diǎn)前后次序，在每對(duì)奇偶交點(diǎn)間的x段予以填充 if 掃描線 y=ymaxthen 從AEL表中刪除這些邊 對(duì)在AEL表中的其他邊，計(jì)算與下一條掃描線的交點(diǎn)：x=x+1/m 計(jì)算下一條掃描線：y=y+1 按照掃描線y值把ET表中相應(yīng)的邊加入AEL表中end end of algorithm,掃描線算法性能分析,掃描線算法的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)都遠(yuǎn)比逐點(diǎn)判斷算法復(fù)雜，對(duì)各種表的維護(hù)和排序的耗費(fèi)很大； 但是由于它充分利用的多邊形的區(qū)域、掃描線和邊的三種形式的連貫性，從而避免了反復(fù)求交點(diǎn)的大量運(yùn)算，因此速度比逐點(diǎn)判斷法快的多。,1.4 邊緣填充算法,基本思想： 在光柵圖形中，如果某區(qū)域已經(jīng)著上了為M的某

14、種顏色，則對(duì)M做偶數(shù)次求補(bǔ)運(yùn)算后，該區(qū)域的顏色不變；而做奇數(shù)次求補(bǔ)運(yùn)算后，該區(qū)域則變?yōu)?的顏色。因此，邊緣填充算法對(duì)于每一條掃描線與多邊形邊的交點(diǎn)(x,y)，依次將交點(diǎn)右方的所有象素取補(bǔ)，從而實(shí)現(xiàn)對(duì)多邊形的填充。,算法實(shí)現(xiàn),步驟1：將位于掃描線y=e上的所有象素都著上值為M的顏色； for x:= xmin to xmax do setpixel(framebuffer, x, e, M); 步驟2：對(duì)每一個(gè)交點(diǎn)xi,依次向右求補(bǔ)； for i:= 1 to m do for x:= xi to xmax do complement(framebuffer, x, e) 當(dāng)完成上述兩個(gè)步驟后，

15、掃描線y=e上位于多邊形內(nèi)部的象素進(jìn)行了奇數(shù)次求補(bǔ)運(yùn)算，并著上了 的顏色。,改進(jìn)：,對(duì)于復(fù)雜的圖形，一些象素可能被訪問(wèn)多次，一種改進(jìn)的辦法是引入柵欄。通過(guò)多邊形設(shè)一柵欄，每次只對(duì)交點(diǎn)與柵欄之間的象素點(diǎn)取補(bǔ)，可使訪問(wèn)象素的次數(shù)減少。下圖示出了這一算法的原理。,邊緣填充算法性能分析,邊緣填充算法的數(shù)據(jù)結(jié)構(gòu)和程序結(jié)構(gòu)都比掃描線算法簡(jiǎn)單的多。因?yàn)檫吘壧畛渌惴ㄓ们笱a(bǔ)代替了排序，因此在算法執(zhí)行時(shí)需要對(duì)幀緩沖器中的大批元素反復(fù)的賦值，因此速度不比掃描線算法快。,1.5 邊界標(biāo)志算法,算法思想： 先用一種特殊的顏色將多邊形的邊界勾畫(huà)出來(lái)，然后在采用和掃描線算法相類似的方法將位于多邊形內(nèi)的各個(gè)區(qū)段著上所需要的顏

16、色。,邊界標(biāo)志算法實(shí)現(xiàn)步驟,步驟1：以值為boundary-color的特殊顏色勾畫(huà)多邊形P的邊界?？刹捎孟鄳?yīng)的直線生成算法； 步驟2：逐條掃描線對(duì)多邊形著色。先將掃描線上值為boundary-color的特殊象素點(diǎn)依x坐標(biāo)遞增順序兩兩配對(duì)，再將中間的象素著上相應(yīng)的顏色；,邊界標(biāo)志算法類語(yǔ)言描述,For y:= ymin to ymax do Begin interior-point := false; for x:= xmin to xmax do begin if getpixel(framebuffer,x,y) = boundary-color then interior-point

17、= not interior-point; if interior-point then setpixel(framebuffer,x,y,polygon-color) else setpixel(framebuffer,x,y,background-color); end end,邊界標(biāo)志算法性能分析,和邊界填充算法相比，本算法避免了對(duì)幀緩沖器中的大量元素的多次賦值，但是需要逐條掃描線的對(duì)幀緩沖器中的元素進(jìn)行搜索和比較。當(dāng)用軟件實(shí)現(xiàn)本算法時(shí)，速度與掃描線算法相當(dāng)。本算法適合于硬件實(shí)現(xiàn)，硬件實(shí)現(xiàn)時(shí)的速度則有很大的提高。,2. 多邊形的種子填充,種子填充是指先將區(qū)域內(nèi)的一點(diǎn)(稱為種子點(diǎn))賦予給定

18、的顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過(guò)程。 這里所指的區(qū)域是已經(jīng)表示成為點(diǎn)陣形式的象素集合。,2.1 4連通區(qū)域和8連通區(qū)域,取區(qū)域內(nèi)任意兩點(diǎn)，若從其中一點(diǎn)出發(fā)通過(guò)上、下、左、右四中運(yùn)動(dòng)，只經(jīng)過(guò)該區(qū)域內(nèi)的點(diǎn)可到達(dá)另一點(diǎn)時(shí)，則稱該區(qū)域?yàn)?連通區(qū)域； 若將運(yùn)動(dòng)方式增加為水平方向、垂直方向和對(duì)角線方向的八種運(yùn)動(dòng)，仍滿足上述的要求，則該區(qū)域?yàn)?連通區(qū)域；,2.2種子填充的遞歸算法,4連通區(qū)域種子填充的遞歸實(shí)現(xiàn)：,procedure flood-fill-4(x,y) begin if getpixel(framebuffer,x,y) = old-color then begin setpixel

19、(framebuffer,x,y,new-color); flood-fill-4(x,y+1); flood-fill-4(x,y-1); flood-fill-4(x-1,y); flood-fill-4(x+1,y); end end of algorithm;,4連通種子填充的遞歸過(guò)程：,遞歸種子填充算法的性能分析,區(qū)域填充的遞歸算法程序簡(jiǎn)單，表達(dá)清楚。但由于多層遞歸，系統(tǒng)堆棧反復(fù)進(jìn)出，費(fèi)時(shí)費(fèi)內(nèi)存。,上述填充算法是一種深度優(yōu)先搜索算法，采用堆棧實(shí)現(xiàn)。也可以改為廣度優(yōu)先搜索，采用隊(duì)列實(shí)現(xiàn)。,2.3掃描線種子填充算法,基本思想： 首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一段區(qū)段，然后確定與這

20、一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次將它們保存起來(lái)。反復(fù)進(jìn)行這個(gè)過(guò)程，直到所保存的各區(qū)段都填充完畢為止。,28,21,12,27,26,20,19,11,25,18,24,23,17,16,8,3,35,7,2,34,37,39,36,38,41,43,45,40,42,44,22,15,14,10,5,13,9,6,30,29,1,33,32,4,31,掃描線種子填充算法舉例,保存上下掃描線區(qū)段最右側(cè)象素為種子象素,區(qū)域填充的掃描線算法描述,將種子象素點(diǎn)壓入堆棧 while 堆棧非空 do begin 從堆棧中彈出一個(gè)種子象素 沿著掃描線對(duì)種子象素的左右象素進(jìn)行填充，直至遇到

21、邊界 象素為止 標(biāo)志區(qū)間內(nèi)最左和最右象素為xleft 和xright if在xleftxxright中檢查與當(dāng)前掃描線相鄰的上下兩條掃描線全為邊界象素或全為已填充過(guò)的象素 then goto 2 在xleftxxright中標(biāo)記每一個(gè)既不包含邊界象素又不包含已填充過(guò)的象素的區(qū)間 將每一區(qū)間的最右象素作為種子象素壓入堆棧end end of algorithm,2.4 掃描轉(zhuǎn)換和區(qū)域填充的比較,多邊形的掃描轉(zhuǎn)換和區(qū)域填充是兩類典型的面著色問(wèn)題，在一定條件下兩者可以相互轉(zhuǎn)換。但二者的基本思想是不同的。 多邊形的掃描轉(zhuǎn)換是指將多邊形的頂點(diǎn)表示轉(zhuǎn)換成點(diǎn)陣表示，在掃描轉(zhuǎn)換過(guò)程中利用了多邊形各種形式的連貫

22、性； 區(qū)域填充只改變區(qū)域的顏色，不改變區(qū)域的表示方法。在填充過(guò)程中應(yīng)用了區(qū)域的連通性。,3. 光柵圖形的反走樣算法,光柵圖形的走樣現(xiàn)象 光柵圖形的走樣(aliasing)是由于采用離散的量來(lái)表示連續(xù)的量而引起的。線段，多邊形的邊界都是連續(xù)量，而光柵圖形的象素是離散量。因此，用離散的象素表示連續(xù)的線段時(shí)導(dǎo)致光柵圖形走樣，即光滑的線段變成了階梯的形狀。用于減少或消除這種效果的技術(shù)稱為反走樣(antialiasing)。,3.1 反走樣線段和反走樣多邊形,基本思想： 現(xiàn)實(shí)中的線段是有寬度的，應(yīng)把線段看作是狹長(zhǎng)的矩形； 當(dāng)線段通過(guò)某象素時(shí)，可求出兩者相交的面積； 最后根據(jù)相交的面積大小決定該象素的顏色

23、或灰度值；,3.2 提高分辨率的反走樣方法,采用高分辨率的光柵圖形顯示器； 用軟件的方法提高分辨率，采用高分辨率計(jì)算，低分辨率顯示的技術(shù)： 高分辨率計(jì)算指將低分辨的圖形顯示象素劃分為許多子象素，如2*2劃分，3*3劃分等，然后按照通常的算法計(jì)算出各個(gè)子象素的顏色或灰度值； 低分辨率顯示指將一個(gè)象素所對(duì)應(yīng)的各個(gè)子象素的顏色值的加權(quán)平均值(或算術(shù)平均值)作為該象素的顏色值進(jìn)行顯示；,提高分辨率的反走樣方法,把顯示器分辨率提高一倍， 直線經(jīng)過(guò)兩倍的象素，鋸齒也增加一倍， 但同時(shí)每個(gè)階梯的寬度也減小了一倍， 所以顯示出的直線段看起來(lái)就平直光滑了一些。 增加分辨率雖然簡(jiǎn)單，但是是不經(jīng)濟(jì)的方法，有物理上的

24、困難，而且它也只能減輕而不能消除鋸齒問(wèn)題,區(qū)域采樣,每個(gè)象素是一個(gè)具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長(zhǎng)矩形。當(dāng)直線段與象素有交時(shí)，求出兩者相交區(qū)域的面積，然后根據(jù)相交區(qū)域面積的大小確定該象素的亮度值。,有寬度的線條輪廓,象素相交的五種情況及用于計(jì)算面積的量,情況（5)陰影面積為：D2/2m； 情況（4)陰影面積為：D - m/2； 情況陰影面積為：1 - D2/m,對(duì)圓等二次曲線的區(qū)域采樣可以采取適當(dāng)?shù)慕?，并建立查找表?lái)減小計(jì)算復(fù)雜度,二、字符的生成,計(jì)算機(jī)圖形學(xué)中，字符可以用不同的方式表達(dá)和生成。常用的方法有點(diǎn)陣式、矢量式和編碼式。 1、點(diǎn)陣式字符 點(diǎn)陣式字符將字符表示為一

25、個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。常用的點(diǎn)陣大小有57、7 9、88、1616等等。下圖所示的字母“P”的點(diǎn)陣式表示例子。在這種88網(wǎng)格中的字形比較粗糙，但當(dāng)點(diǎn)陣變大時(shí)，字型可以做得非常漂亮。,使用點(diǎn)陣式字符時(shí)，需將字庫(kù)中的矩形點(diǎn)陣拷貝到buffer中指定的單元中去。在拷貝過(guò)程中，可以施加變換，以獲得簡(jiǎn)單的變化。 圖（b）變成粗體字：當(dāng)字符原型中每個(gè)象素被寫(xiě)入幀緩存寄存器的指定位置xi, yi時(shí)，同時(shí)被寫(xiě)入xi+1, yi。 圖（c）旋轉(zhuǎn)90度 ：把字符原型中每個(gè)象素的x, y坐標(biāo)彼此交換，并使y值改變符號(hào)后，再寫(xiě)入幀緩存寄存器的指定位置。 圖（d）斜體字：從底到頂逐行拷貝字符，每

26、隔n行，左移一單元。,由于光柵掃描顯示器的普遍使用，點(diǎn)陣式字符表示已經(jīng)成為一種字符表示的主要形式。從字庫(kù)中讀出原字型，經(jīng)過(guò)變換拷貝到buffer中去的操作，經(jīng)常制成專門(mén)的硬件來(lái)完成。這就大大加快了字符生成的速度。,2、矢量式字符 矢量式字符將字符表達(dá)為一個(gè)點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻劃。圖2.4.2示出用矢量式表示的字符“B”。“B”是由頂點(diǎn)序列a, b, c, d, e, f, e, g, h, I, j, k ,a, l的坐標(biāo)表達(dá)。 調(diào)用矢量式字符的過(guò)程相當(dāng)于輸出一個(gè)polyline。由于矢量式字符具有和圖形相一致的數(shù)據(jù)結(jié)構(gòu)，因而可以接受任何對(duì)于圖形的操作，

27、如放大、旋轉(zhuǎn)，甚至透視。而且，矢量式字符不僅可用于顯示，也可用于繪圖機(jī)輸出。,3、方向編碼式字符 方向編碼式字符用有限的若干種方向編碼來(lái)表達(dá)一個(gè)字符，常用8方向編碼。 8個(gè)方向的編碼分別為07，其中編碼為偶數(shù)和0的固定長(zhǎng)度為1，編碼為奇數(shù)的固定長(zhǎng)度為 。 一個(gè)字符就可以表示為一連串方向碼。下圖為字母“B”的方向矢量構(gòu)成。 “B”可用8方向編碼：000012344400012344440666666來(lái)表示。,優(yōu)點(diǎn)： 方向編碼式字符很容易被填入幀緩存寄存器中予以顯示； 方向編碼所占的空間比較小； 能接受一些特定的變換操作，如按比例在x和y兩個(gè)方向放大或縮小以及以45度角為單位的旋轉(zhuǎn)，但難以進(jìn)行任意

28、角度的旋轉(zhuǎn)。,4、輪廓字型技術(shù) 當(dāng)對(duì)輸出字符的要求較高時(shí)（如排版印刷），需要使用高質(zhì)量的點(diǎn)陣字符。 對(duì)于6763個(gè)基本漢字，假設(shè)每個(gè)漢字是72X72點(diǎn)陣，那么一個(gè)字庫(kù)就需要72X72X6763/8=4.4兆字節(jié)存儲(chǔ)空間； 在實(shí)際使用時(shí)，還需要多種字體（如基本體、宋體、仿宋體、黑體、楷體等），每種字體又需要多種字號(hào)。可見(jiàn)，直接使用點(diǎn)陣字符方法將耗費(fèi)巨大的存儲(chǔ)空間。,因此把每種字體、字號(hào)的字符都存儲(chǔ)一個(gè)對(duì)應(yīng)的點(diǎn)陣，在一般情況是不可行的。,解決方法： 對(duì)字型數(shù)據(jù)壓縮后再存儲(chǔ)，使用時(shí)，將壓縮的數(shù)據(jù)還原為字符位圖點(diǎn)陣。 壓縮方法有多種 黑白段壓縮法：簡(jiǎn)單，還原快，不失真，但壓縮較差，使用起來(lái)也不方便，一

29、般用于低級(jí)的文字處理系統(tǒng)中； 部件壓縮法：壓縮比大，缺點(diǎn)是字型質(zhì)量不能保證； 三是輪廓字型法：壓縮比大，且能保證字符質(zhì)量，是當(dāng)今國(guó)際上最流行的一種方法，基本上也被認(rèn)為是符合工業(yè)標(biāo)準(zhǔn)化的方法。,輪廓字型： 輪廓字型法采用直線、或者二、三次Bezier曲線的集合來(lái)描述一個(gè)字符的輪廓線； 輪廓線構(gòu)成一個(gè)或若干個(gè)封閉的平面區(qū)域； 輪廓線定義加上一些指示橫寬、豎寬、基點(diǎn)、基線等的控制信息，構(gòu)成了字符的壓縮數(shù)據(jù)?？刂菩畔⒂糜诒ＷC字符變倍時(shí)引起的字符筆劃原來(lái)的橫寬/豎寬變大變小時(shí)，其寬度在任何點(diǎn)陣情況下永遠(yuǎn)一致 采用適當(dāng)?shù)膮^(qū)域填充算法，可以從字符的輪廓線定義產(chǎn)生字符的位圖點(diǎn)陣，區(qū)域填充算法可以用硬件實(shí)現(xiàn)，也

30、可以用軟件實(shí)現(xiàn)。,由美國(guó)Apple和Microsoft公司聯(lián)合開(kāi)發(fā)的TrueType字型技術(shù)就是一種輪廓字型技術(shù)，已被用于為Windows中文版生成漢字字庫(kù)； 當(dāng)前占領(lǐng)主要的電子印刷市場(chǎng)的我國(guó)北大方正和華光電子印刷系統(tǒng)，用的字型技術(shù)是漢字字型輪廓矢量法。這種方法能夠準(zhǔn)確地把字符的信息描述下來(lái)，保證了還原的字符質(zhì)量，又對(duì)字型數(shù)據(jù)進(jìn)行了大量的壓縮。調(diào)用字符時(shí)，可以任意地放大、縮小或進(jìn)行花樣變化，基本上能滿足電子印刷中字型質(zhì)量的要求； 輪廓字型技術(shù)有著廣泛的應(yīng)用。到目前為止在印刷行業(yè)中使用最多，隨著Ms-Windows的大量使用，在CAD、圖形學(xué)等領(lǐng)域也將變得越來(lái)越重要。,三、圖形求交,在計(jì)算機(jī)圖形

31、學(xué)中常常會(huì)遇到求交計(jì)算： 在進(jìn)行掃描線區(qū)域填充時(shí)要求線段的交點(diǎn) 許多消隱算法需要進(jìn)行直線和平面多邊形的求交 求交運(yùn)算往往比較復(fù)雜，為了減小計(jì)算量，在進(jìn)行真正的求交計(jì)算之前，往往先用凸包等輔助結(jié)構(gòu)進(jìn)行粗略的比較，排除那些顯然不相交的情形。 求交計(jì)算是CAD系統(tǒng)的重要部分。它的準(zhǔn)確性與效率直接影響CAD系統(tǒng)的可靠性與實(shí)用性。,容差： 在數(shù)學(xué)上兩個(gè)浮點(diǎn)數(shù)可以嚴(yán)格相等 計(jì)算機(jī)表示的浮點(diǎn)數(shù)有誤差，所以當(dāng)兩個(gè)浮點(diǎn)數(shù)的差的絕對(duì)值充分小時(shí)（例如，小于某個(gè)正數(shù) ），就認(rèn)為它們相等 求交運(yùn)算中引進(jìn)容差。當(dāng)兩個(gè)點(diǎn)的坐標(biāo)值充分接近時(shí)，即其距離充分近時(shí)，就被認(rèn)為是重合的點(diǎn) 點(diǎn)可看作半徑為 的球，線可看作半徑為 的圓管，

32、面可看作厚度為2 的薄板 一般取 =10-6或更小的數(shù)。 求交問(wèn)題可以分為求交點(diǎn)和求交線兩類。,1、求交點(diǎn)算法,（1）直線段與直線段的交點(diǎn) 方法一： 假設(shè)二條直線的端點(diǎn)分別為P1，P2，Q1，Q2，則它們可以用向量形式表示為： P(t)=A+Bt (0 t 1) Q(s)=C+Ds (0 s 1) 其中，A=P1，B=P2-P1，C=Q1，D=Q2-Q1。 構(gòu)造方程 A+Bt=C+Ds 對(duì)三維空間中的直線段來(lái)說(shuō)，上述方程實(shí)際上是一個(gè)二元一次方程組，由三個(gè)方程式組成?？梢詮钠渲袃蓚€(gè)解出s, t，再用第三個(gè)驗(yàn)證解的有效性：若第三個(gè)方程成立則說(shuō)明找到了解，否則說(shuō)明兩條直線不相交。當(dāng)所得的解（ti,

33、si）是有效解時(shí)，可用二個(gè)線段方程之一計(jì)算交點(diǎn)坐標(biāo)，例如P(ti)=A+Bti。,方法二： 根據(jù)向量的基本性質(zhì)，直接計(jì)算s與t 。對(duì)方程A+Bt=C+Ds兩邊構(gòu)造點(diǎn)積得： (C D) (A+Bt)=(C D) (C+Ds) 由于C D同時(shí)垂直于C和D，等式右邊為零。故有： 類似地有： 此外還應(yīng)判斷無(wú)解與無(wú)窮多解（共線）的情形，以及考慮數(shù)值計(jì)算誤差造成的影響。,（2）直線段與二次曲線的交點(diǎn) 不失一般性，考慮平面上一條直線與同平面的一條二次曲線的交。 設(shè)曲線方程為： f(x, y)=0, 直線段方程為： (x, y)=(x1+t(x2-x1), y1+t(y2-y1), 則在交點(diǎn)處有 f(x1+t

34、(x2-x1), y1+t(y2-y1)=0 當(dāng)曲線為二次曲線時(shí)，上述方程可寫(xiě)為 at2+bt+c=0 用二次方程求根公式即可解出t值。,（3）圓錐曲線與圓錐曲線的交點(diǎn) 其中一條圓錐曲線用代數(shù)/幾何法表示為隱函數(shù)形式 另一條表示為參數(shù)形式（如二次NURBS曲線） 將參數(shù)形式代入隱函數(shù)形式可得關(guān)于參數(shù)的四次方程，可以使用四次方程的求根公式解出交點(diǎn)參數(shù) 驗(yàn)證交點(diǎn)是否在有效的圓錐曲線段上。,（4）直線段與平面的交點(diǎn) 平面上的點(diǎn)表示為P(u, w)=A+uB+wC，直線段上的點(diǎn)表示為Q(t)=D+tE，二者的交點(diǎn)記為R。假設(shè)線段不平行于平面，則它們交于R=P(u, w)=Q(t)，即 A+uB+wC=

35、D+tE 等式兩邊點(diǎn)乘（B C），得 （B C）（A+uB+wC）=（B C）（D+tE）,由于B C既垂直于B，又垂直于C，故有 （B C）A=（B C）（D+tE） 可解出 類似求得 如果是直線與平面區(qū)域求交點(diǎn)，則要進(jìn)一步判斷點(diǎn)是否在平面上的有效區(qū)域中,（5）圓錐曲線與平面的交點(diǎn) 圓錐曲線與平面求交時(shí)，可以把圓錐曲線表示為參數(shù)形式，并把圓錐曲線的參數(shù)形式代入平面方程，即可得到參數(shù)的二次方程進(jìn)行求解。 （6）圓錐曲線與二次曲面的交點(diǎn) 圓錐曲線與二次曲面求交時(shí)，可把圓錐曲線的參數(shù)形式代入二次曲面的隱式方程，得到參數(shù)的四次方程，用求根公式求解。,2、求交線算法,（1）平面與平面的交線 求平面上兩

36、有界區(qū)域的交線 兩個(gè)平面區(qū)域分別由P(u, w), Q(s, t), u, w, s, t0, 1定義。如果它們不共面而且不分離，則必交于一直線段。這條直線必落在P(u, w)-Q(s, t)=0所定義的無(wú)限直線上。 得到含有四個(gè)未知數(shù)，三個(gè)方程式的方程組，只要分別與八條邊界線方程：u=0, u=1, w=0, w=1, s=0, s=1, t=0, t=1聯(lián)立，即可求出線段的兩個(gè)端點(diǎn)的參數(shù)。 只要找到兩組解，就可以不再對(duì)剩余其它方程組求解。找到的兩組解就是所求的交線段端點(diǎn)參數(shù)。,求平面上兩多邊形的交線： 兩個(gè)多邊形（可能是凸的，也可能是凹的，甚至可能帶有內(nèi)孔）相交時(shí)，可能有多段交線。 兩個(gè)多

37、邊形分別記為A和B，用如下的方法求出它們的交線： （1）把A的所有邊與B求交，求出所有有效交點(diǎn)； （2）把B的所有邊與A求交，求出所有有效交點(diǎn)； （3）把所有交點(diǎn)先按y，再按x的大小進(jìn)行排序； （4）把每對(duì)交點(diǎn)的中點(diǎn)與A和B進(jìn)行包含性檢測(cè)，若該中點(diǎn)即在A中又在B中，則該對(duì)交點(diǎn)定義了一條交線段。,（2）平面與二次曲面的交線 1）代數(shù)法 把二次曲面表示為代數(shù)形式， Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0 通過(guò)平移與旋轉(zhuǎn)坐標(biāo)變換把平面變?yōu)閄OY平面，對(duì)二次曲面進(jìn)行同樣的坐標(biāo)變換 在新坐標(biāo)系下平面的方程為z=0，所以新坐標(biāo)系下二次曲面方程中，把含z項(xiàng)都去掉

38、即為平面與二次曲面的交線方程。對(duì)交線方程進(jìn)行一次逆坐標(biāo)變換即可獲得在原坐標(biāo)系下的交線方程。,交線表示法： 代數(shù)表示：用二元二次方程系數(shù)表示交線，輔之以局部坐標(biāo)系到用戶坐標(biāo)系的變換矩陣。 缺點(diǎn)：每當(dāng)需要使用這些交線時(shí)，都要進(jìn)行坐標(biāo)變換。例如，判斷一個(gè)空間點(diǎn)是否在交線上，必須先對(duì)它進(jìn)行坐標(biāo)變換，變到z=0平面上，再進(jìn)行檢測(cè)。需要繪制該交線時(shí)，也要先在局部坐標(biāo)系下求出點(diǎn)坐標(biāo)，再變換到用戶坐標(biāo)系下的坐標(biāo) 幾何表示：幾何表示存儲(chǔ)曲線的類型（橢圓、拋物線或雙曲線），以及定義參數(shù)（中心點(diǎn)、對(duì)稱軸、半徑等大小尺寸）的數(shù)值信息，使用局部坐標(biāo)系到用戶坐標(biāo)系的變換，把局部坐標(biāo)系下的定義參數(shù)變換到用戶坐標(biāo)系直接使用。

39、 特點(diǎn)：使用較少的變換，但需要用計(jì)算來(lái)判斷曲線的種類，及計(jì)算曲線的定義參數(shù)。由于浮點(diǎn)運(yùn)算的不精確性，容易發(fā)生判錯(cuò)類型以及定義參數(shù)誤差過(guò)大的問(wèn)題。,2）幾何法 當(dāng)平面與二次曲面的交線需要精確表示時(shí)，往往采用幾何法求交。,特點(diǎn)： 準(zhǔn)確性大大優(yōu)于用代數(shù)法計(jì)算分類的方法 不需要對(duì)面進(jìn)行變換，所以只要通過(guò)很少的計(jì)算就可以得到交線的精確描述 存儲(chǔ)的信息是具有幾何意義的，所以判斷相等性、相對(duì)性等問(wèn)題時(shí)，可以確定有幾何意義的容差。,二次曲面采用幾何表示 根據(jù)平面與二次曲面的相對(duì)位置與角度直接判斷交線類型,例子：平面與球求交 平面用一個(gè)記錄p表示，p的兩子域p.b, p.w分別代表平面上一點(diǎn)與平面法向量。球面用

40、記錄s表示。它的兩個(gè)子域s.c, s.r分別代表球面中心和半徑。則可寫(xiě)出平面與球面相交的算法如下：,plane_sphere_intersect(p, s) plane p; sphere s; d=球面中心到平面的有向距離； if(abs(d)=s.r) 二個(gè)面相交于一（切）點(diǎn)s.c-d * p.w; else if (abs(d)s.r) 兩個(gè)面無(wú)交； else 所求交線是圓。其圓心，半徑，圓所在平面法向量為 c=s.c-d * p. w; r=sqr t(s.r2-d2); w=p.w; ,一個(gè)平面與一個(gè)圓柱面可以無(wú)交、交于一條直線（切線）、二條直線、一個(gè)橢圓或一個(gè)圓，可以用兩個(gè)面的定義

41、參數(shù)求出它們的相對(duì)位置關(guān)系和相對(duì)角度關(guān)系，進(jìn)而判斷其交屬于何種情況，并求出交線的定義參數(shù) 平面與圓錐的交線也可類似求解。,（3）平面與參數(shù)曲面的交線 方法一： 把參數(shù)曲面的表示（x(s,t), y(s,t), z(s,t)）代入平面方程 ax+by+cz+d=0 得到用參數(shù)曲面的參數(shù)s、t表示的交線方程 ax(s,t)+by(s,t)+cz(s,t)+d=0 方法二： 是用平移和旋轉(zhuǎn)變換對(duì)平面進(jìn)行坐標(biāo)變換，使平面成為新坐標(biāo)系下的xoy平面。再用相同的變換應(yīng)用于參數(shù)曲面方程得到參數(shù)曲面在新坐標(biāo)系下的方程 （x*, y*, z*）=（x*(s,t), y*(s,t), z*(s,t)） 由此得交線

42、在新坐標(biāo)系下的方程為 z*(s, t)=0,四、包含判定,在進(jìn)行圖形求交時(shí)，常常需要判定兩個(gè)圖形間是否有包含關(guān)系。如點(diǎn)是否包含在線段、平面區(qū)域、三維形體中，線段是否包含在平面區(qū)域、三維形體中，等等。 許多包含判定問(wèn)題可轉(zhuǎn)化為點(diǎn)的包含判定問(wèn)題，如判斷線段是否在平面上可以轉(zhuǎn)化為判斷其兩端點(diǎn)是否在平面上。因此主要討論關(guān)于點(diǎn)的包含判定算法。,判斷點(diǎn)與線段的包含關(guān)系，也就是判斷點(diǎn)與線的最短距離是否位于容差范圍內(nèi)。造型中常用的線段有三種： （1）直線段 （2）圓錐曲線段（主要是圓?。?（3）參數(shù)曲線（主要是Bezier，樣條曲線）。 點(diǎn)與面的包含判定也類似地分為三種情況。,（1）點(diǎn)與直線段的包含判定 假設(shè)

43、點(diǎn)坐標(biāo)為P(x, y, z)，直線段端點(diǎn)為P1(x1, y1, z1)，P2(x2,y2,z2)，則點(diǎn)P到線段P1P2的距離的平方為 d2=(x-x1)2+(y-y1)2+(z-z1)2-(x2-x1)(x-x1)+(y2-y1)(y-y1)+(z2-z1)(z-z1)2/(x2-x1)2+(y2-y1)2+(z2-z1)2 當(dāng)d22時(shí)，判定點(diǎn)在線段（或其延長(zhǎng)線）上，這時(shí)還需進(jìn)一步判斷點(diǎn)是否落在直線段的有效區(qū)間內(nèi) 比較坐標(biāo)分量，假設(shè)線段兩端點(diǎn)的x分量不等（否則所有分量均相等，那么線段兩端點(diǎn)重合，線段退化為一點(diǎn)），那么當(dāng)x-x1與x-x2反號(hào)時(shí)，點(diǎn)P在線段的有效區(qū)間內(nèi)。,（2）點(diǎn)與圓錐曲線段的包

44、含判定 以圓弧為例，假設(shè)點(diǎn)的坐標(biāo)為(x, y, z)，圓弧的中心為(x0,y0,z0)，半徑為r，起始角1，終止角2 (相對(duì)局部坐標(biāo)系x軸)。 圓弧所在平面為 ax+by+cz+d=0 先判斷點(diǎn)是否在該平面上，若不在，則點(diǎn)不可能被包含。若在，則通過(guò)坐標(biāo)變換，把問(wèn)題轉(zhuǎn)換到二維的問(wèn)題。 給定中心為（x0, y0），半徑為r，起始角1 ，終止角2的圓弧，對(duì)平面上一點(diǎn)P(x, y)，判斷P是否在圓弧上，可分二步進(jìn)行: 第一步：判斷P是否在圓心為（x0, y0），半徑為r的圓的圓周上，即下式是否成立： 第二步：判斷P是否在有效的圓弧段內(nèi)。,（3）點(diǎn)與參數(shù)曲線的包含判定 設(shè)點(diǎn)坐標(biāo)為P(x, y, z)，參

45、數(shù)曲線為Q(t)=(x(t), y(t), z(t)。點(diǎn)和參數(shù)曲線的求交計(jì)算包括三個(gè)步驟： （1）計(jì)算參數(shù)t值，使P到Q(t)的距離最小，即最小化 R(t)=(P-Q(t)(P-Q(t)=|P-Q(t)|2 （2）判斷t是否在有效參數(shù)區(qū)間內(nèi)（通常為0，1）； （3）判斷Q(t)與P的距離是否小于 。,（4）點(diǎn)與平面區(qū)域的包含判定 設(shè)點(diǎn)坐標(biāo)為P(x, y, z)，平面方程為ax+by+cz+d=0。則點(diǎn)到平面的距離為 d= 若d ，則認(rèn)為點(diǎn)在平面上，否則認(rèn)為點(diǎn)不在平面上。,在造型系統(tǒng)中，通常使用平面上的有界區(qū)域作為形體的表面。在這種情況下，對(duì)落在平面上的點(diǎn)還應(yīng)進(jìn)一步判別它是否落在有效區(qū)域內(nèi)。若點(diǎn)

46、落在該區(qū)域內(nèi)，則認(rèn)為點(diǎn)與該面相交，否則不相交。,判斷平面上一個(gè)點(diǎn)是否包含在同平面的一個(gè)多邊形內(nèi)，有許多種算法，常用的方法有：叉積判斷法、夾角之和檢驗(yàn)法以及交點(diǎn)計(jì)數(shù)檢驗(yàn)法。,1）叉積判斷法 假設(shè)判斷點(diǎn)為P0。多邊形頂點(diǎn)按順序排列為P1P2Pn。如圖所示。令Vi=Pi-P0, i=1, 2, , n, Vn+1=V1， 那么，P0在多邊形內(nèi)的充要條件是叉積ViVi+1(i=1, 2, , n)的符號(hào)相同 叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為凹時(shí)，盡管點(diǎn)在多邊形內(nèi)也不能保證上述叉積符號(hào)都相同。這時(shí)可采用其他方法。,2）夾角之和檢驗(yàn)法 假設(shè)某平面上有點(diǎn)P0和多邊形P1P2P3P4P5，將點(diǎn)P0分別與Pi相連，構(gòu)成向量Vi=Pi-P0 假設(shè)角 PiP0Pi+1=ai。如果 ，則點(diǎn)P0在多邊形之外，如圖2.5.3(a)所示。 如果 ，則點(diǎn)P0在多邊形之內(nèi)，如圖2.5.3(b)所示。 ai可通過(guò)下列公式計(jì)算：令Si=Vi Vi+1, Ci=ViVi+1，