基本圖形的生成與計(jì)算

第二章基本圖形的生成與計(jì)算2.3區(qū)域填充算法2.1直線的生成算法2.2圓的生成算法2.4字符的生成2.5圖形求交2.6圖形裁剪2.1直線的生成算法畫一條從(x1,y1)到(x2,y2)的直線，實(shí)質(zhì)上是一個(gè)發(fā)現(xiàn)最佳逼近直線的像素序列，并填入色彩數(shù)據(jù)的過程。這過程也稱為直線光柵化。連續(xù)性粗細(xì)、亮度要均勻像素逼近待畫直線速度2.1直線的生成算法2.1.1直線DDA算法

(DigitalDifferentialAnalyser)

假設(shè)直線的起點(diǎn)坐標(biāo)為P1(x1,y1)，終點(diǎn)坐標(biāo)為P2(x2,y2)x方向的增量為△x＝x2－x1

；y方向上增量為△y＝y(tǒng)2－y1

直線的斜率為k＝△y／△x

當(dāng)△x＞△y

時(shí)，讓x從x1

到x2變化，每步遞增1，那么，x的變化可以表示為xi+1＝xi＋1y的變化可以表示為yi+1＝y(tǒng)i＋k

用上式可求得圖中直線P1P2和y

向網(wǎng)格線的交點(diǎn)，但顯示時(shí)要用舍入找到最靠近交點(diǎn)處的象素點(diǎn)耒表示。當(dāng)△x<△y

時(shí)，讓y遞增1，x作相應(yīng)變化。

綜合考慮，按照從(x1,y1)到(x2,y2)方向不同，分8個(gè)象限(圖2.1)。對(duì)于方向在第1a象限內(nèi)的直線而言，取增量值Dx=1，Dy=m。對(duì)于方向在第1b象限內(nèi)的直線而言，取增量值Dy=1，Dx=1/m。2.1直線的生成算法2.1.1直線DDA算法（續(xù)）圖2.1直線方向的8個(gè)象限

象

限dx>dy?

Dx

Dy1atrue1

m1bfalse1/m12atrue-1m2bfalse-1/m13atrue-1-m3bfalse-1/m

-14atrue1

-m4bfalse1/m

-1表2.18個(gè)象限中的坐標(biāo)增量值

研究表中的數(shù)據(jù)，可以發(fā)現(xiàn)兩個(gè)規(guī)律。⒈

當(dāng)dx>dy時(shí)

Dx=1，Dy=m否則

Dx=1/m，Dy=1⒉

Dx、Dy的符號(hào)與dx、dy的符號(hào)相同。

2.1直線的生成算法2.1.1直線DDA算法（續(xù)）算法描述如下：dda_line(xa,ya,xb,yb,c)intxa,ya,xb,yb,c;{floatdelta_x,delta_y,x,y;intdx,dy,steps,k;dx=xbxa;dy=ybya;if(abs(dx)>abs(dy))steps=abs(dx);elsesteps=abs(dy);delta_x=(float)dx/(float)steps;delta_y=(float)dy/(float)steps;2.1直線的生成算法2.1.1直線DDA算法（續(xù)）x=xa;y=ya;set_pixel(x,y,c);for(k=1;k<=steps;k++){x+=delta_x;y+=delta_y;set_pixel(x,y,c);}}

使用DDA算法，每生成一條直線做兩次除法，畫線中每一點(diǎn)做兩次加法。因此，用DDA法生成直線的速度是相當(dāng)快的。

2.1直線的生成算法2.1.2直線Bresenham算法

設(shè)直線從起點(diǎn)(x1,y1)到終點(diǎn)(x2,y2)。直線可表示為方程y=mx+b，其中

b=y1-m*x1,m=（y2-y1)/(x2-x1)=dy/dx;

此處的討論先將直線方向限于1a象限(圖2.1)，在這種情況下，當(dāng)直線光柵化時(shí)，x每次都增加1個(gè)單元，即xi+1=xi

+1而y的相應(yīng)增加值應(yīng)當(dāng)小于1。為了光柵化，yi+1只可能選擇圖2.2中兩種位置之一。圖2.2縱坐標(biāo)的位置選擇

