計(jì)算機(jī)圖形學(xué)2425的知識(shí)

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

點(diǎn)陣式字符將字符形狀表示為一個(gè)矩形點(diǎn)陣，由點(diǎn)陣中點(diǎn)的不同值表達(dá)字符的形狀。

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

1矩陣中的每個(gè)元素都是一位二進(jìn)制位。（1：字符顏色；0：背景顏色）算法如下：Writechar(x0,y0,value)Intx0,y0,value;{for(j=0;j<=ymax;j++)for(i=0;i<=xmax;i++)if(mask(i,j)<>0)set_pixel(x0+i;y0+j;value);elseset_pixel(x0+i;y0+j;background);}22.4字符的生成2.4.2矢量式字符

矢量式字符將字符表達(dá)為點(diǎn)坐標(biāo)的序列，相鄰兩點(diǎn)表示一條矢量，字符的形狀便由矢量序列刻畫(huà)。圖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”32.4字符的生成2.4.3

方向編碼式字符

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

圖2.14方向編碼式字符的實(shí)例42.4字符的生成2.4.4輪廓字形技術(shù)

直接使用點(diǎn)陣式字符方法將耗費(fèi)巨大的存儲(chǔ)空間。壓縮方法有多種，最簡(jiǎn)單的有黑白段壓縮法。另一種方法是部件壓縮法。三是輪廓字形法，這種方法壓縮比大，且能保證字符質(zhì)量，是當(dāng)今國(guó)際上最流行的一種方法。

輪廓字形法采用直線、或者二次Bezier曲線、三次Bezier曲線的集合來(lái)描述一個(gè)字符的輪廓線。輪廓線構(gòu)成一個(gè)或若干個(gè)封閉的平面區(qū)域。輪廓線定義和一些指示橫寬、豎寬、基點(diǎn)、基線等的控制信息，就構(gòu)成了字符的壓縮數(shù)據(jù)。52.5圖形求交

在計(jì)算機(jī)圖形學(xué)中常常會(huì)遇到求交計(jì)算。求交運(yùn)算是比較復(fù)雜的，為了減少計(jì)算量，在進(jìn)行真正的求交計(jì)算之前，往往先用凸包等輔助結(jié)構(gòu)進(jìn)行粗略地比較，排除那些顯然不相交的情形。容差求交問(wèn)題可以分為兩類(lèi)：

求交點(diǎn)求交線

62.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ì)三維空間中的直線段來(lái)說(shuō)，上述方程組實(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。

72.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。故有類(lèi)似地有82.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

2.直線段與平面的交點(diǎn)圖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+tE等式兩邊點(diǎn)乘(BC)，得

(BC)·(A+uB+wC)=(BC)·(D+tE)由于BC既垂直于B，又垂直于C，故有(BC)·A=(BC)·(D+tE)92.5圖形求交2.5.1求交點(diǎn)算法（續(xù)）

可解出類(lèi)似求得102.5圖形求交

2.5.2求交線算法

⒈平面與平面的交線

當(dāng)兩個(gè)一般的多邊形相交時(shí)，可能有多段交線?？梢园褍蓚€(gè)多邊形分別記為A和B，用如下的算法求出他們的交線：把A的所有邊與B相交，求出所有有效交點(diǎn)；把B的所有邊與A相交，求出所有有效交點(diǎn)；把所有交點(diǎn)先按y，再按x的大小進(jìn)行排序；把每對(duì)交點(diǎn)所形成線段的中點(diǎn)與A和B進(jìn)行包含性檢測(cè)，若該中點(diǎn)既在A中又在B中，則這對(duì)交點(diǎn)定義了一條交線段。

112.5圖形求交2.5.3包含判定算法

判斷點(diǎn)與線段的包含關(guān)系，也就是判斷點(diǎn)與線的最短距離是否位于容差范圍內(nèi)。⒈點(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)在線段(或其延長(zhǎng)線)上，這時(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)。122.5圖形求交2.5.3包含判定算法（續(xù)）2.點(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)法。

132.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叉積判斷法142.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)所示。圖2.17夾角之和檢驗(yàn)法

152.5圖形求交⑶交點(diǎn)計(jì)數(shù)檢驗(yàn)法當(dāng)多邊形是凹多邊形，甚至還帶