計(jì)算機(jī)圖形學(xué) 3多邊形

計(jì)算機(jī)圖形學(xué)

學(xué)時(shí)：48

第一章緒論1

第二章直線與直線的圖形3

第四章二次曲線4

第五章裁剪6

第六章曲線曲面4

第七章圖形變換2

考試2

第三章多邊形

■1多邊形的概念

■2多邊形的填充

■3polygonfill-areaalgorithm

■4反走樣基礎(chǔ)

■3.1多邊形的概念

■一多邊形的分類

■多邊形：由一些首尾連接的線段構(gòu)成的圖形，

線段為多邊形的邊線段的端點(diǎn)成為多邊形的頂

點(diǎn)。

■多邊形分為凸多邊形和凹多邊形。

■多邊形的特征:

■Vertex:P15P2,.--.Pn

■Edge:PiR+i

■二多邊形的描述

■如果要用來描述多邊形則應(yīng)該描述多邊形

的特征，比如邊和頂點(diǎn)。

■多邊形的頂點(diǎn)序列為：P1,P2,.…Pn,

Pio則用一個(gè)二維數(shù)組來表示。

3.2多邊形的填充

■1點(diǎn)在多邊形內(nèi)外的判斷：

■方法：射線法:過該點(diǎn)劃射線與多邊形的邊界的交點(diǎn)如果

為偶數(shù)，則該點(diǎn)在多邊形外，如果為奇數(shù)，則該點(diǎn)在多

邊形內(nèi)。

■交點(diǎn)個(gè)數(shù)：射線1跨越多邊形P得邊界次數(shù)。

■交點(diǎn)：設(shè)A為1與P的邊界公共點(diǎn)，當(dāng)沿著1在A點(diǎn)附近從P的

外部（內(nèi)部）跨入內(nèi)部（外部），則認(rèn)為是一個(gè)交點(diǎn)，否

則不作為一個(gè)交點(diǎn)。

■奇點(diǎn)：射線1與多邊形P公共點(diǎn)為P的頂點(diǎn)時(shí)該點(diǎn)為奇點(diǎn)。

■奇點(diǎn)處理：與奇點(diǎn)相連的多邊形P的邊，若在射線1的同側(cè),

該奇點(diǎn)不作為交點(diǎn)，若在射線1的同側(cè)，該奇點(diǎn)作為一個(gè)交

點(diǎn)，

■在帶狀區(qū)域：Y1＜y1+1o

■區(qū)＜二xV=Xj+i,乂＜=yV二％+i］內(nèi)的象素被P的

邊界分割成梯形和三角形。

■作用：1）區(qū)域中的梯形或三角形關(guān)于P的

內(nèi)外關(guān)系一旦確定，各個(gè)梯形或三角形關(guān)

于P的內(nèi)外關(guān)系也隨之確定。

■2）區(qū)域內(nèi)關(guān)于大量點(diǎn)P的關(guān)系的判別轉(zhuǎn)換

為一個(gè)點(diǎn)的判別。

■2,掃描線的連貫性:

設(shè)掃描線y=c與多邊形P的各邊的交點(diǎn)的坐標(biāo)

遞增序列為x2，，X]O

■1）1為偶數(shù)（?）

■2）交點(diǎn)序列,

■3）在P內(nèi)外線段沿y=c的掃描線相間排列。

■在P內(nèi)的線段的區(qū)間：的，x2）,區(qū)，x4）

■（X11，X1）

3邊的連貫性：

設(shè)掃描線丫=(：-1與P的各邊交點(diǎn)的x坐標(biāo)遞增序

列為X'I,x'2,....,x'h,如果：yij<c,c-1<yi>i

則1)h=1;

2)(x；c-1),(x.c)位于多邊形P的同

一邊pkpk+1上。

3)XI=Xi+△Xik,AXik為Pkpk-1的斜率的負(fù)倒數(shù)

????008軟，Q

“????????cocoeo。

iiifiii

??????????see?得

煞求初挑

3.3polygonfill-areaalgorithm

■一多邊形掃描轉(zhuǎn)換的掃描線算法

■1,思想：

■1）取最上端的一條掃描線與多邊形的各邊相交,

（xl，x2）,（x3，x4）.,（xl-1，xl）,在第一，條