2.1直線的生成算法2.1.2直線Bresenham算法(續(xù)）

yi+1的位置選擇yi+1=yi或者yi+1=yi+1，選擇的原則是看精確值y與yi及yi+1的距離d1及d2的大小而定。計(jì)算公式為

y=m(xi

+1)+b(2.1)

d1=y

yi

(2.2)

d2=

yi+1

y

(2.3)如果d1d2>0，則yi+1=yi+1，否則yi+1=yi。將式(2.1)、(2.2)、(2.3)代入d1d2，再用dx乘等式兩邊，并以Pi=(d1d2)dx代入上述等式，得

Pi=2xidy2yidx+2dy+(2b1)dx

(2.4)d1d2是用以判斷符號(hào)的誤差。由于在1a象限，dx總大于0，所以Pi仍舊可以用作判斷符號(hào)的誤差。Pi+1為

Pi+1=Pi+2dy2(yi+1yi)dx

(2.5)2.1直線的生成算法2.1.2直線Bresenham算法(續(xù)）

求誤差的初值P1，可將x1、y1和b代入式(2.4)中的xi、yi而得到

P1=2dydx

綜述上面的推導(dǎo)，第1a象限內(nèi)的直線Bresenham算法思想如下：⒈

畫點(diǎn)(x1,y1)，dx=x2x1，dy=y2y1，計(jì)算誤差初值P1=2dy

dx，i=1；⒉

求直線的下一點(diǎn)位置xi+1=xi+1

如果Pi>0，則yi+1=yi+1，否則yi+1=yi；⒊

畫點(diǎn)(xi+1,

yi+1)；⒋

求下一個(gè)誤差Pi+1，如果Pi>0，則Pi+1=Pi+2dy2dx，否則

Pi+1=Pi+2dy；⒌

i=i+1；如果i<dx+1則轉(zhuǎn)步驟2；否則結(jié)束操作。2.1直線的生成算法2.1.2直線Bresenham算法(續(xù)）

Bresenham算法的優(yōu)點(diǎn)如下：⒈

不必計(jì)算直線的斜率，因此不做除法。⒉

不用浮點(diǎn)數(shù)，只用整數(shù)。⒊

只做整數(shù)加減運(yùn)算和乘2運(yùn)算，而乘2運(yùn)算可以用移位操作實(shí)現(xiàn)。Bresenham算法的運(yùn)算速度很快，并適于用硬件實(shí)現(xiàn)。討論：以上討論的是0＜△y＜△x的情況，對(duì)于適用所有8個(gè)方向的直線(圖2.1)的生成算法，則要考慮以判斷條件|dx|>|dy|為分支，并分別將2a、3a象限的直線和3b、4b象限的直線變換到1a、4a和2b、1b象限方向去，以實(shí)現(xiàn)程序處理的簡(jiǎn)潔。2.2圓的生成算法2.2.1基礎(chǔ)知識(shí)

給出圓心坐標(biāo)(xc,

yc)和半徑r，逐點(diǎn)畫出一個(gè)圓周的公式有下列兩種：⒈

直角坐標(biāo)法

(xxc)2+(yyc)2=r2由上式導(dǎo)出：

當(dāng)xxc從r到r作加1遞增時(shí)，就可以求出對(duì)應(yīng)的圓周點(diǎn)的y坐標(biāo)。但是這樣求出的圓周上的點(diǎn)是不均勻的，xxc越大，對(duì)應(yīng)生成圓周點(diǎn)之間的圓周距離也就越長。因此，所生成的圓不美觀。2.2圓的生成算法2.2.1基礎(chǔ)知識(shí)(續(xù)）

⒉

極坐標(biāo)法

x=

xc+r·cosθ，y=

yc+r·sinθ當(dāng)θ從0到π作遞增時(shí)，由此式便可求出圓周上均勻分布的360個(gè)點(diǎn)的(x,y)坐標(biāo)。

利用圓周坐標(biāo)的對(duì)稱性，此算法還可以簡(jiǎn)化。將圓周分為8個(gè)象限(圖2.3)，只要將第1a象限中的圓周光柵點(diǎn)求出，其余7部分圓周就可以通過對(duì)稱法則計(jì)算出來。

圖2.3圓心在(0,0)點(diǎn)圓周生成時(shí)的對(duì)稱變換2.2圓的生成算法2.2.2圓的Bresenham算法

設(shè)圓的半徑為r。先考慮圓心在(0,0)，并從x=0、y=r開始的順時(shí)針方向的1/8圓周的生成過程。在這種情況下，x每步增加1，從x=0開始，到x=y結(jié)束。即有

xi+1=xi+1相應(yīng)的yi+1則在兩種可能中選擇：

yi+1=

yi或者yi+1=

yi1選擇的原則是考察精確值y是靠近yi還是靠近yi1(圖2.4)，計(jì)算式為y2=r2(xi+1)2d1=yi2y2=yi2r2+(xi+1)2d2=y2(yi1)2=r2(xi+1)2(yi1)2圖2.4y的位置

2.2圓的生成算法2.2.2圓的Bresenham算法(續(xù)）

令pi=d1d2，并代入d1、d2，則有

pi=2(xi+1)2+yi2+(yi1)22r2

(2.6)pi稱為誤差。如果pi<0則yi+1=yi，否則yi+1=yi1。pi的遞歸式為

pi+1=pi+4xi

+6+2(yi2+1yi2)2(yi+1yi)(2.7)pi的初值由式(2.6)代入xi=0，yi=r而得

p1=32r

(2.8)根據(jù)上面的推導(dǎo)，圓周生成算法思想如下：⒈

求誤差初值，p1=32r，i=1，畫點(diǎn)(0,r)；⒉

求下一個(gè)光柵位置，其中xi+1=xi+1，如果pi<0則yi+1=yi，否則yi+1=yi1；⒊

畫點(diǎn)(xi+1,

yi+1)；⒋

計(jì)算下一個(gè)誤差，如果pi<0則pi+1=pi+4xi+6，否則pi+1=pi+4(xiyi)+10；⒌

i=i+1，如果x=y則結(jié)束，否則返回步驟2。2.2圓的生成算法2.2.2圓的Bresenham算法(續(xù)）圓的Bresenham算法的程序?qū)崿F(xiàn)如下：

circle(xc,yc,radius,c)

intxc,yc,radius,c;

{

intx,y,p;

x=0;

y=radius;

p=32*radius；

while(x<y){

plot_circle_points(xc,yc,x,y,c);

if(p<0)p=p+4*x+6;

else{

p=p+4*(xy)+10;

y=1;

}

x+=1;

}

if(x==y)

plot_circle_points(xc,yc,x,y,c);

}

2.2圓的生成算法2.2.2圓的Bresenham算法(續(xù)）plot_circle_points(xc,yc,x,y,c)intxc,yc,x,y,c;{set_pixel(xc+x,yc+y,c);set_pixel(xcx,yc+y,c);set_pixel(xc+x,ycy,c);set_pixel(xcx,ycy,c);set_pixel(xc+y,yc+x,c);

set_pixel(xcy,yc+x,c);set_pixel(xc+y,ycx,c);set_pixel(xcy,ycx,c);}2.3區(qū)域填充算法2.3.1基礎(chǔ)知識(shí)

區(qū)域填充即給出一個(gè)區(qū)域的邊界，要求對(duì)邊界范圍內(nèi)的所有像素單元賦予指定的顏色代碼。區(qū)域填充中最常用的是多邊形填色。

多邊形的表示方法頂點(diǎn)表示點(diǎn)陣表示圖2.5掃描線與多邊形相交

圖2.6光柵化后直線變成離散點(diǎn)

多邊形填色一個(gè)首要的問題，是判斷一個(gè)像素是在多邊形內(nèi)還是多邊形外。數(shù)學(xué)上提供的方法是“掃描交點(diǎn)的奇偶數(shù)判斷法”。

2.3區(qū)域填充算法2.3.1基礎(chǔ)知識(shí)(續(xù)）

2.3區(qū)域填充算法2.3.1基礎(chǔ)知識(shí)(續(xù)）

填色算法分為兩大類：⒈

掃描線填色(Scan-LineFilling)算法。這類算法建立在多邊形邊界的矢量形式數(shù)據(jù)之上，可用于程序填色，也可用于交互填色。⒉

種子填色(SeedFilling)算法。這類算法建立在多邊形邊界的圖像形式數(shù)據(jù)之上，并還需提供多邊形邊界內(nèi)一點(diǎn)的坐標(biāo)。所以，它一般只能用于人機(jī)交互填色，而難以用于程序填色。2.3區(qū)域填充算法2.3.2掃描線填色算法

算法的基本思想。多邊形以n、x_array、y_array的形式給出，其中，x_array、y_array中存放著多邊形的n個(gè)頂點(diǎn)的x，y坐標(biāo)。用水平掃描線從上到下掃描由點(diǎn)線段構(gòu)成的多段定義成的多邊形。每根掃描線與多邊形各邊產(chǎn)生一系列交點(diǎn)。這些交點(diǎn)按照x坐標(biāo)進(jìn)行分類，將分類后的交點(diǎn)成對(duì)取出，作為兩個(gè)端點(diǎn)，以所需要填的色彩畫水平直線。多邊形被掃描完畢后，填色也就完成。2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

上述基本思想中，有幾個(gè)問題需要解決或改進(jìn)：⒈

左、右頂點(diǎn)處理。當(dāng)以1、2、3的次序畫多邊形外框時(shí)，多邊形的左頂點(diǎn)和右頂點(diǎn)如圖2.7中所示的頂點(diǎn)2。它們具有以下性質(zhì)。左頂點(diǎn)2：y1<y2<y3右頂點(diǎn)2：y1>y2>y3

其中y1、y2、y3是3個(gè)相鄰的頂點(diǎn)的y坐標(biāo)。圖2.7多邊形的頂點(diǎn)

當(dāng)掃描線與多邊形的每個(gè)頂點(diǎn)相交時(shí)，會(huì)同時(shí)產(chǎn)生2個(gè)交點(diǎn)。這時(shí)，填色就會(huì)因掃描交點(diǎn)的奇偶計(jì)數(shù)出錯(cuò)而出現(xiàn)錯(cuò)誤。因此，對(duì)所有左、右頂點(diǎn)作如下處理：2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

左、右頂點(diǎn)的入邊(以該頂點(diǎn)為終點(diǎn)的那條邊，即1–2邊)之終點(diǎn)刪去。對(duì)于左頂點(diǎn)，入邊端點(diǎn)(x1,y1)、(x2,y2)修改為(x1,y1)、(

,y21)；對(duì)于右頂點(diǎn)，入邊端點(diǎn)(x1,y1)、(x2,y2)修改為(x1,y1)、(

,y2+1)；其中，，即入邊的斜率。對(duì)于多邊形的上頂點(diǎn)(y2>y1、y2>y3)或下頂點(diǎn)(y2<y1、y2<y3)，奇偶計(jì)數(shù)保持正確。⒉

水平邊處理。水平邊(y1=y2)與水平掃描線重合無法求交點(diǎn)。因此，將水平邊畫出后刪去，不參加求交點(diǎn)及求交點(diǎn)以后的操作。

2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

⒊

掃描線與邊的求交點(diǎn)方法采用遞歸算法。以(x1,y1)、(x2,y2)為端點(diǎn)的邊與第i+1條掃描線的交點(diǎn)為此式表示交點(diǎn)不為(x1,y1)。否則，交點(diǎn)為(x1,y1)。⒋

減少求交計(jì)算量，采用活性邊表。對(duì)于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分,每根掃描線與多邊形所有邊求交的操作是一種浪費(fèi)，需要加以改進(jìn)。

活性邊表(ActiveListofSide)的采用將多邊形的邊分成兩個(gè)子集：與當(dāng)前掃描線相交的邊的集合，以及與當(dāng)前掃描線不相交的邊的集合。對(duì)后者不必進(jìn)行求交運(yùn)算，這樣就提高了算法的效率。2.3區(qū)域填充算法2.3.2掃描線填色算法(續(xù)）

圖2.8活性邊表及其指針的表示

掃描線填充算法是一種非常有效的算法，它對(duì)于每個(gè)象素只訪問一次，其缺點(diǎn)是對(duì)于各種表的維持和排序的耗費(fèi)大。2.3區(qū)域填充算法種子填色又稱邊界填色(BoundaryFilling)。它的功能是，給出多邊形光柵化后的邊界位置及邊界色代碼boundary_color，以及多邊形內(nèi)的一點(diǎn)(x,y)位置，要求將顏色fill_color填滿多邊形。2.3.3種子填色算法算法要求區(qū)域是連通的連通性4連通、8連通4連通：從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；

8連通從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，可通過上、下、左、右、左上、左下、右上、右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意象素；

2.3區(qū)域填充算法2.3.3種子填色算法(續(xù)）

2.3區(qū)域填充算法圖2.10四鄰法和八鄰法種子填色

2.4字符的生成2.4.1點(diǎn)陣式字符

點(diǎn)陣式字符將字符形狀表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。使用點(diǎn)陣式字符時(shí)，需將字庫中的矩形點(diǎn)陣復(fù)制到緩沖器中指定的單元中去。在復(fù)制過程中，可以施加變換，以獲得簡(jiǎn)單的變化。圖2.11(b)~(d)列出了以字母P為原型的一些變化例子。圖2.11點(diǎn)陣式字符及其變化

2.4字符的生成2.4.2矢量式字符

矢量式字符將字符表達(dá)為點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻畫。圖2.12示出用矢量式表示的字符“B”?！癇”是由頂點(diǎn)序列{a,b,c,d,e,f,e,g,h,i,j,k,j,

a,l}的坐標(biāo)表達(dá)。圖2.12矢量式表示字符“B”2.4字符的生成2.4.3方向編碼式字符

方向編碼式字符用有限的若干種方向編碼來表達(dá)一個(gè)字符。圖2.13示出8個(gè)方向的編碼為0~7。圖2.14(a)示出字母“B”的方向矢量構(gòu)成。這樣，“B”就表示為8方向編碼{0000123444000123444406666}。方向編碼式字符很容易被填入幀暫存寄存器中予以顯示(圖2.14(b))，方向編碼所占的空間比較小，它也能接受一些特定的變換操作。圖2.13字符的8方向編碼

圖2.14方向編碼式字符的實(shí)例2.4字符的生成2.4.4輪廓字形技術(shù)直接使用點(diǎn)陣式字符方法將耗費(fèi)巨大的存儲(chǔ)空間。壓縮方法有多種，最簡(jiǎn)單的有黑白段壓縮法。另一種方法是部件壓縮法。三是輪廓字形法，這種方法壓縮比大，且能保證字符質(zhì)，是當(dāng)今國際上最流行的一種方法。

輪廓字形法采用直線、或者二次Bezier曲線、三次Bezier曲線的集合來描述一個(gè)字符的輪廓線。輪廓線構(gòu)成一個(gè)或若干個(gè)封閉的平面區(qū)域。輪廓線定義和一些指示橫寬、豎寬、基點(diǎn)、基線等的控制信息，就構(gòu)成了字符的壓縮數(shù)據(jù)。2.5圖形求交在計(jì)算機(jī)圖形學(xué)中常常會(huì)遇到求交計(jì)算。求交運(yùn)算是比較復(fù)雜的，為了減少計(jì)算量，在進(jìn)行真正的求交計(jì)算之前，往往先用凸包等輔助結(jié)構(gòu)進(jìn)行粗略地比較，排除那些顯然不相交的情形。。

求交問題可以分為兩類：

求交點(diǎn)求交線

2.5圖形求交

2.5.1求交點(diǎn)算法

求交點(diǎn)可以分兩種情況，即求線與線的交點(diǎn)以及求線與面的交點(diǎn)。⒈

直線段與直線段的交點(diǎn)假設(shè)兩條直線的端點(diǎn)分別為P1、P2和Q1、Q2，則直線可以用向量形式表示為P(t)=A+Bt，

0≤t≤1Q(s)=C+Ds，

0≤s≤1其中，A=P1，B=P2P1，C=Q1，D=Q2Q1。構(gòu)造方程

A+Bt=C+Ds(2.9)

對(duì)三維空間中的直線段來說，上述方程組實(shí)際上是一個(gè)二元一次方程組，由3個(gè)方程式組成?？梢詮钠渲袃蓚€(gè)解出s、t，再用第三個(gè)驗(yàn)證解的有效性。當(dāng)所得的解(ti,

si)是有效解時(shí)，可用兩個(gè)方程之一計(jì)算交點(diǎn)坐標(biāo)，例如P(ti)=A+Bti。

2.5圖形求交

2.5.1求交點(diǎn)算法（續(xù)）

根據(jù)向量的基本性質(zhì)，可直接計(jì)算s與t。對(duì)方程(2.9)兩邊構(gòu)造點(diǎn)積得

(CD)·(A+Bt)=(CD)·(C+Ds)由于CD同時(shí)垂直于C和D，等式右邊為0。故有類似地有2.5圖形求交

2.5.1求交點(diǎn)算法（續(xù)）

⒉

直線段與二次曲線的交點(diǎn)考慮平面上一條直線與同平面的一條二次曲線的交點(diǎn)。假設(shè)曲線方程為f(x,y)=0直線段方程為(x,y)=(x1+tdx,y1+tdy)則在交點(diǎn)處有

f(x1+tdx,y1+tdy)=0當(dāng)曲線為二次曲線時(shí)，上述方程可寫為

at2+bt+c=0用二次方程求根公式即可解出t值。⒊

圓錐曲線與圓錐曲線的交點(diǎn)在進(jìn)行一對(duì)圓錐曲線的求交時(shí)，把其中一條圓錐曲線用代數(shù)法或幾何法表示為隱函數(shù)形式，另一條表示為參數(shù)形式(如二次NURBS曲線)。將參數(shù)形式代入隱函數(shù)形式可得到關(guān)于參數(shù)的四次方程，2.5圖形求交

2.5.1求交點(diǎn)算法（續(xù)）

下面討論線與面的交點(diǎn)的求法。⒈

直線段與平面的交點(diǎn)圖2.15線段與平面求交

如圖2.15所示。把平面上的點(diǎn)表示為P(u,w)=A+uB+wC，直線段上的點(diǎn)表示為Q(t)=D+tE，二者的交點(diǎn)記為R。假設(shè)線段不平行于平面，則它們交于

R=P(u,w)=Q(t)，即A+uB+wC=D+tE2.5圖形求交

2.5.1求交點(diǎn)算法（續(xù)）

等式兩邊點(diǎn)乘(BC)，得

(BC)·(A+uB+wC)=(BC)·(D+tE)由于BC既垂直于B，又垂直于C，故有

(BC)·A=(BC)·(D+tE)可解出類似求得如果是直線與平面區(qū)域求交點(diǎn)，則要進(jìn)一步判斷交點(diǎn)是否在平面的有效區(qū)域中，其算法可參見2.5.3節(jié)。2.5圖形求交

2.5.1求交點(diǎn)算法（續(xù)）

⒉

圓錐曲線與平面的交點(diǎn)圓錐曲線與平面求交點(diǎn)時(shí)，可以把圓錐曲線表示為參數(shù)形式，并把圓錐曲線的參數(shù)形式代入平面方程，即可得到參數(shù)的二次方程，從而進(jìn)行求解。⒊

圓錐曲線與二次曲面的交點(diǎn)圓錐曲線與二次曲面求交點(diǎn)時(shí)，可把圓錐曲線的參數(shù)形式代入二次曲面的隱式方程，得到參數(shù)的四次方程，用四次方程求根公式求解。2.5圖形求交

2.5.2

求交線算法

⒈

平面與平面的交線先考慮最簡(jiǎn)單的情形。兩個(gè)平面區(qū)域分別由P(u,w)，Q(s,t)，u，w，s，t[0,1]定義。如果它們不共面而且不分離，則必交于一直線段。這條直線必落在P(u,w)Q(s,t)=0所定義的無限直線上。這是個(gè)含有4個(gè)未知數(shù)，3個(gè)方程式的方程組，只要分別與8條邊界線方程：u=0，u=1，w=0，w=1，s=0，s=1，t=0，t=1聯(lián)立，即可求出線段的兩個(gè)端點(diǎn)的參數(shù)。

2.5圖形求交2.5.2

求交線算法

（續(xù)）

⒉

平面與二次曲面的交線

代數(shù)法:把二次曲面表示為代數(shù)形式

Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0

通過平移與旋轉(zhuǎn)坐標(biāo)變換把平面變?yōu)閤Oy平面，對(duì)二次曲面進(jìn)行同樣的坐標(biāo)變換。由于在新坐標(biāo)系下平面的方程為z=0，所以新坐標(biāo)系下二次曲面方程中，把含z項(xiàng)都去掉即為平面與二次曲面的交線方程。對(duì)該交線方程進(jìn)行一次逆坐標(biāo)變換即可獲得在原坐標(biāo)系下的交線方程。

幾何法:幾何法存儲(chǔ)曲線的類型(橢圓、拋物線或雙曲線)，以及定義參數(shù)(中心點(diǎn)、對(duì)稱軸、半徑等)的數(shù)值信息，使用局部坐標(biāo)系到用戶坐標(biāo)系的變換，把局部坐標(biāo)系下的定義參數(shù)變換到用戶坐標(biāo)系直接使用。當(dāng)平面與二次曲面的交線需要精確表示時(shí)，往往采用幾何法求交。2.5圖形求交2.5.2

求交線算法

（續(xù)）

下面以平面—球求交為例，說明幾何法求交算法。平面用一個(gè)記錄p表示，p的兩個(gè)子域p.b、p.w分別代表平面上一點(diǎn)、平面法向量。球面用記錄s表示，它的兩個(gè)子域s.c、s.r分別代表球面中心和半徑。則可寫出平面與球面相交的算法如下：plane_sphere_intersect(p,s)planep;spheres;{d=球面中心到平面的有向距離；if(abs(d)==s.r){2個(gè)面相交于一(切)點(diǎn)s.cd*p.w;}elseif(abs(d)>s.r){兩個(gè)面無交；}2.5圖形求交2.5.2

求交線算法

（續(xù)）

else{所求交線是圓。其圓心、半徑、圓所在平面法向量為c=s.cd*p.w;r=sqrt(s.r2d2);w=p.w;}}

2.5圖形求交2.5.2

求交線算法（續(xù)）

⒊

平面與參數(shù)曲面的交線求平面與參數(shù)曲面的交線，最簡(jiǎn)單的方法是把表示參數(shù)曲面的變量(x(s,t),y(s,t),z(s,t))代入平面方程

ax+by+cz+d=0得到用參數(shù)曲面的參數(shù)s、t表示的交線方程

ax(s,t)+by(s,t)+cz(s,t)+d=0

另一種方法是，用平移和旋轉(zhuǎn)對(duì)平面進(jìn)行坐標(biāo)變換，使平面成為新坐標(biāo)系下的xOy平面。再將相同的變換應(yīng)用于參數(shù)曲面方程，得到參數(shù)曲面在新坐標(biāo)系下的方程

(x*,y*,z*)=(x*(s,t),y*(s,t),z*(s,t))由此得交線在新坐標(biāo)系下的方程為z*(s,t)=0。2.5圖形求交2.5.3包含判定算法在進(jìn)行圖形求交時(shí)，常常需要判定兩個(gè)圖形間是否有包含關(guān)系。如點(diǎn)是否包含在線段、平面區(qū)域或三維形體中，線段是否包含在平面區(qū)域或三維形體中，等等。許多包含判定問題可轉(zhuǎn)化為點(diǎn)的包含判定問題，如判斷線段是否在平面上的問題可以轉(zhuǎn)化為判斷線段兩端點(diǎn)是否在平面上。判斷點(diǎn)與線段的包含關(guān)系，也就是判斷點(diǎn)與線的最短距離是否位于容差范圍內(nèi)。造型中常用的線段有3種，即直線段、圓錐曲線段(主要是圓弧)和參數(shù)曲線(主要是Bezier曲線、B樣條與NURBS曲線)。點(diǎn)與面的包含判定也類似地分為3種情況。下面分別予以討論。2.5圖形求交2.5.3包含判定算法（續(xù)）⒈

點(diǎn)與直線段的包含判定假設(shè)點(diǎn)坐標(biāo)為P(x,y,z)，直線段端點(diǎn)為P1(x1,y1,z1)、P2(x2,y2,z2)，則點(diǎn)P到線段P1P2的距離的平方為

d2=(xx1)2+(yy1)2+(zz1)2[(x2x1)(xx1)+(y2y1)(yy1)+

(z2z1)(zz1)]2/[(x2x1)2+(y2y1)2+(z2z1)2]

當(dāng)d2<2時(shí)，認(rèn)為點(diǎn)在線段(或其延長線)上，這時(shí)還需進(jìn)一步判斷點(diǎn)是否落在直線段的有效區(qū)間內(nèi)。對(duì)坐標(biāo)分量進(jìn)行比較，假設(shè)線段兩端點(diǎn)的x分量不等(否則所有分量均相等，那么線段兩端點(diǎn)重合，線段退化為一點(diǎn))，那么當(dāng)xx1與xx2異號(hào)時(shí)，點(diǎn)P在線段的有效區(qū)間內(nèi)。2.5圖形求交2.5.3包含判定算法（續(xù)）⒉

點(diǎn)與圓錐曲線段的包含判定以圓弧為例，假設(shè)點(diǎn)的坐標(biāo)為(x,y,z)，圓弧的中心為(x0,y0,z0)，半徑為r，起始角為1，終止角為2。圓弧所在平面為

ax+by+cz+d=0

先判斷點(diǎn)是否在該平面上；若點(diǎn)在該平面上，則通過坐標(biāo)變換，把問題轉(zhuǎn)換成二維空間中的問題。

對(duì)于平面上一點(diǎn)P(x,y)，判斷P是否在圓弧上，可分兩步進(jìn)行。第一步判斷P是否在圓心為(x0,y0)，半徑為r的圓的圓周上，即下式是否成立第二步判斷P是否在有效的圓弧段內(nèi)。2.5圖形求交2.5.3包含判定算法（續(xù)）⒊

點(diǎn)與參數(shù)曲線的包含判定設(shè)點(diǎn)坐標(biāo)為P(x,y,z)，參數(shù)曲線方程為Q(t)=(x(t),y(t),z(t))。點(diǎn)與參數(shù)曲線的求交計(jì)算包括3個(gè)步驟。⑴

計(jì)算參數(shù)t的值，使P到Q(t)的距離最小。⑵

判斷t是否在有效參數(shù)區(qū)間內(nèi)(通常為[0,1])。⑶

判斷Q(t)與P的距離是否小于。若第(2)、(3)步的判斷均為“是”，則點(diǎn)在曲線上；否則，點(diǎn)不在曲線上。第一步應(yīng)計(jì)算參數(shù)t，使得|PQ(t)|最小，即R(t)=(PQ(t))(PQ(t))=|PQ(t)|2最小。根據(jù)微積分知識(shí)，在該處R(t)=0，即Q(t)[PQ(t)]=0。用數(shù)值方法解出t值，再代入曲線參數(shù)方程，可求出曲線上對(duì)應(yīng)點(diǎn)的坐標(biāo)。第(2)、(3)步不再贅述。2.5圖形求交2.5.3包含判定算法（續(xù)）⒋

點(diǎn)與平面區(qū)域的包含判定設(shè)點(diǎn)坐標(biāo)為P(x,y,z)，平面方程為ax+by+cz+d=0。則點(diǎn)到平面的距離為若d<，則認(rèn)為點(diǎn)在平面上；否則，認(rèn)為點(diǎn)不在平面上。對(duì)落在平面上的點(diǎn)還應(yīng)進(jìn)一步判別它是否落在有效區(qū)域內(nèi)。下面以平面區(qū)域多邊形為例，介紹有關(guān)算法。判斷平面上的一個(gè)點(diǎn)是否包含在該平面的一個(gè)多邊形內(nèi)，有多種算法，這里僅介紹常用的3種，即叉積判斷法、夾角之和檢驗(yàn)法以及交點(diǎn)計(jì)數(shù)檢驗(yàn)法。

2.5圖形求交2.5.3包含判定算法（續(xù)）⑴

叉積判斷法假設(shè)判斷點(diǎn)為P0，多邊形頂點(diǎn)按順序排列為P1，P2，…，Pn，如圖2.16所示。令Vi=PiP0，其中，i=1,2,…,n，Vn+1=V1。那么，P0在多邊形內(nèi)的充要條件是叉積ViVi+1(i=1,2,…,n)的符號(hào)相同。叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為凹多邊形時(shí)，可采用后面介紹的兩種方法。圖2.16叉積判斷法2.5圖形求交2.5.3包含判定算法（續(xù)）⑵

夾角之和檢驗(yàn)法假設(shè)某平面上有點(diǎn)P0和多邊形P1P2P3P4P5，如圖2.17所示。將點(diǎn)P0分別與Pi相連，構(gòu)成向量Vi=PiP0，假設(shè)PiP0Pi+1=i。如果，則點(diǎn)P0在多邊形之外，如圖2.17(a)所示。如果，則點(diǎn)P0在多邊形之內(nèi)，如圖2.17(b)所示。i可通過公式計(jì)算。令Si=ViVi+1，Ci=Vi·Vi+1，則tan(i)=Si/Ci。所以，i=arctan(Si/Ci)且i的符號(hào)即代表角度的方向。圖2.17夾角之和檢驗(yàn)法

2.5圖形求交2.5.3包含判定算法（續(xù)）在多邊形邊數(shù)不超過43的情況下，可以采用下列近似公式計(jì)算i：

Si≤Ci

Si>Ci其中，常數(shù)d=0.0355573。當(dāng)i≥π時(shí)，可判定P0在多邊形內(nèi)。當(dāng)i＜π時(shí)，可判定P0在多邊形外。⑶

交點(diǎn)計(jì)數(shù)檢驗(yàn)法當(dāng)多邊形是凹多邊形，甚至還帶孔時(shí)，可采用交點(diǎn)計(jì)數(shù)法判斷點(diǎn)是否在多邊形內(nèi)。具體做法是，從判斷點(diǎn)作一射線至無窮遠(yuǎn)2.5圖形求交2.5.3包含判定算法（續(xù)）求射線與多邊形邊的交點(diǎn)個(gè)數(shù)。若交點(diǎn)個(gè)數(shù)為奇數(shù)，則點(diǎn)在多邊形內(nèi)；否則，點(diǎn)在多邊形外。如圖2.18所示，射線a、c與多邊形分別交于2個(gè)點(diǎn)和4個(gè)點(diǎn)，為偶數(shù)，故判斷點(diǎn)A、C在多邊形外。而射線b、d與多邊形分別交于3個(gè)點(diǎn)和1個(gè)點(diǎn)，為奇數(shù)，所以點(diǎn)B、D在多邊形內(nèi)。圖2.18交點(diǎn)計(jì)數(shù)法

當(dāng)射線穿過多邊形頂點(diǎn)時(shí)，必須特殊對(duì)待。若共享頂點(diǎn)的兩邊在射線的同一側(cè)，則交點(diǎn)計(jì)數(shù)加2，否則加1。按這種方法，交點(diǎn)計(jì)數(shù)為偶數(shù)時(shí)點(diǎn)在多邊形外；交點(diǎn)計(jì)數(shù)為奇數(shù)時(shí)點(diǎn)在多邊形內(nèi)。

2.5圖形求交2.5.3包含判定算法（續(xù)）⒌

點(diǎn)與二次曲面/參數(shù)曲面的包含判定假設(shè)點(diǎn)坐標(biāo)為P(x0,y0,z0)，二次曲面方程為Q(x,y,z)=0，則當(dāng)|Q(x0,y0,z0)|<時(shí)，認(rèn)為點(diǎn)在該二次曲面上。有時(shí)還要判斷點(diǎn)是否在曲面有效范圍內(nèi)。⒍

點(diǎn)與三維形體的包含判定判斷點(diǎn)是否被三維形體所包含，可先判斷點(diǎn)是否在三維形體的表面上，然后判斷點(diǎn)是否在形體內(nèi)部，其方法因形體不同而異。以凸多面體為例。設(shè)凸多面體某個(gè)面的平面方程為ax+by+cz+d=0，調(diào)整方程系數(shù)的符號(hào)，使當(dāng)ax+by+cz+d<0時(shí)，點(diǎn)(x,y,z)位于該平面兩側(cè)方向包含該凸多面體的一側(cè)。于是要檢驗(yàn)一個(gè)點(diǎn)是否在凸多面體內(nèi)部，只要檢驗(yàn)它是否對(duì)凸多面體的每一個(gè)面均滿足以上的不等式即可。2.5圖形求交2.5.4

重疊判定算法

判斷空間一點(diǎn)與另一點(diǎn)是否重疊，只要判斷兩點(diǎn)之間的距離是否等于0即可。判斷兩條線段是否重疊，可先判斷它們是否共線，即判斷一條線段上的任意兩點(diǎn)是否在另一條線段所在的直線上，或是比較兩條線段的方向向量并判斷一條線段上的任意一點(diǎn)是否在另一條線段所在的直線上。若兩條線段不共線，則它們不可能重疊；否則，可通過端點(diǎn)坐標(biāo)的比較來判斷兩線段的重疊部分。判斷兩個(gè)平面的重疊關(guān)系，一種方法是判斷一個(gè)平面上不共線的3個(gè)點(diǎn)是否在另一個(gè)平面上；另一種方法是先比較兩個(gè)平面的法向量，再判斷一個(gè)平面上的某點(diǎn)是否在另一個(gè)平面上。2.5圖形求交2.5.5

凸包計(jì)算

一個(gè)圖形的凸包，就是包含這個(gè)圖形的一個(gè)凸的區(qū)域。例如，一個(gè)平面圖形的凸包可以是一個(gè)凸多邊形，一個(gè)三維物體的凸包可以是一個(gè)凸多面體。一個(gè)圖形的凸包不是惟一的。在進(jìn)行圖形求交計(jì)算時(shí)，如果兩個(gè)圖形的凸包不相交，顯然它們不可能相交。否則，需要進(jìn)一步計(jì)算。包圍盒是一種常用的凸包。二維包圍盒是二維平面上的一個(gè)矩形，它的兩條邊分別與兩條坐標(biāo)軸x、y平行，可以表示xmin≤x≤xmax、ymin≤y≤ymax。三維空間中的包圍盒是一個(gè)長方體，可表示為3個(gè)不等式，即xmin≤x≤xmax、ymin≤y≤ymax、zmin≤z≤zmax。兩個(gè)包圍盒相交的充要條件是它們?cè)诿恳粋€(gè)坐標(biāo)軸方向上都相交。2.5圖形求交2.5.5

凸包計(jì)算

求多邊形或多面體的包圍盒是相當(dāng)簡(jiǎn)便的。只要遍歷其所有頂點(diǎn)，就的方法求出包圍盒。對(duì)于一般的幾何形體，則要根據(jù)其具體性質(zhì)來求。

對(duì)含有曲線、曲面的幾何體進(jìn)行求交時(shí)，常常先求它們的一個(gè)凸多邊形或凸多面體的凸包。由于凸多邊形和凸多面體間的求交相對(duì)簡(jiǎn)單，因此可以節(jié)省一定的計(jì)算量。例如，Bezier曲線、B樣條和NURBS曲線、曲面具有凸包性質(zhì)，其控制多邊形或控制網(wǎng)格是其本身的凸包一般的凸包的求法因具體情況而異，下面舉一個(gè)求圓弧凸包的例子。設(shè)圓弧段的圓方程為(xx0)2+(yy0)2=r2，圓弧起始角為1，終止角為2。對(duì)圓弧計(jì)算凸包如圖2.19所示。先根據(jù)起始角1與終止角2求出相應(yīng)的弧端點(diǎn)P1、P2坐標(biāo)，進(jìn)而求出弧的弦中點(diǎn)Pm=(P1+P2)/2。

2.5圖形求交2.5.5

凸包計(jì)算（續(xù)）

再用下式計(jì)算弧中點(diǎn)Pc：

則該弧的包圍盒頂點(diǎn)為P1、P1+(PcPm)、P2+(PcPm)、P2。圖2.19圓弧的凸包

2.6圖形裁剪裁剪(clipping)是裁去窗口之外物體或物體部分的一種操作。2.6.1直線的剪裁

Cohen-Sutherland算法；2.6.2多邊形的剪裁

Sutlerland_Hodgman算法2.6.3字符串的剪裁

2.6圖形裁剪2.6.1

直線的剪裁

直線和窗口的關(guān)系可以分為如下3類(圖2.20)：⑴

整條直線在窗口內(nèi)。此時(shí)，不需剪裁，顯示整條直線。⑵

整條直線在窗口外，此時(shí)，不需剪裁，不顯示整條直線。⑶

部分直線在窗口內(nèi)，部分直線在窗口外。此時(shí)，需要求出直線與窗框的交點(diǎn)，并將窗口外的直線部分剪裁掉，顯示窗口內(nèi)的直線部分。

直線剪裁算法有兩個(gè)主要步