【文章內(nèi)容簡介】 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 46 誤差項的遞推 d1≤0： ( a) d = 0 的情況Px iy i 2x i + 1y iy i 1x i + 2)x(bd )x(bba).(ya)(xb ba).(ya)(xb).,yF (xdiiiiiiii32325015025022122222222222221???????????????????2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 47 d10： )22()32( )22()32()()1( )()2(),2(221222222222222221????????????????????????iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd( b) d 0 的情況Px i x i + 2x i + 1y i 1y iy i 2判別式的初始值 )( )(),1(222222210??????????babbababbFd2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 49 p(x i ,y i )p l (x i ,y i1 ) p r (x i+1 ,y i1 )M (x i+1 ,y )5 1 9 下半部分橢圓弧的繪制原理再來推導(dǎo)橢圓弧下半部分的繪制公式 原理 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 50 判別式 2222222 )1()()1,( bayaxbyxFd iiii ?????????若 d20， 取 Pl(xi,yi1) ?若 d2≤0， 取 Pr(xi+1,yi1) p(x i ,y i )p l (x i ,y i1 ) p r (x i+1 ,y i1 )M (x i+1 ,y )5 1 9 下半部分橢圓弧的繪制原理2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 51 誤差項的遞推 d20： )y(ad )y(aba)(ya)(xb ba)(ya)(xb),yF ( xdiiiiiiii32 2222222222222222????????????????????( a) d 0 的情況Px iy i 2x i + 1y iy i 1x i + 22020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 52 d2≤0： )32()22( )32()22()1()( )2()()2,(222222222222222222????????????????????????iiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd( b) d = 0 的情況Px i x i + 2x i + 1y i 1y iy i 22020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 53 注意 ： ? 上半部分的終止判別 ? 下半部分誤差項的初值 算法步驟 ： a和短半軸 b。 d=b2+a2(b+)、 x=0、 y=b。 (x,y)及其在四分象限上的另外三個對稱點 。 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 54 d的符號 。 若 d≤0， 則先將 d更新為 d+b2(2x+3)，再將 ( x,y) 更新為 ( x+1,y)； 否 則 先將 d 更 新為d+b2(2x+3)+a2(2y+2)， 再將 (x,y)更新為 (x+1,y1)。 b2(x+1)a2()時 ， 重復(fù)步驟 3和 4。 否則轉(zhuǎn)到步驟 6。 (x,y)來計算下半部分中 d的初值： 222222 )1()( bayaxbd ?????2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 55 (x,y)及其在四分象限上的另外三個對稱點 。 d的符號 。 若 d≤0， 則先將 d更新為 b2(2xi+2)+a2(2yi+3)， 再將 (x,y)更新為 (x+1,y1)； 否則先將 d更新為 d+a2(2yi+3)， 再將 (x,y)更新為 (x,y1)。 y0時 ， 重復(fù)步驟 7和 8。 否則結(jié)束 。 程序 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 56 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 多邊形的掃描轉(zhuǎn)換 主要是通過確定穿越區(qū)域的掃描線的覆蓋區(qū)間來填充 ， 區(qū)域填充 是從給定的位置開始涂描直到指定的邊界條件為止 。 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 57 多邊形的掃描轉(zhuǎn)換 頂點表示 用多邊形的頂點序列來刻劃多邊形 點陣表示 是用位于多邊形內(nèi)的象素的集合來刻劃多邊形 掃描轉(zhuǎn)換多邊形或多邊形的填充 ：從多邊形頂點表示到點陣表示的轉(zhuǎn)換 。 1. 什么是多邊形的掃描轉(zhuǎn)換 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 58 2. x掃描線算法 基本思想 圖5 2 3 x 掃描線算法填充多邊形xy21 3 4 5 6 7 8 9 1112345678910111210 122020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 59 算法步驟 ： (1)確定多邊形所占有的最大掃描線數(shù) ， 得到多邊形頂點的最小和最大 y值 （ ymin和 ymax） 。 (2)從 y=ymin到 y=ymax， 每次用一條掃描線進(jìn)行填充 。 (3)對一條掃描線填充的過程可分為四個步驟： 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 60 存在問題： 當(dāng)掃描線與多邊形頂點相交時 ， 交點的取舍問題 。 xy21 3 4 5 6 7 8 9 1112345678910111210 12圖5 2 4 與多邊形頂點相交的交點的處理2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 61 解決 ： 當(dāng)掃描線與多邊形的頂點相交時 ， ? 若共享頂點的兩條邊分別落在掃描線的兩邊 ， 交點只算一個； ? 若共享頂點的兩條邊在掃描線的同一邊 ， 這時交點作為零個或兩個 。 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 62 圖5 2 5 與掃描線相交的多邊形頂點的交點數(shù)0 1 1 1 1 0 2 2 2 填充過程實例 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 63 3. 改進(jìn)的有效邊表算法 （ Y連貫性算法 ） x i ,y ix i + 1 ,y i + 111/k圖5 2 6 與多邊形邊界相交的兩條連續(xù)掃描線交點的相關(guān)性改進(jìn)原理 ： ? 處理一條掃描線時 ， 僅對有效邊求交 ? 利用掃描線的連貫性 ? 利用多邊形邊的連貫性 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 64 有效邊 （ Active Edge） ： 指與當(dāng)前掃描線相交的多邊形的邊 ， 也稱為活性邊 。 有效邊表 （ Active Edge Table, AET） ： 把有效邊按與掃描線交點 x坐標(biāo)遞增的順序存放在一個鏈表中 ，此鏈表稱為有效邊表 。 有效邊表的每個結(jié)點： x ymax 1/k next 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 65 邊表 （ Edge Table） 邊表的構(gòu)造： (1)首先構(gòu)造一個縱向鏈表 ， 鏈表的長度為多邊形所占有的最大掃描線數(shù) ， 鏈表的每個結(jié)點 ， 稱為一個桶 ， 則對應(yīng)多邊形覆蓋的每一條掃描線 。 (2)將每條邊的信息鏈入與該邊最小 y坐標(biāo) （ ymin ） 相對應(yīng)的桶處 。 也就是說 ， 若某邊的較低端點為 ymin， 則該邊就放在相應(yīng)的掃描線桶中 。 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 66 (3)每條邊的數(shù)據(jù)形成一個結(jié)點 ， 內(nèi)容包括：該掃描線與該邊的初始交點 x（ 即較低端點的 x值 ） ， 1/k，以及該邊的最大 y值 ymax。 x|ymin ymax 1/k NEXT (4)同一桶中若干條邊按 X|ymin由小到大排序 ， 若X|ymax 相等 ， 則按照 1/m由小到大排序 。 2020/10/7 華中理工大學(xué)計算機學(xué)院 陸楓 997 67 解決頂點交點計為 1時的情形 ： 圖5 2 8 將多邊形的某些邊縮短以分離那些應(yīng)計為1 個交點的頂點（a ) 原圖 （b ) 縮短y max 的邊 （