甘福線時(shí)，xl=x2,x3=x4o

■2）排序

■3）填色

■4）下—^條掃描線

■5）區(qū)域會(huì)化：金邊的下端點(diǎn)變化

■I）換新邊，ii）一起退出

■2,要求的序列

■1）交點(diǎn)序列：動(dòng)態(tài)，可調(diào)。

■I）x值可修改（Axik）

■II）區(qū)域發(fā)生變化時(shí)，老邊退出，新邊加入。

■2）y下：判別帶狀區(qū)域是否發(fā)生變化。

■3）y上

■3,數(shù)據(jù)結(jié)構(gòu)

■回顧：

■1)建立邊結(jié)構(gòu)：new(element),alloc()

■2)判斷是否到尾：next==Null

■3)插入一*兀素(element)

head

二＞

■4)刪除某一元素：delete()

■5)排序:

■6)搜索:

■掃描線算法的數(shù)據(jù)結(jié)構(gòu)：

■1)用來保存交點(diǎn)序列的鏈表：AEL(Active_Edge_List)

2)elementinlist(金生表.中白勺元(素)：edge(ii)

3)saveedgeinEdgeTable(ET)

Edge:x△xy下next

X:該邊與當(dāng)前掃寸苗線交點(diǎn)、白勺乂值,

初值.為邊的上漏，占、的x值

△x：彳亥關(guān)于y的向后—F介差分":上立巖，懸（x上,y上）

湍，息（x下,y下）

△x=xb-xH

y上一y下

ymin：=y下°

next:與旨4十,才旨向Edge自勺才旨4十

AEL：與旨4十，寺旨向Edge白勺月^4十。

ET婁t組;寸旨Edge白勺寺旨4十?dāng)?shù)紅L,長度為顯半屏掃才苗

名與白勺條我。

■algorithm：

■structEdge

■{floatx;

■floatAx;

■fl°atYmin；

■Edge*next;

■）；

■Stepl：（初始化）將ET表中各元素置空，建立ET表

■Step2：（basketsort,分桶分類）為多邊形P的每一條邊建立

邊結(jié)構(gòu)按該邊的上端點(diǎn)的y值y上插入ET表中的第y上類

（組），即插入ET[y上].

■Step3：（初始化）AEL置空//AEL=Null

■y:ET表中非空元素的區(qū)域號(hào)最大值。

■Step4：掃描轉(zhuǎn)化

■while（AELorETmS空）

■do

■{No.l（邊插入）如果ET[y]非空，貝1J將ET[y]

■由各邊插入AEL。

■No.2（排序）將AEL中的各邊按照x（若x相等按Ax

■的遞增順序排序。

■No.3（如果AEL非空填色）將AEL中各邊依次組成對(duì)，在橫坐標(biāo)為上

的掃描線上，將以每對(duì)邊的x坐標(biāo)為端點(diǎn)的區(qū)間上填上多邊形所需重

的顏色.

■No.4（下一條掃描線）y-----o

■No.5（邊刪除）將AEL中滿足尸ymin的邊刪除。

■No.6（邊更新）將AEL中的各邊x值更新，x=x+

■Ax}

注：1)y=ymin體現(xiàn)了奇點(diǎn)處理。

2)Ax體現(xiàn)了邊的連貫性。

3)AEL體現(xiàn)了掃描線的連貫性

多邊形各頂點(diǎn)為：

(1,6),(1,4),(3,1),(6,2)

(8,1),(10,5),(7,8),

(5,8),(3,10),(2,6)

1,建立ET表

申請(qǐng)與屏幕掃描線

條數(shù)相同的指向edge

的數(shù)組指針

el=[l,0,4,next]插入

ET[6]

e2=[1,2/3,1,next]插入

ET[4]

e3=[3,-3,1,next]插入

ET[2]

e4二[6,2,1,next]插入

ET[2]

2,為多邊形的10條邊建立邊結(jié)構(gòu)。并按該邊的上

端點(diǎn)的y值插入ET表中的y上類。

e5=[8,-l/2,1,next]插入ET[5];

e6=[l0,1,5,next]fiAET[8];

e7=[5,l,8,next]fi|AET[10];

e8=[3,-l/4,6,next]fiAET[10];

■3,AEL置空；y=10；

