計(jì)算機(jī)圖形學(xué) 課件 第2章 圖形處理中的幾何問題

第2章圖形處理中的幾何問題2.1圖形坐標(biāo)系2.2幾何元素的定義及特點(diǎn)2.3平面圖形的幾何性質(zhì)2.4幾何元素之間的位置判斷2.5幾何元素之間的求交計(jì)算2.6多邊形及其凸凹性2.7多邊形的分解與網(wǎng)格劃分

2.1圖形坐標(biāo)系

對(duì)圖形對(duì)象的描述，圖形的處理及輸入、輸出，都是在一定的坐標(biāo)系中進(jìn)行的。目前，對(duì)世界坐標(biāo)系、用戶坐標(biāo)系、局部坐標(biāo)系還沒有統(tǒng)一的定義，各種文獻(xiàn)及圖形軟件中的說法不一。這里從圖形系統(tǒng)的角度提出世界坐標(biāo)系、局部坐標(biāo)系、觀察坐標(biāo)系、設(shè)備坐標(biāo)系、規(guī)范化設(shè)備坐標(biāo)系等5種坐標(biāo)系。在標(biāo)準(zhǔn)圖形系統(tǒng)中，主要坐標(biāo)系使用的邏輯關(guān)系如圖2.1所示。

圖2.1坐標(biāo)系使用的邏輯關(guān)系

在三維坐標(biāo)系統(tǒng)中，有右手坐標(biāo)系和左手坐標(biāo)系之分，通常采用右手坐標(biāo)系。左手坐標(biāo)系和右手坐標(biāo)系的判斷方法有旋向法和三指法。伸開右手，若坐標(biāo)系的手指間關(guān)系符合圖2.2所示的關(guān)系則稱為右手坐標(biāo)系，否則為左手坐標(biāo)系。

圖2.2右手坐標(biāo)系的判斷方法

2.1.1世界坐標(biāo)系

世界坐標(biāo)系是用戶為繪圖而建立的初始直角坐標(biāo)系，

為右手坐標(biāo)系，可以是二維或三維的坐標(biāo)系。世界坐標(biāo)系的坐標(biāo)軸方位是固定的，在顯示屏幕上，一般x軸正向朝右，y軸正向朝上，z軸正向按右手定則垂直于屏幕顯示平面朝外，坐標(biāo)系的原點(diǎn)由定義的作圖范圍來確定，坐標(biāo)的取值范圍可以是計(jì)算機(jī)能夠處理的實(shí)數(shù)范圍，可根據(jù)需要設(shè)置。

2.1.2局部坐標(biāo)系

局部坐標(biāo)系是用戶在世界坐標(biāo)系或當(dāng)前的坐標(biāo)系中定

義的直角坐標(biāo)系，為右手坐標(biāo)系。局部坐標(biāo)系的坐標(biāo)原點(diǎn)、坐標(biāo)軸的方位是任意的。在某些圖形系統(tǒng)中，把局部坐標(biāo)系稱為用戶坐標(biāo)系。設(shè)立局部坐標(biāo)系是為了便于作圖。例如，在三維繪圖中，利用局部坐標(biāo)系可以把較為復(fù)雜的三維作圖問題轉(zhuǎn)化為二維作圖問題。圖2.3為局部坐標(biāo)系的應(yīng)用。

圖2.3局部坐標(biāo)系的應(yīng)用

2.1.3觀察坐標(biāo)系

觀察坐標(biāo)系是以視點(diǎn)為坐標(biāo)原點(diǎn)的三維左手(或右手)直角坐標(biāo)系，其中z軸方向?yàn)橐朁c(diǎn)與世界坐標(biāo)系原點(diǎn)(默認(rèn)情況)或模型上點(diǎn)的連線方向，xy平面(觀察平面，即投影平面)與z軸垂直，如圖2.4所示。

觀察坐標(biāo)系取為左手系的原因在于:當(dāng)把觀察平面作為屏幕時(shí)，z軸正方向朝向顯示器里的方向符合我們的視覺習(xí)慣，越向里表示離我們?cè)竭h(yuǎn)，z值也就越大。

圖2.4觀察坐標(biāo)系與世界坐標(biāo)系

2.1.4設(shè)備坐標(biāo)系

與一個(gè)圖形設(shè)備(輸入設(shè)備或輸出設(shè)備)相關(guān)聯(lián)的直角坐標(biāo)系稱為設(shè)備坐標(biāo)系。設(shè)備坐標(biāo)系可以是二維坐標(biāo)系(如二維掃描儀、屏幕、繪圖機(jī)、二維打印機(jī)等)，也可以是三維坐標(biāo)系(如三維掃描儀、三維打印機(jī))。圖形的輸出在設(shè)備坐標(biāo)系下進(jìn)行。設(shè)備坐標(biāo)系的坐標(biāo)取值范圍與設(shè)備的有效幅面和精度有關(guān)，為某個(gè)整數(shù)區(qū)間。對(duì)點(diǎn)陣圖形顯示器和無筆繪圖機(jī)而言，坐標(biāo)單位是像素(也叫光柵單位)；對(duì)筆式繪圖機(jī)而言，其坐標(biāo)單位是步距(也叫脈沖當(dāng)量)。

