計(jì)算機(jī)圖形學(xué)-多邊形的掃描轉(zhuǎn)換（基本光柵圖形算法）4395

計(jì)算機(jī)圖形學(xué)——多邊形的掃描轉(zhuǎn)換（基本光柵圖形算法）?、多邊形掃描轉(zhuǎn)換在光柵圖形中，區(qū)域是由【相連的】像素組成的集合，這些像素具有【相同的】屬性值或者它們位于某邊界線的內(nèi)部1、光柵圖形的?個(gè)基本問(wèn)題是把多邊形的頂點(diǎn)表?轉(zhuǎn)換為點(diǎn)陣表?。這種轉(zhuǎn)換成為多邊形的掃描轉(zhuǎn)換。2、多邊形的掃描轉(zhuǎn)換與區(qū)域填充問(wèn)題是怎樣在離散的像素集上表??個(gè)連續(xù)的?維圖形。3、多邊形有兩種重要的表??法：（1）頂點(diǎn)表?：?多邊形的定點(diǎn)序列來(lái)表?多邊形優(yōu)點(diǎn)：直觀、?何意義強(qiáng)、占內(nèi)存少、易于進(jìn)??何變換缺點(diǎn)：沒(méi)有明確指出那些象素在多邊形內(nèi)，故不能直接?于上?（2）點(diǎn)陣表?：是?位于多邊形內(nèi)的象素集合來(lái)刻畫多邊形缺點(diǎn)：丟失了許多?何信息（eg:邊界、頂點(diǎn)等）但是【點(diǎn)陣表?是光柵顯?系統(tǒng)顯?時(shí)所需的表現(xiàn)形式。】多邊形的掃描轉(zhuǎn)換就是把多邊形的頂點(diǎn)表?轉(zhuǎn)換為點(diǎn)陣表?，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素，并將幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置相應(yīng)的灰度或顏?。實(shí)際上就是多邊形內(nèi)的區(qū)域的著?過(guò)程。4、多邊形分類?、X掃描線算法X掃描線算法填充多邊形的基本思想是按掃描線順序，計(jì)算掃描線與多邊形的相交區(qū)間，再?要求的顏?顯?這些區(qū)間的象素，即完成填充?作。區(qū)間的端點(diǎn)可以通過(guò)計(jì)算掃描線與多邊形邊界線的交點(diǎn)獲得。如掃描線y=3與多邊形的邊界相交于4點(diǎn)（2,3）、（4,3）、（7,3）、（9,3）這四個(gè)點(diǎn)定義了掃描線從x=2到x=4，從x=7到x=9兩個(gè)落在多邊形內(nèi)的區(qū)間，該區(qū)間內(nèi)像素應(yīng)取填充?。算法的核?是按x遞增順序排列交點(diǎn)的x坐標(biāo)序列。由此可得到掃描線算法步驟如下：算法步驟：1.確定多邊形所占有的最?掃描線數(shù)，得到多邊形定點(diǎn)的最?最?值（y和ymin）；max2.從ymin到每次??條掃描線進(jìn)?填充；ymax3.對(duì)?條掃描線填充的過(guò)程分為四個(gè)步驟：a)求交點(diǎn)；b)把所有交點(diǎn)按遞增順序排序；c)交點(diǎn)配對(duì)（第?個(gè)和第?個(gè)，第三個(gè)和第四個(gè)）；d)區(qū)間填?。把相交區(qū)間內(nèi)的像素置成多邊形的顏?，相交區(qū)間外的像素置成背景?。掃描線與多邊形頂點(diǎn)相交時(shí)，交點(diǎn)的取舍問(wèn)題【交點(diǎn)應(yīng)保證為偶數(shù)個(gè)】交點(diǎn)問(wèn)題的處理：為了計(jì)算每條掃描線與多邊形各邊的交點(diǎn)，最簡(jiǎn)單的?法是把多邊形的所有邊放在?個(gè)表中。在處理每條掃描線的時(shí)候，按順序從表中取出所有的邊，分別與掃描線求交。但這個(gè)算法效率很低因?yàn)殛P(guān)鍵問(wèn)題是求交!求交是很可怕的，求交的計(jì)算量?常?。‘排序、配對(duì)、填?總是要的！掃描轉(zhuǎn)換算法重要的意義是提出了圖形學(xué)?兩個(gè)重要的思想：（1）掃描線：當(dāng)處理圖形圖像時(shí)按?條條掃描線處理（2）增量的思想。已經(jīng)知道X-掃描線算法效率低是因?yàn)榍蠼?煩，那求教點(diǎn)的時(shí)候能否也采?增量思想，每條掃描線的y值都知道，關(guān)鍵是求x值?？梢詮娜齻€(gè)??改進(jìn)：1、在處理?條掃描線時(shí)，僅對(duì)與它相交的多邊形的邊（有效邊）進(jìn)?求交運(yùn)算。2、考慮掃描線的連貫性，也就是當(dāng)前掃描線與各邊交點(diǎn)順序與下?條掃描線邊與各邊的交點(diǎn)順序很可能相同或?常相似。3、考慮多邊形的連貫性，即當(dāng)某條邊與掃描線相交時(shí)它很可能與下?條掃描線也相交。為了避免求交運(yùn)算，需要引進(jìn)?套特殊的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：(1)活性邊表（AET）把當(dāng)前掃描線相交的邊稱為活性邊，并把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在?個(gè)鏈表中。上圖中P4P1、P3P2是活性邊，P4P3、P1P2是?活性邊2）節(jié)點(diǎn)內(nèi)容x:當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)Δx:從當(dāng)前掃描線到下?條掃描線間x的增量ymax:該邊所交的最?掃描線的坐標(biāo)值next:指向下?條邊的指針另外，需要知道?條邊何時(shí)不再與下?條掃描線相交，以便及時(shí)把它從有效邊表中刪除出去，避免下?步進(jìn)??謂的計(jì)算。?個(gè)具體的例?：（3）新邊表（NET）為了?便活性邊表的建?與更新，?來(lái)存放多邊形的邊的信息，分為4個(gè)步驟1.構(gòu)造?個(gè)縱向鏈表，長(zhǎng)度為多邊形所占有的最?掃描線數(shù)，鏈表的每個(gè)結(jié)點(diǎn)稱為吊桶，對(duì)應(yīng)多邊形覆蓋的每?條掃描線。2.新邊表（NET）掛在與【該邊低端y值相同】的掃描線桶中。也就是說(shuō)，存放在該掃描線第?次出現(xiàn)的邊也就是說(shuō)，如果某邊的較低端點(diǎn)為ymin,則該邊就放在掃描線ymin的新邊表中。注意：?平邊不放到任何掃描線的NEL中，即?平邊不參與分類。ymax：該邊的最?值；xmin：該邊較低點(diǎn)的x坐標(biāo)值xmin;1/k：該邊的斜率next：指向下?條具有相同較低端y坐標(biāo)的邊的指針從上邊的這個(gè)NET表?就知道多邊形是從哪?開(kāi)始的從這個(gè)表?只有1、3、5、7處有邊，從y=1開(kāi)始做，?1這條線上有兩條邊進(jìn)來(lái)了，然后就把這兩條邊放?活性表來(lái)處理。3.每做?次新的掃描時(shí)，要對(duì)已有的邊進(jìn)?三個(gè)處理：1.是否被去除掉；2.若不被去除掉，就要對(duì)它的數(shù)據(jù)進(jìn)?更新，x=x+1/k；3.是否有新的邊進(jìn)來(lái)，新的邊在NET?，可以插?排序插進(jìn)來(lái)。這個(gè)算法過(guò)程從來(lái)沒(méi)有求交，這套數(shù)據(jù)結(jié)構(gòu)使得你不?求交點(diǎn)！避免了求交運(yùn)算。結(jié)：為提?算法效率:（1）增量的思想；（2）連貫性思想；（3）構(gòu)建?套特殊的數(shù)據(jù)結(jié)構(gòu)。【缺點(diǎn)】這?的區(qū)間端點(diǎn)通過(guò)計(jì)算掃描線與多邊形邊界的交點(diǎn)獲得，所以待填充區(qū)域的邊界線必須預(yù)先知道，因此它的缺點(diǎn)所在是?法實(shí)現(xiàn)對(duì)未知邊界的區(qū)域填充。、邊緣填充算法本原理采?對(duì)圖像進(jìn)?逐位求反的?法，免去對(duì)邊排序的?作量。對(duì)顏?M作偶數(shù)次求反運(yùn)算，其結(jié)果還是M，?對(duì)M作奇數(shù)次求反運(yùn)算的結(jié)果是M的反M。在光柵圖形中，如某區(qū)域已著上值為M的某種顏?，則上述求反運(yùn)算得到的結(jié)果是：對(duì)區(qū)域作偶數(shù)次求反運(yùn)算后，該區(qū)域的顏?不變；作奇數(shù)次求反運(yùn)算后，該區(qū)域的顏?則變成值為反M的顏?。實(shí)現(xiàn)：對(duì)多邊形P的每???平邊上的各像素做向右求反運(yùn)算即可，見(jiàn)下圖，其中(a)為給定的多邊形；(b)為對(duì)區(qū)域賦初值；(c)，(d)，(e)和(f)表?逐邊向右求反。五、邊界標(biāo)志算法基本原理：?先??種特殊的顏?在幀緩沖器中將多邊形的邊界（?平邊的部分邊界除外）勾畫出來(lái)。然后再把位于多邊形內(nèi)的各個(gè)像素著上所需的顏?。實(shí)現(xiàn)原理：步驟1：以值為boundary-color的特殊顏?勾畫多邊形P的邊界。設(shè)多邊形頂點(diǎn)為Pi=(xi,yi),0≤i≤n，xi,yi均為整數(shù)；置Pn+1=P0。每?條掃描線上著上這種特殊顏?的點(diǎn)的個(gè)數(shù)必定是偶數(shù)(包括零)。pixels[]是?個(gè)整數(shù)數(shù)組，表?像素的顏?。publicImageboundary(){Imageimage;for(i=0;i<=n;i++)//多邊形的邊數(shù){dy=p[i+1].y-p[i].y;dx=(p[i+1].x-p[i].x)/dy;if(dy>0)//?平邊不考慮{x=p[i].x;}else{x=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]==blue)//邊界顏?藍(lán)?{pixels[y*w+x+1]=blue;}else{pixels[y*w+x]=blue;}}}ImageProducerip=newMemoryImageSource(w,h,pixels,0,w);//通過(guò)MemoryImageSource將數(shù)組中的像素產(chǎn)??個(gè)圖像，w,h分別表其寬度和?度image=createImage(ip);returnimage；}

步驟2：設(shè)in_flag是?布爾變量。對(duì)每?條掃描線從左到右進(jìn)?搜索，如果當(dāng)前是像素位于多邊形P內(nèi)，則in_flag=true，需要填上值為polygon_color的顏?；否則該像素在多邊形P外，需要填上值為background_color的顏?。//maxx、maxy、minx、miny是獲得的多邊形最?矩形包圍盒邊界值publicImageinterior(){Imageimage;intmaxx=150,minx=20,maxy=120,miny=20,l;for(y=miny-1;y<=maxy;y++){in_flag=0;//多邊形內(nèi)部標(biāo)志變量for(x=minx-1;x<=maxx-1;x++){l=pixels[y*w+x];//獲得當(dāng)前像素顏?以判斷是否是邊界?//多邊形邊界顏?blueif(l==blue){if(in_flag==0)//如果是邊界，且第?/三次碰到邊界，就置flag為1，表明其后的象素要置成多邊形的顏?{in_flag=1;}else//如果是第?/四次遇到邊界，就置flag為0，對(duì)其后的元素置背景?為??。{in_flag=0;}