第四講二維圖形填充

第四講二維圖形填充2023/6/5第一頁(yè)，共三十一頁(yè)，編輯于2023年，星期一內(nèi)容摘要字符矢量字符點(diǎn)陣字符字型技術(shù)字符裁剪反走樣基礎(chǔ)提高分辯率簡(jiǎn)單的區(qū)域反走樣算法卷積積分與反走樣算法半色調(diào)技術(shù)第二頁(yè)，共三十一頁(yè)，編輯于2023年，星期一內(nèi)容摘要區(qū)域填充有序邊表算法邊填充算法邊標(biāo)志算法種子填充算法圓域的填充線寬與線型的處理直線線寬的處理（筆型：線、方形）圓弧線寬的處理（筆型：線、方形）線型的處理第三頁(yè)，共三十一頁(yè)，編輯于2023年，星期一有序邊表算法一般多邊形的填充過(guò)程，對(duì)于一條掃描線Y值，可以分為四個(gè)步驟：求交點(diǎn)X：計(jì)算掃描線與多邊形各邊的交點(diǎn)X的值；排序：把所有相交點(diǎn)x按遞增順序進(jìn)行排序；交點(diǎn)配對(duì)：第一個(gè)與第二個(gè)，第三個(gè)與第四個(gè)等等。每對(duì)交點(diǎn)就代表掃描線與多邊形的一個(gè)相交區(qū)間；區(qū)間填色：把這些相交區(qū)間內(nèi)的象素置成多邊形色，把相交區(qū)間外的象素置成背景色。特殊頂點(diǎn)處理:P1、P3情況:相同交點(diǎn)取1個(gè);P2、P5情況:相同交點(diǎn)取2個(gè);P4、P6情況:相同交點(diǎn)取0個(gè);(下閉上開原則，防止填充擴(kuò)大化)第四頁(yè)，共三十一頁(yè)，編輯于2023年，星期一填充擴(kuò)大化問(wèn)題的解決采用下閉上開、左閉右開原則，防止填充擴(kuò)大化。例如填充左下角為（1，1），右上角為（3，3）的區(qū)域，得到的圖形如圖所示九個(gè)象素被點(diǎn)亮，而實(shí)際區(qū)域應(yīng)是黃區(qū)所示。采取的措施：在具體實(shí)現(xiàn)時(shí)，只要對(duì)掃描線與多邊形的相交區(qū)間取“左閉右開”。在上述討論中，當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，所使用的交點(diǎn)取舍的方法，保證了多邊形的“下閉上開”，丟棄上方水平邊以及上方非水平邊上作為局部最高點(diǎn)的頂點(diǎn)。第五頁(yè)，共三十一頁(yè)，編輯于2023年，星期一如左圖活性邊與活性邊表處理方法一個(gè)多邊形與若干掃描線。為了計(jì)算每條掃描線與多邊形各邊的交點(diǎn)，最簡(jiǎn)單的方法是把多邊形的所有邊放在一個(gè)表中。在處理每條掃描線時(shí)，按順序從表中取出所有的邊，分別與掃描線求交點(diǎn)。這樣處理效率很低。這是因?yàn)橐粭l掃描線往往只與少數(shù)幾條邊相交，甚至與整個(gè)多邊形都不相交。若在處理每條掃描線時(shí)，不分青紅皂白地把所有邊都拿來(lái)與掃描線求交點(diǎn)，則其中絕大多數(shù)都是徒勞無(wú)用的。如果采用活性邊表，則可減少許多計(jì)算。掃描線依次變化為1,2,3,4,5,6,7,8,…...x是邊與當(dāng)前掃描線的交點(diǎn)；x是該邊從當(dāng)前掃描線到下一掃描線之間x增量；ymax是邊所交的最高掃描線號(hào)。在上述的交點(diǎn)x坐標(biāo)更新和新邊插入之前，必須把那些與當(dāng)前掃描線相交，而與下一條掃描線不再相交的邊，從活性邊表(AET)中刪除出去。第六頁(yè)，共三十一頁(yè)，編輯于2023年，星期一新邊表處理方法為了方便活性邊表的建立與更新，為每一條掃描線建立一個(gè)新邊表，在該掃描線第一次出現(xiàn)的邊保留與此。也就是說(shuō)若某邊的較低端點(diǎn)為ymin，則該邊就放在掃描線ymin的新邊表中。這樣，當(dāng)按掃描線號(hào)從小到大順序處理掃描線時(shí)，該邊在該掃描線第一次出現(xiàn)。新邊表的每個(gè)結(jié)點(diǎn)存放對(duì)應(yīng)邊的初始信息，比如該掃描線與該邊的初始交點(diǎn)x（即較低端點(diǎn)的x值），x的增量x，以及該邊的最大y值ymax。圖3-18所示，為左圖中各掃描線的新邊表。區(qū)間填充需設(shè)置一個(gè)布爾變量b,在多邊形內(nèi)b為真,,在多邊形外b為假,,b的初值為假。當(dāng)指針從活性邊表中第一個(gè)結(jié)點(diǎn)（交點(diǎn)）到最后一個(gè)結(jié)點(diǎn)遍歷一次時(shí)，每訪問(wèn)一個(gè)結(jié)點(diǎn)，把b取反一次。若b為真，則把從當(dāng)前結(jié)點(diǎn)的x值開始到下一結(jié)點(diǎn)的x值結(jié)束的左閉右開區(qū)間，用多邊形色填充。利用區(qū)間連貫性，即同一區(qū)間上的象素取同一顏色屬性。多邊形外的點(diǎn)用背景色填充。第七頁(yè)，共三十一頁(yè)，編輯于2023年，星期一邊填充算法基本思想：對(duì)于每一條掃描線和每一條多邊形邊的交點(diǎn)(xi，yi)，將該掃描線上交點(diǎn)右方的所有象素取補(bǔ)。對(duì)多邊形的每條邊均作此處理，多邊形的順序隨意。右圖為采用最簡(jiǎn)單的邊填充算法填充一個(gè)多邊形的示意圖。邊填充算法最適用于具有幀緩沖存儲(chǔ)器的圖形系統(tǒng)，按任意順序處理的邊。在處理每條邊時(shí)，僅訪問(wèn)與該邊相交的掃描線上交點(diǎn)右方的象素。當(dāng)所有的邊都被處理之后，按掃描線順序讀出幀緩沖存儲(chǔ)器的內(nèi)容，送入顯示設(shè)備?？梢姳舅惴ǖ膬?yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是對(duì)于復(fù)雜圖形，每一象素可能被訪問(wèn)多次，輸入／輸出的量比有序邊表算法大得多。為了減少邊填充算法訪問(wèn)象素的次數(shù)，可引入柵欄。所謂柵欄指的是一條與掃描線垂直的直線，柵欄位置通常取過(guò)多邊形頂點(diǎn)、且把多邊形分為左右兩半。第八頁(yè)，共三十一頁(yè)，編輯于2023年，星期一柵欄填充算法基本思想是：當(dāng)掃描線與多邊形邊有交點(diǎn)，就將交點(diǎn)與柵欄之間的象素取補(bǔ)。若交點(diǎn)位于柵欄左邊，則將交點(diǎn)之右，柵欄之左的所有象素取補(bǔ)；若交點(diǎn)位于柵欄右邊，則將柵欄之右，交點(diǎn)之左的象素取補(bǔ)。如圖所示，為采用柵欄填充算法填充多邊形的示意圖。柵欄填充算法只是減少了被重復(fù)訪問(wèn)的象素的數(shù)目，但仍有一些象素會(huì)被重復(fù)訪問(wèn)。從圖中很容易看出這一點(diǎn)。下面介紹的邊標(biāo)志算法進(jìn)一步改進(jìn)了柵欄填充算法，使得算法對(duì)每個(gè)象素僅訪問(wèn)一次。算法示意圖如下頁(yè)所示。第九頁(yè)，共三十一頁(yè)，編輯于2023年，星期一邊標(biāo)志算法基本思想是：分為兩步驟，第一步，對(duì)多邊形的每條邊進(jìn)行直線掃描變換，亦即對(duì)多邊形邊界所經(jīng)過(guò)的象素打上標(biāo)志；第二步，填充。對(duì)每條與多邊形相交的掃描線，依從左到右順序，逐個(gè)訪問(wèn)該掃描線上象素。使用一個(gè)布爾量inside來(lái)指示當(dāng)前點(diǎn)的狀態(tài)，若點(diǎn)在多邊形內(nèi)，則inside為真。若點(diǎn)在多邊形外，則inside為假。inside的初始值為假，每當(dāng)訪問(wèn)到象素為被打上邊標(biāo)志的點(diǎn)時(shí)，就把inside取反。對(duì)未打標(biāo)志的象素，inside不變。若訪問(wèn)象素時(shí)，inside為真，則把該象素置為多邊形色。用軟件實(shí)現(xiàn)時(shí)，有序邊表算法與邊標(biāo)志算法的執(zhí)行速度幾乎相同，但由于在幀緩沖存儲(chǔ)器中應(yīng)用邊標(biāo)志算法時(shí)，不必建立、維護(hù)邊表以及對(duì)它進(jìn)行排序，所以邊標(biāo)志算法更適合于硬件實(shí)現(xiàn)，這時(shí)它的執(zhí)行速度比有序邊表算法快到一至兩個(gè)數(shù)量級(jí)。第十頁(yè)，共三十一頁(yè)，編輯于2023年，星期一種子填充算法的連通區(qū)域基本思想是前面討論的填充算法都是按掃描線的順序進(jìn)行象素點(diǎn)的填充的，種子填充算法是根據(jù)已知的一個(gè)多邊形區(qū)域內(nèi)部的一個(gè)象素點(diǎn)來(lái)找到區(qū)域內(nèi)其它的象素點(diǎn)進(jìn)行填充的。前面討論的填充算法都是按掃描線的順序進(jìn)行象素點(diǎn)的填充的，種子填充算法是根據(jù)已知的一個(gè)多邊形區(qū)域內(nèi)部的一個(gè)象素點(diǎn)來(lái)找到區(qū)域內(nèi)其它的象素點(diǎn)進(jìn)行填充的。一般都采用邊界定義區(qū)域，即邊界區(qū)域上所有象素被置為特定值，而區(qū)域內(nèi)部所有的象素均不取這個(gè)值。區(qū)域可以分為四連通或八連通兩種，如果區(qū)域是四連通的，那么區(qū)域內(nèi)每一個(gè)象素可以通過(guò)四個(gè)方向（上、下、左、右）組合到達(dá)，而對(duì)八連通區(qū)域，區(qū)域內(nèi)的每個(gè)象素可通過(guò)上、下、左、右以及四個(gè)對(duì)角線方向的移動(dòng)組合到達(dá)。八連通算法可以填充四連通區(qū)域，而四連通算法不能填充八連通區(qū)域。兩類連通區(qū)域如圖所示。圖(b)中八連通區(qū)域的子區(qū)域是四連通的，然而從一個(gè)子區(qū)域到另一個(gè)子區(qū)域需用八連通算法，若每個(gè)子區(qū)域看成是分離的二個(gè)四連通區(qū)域，并且每個(gè)區(qū)域填上不同的色彩值，如果用八連通算法會(huì)讓兩個(gè)區(qū)域均被錯(cuò)誤地填上同樣的色彩。下面僅討論四向連通算法,只要把搜索方向從四個(gè)該為八個(gè),即可得到八向算法。第十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期一簡(jiǎn)單種子填充算法簡(jiǎn)單的種子填充算法如下：(1)將種子象素壓入棧中；(2)當(dāng)棧非空時(shí)從棧中彈出一個(gè)象素；將該象素置成所要求的色彩值；檢查每個(gè)與當(dāng)前象素鄰接的四連通象素是否是邊界色或已置成所要求的色彩值，若是則返回(2)，否則將該象素壓入棧中回到(2)。[例]簡(jiǎn)單的種子填充算法。多邊形由頂點(diǎn)P0、P1、P2、P3、P4構(gòu)成，見圖3-23。P0（1，5）、P1(5，5)、P2(7，3)、P3(7，1)、P4(1，1)，可設(shè)種子點(diǎn)為(3，3)；四連通的組合方向是上、下、左、右。初始時(shí)棧中只有(3，3)象素；彈出(3，3)，由于該象素未置成色彩值且也不是邊界色，故填色彩值；同時(shí)將(3，4)(3，2)(2，3)及(4，3)壓入棧中；棧中有四個(gè)元素；彈出(4，3)并置上要求的色彩值，再將(4，4)(4，2)(5，3)壓入棧中；棧中有6個(gè)元素；依次類推，象素被選中并填充的次序如圖中箭頭所示。當(dāng)棧為空時(shí)，算法終止。分析該算法不難發(fā)現(xiàn)，在進(jìn)行填充過(guò)程中堆棧會(huì)變得很大，而且在堆棧中還常常包含有一些重復(fù)的和不必要的信息。為此提出了掃描線種子填充算法。(3,3)彈出(3,3)(4,3)(2,3)(3,2)(3,4)彈出(4,3)(2,3)(3,2)(3,4)