點(diǎn)陣圖形顯示器的設(shè)備坐標(biāo)系與屏幕分辨率有關(guān)。假定顯示器的分辨率為1024×768，則該顯示器的設(shè)備坐標(biāo)系為:x∈［0，1023］，y∈［0，767］，x、y為整數(shù)(代表像素位置)。坐標(biāo)原點(diǎn)默認(rèn)情況是在屏幕左上角，如圖2.5(a)所示；坐標(biāo)原點(diǎn)也可設(shè)置在屏幕左下角，如圖2.5(b)所示。

圖2.5屏幕坐標(biāo)系

2.1.5規(guī)范化設(shè)備坐標(biāo)系

坐標(biāo)取值范圍為0到1.0的坐標(biāo)系稱為規(guī)范化設(shè)備坐標(biāo)系(。規(guī)范化設(shè)備坐標(biāo)系為:x∈［0.0，1.0］，y∈［0.0，1.0］，x、y為實(shí)數(shù)。用戶的圖形處理數(shù)據(jù)(如對(duì)模型投影并經(jīng)窗口裁剪得到的數(shù)據(jù))經(jīng)歸一化轉(zhuǎn)換即得規(guī)范化設(shè)備坐標(biāo)系中的坐標(biāo)值。

另外，在一些圖形系統(tǒng)中還使用圓柱面坐標(biāo)系(ρ-φ-z，ρ、φ為空間點(diǎn)在xOy平面上投影的極坐標(biāo)，ρ為極徑，φ為極角，z為空間點(diǎn)到xOy平面的距離)和球面坐標(biāo)系(r-φ-θ，r為空間點(diǎn)到原點(diǎn)的距離，φ為從x軸正向起度量的經(jīng)度角(0°~360°)，θ為從z軸正向起度量的緯度角(0°~180°))。在某些工程應(yīng)用中，如三角形區(qū)域內(nèi)物理量的插值計(jì)算，還可使用面積坐標(biāo)等。

2.2幾何元素的定義及特點(diǎn)

1.點(diǎn)點(diǎn)是圖形處理中最基本的元素，分為端點(diǎn)、交點(diǎn)、切點(diǎn)等。在通常的直角坐標(biāo)系下，二維空間中的點(diǎn)用二元組｛x，y｝或｛x(t)，y(t)｝表示；三維空間中的點(diǎn)用三元組｛x，y，z｝或｛x(t)，y(t)，z(t)｝表示。而在齊次坐標(biāo)系下，n維空間中的點(diǎn)用n+1維坐標(biāo)表示。

在自由曲線和曲面的描述中，常用以下三種類型的點(diǎn)：

(1)控制點(diǎn):用來確定曲線和曲面的位置與形狀，而相應(yīng)的曲線和曲面不一定經(jīng)過的點(diǎn)。控制點(diǎn)用于構(gòu)造逼近曲線、逼近曲面。

(2)型值點(diǎn):用來確定曲線和曲面的位置與形狀，而相應(yīng)的曲線和曲面一定經(jīng)過的點(diǎn)。型值點(diǎn)用于構(gòu)造插值曲線、插值曲面。

(3)插值點(diǎn):為提高曲線和曲面的輸出精度，在型值點(diǎn)之間插入的一系列點(diǎn)。

2.邊(線)

邊分為直線邊和曲線邊。直線邊由其端點(diǎn)(起點(diǎn)和終點(diǎn))定界；曲線邊由一系列型值點(diǎn)或控制點(diǎn)表示，也可用顯式、隱式方程表示。

3.環(huán)

環(huán)是由有序的有向邊(直線段或曲線段)組成的封閉邊界。環(huán)有內(nèi)、外之分，確定面的最大外邊界的環(huán)稱為外環(huán)，其邊(或頂點(diǎn))按逆時(shí)針方向排序；而把確定面中內(nèi)孔或凸臺(tái)邊界的環(huán)稱為內(nèi)環(huán)，其邊(或頂點(diǎn))按順時(shí)針方向排序?；谶@種定義，在面上沿一個(gè)環(huán)前進(jìn)，其左側(cè)總是面內(nèi)，右側(cè)總是面外。

4.面

面是由一個(gè)外環(huán)和若干個(gè)(包括0個(gè))內(nèi)環(huán)圍成的區(qū)域。一個(gè)面可以無內(nèi)環(huán)，但必須有一個(gè)且只有一個(gè)外環(huán)。形體中的面有方向性，一般用其外法線矢量方向作為該面的正向。若一個(gè)面的外法線矢量向外，此面為正向面；反之，為反向面。區(qū)分正向面和反向面在實(shí)體造型中的新面生成、真實(shí)感圖形顯示等方面都很重要。

5.體

體是由封閉表面圍成的空間，其邊界是有限面的并集。為了保證幾何造型的可靠性和可加工性，要求形體上任意一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)是一個(gè)等價(jià)的封閉圓，即圍繞該點(diǎn)的形體鄰域在二維空間中可以構(gòu)成一個(gè)單連通域。我們把滿足這個(gè)定義的形體稱為正則形體(或稱為流形物體)。含懸掛邊、懸掛面、懸掛體(以點(diǎn)、邊接觸的體)的形體均不是正則形體。

6.形體定義的層次結(jié)構(gòu)

形體在計(jì)算機(jī)中可按上述幾何元素分五個(gè)層次表示，如圖2.6所示。圖2.6形體的層次表示

