三角網(wǎng)求交的共形幾何代數(shù)算法

宗 真，袁林旺，2，羅 文，俞肇元，2，胡 勇，3

1.南京師范大學(xué) 虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京210023；2.南京師范大學(xué) 江蘇省大規(guī)模復(fù)雜系統(tǒng)數(shù)值模擬重點(diǎn)實(shí)驗(yàn)室，江蘇南京210023；3.南京師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇南京210023

1 引 言

三角網(wǎng)表達(dá)及求交是三維表面模型建模的基礎(chǔ)，也是地質(zhì)工程、科學(xué)可視化以及模型分析的關(guān)鍵算法之一［1，2］。GIS研究對(duì)象向三維以及時(shí)空維的擴(kuò)展，不僅導(dǎo)致了數(shù)據(jù)量的激增［3］，也導(dǎo)致了對(duì)象表達(dá)結(jié)構(gòu)的復(fù)雜性。GIS對(duì)象表達(dá)結(jié)構(gòu)的復(fù)雜性，不僅使得在空間關(guān)系計(jì)算過(guò)程中對(duì)象類型及求交條件判斷模式的復(fù)雜，也增加了對(duì)諸如空間、邊界等復(fù)雜的空間約束［4］判斷的難度，因而極大地影響了現(xiàn)有矢量GIS的效率。伴隨著GIS研究對(duì)象向三維以及時(shí)空維的擴(kuò)展，三角網(wǎng)求交的復(fù)雜度也隨之增加。在三維動(dòng)態(tài)場(chǎng)景中，三角網(wǎng)中對(duì)象的維度、形態(tài)和結(jié)構(gòu)均存在顯著的變化［5］?；跉W氏幾何或計(jì)算幾何發(fā)展而來(lái)的三角網(wǎng)求交算法需要對(duì)其相對(duì)位置關(guān)系進(jìn)行預(yù)判斷，且在處理不同維度三角網(wǎng)時(shí)，需要對(duì)線、面進(jìn)行分別處理，導(dǎo)致了其對(duì)動(dòng)態(tài)變化的三角網(wǎng)求交支撐不足［6－7］。以文獻(xiàn)［8］算法為代表的標(biāo)量法在平面距離計(jì)算及交線位置判斷上的計(jì)算相對(duì)復(fù)雜，在大規(guī)模環(huán)境中時(shí)間耗費(fèi)較多。文獻(xiàn)［9］的矢量法利用行列式符號(hào)的幾何意義來(lái)判斷三角形的關(guān)系而后求交，計(jì)算過(guò)程中必須根據(jù)相關(guān)情況進(jìn)行復(fù)雜的判斷，導(dǎo)致程序結(jié)構(gòu)復(fù)雜，適應(yīng)性不強(qiáng)。

幾何代數(shù)是以代數(shù)語(yǔ)言進(jìn)行幾何對(duì)象表達(dá)、構(gòu)造與運(yùn)算的數(shù)學(xué)系統(tǒng)，被認(rèn)為是有效連接幾何與代數(shù)，實(shí)現(xiàn)幾何計(jì)算的數(shù)學(xué)語(yǔ)言［10］。共形幾何代數(shù)（conformal geometric algebra，CGA）基于協(xié)變視角引入了基準(zhǔn)原點(diǎn)和無(wú)窮遠(yuǎn)點(diǎn)，使得分別基于外積和內(nèi)積的形體表達(dá)和幾何度量都具有明確的幾何意義［11］。通過(guò)定義幾何代數(shù)運(yùn)算空間，可實(shí)現(xiàn)高維空間中不依賴于坐標(biāo)的幾何計(jì)算，前期研究表明幾何代數(shù)可用于多維空間對(duì)象的統(tǒng)一表達(dá)、建模與復(fù)雜對(duì)象間的空間關(guān)系分析［12－14］，且基于其設(shè)計(jì)的算法具有較強(qiáng)的高維拓展性［15］。本文針對(duì)三角網(wǎng)求交中三角形空間關(guān)系判定及點(diǎn)、線、面等不同幾何對(duì)象統(tǒng)一求交問(wèn)題，從代數(shù)表達(dá)與關(guān)系運(yùn)算相結(jié)合的角度，基于幾何代數(shù)中交并關(guān)系運(yùn)算的meet算子構(gòu)建空間關(guān)系判斷算子，為三角網(wǎng)表達(dá)結(jié)構(gòu)的動(dòng)態(tài)構(gòu)建及各維度組分的統(tǒng)一求解提供基礎(chǔ)，進(jìn)而實(shí)現(xiàn)多維統(tǒng)一三角網(wǎng)求交的幾何代數(shù)算法。

2 三角網(wǎng)的CGA表達(dá)與求交流程

2.1 三角網(wǎng)的CGA表達(dá)