4,掃描轉(zhuǎn)換

8-]1015n

AEL93-0-256n—A518n

■1）inserttheedge（邊插入）。

■6）updatetheedge（邊更新）。

■2）sort（排序）。

■3）filling（填曲）。

■4）nextscanline（下一條掃描線）。

■5）deletetheedge（邊刪除）。

■remark：

■1）充分利用連貫性

■2）避免求交點(diǎn)運(yùn)算，計(jì)算量少，速度快

■3）數(shù)據(jù)結(jié)構(gòu)復(fù)雜

■4）程序復(fù)雜

■二區(qū)域的種子填充算法

■1）點(diǎn)鄰域：四鄰域，八鄰域

■四鄰域：四個(gè)點(diǎn)為A點(diǎn)的鄰域，對(duì)于上下左右四個(gè)

■方向運(yùn)動(dòng)而言，上下左右四點(diǎn)構(gòu)成一點(diǎn)的四鄰域。

■八鄰域同樣可得。

■2）路徑：四連通路徑，八連通路徑

■四連通路徑：點(diǎn)集中相鄰兩點(diǎn)均在對(duì)方的四鄰域中

■3）區(qū)域：四連通區(qū)域，八連通區(qū)域

■四連通區(qū)域：如果一點(diǎn)集內(nèi)任意兩點(diǎn)都存在一條完全有

■該點(diǎn)集中的內(nèi)點(diǎn)組成的四連通路徑相連接則稱該點(diǎn)集為

■四連通區(qū)域。

■注：如果四連通區(qū)域內(nèi)的任意點(diǎn)出發(fā)只經(jīng)

過上下左右四個(gè)方向的運(yùn)動(dòng)可以到達(dá)區(qū)域

的任何一點(diǎn)，即為漫延。

■種子填充法：有一點(diǎn)出發(fā)逐步影響周圍的

點(diǎn)。

■種子填充算法：

■1)遞歸算法：出口：種子點(diǎn)seedpoint

■flood_fi114(x5y?oldcolor,newcolor)

■{if(frame_buffer(x?y)==oldcolor)

■{frame_buffer(x5y)==newcolor;

■flood_fill4(x5y+15oldcolor,newcolor);

■flood_fill4(x,y-l,oldcolor,newcolor);

■flood_fill4(x-l,y,oldcolor,newcolor);

■flood_fill4(x+1,y,oldcolor,newcolor);

■逐點(diǎn)漫延，用堆棧實(shí)現(xiàn)。

■注：

■1）點(diǎn)進(jìn)出系統(tǒng)堆棧達(dá)4次

■2）程序簡(jiǎn)單明了

■3）算法采用遞歸（盡量不用）

■4）費(fèi)時(shí)費(fèi)內(nèi)存。

■2種子填充的掃描線算法

■Algorithm:

■stepl:給定種子點(diǎn)（x,y）在種子點(diǎn)所在掃描線上找出包

含種子點(diǎn)所在區(qū)域內(nèi)的最長的區(qū)間（xbxr）

■step?:在種子點(diǎn)所在掃描線上下相鄰的掃描線上的(xl,xr)的區(qū)間

的標(biāo)一個(gè)點(diǎn)做為種子點(diǎn)處理。

■程序：

■Stepl：初始化：

■"stack置空。?種子點(diǎn)進(jìn)棧push(x,x,y)

■Step2：區(qū)域填充

■while(stack_is_not_empty)

■{2.1出棧pop(x,x,y)

■2.2向左延伸

■if(frame_buffer(xl,y)==oldcolor)

■{if(frame_buffer(xl-l,y)==oldcolor)xl=xl-1

■}

■2.3向右延伸(同上)

■2.4確定子區(qū)間(xl,xr),在縱坐標(biāo)為y的掃描線的區(qū)間(xl,xr)內(nèi)

定義區(qū)間內(nèi)的各子區(qū)間，從對(duì)到xr逐一魚查象素的顏色

■若frame_buffer(xl,y)==oldcolor,則將該象素變色，否則

確定(X—1,y)，(x+1,y)是否為端,占，也即：(X—

1,y)是否為學(xué)區(qū)間的右端點(diǎn)，(x+1,y)是否為子區(qū)間

的若端點(diǎn)。

■2.5(填色進(jìn)棧)