2.3平面圖形的幾何性質(zhì)

1.平面的外法線矢量計(jì)算設(shè)形體表面外環(huán)上三個(gè)相鄰頂點(diǎn)依次為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，則該平面的外法線矢量(按右手定則定方向)為

2.三角形的面積、質(zhì)心和質(zhì)量因子的計(jì)算

設(shè)三角形的三個(gè)頂點(diǎn)依次為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，則有三角形的面積：

其中，ｐ為三角形周長的一半，a、b、c為三邊的邊長。

當(dāng)α=0時(shí)，表示一條直線；當(dāng)α=1時(shí)，表示正三角形，這時(shí)質(zhì)量最好。圖2.7分別為不同三角形的質(zhì)量因子α的值。在三角形質(zhì)量判斷中，α的取值由經(jīng)驗(yàn)數(shù)據(jù)決定，一般它的推薦值為α>0.1。

圖2.7不同三角形的質(zhì)量因子α的值

3.平面凸四邊形的面積、質(zhì)心和質(zhì)量因子的計(jì)算

2.4幾何元素之間的位置判斷

1.點(diǎn)與點(diǎn)的位置判斷點(diǎn)與點(diǎn)的位置關(guān)系主要用于兩點(diǎn)是否重合、兩三角形是否有公共邊的判斷等方面。設(shè)空間兩點(diǎn)P1(x1，y1，z1)、P2(x2，y2，z2)，則這兩點(diǎn)之間的距離1為當(dāng)1＜ε(ε為誤差精度)時(shí)，可判定P1、P2兩點(diǎn)是同一點(diǎn)。

2.點(diǎn)與直線段的位置判斷

點(diǎn)與直線之間的位置關(guān)系用于點(diǎn)是否在直線上、三點(diǎn)是否共線以及三點(diǎn)是否能構(gòu)成三角形的判斷等方面。

設(shè)點(diǎn)為P(x，y，z)，直線段端點(diǎn)為P1(x1，y1，z1)、P2(x2，y2，z2)，則點(diǎn)P到線段P1P2的距離為

3.點(diǎn)與平面的位置判斷

點(diǎn)與平面之間的位置關(guān)系用于四點(diǎn)共面、兩相鄰三角形是否可合并構(gòu)成平面四邊形的判斷等方面。

已知平面上不共線的三點(diǎn)為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，空間點(diǎn)為P(x，y，z)，設(shè)ｑ為點(diǎn)到平面的代數(shù)距離，則有

若｜ｑ｜≤ε(ε為誤差精度)，則點(diǎn)P在不共線的三點(diǎn)P1、P2、P3所確定的平面上。

4.點(diǎn)在多邊形內(nèi)部的判斷

判斷平面上一個(gè)點(diǎn)是否包含在同平面的一個(gè)多邊形內(nèi)有多種算法，經(jīng)典方法有叉積判斷法、夾角之和檢驗(yàn)法和交點(diǎn)計(jì)數(shù)檢驗(yàn)法。

1)叉積判斷法

叉積判斷法適用于空間平面上一點(diǎn)在同一平面內(nèi)的一個(gè)凸多邊形內(nèi)的判斷。如圖2.8所示，設(shè)P0為平面上一點(diǎn)，P1P2P3P4為凸多邊形。由于空間點(diǎn)可用位置矢徑表示，令Vi=Pi-P0(i=1，2，…，n)，Vn+1=V1，一般情況下，點(diǎn)P0在多邊形內(nèi)的充要條件是叉積Vi×Vi+1

(i=1，2，…，n)的符號(hào)相同。特殊地，當(dāng)Vi×Vi+1=0(點(diǎn)P0在多邊形的邊上或邊的延長線上)時(shí)，認(rèn)為點(diǎn)在多邊形外。

圖2.8叉積判斷法

2)夾角之和檢驗(yàn)法

如圖2.9所示，假設(shè)平面上有點(diǎn)P0和多邊形P1P2P3

P4P5，將點(diǎn)P0分別與Pi相連，構(gòu)成向量Vi=Pi-P0(i=1，2，…，n)，Vn+1=V1。假設(shè)∠Pi

P0Pi+1=αi(Pn+1=P

1)，則它可通過下列公式計(jì)算：

αi的正負(fù)號(hào)由Vi×Vi+1的正負(fù)決定。

圖2.9夾角之和檢驗(yàn)法

3)交點(diǎn)計(jì)數(shù)檢驗(yàn)法

交點(diǎn)計(jì)數(shù)檢驗(yàn)法適用較廣，特別適用凹多邊形及帶孔多邊形情況下的點(diǎn)是否在多邊形內(nèi)的判斷。判斷的基本思想是:從被判斷點(diǎn)(x0，y0)向右作一射線至無窮遠(yuǎn)，即射線方程為

求射線與多邊形相交時(shí)的交點(diǎn)個(gè)數(shù)。

如果交點(diǎn)個(gè)數(shù)為奇數(shù)，則點(diǎn)在多邊形之內(nèi)；如果交點(diǎn)