基于內(nèi)積和外積進(jìn)行代數(shù)空間構(gòu)造及幾何對(duì)象表達(dá)，基于幾何代數(shù)多重向量（multivector）可實(shí)現(xiàn)多維幾何對(duì)象的整合表達(dá)。在幾何代數(shù)中，基于外積表達(dá)的幾何對(duì)象維度與Grassmann維度具有一致性，可以實(shí)現(xiàn)不同維度對(duì)象的構(gòu)造與相互轉(zhuǎn)化［10］。多重向量則為不同類型、不同維度幾何對(duì)象的描述和存儲(chǔ)提供了高維可拓展性。幾何代數(shù)自身的坐標(biāo)無(wú)關(guān)性與維度無(wú)關(guān)性使其所表達(dá)的幾何特征是幾何對(duì)象自身內(nèi)蘊(yùn)的幾何特征，計(jì)算獲得的幾何關(guān)系也是各幾何對(duì)象間不依賴坐標(biāo)的相對(duì)關(guān)系［11，16］。這為幾何對(duì)象的自適應(yīng)表達(dá)、關(guān)系判斷與關(guān)系計(jì)算提供了有利前提。CGA表達(dá)中包含有如方向、位置、值大小等幾何語(yǔ)義信息，可通過(guò)直觀的算子運(yùn)算直接判斷對(duì)象間相離、相交、包含等拓?fù)潢P(guān)系。表1給出了CGA中常用blade的分類及其所包含的幾何特征及其計(jì)算方法［15］。

表1 blade分類及其幾何特征Tab.1 Blades and their geometric characteristics

根據(jù)CGA中blade的表達(dá)，并結(jié)合前期研究中所構(gòu)造的基于CGA的三維空間數(shù)據(jù)模型［12］，可以構(gòu)造三角網(wǎng)的表達(dá)模式如圖1所示。首先構(gòu)建多重向量集合MVi。在MVi集合中任意一個(gè)對(duì)象均為構(gòu)成該三角網(wǎng)的特定三角形Ti，采用外積構(gòu)造點(diǎn)、線、面對(duì)象，并利用其邊界范圍將其約束為點(diǎn)、線段與三角形。利用CGA中幾何對(duì)象維度與Grassmann維度的一致性，實(shí)現(xiàn)點(diǎn)、線段與三角形的層次組織。在三角網(wǎng)的表達(dá)中，點(diǎn)、線段與三角形均用blade表達(dá)，且依據(jù)其層次關(guān)系組合形成最終的三角網(wǎng)多重向量表達(dá)。不僅在維度結(jié)構(gòu)上具有簡(jiǎn)明性，也為三角網(wǎng)的統(tǒng)一表達(dá)與空間關(guān)系計(jì)算提供了獨(dú)立、完備的數(shù)據(jù)組織與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。

2.2 三角網(wǎng)求交的幾何代數(shù)描述

幾何代數(shù)算子的多維統(tǒng)一性使其可以直接用于處理多維對(duì)象，而無(wú)需根據(jù)對(duì)象維度進(jìn)行分別處理［17］，從而可構(gòu)建簡(jiǎn)明、清晰、多維統(tǒng)一的三角網(wǎng)快速求交算法?；贑GA幾何對(duì)象表達(dá)的多維統(tǒng)一性和meet算子構(gòu)建三角網(wǎng)自適應(yīng)求交算法（圖1），通過(guò)對(duì)表征兩三角網(wǎng)的多重向量直接應(yīng)用meet算子實(shí)現(xiàn)對(duì)多重向量中所包含的各幾何對(duì)象的分別求交。對(duì)于基本幾何對(duì)象間交并關(guān)系的求解，如點(diǎn)、線、平面、圓環(huán)、球面等一般blade，可直接基于meet算子進(jìn)行運(yùn)算；對(duì)于求解含固定邊界幾何對(duì)象間交并關(guān)系，如多邊形、多面體對(duì)象，除了先基于meet算子進(jìn)行求交判斷外，還需借助對(duì)象表達(dá)中所蘊(yùn)含的豐富的幾何屬性特征，并定義一系列具有統(tǒng)一結(jié)構(gòu)的關(guān)系判斷算子，去除無(wú)效結(jié)果。最后將meet求解結(jié)果重新投影回歐氏空間，可設(shè)計(jì)相應(yīng)的語(yǔ)法解析器對(duì)運(yùn)算結(jié)果加以解析，并轉(zhuǎn)換成對(duì)應(yīng)幾何對(duì)象，形成三角網(wǎng)求交的最終算法流程。

圖1 基于幾何代數(shù)三角網(wǎng)求交流程Fig.1 Calculation flow of triangulation intersection based on geometric algebra

3 基于meet算子空間對(duì)象求交

