計算機圖形學基本光柵圖形算法

第三章基本光柵圖形算法計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第1頁!本章內容3.1用Java語言繪圖13.2直線的掃描轉換23.3圓的掃描轉換33.4多邊形的掃描轉換43.5區(qū)域填充53.6字符的生成63.7光柵圖形的反走樣算法7計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第2頁!3.2直線的掃描轉換

⊙圖形圖像是由屏幕上不同亮度不同顏色的光點（像素）組成。在光柵顯示器的熒光屏上生成一個對象，實質上是往幀緩存寄存器的相應單元中填入數(shù)據(jù)。所以

⊙對直線進行光柵化的時候，只能在顯示器所給定的有限個像素組成的點陣中確定最佳逼近于該直線的一組像素，用這些像素表示該直線。所以

⊙生成直線的主要工作是：快速找出距離直線最近的網(wǎng)格點，用這些網(wǎng)格點對應的像素表示該直線。3計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第3頁!像素逼近直線示意圖圖像元素可尋址點4計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第4頁!3.2.1基本增量算法注：上述討論只適合的情況，當時，只需將和的角色互換，即每次增加一個單位，每次增加?；驹隽克惴ㄒ步袛?shù)字微分分析器算法（DigitalDifferentialAnalyzer，DDA）。DDA是用數(shù)值方法求解微分方程的一種設備，即根據(jù)111和的一階導數(shù)，在和方向上漸進地以小步長移動，由此產生連續(xù)的像素坐標。5計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第5頁!3、提高速度的方法：

乘法用加法實現(xiàn)，每一個點坐標都可以由前一個坐標變化一個增量得到。設(xi,yi)是第i步得的直線上的點，則直線上第個i+1點是(xi+1,yi+1)，其中當Δx>Δy>0，即直線斜率小于1，應使x方向每次增加1，y方向最多增加1，此時取Δt=1/Δx；

同理,當Δy>Δx>0,直線斜率大于1，取Δt=1/Δy，所以(3.2)令，將參數(shù)區(qū)間[0，1]分為等份，即每次的增量為。6計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第6頁!圖中黑點表示用DDA法生成的直線4、直線的DDA算法程序voiddda(Graphicsg,intx1,intx2,inty1,inty2){intk;floatx,y,dx,dy;k=Math.abs(x2-x1);if(Math.abs(y2-y1)>k)k=Math.abs(y2-y1);dx=(float)(x2-x1)/k;dy=(float)(y2-y1)/k;//變化的增量x=(float)(x1);y=(float)(y1);for(inti=0;i<k;i++){

g.drawLine((int)(x+.5f),(int)(y+.5f),(int)(x+.5f),(int)(y+.5f));x=x+dx;y=y+dy;}}//endDDA

完成四舍五入7計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第7頁!算法背景設直線的起點坐標為，斜率為。下面就的情況來說明該算法。取為像素所在點的橫坐標（整數(shù)），令，直線上相鄰兩點的坐標滿足關系(3.3)一般來說，不一定是整數(shù)，所以也不一定是整數(shù)，因此要用靠近該點最近的網(wǎng)格點來近似。由于取整計算量較大，為了提高效率，Bresenham算法用下面的方法來避免使用取整運算。3.2.2Bresenham算法8計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第8頁!通過遞推的方式，高效地計算點序列和，由圖3.4可得(3.5)由式（3.3）～（3.5）可得=(3.6)9計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第9頁!算法的程序實現(xiàn)由式（3.3）和（3.4）可得假設直線段起始點的坐標分量和均為整數(shù)，則有m=(double)dy/(double)dx；e=m–0.5；for(i=0;i<dx;i++){g.drawLine(x,y,x,y);if(e>=0){y=y+1；e=e–1;}x=x+1；e=e+m;}該算法在計算直線斜率和誤差項時用到了小數(shù)與除法，可改用整數(shù)來避免除法，以提高算法的效率和減少算法的復雜性。由于算法中只用到誤差項的符號，因此可進行如下替換：。10計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第10頁!3.3圓的掃描轉換1、基本原理：