個(gè)數(shù)為偶數(shù)(含0)或特殊情況時(shí)點(diǎn)在多邊形邊上，則點(diǎn)在多邊形之外。如圖2.10(a)所示，射線a、c、d與多邊形相交，其交點(diǎn)個(gè)數(shù)分別為2、2、4，為偶數(shù)，可以直接判斷A、C、D三點(diǎn)均在多邊形之外；而射線b、e分別交多邊形的交點(diǎn)數(shù)為3和1，所以也可直接判斷B、E兩點(diǎn)均在多邊形之內(nèi)。

但當(dāng)圖2.10(b)中的射線f、g、h、i、j均通過多邊形的頂點(diǎn)、圖2.10(a)中射線ｋ與邊重合時(shí)，交點(diǎn)計(jì)數(shù)應(yīng)特殊處理。如射線

g與多邊形的邊6、邊7交于一頂點(diǎn)，這時(shí)如果將交點(diǎn)計(jì)數(shù)為2，則會(huì)誤判斷點(diǎn)G在多邊形之外；如果將交點(diǎn)計(jì)數(shù)為1，則又會(huì)誤判斷點(diǎn)F在多邊形之內(nèi)(射線f與邊7、邊8交于一頂點(diǎn))。

圖2.10交點(diǎn)計(jì)數(shù)檢驗(yàn)法

參見圖2.11，具體計(jì)數(shù)時(shí)，當(dāng)兩條邊的另兩個(gè)端點(diǎn)的y值均大于y0，即兩邊均處于射線上方時(shí)，計(jì)數(shù)為2，如圖2.11(a)所示；當(dāng)兩條邊另兩端點(diǎn)的y值均小于y0，即兩條邊均處在射線下方時(shí)，交點(diǎn)計(jì)數(shù)為0，如圖2.11(b)所示；當(dāng)兩條邊的兩端點(diǎn)分布在射線兩側(cè)時(shí)，交點(diǎn)計(jì)數(shù)為1，如圖2.11(c)所示。當(dāng)邊與射線重合時(shí)，可將邊視作壓縮為一點(diǎn)，按圖2.11(d)、(e)、(f)類似處理。

圖2.11交點(diǎn)計(jì)數(shù)方法

5.點(diǎn)在多面體內(nèi)的判斷

1)點(diǎn)在凸多面體內(nèi)的判斷

設(shè)點(diǎn)P為空間點(diǎn)，Ni是凸多面體每個(gè)面的外法矢量，Pi是面上一點(diǎn)(常取面的頂點(diǎn))，若滿足Ni·(P-Pi)＜0，則點(diǎn)P在多面體內(nèi)。

2)點(diǎn)在一般多面體內(nèi)的判斷

點(diǎn)在一般多面體內(nèi)的判斷類似于點(diǎn)在多邊形內(nèi)部判斷的交點(diǎn)計(jì)數(shù)法。

2.5幾何元素之間的求交計(jì)算

幾何元素之間的求交計(jì)算主要有兩直線段求交、直線段與平面求交、平面與平面求交等，其應(yīng)用十分廣泛，除用于點(diǎn)在多邊形及多面體內(nèi)的包含性判斷外，還用于區(qū)域填充、二維或三維圖形裁剪、二維或三維圖形布爾運(yùn)算、投影求取、多邊形或多面體分解、對(duì)稱計(jì)算、幾何量或物理量插值計(jì)算、消隱計(jì)算、光線跟蹤計(jì)算等。

1.空間平面上兩直線段的求交

兩條線段的求交分兩步，第一步為快速排斥判斷及跨立判斷以確定兩線段是否相交；第二步為對(duì)相交線段求交點(diǎn)。設(shè)線段P1P2、Q1Q2在同一平面上，兩線段求交算法的步驟如下。

1)快速排斥判斷

設(shè)以線段P1P2為對(duì)角線的軸向矩形(矩形邊與坐標(biāo)軸平行)為R、以線段Q1Q2為對(duì)角線的軸向矩形為T，如果R和T分離不相交，顯然兩線段不會(huì)相交，則求交結(jié)束；否則(R和T相交或內(nèi)含情況，這時(shí)線段可能相交，也可能不相交)進(jìn)行跨立判斷。

2)跨立判斷

如果兩線段相交，則兩線段必然相互跨立對(duì)方(一條線段的兩個(gè)端點(diǎn)在另一條線段的兩側(cè))，如圖2.12所示。

圖2.12跨立驗(yàn)證

3)求取交點(diǎn)

線段P1P2、Q1Q2的方程用矢量形式分別表示為

2.直線段與平面的求交

1)矢量求解方法

考慮直線段與無界平面的求交問題，如圖2.13所示。

給定直線段的兩個(gè)端點(diǎn)，則直線段方程可表示為

給定平面上三個(gè)點(diǎn)，則平面方程可表示為

圖2.13直線段與平面的求交

2)代數(shù)求解方法

其中：

2.14直線與空間平面的交點(diǎn)

3.平面與平面的求交

平面是最常用的一種面。在進(jìn)行包含平面的實(shí)體之間的布爾運(yùn)算、進(jìn)行實(shí)體的剖切運(yùn)算(以便得到實(shí)體的剖面圖)或利用掃描線進(jìn)行光照計(jì)算及消隱時(shí)，都涉及平面與平面的求交問題。

1)基于線面求交的面面求交算法

設(shè)兩個(gè)一般多邊形分別記為A和B，面面求交算法包括下面四步：