3.1 meet算子與空間對(duì)象自適應(yīng)求交

不同幾何對(duì)象的相交關(guān)系會(huì)隨著對(duì)象類型和位置關(guān)系的變化而變化。傳統(tǒng)歐氏幾何中需要對(duì)不同維度對(duì)象各種相交情況分別進(jìn)行處理，導(dǎo)致時(shí)變對(duì)象的求交計(jì)算較為復(fù)雜，對(duì)動(dòng)態(tài)空間關(guān)系計(jì)算的支撐不足。在幾何代數(shù)中，不同幾何對(duì)象間所共有的最大子空間可以通過(guò)meet算子獲得。由于meet運(yùn)算的多維統(tǒng)一性，使其可以同時(shí)處理點(diǎn)、線、面以及其他各類blade表達(dá)的幾何對(duì)象間的相交運(yùn)算［17］。meet運(yùn)算的結(jié)果為多重向量，且其運(yùn)算結(jié)果的幾何對(duì)象類型僅與參與meet運(yùn)算的幾何對(duì)象相關(guān)，而與維度和坐標(biāo)系統(tǒng)無(wú)關(guān)。meet算子計(jì)算結(jié)果所具有的自適應(yīng)性，有助于實(shí)現(xiàn)利用單一算子實(shí)現(xiàn)不同幾何對(duì)象相交關(guān)系的統(tǒng)一求解。

給定任意兩bladeA和B，兩者間的meet運(yùn)算M＝A∩B滿足下式

引入可容納A、B的最小子空間偽標(biāo)量IAB，則meet算子可利用A、B間的對(duì)偶運(yùn)算求解

其一般形式為

式中，β為標(biāo)量。對(duì)于blade對(duì)象間的求交，可通過(guò)meet算子M的符號(hào)和它的平方M2的符號(hào)來(lái)作初步的相交關(guān)系判斷。Eduardo等基于meet算子詳細(xì)推導(dǎo)了線－線，線－面，面－面之間相交關(guān)系的計(jì)算方法與判斷規(guī)則［18］：當(dāng)M2＞0時(shí)，A與B至少相交于兩點(diǎn)；當(dāng)M2＝0時(shí)，A與B至少相切于一點(diǎn)；當(dāng)M2＜0時(shí)，A與B不交。各類型幾何對(duì)象基于meet算子的相交關(guān)系的判斷如表2。meet算子表達(dá)形式上的統(tǒng)一性及其計(jì)算結(jié)果的自適應(yīng)性使其可適用于動(dòng)態(tài)場(chǎng)景中變化對(duì)象的自適應(yīng)求交，并能保證動(dòng)態(tài)對(duì)象條件下，不同維度對(duì)象間空間關(guān)系計(jì)算的統(tǒng)一性與一致性。

表2 基于meet算子的基本幾何對(duì)象相交關(guān)系求解Tab.2 The solutions of intersection relations among basic geometric objects based on meet operators

3.2 空間對(duì)象meet的計(jì)算方法

meet算子對(duì)于求解A＝a1∧a2∧…∧ak形式的blade之間的交集簡(jiǎn)單有效，但對(duì)于由多個(gè)blade的加和構(gòu)成的k－blade間的meet運(yùn)算，需要基于join（并）和meet的關(guān)系對(duì)其進(jìn)行拆分和變換［10，19］。鑒于 meet運(yùn)算的可拆分性，可以通過(guò)將blade對(duì)象分解成線性無(wú)關(guān)的幾個(gè)支撐向量以簡(jiǎn)化運(yùn)算。對(duì)于k－bladeB，其因子分解就是要找到k個(gè)線性不相關(guān)的支撐向量fi，使得B＝βf1∧f2∧…∧fk。使用投影算子qi＝（pi」B－1）」B搜尋B中k個(gè)相互獨(dú)立的分解因子。設(shè)計(jì)meet算子快速求解算法，其基本流程為：

（1）先將“測(cè)試向量”pi投影到二維平面B上；

（2）用pi」B－1計(jì)算出pi在B中投影的正交補(bǔ)余；

（3）據(jù)公式qi＝（pi」B－1）」B求解pi」B－1順時(shí)針旋轉(zhuǎn)90度的正交投影，qi即為所求支撐向量；

（4）循環(huán)直至找到k個(gè)支撐向量。

由于對(duì)象分解過(guò)程具有可加和性和可逆性，且分解得到的qi線性不相關(guān)，可用于對(duì)象間meet的快速運(yùn)算。為快速求得meet算子結(jié)果的維度，可引入delta積運(yùn)算，其幾何意義為兩對(duì)象間的并集減交集［19－20］，存在

