第四章多邊形的掃描轉(zhuǎn)換與區(qū)域填充-wenkub
2022-08-29 13:31:42 本頁面
【正文】 連貫性都基于這樣的幾何事實：每一條掃描線與多邊形 P的邊界的交點(diǎn)個數(shù)都是偶數(shù)。 y=e y=d 邊的連貫性 特別是當(dāng)存在某一個整數(shù) k,0≤k≤n 1,使得 yike, dyik+1 成立時，則由區(qū)域的連貫性可知 d的交點(diǎn)序列和 e的交點(diǎn)序列之間有以下關(guān)系： 1）兩序列元素的個數(shù)相等，如上圖所示。 設(shè)位于掃描線 y=d上的交點(diǎn)序列為 xdj1,xdj2,xdj3,… ,xdjk 現(xiàn)在來討論掃描線 d， e交點(diǎn)序列之間的關(guān)系。由區(qū)域的連貫性可知，此交點(diǎn)序列具有以下性質(zhì)： 掃描線的連貫性 掃描線的連貫性 1）設(shè) L是偶數(shù)。 y=yik+1 y=yik 區(qū)域的連貫性 根據(jù)這些性質(zhì)，實際上只需知道該長方形區(qū)域內(nèi)任一梯形內(nèi)一點(diǎn)關(guān)于多邊形 P的內(nèi)外關(guān)系后，即可確定區(qū)域內(nèi)所有梯形關(guān)于 P的內(nèi)外關(guān)系 。掃描轉(zhuǎn)換算法綜合利用了區(qū)域的連貫性、掃描線連貫性和邊的連貫性等三種形式的連貫性。 只要檢查頂點(diǎn)的兩條邊的另外兩個端點(diǎn)的 Y值，兩個 Y值中大于交點(diǎn) Y值的個數(shù)是 0， 1， 2，來決定取 0， 1， 2個交點(diǎn)。 掃描線算法 ? 掃描線算法 – 目標(biāo)：利用相鄰像素之間的連貫性，提高算法效率 – 處理對象：非自交多邊形 （邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)） 掃描線算法 – 交點(diǎn)的取整規(guī)則 ? 要求：使生成的像素全部位于多邊形之內(nèi) – 用于線畫圖元掃描轉(zhuǎn)換的四舍五入原則導(dǎo)致部分像素位于多邊形之外，從而不可用 ? 假定非水平邊與掃描線 y=e 相交，交點(diǎn)的橫坐標(biāo)為 x, 規(guī)則如下 掃描線算法 ● 規(guī)則 1： X為小數(shù)，即交點(diǎn)落于掃描線上兩個相鄰像素之間 (a)交點(diǎn)位于左邊之上，向右取整 (b)交點(diǎn)位于右邊之上，向左取整 ● 規(guī)則 2： 邊界上象素的取舍問題，避免填充擴(kuò)大化。 ? 點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來刻劃多邊形。第四章多邊形的掃描轉(zhuǎn)換 與區(qū)域填充 ? 多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲器表示圖形，易于面著色。 ● 解決方法： 邊界象素：規(guī)定落在右上邊界的象素不予填充。 掃描線算法 掃描線算法是多邊形掃描轉(zhuǎn)換的常用算法。 掃描線算法 設(shè)多邊形 P的頂點(diǎn) Pi=(xi,yi),i=0,1, … ,n，又設(shè)yi0,yi1,… yin 是各頂點(diǎn) Pi的坐標(biāo) yi的遞減數(shù)列，即 yik≥y ik+1,0≤k≤n 1 這樣，當(dāng) yik≥y ik+1,0≤k≤n 1時，屏幕上位于 y=yik和y=yik+1兩條掃描線之間的長方形區(qū)域 被多邊形 P的邊分割成若干梯形（三角形可看作其中一底邊長為零的梯形），它們具有下列性質(zhì)： 區(qū)域的連貫性 y=yik y=yik+1 區(qū)域的連貫性 1）梯形的兩底邊分別在 y=yik和 y=yik+1兩條掃描線上，腰在多邊形 P的邊上或在顯示屏幕的邊界上。 設(shè) e為一整數(shù)， yi0≥e≥y in。 2）在該掃描線上，只有區(qū)段(xeik,xeik+1） ,k=1,3,5,… ,L1位于多邊形 P內(nèi)，其余區(qū)段都在 P外。若多邊形 P的邊 Pr1Pr與掃描線 y=e,y=d都相交，則交點(diǎn)序列中對應(yīng)元素 xer,xdr滿足下列關(guān)系： xer= xdr + 1/mr (1) 其中 mr為邊 Pr1Pr的斜率。 2）點(diǎn) (xeir,e)與 (xdjr,d)位于多邊形 P的同一邊上，于是 xeir= xdjr + 1/kjr (2) 這樣，運(yùn)用遞推關(guān)系式 (2)可直接由 d的交點(diǎn)序列和 e的獲得 e的交點(diǎn)序列。但是如果把每一奇點(diǎn)簡單地計為一個交點(diǎn)或者簡單地計為兩個交點(diǎn)，都可能出現(xiàn)奇數(shù)個交點(diǎn)。如果 (yi1 yi)(yi+1 yi)≥0 ，則稱頂點(diǎn) Pi為極值點(diǎn)；否則稱 Pi為非極值點(diǎn)。 由 yin的交點(diǎn)序列 開始，根據(jù)多邊形的
物理相關(guān)推薦
鄂ICP備17016276號-1