(1)將A的所有邊分別與B求交(利用直線段與平面求交，直線段落在平面上時(shí)不計(jì)交點(diǎn))，求出所有有效交點(diǎn)(既在多邊形A的邊上(檢查參數(shù)范圍判斷)，又在多邊形B內(nèi)(利用點(diǎn)在多邊形內(nèi)的判斷)的點(diǎn))；

(2)將B的所有邊分別與A求交，求出所有有效交點(diǎn)(既在多邊形B的邊上，又在多邊形A內(nèi)的點(diǎn))；

(3)將所有交點(diǎn)依次按x、y、z的大小進(jìn)行排序，即先按x坐標(biāo)排序，然后對(duì)x坐標(biāo)相同的交點(diǎn)再按y坐標(biāo)排序，最后對(duì)x、y相同的交點(diǎn)按z坐標(biāo)排序；

(4)將每對(duì)交點(diǎn)(如交點(diǎn)1、交點(diǎn)2為一對(duì)，交點(diǎn)3、交點(diǎn)4為一對(duì)，依次類推)的中點(diǎn)與A和B進(jìn)行包含性檢測(cè)(利用點(diǎn)在多邊形內(nèi)的判斷)，若該中點(diǎn)既在A中又在B中，則該對(duì)交點(diǎn)為A和B的一條交線段。

2)基于線線求交的面面求交算法———課程思政案例

基于線線求交的面面求交算法是編者已授權(quán)的國家發(fā)明專利。此案例的創(chuàng)新思路在于抓住了平面與平面的理論交線這個(gè)兩個(gè)平面之間的橋梁，進(jìn)而可以將線面求交轉(zhuǎn)化為線線求交并利用交點(diǎn)在理論交線的位置參數(shù)(直線參數(shù)方程中的參數(shù))對(duì)交點(diǎn)排一次序即可。此案例旨在培養(yǎng)創(chuàng)新思維能力和創(chuàng)新精神。

設(shè)兩個(gè)一般多邊形分別記為A和B，參見圖2.15、圖2.16，算法步驟如下：

(1)求取A和B的理論交線，并取足夠長度形成理論交線段；

(2)分別在A和B上進(jìn)行理論交線段與多邊形的邊線段求交(利用直線段與直線段求交)，線段重合時(shí)不計(jì)交點(diǎn)，以避免在進(jìn)行三維實(shí)體布爾運(yùn)算時(shí)出現(xiàn)重合或懸掛的線、面；

(3)分別對(duì)A和B沿理論交線對(duì)交點(diǎn)按位置參數(shù)從小到大排序并形成交點(diǎn)組(如圖2.15所示，A的交點(diǎn)11、9為一組，交點(diǎn)10、12為一組；B的交點(diǎn)9′、11′為一組，交點(diǎn)12′、10′為一組)，剔除端點(diǎn)重合的交點(diǎn)組，以避免在三維實(shí)體布爾運(yùn)算時(shí)出現(xiàn)孤立的點(diǎn)或懸掛的線；

(4)對(duì)A和B的交點(diǎn)組按位置參數(shù)求交集得到可能交線段(如圖2.15所示的線段9′-9、10-10′，圖2.16所示的線段1-2、3-4、5-6)；

(5)對(duì)可能交線段的中點(diǎn)進(jìn)行A和B的包含性檢測(cè)以確定最終交線段，這一步主要適用于有內(nèi)環(huán)且內(nèi)環(huán)邊在兩個(gè)平面理論交線上時(shí)的處理，如圖2.16所示。

按此算法，圖2.15的最終交線段為9′-9、10-10′，圖2.16所示最終交線段為1-2、5-6。圖2.15面面求交示例

圖2.16面面求交奇異情況

4.矢量表示點(diǎn)批判學(xué)習(xí)案例

比較有影響的國外專著《計(jì)算機(jī)圖形學(xué)幾何工具算法詳解》的9.2.1節(jié)講平面方程時(shí)，平面上的點(diǎn)用P=dn表示，其中n為平面法線矢量，d為常數(shù)，即點(diǎn)用矢量表示。11.5.1節(jié)講兩個(gè)平面求交時(shí)，直線上的點(diǎn)用P=an1+bn2表示，其中n1、n2分別為兩個(gè)平面的法線矢量，a、b為常數(shù)，an1+bn2的結(jié)果仍為矢量，即點(diǎn)也用矢量表示。

2.6多邊形及其凸凹性2.6.1基本概念1.簡(jiǎn)單多邊形設(shè)Vi(i=1，2，3，…，n)是給定封閉多邊形的n個(gè)頂點(diǎn)。若同時(shí)滿足以下條件：(1)對(duì)任意的i≠j(i，j=1，2，3，…，n)，存在Vi≠Vj，即所有頂點(diǎn)均不相同；(2)任何頂點(diǎn)都只屬于它所在的邊；(3)任何兩條非相鄰邊都不相交。則稱該多邊形為簡(jiǎn)單多邊形。

圖2.17為簡(jiǎn)單多邊形，圖(a)是一個(gè)簡(jiǎn)單單連通多邊形(不帶內(nèi)環(huán))，圖(b)是一個(gè)簡(jiǎn)單多連通多邊形(帶內(nèi)環(huán))。圖2.17簡(jiǎn)單多邊形

圖2.18不是簡(jiǎn)單多邊形，其中(a)不滿足第(1)條，(b)不滿足第(2)、(3)條。圖2.18非簡(jiǎn)單多邊形

