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

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

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

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

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

5、包圍矩形外的點(diǎn)肯定是多邊形的外部點(diǎn)； （2）交點(diǎn)計數(shù)的特殊情況處理,線段和多邊形相交在頂點(diǎn)（奇點(diǎn)的處理）： 當(dāng)線段與多邊形P的交點(diǎn)是P的頂點(diǎn)Pi 時，則稱該交點(diǎn)為奇點(diǎn); 為了保證線段和多邊形P邊界的交點(diǎn)個數(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)時，該點(diǎn)按照兩個交點(diǎn)計算；否則按照一個交點(diǎn)計算。,線段和多邊形邊共線：線段與多邊形相交二次；,算法實現(xiàn),現(xiàn)設(shè)P=P0P1PnP0為一給定的多邊形。Framebuffer(x,y)是與點(diǎn)(x,y)相對應(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)判斷的算法雖然程序簡單，但是不可取。原因是速度太慢，該算法割斷了各個象素之間的聯(lián)系，孤立的考察各個象素和多邊形P的內(nèi)外關(guān)系，使得幾十萬甚至幾百萬個象素都要一一判別，每次判別都要多次求交點(diǎn)，需要做大量的乘除運(yùn)算，花費(fèi)大量的時間。,1.3 掃描線算法,掃描線算法是多邊形掃描轉(zhuǎn)換的

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

8、中任一梯形內(nèi)一點(diǎn)關(guān)于多邊形P的內(nèi)外關(guān)系后，整個梯形內(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 時，則稱該交點(diǎn)為奇點(diǎn); 為了保證掃描線和多邊形P邊界的交點(diǎn)個數(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)時，該點(diǎn)按照兩個交點(diǎn)計算；否則按照一個交點(diǎn)計算。,掃描線和多邊形邊共線：線段與多邊形相交二次；,掃描線算法的實現(xiàn),算法的基本思想： 利用多邊形的邊的連貫性和掃描線的連貫性，對于一個給定的多邊形，用一組水平(垂直)的掃描線進(jìn)行掃描 對每一條掃描線均可求出

10、與多邊形邊的交點(diǎn) 交點(diǎn)將掃描線分割成落在多邊形內(nèi)部的線段和落在多邊形外部的線段，并且二者相間排列 將落在多邊形內(nèi)部的線段上的所有象素點(diǎn)賦以給定的色彩值。,掃描線算法的實現(xiàn)原理,根據(jù)多邊形內(nèi)部點(diǎn)的連續(xù)性知：一條掃描線與多邊形的交點(diǎn)中，入點(diǎn)和出點(diǎn)之間所有點(diǎn)都是多邊形的內(nèi)部點(diǎn)。所以，對所有的掃描線填充入點(diǎn)到出點(diǎn)之間所有的點(diǎn)就可填充多邊形。 判斷掃描線上的點(diǎn)是否在多邊形之內(nèi)根據(jù)多邊形區(qū)域連續(xù)性，分為3個步驟： 求出掃描線與多邊形所有邊的交點(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)，然后對交點(diǎn)2與

11、4之間、9與13之間的所有象素點(diǎn)進(jìn)行填充。,掃描線算法的實現(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,掃描線算法的實現(xiàn)步驟,對于一條掃描線填充過程可以分為四個步驟： 求交 排序 配對 填色,掃描線算法的數(shù)據(jù)結(jié)構(gòu),邊的活化鏈表(AET)：把與當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個

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

13、交點(diǎn)前后次序，在每對奇偶交點(diǎn)間的x段予以填充 if 掃描線 y=ymaxthen 從AEL表中刪除這些邊 對在AEL表中的其他邊，計算與下一條掃描線的交點(diǎn)：x=x+1/m 計算下一條掃描線：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ù)雜，對各種表的維護(hù)和排序的耗費(fèi)很大； 但是由于它充分利用的多邊形的區(qū)域、掃描線和邊的三種形式的連貫性，從而避免了反復(fù)求交點(diǎn)的大量運(yùn)算，因此速度比逐點(diǎn)判斷法快的多。,1.4 邊緣填充算法,基本思想： 在光柵圖形中，如果某區(qū)域已經(jīng)著上了為M的某

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

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

16、色。,邊界標(biāo)志算法實現(xiàn)步驟,步驟1：以值為boundary-color的特殊顏色勾畫多邊形P的邊界?？刹捎孟鄳?yīng)的直線生成算法； 步驟2：逐條掃描線對多邊形著色。先將掃描線上值為boundary-color的特殊象素點(diǎn)依x坐標(biāo)遞增順序兩兩配對，再將中間的象素著上相應(yīng)的顏色；,邊界標(biāo)志算法類語言描述,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)志算法性能分析,和邊界填充算法相比，本算法避免了對幀緩沖器中的大量元素的多次賦值，但是需要逐條掃描線的對幀緩沖器中的元素進(jìn)行搜索和比較。當(dāng)用軟件實現(xiàn)本算法時，速度與掃描線算法相當(dāng)。本算法適合于硬件實現(xiàn)，硬件實現(xiàn)時的速度則有很大的提高。,2. 多邊形的種子填充,種子填充是指先將區(qū)域內(nèi)的一點(diǎn)(稱為種子點(diǎn))賦予給定

