【正文】 ），修改比較的基點(diǎn)為改點(diǎn)，即將 d1 –而當(dāng) d，選擇當(dāng)前象素的右方象素（ ），此時(shí)不改變基點(diǎn) ?為方便計(jì)算，令 e＝ ， ?e的初值為 ，增量為 k。 –當(dāng) e≥ 0時(shí)，取當(dāng)前象素（ xi， yi）的右上方象素（ ）； –而當(dāng) e0時(shí)，更接近于右方象素（ ）。 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) Bresenham算法 ?例： Line: P0(0, 0), P1(5,2) k=dy/dx= ? x y e ? 0 0 ? 1 0 ? 2 1 ? 3 1 ? 4 2 ? 5 2 ?e每次加 k，若 e大于零則 y加 1且 e減 1， 若 e小于零則不變 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) Bresenham算法 ? void Bresenhamline (int x0,int y0,int x1, int y1,int color) ? { int x, y, dx, dy。 ? float k, e。 ? dx = x1x0, dy = y1 y0, k=dy/dx。 ? e=, x=x0, y=y0。 ? for (i=0。 i?dx。 i++) ? { drawpixel (x, y, color)。 ? x=x+1， e=e+k。 ? if (e?0) ? { y++, e=e1。} ? } ? } 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) Bresenham算法 ? 可以改用整數(shù)以避免除法。由于算法中只用到誤差項(xiàng)的符號(hào)，因此可作如下替換： dx e e * * 2 39。 ? 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) Bresenham算法 ? void Bresenhamline (int x0,int y0,int x1, int y1,int color) ? { int x, y, dx, dy,e。 ? dx = x1x0, dy = y1 y0。 ? e= dx, x=x0, y=y0。 ? for (i=0。 i?dx。 i++) ? { drawpixel (x, y, color)。 ? x=x+1， e=e+2*dy。 ? if (e?0) ? { y++, e=e2*dx。} ? } ? } int x, y, dx, dy。 float k, e。 dx = x1x0, dy = y1 y0。 k=dy/dx,e=。 x=x0, y=y0。 for (i=0。 i?dx。 i++) {drawpixel (x, y, color)。 x=x+1， e=e+k。 if (e?0) { y++, e=e1。} } 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) Bresenham算法 ? y每次增 k ? 誤差項(xiàng) 每次也增 k （同 DDA算法） ? 通過(guò) 交點(diǎn) 與 基點(diǎn) 的距離 d 來(lái)判斷 ? 為了用正負(fù)號(hào)判斷， e＝ ? 為了變?yōu)檎麛?shù)算法 ? 最終， Bresenham算法也是每個(gè)象素，需一個(gè)整數(shù)算法， ? 其優(yōu)點(diǎn)是可以用于其他二次曲線。 dx e e * * 2 39。 ? 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 圓弧的掃描轉(zhuǎn)換算法 ? 圓的特征： 八對(duì)稱性。只要掃描轉(zhuǎn)換八分之一圓弧，就可以求出整個(gè)圓弧的象素集 ? 中點(diǎn)畫圓法 ? 考慮中心在原點(diǎn)，半徑為 R ? 的第二個(gè) 8分圓， –構(gòu)造判別式（圓方程） 222 )()1(),1()(RyxyxFMFdpppp?????????計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 圓弧的掃描轉(zhuǎn)換算法 若 d0, 則取 P1為下一象素，而且再下一象素的判別式為 ? 若 d=0, 則應(yīng)取 P2為下一象素，而且下一象素的判別式為 ? 第 一個(gè)象素是（ 0,R），判別式 d的初始值為 32)()2(),2(39。 222 ??????????? ppppp xdRyxyxFd5)(2)()2(),2(39。 222 ???????????? pppppp yxdRyxyxFdRRFd ???? ),1(0計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 圓弧的掃描轉(zhuǎn)換算法 ? MidPointCircle(int r int color) ? { int x,y。 ? float d。 ? x=0。 y=r。 d=。 ? circlepoints (x,y,color)。 //顯示圓弧上的八個(gè)對(duì)稱點(diǎn) ? while(x=y) ? { if(d0) d+=2*x+3。 ? else { d+=2*(xy)+5。 y。} x++。 circlepoints (x,y,color)。 ? } ? } 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 圓弧的掃描轉(zhuǎn)換算法 ? 為了進(jìn)一步提高算法的效率，可以將上面的算法中的浮點(diǎn)數(shù)改寫成整數(shù)，將乘法運(yùn)算改成加法運(yùn)算，即僅用整數(shù)實(shí)現(xiàn)中點(diǎn)畫圓法。 ? 如何改？ 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 圓弧的掃描轉(zhuǎn)換算法 ? 使用 e= d ? e0=1R 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 圓弧的中點(diǎn)掃描轉(zhuǎn)換算法 ? 利用圓八對(duì)稱性 ? 類似于直線的中點(diǎn)法 ? 使用了圓的隱式方程 ? 兩種不同的增量（ 0時(shí) ， 0時(shí)） ? 為了改為整數(shù)算法 e= d 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 小結(jié) ? 直線段的掃描轉(zhuǎn)換算法 – 數(shù)值微分 (DDA)法 – 中點(diǎn)畫線法 – Bresenham算法 ? 圓弧的掃描轉(zhuǎn)換算法 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 ? 多邊形的表示方法 – 頂點(diǎn)表示 – 點(diǎn)陣表示 ? 頂點(diǎn)表示：用多邊形頂點(diǎn)的序列來(lái)刻劃多邊形。直觀、幾何意義強(qiáng)、占內(nèi)存少；不能直接用于面著色。 ? 點(diǎn)陣表示：用位于多邊形內(nèi)的象素的集合來(lái)刻劃多邊形。失去了許多重要的幾何信息；便于運(yùn)用幀緩沖存儲(chǔ)器表示圖形，易于面著色。 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 ? 多邊形的掃描轉(zhuǎn)換： 把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，也就是從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)象素，并給幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度和顏色，通常稱這種轉(zhuǎn)換為多邊形的掃描轉(zhuǎn)換。 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 ? 區(qū)域 指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是象素的集合。 ? 區(qū)域填充 指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過(guò)程。區(qū)域填充算法要求區(qū)域是連通的。 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 多邊形的掃描轉(zhuǎn)換與區(qū)域填充 ? 區(qū)域表示方法： 內(nèi)點(diǎn)表示、邊界表示 ? 內(nèi)點(diǎn)表示 – 枚舉出 區(qū)域內(nèi)部 的所有像素 – 內(nèi)部的所有像素著同一個(gè)顏色 – 邊界像素著與內(nèi)部像素不同的 顏色 ? 邊界表示 – 枚舉出 邊界上 所有的像素 – 邊界上的所有像素著同一顏色 – 內(nèi)部像素著與邊界像素不同的顏色 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) ? 多邊形分為凸多邊形、凹多邊形、含內(nèi)環(huán)的多邊形。 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 逐點(diǎn)判斷算法 ? 逐點(diǎn)判斷算法：逐個(gè)像素判別其是否位于多邊形內(nèi)部 ? 判斷一個(gè)點(diǎn)是否位于多邊形內(nèi)部： 射線法 –從當(dāng)前像素發(fā)射一條射線，計(jì)算射線與多邊形的交點(diǎn)個(gè)數(shù) ? 內(nèi)部：奇數(shù)個(gè)交點(diǎn) ? 外部：偶數(shù)個(gè)交點(diǎn) 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 逐點(diǎn)判斷算法 判斷一點(diǎn)是否位于多邊形內(nèi)部？ 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 逐點(diǎn)判斷算法 ? 算法描述 for(y=0。 y=y_resolution。 y++) for(x=0。 x=x_resolution。 x++) { if(inside(polygon, x, y)) setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_color) } 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 逐點(diǎn)判斷算法的不足 ? 速度慢：幾十萬(wàn)甚是幾百萬(wàn)像素的多邊形內(nèi)外判斷，大量的求交、乘除運(yùn)算 ? 沒(méi)有考慮像素之間的聯(lián)系 ? 結(jié)論： 逐點(diǎn)判斷算法不可??！ 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 掃描線算法 ? ? 一個(gè)多邊形與若干掃描線 ? 0 1122 3344 5566 7788 9 10 11P 2(5,1)EP 3(11,3 )DP 4(11,8 )GFCBP 5(5,5)P 6(2,7)AP 1(2,2)計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) ? 掃描線算法 –基本思想： ? 按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的象素，即完成填充工作。 –對(duì)于一條掃描線填充過(guò)程可以分為四個(gè)步驟： ?求交 ?排序 ?配對(duì) ?填色 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 多邊形掃描轉(zhuǎn)換算法 P0 P1 P2 P3 P4 P5 P6 P7 x y 掃描轉(zhuǎn)換示意圖 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 相鄰像素之間的連貫性 ? 掃描線算法充分利用了相鄰像素之間的連貫性，避免了對(duì)像素的逐點(diǎn)判斷和求交運(yùn)算，提高了算法效率 ? 各種連貫性的定義 –區(qū)域連貫性 –掃描線連貫性 –邊的連貫性 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 區(qū)域連貫性 ? 區(qū)域的連貫性是指多邊形定義的區(qū)域內(nèi)部相鄰的像素具有相同的性質(zhì)。例如具有相同的顏色 區(qū)域的連貫性 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 區(qū)域連貫性 ? 兩條掃描線之間的長(zhǎng)方形區(qū)域被所處理的多邊形分割成若干梯形 (三角形可以看作退化梯形 ) ? 梯形的底邊為掃描線，梯形的腰為多邊形的邊或窗口邊緣 區(qū)域的連貫性 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 區(qū)域連貫性 ? 梯形分為兩類：多邊形內(nèi)部和多邊形外部 ? 兩類梯形在多邊形內(nèi)部相間排列 (相鄰的兩個(gè)梯形必然有一個(gè)位于多邊形內(nèi)部，有一個(gè)在多邊形外部 ) 區(qū)域的連貫性 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 區(qū)域連貫性 ? 推論：如果上述梯形屬于多邊形內(nèi) (外 )，那么該梯形內(nèi)所有點(diǎn)的均屬于多邊形內(nèi) (外 )。 ? 效率提高的根源：逐點(diǎn)判斷 ?區(qū)域判斷 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 掃描線連貫性 ? 區(qū)域連貫性在一條掃描線上的反映 掃描線的連貫性 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 掃描線連貫性 ? 交點(diǎn)序列：掃描線與多邊形的交點(diǎn)個(gè)數(shù)為偶數(shù) (1,2,3,4,5,6) ? 紅色 區(qū)間 (1,2)、 (3,4)、(5,6)位于多邊形內(nèi)部 ? 其余 綠色 區(qū)間位于多邊形外部 ? 兩類區(qū)間相間排列 掃描線的連貫性 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 掃描線連貫性 ? 推論：如果上述交點(diǎn)區(qū)間屬于多邊形內(nèi) (外 )，那么該區(qū)間內(nèi)所有點(diǎn)均屬于多邊形內(nèi) (外 )。 ? 效率提高的根源：逐點(diǎn)判斷 ?區(qū)間判斷 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 邊的連貫性 ? 邊的連貫性：直線的線性性質(zhì)在光柵上的表現(xiàn) 邊的連貫性 1 (x1,y1) 2 (x2,y2) 11 (x11,y11) 22 (x22,y22) 掃描線與邊的交點(diǎn) 計(jì)算機(jī)圖形學(xué) 福建師范大學(xué) 邊的連貫性 ? 相鄰掃描線 (y1=y11+1)與多邊形的同一條邊的交點(diǎn)存在如下關(guān)系： ? 當(dāng)知道掃描線與一條邊的一個(gè)交點(diǎn)之后，通過(guò)上述公式可以通過(guò)增量算法迅速求出其他交點(diǎn)