假設已選取Pi-1為第i-1個像素，則如果Pi-1在圓內，就要向圓外方向走一步，若Pi-1在圓外就要向圓內走一步。若Pi-1在圓上，則可以向圓內走一步，也可以向圓外走。xypiPi+1Pi-1BA(0,0)圖3.9對圓弧AB用正負法取點3.3.1正負法這樣用于表示圓弧的點均在理想圓弧附近且時正時負，因此稱為正負法。由于這種方法每走完一步，都要比較當前位置的函數(shù)值，以決定下一步的走向，因而也稱為逐點比較法。11計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第11頁!2）實現(xiàn)步驟第1步：x0=0，y0=R第2步：

求得Pi(xi,yi)后找點Pi+1的原則為：yPiBA(0,0)當Pi在圓內時(F(xi,yi)≤0)，要向右走一步得Pi+1，這是向圓外方向走去。取xi+1=xi+1,yi+1=yiPi+1當Pi在圓外時(F(xi,yi)>0)，

要向下走一步得Pi+1，這是向圓內方向走去，取xi+1=xi,yi+1=yi-1Pi+1用來表示圓弧的點均在圓弧附近且

F(xi,yi)時正時負

x12計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第12頁!算法的程序實現(xiàn)voidpnarc(Graphicsg,intradius){intx,y,f;x=0;y=0+radius;f=0;while(y>0){ g.drawLine(x,y,x,y); if(f>0){ f=f–2*y+1; y--; }else{ f=f+2*x+1;x++; }}if(y==0)g.drawLine(x,y,x,y);}13計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第13頁!1、基本原理考慮AB弧段，x每步增加1，從x=0開始，到x=y結束。即有：xi+1=xi+1

相應的yi+1則在兩種可能中選擇：yi+1=yi，或者

yi+1=yi-1。所以

選擇的原則是確定這兩個點哪一個更接近于圓弧。Pi-1HiLi即：設Pi-1是已選中的一個表示圓弧上的點，下一個點應從Hi或Li中選擇。設Hi和Li兩點的坐標分別為(xhi,yhi)和(xli,yli)14計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第14頁!2）di遞推公式設已選中的點Pi-1=(xi-1,yi-1)，則Hi和Li點的坐標分別為(xi,yi-1)和(xi,yi-1–1),Hi+1和Li+1的坐標分別為(xi+1,yi)和(xi+1,yi

–1)。因為x0=0,y0=R,x1=x0+1，所以d1=D(H1)+D(L1)=(12+y20-R2)+(12+(y0-1)2-R2)=3-2y0=3-2Rdi=(x2i+y2i-1-R2)+(x2i+(yi-1-1)2-R2)=2x2i+2y2i-1-2yi-1-2R2+1di+1=(xi+1)2+y2i-R2+(xi+1)2+(yi-1)2-R2=2x2i+4xi+2y2i-2yi-2R2+315計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第15頁!算法的程序實現(xiàn)voidbresenham_arc(Graphicsg,intradius){intx,y,d;x=0;y=radius;d=3-2*radius;while(x<y){ g.drawLine(x,y,x,y); if(d<0)d=d+4*x+6; else{d=d+4*(x-y)+10;y--;}x++;}if(x==y)g.drawLine(x,y,x,y);}Bresenham算法在候選的兩個像素中，總是選離圓弧最近的像素為圓弧的一個近似點，因此，它比正負法決定的像素更合理。16計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第16頁!橢圓弧的生成設橢圓的中心在原點，長短軸分別為a和b，且平行于坐標柚，則該橢圓的參數(shù)方程為，設頂點序列的第i個頂點為,則下一個頂點的坐標應滿足,

