第3章 基本圖形生成

第3章基本圖形生成現(xiàn)在的計算機能夠生成非常復(fù)雜的圖形，但圖形無論多么復(fù)雜，它都是由基本圖形組合而成的。因此，學(xué)習(xí)基本圖形的生成算法是掌握計算機圖形學(xué)的基礎(chǔ)。本章主要討論一些基本圖形的生成原理，如直線、圓、橢圓的生成問題，二維封閉圖形（多邊形、圓、橢圓）的填充問題（包括顏色填充、影線填充和圖案填充）以及線型和線寬的處理。VisualC++的CDC圖形程序庫已提供了畫線、畫圓和橢圓、填充等基本圖形的繪制函數(shù)，它們實質(zhì)上是按計算機圖形標準并以C++的語法約定提供給用戶使用的標準圖形生成算法。因此，從實用的角度出發(fā)，用戶只需完全按照C++的語法約定使用這些圖形程序庫，就沒有必要學(xué)習(xí)基本圖形的生成原理及算法。但是，基于下面的二個理由，我們認為學(xué)習(xí)本章介紹的基本圖形生成原理及算法是非常有必要的。第二，VisualC++雖然提供了許多繪圖函數(shù)，但總有滿足不了用戶特殊繪圖要求的時候。如果僅僅學(xué)會使用VisualC++的繪圖函數(shù)，不掌握基本圖形生成原理及算法，那么你就永遠無法超越VisualC++的限制。第一，基本圖形生成原理及算法是計算機圖形學(xué)的基本原理，如果不學(xué)習(xí)這些基本原理，那么以后還要涉及的其他計算機圖形學(xué)原理就無從談起；眾所周知，計算機內(nèi)部存儲和使用的數(shù)據(jù)是二進制數(shù)(由0和1組成)。目前我們使用的主要圖形輸出設(shè)備顯示器(一般為光柵圖形顯示器)和打印機(點陣、噴墨、激光打印機)本質(zhì)上是一種畫點設(shè)備，是由一定數(shù)量的網(wǎng)格狀細小光點(光點稱為像素，光點的數(shù)量稱為分辨率)，使其某些像素亮(二進值為1)，某些像素不亮(二進值為0)來顯示圖形或文字的。因此，所謂的基本圖形生成原理是指在點陣輸出設(shè)備的情況下，如何對一條斜的直線或彎曲的曲線盡可能快地輸出其最接近理想的直線或曲線，即如何以最快的速度確定最佳逼近于圖形的像素集，如圖3-1所示圖3-1直線與曲線掃描轉(zhuǎn)換本章我們主要以光柵圖形顯示器為例討論基本圖形的生成原理及算法。在顯示設(shè)備上，確定一個像素集合及其顏色，用于顯示一個圖形的過程稱為圖形的掃描轉(zhuǎn)換或光柵化。我們假定，編程語言(以C語言為例)提供了一個最底層的對顯示設(shè)備的像素進行寫操作的函數(shù)：putpixel(x,y,color);其中，x和y指定像素的位置坐標，color指定像素的顏色。另外，為了方便起見，以下的討論還假定所給出原始坐標數(shù)據(jù)為整數(shù)，并設(shè)定直線的斜率：|k|≤1，至于任意斜率直線的生成可以在基本算法的基礎(chǔ)上稍加變換即可得到。3.1直線的生成在計算機上畫線一般都是給定兩個坐標點(x1,y1)和(x2,y2)，要求畫出它們的直線。當要在屏幕上顯示一條直線時，只能在顯示器所給定的有限個像素矩陣中，確定最佳逼近于該直線的一組像素，對這些像素進行寫操作。這就是通常所說的在顯示器上繪制直線，或直線的掃描轉(zhuǎn)換。直線的斜率截距方程為：

y=k·x+b(3–1)其中，k表示斜率，b是y軸截距。解析幾何問題

已知:給定兩個坐標點P1(x1,y1)和P2(x2,y2),求:1)對應(yīng)于線段P1、P2的直線方程y=kx+b的系數(shù)k、b;2)對應(yīng)于線段P1、P2的直線方程F(x,y)=ax+by+c=0的系數(shù)a、b、c。解1)：給定線段的兩個端點(x1,y1)和(x2,y2)，可以計算出斜率可k和截距如下：

k=△y/△x=(y2–y1)/(x2–x1)

b=y1–k·x1(3-2)

解2)：假設(shè)直線的起點和終點分別為(x1,y1)和(x2,y2)，利用1）的端點的斜率表示及其方程，非常方便地求的一組參數(shù)：a=y1-y2，b=x2-x1，c=x1y2-x2y1。直線生成算法主要思想圖3-3直線生成算法示意圖

圖3-2直線（斜率：0≤k≤1）掃描轉(zhuǎn)換示意圖針對上述式（3-3）中P1或P2點的選擇，我們會有不同的方法。這就是本章將要敘述的數(shù)值微分法、中點畫線法以及Bresenham畫線算法。為此，只需讓x從起點到終點每次增加(或減少)1，首先，我們可以用(3.1.1)式計算對應(yīng)的y值，再用putpixel(x,int(y+0.5),color)函數(shù)輸出該像素的顏色值即可。這里用int來取整是因為像素的坐標值都是整數(shù)的。但是，用這種方法畫線效率太低，這是因為每步都需要一個浮點乘法運算和一個四舍五入運算。3.1.1數(shù)值微分法

圖3-4數(shù)值微分法示意圖△y=k·△x△x=△y/k

對于具有斜率絕對值|k|<1的線段，可以讓x從起點到終點變化，每步遞增(或遞減)1，即令△x=±1，則△y=±k。若前一次的直線上像素點坐標為(xi,yi)，這一次的直線上像素點坐標為(xi+1,yi+1)，則xi+1=xi±1，yi+1=yi±k。隨后用putpixel函數(shù)輸出該像素的顏色值即可。見圖3-4。圖3-4數(shù)值微分法示意圖

對于具有斜率絕對值|k|>1的線段，可以讓y從起點到終點變化，每步遞增(或遞減)1，即△y=±1,計算對應(yīng)的x增量，則為即△x=±1/k。若前一次的直線上像素點坐標為(xi,

yi)，這一次的直線上像素點坐標為(xi+1,yi+1)，則xi+1=xi±1/k，yi+1=yi±1。隨后用putpixel函數(shù)輸出該像素的顏色值即可。