2.簡(jiǎn)單多邊形頂點(diǎn)凸凹性的定義、凸角與凹角、凸多邊形與凹多邊形

設(shè)V1，…，Vn是一個(gè)簡(jiǎn)單多邊形。對(duì)于任一頂點(diǎn)Vi(i=1，2，3，…，n)，若線段Vi

-

1Vi(令V0=Vn)與線段ViVi+1(令Vn+1=V1)所形成的內(nèi)角(由該多邊形所圍成有界區(qū)域內(nèi)兩邊所夾的角)是一個(gè)小于180°的角，則稱Vi是凸頂點(diǎn)；若內(nèi)角是一個(gè)大于180°的角，則稱Vi是凹頂點(diǎn)；若內(nèi)角是一個(gè)等于180°的角，則稱Vi是中性點(diǎn)，在圖形處理時(shí)可根據(jù)需要將其看作凸頂點(diǎn)或者凹頂點(diǎn)。由此定義可知，對(duì)任意一個(gè)簡(jiǎn)單多邊形，其每個(gè)頂點(diǎn)或是凸的，或是凹的。凸頂點(diǎn)對(duì)應(yīng)的內(nèi)角稱為凸角，凹頂點(diǎn)對(duì)應(yīng)的內(nèi)角稱為凹角。

對(duì)簡(jiǎn)單單連通多邊形而言，所有頂點(diǎn)都為凸頂點(diǎn)的多邊形稱為凸多邊形，至少有一個(gè)頂點(diǎn)為凹頂點(diǎn)的多邊形稱為凹多邊形。

3.多邊形的方向、有向邊

多邊形的方向有逆時(shí)針方向和順時(shí)針方向之分。對(duì)簡(jiǎn)單單連通多邊形而言，沿觀察方向看去，若觀察者按頂點(diǎn)序列V1V2…VnVn+1繞多邊形一周時(shí)，該多邊形所圍的有界區(qū)域總在左邊，則稱該多邊形為逆時(shí)針方向，如圖2.19(a)所示；否則，稱其為順時(shí)針方向，如圖2.19(b)所示。

圖2.19多邊形的方向

4.頂點(diǎn)的叉積

2.6.2多邊形凸凹性的判斷

1.多邊形方向的判斷

多邊形方向的判斷方法為極值頂點(diǎn)法。多邊形頂點(diǎn)中坐標(biāo)值為xmin或xmax或ymin或ymax的頂點(diǎn)稱為極值頂點(diǎn)，極值頂點(diǎn)必為凸頂點(diǎn)。

極值頂點(diǎn)法如下：

(1)找出多邊形的某一極值頂點(diǎn)。

(2)求該極值頂點(diǎn)的叉積。

(3)若叉積值nz>0，則多邊形的方向?yàn)槟鏁r(shí)針方向；若叉積值nz＜0，則多邊形的方向?yàn)轫槙r(shí)針方向。

2.多邊形頂點(diǎn)凸凹性的判斷

假定多邊形V1V2…Vn的方向?yàn)槟鏁r(shí)針方向，這是常見的情況。多邊形頂點(diǎn)凸凹性的判斷方法有頂點(diǎn)叉積法、平移旋轉(zhuǎn)法等。這里介紹較為簡(jiǎn)單的頂點(diǎn)叉積法。

對(duì)于逆時(shí)針方向的多邊形，任一頂點(diǎn)Vi凸凹性判斷的頂點(diǎn)叉積法如下：

(1)計(jì)算頂點(diǎn)Vi的叉積。

(2)若叉積值nz>0，則該頂點(diǎn)為凸頂點(diǎn)；若叉積值nz＜0，則該頂點(diǎn)為凹頂點(diǎn)；若叉積值nz=0，則該頂點(diǎn)為中性點(diǎn)，可根據(jù)需要將其看作凸頂點(diǎn)或者凹頂點(diǎn)

如圖2.20所示，多邊形V1V2V3V4V5V6為逆時(shí)針走向，圖中箭頭代表各個(gè)頂點(diǎn)的叉積方向。箭頭朝上表示叉積值為正，可知頂點(diǎn)V1、V2、V3、V4、V6是凸頂點(diǎn)；箭頭朝下表示叉積值為負(fù)，可知頂點(diǎn)V5是凹頂點(diǎn)。

圖2.20逆時(shí)針方向多邊形的叉積示意圖

3.多邊形凸凹性的判斷

經(jīng)過頂點(diǎn)凸凹性判斷后，若多邊形所有頂點(diǎn)都為凸頂點(diǎn)，則該多邊形是凸多邊形；否則為凹多邊形。

經(jīng)上述判斷，圖2.20所示的多邊形為凹多邊形。

2.7多邊形的分解與網(wǎng)格劃分

2.7.1凸多邊形的三角分解參見圖2.21，凸多邊形三角分解的算法如下：(1)找出多邊形最長對(duì)角線的兩個(gè)端點(diǎn)，目的是得到質(zhì)量較好的三角形。(2)將每個(gè)端點(diǎn)與它們相鄰頂點(diǎn)連線形成兩個(gè)三角形并輸出。(3)對(duì)剩余部分按(1)、(2)遞歸剖分，直至剖分完畢或最后剩余一個(gè)三角形輸出。