由此可得其中17計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第17頁!3.4.2掃描線算法特點：充分利用了相鄰像素之間的連續(xù)性，避免對像素的逐點判斷和反復求交運算，減少了計算量，提高了算法速度?；靖拍睿?）掃描線的連續(xù)性2）邊的連續(xù)性3）奇點基本思想先求出掃描線與多邊形邊的交點，利用掃描線的連續(xù)性求出多邊形與掃描線相交的連續(xù)區(qū)域，然后利用多邊形邊的連續(xù)性，求出下一條掃描線與多邊形的交點，對所有掃描線由下到上依次處理。掃描線算法是按掃描線的順序計算出掃描線與多邊形的相交區(qū)間，然后用要求的顏色填充這些區(qū)間內的像素。18計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第18頁!交點序列具有以下性質：1)交點個數(shù)l是偶數(shù)；2)掃描線上的區(qū)間 l–1位于多邊形P內（圖3.13中的實線段部分），其余區(qū)間都在P外（圖3.13中的虛線段部分），兩類區(qū)間沿掃描線相間排列。這些性質就稱為掃描線的連續(xù)性。P0P1P2P3P4P5P6P7P8xe01xe22xe33xe74xe65xe46圖3.13掃描線的連續(xù)性圖中----表示在多邊形外的區(qū)間──表示在多邊形內的區(qū)間根據(jù)掃描線的連續(xù)性，只需求出掃描線與多邊形P的邊界的所有交點，就可確定掃描線位于多邊形P內的區(qū)間。19計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第19頁!但當掃描線與多邊形P的邊界的交點恰好是P的頂點時（該交點稱為奇點），必須按不同的情況區(qū)別對待。3奇點的處理上述兩種形式的連續(xù)性都基于一個幾何事實：每一條掃描線與多邊形P的邊界的交點個數(shù)都是偶數(shù)（包括零）。設多邊形P的頂點為這些頂點可分為兩類：極值點和非極值點。如果，則稱頂點為極值點（如圖3.15中的）；否則稱為非極值點（如圖3.15中的）。圖3.15一個多邊形與若干條掃描線P8P0P1P2P3P4P5P6P720計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第20頁!4算法的實現(xiàn)步驟與數(shù)據(jù)結構對于每一條掃描線，多邊形的填充過程可分為以下4步：計算掃描線與多邊形各邊的交點，設交點個數(shù)為n；把所有的交點按x值遞增的順序進行排列；將排序后的第1個與第2個交點，第3個與第4個交點，……第n-1個與第n個交點配對，每對交點就代表掃描線與多邊形的一個相交區(qū)間；把相交區(qū)間內的像素置成多邊形的顏色，相交區(qū)間外的像素置成背景色。1234上述方法要計算每一條掃描線與所有邊的交點，計算量很大。為提高效率，可以對每一條掃描線，僅對與它相交的多邊形進行求交運算。21計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第21頁!綜上，AEL中的節(jié)點應由如下四個域組成：:邊的上端點的y坐標，即與該邊相交的最高掃描線號。

x

:邊與掃描線的交點的x坐標。:從當前掃描線到下一條掃描線間的x坐標的增量，即邊的斜率的倒數(shù)。Next