給定初始交積M＝1、并積J＝In，對(duì)于kbladeA與B，計(jì)算其delta積在空間IAB中的補(bǔ)集S＝（AΔB）＊，并將S分解為線性無(wú)關(guān)的k個(gè)部分Si；對(duì)于每個(gè)Si計(jì)算其投影pi，如果pi非零，則通過(guò)M＝M∧pi擴(kuò)充meet，直到M的維度與所求得meet的維度相等。

4 三角形求交中對(duì)象空間關(guān)系判斷

在復(fù)雜三角網(wǎng)對(duì)象求交中，對(duì)象間空間關(guān)系判斷是進(jìn)行求交對(duì)象篩選和處理的基礎(chǔ)。在三角形求交過(guò)程中，主要需考慮不同線段、線段與三角形以及點(diǎn)與三角形之間的關(guān)系判斷。為此，基于三角形及其相關(guān)幾何對(duì)象的CGA表達(dá)，通過(guò)構(gòu)造相應(yīng)的判斷算子進(jìn)行上述對(duì)象的空間關(guān)系判斷。其計(jì)算過(guò)程如圖2所示。

圖2 線段、三角形、點(diǎn)的位置關(guān)系判斷Fig.2 Location relations judgment between segments，triangles and points

4.1 平面上的線段與線段的關(guān)系判斷算子

計(jì)算線段R1及其端點(diǎn)p1與線段R2兩端點(diǎn)所構(gòu)成向量間的外積2－bladeB1＝v3∧v1、B2＝v3∧v2，同理可求得由線段R2及R1端點(diǎn)所構(gòu)成向量間外積B3、B4。構(gòu)建平面上線段關(guān)系判斷算子：Oseg－seg＝（dir（B1）＝ ＝dir（B2））‖（dir（B3）＝＝dir（B4）），當(dāng)Oseg－seg為true時(shí)，線段不交，否則線段相交。

4.2 線段與三角形的關(guān)系判斷算子

構(gòu)建由線段R的頂點(diǎn)q1到三角形的三個(gè)頂點(diǎn)所構(gòu)成向量的外積3－bladeTr1＝v1∧v2∧v3，同理可得到由頂點(diǎn)q2與三角形頂點(diǎn)所構(gòu)成向量的外積Tr2。構(gòu)建線段與三角形的關(guān)系判斷算子：Oseg－tri＝（dir（Tr1）＝＝dir（Tr2）），當(dāng)Oseg－tri為true時(shí)，二者不交，否則線段與三角形相交。

4.3 平面上點(diǎn)與三角形的關(guān)系判斷算子

構(gòu)建由三角形各頂點(diǎn)指向待求點(diǎn)的向量，按一定的方向計(jì)算三角形邊同各向量的外積：B1＝v12∧v10、B2＝v23∧v20、B3＝v31∧v30。構(gòu)建點(diǎn)與三角形的關(guān)系判斷算子：Opt－tri＝（dir（B1）≥0＆＆dir（B2）≥0＆＆dir（B3）≥0），當(dāng)Opt－tri為true時(shí)，點(diǎn)在三角形內(nèi)部或邊界，否則點(diǎn)在三角形外部。

5 算法實(shí)現(xiàn)與案例驗(yàn)證

5.1 三角形求交的形式化表達(dá)

不失一般性，據(jù)文獻(xiàn)［17］構(gòu)建的基于幾何代數(shù)的對(duì)象表達(dá)模型，給定兩三角形T1、T2，其共形幾何代數(shù)表達(dá)為

上述三角形的多重向量表達(dá)中，已同時(shí)包含有各三角形中線段和面對(duì)象的幾何代數(shù)表達(dá)，其meet的求解過(guò)程為

式中，S1∩l21＋S1∩l22＋S1∩l23由于與S2∩l11＋S2∩l12＋S2∩l13具有等同性，二者取一即可，并根據(jù)三角形與直線的構(gòu)建關(guān)系可將上式改寫(xiě)成如下形式

式中，“＊”僅為一種連接關(guān)系，不參與運(yùn)算，表示當(dāng)“＊”左側(cè)滿足一定要求時(shí)，才進(jìn)行其右側(cè)運(yùn)算，即在求解過(guò)程中，可利用面—面、線—面、線—線對(duì)象meet算子結(jié)果的符號(hào)對(duì)其相交關(guān)系進(jìn)行初步判定，從而降低算法的計(jì)算復(fù)雜度。

5.2 算法描述與流程

基于上述形式化表達(dá)，利用三角形求交的空間關(guān)系判定方法，構(gòu)造相應(yīng)的判定算子對(duì)其空間關(guān)系進(jìn)行判定，進(jìn)而獲得三角形在共面、異面等情況下，其中各要素的相交情況，然后將求交結(jié)果逆向回溯，由交點(diǎn)構(gòu)建線段，即為所求交線結(jié)果。