圖2.21凸多邊形的三角分解過程

2.7.2凹多邊形的分解

參見圖2.22，凹多邊形分解的算法如下：

圖2.22凹多邊形的分解

(1)找出多邊形中的第一個(gè)凹頂點(diǎn)(如C點(diǎn))，并確定其前一個(gè)頂點(diǎn)(如B點(diǎn))和后一個(gè)頂點(diǎn)(如D點(diǎn))。

(2)根據(jù)頂點(diǎn)順序，往后另找一點(diǎn)(如E點(diǎn))，判斷此點(diǎn)與凹頂點(diǎn)的連線是否與多邊形的各邊相交，如果相交，則繼續(xù)找下一點(diǎn)，直到找到不相交的點(diǎn)為止。

(3)計(jì)算并判斷此點(diǎn)(如E點(diǎn))與凹頂點(diǎn)連線是否可將本凹頂點(diǎn)(如C點(diǎn))對(duì)應(yīng)的凹角(如∠BCD)劃分為兩個(gè)凸角(此例即是判斷劃分的兩個(gè)內(nèi)角∠BCE和∠ECD是否構(gòu)成凸頂點(diǎn)，可通過求頂點(diǎn)的叉積進(jìn)行判斷)；如果可以，將凹角劃分，并將劃分后的多邊形分別輸出；如果不行繼續(xù)找下一點(diǎn)，直到滿足條件為止(此例F點(diǎn)滿足將凹角劃分為兩個(gè)凸角的要求，輸出兩個(gè)多邊形ABCF和DEFC)。

(4)判斷輸出的兩個(gè)多邊形的類型，若為三角形或凸多邊形，則不需再劃分；否則執(zhí)行步驟(1)～(3)。

(5)對(duì)劃分出的凸多邊形調(diào)用凸多邊形分解算法，將這些凸多邊形分解為三角形輸出。

此算法簡(jiǎn)單，但缺點(diǎn)是分解結(jié)果與多邊形頂點(diǎn)的排序有關(guān)，分解不具有唯一性。

2.7.3帶內(nèi)環(huán)多邊形的分解與基于單調(diào)鏈的凸分解

1.非自交多邊形

在有向多邊形中，非相鄰邊相交的多邊形稱為自交多邊形，如圖2.23所示。非相鄰邊不相交但可以重疊的多邊形稱為非自交多邊形，如圖2.24所示。非自交多邊形包括簡(jiǎn)單多邊形(圖2.24(a))和有重疊邊但不自相交的多邊形(圖2.24(b))。在圖形處理中，為使帶內(nèi)環(huán)多邊形拓?fù)涞葍r(jià)于不帶內(nèi)環(huán)的多邊形，從而使多邊形分解簡(jiǎn)單、統(tǒng)一，就需要在形式上消除內(nèi)環(huán)，其方法就是在外環(huán)與內(nèi)環(huán)之間、內(nèi)環(huán)與內(nèi)環(huán)之間引入重疊邊或“橋邊”，如圖2.23、圖2.24、圖2.25所示。

圖2.23自交多邊形

圖2.24非自交多邊形NIP

2.基于NIP多邊形的三角分解

該方法通過在外環(huán)與內(nèi)環(huán)之間、內(nèi)環(huán)與內(nèi)環(huán)之間引入“橋邊”將帶內(nèi)環(huán)多邊形轉(zhuǎn)換為NIP多邊形，然后對(duì)NIP多邊形進(jìn)行三角分解。圖2.25是帶兩個(gè)內(nèi)環(huán)的多邊形轉(zhuǎn)換為一個(gè)NIP多邊形的情況。

圖2.25帶內(nèi)環(huán)多邊形的NIP轉(zhuǎn)換

圖2.26NIP三角分解過程

圖2.27帶內(nèi)環(huán)多邊形的NIP三角分解

3.基于單調(diào)鏈的凸分解

基于單調(diào)鏈的凸分解的目標(biāo)是將帶內(nèi)環(huán)多邊形分解為凸多邊形。

1)單調(diào)鏈、尖點(diǎn)的概念

單調(diào)鏈的定義:如果一條鏈(開口多邊形)上的點(diǎn)在直線L上的正交投影是有序的，即投影點(diǎn)的坐標(biāo)值依次增大(包括相等)，或依次減小(包括相等)，則稱該鏈相對(duì)于L單調(diào)，如圖2.28所示。點(diǎn)在直線L上的正交投影是否有序的判斷方法為:沿直線L建立局部坐標(biāo)系并取L為x軸正向，將鏈頂點(diǎn)坐標(biāo)轉(zhuǎn)換為局部坐標(biāo)，比較鏈頂點(diǎn)的x坐標(biāo)看其是否依次增大或依次減小。

圖2.28單調(diào)鏈

如果直線L為y軸，則稱該單調(diào)鏈為對(duì)y軸單調(diào)鏈。基于單調(diào)鏈的凸分解算法中的單調(diào)鏈均為對(duì)y軸單調(diào)鏈。圖2.29中的多邊形有M1、M2、M3、M4共4條單調(diào)鏈。