18、的顏色，然后將這種顏色擴(kuò)展到整個區(qū)域內(nèi)的過程。 這里所指的區(qū)域是已經(jīng)表示成為點(diǎn)陣形式的象素集合。,2.1 4連通區(qū)域和8連通區(qū)域,取區(qū)域內(nèi)任意兩點(diǎn)，若從其中一點(diǎn)出發(fā)通過上、下、左、右四中運(yùn)動，只經(jīng)過該區(qū)域內(nèi)的點(diǎn)可到達(dá)另一點(diǎn)時，則稱該區(qū)域為4連通區(qū)域； 若將運(yùn)動方式增加為水平方向、垂直方向和對角線方向的八種運(yùn)動，仍滿足上述的要求，則該區(qū)域為8連通區(qū)域；,2.2種子填充的遞歸算法,4連通區(qū)域種子填充的遞歸實現(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連通種子填充的遞歸過程：,遞歸種子填充算法的性能分析,區(qū)域填充的遞歸算法程序簡單，表達(dá)清楚。但由于多層遞歸，系統(tǒng)堆棧反復(fù)進(jìn)出，費(fèi)時費(fèi)內(nèi)存。,上述填充算法是一種深度優(yōu)先搜索算法，采用堆棧實現(xiàn)。也可以改為廣度優(yōu)先搜索，采用隊列實現(xiàn)。,2.3掃描線種子填充算法,基本思想： 首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一段區(qū)段，然后確定與這

20、一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次將它們保存起來。反復(fù)進(jìn)行這個過程，直到所保存的各區(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 從堆棧中彈出一個種子象素 沿著掃描線對種子象素的左右象素進(jìn)行填充，直至遇到

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

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

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

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

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

26、隔n行，左移一單元。,由于光柵掃描顯示器的普遍使用，點(diǎn)陣式字符表示已經(jīng)成為一種字符表示的主要形式。從字庫中讀出原字型，經(jīng)過變換拷貝到buffer中去的操作，經(jīng)常制成專門的硬件來完成。這就大大加快了字符生成的速度。,2、矢量式字符 矢量式字符將字符表達(dá)為一個點(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)用矢量式字符的過程相當(dāng)于輸出一個polyline。由于矢量式字符具有和圖形相一致的數(shù)據(jù)結(jié)構(gòu)，因而可以接受任何對于圖形的操作，

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

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

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

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

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

32、面可看作厚度為2 的薄板 一般取 =10-6或更小的數(shù)。 求交問題可以分為求交點(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 對三維空間中的直線段來說，上述方程實際上是一個二元一次方程組，由三個方程式組成。可以從其中兩個解出s, t，再用第三個驗證解的有效性：若第三個方程成立則說明找到了解，否則說明兩條直線不相交。當(dāng)所得的解（ti,

33、si）是有效解時，可用二個線段方程之一計算交點(diǎn)坐標(biāo)，例如P(ti)=A+Bti。,方法二： 根據(jù)向量的基本性質(zhì)，直接計算s與t 。對方程A+Bt=C+Ds兩邊構(gòu)造點(diǎn)積得： (C D) (A+Bt)=(C D) (C+Ds) 由于C D同時垂直于C和D，等式右邊為零。故有： 類似地有： 此外還應(yīng)判斷無解與無窮多解（共線）的情形，以及考慮數(shù)值計算誤差造成的影響。,（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)曲線為二次曲線時，上述方程可寫為 at2+bt+c=0 用二次方程求根公式即可解出t值。,（3）圓錐曲線與圓錐曲線的交點(diǎn) 其中一條圓錐曲線用代數(shù)/幾何法表示為隱函數(shù)形式 另一條表示為參數(shù)形式（如二次NURBS曲線） 將參數(shù)形式代入隱函數(shù)形式可得關(guān)于參數(shù)的四次方程，可以使用四次方程的求根公式解出交點(diǎn)參數(shù) 驗證交點(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ù)的二次方程進(jìn)行求解。 （6）圓錐曲線與二次曲面的交點(diǎn) 圓錐曲線與二次曲面求交時，可把圓錐曲線的參數(shù)形式代入二次曲面的隱式方程，得到參數(shù)的四次方程，用求根公式求解。,2、求交線算法,（1）平面與平面的交線 求平面上兩

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

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

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

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

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

41、參數(shù)求出它們的相對位置關(guān)系和相對角度關(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)變換對平面進(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)行圖形求交時，常常需要判定兩個圖形間是否有包含關(guān)系。如點(diǎn)是否包含在線段、平面區(qū)域、三維形體中，線段是否包含在平面區(qū)域、三維形體中，等等。 許多包含判定問題可轉(zhuǎn)化為點(diǎ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時，判定點(diǎn)在線段（或其延長線）上，這時還需進(jìn)一步判斷點(diǎn)是否落在直線段的有效區(qū)間內(nèi) 比較坐標(biāo)分量，假設(shè)線段兩端點(diǎn)的x分量不等（否則所有分量均相等，那么線段兩端點(diǎn)重合，線段退化為一點(diǎn)），那么當(dāng)x-x1與x-x2反號時，點(diǎn)P在線段的有效區(qū)間內(nèi)。,（2）點(diǎn)與圓錐曲線段的包

44、含判定 以圓弧為例，假設(shè)點(diǎn)的坐標(biāo)為(x, y, z)，圓弧的中心為(x0,y0,z0)，半徑為r，起始角1，終止角2 (相對局部坐標(biāo)系x軸)。 圓弧所在平面為 ax+by+cz+d=0 先判斷點(diǎn)是否在該平面上，若不在，則點(diǎn)不可能被包含。若在，則通過坐標(biāo)變換，把問題轉(zhuǎn)換到二維的問題。 給定中心為（x0, y0），半徑為r，起始角1 ，終止角2的圓弧，對平面上一點(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ù)曲線的求交計算包括三個步驟： （1）計算參數(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ū)域作為形體的表面。在這種情況下，對落在平面上的點(diǎn)還應(yīng)進(jìn)一步判別它是否落在有效區(qū)域內(nèi)。若點(diǎn)

46、落在該區(qū)域內(nèi)，則認(rèn)為點(diǎn)與該面相交，否則不相交。,判斷平面上一個點(diǎn)是否包含在同平面的一個多邊形內(nèi)，有許多種算法，常用的方法有：叉積判斷法、夾角之和檢驗法以及交點(diǎn)計數(shù)檢驗法。,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)的符號相同 叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為凹時，盡管點(diǎn)在多邊形內(nèi)也不能保證上述叉積符號都相同。這時可采用其他方法。,2）夾角之和檢驗法 假設(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可通過下列公式計算：令Si=Vi Vi+1, Ci=ViVi+1，