:指向下一條邊的指針。新邊表為方便活性邊表的建立與更新，還要為每一條掃描線建立一個新邊表（NewEdgeList,NEL），存放在該掃描線上第一次出現(xiàn)的邊。也就是說，如果某邊的較低端點為，則該邊放在掃描線的新邊表中。注意：水平邊不放到任何掃描線的NEL中，即水平邊不參加分類。NEL中的節(jié)點結構與AEL相同，只是x在這里不再表示邊與掃描線的交點，而是表示該邊較低端點的x坐標值。22計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第22頁!-5/3516/3AELe0e54214AEL在y=3掃描線上的狀態(tài)AEL-5/3511/3e0e54216AEL在y=4掃描線上的狀態(tài)AEL-5/352e0e49016AEL在y=5掃描線上的狀態(tài)…0102e1e210-7/411/2AEL在y=8掃描線上的狀態(tài)AEL97/341/3e39016e4圖3.18新邊表NEL123456e11002△xxymaxnexte49016e54212圖3.17多邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e6e2109-7/4e3997/357e0-5/323計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第23頁!對多邊形P的每一非水平邊（i=0,1,…,n）上的各像素進行向右求補運算，當相對于所有邊的求補運算都完成后，多邊形的掃描轉換也隨之完成。圖3.20a為給定的多邊形；b為對區(qū)域賦初值；c、d、e和f表示逐邊向右求補。(c)(d)(f)(e)(a)(b)圖3.20邊緣填充算法的過程3、邊緣填充算法的實現(xiàn)24計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第24頁!intred=Color.red.getRGB();publicImageboundary(){Imageimage;//定義Image對象for(i=0;i<7;i++){dy=p[i+1].y-p[i].y;dx=(p[i+1].x-p[i].x)/dy;if(dy>0)x=p[i].x;elsex=p[i+1].x; ymax=(Math.max(p[i].y,p[i+1].y)); ymin=(Math.min(p[i].y,p[i+1].y));for(y=ymin+1;y<=ymax;y++){x=(int)(x+dx+.5);if(pixels[y*w+x]==red)pixels[y*w+x+1]=red;elsepixels[y*w+x]=red;}}ImageProducerip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}圖3.17多邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e625計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第25頁!3、邊界標志算法實例XXXXXXP2(9,6)XXXXXXP0(2,5)P1(2,11)P3(15,9)P4(15,3)P5(12,1)P6(7,1)XXXXxXXxXXXXXXY=2Y=3Y=4Y=5Y=626計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第26頁!區(qū)域填充是指先將區(qū)域內的一點（常稱種子點）賦予給定顏色，然后將這種顏色擴展到整個區(qū)域內的過程。3.5區(qū)域填充區(qū)域是指已經表示成點陣形式的像素集合。在光柵圖形中，區(qū)域可采用內點表示和邊界表示兩種形式進行描述。1、內點表示法：把位于給定區(qū)域內的所有像素一一列舉出來的方法稱為內點表示法。2、邊界表示法：把位于給定區(qū)域邊界上的像素一一列舉出來的方法稱為邊界表示法。3.5.1區(qū)域的表示和類型圖3.22內點表示的區(qū)域圖3.23邊界表示的區(qū)域27計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第27頁!3）4連通區(qū)域也可理解成8連通區(qū)域，即4連通能達到的8連通肯定能達到，4連通只是8連通的一種特殊情況。連通不是指邊界而是邊界內的區(qū)域這里是X圍起來的區(qū)域·號是區(qū)域X是邊界8連通而非4連通的地方圖3.26內點表示的八連通區(qū)域圖3.27邊界表示的八連通區(qū)域28計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第28頁!基本思想設（x,y）是內點表示的一區(qū)域G內的一點，old_color是G的原色。先?。▁,y）點為種子點，測試其顏色，若等于old_color，說明是區(qū)域內一點，則將其置為新的顏色new_color，否則說明該點不在區(qū)域G內，則停止填充；然后將該點周圍的四個點（四連通）或八個點（八連通）作為新的種子點進行同樣的處理，通過這種擴散完成對整個區(qū)域的填充。顯然，這一過程是用遞歸實現(xiàn)的。3.5.2遞歸算法29計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第29頁!3.5.3掃描線種子填充算法1、基本思想：從給定的種子點開始，先填充當前掃描線上種子點所在的一區(qū)段，然后確定與這一段相鄰的上下兩條掃描線上位于區(qū)域內的區(qū)段（需要填充的區(qū)間），從這些區(qū)間上各取一個種子點依次把它們存起來，作為下次填充的種子點。反復進行這過程，直到所保存的各區(qū)段都填充完畢。30計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第30頁!步驟3：（區(qū)段填充）從種子點（x,y）開始，沿縱坐標為y的當前掃描線向左右兩個方向逐個像素用新的顏色值進行填充，直到邊界為止即像素顏色等于邊界色。設區(qū)間兩邊界的橫坐標分別為xleft和xright；步驟4：在與當前掃描線相鄰的上下兩條掃描線上，以區(qū)間[xleft,xright]為搜索范圍，求出需要填充的各小區(qū)間，把各小區(qū)間中最右邊的點并作為種子點壓入堆棧，轉到步驟2。12種子點xleftxright31計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第31頁!publicvoidscan(int[]pixels,Pointpoint,intboundary_color,intnew_color,intold_color){intx,y,savex,xright,xleft;Pointp;Stackstack=newStack();//設置堆棧對象stack.push(point);//壓棧booleanspan_need_fill;while(!stack.empty()){p=(Point)(stack.pop());//出棧，從堆棧中取一像素作為種子像素x=p.x;y=p.y;savex=x;//保存橫坐標x的值while(pixels[y*w+x]!=boundary_color){ pixels[y*w+x]=new_color;x++;}//從種子像素開始向右填充到邊界

xright=x-1;//保存線段的右端點

x=savex-1;x-1填充過程xxright4、程序實現(xiàn)32計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第32頁!//繼續(xù)向右檢查以防有遺漏

while((pixels[y*w+x]==boundary_color||pixels[w*y+x]!=new_color)&&x<=xright)x++;}//在上一條掃描線上檢查完