尖點(diǎn)的定義:任意多邊形中，單調(diào)鏈的端點(diǎn)稱為尖點(diǎn)。對(duì)于相對(duì)于y軸的單調(diào)鏈，其上端點(diǎn)定義為上尖點(diǎn)，其下端點(diǎn)定義為下尖點(diǎn)。如圖2.29中，S1、S3為上尖點(diǎn)，S2、S4為下尖點(diǎn)。

上、下單調(diào)鏈:任意多邊形中，若沿環(huán)的方向單調(diào)鏈的起點(diǎn)為上尖點(diǎn)，終點(diǎn)為下尖點(diǎn)，則定義其為下單調(diào)鏈，相反則定義其為上單調(diào)鏈。圖2.29中，M1、M3為下單調(diào)鏈，M2、M4為上單調(diào)鏈。

圖2.29上、下尖點(diǎn)與上、下單調(diào)鏈

2)凸分解算法

參見圖2.30，基于單調(diào)鏈的凸分解算法主要包括三個(gè)步驟：

(1)將帶內(nèi)環(huán)多邊形分解為有序單調(diào)鏈。圖2.30(a)按下單調(diào)鏈分解，可分解為9個(gè)下單調(diào)鏈。

(2)通過分裂和組合單調(diào)鏈，逐次拆分出單調(diào)多邊形。由兩條單調(diào)鏈組成的多邊形稱為單調(diào)多邊形，圖(a)的多邊形可拆分如圖(b)所示的4個(gè)單調(diào)多邊形。

(3)將單調(diào)多邊形分解為凸多邊形，如圖(c)所示?？衫们笆龅陌级噙呅畏纸馑惴ㄟM(jìn)行分解。

圖2.30基于單調(diào)鏈的凸分解過程

2.7.4Delaunay三角剖分

蘇聯(lián)數(shù)學(xué)家Delaunay于1934年證明，對(duì)于散亂點(diǎn)集，必定存在且僅存在一種三角剖分算法，使得剖分得到的所有三角形的最小內(nèi)角之和最大(“最小角最大原則”)，這種算法稱為Delaunay三角剖分，簡(jiǎn)稱DT剖分。Delaunay三角剖分算法是最著名的三角化網(wǎng)格生成方法，因?yàn)樗哂小叭瞧史肿钚?nèi)角之和為最大”的性質(zhì)，從而保證了網(wǎng)格整體質(zhì)量最優(yōu)，稱為最優(yōu)三角剖分。DT剖分可用于數(shù)字地形建模、工程網(wǎng)格劃分、人臉圖像結(jié)構(gòu)建模等。

1.Delaunay三角剖分的性質(zhì)

Delaunay三角剖分具有一些非常重要的性質(zhì)，其中最為重要的性質(zhì)如下：

1)最小內(nèi)角最大準(zhǔn)則

對(duì)一個(gè)凸四邊形進(jìn)行劃分時(shí)，該準(zhǔn)則要求對(duì)角線兩側(cè)兩個(gè)三角形中的最小內(nèi)角為最大。沿短對(duì)角線進(jìn)行劃分可滿足最小內(nèi)角最大準(zhǔn)則，如圖2.31所示。

圖2.31最小內(nèi)角最大原則

2)空外接圓(空外接球)準(zhǔn)則

對(duì)于三角形剖分而言，該準(zhǔn)則稱為空外接圓準(zhǔn)則。對(duì)于四面體剖分而言，該準(zhǔn)則稱為空外接球準(zhǔn)則。這里討論三角形剖分。對(duì)于任意一個(gè)Delaunay三角形，它的外接圓的內(nèi)部區(qū)域不包含其他的任何結(jié)點(diǎn)，所有Delaunay三角形互不重疊，并且完整地覆蓋整個(gè)區(qū)域。

如圖2.32所示，左圖三點(diǎn)組成了Delaunay三角形，因其外接圓內(nèi)即虛線所示部分再無其他結(jié)點(diǎn)，而右圖三角形不滿足空外接圓準(zhǔn)則，故不是Delaunay三角形。

圖2.32Delaunay三角形空外接圓準(zhǔn)則

3)局部性

在已有的Delaunay剖分中加入、去除或移動(dòng)一個(gè)結(jié)點(diǎn)后，僅需進(jìn)行局部修改即可獲得Delaunay三角剖分，這就是DT剖分的局部性。所有需要進(jìn)行修改的三角形的并集稱為影響域。圖2.33左圖影響域?yàn)閹摼€的5個(gè)三角形的并集，右圖影響域?yàn)閹摼€的3個(gè)三角形的并集。可以證明，影響域的各結(jié)點(diǎn)對(duì)于加入或刪除的點(diǎn)來說都是可見的，所謂可見是指該點(diǎn)與結(jié)點(diǎn)連線不與三角形的邊相交，這給出了影響域的求取方法。因此，影響域是局部的。圖2.33表示了加入或刪除一點(diǎn)所需進(jìn)行的修改。局部性可用于網(wǎng)格稀疏或加密操作。

圖2.33Delaunay三角剖分的局部性

2.Delaunay三角剖分算法

參見圖2.34，算法主要步驟如下：

(1)從當(dāng)前多邊形(初始多邊形和每剖分一次剩余的多邊形)的第一邊開始，找對(duì)該邊的可見頂點(diǎn)(在多邊形內(nèi)且頂點(diǎn)與邊的端點(diǎn)連線不與多邊形的邊相交的頂點(diǎn))，若可見頂點(diǎn)有多個(gè)