上述采用的增量計算方法稱為數(shù)值微分算法(DigitalDifferentialAnalyzer簡稱DDA)。以下是用數(shù)值微分算法(DDA)生成直線(斜率在0～l)的C語言描述。voidDDALine(intx1,inty1,intx2,inty2,intcolor){intx；floatk,dx，dy，y=y1；dx=x2–x1；dy=y2–y1；k=dy/dx;for(x=x1；x<=x2；x++){putpixel(x,(int)(y+0.5),color);y=y+k;}}3.1.2中點畫線法d=F(M)=F(xk+1,yk+0.5),d1=F(M1)=d+a,d2=F(M2)=d+a+bd0=a+0.5bM:中點Q:精確值圖3-5中點畫線法示意圖F(x,y)=ax+by+c=03.1.2中點畫線的改進算法圖3-5中點畫線法示意圖下面來討論中點畫線法的具體實現(xiàn)。直線方程為：F(x,y)=ax+by+c＝0假設(shè)直線的起點和終點分別為(x1,y1)和(x2,y2)，則上述參數(shù)：a=y1-y2，b=x2-x1，c=

x1y2-x2y1。對于直線上的點，F(xiàn)(x,y)=0；對于直線上方的點，F(xiàn)(x,y)>0；而對于直線下方的點，F(xiàn)(x，y)<0。因此，欲判斷前述Q在M的上方還是下方，只要把

M代入

F(x，y)，并判斷它的符號。

構(gòu)造判別式d＝F(M)=F(xk+1,yk+0.5)=a(xk+1)+b(yk+0.5)+c當

d>0時，M在直線上方（即在Q的上方），故應(yīng)取右方的P1作為下一個像素。而當d<0，則應(yīng)取右上方的P2。當d=0時，約定取右方P1。

對每一個像素計算判別式d，根據(jù)它的符號確定下一像素。由于d是xk和yk的線性函數(shù)，可采用增量計算，以便提高運算效率。在d≥0的情況下，取正右方像素P1，欲判斷再下一個像素應(yīng)取那個，應(yīng)計算

d1=F(xk+2,yk+0.5)=a(xk+2)+b(yk+0.5)+c

=(a(xk+1)+b(yk+0.5)+c)+a=d+a故d的增量為a。在d<0時，取右上方像素P2。要判斷再下一個像素，應(yīng)計算

d2=F(xk+2,yk+l.5)=a(xk+2)+b(yk+1.5)+c

=(a(xk+1)+b(yk+0.5)+c)+a+b=d+a+b再看d的初始值。直線的第一個像素為左端點(x1,y1)，所以相應(yīng)的判別式值為

d0=F(x1+1,y1+0.5)=a(x1+1)+b(y1+0.5)+c=(ax1+by1+c)+a+0.5b=F(x1，y1)+a+0.5b由于(x1,y1)在直線上，故F(x1,y1)

=0。因此，d的初始值為d0=a＋0.5b。由于我們使用的只是d的符號，而且d的增量都是整數(shù)，只是其初始值包含小數(shù)。因此，我們可以用2d代替d，就可以寫出僅包含整數(shù)運算的中點畫線算法(斜率在0～l)：

故d的增量為a＋b。

voidMPLine(intx1,inty1,intx2,inty2,intcolor){intx,y,a,b,d,d1,d2;a=y1–y2;b=x2–x1;y=y1;d=2*a+b;dl=2*a;d2=2*(a+b);for(x=x1;x<=x2;x++){putpixel(x,y,color);if(d<=0){y++;d+=d2;}else{d+=dl;}}}3.1.3

Bresenham畫線算法

xkykyk+1yxk+1d1d23.1.3

Bresenham畫線算法

1965年，Bresenham提出了一種更好的直線生成算法，稱為Bresenham算法。此算法的一個主要思想是借助于一個決策變量dk，來確定下一個該點亮的像素點。

對于直線斜率k在0～1之間的情況，如圖3.3所示，從給定線段的左端點(x1,y1)開始，逐步處理每個后續(xù)列(x位置)，并在掃描線y值最接近線段的像素上繪出一點。假設(shè)當前直線上的像素已確定，其坐標為(xk,yk)。那么下一步需要在列xk+1上確定掃描線y的值。y值要么不變，要么遞增1。

在列位置xk+1，用d1和d2來標識兩個候選像素的y值與線段上理想y值的差值，則：

d1=y–yk=(k(xk+1)+b)–yk

d2=(yk+1)–y=yk+1–(k(xk+1)+b)那么

d1–d2=2k(xk+1)–2yk+2b–1xkykyk+1yxk+1d1d2特別地，初始值：d10=y-y0=kd20=y0+1-y=1-kd0=d10-d20=2k-1設(shè)△y=y2–y1和△x=x2–x1，則k=△y/△x，代入上式，得：△x(d1–d2)=2△y·xk–2△x·yk+c(3–4)當dk>0時，直線上理想位置與右上方像素(xk+1，yk+l)更接近，所以應(yīng)取右上方像素；而當dk<0時，右方像素(xi+l，y)與直線上理想位置更接近，應(yīng)取右方像素；當dk=0時，兩個候選像素與直線上理想位置一樣接近，約定取(xk+l，yk+1)。

若令dk=△x(d1–d2),并稱dk為畫線中第k步的決策參數(shù),則dk的計算僅包含整數(shù)運算,它的符號與d1–d2的符號相同。c為常量，在計算中將被消除。

在k+1步，決策參數(shù)可從方程(3–4)算出：

dk+1=2△y·xk+1–2△x·yk+1+c從上述方程中減去方程（3–4），可得：

dk+1–dk=2△y(xk+1–xk)–2△x(yk+1–yk)已知xk+1=xk+1，因而得到：

dk+1=dk

+2△y–2△x(yk+1–yk)若取右上方像素，yk+1–yk=1，則：

dk+1=dk

+2△y–2△x若取右方像素，yk+1=yk，則：

dk+1=dk

+2△y

在每個整數(shù)x位置,從線段的坐標端點開始,反復(fù)進行決策參數(shù)的這種循環(huán)計算。在起始像素(x1,y1)的第一個參數(shù)d0可從方程(3–4)及k=△y/△x計算出：以下是Bresenham算法的C語言描述(斜率在0～l)。

d0=2△y·x1–2△x·y1+2△y+△x·(2b-1)=2△y·x1–2△x·(k·x1+b)+2△y+△x·(2b-1)=2△y·x1–2k△x·x1-2b△x+2△y+2b△x-△x