其算法流程如圖3所示。首先利用meet算子進(jìn)行三角形所在平面間相交關(guān)系的預(yù)判斷，即M＝（T1∩T2）。由于當(dāng)M2＜0時(shí)，T1與T2不交，因此，可篩選出所有M2＜0（即不滿足相交條件）的三角形，對(duì)所有可能滿足相交條件的三角形進(jìn)行空間關(guān)系的判斷。構(gòu)造由三角形T1任一頂點(diǎn)A1、B1、C1到三角形T2頂點(diǎn)A2、B2、C2所構(gòu)成向量的外積3－bladeVol＝A2∧B2∧C2值是否為零，篩選出共面相交的情況。對(duì)于異面相交的三角形，計(jì)算三角形各邊與另一三角形平面的meet。共面相交的三角形，則需要遍歷計(jì)算兩三角形邊與邊的meet，并通過(guò)交點(diǎn)、交線與三角形空間位置關(guān)系判斷算子篩選出落在三角形內(nèi)部或邊界上的對(duì)象。

圖3 三角形求交流程示意Fig.3 The triangle intersection process

對(duì)上述算法流程的求解步驟為：

輸入：待求交的兩三角網(wǎng)T1、T2。

輸出：兩三角網(wǎng)交線、交點(diǎn)等幾何對(duì)象Vout。

（1）對(duì)T1、T2進(jìn)行幾何代數(shù)編碼，形成多重向量表達(dá)MVT1、MVT2；

（2）順序提取MVT1、MVT2中三角形Π1、Π2，對(duì)其所在平面求meet，并進(jìn)行三角形相交與共面的判斷；

（3）對(duì)Π1、Π2中各邊求交，判斷其相交情況；

（4）對(duì)所求交點(diǎn)、交線與三角形關(guān)系進(jìn)行判斷，當(dāng)交點(diǎn)、交線在三角形內(nèi)時(shí)，保留結(jié)果；

（5）依次遍歷三角網(wǎng)中各三角形，直至所有三角形求交完成；

（6）解析計(jì)算結(jié)果，轉(zhuǎn)化為對(duì)應(yīng)歐氏幾何對(duì)象輸出或可視化。

5.3 案例驗(yàn)證

以南極冰蓋時(shí)空演化［21］的三維表面模型求交為例進(jìn)行算法驗(yàn)證，選用33 800Ka BP、33 550Ka BP、33 400Ka BP、33 300Ka BP、33 200Ka BP 5個(gè)時(shí)間節(jié)點(diǎn)的南極冰蓋三角網(wǎng)曲面模擬數(shù)據(jù)作為案例數(shù)據(jù)，數(shù)據(jù)結(jié)點(diǎn)及三角網(wǎng)個(gè)數(shù)信息見(jiàn)表3。利用幾何代數(shù)對(duì)三角形的統(tǒng)一表達(dá)與運(yùn)算，結(jié)合相關(guān)的運(yùn)算與判斷算子，設(shè)計(jì)三角網(wǎng)求交的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)和算法。首先對(duì)三角網(wǎng)格曲面數(shù)據(jù)進(jìn)行共形空間轉(zhuǎn)換與維度映射，實(shí)現(xiàn)三角格網(wǎng)的幾何代數(shù)表達(dá)與存儲(chǔ)；然后利用空間三角形的幾何代數(shù)求交方法，基于meet算子和關(guān)系判斷算子Oseg－seg、Oseg－tri、Opt－tri進(jìn)行相交結(jié)果的篩選與位置關(guān)系判斷，并獲取相應(yīng)的交點(diǎn)與交線段，最后求得兩個(gè)時(shí)期冰蓋表面的曲面交線。結(jié)果顯示本文算法提取出的交線能夠清晰反映某一時(shí)刻冰蓋曲面相對(duì)原始冰蓋變化的空間結(jié)構(gòu)與位置，可為地質(zhì)地形建模與分析提供可行的思路與方法（圖4）。

表3 三角網(wǎng)數(shù)據(jù)的基本信息Tab.3 General information of the triangulation data

圖4 本文算法求得的南極冰蓋表面三角網(wǎng)交線結(jié)果Fig.4 The triangulation intersection of Antarctic ice sheet based on CGA algorithm

