計算機圖形學課件 第9講 區域填充和字符處理

信息科學與工程學院 1999年7月 5.4.1 多邊形的掃描轉換 多邊形的兩種表示方法： 頂點表示：用多邊形的頂點序列來刻劃多邊形。直觀、幾何意義強、占內存少；不能直接用于面著色。 點陣表示是用位于多邊形內的像素的集合來刻劃多邊形。失去了許多重要的幾何信息；便于運用幀緩沖存儲器表示圖形，易于面著色。 算法步驟： (1)確定多邊形所占有的最大掃描線數，得到多邊形頂點的最小和最大y值(ymin和ymax)。 (2)從y=ymin到y=ymax，每次用一條掃描線進行填充。對一條掃描線填充的過程可分為四個步驟： a. 求交：計算掃描線與多邊形各邊的交點； b. 排序：把所有交點按x值遞增順序排序； c. 配對：第一個與第二個，第三個與第四個等等；每對交點代表掃描線與多邊形的一個相交區間; d. 填色：把相交區間內的像素置成多邊形顏色，把相交區間外的像素置成背景色。 存在問題和解決方法：當掃描線與多邊形頂點相交時，交點的取舍問題。 3. 改進的有效邊表算法(Y連貫性算法) 有效邊(Active Edge)：指與當前掃描線相交的多邊形的邊，也稱為活性邊。 有效邊表(Active Edge Table, AET)：把有效邊按與掃描線交點x坐標遞增的順序存放在一個鏈表中，此鏈表稱為有效邊表。 有效邊表的每個結點： x ymax 1/k next 邊表(Edge Table)——方便有效邊的建立和更新 邊表的構造： (1)首先構造一個縱向鏈表，鏈表的長度為多邊形所占有的最大掃描線數，鏈表的每個結點，稱為一個桶，其對應多邊形覆蓋的每一條掃描線。 (2)將每條邊的信息鏈入與該邊最小y坐標(ymin )相對應的桶處。也就是說，若某邊的較低端點為ymin，則該邊就放在相應的掃描線桶中。 (3)每條邊的數據形成一個結點，內容包括：該掃描線與該邊的初始交點x(即較低端點的x值)，1/k，以及該邊的最大y值ymax。 x|ymin ymax 1/k next 算法步驟： (1)初始化：構造邊表，AET表置空； (2)將第一個不空的ET表中的邊與AET表合并； (3)由AET表中取出交點對進行填充。 填充時設一布爾變量b(初值為假)，令指針從AET中第一個結點到最后一個結點遍歷一次，每訪問一個結點，把b取反一次，若b為真，則把從當前結點的x值到下一結點的x值結束的區間用多邊形色填充。填充之后刪除y=ymax的邊。(期間，x=round(x) ) (4)yi+1=yi+1,根據xi+1=xi+1/k計算并修改AET表，同時合并ET表中y=yi+1桶中的邊，按次序插入到AET表中，形成新的AET表； (5)AET表不為空則轉(3)，否則結束。 5.4.2 邊緣填充算法 邊緣填充算法基本思想 按任意順序處理多邊形的每條邊。在處理每條邊時，首先求出該邊與掃描線的交點，然后將每一條掃描線上交點右方的所有像素取補。 5.4.3 區域填充 區域填充是指從區域內的一個點(種子)開始，由內向外將填充色擴展到整個區域內的過程。 區域是指已經表示成點陣形式的填充圖形，它是像素集合。通常有內點表示和邊界表示兩種形式。 邊界表示法 邊界表示法：把位于給定區域的邊界上像素一一列舉出來的方法。 在邊界表示法中，區域邊界上的像素著同一顏色，而區域內的像素點不能著這種顏色。 由于邊界以特殊顏色指定，填充算法可逐個像素地向外處理，直到遇到邊界顏色為止。以此為基礎的區域填充算法稱為邊界填充算法(Boundary-fill Algorithm)。 內點表示法 內點表示：枚舉出給定區域內所有像素的表示方法。 在內點表示法中，區域內的所有像素點著同一顏色，而區域邊界上的像素著不同的顏色。 以內點表示法為基礎的區域填充算法稱為泛填充算法(Flood-fill Algorithm)。 區域通常分為4-連通區域和8-連通區域兩類。 一個點p的4-鄰接點是指上、下、左、右四個相鄰的點。 一個點p的8-鄰接點是指上、下、左、右、左上、右上、左下、右下八個相鄰的點。 4-連通區域是指從區域上一點出發，通過訪問已知點的4-鄰接點，在不越出區域的前提下，遍歷區域內的所有像素。 8-連通區域是指從區域上一點出發，通過訪問已知點的8-鄰接點，在不越出區域的前提下，遍歷區域內的所有像素。 1. 邊界填充算法 算法的輸入：種子點坐標(x,y)，填充色和邊界顏色。 棧結構實現4-連通邊界填充算法的算法步驟為： 種子像素入棧；當棧非空時重復執行如下三步操作： (1)棧頂像素出棧； (2)將出棧像素置成填充色；

總結

以上是生活随笔為你收集整理的计算机图案填充的两种方法,计算机图形学课件 第9讲 区域填充和字符处理.ppt...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。