=2△y·x1–2(△y/△x)△x·x1+2△y-△xd0=2△y–△x由于：dk=△x(d1–d2),則：d0=△x(d10-d20)(對比原來：d0=d10-d20=2k-1=2△y/△x-1，)故d0=（2k-1)△x=2△y–△x綜合上述：xkykyk+1yxk+1d1d2voidBHLine(intx1,inty1,intx2,inty2,intcolor){intx,y,dx,dy,dk;dx=x2–x1;dy=y2–y1;dk=2dy–dx;y=y1;for(x=x1;x<=x2;x++){putpixel(x,y,color);if(dk>=0){y++;dk=dk–2*dx;}dk=dk+2*dy;}}思考題：任意給定某一線段端點的2個像素坐標值，利用直線掃描轉(zhuǎn)換的三種算法中的任一種，計算出其他各個像素值？3.2圓與橢圓的生成

3.2.1圓的特性由于圓是圖形和圖像中經(jīng)常使用的元素，因此在大多數(shù)圖形軟件中都包含有生成圓和圓弧的過程。也會提供一個既能顯示圓曲線，又能顯示橢圓曲線的繪圖函數(shù)。

圓被定義為所有離一中心位置(xc，yc)距離為給定值r的點集，可用如下方程表示：(x–xc)2+(y–yc)2=r2利用這個方程，我們可以沿x軸從xc–r到xc+r以單位步長計算對應(yīng)的y值來得到圓周上每點的位置：

y=yc

±

但這并非是生成圓的最好方法。這個方法的一個問題是每一步包含很大的計算量。而且所畫像素位置間的間距是不一致的，在靠近x軸的0°和180°處像素點之間的間距越來越大。當然可以在圓斜率的絕對值大于1后，交換x和y（即步進y值，計算x值）來調(diào)整間距。但這樣增加了算法所需的計算量和處理過程。

另一種消除不等間距的方法是使用極坐標r和θ計算沿圓周的點。以參數(shù)極坐標形式表示圓方程可得到方程組：

x=xc+rcosθ

y=yc+rsinθ

使用上述方法以固定角度為步長生成顯示時，圓就可沿圓周等距點繪制出來。但這個方法使用了三角函數(shù)調(diào)用和浮點運算，運算速度太慢。

考慮到圓的對稱性可以減少計算量。只要能生成8分圓，那么圓的其他部分可通過一系列的簡單反射變換得到。如圖3.4所示，假設(shè)已知一個圓心在原點的圓上一點(x，y)，根據(jù)對稱性可得另外七個8分圓上的對應(yīng)點(y,x),(y,–x),(x,–y),(–x,–y),(–y,–x),(–y,x),(–x,y)。因此，只需討論8分圓的生成算法。

另外，為了方便起見，我們只考慮中心在原點，半徑為整數(shù)R的圓x2＋y2=R2。對于中心不在原點的圓，可先通過平移變換，化為中心在原點的圓，再進行掃描轉(zhuǎn)換，把所得的像素坐標加上一個位移量即得所求像素坐標。

(y,x)(y,-x)(x,y)(x,-y)(-x,y)(-x,-y)(-y,-x)(-y,x)圖3.4圓的對稱性

圓弧像素生成示意圖1/8圓弧生成算法主要思想P=(x,y)P1P2Md=F(M)=F(xk+1,yk-0.5)d1=F(M1)=d+2xk+3d2=F(M2)=d+2(xk-yk)+5

F(x,y)=x2＋y2–r23.2.2中點畫圓法

F(x,y)=x2＋y2–r23.2.2中點畫圓法改進后純整數(shù)算法voidMidpointCircle(intxc,intyc,intr,intcolor){intx=0,y=r,d=1–r；WholeCircle（xc，yc，x，y，color）；while（x<=y）{if（d＜0）{d+=2*x+3；x++；}else{d+=2*（x–y）+5；x++;y––；}WholeCircle（xc，yc，x，y，color）；}}以下是中點畫圓算法的C語言描述：voidWholeCircle(intxc,intyc,intx,inty,intcolor){putpixel(xc+x，yc+y，color)；putpixel(xc–x，yc+y，color)；putpixel(xc+x，yc–y，color)；putpixel(xc–x，yc–y，color)；putpixel(xc+y，yc+x，color)；putpixel(xc–y，yc+x，color)；putpixel(xc+y，yc–x，color)；putpixel(xc–y，yc–x，color)；}3.2.3Bresenham畫圓算法d=F(H)+F(D)d1=F(H1)+F(D1)=d+4xi+6d2=F(H2)+F(D2)=d+4(xi-yi)+10

F(x,y)=x2＋y2–r2判別式d=F(H)+F(D)解析圖3.2.3Bresenham畫圓算法歸納voidBresenhamCircle(intxc,intyc,intr,intcolor){intx=0,y=r,d=3-2*r;while(x<y){WholeCircle(xc,yc,x,y,color);if(d<0)d=d+4*x+6;else{d=d+4*(x-y)+10;y--;}x++;}if(x==y)WholeCircle(xc,yc,x,y,color);}3.2.4橢圓生成算法基本思想:將圓的正負法推廣。橢圓的方程：F(x,y)=b2x2+a2y2-a2b2=0

(3.2.4)只考慮第一象限橢圓弧生成，分上下兩部分，以切線斜率為-1的點作為分界點。橢圓上一點處的法向：圖3.14第一象限的橢圓弧1.橢圓上半部分與下半部分圓弧分界點的求取橢圓弧像素生成示意圖圓弧像素生成示意圖而對應(yīng)于橢圓方程(3.2.4)來說，我們可以很方便地得到其1/4橢圓弧上任意一點的法向量為：