對(duì)上述三角網(wǎng)交線結(jié)果進(jìn)行分析易知其中含有大量的重復(fù)交線，這些冗余交線會(huì)影響后期交線拓?fù)涞臉?gòu)造效率。冗余交線主要產(chǎn)生于如下3種情況：①退化交線（交點(diǎn)），例如當(dāng)一三角形頂點(diǎn)與另一三角形相切（接）時(shí)，交線段退化為交點(diǎn)，此交點(diǎn)必為其鄰接三角形交線的頂點(diǎn)；②切交線，例如當(dāng)三角形一邊切另一三角形面時(shí)，該三角形的鄰接三角形必求解出相同的切交線；③接交線，例如當(dāng)兩個(gè)三角形的邊部分或整體重合時(shí)，該求解結(jié)果將會(huì)在其鄰接三角形中重復(fù)出現(xiàn)。情況①中的點(diǎn)由于不參與拓?fù)錁?gòu)建可直接刪除，情況②與情況③中需要保留一條交線用于構(gòu)造交線拓?fù)?。基于上述考慮，可分別為線線關(guān)系判斷算子Oseg－seg和線面關(guān)系判斷算子Oseg－tri添加判斷條件Bi＝＝0，i＝1，…，4和Oseg－segi＝＝true，i＝1，2，3，標(biāo)記出線線相接和線面相接的情況，對(duì)退化交線加以篩除，式中Bi為線段端點(diǎn)構(gòu)成的2－blade，segi指代三角形tri的第i條邊。

分別運(yùn)用M?ller標(biāo)量法、Guigue＆Devillers矢量法和本文算法（CGA算法）按時(shí)間序?qū)ι鲜鋈蔷W(wǎng)數(shù)據(jù)兩兩求交，統(tǒng)計(jì)出交線數(shù)目及各算法運(yùn)行時(shí)間，對(duì)本文算法的準(zhǔn)確性和效率加以驗(yàn)證。最終交線的統(tǒng)計(jì)結(jié)果如表4所示。由于基于CGA的三角形求交算法去除了一定量的冗余交線，其求得的交線總數(shù)均小于另兩算法，減去冗余交線后，三算法求得的有效交線數(shù)目一致，表明了本算法求解結(jié)果的準(zhǔn)確性與有效性。從計(jì)算效率上看（圖5），本方法較 M?ller算法略快，但慢于Guigue＆Devillers算法。其主要原因在于，本文實(shí)現(xiàn)的CGA算法是將幾何對(duì)象由三維歐氏空間投影到五維空間后，使用數(shù)值運(yùn)算而非邏輯位運(yùn)算進(jìn)行幾何代數(shù)計(jì)算的求解，導(dǎo)致了內(nèi)積、外積以及meet算子等基本幾何代數(shù)運(yùn)算仍然依賴于加、減、乘、除等數(shù)值運(yùn)算。通過(guò)基于邏輯位運(yùn)算優(yōu)化的幾何代數(shù)引擎的利用［22］，可進(jìn)一步大幅提升運(yùn)算效率。而幾何代數(shù)對(duì)象表達(dá)與運(yùn)算的統(tǒng)一性，及其算法的結(jié)構(gòu)簡(jiǎn)明性與自適應(yīng)性，也為基于幾何代數(shù)的并行計(jì)算方法提供了便利［23］。

表4 三角網(wǎng)相交結(jié)果統(tǒng)計(jì)Tab.4 The statistical results of the triangulation intersection

圖5 三角形求交算法效率對(duì)比Fig.5 Efficiency comparisons of the three triangulation intersection algorithms

6 結(jié)論與展望

三角形是三角網(wǎng)格曲面、四面體格網(wǎng)、單純形剖分等三維矢量模型構(gòu)建的基本單元，三角形求交運(yùn)算是上述模型空間拓?fù)潢P(guān)系運(yùn)算的基礎(chǔ)。空間對(duì)象的相交、距離關(guān)系的判斷是空間拓?fù)浞治龅幕A(chǔ)，幾何代數(shù)通過(guò)定義相應(yīng)的運(yùn)算空間實(shí)現(xiàn)多維對(duì)象的統(tǒng)一表達(dá)與計(jì)算。本文利用幾何代數(shù)多維統(tǒng)一表達(dá)與運(yùn)算的優(yōu)勢(shì)，設(shè)計(jì)了三角形等基本對(duì)象的統(tǒng)一表達(dá)；基于meet算子維度統(tǒng)一與對(duì)象無(wú)關(guān)特性，構(gòu)建統(tǒng)一的三角形求交運(yùn)算流程；并設(shè)計(jì)相應(yīng)的關(guān)系判斷算子實(shí)現(xiàn)計(jì)算過(guò)程中對(duì)象的篩選與判斷。

在三角形的求交過(guò)程中存在三角形退化為線段、三角形相接、三角形相切等多種臨界與奇異情況，在所選的兩類傳統(tǒng)對(duì)比算法中，均存在人為設(shè)定的相交準(zhǔn)則，使得計(jì)算流程存在一定的定制化，而對(duì)不同維度、不同對(duì)象缺乏自適應(yīng)性。本文算法基于統(tǒng)一的多重向量表達(dá)及靈活的關(guān)系判斷算子可根據(jù)應(yīng)用需要合理配制相交準(zhǔn)則，對(duì)動(dòng)態(tài)場(chǎng)景下的時(shí)變對(duì)象間相交關(guān)系的計(jì)算具有更強(qiáng)的自適應(yīng)性?；谀蠘O冰蓋曲面網(wǎng)格數(shù)據(jù)的案例表明，本文提出的基于幾何代數(shù)的三角形快速求交方法，可有效支撐三角網(wǎng)的求交運(yùn)算，且邏輯結(jié)構(gòu)清晰，運(yùn)算簡(jiǎn)潔高效，可為其他復(fù)雜幾何對(duì)象間建模表達(dá)與空間分析統(tǒng)一求解提供借鑒。