如果種子點在這里12123xleftxright33計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第33頁!1210222233222225、實例034計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第34頁!(a)(b)(c)(d)圖3.30點陣式字符及其變化下圖(a)所示的是字母“P”的點陣式表示。(b)-(d)即以(a)為原型的變化例子。其中，(b)表示變成粗體字，(c)表示旋轉90o,(d)表示變成斜體字。35計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第35頁!3.7光柵圖形的反走樣算法3.7.1光柵圖形的走樣現(xiàn)象采用本章介紹的算法在光柵圖形顯示器上繪制的非水平且非垂直的直線或多邊形邊界，會或多或少地呈現(xiàn)鋸齒狀。這是由于采用離散量表示連續(xù)量而引起的。圖形信號是連續(xù)的，而它們在光柵顯示器上對應的圖形則是由一系列相同亮度的離散像素組成。用離散的像素表示連續(xù)的直線或多邊形的邊界必然會引起圖形的失真，即光滑的線段變成了階梯的形狀，這種現(xiàn)象就稱為走樣。用于減輕或消除這種效果的技術就稱為反走樣。36計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第36頁!種是提高硬件的分辨率。如把圖形顯示器的分辨率提高一倍，直線經過兩倍的像素，鋸齒增加了一倍，但同時每個階梯的寬度也減小了一半，因此顯示出的直線看起來就平滑了一些。這種方法是以4倍的存儲器代價和2倍的掃描轉換時間獲得的，花費較大，而且它只能減輕而不能從根本上消除鋸齒問題，另外，分辨率不可能無限制地提高，因此這并不是最好的方法。提高分辨率的方法有兩種：3.7.2提高分辨率的反走樣算法37計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第37頁!基本思想假定每個像素都是一個具有一定面積的小區(qū)域，將直線段看作具有一定寬度的狹長矩形（如下圖所示）。這樣，當線段通過某像素時，可以求出兩者相交區(qū)域的面積，根據(jù)相交面積的大小來確定該像素的顏色值或灰度值。圖3.35有寬度的線段3.7.3區(qū)域采樣的反走樣算法38計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第38頁!如圖3.37，情況（a）的陰影面積為；情況（b）的陰影面積為。這里的陰影面積是介于0～1之間的正數(shù)，用它乘以像素的最大灰度值，再取整，就可得到像素的顯示灰度值。圖3.38陰影面積的離 散計算為了簡化運算，有時候還可以采用離散的方法。即將屏幕像素均分成n個子像素，計算中心點落在直線段內的子像素的個數(shù)k，那么該像素的亮度就是最大灰度值乘以相交區(qū)域面積的近似值k/n。圖3.38所示是n=9，k=3，近似面積為1/3的情況。39計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第39頁!基本思想這里只討論用離散的方法來實現(xiàn)該算法，即將像素均分成n個子像素，每個子像素的面積為1/n，計算每個子像素對原像素的貢獻，并保存在一張二維的加權表中；求出所有中心落在直線段內的子像素組成的集合，并計算這些子像素對原像素的亮度貢獻之和的值，該值乘以像素的最大灰度值就得到該像素最終要顯示的亮度。3.7.4加權區(qū)域采樣的反走樣算法40計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第40頁!3.2.1基本增量算法設直線滿足，由于直線的斜率小于等于1，所以，該直線的掃描轉換可從最左端開始，每次遞增一個單位，對每個，相應的有，則所以，每增加一個單位，只需加上一個，這樣就去掉了乘法運算，提高了算法效率。在該算法中，直線上的所有點的和值可由前一點的值加一個基本增量得到，所以該算法稱為基本增量算法。3.2.1基本增量算法(DDA-digitaldifferential analyzer)

1、基本思想：41計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第41頁!2、直線的表示：