在上部分和下部分的交界處，法向量的x和y方向兩個分量相等，必定滿足：即：2b2x=2a2y(3.2.5)因此，上半部分的條件是：2b2x<2a2y；下半部分的條件是：2b2x>=2a2y將式(3.2.5)與式(3.2.4)聯(lián)立求解，可以得到分界點的精確坐標。1)上半部分橢圓弧生成算法示意圖d=F(M)2.中點畫橢圓算法運用中點畫橢圓的方法，可以得到算法表達式如下：對于1/4圓弧的上半部分(b2x<a2y,x≥0）：2)下半部分橢圓弧生成算法示意圖d=F(M)2.中點畫橢圓算法對于1/4圓弧的下半部分(b2x≥a2y,y>0）中點畫圓法可以推廣到一般二次曲線的生成。給定橢圓參數(shù)中心（xc，yc）、長半軸a和短半軸b，該橢圓的一般方程為：(x–xc)2/a2+(y–yc)2/b2=1為此，可以先把中心平移到坐標原點，確定好中心在原點的標準位置的橢圓像素點集后，再平移到(xc,yc)位置。如果橢圓的長軸和短軸方向不與坐標軸x和y平行，可以先繞中心點進行旋轉(zhuǎn)變換，確定變換矩陣，然后用本方法生成橢圓像素點集，再用變換矩陣乘以這些點集，就可繪出傾斜的橢圓。

寫出完整的中點畫橢圓的算法如下：voidMidpointEllipse(intxc,intyc,inta,intb,intcolor){intaa=a*a,bb=b*b;inttwoaa=2*aa,twobb=2*bb;intx=0,y=b;intdx=0,dy=twoaa*y;intd=(int)(bb+aa*(–b+0.25)+0.5);WholeEllipse(xc,yc,x,y,color);while(dx<dy){x++;dx+=twobb; if(d<0)d+=bb+dx; else{y––;dy–=twoaa;d+=bb+dx–dy;}WholeEllipse(xc,yc,x,y,color);}voidWholeEllipse(xc,yc,x,y,color)intxc,yc,x,y,color;{putpixel(xc+x,yc+y,color);putpixel(xc+x,yc–y,color);putpixel(xc–x,yc+y,color);putpixel(xc–x,yc–y,color);}d=(int)(bb*(x+0.5)*(x+0.5)+aa*(y–1)*(y–1)–aa*bb+0.5);while(y>0){y––;dy–=twoaa;if(d>0)d+=aa–dy;else{x++;dx+=twobb;d+=aa–dy+dx;}WholeEllipse(xc,yc,x,y,color);}}3.Bresenham畫橢圓算法參照前面Bresenham畫圓算法可以推導(dǎo)Bresenham畫橢圓算法表達式如下：1)對于1/4圓弧的上半部分(b2x<a2y,x≥0）：(3.2.8)2)對于1/4圓弧的下半部分(b2x≥a2y,y>0）3.3區(qū)域填充3.3.1有序邊表填充算法本節(jié)討論如何用一種顏色或圖案來填充一個二維區(qū)域。填充的區(qū)域可以是多邊形的，也可以是圓或橢圓的，還可以是帶孔的。區(qū)域填充可以分兩步進行，第一步先確定需要填充哪些像素。第二步確定用什么顏色值或圖案來填充。多邊形區(qū)域填充的一種常用方法是按掃描線順序，計算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素，即完成填充工作。有序邊表定義：有序邊表（SortedEdgeTable），又稱作新邊表（NewEdgeTable）,即為對多邊形的節(jié)點坐標進行適當?shù)刈兓?，所形成的一種特殊的鏈表數(shù)據(jù)結(jié)構(gòu)，其目的是方便、快速而有效地實現(xiàn)掃描線與多邊形的求交、排序等算法的處理，以利于多邊形域的掃描線填充。特別需要指出的是，利用該表可以有效地解決冗余求交問題。ABCDP1P2P3P4P5P62468102468Oyx如圖3.8所示，掃描線3與多邊形的邊界線交于四點A、B、C、D。這四點把掃描線分為四個區(qū)間[0,3],[3,4.5],[4.5,6],[6,.3],[8.3,11]。其中,[3,.5],[6,8.3]兩個區(qū)間落在多邊形內(nèi)，該區(qū)間內(nèi)的像素應(yīng)取多邊形色。其他區(qū)間內(nèi)的像素取背景色。

圖3.8多邊形與掃描線

1)求交——利用邊的連續(xù)性，用迭代、增量法實現(xiàn);2)排序——用冒泡法等數(shù)據(jù)結(jié)構(gòu)常規(guī)算法即可實現(xiàn);3)交點配對——研究上部、中部、下部各交點的特點;4)區(qū)間填色。1.算法要點:2.求交算法的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)步驟數(shù)據(jù)結(jié)構(gòu)1)有序邊表NET(又稱新邊表);2)活化邊表AET。typedefstructtEdge{floatx;/*當前掃描線與邊的交點的x值*/floatdx;/*從當前掃描線到下一條掃描線之間的x增量*/intymax;/*邊所交的最高掃描線號*/structtEdge*next/*指向下一條邊的指針*/}Edge;實現(xiàn)步驟

利用邊的連續(xù)性，用迭代、增量法實現(xiàn);xk+1=xk+1/m(m為邊的斜率)ABCDP1P2P3P4P5P62468102468Oyx9^8^765^4^3^210^7-1/3473/56^3-1/5733/24^10-5/39^23/29^P4P5P3P4P6P1P5P6P2P3P1P2PiPj[(xi,yi)、(xj,yj)]Polygon={P1P2,P2P3,P3P4,P4P5,P5P6,P6P1}P1(2,7),P2(5,9),p3(10,6),p4(7,1),p5(6,4),p6(3,2)xdxymax^kNET:多邊形邊集合的重新表示，以便于掃描線求交AET:與當前掃描線相交的點的集合有些在多邊形頂點處的掃描線交點需要專門處理。在這些位置上，掃描線通過一個頂點與多邊形的兩條邊相交。例如圖3.8所示，若交點算一個，則掃描線2與P6相交，求得交點(x坐標)序列3,6.5,7.5。這將導(dǎo)致[3,6.5]區(qū)間內(nèi)的像素被填充，而這個區(qū)間的像素是屬于多邊形外部，不需要填充。若交點算二個，則掃描線7與P1相交，求得交點(x坐標)序列2,2,10。這將導(dǎo)致[2,10]區(qū)間內(nèi)的像素不被填充，而這個區(qū)間的像素是屬于多邊形內(nèi)部，需要填充。

為了正確地進行交點取舍，必須對上述兩種情況區(qū)別對待。在第一種情況，掃描線交于一頂點，而共享頂點的兩條邊分別落在掃描線的兩邊。這時，交點只算一個。在第二種情況，共享交點的兩條邊在掃描線的同一邊，這時交點作為零個或兩個，取決于該點是多邊形的局部最高點還是局部最低點。具體實現(xiàn)時，只需檢查頂點的兩條邊的另外兩個端點的y值。按這兩個y值中大于交點y值的個數(shù)是0，1，2來決定是取零個、一個、還是兩個。例如，掃描線1交頂點P4，由于共享該頂點的兩條邊的另外二個頂點均高于掃描線，故取交點P4兩次。這使得P4像素用多邊形顏色設(shè)置。而在P2處，由于P1和P3均在下方，所以掃描線9與之相交時，交點算零個，該點不予填充。