支持復(fù)雜對(duì)象與現(xiàn)象的動(dòng)態(tài)化表達(dá)、建模與模擬是GIS發(fā)展的必然趨勢(shì)［24］。建立幾何—拓?fù)洹Z(yǔ)義一致的且可有效支撐地學(xué)分析的地理格網(wǎng)與空間分析模型是實(shí)現(xiàn)上述目標(biāo)的重要途徑［25］?；趲缀未鷶?shù)的三角網(wǎng)參數(shù)化表達(dá)在融入對(duì)象的幾何、拓?fù)涮卣鞯耐瑫r(shí)可直接支撐幾何運(yùn)算，并具有對(duì)象和維度的自適應(yīng)性。除meet算子外，大部分的幾何代數(shù)算子均具有類似的多維統(tǒng)一和自適應(yīng)特性，因此，基于幾何代數(shù)算子設(shè)計(jì)對(duì)象和維度無(wú)關(guān)的空間關(guān)系計(jì)算算法，將可為多維統(tǒng)一分析與計(jì)算提供了新的理論與方法參考。未來(lái)主要的研究拓展包括：①研究可支撐復(fù)雜對(duì)象的幾何代數(shù)表達(dá)方法，實(shí)現(xiàn)地理場(chǎng)景中不規(guī)則邊界形體數(shù)據(jù)的語(yǔ)義結(jié)構(gòu)與拓?fù)涮匦苑治?；②基于幾何代?shù)算法流程的一致性與邏輯結(jié)構(gòu)的簡(jiǎn)潔性，構(gòu)建并行化分析算法以支撐大規(guī)模復(fù)雜場(chǎng)景及海量數(shù)據(jù)分析；③將算法向復(fù)雜、高維對(duì)象擴(kuò)展，設(shè)計(jì)幾何與語(yǔ)義統(tǒng)一的空間關(guān)系計(jì)算算法，建立具有以維度融合為特征的GIS空間分析體系。

［1］ AI Tinghua，LIU Yaolin，HUANG Yafeng.The Hierarchical Watershed Partitioning and Generalization of River Network［J］.Acta Geodaetica et Cartographica Sinica，2007，36（2）：231－236，243.（艾廷華，劉耀林，黃亞鋒.河網(wǎng)匯水區(qū)域的層次化剖分與地圖綜合［J］.測(cè)繪學(xué)報(bào)，2007，36（2）：231－236，243.）

［2］ ZHANG Yao，F(xiàn)AN Hong，HUANG Wang.The Method of Generating Contour Tree Based on Contour Delaunay Triangulation［J］.Acta Geodaetica et Cartographica Sinica，2012，41（3）：461－467.（張堯，樊紅，黃旺.基于Delaunay三角網(wǎng)的等高線樹(shù)生成方法［J］.測(cè)繪學(xué)報(bào)，2012，41（3）：461－467.）

［3］ WANG Yuan，LIU Jianyong，JIANG Nan，et al.A Dynamic Triangulation Algorithm for the View－dependent and Realtime LoD Model of Terrain［J］.Acta Geodaetica et Cartographica Sinica，2003，32（1）：47－52.（王源，劉建永，江南，等.視點(diǎn)相關(guān)實(shí)時(shí)LoD地形模型動(dòng)態(tài)構(gòu)網(wǎng)算法［J］.測(cè)繪學(xué)報(bào)，2003，32（1）：47－52.）

［4］ LIU Qiliang，DENG Min，SHI Yan，et al.A Novel Spatial Clustering Method Based on Multi－constraints［J］.Acta Geodaetica et Cartographica Sinica，2011，40（4）：509－516.（劉啟亮，鄧敏，石巖，等.一種基于多約束的空間聚類方法［J］.測(cè)繪學(xué)報(bào)，2011，40（4）：509－516.）

［5］ SUN Dianzhu，LI Xincheng，TIAN Zhongchao，et al.Accelerated Boolean Operations on Triangular Mesh Models Based on Dynamic Spatial Indexing［J］.Journal of Computer－aided Design ＆ Computer Graphics，2009，21（9）：1232－1237.（孫殿柱，李心成，田中朝，等.基于動(dòng)態(tài)空間索引結(jié)構(gòu)的三角網(wǎng)格模型布爾運(yùn)算［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，21（9）：1232－1237.）