(5,3)(4,2)(4,4)(2,3)(3,2)(3,4)

彈出(5,3)(4,2)(4,4)(2,3)(3,2)(3,4)(6,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(6,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(6,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(6,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(5,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(5,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(4,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(4,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(3,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(3,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(2,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(2,2)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(2,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(2,3)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(2,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(2,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(3,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(3,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(4,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(4,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)(5,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)彈出(5,4)(5,2)(5,4)(4,2)(4,4)(2,3)(3,2)(3,4)第十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期一掃描線種子填充算法所謂掃描線種子填充算法，是在任意不間斷掃描線區(qū)間中只取一個(gè)種子象素。不間斷區(qū)間即指在一條掃描線上一組相鄰的元素。算法可分為以下幾步：1）從包含種子象素的棧中彈出種子象素；2）沿著掃描線對(duì)種子象素進(jìn)行填充，直到遇到邊界象素為止，這樣就填充了種子所在的掃描線中的元素；3）區(qū)間內(nèi)最左、最右元素為Xleft，Xright;則在XleftXXright區(qū)間中檢查與當(dāng)前掃描線相鄰的上、下兩條掃描線是否全為邊界象素或已填充過(guò)的象素。若不是，則對(duì)于XleftXXrigh，把與當(dāng)前掃描線相鄰的上、下兩條掃描線中該區(qū)間的最右象素作為種子壓入棧中。算法結(jié)束條件為棧空。此算法適用于用邊界定義的區(qū)域。第十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期一圓域的填充上面所討論的多邊形區(qū)域的填充原理也可以推廣到圓域的填充。對(duì)每條掃描線，先計(jì)算它與圓域的相交區(qū)間，再把區(qū)間內(nèi)象素用指定顏色填充。第十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期一在實(shí)際應(yīng)用中，除了使用單象素寬的線條，還經(jīng)常使用指定線寬和線型的直線與弧線。欲產(chǎn)生具有寬度的線，可以順著掃描所生成的單象素線條軌跡，移動(dòng)一把具有一定寬度的“刷子”來(lái)獲得?！八⒆印钡男螤羁梢允且粭l線段或一個(gè)正方形。也可以采用區(qū)域填充的辦法間接地產(chǎn)生有寬度的線。假設(shè)直線斜率在[－1，1]之間，這里可以把刷子置成垂直方向，刷子的中點(diǎn)對(duì)準(zhǔn)直線一端點(diǎn)，然后讓刷子中心往直線的另一端移動(dòng)，即可“刷出“具有一定寬度的線。當(dāng)直線斜率不在[－1，1]之間時(shí)，把刷子置成水平方向。具體實(shí)現(xiàn)線刷子時(shí)，只要對(duì)直線掃描變換算法的內(nèi)循環(huán)稍作修改即可。例如，當(dāng)直線斜率在[－1，1]之間時(shí)，把每步迭代所得的點(diǎn)的上下方半線寬之內(nèi)的象素全部置成直線顏色。如右上圖所示為線寬是5個(gè)象素的情形。線刷子的優(yōu)點(diǎn)是算法簡(jiǎn)單、效率高。但是，線的始末端總是水平或垂直的。因此，當(dāng)線寬較大時(shí)，看起來(lái)很不自然。當(dāng)比較接近水平的線與比較接近垂直的線匯合時(shí)，匯合處外角將有缺口,如左上圖所示。斜線與水平（或垂直）線不一樣粗。對(duì)于水平線或垂直線，刷子與線條垂直，因而最粗。其粗細(xì)與指定線寬相等。而對(duì)于45斜線，刷子與線條成45角，粗細(xì)僅為指定線寬的1/20.7倍。直線線寬的處理

線刷子原理第十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期一為用正方形刷子繪制的具有寬度的線條。用方形刷子所得的線條比用線刷子所繪制的線條要粗一些。與線刷子類似，用方刷子繪制的線條始末端也是水平或垂直的，且線寬與線條方向有關(guān)。與線刷子的情形相反，對(duì)于水平線與垂直線，線寬最小，而對(duì)于斜率為1的線條，線寬最大，為垂直（水平）的2倍。實(shí)現(xiàn)正方形刷子最簡(jiǎn)單的辦法是，把方形中心對(duì)準(zhǔn)單象素寬的線條上各個(gè)象素，并把方形內(nèi)的象素全部置成線條顏色。這種簡(jiǎn)單方法將會(huì)重復(fù)地寫象素。這是因?yàn)閷?duì)應(yīng)于相鄰象素的方形一般會(huì)重迭。為了避免重復(fù)寫象素，可以采用與活性邊表類似的技術(shù)。方形刷子的原理線刷子還有另一個(gè)問(wèn)題：當(dāng)線寬為偶數(shù)個(gè)象素時(shí)，用上述方法繪制的線條要么粗一個(gè)象素，要么細(xì)一個(gè)象素。為了生成有寬度的線，還可以用方形的刷子，把邊寬為指定線寬的正方形的中心沿直線作平行移動(dòng)，即可獲得具有線寬的線條，如圖所示第十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期一方刷子的活性邊表技術(shù)為每條掃描線建一個(gè)表，存放該掃描線與線條的相交區(qū)間左右端點(diǎn)位置。在每個(gè)象素使用方形刷子時(shí)，用該方形與各掃描線的相交區(qū)間端點(diǎn)坐標(biāo)去更新原表內(nèi)端點(diǎn)數(shù)據(jù)，右圖為刷子移動(dòng)的相鄰兩步與有關(guān)掃描線的臨時(shí)數(shù)據(jù)結(jié)構(gòu)所保存的對(duì)應(yīng)于各步的區(qū)間端點(diǎn)坐標(biāo)。生成具有寬度的線條還可以采用區(qū)域填充的算法。先算出線條各角點(diǎn)，再用直線段把相鄰角點(diǎn)連接起來(lái)，最后調(diào)用多邊形填充算法把所得的四邊形進(jìn)行填色，即得到具有寬度的線條。用這種方法還可以生成兩端粗細(xì)不一樣的線條第十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期一圓弧線寬的處理（筆）為了生成具有寬度的圓弧，可采用與直線情形類似的方法，當(dāng)采用線刷子時(shí)，在經(jīng)過(guò)曲線斜率為1的點(diǎn)時(shí)，必須把線刷子在水平與垂直方向之間切換。由于線刷子總是置成水平或垂直的，所以在曲線接近水平與垂直的地方，線條更粗一些，而在斜率接近1的點(diǎn)附近，線條更細(xì)一些，如右上圖所示。當(dāng)采用正方形刷子時(shí)，無(wú)需移動(dòng)刷子方向。只需順著單象素的軌跡，把正方形中心對(duì)準(zhǔn)軌跡上的象素，把方形內(nèi)的象素全部用線條顏色填充。用正方形刷子繪制的曲線條，在接近水平與垂直的部分最細(xì)，而在斜率為1的點(diǎn)附近最粗，這恰與線刷子情形相反，如左上圖所示。第十八頁(yè)，共三十一頁(yè)，編輯于2023年，星期一圓弧線寬的處理(填充法)繪制具有寬度的圓弧線條也可以采用填充的辦法，先繪制圓弧線條的內(nèi)邊界和外邊界，然后在內(nèi)外邊界之間對(duì)其填色?？梢宰寖?nèi)外邊界都與單象素弧線軌跡距離半線寬，或把內(nèi)外邊界之一對(duì)準(zhǔn)單象素弧線軌跡,另一邊界線離開此線一個(gè)線寬距離。如圖所示為采用填充方法所得的圓弧線條示意圖。第十九頁(yè)，共三十一頁(yè)，編輯于2023年，星期一線型的處理在繪圖應(yīng)用中常用到不同線型的線條，以便區(qū)分各種不同的意義。實(shí)線:可見的輪廓線;虛線:不可見的輪廓線;點(diǎn)劃線:中心線等等。線型可以用一個(gè)布爾值的序列來(lái)存放。例如，用一個(gè)32位整數(shù)可以存放32個(gè)布爾值。用這樣的整數(shù)存放線型定義時(shí)，線型必須以32個(gè)象素為周期進(jìn)行重復(fù)?？梢园褣呙枳儞Q算法中的無(wú)條件寫象素語(yǔ)句改為if(bitstring[i%32])WritePixel(x，y，value);其中i為循環(huán)變量，在掃描變換算法的內(nèi)循環(huán)中每處理一個(gè)象素遞增1，然后除以32取余(“%”為C語(yǔ)言中求模運(yùn)算符),余數(shù)變化范圍是031。例子:bitstring=11111111110000000000111111111100用這種簡(jiǎn)單辦法實(shí)現(xiàn)的線型有個(gè)毛病。因?yàn)槊课粚?duì)應(yīng)于算法的一個(gè)迭代步驟而不是線條上一個(gè)長(zhǎng)度單位，因此線型中虛實(shí)筆劃長(zhǎng)度與直線傾斜度有關(guān)，斜線上的筆劃長(zhǎng)度比橫向或豎向上的筆劃更長(zhǎng),這在工程圖上是不允許的。所以,受影響的筆劃應(yīng)該作為單獨(dú)線段進(jìn)行計(jì)算和掃描變換,使其長(zhǎng)度不隨線的傾斜度的變化而變。以實(shí)心或透明矩形交替序列畫出的粗線,各矩形頂點(diǎn)作為所選線型函數(shù)精確地計(jì)算。然后分別對(duì)單個(gè)鉅形進(jìn)行掃描變換。對(duì)于垂直或水平的粗線線型，可以用復(fù)制矩形完成。線形和筆型在粗輪廓圖元中相互作用，線型用于計(jì)算每一個(gè)筆畫的矩形，而每一個(gè)矩形的填充則是用所選擇的筆型。第二十頁(yè)，共三十一頁(yè)，編輯于2023年，星期一字符討論的字符是指數(shù)字、字母、漢字等符號(hào)，用于圖形的標(biāo)注、說(shuō)明等。國(guó)際上最流行的字符集是“美國(guó)信息交換用標(biāo)準(zhǔn)代碼集“（AmericanStandardCodeforInformationInterchange），簡(jiǎn)稱ASCII碼。該字符集規(guī)定了127個(gè)字符代碼。其中代碼0—31表示控制字符，代碼32—127表示英文字母、標(biāo)點(diǎn)符號(hào)、數(shù)字符號(hào)、各種運(yùn)算符以及特殊符號(hào)。每個(gè)ASCII碼用一個(gè)字節(jié)（實(shí)際上只要七位二進(jìn)制）代碼表示。我國(guó)除采用ASCII碼外，還另外制訂了漢字代碼的國(guó)家標(biāo)準(zhǔn)字符集。最常用的字符集是”信息交換用漢字編碼字符集基本集”GB2312—80。該字符集包含了六千多個(gè)常用漢字，以及英文字母、數(shù)字和其它圖形符號(hào)。分成94個(gè)區(qū)94個(gè)位。區(qū)碼和位碼各用一個(gè)字節(jié)（實(shí)際上只要七位二進(jìn)制）來(lái)表示。為了能識(shí)別哪些字節(jié)表示ASCII碼，哪些字節(jié)表示漢字編碼，一般采用多余的一位（最高位）來(lái)標(biāo)識(shí)。最高位為0時(shí)，表示ASCII碼，最高位為1時(shí)表示漢字編碼。為了在終端顯示器或繪圖儀上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字符庫(kù)。字符庫(kù)中儲(chǔ)存了每個(gè)字符的形狀信息。字符庫(kù)分為矢量型和點(diǎn)陣型兩種。在筆式繪圖儀上采用矢量型字符比較適合，矢量型字符庫(kù)采用矢量代碼序列表示字符的各個(gè)筆畫，輸出一個(gè)字符時(shí)，系統(tǒng)中的字符處理器解釋該字符的每個(gè)矢量代碼，輸出對(duì)應(yīng)的矢量，達(dá)到產(chǎn)生字符的目的。在終端顯示器上顯示字符一般采用點(diǎn)陣型字符庫(kù)。點(diǎn)陣型字符庫(kù)為每個(gè)字符定義一個(gè)字符掩膜，即表示該字符的象素圖案的一個(gè)點(diǎn)陣。第二十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期一矢量字符為了建立一個(gè)矢量字符庫(kù)，必須對(duì)每個(gè)字符定義一個(gè)矢量代碼序列，下面以AutoCAD系統(tǒng)使用的矢量字符來(lái)說(shuō)明。在AutoCAD中，使用一種稱為形（shape）的圖形實(shí)體來(lái)定義西文字符、漢字甚至一些簡(jiǎn)單的圖形。形定義中使用直線和圓弧作為基本筆劃。每個(gè)形的定義包括一個(gè)標(biāo)題行和若干個(gè)描述行：*＜形編號(hào)＞，＜字節(jié)數(shù)＞，＜形名稱＞＜字節(jié)1＞＜字節(jié)2＞，…，0標(biāo)題行中，形編號(hào)是1到255的整數(shù)值。字節(jié)數(shù)表示形定義描述行中包括結(jié)束符0在內(nèi)的字節(jié)數(shù)目。形名稱用大寫字母才可以被調(diào)用，否則只作為形的一種解釋性信息，不存入存儲(chǔ)器，因而不占用存儲(chǔ)空間。描述行由若干個(gè)用逗號(hào)隔開的字節(jié)組成，并以0作為形定義的結(jié)束字節(jié)。帶有前綴0的字節(jié)是十六進(jìn)制。無(wú)前綴0的字節(jié)是十進(jìn)制。描述行中的每個(gè)字節(jié)包含矢量長(zhǎng)度和方向兩種信息。字節(jié)的低四位表示矢量方向，高四位表示矢量長(zhǎng)度。矢量的方向編碼如圖所示。注意，圖3-32中所有矢量都具有“相同“的長(zhǎng)度，即不同方向的矢量的長(zhǎng)度不一樣。例如，45方向的矢量一個(gè)單位長(zhǎng)相當(dāng)于水平方向的2單位長(zhǎng)。圖所示的二極管符號(hào)的形定義為：*133，11，DIODE040，044，04C，042，04C，040，048，04C，046，04C，0形描述的第一個(gè)字節(jié)040中，最高位0表示本字節(jié)為十六進(jìn)制數(shù)。后面兩位數(shù)4和0分別表示字節(jié)的高四位和低四位。高四位的4表示矢量長(zhǎng)度為4，低四位的0表示矢量方向?yàn)樗较蛴曳较?。第二十二?yè)，共三十一頁(yè)，編輯于2023年，星期一點(diǎn)陣字符在點(diǎn)陣字符庫(kù)中，每個(gè)字符都定義成一個(gè)字符掩膜的矩陣。矩陣中的每個(gè)元素都是一位二進(jìn)制數(shù)。該位為1時(shí)，表示字符的筆劃經(jīng)過(guò)此位，對(duì)應(yīng)于此位的象素應(yīng)置為字符顏色；該位為0時(shí)，表示字符的筆劃不經(jīng)過(guò)此位置，對(duì)應(yīng)此位的象素應(yīng)置為背景色（若當(dāng)前的寫方式是“替換“方式）或不改變（若當(dāng)前寫方式是“與“方式）。一般認(rèn)為定義西文字符的掩膜矩陣尺寸應(yīng)不小于57，而定義漢字字符的掩膜矩陣尺寸應(yīng)不小于1616。在我國(guó)廣泛使用的微機(jī)漢字系統(tǒng)，如CCDOS等等，都采用1616點(diǎn)陣漢字作為顯示用字符，而在打印時(shí)，采用2424，4040甚至7272的點(diǎn)陣字符。一個(gè)57西文字符點(diǎn)陣包括35個(gè)點(diǎn)，需要35位，故需要35位二進(jìn)制數(shù)（占四個(gè)多字節(jié)），一個(gè)1616點(diǎn)陣漢字，需要256位，即32個(gè)字節(jié)。而一個(gè)7272點(diǎn)陣漢字需要972=648個(gè)字節(jié)。用于打印的高分辯率點(diǎn)陣字符的掩膜位圖，可以是通過(guò)用掃描儀輸入放大的手寫美術(shù)字符或印刷字符，掃描輸入進(jìn)來(lái)的字符可用交互作圖程序?qū)ξ粓D的個(gè)別象素進(jìn)行修改，使之完善。用于顯示的或用于低分辯率打印機(jī)的字符位圖可以使用交互繪圖程序，通過(guò)手工建立。用低分辯率點(diǎn)陣字符產(chǎn)生的字符一般比較粗糙，不美觀，所以在微機(jī)上通常使用幾個(gè)不同分辯率的字符庫(kù)，以滿足不同的需要，例如在CCDOS4.0中就使用了24種不同的字符庫(kù)。第二十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期一字型技術(shù)當(dāng)應(yīng)用對(duì)輸出字符的要求較高時(shí)（如排版印刷），需要使用高質(zhì)量的點(diǎn)陣字符。然而直接使用上一小節(jié)所介紹的點(diǎn)陣字符方法將耗費(fèi)巨大的存儲(chǔ)空間。對(duì)于GB2312—80所規(guī)定的6763個(gè)基本漢字，假設(shè)每個(gè)漢字是7272點(diǎn)陣，那么一個(gè)字庫(kù)就需要4.4兆字節(jié)存儲(chǔ)空間！在實(shí)際使用時(shí)，需要多種字體（如基本體、宋體、仿宋體、黑體、楷體等），而每種字體又需要十種以上字號(hào)。因此把每種字體、字號(hào)的字符都存儲(chǔ)一個(gè)對(duì)應(yīng)的點(diǎn)陣，在一般情況是不可行的。解決這個(gè)問(wèn)題一般采用壓縮技術(shù)。對(duì)字型數(shù)據(jù)壓縮后再存儲(chǔ)，使用時(shí)，將壓縮的數(shù)據(jù)還原為字符位圖點(diǎn)陣。壓縮方法有多種，最簡(jiǎn)單的有黑白段壓縮法，這種方法簡(jiǎn)單，還原快，不失真，但壓縮較差，使用起來(lái)也不方便，一般用于低級(jí)的文字處理系統(tǒng)中，二是部件壓縮法。這種方法壓縮比大，缺點(diǎn)是字型質(zhì)量不能保證。三是輪廓字型法，這種方法壓縮比大，且能保證字符質(zhì)量，是當(dāng)今國(guó)際上最流行一種方法，基本上也被認(rèn)為是符合工業(yè)標(biāo)準(zhǔn)化的方法。輪廓字型法采用直線、或者二／三次/Bezier曲線的集合來(lái)描述一個(gè)字符的輪廓線。輪廓線構(gòu)成一個(gè)或若干封閉的平面區(qū)域。輪廓線定義加上一些指示橫寬、豎寬、基點(diǎn)、基線等的控制信息就構(gòu)成了字符的壓縮數(shù)據(jù)。這種控制信息用于保證字符變倍時(shí)引起原來(lái)的橫寬／豎寬變大變小時(shí)，其寬度在任何點(diǎn)陣情況下永遠(yuǎn)一致。采用適當(dāng)?shù)膮^(qū)域填充算法，可以從字符的輪廓線定義產(chǎn)生字符位圖點(diǎn)陣，區(qū)域填充算法可以用硬件實(shí)現(xiàn)，做在RISC集成電路板上成為RIP(RasterImageProcessor)。也可以用軟件實(shí)現(xiàn)，寫成一段精心編制的程序。第二十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期一字型技術(shù)當(dāng)前國(guó)際流行的TrueType字型技術(shù)是由美國(guó)Apple和Microsoft公司聯(lián)合開發(fā)的。并且已被用于為Windows中文版生成漢字字庫(kù)。TrueType使用二次Bezier曲線來(lái)描述字符輪廓，對(duì)字符輪廓線的控制點(diǎn)進(jìn)行編號(hào)。其順序是按順時(shí)針?lè)较蜃咭蝗?，填充的部分始終在其右邊，下面以大寫字母Ｈ為例，說(shuō)明TrueType字庫(kù)控制信息。x方向控制信息有：1)字身最左起始點(diǎn)到字母主干的距離間隔；2)字母主體部分的寬度；3)字身的寬度；4)字母Ｈ主干（stem）的寬度；5)字母Ｈ的襯線(Serif) 如圖(a)所示。y方向控制信息有：6)字母Ｈ橫干(crossbar)的厚度；7)字母Ｈ襯線的厚度；8)字母主體部分的厚度；9)字母Ｈ橫干的高度；如圖(b)所示。這上述9個(gè)參數(shù)用于產(chǎn)生控制信息表。這個(gè)控制信息表和曲線輪廓定義信息將在不同分辯率情況下產(chǎn)生字符的點(diǎn)陣中起關(guān)鍵作用。這種方法能夠準(zhǔn)確地把字符的信息描述下來(lái)，保證了還原的字符質(zhì)量，又對(duì)字型數(shù)據(jù)進(jìn)行了大量的壓縮。調(diào)用字符時(shí)，可以任意地放大、縮小或進(jìn)行花樣變化，基本上能滿足電子印刷中字型質(zhì)量的要求。一套字型的生產(chǎn)周期大于1個(gè)人年，最早的生產(chǎn)方法是由寫字專家寫出字符，然后把字符托到9696方格紙上，在9696方格紙上人為地畫出矢量節(jié)點(diǎn)，最后由操作員錄入計(jì)算機(jī)?，F(xiàn)在使用的一般方法是用掃描儀把字型數(shù)字化，用程序自動(dòng)地進(jìn)行矢量輪廓的生成，再由操作員對(duì)矢量結(jié)果進(jìn)行調(diào)整優(yōu)化，做成合格的字型。好的字型數(shù)據(jù)是來(lái)之不易的!第二十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期一字符裁剪當(dāng)字符或文本整個(gè)不在窗口時(shí)，則不予顯示。然而，當(dāng)字符和文本部分在窗口內(nèi)，部分在窗口外時(shí)，就提出了字符裁剪的問(wèn)題。字符精度：最簡(jiǎn)單的字符裁剪方法是把字符方框（即字符掩膜）與窗口比較。若整個(gè)方框位于窗口內(nèi)，則顯示對(duì)應(yīng)字符，否則不予顯示。象素精度：有些應(yīng)用要求更準(zhǔn)確的處理：即使字符只有一部分在窗口內(nèi)，也要把這一部分顯示出來(lái)。若字符為點(diǎn)陣型的，只要在把字符掩膜各位寫入象素之前，先判斷該位對(duì)應(yīng)的象素是否在窗口內(nèi)，若該位在窗口內(nèi)則寫，否則就不寫。筆劃精度：在字符為矢量型的情形，問(wèn)題就更復(fù)雜一些。這時(shí)要對(duì)跨越窗口邊界的筆劃進(jìn)行裁剪，裁去筆劃伸到窗口外的部分，保留筆劃在窗口內(nèi)的部分，這個(gè)問(wèn)題可以轉(zhuǎn)化為線段的裁剪。字符串裁剪，可以按三個(gè)精確度來(lái)進(jìn)行：串精確度、字符精確度、以及筆劃／象素精確度。采用串精確度進(jìn)行裁剪時(shí)，當(dāng)字符串方框整個(gè)在窗口內(nèi)予以顯示，否則不顯示。采用字符精確度時(shí)，當(dāng)字符串的某個(gè)字符方框整個(gè)在窗口內(nèi)時(shí)，顯示該字符，否則不顯示。當(dāng)采用筆劃／象素精度時(shí)，要具體判斷字符串中各字符的哪些象素、筆劃的哪一部分在窗口內(nèi)，處理方法同字符裁剪。第二十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期一反走樣在光柵圖形顯示器上繪制直線、多邊形等連續(xù)圖形時(shí)，由于光柵是由離散的點(diǎn)組成，因此使生成的圖形呈鋸齒狀，從而使圖形出現(xiàn)失真。這種離散量表示連續(xù)量引起的失真就叫走樣（aliasing）。用于減少或克服這種效果的技術(shù)叫做反走樣(antialiasing)。光柵圖形的走樣現(xiàn)象除了產(chǎn)生鋸齒狀之外，還有圖形的細(xì)節(jié)失真及狹小圖形遺失等現(xiàn)象當(dāng)在光柵圖形顯示器上顯示如圖(a)所示的許多細(xì)長(zhǎng)矩形時(shí)，由于僅當(dāng)象素中心被這些矩形覆蓋時(shí)才被顯示，因而造成圖形失真，即將圖形中細(xì)節(jié)丟失，稱為細(xì)節(jié)失真。圖(b)即為(a)的失真圖形。此外還有一種叫狹小圖形遺失的走樣，即在進(jìn)行圖形顯示時(shí)一些相對(duì)微小的物體被丟失或忽略。走樣現(xiàn)象還會(huì)使得動(dòng)態(tài)圖形時(shí)隱時(shí)現(xiàn)、產(chǎn)生閃爍。如對(duì)于一個(gè)狹小的長(zhǎng)方形從上往下進(jìn)行運(yùn)動(dòng)時(shí)，由于圖形忽顯忽不顯，給人的感覺就象是一明一暗的間斷閃爍。所以，為了提高圖形顯示質(zhì)量，需要反走樣技術(shù)。第二十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期一通過(guò)提高分辯率反走樣可以采用提高分辯率的方法進(jìn)行反走樣，因?yàn)橛酶叻洲q率顯示器所顯示的圖形與低分辯率相比質(zhì)量高，鋸齒就不明顯。提高分辯率的方法有二種：采用高分辯率的光柵圖形顯示器，但是代價(jià)太高，故