在處理一條掃描線時，只需對與它相交的多邊形的邊進行求交運算。由于邊的連貫性，即當某條邊與當前掃描線相交時，它很可能也與下一條掃描線相交，為此，計算下一條掃描線與同一條邊的交點x值時，只需把當前交點x值加上一個邊的反斜率即可：

xk+1=xk

+1/m(m為邊的斜率)

我們把與當前掃描線相交的邊稱為活化邊，并把它們按與掃描線交點x坐標遞增的順序存放在一個鏈表中，稱此鏈表為活化邊表。令△x=1/m為常量，可以存放在對應(yīng)邊的活化邊表結(jié)點中。

另外，使用增量法計算時，我們需要知道一條邊何時不再與下一條掃描線相交，以便及時把它從活化邊表中刪除出去，避免下一步進行無謂的計算。為此，需設(shè)一個變量ymax，用于保存邊所交的最高掃描線號。由此，活化邊表結(jié)點的數(shù)據(jù)結(jié)構(gòu)可定義為如下形式：typedefstructtEdge{floatx;/*當前掃描線與邊的交點的x值*/floatdx;/*從當前掃描線到下一條掃描線之間的x增量*/intymax;/*邊所交的最高掃描線號*/structtEdge*next/*指向下一條邊的指針*/}Edge;為了保證交點的正確配對，必須使活化邊表中的結(jié)點按交點x值的升序排序。排序方法可采用插入排序法。

在處理完當前掃描線后轉(zhuǎn)入下一條掃描線之前，要對交點x坐標進行更新(+dx),插入新加入的邊，并把那些與當前掃描線有交，而與下一條掃描線不再相交的邊，從活化邊表中刪除出去(通過檢查當前掃描線y值是否等于各邊的ymax值來確定)。

另外，為了方便活化邊表的建立與更新，我們?yōu)槊恳粭l掃描線建立一個有序邊表，存放在該掃描線第一次出現(xiàn)的邊。也就是說，若某邊的較低端點的y值為ymin，則該邊就放在掃描線為ymin的有序邊表中。這樣，當我們按掃描線號從小到大順序處理掃描線時，該邊在該掃描線第一次出現(xiàn)。有序邊表的數(shù)據(jù)結(jié)構(gòu)與活化邊表相同，每個結(jié)點存放對應(yīng)邊的初始信息。如該掃描線與該邊的初始交點x值(即較低端點的x值)，x的增量△x，以及該邊的最大y值ymax。有序邊表的邊結(jié)點也按x值升序排序。

在活化邊表的基礎(chǔ)上，進行交點配對和區(qū)間填充是很容易的事。令指針從活化邊表中第一個結(jié)點到第二個結(jié)點遍歷一次，對每一個像素進行寫操作。然后令指針從活化邊表中第三個結(jié)點到第四個結(jié)點遍歷一次，對每一個像素進行寫操作。如此反復(fù)，直至本掃描線全部填充完畢。

3.交點配對交點個數(shù)統(tǒng)計1）非極值點——1個；2）極值點：①極小點——2個；②極大點——0個；邊界象素取舍問題１）［左，右）２）（上，下］歸納上述討論，我們可寫出多邊形區(qū)域填充的步驟為：①輸入欲填充多邊形的頂點數(shù)及其頂點坐標。這里，頂點數(shù)為實際頂點數(shù)加1，最后一個頂點坐標與第一個頂點坐標相同。②計算所有多邊形頂點坐標中y的最大值和最小值，以此作為掃描線的處理范圍。③對處理范圍內(nèi)的每條掃描線建立有序邊表。

④對處理范圍內(nèi)的每條掃描線，重復(fù)下列步驟：

A．用有序邊表建立當前掃描線的活化邊表；

B．從活化邊表中依次取出一對交點，對該兩個交點內(nèi)的像素進行填充；

C．為下一條掃描線更新活化邊表，即增加交點的x值和刪除不再相交的邊；

D．重排活化邊表。以下是有序邊表填充算法描述。