設直線的起點坐標為(xs，ys)，終點坐標為(xe,ye)，令Δx＝xe-xs，Δy＝y(tǒng)e-ys，則直線參數(shù)方程為目標：能快速地求出能很好地表示直線的像素第步時(3.1)42計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第42頁!下圖中，用公式（3.2）求得的直線上的點用空心圓表示，但顯示時要用像素來表示，即采用四舍五入的辦法得到最靠近空心圓點的像素，用這些像素（下圖中的實心圓點）來表示直線。圖中實心圓點表示用DDA方法生成的直線43計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第43頁!實例設給定直線的起點坐標為(0，0)，終點坐標為(9，6)，則上述DDA算法畫出的直線如下圖所示。DDA方法所畫直線圖DDA算法缺點：需要進行浮點數(shù)運算，產生一個像素要做兩次加法和兩次取整運算，運行效率低且取整運算不利于硬件實現(xiàn)。44計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第44頁!當B在A的下面時，，此時應取C點作為；當B在A的上面時，，則應取D點作為。BACD圖3.4的幾何意義設圖3.4中已得到第個顯示的點，B點是直線與第列網(wǎng)格線的交點，則第個顯示的點只能從C或D點中去選。設A為CD邊的中點，令誤差項(3.4)算法思想：45計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第45頁!注：式（3.5）和（3.6）是根據(jù)圖3.4所示的情況推出的，容易驗證，式（3.5）和（3.6）對圖3.5所示的兩種情況也成立。CBADBACD圖3.5的幾何意義的其他兩種情況46計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第46頁!改進后的算法程序voidbresenham(Graphicsg,intxs,intys,intxe,intye) {intdx=xe-xs; intdy=ye-ys; inte=2*dy-dx; intx=xs; inty=ys; for(inti=0;i<dx;i++){g.drawLine(x,y,x,y);//畫點（x,y）if(e>=0){y=y+1;e=e-2*dx;}x=x+1;e=e+2*dy;} }注：上面討論了的情況，如果，則需把和的地位互換。如果或，程序中 或需換成或，同時也應相應地改變。47計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第47頁!2、正負法的具體實現(xiàn)1）圓的表示：設圓的圓心為(0,0),半徑為R，則圓的方程為：

F(x,y)=x2+y2–R2=0

ypiPi+1Pi-1BA(0,0)圖3.9對圓弧AB用正負法取點如何判斷一個點和圓的內外關系當點(x,y)在圓內時，F(xiàn)(x,y)<0；

當點(x,y)在圓外時，F(xiàn)(x,y)>0；當點(x,y)在圓上時，F(xiàn)(x,y)=0。48計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第48頁!當時，假設已經算出F(xi,yi)，如何計算F(xi+1,yi+1)？？？由上可知。如果的值已算出，計算 時可分為兩種情況：(3.9)當時，(3.10)由式（3.9）和式(3.10)知，49計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第49頁!3.3.2Bresenham算法假設圓心(0,0)為原點，考慮AB弧的畫法，顯示一個整圓時，只要在顯示AB上任一點(x,y)時，同時顯示在圓周上其它七個對稱點

(y,x),(y,-x),(x,-y),(-x,-y),(-y,-x),(-y,x),(-x,y)。7個對稱點50計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第50頁!2、Bresenham的具體實現(xiàn)1）令D(P)=(x2+y2)-R2，表示點P到原點的距離平方與圓的半徑的平方之差。令：當di=0時，點Hi和Li距弧AB的距離相等當di<0時，|D(Hi)|<|D(Li)|，取Hi來顯示弧AB當di≥0時，|D(Hi)|>|D(Li)|，取Li來顯示弧AB。Pi-1HiLidi=D(Hi)+D(Li)51計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第51頁!di=2x2i+2y2i-1-2yi-1-2R2+1(3.13)di+1=2x2i+4xi+2y2i-2yi-2R2+3(3.14)當di<0時,點Hi被選中,xi=xi-1+1，yi=yi-1，由(3.13)-(3.14)得

di+1=di+4xi+2=di+4xi-1+6(3.15)當di≥0時,點Li被選中,

xi=xi-1+1，yi=yi-1-1，由(3.13)-(3.14)得

di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+10(3.16)52計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第52頁!基本思想按一定方式計算給定圓弧軌跡上的一系列頂點，然后用連接相鄰點的一系列直線段來逼近圓弧。用正多邊形迫近圓弧法設圓弧所在圓的半徑為R，圓弧的起始角和終止角分別為和，把圓弧分割成份，則相鄰兩個頂點之間的夾角為。設頂點序列的第個點為，為該點的幅角。則下一個頂點的坐標為或表示為矩陣形式3.3.3圓的多邊形迫近法53計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第53頁!3.4.1多邊形的掃描轉換1、表示方法：頂點表示和點陣表示1）頂點表示是用多邊形的頂點的序列來描述多邊形，該表示幾何意義強、占內存少，但它不能直觀地說明哪些像素在多邊形內。2）點陣表示是用位于多邊形內的像素的集合來描述多邊形，該方法雖然沒有多邊形的幾何信息，但具有面著色所需要的圖像表示形式。3.4多邊形的掃描轉換圖3.11多邊形頂點表示P1P0P2P3P4圖3.16多邊形點陣表示

多邊形的掃描轉換就是把多邊形的頂點表示轉換為點陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內部的各個像素，并為幀緩存內的各個對應元素設置相應的灰度或顏色。54計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第54頁!1掃描線的連續(xù)性設多邊形P的頂點，將各頂點的縱坐標按遞減順序排列,即設當前掃描線，，與多邊形P的邊的交點記為。設為與P的邊界各交點橫坐標的遞增序列，該序列稱為交點序列。(3.21)當知道一條掃描線上一點與多邊形的內外關系時，即可確定該掃描線上所有點與多邊形之間的內外關系。55計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第55頁!2邊的連續(xù)性掃描線的連續(xù)性知，序列（3.21）和（3.22）的點滿足以下關系：（1）兩序列元素的個數(shù)相等，即；（2）點（）與（）位于多邊形P的同一邊上（見圖3.14），所以可由下式計算(3.23)以上性質稱為邊的連續(xù)性。若,

成立，則掃描線與掃描線和多邊形P相同的邊相交，由圖3.14邊的連續(xù)性P0P1P2P3P4P5P6P7P8xe01xe22xe33xe74xe65xe46xd01xd65xd46設當前掃描線的下一條掃描線為，，且,設位于掃描線上的交點序列為（3.22）56計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第56頁!為使每一條掃描線與多邊形P的邊界的交點個數(shù)始終為偶數(shù)，規(guī)定當奇點是多邊形P的極值點時，該點按兩個交點計算，否則按一個交點計算。圖3.16非極值點的處理（a）（b）實際計算中，可如下處理非極值點：若是非極值點，則將,兩邊中位于掃描線上方的那條邊在處截去一個單位長，這樣就能保證掃描線只和，中的一邊相交，只有一個交點。57計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第57頁!使用增量計算時，還要知道一條邊何時不再與下一條掃描線相交，以及時地把該邊從活性邊表中刪除，因此需要記錄下與該邊相交的最高掃描線號?；钚赃叡砼c當前掃描線相交的邊稱為活性邊。把活性邊與掃描線的交點按x坐標遞增的順序放在一個鏈表中，該鏈表就稱為活性邊表（ActiveEdgeList,AEL）。設多邊形某一條邊的方程為，當前掃描線與該邊的交點坐標為，則下一條掃描線與該邊的交點不需要重新計算，只要加一個增量即可。因為此時有其中為常數(shù)，并規(guī)定時，。58計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第58頁!具體例子圖3.18和3.19是圖3.17中多邊形的新邊表NEL和活性邊表AEL。在左圖中表示邊，各頂點為[P0P1…P6]=[(2,5)(2,10)(9,6)(16,9)(16,4)(12,2)(7,2)]

其中，是非極值點，在分類前已對邊作了預處理，即分別在處把它們截去一個單位長，這樣保證掃描線只和兩邊中的一邊相交，求得一個交點，是水平邊，不參加分類。圖3.17邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e659計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第59頁!3.4.3邊緣填充算法1、特點：采用對圖像進行逐位求補的方法，免去對邊排序的工作量。2、預備知識：假設某像素的顏色是C，對該像素做偶數(shù)次求補運算后，其顏色還是C；做奇數(shù)次求補運算后，其顏色變?yōu)镃。在光柵圖形中，如某區(qū)域已著上值為M的某種顏色，則上述求補運算的結果是：對區(qū)域作偶數(shù)次求反運算后，該區(qū)域的顏色不變；作奇數(shù)次求反運算后，該區(qū)域的顏色則變成值為M的顏色。60計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第60頁!3.4.4邊界標志算法1、基本原理：首先用一種特殊的顏色在幀緩沖器中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來。然后再把位于多邊形內的各個像素著上所需的顏色。2、算法具體實現(xiàn)步驟：步驟1：以值為boundary_color的特殊顏色勾畫多邊形P的邊界。設多邊形頂點為Pi=(xi,yi),0≤i≤n，xi,yi均為整數(shù)；置Pn+1=P0。每一條掃描線上著上這種特殊顏色的點的個數(shù)必定是偶數(shù)(包括零)。61計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第61頁!//maxx、maxy、minx、miny是獲得的多邊形最小矩形包圍盒邊界值publicImageinterior(){Imageimage;intmaxx=150,minx=20,maxy=120,miny=20,l;intin_flag；//多邊形內部標志變量for(y=miny;y<=maxy;y++){in_flag=0;for(x=minx;x<maxx;x++){l=pixels[y*w+x];if(l==red){if(in_flag==0)in_flag=1;elsein_flag=0;}if(in_flag==1)pixels[y*w+x]=red;}}ImageProducerip=newMemoryImageSource(w,h,pixels,0,w);image=createImage(ip);returnimage;}步驟2：設in_flag是一布爾變量。對每一條掃描線從左到右進行搜索，如果當前像素位于多邊形P內，則in_flag=true，需要填上值為polygon_color的顏色；否則該像素在多邊形P外，需要填上值為background_color的顏色。圖3.17多邊形P0P1…P6P0P3P4e410155P1P2P5P6P0e0e2e3e5e1e662計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第62頁!實例最終結果XXXXXXXXXX

63計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第63頁!1）4連通的區(qū)域:取區(qū)域內任意兩點，在該區(qū)域內若從其中一點出發(fā)通過上、下、左、右四種運動可到達另一點。圖3.24四個方向的運動2）8連通的區(qū)域:取區(qū)域內任意兩點，若從其中任一點出發(fā)，在該區(qū)域內通過沿水平方向、垂直方向和對角線方向的八種運動可到達另一點。圖3.25八個方向的運動3、區(qū)域的連通性64計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第64頁!但是兩者的邊界不盡相同。如果圖中標有·號的像素組成的區(qū)域作為4連通區(qū)域，則其邊界由圖中的標有△號的像素組成。如果將該區(qū)域作為8連通的區(qū)域，則其邊界由圖中標有△號和×號的兩種像素組成。圖3.28四連通區(qū)域與八連通區(qū)域的不同邊界因為如果區(qū)域是8連通的，△邊界不能將區(qū)域有效封堵，X的位置和區(qū)域也是連通的。用于八連通區(qū)域的填充算法可用于四連通區(qū)域的填充，但用于四連通區(qū)域的填充算法并不適用于八連通區(qū)域的填充。65計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第65頁!publicvoidflood_fill_8(int[]pixels,intx,inty,intold_color,intnew_color){if(x<w&&x>0&&y<h&&y>0){if(pixels[w*y+x]==old_color){pixels[w*y+x]=new_color; flood_fill_8(pixels,x,y+1,old_color,new_color); flood_fill_8(pixels,x,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y,old_color,new_color); flood_fill_8(pixels,x+1,y,old_color,new_color); flood_fill_8(pixels,x+1,y+1,old_color,new_color); flood_fill_8(pixels,x+1,y-1,old_color,new_color); flood_fill_8(pixels,x-1,y+1,old_color,new_color); flood_fill_8(pixels,x-1,y-1,old_color,new_color);}}}算法實現(xiàn)66計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第66頁!2、算法步驟：步驟1：（初始化）將算法設置的堆棧置為空。將給定的種子點（x,y）壓入堆棧；步驟2：（出棧）如果堆棧為空，算法結束；否則取棧頂元素（x,y）作為種子點；12棧種子67計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第67頁!3、算法的關鍵原則：1）搜索原則：從前一個填充的區(qū)間（區(qū)間的范圍為xleft,xright）作為后一條掃描線種子點尋找的范圍。2）種子點的位置原則：（1）當xleft,xright范圍比較大時，當前區(qū)間的種子點可能是邊界前一點；（2）當xleft,xright范圍比較小，當前區(qū)間的種子點就是xright位置。3）填充原則：從種子點往左，右填，填到邊界。1212如果種子點在這里xleftxright搜索確定種子點種子點填充68計算機圖形學基本光柵圖形算法共77頁，您現(xiàn)在瀏覽的是第68頁!while(pixels[y*w+x]!=boundary_color){pixels[y*w+x]=new_color;x--;}//從種子像素開始向左填充到邊界，以上兩步完成區(qū)間填充xleft=x+1;//保存線段的左端點x=xleft;y=y+1;while(x<=xright){//在上一條掃描線上檢查是否需要填充span_need_fill=false;while(pixels[w*y+x]!=boundary_color&&pixels[w*y+x]!=new_color&&x<=xright){//待填充的線段span_need_fill=true;x++;}//待填充的線段處理完if(span_need_fill){//如果區(qū)間需要填充，則將其右端點作為

p=newPoint(x-1,y);