［6］ JIANG Qianping，TANG Jie，YUAN Chunfeng.Fast Triangle Mesh Surface Intersection Algorithm Based on Uniform Grid［J］.Computer Engineering，2008，34（21）：172－174.（蔣錢平，唐杰，袁春風(fēng)，等.基于平均單元格的三角網(wǎng)曲面快速求交算法［J］.計(jì)算機(jī)工，2008，34（21）：172－174.）

［7］ YIN Changlin，YU Dingquan.Rapid Topological Searchingbased Intersection Algorithm of Triangulated Networks［J］.Computer Engineering and Applications，2006，42（36）：209－211.（尹長(zhǎng)林，喻定權(quán).一種基于拓?fù)渌阉鞯娜蔷W(wǎng)求交算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（36）：209－211.）

［8］ M?LLER T.A Fast Triangle－triangle Intersection Test［J］.Journal of Graphics Tools，1997，2（2）：25－30.

［9］ GUIGUE P，DEVILLERS O.Fast and Robust Triangle：Triangle Overlap Test Using Orientation Predicates［J］.Journal of Graphics Tools，2003，8（1）：25－42.

［10］ DORST L，F(xiàn)ONTIJNE D，MANN S.Geometric Algebra for Computer Science［C］∥ An Object－oriented Approach to Geometry.San Fransisco：Morgan Kaufmann Publishers，2007.

［11］ LI Hongbo.Conformal Geometric Algebra：A New Framework for Computational Geometry［J］.Journal of Computer Aided Design ＆ Computer Graphics，2005，17（11）：2383－2393.（李洪波.共形幾何代數(shù)：幾何代數(shù)的新理論和計(jì)算框架［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（11）：2383－2393.）

［12］ YUAN L W，YU Z Y，CHEN S F，et al.CAUSTA：Clifford Algebra－based Unified Spatio－temporal Analysis ［J］.Transactions in GIS，2010，14（s1）：59－83.

［13］ LASENBY J.New Geometric Methods for Computer Vision：An Application to Structure and Motion Estimation［J］.Inter－national Journal of Computer Vision，1998，26（3）：191－213.

［14］ YUAN L W，YU Z Y，LUO W，et al.A 3DGIS Spatial Data Model Based on Conformal Geometric Algebra［J］.Science China：Earth Sciences，2011，54（1）：101－112.

［15］ YI Lin，YUAN Linwang，Yu Zhaoyuan，et al.Cliffrod Algebra－based Voronoi Algorithm［J］.Geography and Geo－Information Science，2011，27（5）：37－41.（易琳，袁林旺，俞肇元，等.Voronoi生成的Clifford代數(shù)實(shí)現(xiàn)方法［J］.地理與地理信息科學(xué)，2011，27（5）：37－41.）

［16］ PERWASS C.Geometric Algebra with Applications in Engineering［M］.Heidelberg：Springer－Verlag，2009.

［17］ YUAN L W，LüG N，LUO W，et al.Geometric Algebra Method for Multidimensionally：Unified GIS Computation［J］.China Science Bulletin，2012，57（7）：802－811.

［18］ EDUARDO R.Operaciones de Cómputo Gráfico en el Espacio Geométrico Conforme 5DUsando GPU［D］.Caracas：Universidad Simón Bolívar，2011.

［19］ FONTIJNE D，DORST L.Efficient Algorithms for Factorization and Join of Blades［C］∥Proceedings of the 3rd International Conference on Applications of Geometric Algebras in Computer Science and Engineering（AGACSE 2008）.London：Grimma，2010.

［20］ BOUMA T A，DORST L，PIJLS H G J.Geometric Algebra for Subspace Operations［J］.Acta Applicandae Mathematicae，2002，73：285－300.

［21］ DECONTO R.POLLARD D.Rapid Cenozoic Glaciation of Antarctica Induced by Declining Atmospheric CO2［J］.Nature，2003，421：245－249.

［22］ FRANCHINI S，GENTILE A，SORBELLO F，et al.Fixedsize Quadruples for a New，Hardware－oriented Representation of the 4DClifford Algebra［J］.Advances in Applied Clifford Algebras，2011，21（2）：315－340.

［23］ WAREHAM R J.Computer Graphics Using Conformal Geometric Algebra［D］.Cambridge：University of Cambridge，2006.

［24］ GOODCHILD M F，GUO H，ANNONI A，et al.Nextgeneration Digital Earth［J］.Proceedings of the National Academy of Sciences，2012，109（28）：11088－11094.

［25］ CAMELLI F，LIEN J M，SHEN D，et al.Generating Seamless Surfaces for Transport and Dispersion Modeling in GIS［J］.Geoinformatica，2012，16（2）：307－327.