Polygonfill(polydef，color）｛多邊形定義polydef；//pts=newPOINT[cnt],cnt為邊數(shù);for（各條掃描線i）｛求ymin、ymax｝建立NET//buildEdgeList(cnt,pts,edges[i])，edges[]為NETfor（各條掃描線i）｛建立活化邊表//buildActiveList(scan,active,edges);即把新邊表NET[i]中的邊結(jié)點用插入排序法插入AET，使之按x坐標遞增順序排列；填充配對線段的顏色//FillScan(scan,active,color);,即遍歷AET表，把配對交點之間的區(qū)間（左閉右開）上的各象素(x,y)，用setpixel(x,y,color)改寫象素顏色值；更新活化邊表//updateActiveList(scan,active),即遍歷AET表，把ymax=i的結(jié)點從AET表中刪除，并把i<ymax結(jié)點的x值遞增△xi；

重排活化邊表//resortActiveList(active);若允許多邊形的邊自相交，則用冒泡排序法對AET表重新排序｝｝／*Polygonfill*／#defineWINDOW_HEIGHT480typedefstructpoint{intx,y;}POINT;//按交點x的升序?qū)呥M行插入排序voidInsertEdge(Edge*list,Edge*edge)//生成有序邊表的一條邊voidMakeEdgeRec(POINTlower,POINTupper,intyComp,Edge*edge,Edge*edges[])voidBuildEdgeList(intcnt,POINT*pts,Edge*edges[])//建立有序邊表voidBuildActiveList(intscan,Edge*active,Edge*edges[])//建立活化邊表voidDeleteAfter(Edge*q)//刪除不再相交的邊

//更新活化邊表

voidUpdateActiveList(intscan,Edge*active)//遍歷AET表，把ymax=i的結(jié)點從AET表中刪除，并把ymax>i結(jié)點的x值遞增△xi；

voidResortActiveList(Edge*active)//重排活化邊表

voidFillScan(intscan,Edge*active,intcolor)//區(qū)間填色：把配對交點之間的區(qū)間（左閉右開）上的各象素(x,y)填色；{Edge*p1,*p2;inti;p1=active–>next;while(p1){p2=p1–>next;for(i=p1–>x;i<p2–>x;i++) putpixel((int)i,scan,color);p1=p2–>next;}}voidScanFill(intcnt,POINT*pts,intcolor)//cnt為多邊形的頂點數(shù)，pts為頂點坐標數(shù)組{Edge*edges[WINDOW_HEIGHT],*active;inti,scan,smax=0,smin=1024;for(i=0;i<cnt–1;i++)//求smax和smin{if(smax<pts[i].y)smax=pts[i].y;if(smin>pts[i].y)smin=pts[i].y;}for(scan=smin;scan<=smax;scan++)//初始化每條掃描線的邊鏈表{edges[scan]=(Edge*)malloc(sizeof(Edge)); edges[scan]–>next=NULL;}BuildEdgeList(cnt,pts,edges);//建立有序邊表active=newEdge;//初始化活化邊表active–>next=NULL;for(scan=smin;scan<=smax;scan++){BuildActiveList(scan,active,edges);if(active–>next){FillScan(scan,active,color);//填充當前掃描線UpdateActiveList(scan,active);//更新活化邊表ResortActiveList(active);//重排活化邊表}}}voidinsertEdge(Edge*list,Edge*edge){//在邊表list中，按從小到大順序，插入一條新的邊edgeEdge*p,*q=list;p=q->next;while(p)//p!=NULL{if(edge->x<p->x)p=NULL;else{q=p;p=p->next;}}edge->next=q->next;q->next=edge;}3.3.2邊填充算法

邊填充算法的基本思想是：對于每一條掃描線和每條多邊形的交點(x1,y1)，將該掃描線上交點右方的所有像素取補。對多邊形的每條邊作此處理，多邊形的順序隨意。如圖3.9所示，為應(yīng)用最簡單的邊填充算法填充一個多邊形的示意圖。邊填充算法最適用于具有幀緩沖器的圖形系統(tǒng)，按任意順序處理多邊形的邊。在處理每條邊時，僅訪問與該邊有交的掃描線上交點右方的像素。當所有的邊都處理之后，按掃描線順序讀出幀緩沖器的內(nèi)容，送入顯示設(shè)備。P5P4P3P1P2P2P3P3P4P4P5P5P1圖3.9邊填充算法示意圖

本算法的優(yōu)點是簡單，缺點是對于復(fù)雜圖形，每一像素可能被訪問多次，輸入/輸出的量比有序邊表算法大得多。為了減少邊填充算法訪問像素的次數(shù)，可引入柵欄。所謂柵欄指的是一條與掃描線垂直的直線，柵欄位置通常取過多邊形頂點、且把多邊形分為左右兩半。柵欄填充法的基本思想是：對于每個掃描線與多邊形的交點，就將交點與柵欄之間的像素取補。若交點位于柵欄左側(cè)，則將交點之右至柵欄之左的所有像素取補；若交點位于柵欄右邊，則將柵欄之右至交點之左的像素取補。圖3.10為柵欄填充法示意圖。

P5P4P3P1P2P2P3P4P5P3P4P5P1圖3.16柵欄填充算法示意圖

柵欄填充算法只是減少了被重復(fù)訪問的像素的數(shù)目，但仍有一些像素會被重復(fù)訪問。因此又進一步提出了改進的邊標志算法，使得算法對每個像素僅訪問一次。

邊標志算法分為兩步驟：第一步，對多邊形的每條邊進行直線掃描轉(zhuǎn)換，亦即對多邊形邊界所經(jīng)過的像素打上邊標志；第二步，填充。對每條與多邊形相交的掃描線，依從左到右順序，逐個訪問該掃描線上像素。使用一個布爾量inside來指示當前點的狀態(tài)，若點在多邊形內(nèi)，則inside為真。若點在多邊形外，則inside為假。上述邊標志算法思想可歸納為如下偽程序：

inside的初始值為假，每當當前訪問像素為被打上邊標志的點，就把inside取反。對未打標志的像素，inside不變。若訪問當前像素時，對inside作必要操作之后，inside為真，則把該像素置為多邊形色。voidedge_mark_fill(polydef,color)多邊形定義polydef;intcolor;{對多邊形polydef每條邊進行直線掃描轉(zhuǎn)換;inside=FALSE;for(每條與多邊形polydef相交的掃描線y){if(像素x被打上邊標志)inside=!(inside);if(inside!=FALSE)drawpixel(x,y,color);elsedrawpixel(x,y,background);}}3.3.3種子填充算法種子填充算法則采用不同的原理：填充方法是從多邊形區(qū)域內(nèi)部的一點開始，由此出發(fā)找到區(qū)域內(nèi)的所有像素。這種填充算法在交互式繪圖中很常用。

種子填充算法采用的邊界定義是區(qū)域邊界上所有像素均具有某個特定的顏色值，區(qū)域內(nèi)部所有像素均不取這一特定顏色，而邊界外的像素則可具有與邊界相同的顏色值。比較掃描線求交的多邊形填充算法而言,種子填充算法則采用不同的原理：假設(shè)在多邊形區(qū)域內(nèi)部有一象素已知，由此出發(fā)找到區(qū)域內(nèi)的所有象素。區(qū)域可以分為四向連通和八向連通兩種：(1)四向連通區(qū)域指的是從區(qū)域上一點出發(fā)，可通過四個方向，即上、下、左、右移動的組合，在不越出區(qū)域的前提下，到達區(qū)域內(nèi)的任意象素；(2)八向連通區(qū)域指的是區(qū)域內(nèi)每一個象素，可以通過左、右、上、下、左上、右上、左下、右下這八個方向的移動的組合來到達。圖4.3.8(a)所示的區(qū)域是四連通區(qū)域。圖4.3.8(b)所示的區(qū)域是八連通區(qū)域。

圖3-18兩類聯(lián)通區(qū)域示意圖1.種子填充的遞歸算法（后進先出）可以使用棧結(jié)構(gòu)來實現(xiàn)簡單的種子填充算法。算法原理如下：種子象素入棧；當棧非空時重復(fù)執(zhí)行如下三步操作：(1)棧頂象素出棧；(2)將入棧象素置成多邊形色；(3)按上、下、左、右順序檢查與出棧象素相鄰的四個象素，若其中某個象素不在邊界且未置成多邊形色，則把該象素入棧。圖3.3.7遞歸種子填充算法及入棧示意圖程序從(x，y)開始，先檢測該點的顏色，如果它與邊界色和填充色均不相同，就用填充色填充該點，然后檢測相鄰位置，以確定它們是否是邊界色和填充色，若不是，就填充該相鄰點。這個過程延續(xù)到已經(jīng)檢測完區(qū)域邊界范圍內(nèi)的所有像素為止。

從當前點檢測相鄰像素有兩種方法：四向連通和八向連通。四向連通方法指的是從區(qū)域上一點出發(fā)，可通過四個方向，即上、下、左、右移動的組合，在不越出區(qū)域的前提下，到達區(qū)域內(nèi)的任意像素；八向連通方法指的是區(qū)域內(nèi)每一個像素，可以通過左、右、上、下、左上、右上、左下、右下這八個方向的移動的組合來到達。種子填充算法中允許從四個方向?qū)ふ蚁乱幌袼卣?，稱為四向算法；允許從八個方向搜索下一像素者，稱為八向算法。八向算法可以填充八向連通區(qū)域，也可以填充四向連通區(qū)域。但四向算法只能填充四向連通區(qū)域，而不能填充八向填充區(qū)域。以下我們只討論四向算法。只要把搜索方向從四個改變八個，即可得到八向算法。

下面程序給出了四向連通填充的遞歸算法。voidboundaryfill4(intseedx,intseedy,intfcolor,intbcolor){intcurrent=getpixel(seedx,seedy);if((current!=bcolor)&&(current!=fcolor)){ putpixel(seedx,seedy,fcolor); boundaryfill4(seedx+1,seedy,fcolor,bcolor); boundaryfill4(seedx–1,seedy,fcolor,bcolor); boundaryfill4(seedx,seedy+1,fcolor,bcolor); boundaryfill4(seedx,seedy–1,fcolor,bcolor);}}voidSeedFill(intcnt,POINT*pts,intseedx,intseedy,intfcolor,intbcolor){POINTv1,v2;inti;for(i=0;i<cnt–1;i++){v1=pts[i];v2=pts[i+1];BoundaryMark(v1.x,v1.y,v2.x,v2.y,bcolor);}boundaryfill4(seedx,seedy,fcolor,bcolor);}

這種算法的優(yōu)點是算法簡單，易于實現(xiàn)，也可以填充帶有內(nèi)孔的平面區(qū)域。但是這種算法需要很大的存儲空間以實現(xiàn)棧結(jié)構(gòu)，同一個像素多次入棧和出棧，所花費的時間也很多。因此后來提出了許多改進的算法，如書上的掃描線種子填充算法，我也提出了一個鏈隊列種子填充算法。

2.鏈隊列種子填充算法(先進先出）鏈隊列種子填充算法的算法基本思路是：從鏈隊列中獲得一個像素點，判斷其四連通像素點，若沒有填充，則填充它，并將它入隊列，如此循環(huán)，直到隊列空為止。1)鏈隊列示意圖2)鏈隊列種子填充算法過程圖3-20基于鏈隊列的種子填充算法示意圖的種子填充算法示意圖鏈隊列種子填充算法核心代碼(一)LinkQueueCreateQueue()//創(chuàng)建隊列{ LinkQueueq; QNode*p=newQNode; q.Front=p;q.Rear=p;q.Rear->Next=NULL; returnq;}鏈隊列種子填充算法核心代碼(二)POINTDequeue(LinkQueue&q)//刪除節(jié)點{ QNode*p;POINTx; p=q.Front;x=q.Front->Data;q.Front=q.Front->Next;deletep; returnx;}voidEnqueue(LinkQueue&q,POINTx)//加入節(jié)點{ QNode*p=newQNode; q.Rear->Next=p;q.Rear->Data=x;q.Rear=p;}3.3.4圓和橢圓的填充

上面所討論的多邊形區(qū)域的填充原理也可以推廣到圓域的填充。由于圓和橢圓的特殊屬性，即可依據(jù)任何欲填充的像素點與圓心的距離是否大于或小于半徑來判斷是否在圓外或圓內(nèi)，或者依據(jù)欲填充的像素點與橢圓兩焦點的距離之和是否大于或小于橢圓的半徑常數(shù)來判斷是否在橢圓外或橢圓內(nèi)，因此圓和橢圓的填充采用種子填充算法最為簡單，并且它不需要先對圓或橢圓邊界進行掃描轉(zhuǎn)換。

以下是圓的四向連通填充算法的C語言描述。voidCircleFill4(intxc,intyc,intr,intseedx,intseedy,intcolor){intfill=getpixel(seedx,seedy);if(((seedx–xc)*(seedx–xc)+(seedy–yc)*(seedy–yc)<=r*r)&&(fill!=color)){putpixel(seedx,seedy,color); CircleFill4(xc,yc,r,seedx+1,seedy,color);CircleFill4(xc,yc,r,seedx–1,seedy,color); CircleFill4(xc,yc,r,seedx,seedy+1,color); CircleFill4(xc,yc,r,seedx,seedy–1,color);}}3.3.5圖案填充

前面介紹的區(qū)域填充算法，把區(qū)域內(nèi)部的像素全部置成同一種顏色。但在實際應(yīng)用中，有時需要用一種圖案來填充平面區(qū)域。這可以通過對前述填充算法中寫像素的那部分代碼稍作修改來實現(xiàn)：在確定了區(qū)域內(nèi)一像素之后,不是馬上往該像素填色，而是先查詢圖案位圖的對應(yīng)位置。若是以透明方式填充圖案,則當圖案的對應(yīng)位置為1時,用前景色寫像素,否則,不改變該像素的值。若以不透明方式填充圖案，則視圖案位圖對應(yīng)位置為1或0來決定是用前景色還是背景色去寫像素。

1.圖案定義1)圖案分析2)圖案定義#defineM40#defineN60intj,pattern[M][N];for(i=0;i<M;i++)for(j=0;j<N;j++)pattern[i][j]=0;for(j=0;j<N;j++){pattern[0][j]=1;pattern[M/2][j]=1;}for(i=M/2;i<M;i++){pattern[i][N/2]=1;}for(i=0;i<M/2;i++){pattern[i][0]=1;}2.圖案填充if(pattern(x％M，y％N))putpixel(x,y,color)；elseputpixel(x,y,bkcolor)；

進行圖案填充時,在不考慮圖案旋轉(zhuǎn)的情況下，必須確定區(qū)域與圖案之間的位置關(guān)系。這可以通過把圖案原點與圖形區(qū)某點對齊的辦法來實現(xiàn)。對齊方法有兩種。第一種方式是把圖案原點與填充區(qū)域邊界或內(nèi)部的某點對齊。第二種方式是把圖案原點與填充區(qū)域外部的某點對齊。用第一種方式填充的圖案，將隨著區(qū)域的移動而跟著移動，看起來很自然。對于多邊形，可取區(qū)域邊界上最左邊的頂點。而對于圓和橢圓這樣的具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點，如中心，對應(yīng)圖案原點。從算法復(fù)雜性看，第二種方法比較簡單，并且在相鄰區(qū)域用同一圖案填充時，可以達到無縫連接的效果。但是它有一個潛在的毛病，即當區(qū)域移動時，圖案不會跟著移動。其結(jié)果是區(qū)域內(nèi)的圖案變了。

下面我們來討論在第二種對齊方式下，如何對平面區(qū)域填充圖案。假定圖案是一個M×N位圖，用M×N數(shù)組存放。M、N一般比需要填充的區(qū)域的尺寸小得多。所以圖案總是設(shè)計成周期性的，使之能通過重復(fù)使用，構(gòu)成任意尺寸的圖案。當需要填充的區(qū)域與當前掃描線的相交區(qū)間確定之后，假定相交區(qū)間上一像素坐標為(x,y)，則圖案位圖上的對應(yīng)位置為(x％M,y％N)，其中％為C語言整除取余運算符。若采用不透明方式填充圖案，則應(yīng)把算法中用前景色color寫像素的操作putpixel(x,y,color)，改為當圖案值為1時，用前景色color寫，否則，用背景色bkcolor寫，采用透明方式填充圖案時，只要去掉else分句即可。以下是把有序邊表填充算法改為用圖案填充的算法。為了節(jié)省篇幅，以下僅給出圖案的定義和有序邊表填充算法中修改后的FillScan函數(shù)。圖案定義：intpattern[8][8]={{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{0,0,0,1,1,1,1,1},{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{0,0,0,1,0,0,0,1},{1,1,1,1,0,0,0,1}};(注：這里列為x方向，行為y方向)修改后的FillScan函數(shù)：voidFillScan(intscan,Edge*active,intcolor){Edge*p1,*p2;inti;p1=active–>next;while(p1){p2=p1–>next;for(i=p1–>x;i<p2–>x;i++)

if(pattern[i%8][scan%8])

putpixel(i,scan,color);p1=p2–>next;}}上述程序的一個運行結(jié)果如圖3.12所示。

圖3.12圖案填充的一個實例

3.4裁剪

要把圖形的某一部分(窗口)顯示于屏幕上的指定位置(視區(qū))，必須正確識別圖形在窗口內(nèi)部分(可見部分)和窗口外部分(不可見部分)，以便把窗口內(nèi)的圖形信息輸出,而窗口外的部分則不輸出。我們把這種選擇可見信息的方法稱為裁剪。裁剪問題是計算機圖形學(xué)的基本問題之一，裁剪的邊界(即窗口)可以是任意多邊形，但常用的是矩形。被裁剪的對象可以是線段、字符、多邊形等，顯然直線段的裁剪是圖形裁剪的基礎(chǔ)，在本節(jié)中我們著重討論直線段的裁剪。

3.4.1點的裁剪裁剪算法的核心問題是速度，就一條直線段而言，就是要迅速而準確地判定：它是全部在窗口內(nèi)還是在窗口外，否則，它必定是部分在窗口內(nèi)。此時要求出它與窗口的交點，從而確定窗口內(nèi)的部分。

點的裁剪是最簡單的一種，但也是裁剪其他元素的基礎(chǔ)。判斷點的可見性可用下面簡單的不等式，若P（x，y）滿足： (3-7)則點P(x,y)為可見(在窗口內(nèi))，否則為不可見(在窗口外)。由點的裁剪方法我們自然地想到一種最簡單的裁剪方法——逐點比較法，即把圖形離散成點，然后逐點判斷各點是否滿足式(5-7)，若滿足則在窗口內(nèi)，為可見點，否則即在窗口外被裁掉。但這種方法速度太慢，不適用。因此我們有必要研究高效的裁剪方法。

圖3.13表示出直線段與窗口的位置關(guān)系有如下幾種情況：

3.4.2直線段的裁剪abcde圖3.13直線段與窗口的位置關(guān)系

⑴直線段兩個端點在窗口內(nèi)(線段c)；⑵直線段兩個端點在窗口外，且與窗口不相交（線段e,d)；⑶直線段兩個端點在窗口外，但與窗口相交(線段b)；⑷

直線段一個端點在窗口內(nèi)，一個端點在窗口外(線段a)。

由于矩形窗口是凸多邊形，因此，一條直線段的可見部分最多為一段，因此可以通過判斷兩個端點的可見性來確定直線段的可見部分。對于第一種和第二種情況，很容易判斷出：第一種為全部可見段；第二種為全部不可見段；但對于第三、四種情況，則需要根據(jù)線段與窗口邊界的相交情況加以進一步判斷。

直線段的裁剪算法有多種，在此我們介紹以下幾種算法：

一．編碼裁剪算法Cohen-Sutherland編碼裁剪亦稱Cohen-Sutherland算法，該算法基于下述考慮：每一線段或者整個位于窗口內(nèi)部，或者能夠被窗口分割而使其中的一部分能很快的舍棄。

１．基本原理１）區(qū)域編碼WytWybWxlWxr100110001010000100000010010101000110窗口２)可見性分析(１)code1=0且code2=0(全可見,顯示)(２)code1&code2≠0(全不見,退出),code1=1010,code2=0010(３)code1&code2=0且(code1≠0或code2≠0)(半可見,求交),如：code1=0001,code2=10001010&0010=00103)求交y=YT,YBX=XL,XR因此，該算法分為兩步：第一步先確定一條線段是否整個位于窗口內(nèi)，若是，則取之；第二步，確定該線段是否整個位于窗口外，若是則棄之；第三步，如果第一、二步的判斷均不成立，那么就通過窗口邊界所在的直線將線段分成兩部分，再對每一部分進行第一、二步的測式。

在具體實現(xiàn)該算法時，需把窗口邊界延長，把平面劃分成9個區(qū)，每個區(qū)用4位二進制代碼表示，如圖3.14所示。線段的兩個端點按其所在區(qū)域賦與對應(yīng)的代碼，4位代碼的意義如下(從右到左)：

第一位：如果端點在窗口左邊界的左側(cè)，則為1，否則為0；第二位：如果端點在窗口右邊界的右側(cè)，則為1，否則為0；第三位：如果端點在窗口下邊界的下側(cè)，則為1，否則為0；第四位：如果端點在窗口上邊界的上側(cè)，則為1，否則為0。

WytWybWxlWxr100110001010000100000010010101000110窗口圖3.14分區(qū)代碼由上述編碼規(guī)則可知，①如果兩個端點的編碼都為“0000”，則線段全部位于窗口內(nèi)；

②如果兩個端點編碼的位邏輯乘不為0，則整條線段必位于窗口外。③如果線段不能由上述兩種測試決定，則必須把線段再分割。簡單的分