張 芳， 朱合華

（1. 北京市勘察設(shè)計(jì)研究院有限公司，北京 100038；2. 同濟(jì)大學(xué)巖土及地下工程教育部重點(diǎn)實(shí)驗(yàn)室、地下建筑與工程系，上海 200092）

三維TIN與TIN相交算法及其在巖土工程中應(yīng)用

張 芳1， 朱合華2

（1. 北京市勘察設(shè)計(jì)研究院有限公司，北京 100038；2. 同濟(jì)大學(xué)巖土及地下工程教育部重點(diǎn)實(shí)驗(yàn)室、地下建筑與工程系，上海 200092）

地質(zhì)剖面圖或籬柵圖是地質(zhì)勘探人員了解描述地質(zhì)結(jié)構(gòu)的常規(guī)手段之一。該文實(shí)現(xiàn)了從三維地質(zhì)模型中提取任意剖面圖的基礎(chǔ)算法，即三維TIN與TIN相交算法。該算法作為許多商業(yè)圖形軟件的核心算法，屬于商業(yè)秘密。該文詳細(xì)論述了該算法原理、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、計(jì)算流程等。該算法作為實(shí)現(xiàn)自主知識產(chǎn)權(quán)的三維巖土工程系統(tǒng)的一部分，既能靈活的設(shè)定曲面形狀與方向，又能夠顧及到復(fù)雜的約束條件。最后針對具體的工程實(shí)例檢驗(yàn)了算法的正確性和應(yīng)用價(jià)值。

計(jì)算機(jī)應(yīng)用；TIN與TIN相交算法；剖面；空間分析

地質(zhì)剖面圖或籬柵圖是地質(zhì)勘探人員了解地質(zhì)結(jié)構(gòu)常規(guī)的手段之一。為了從三維地質(zhì)模型中獲得剖面信息，通常采用任意剖面去切割地層模型，三維TIN與TIN相交算法是實(shí)現(xiàn)該項(xiàng)功能的基礎(chǔ)算法之一，另外，該算法也是地層建模及人工交互、GIS空間分析等功能的支撐算法，是許多三維地質(zhì)、油田和 GIS商業(yè)軟件的核心算法。

此外，在幾何造型、計(jì)算機(jī)模擬、GIS、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域中，往往要處理大量的復(fù)雜圖形布爾運(yùn)算問題，尤其是三維問題涉及到大量的三維TIN與TIN的相交處理，現(xiàn)在世界流行的CAD圖形平臺 ACIS、PARASOLID、Open CAS.CADE、DESIGNBASE等都很好的解決了這個問題，但由于涉及核心算法，源代碼沒有公布。三維TIN與TIN相交算法與二維相交算法相比復(fù)雜程度有量級上的區(qū)別，作為核心，屬于商業(yè)秘密，本文探索該算法在三維上的實(shí)現(xiàn)，作為實(shí)現(xiàn)自主知識產(chǎn)權(quán)的某三維巖土工程系統(tǒng)的一部分。

1 TIN與TIN相交算法

空間三角形與三角形的相交問題是研究三維TIN與TIN相交算法的基礎(chǔ)（但不是全部），Martin Held[1]和 Tomas M?ller[2]提出的算法在其中最具代表性，Olivier Devillers[3]對這兩種算法進(jìn)行了比較。本文根據(jù)已知地層鉆孔離散數(shù)據(jù)的特點(diǎn)，考慮搜索半徑與搜索效率，編制實(shí)現(xiàn)了三維TIN與TIN相交算法。

1.1 算法原理

（1） 根據(jù)文獻(xiàn)Tomas M?ller[2]首先寫出平面π2(或π1)點(diǎn)法式方程（見圖1）

（2） 分別利用三角形 T1(或 T2)的三點(diǎn)到平面π2(或π1)的有向距離()的正負(fù)還是零來判斷三角間的平行、共面還是可能相交三種情況。

圖1 三角形求交線（Tomas M?ller，1997）

（3） 對于可能相交的三角形，會出現(xiàn)兩種情況，如圖2(a)是真實(shí)的相交，圖2(b)是相離的。本文對這兩種情況統(tǒng)一處理，首先生成三角形 T1（或T2）與平面π2（或π1）的交線P1P2，再生成三角形T2（或T1）與平面π1（或π2）的交線Q1Q2（如圖2），顯然二者都位于交線L上，是交線L的一部分。

圖2 三角形求交線（Tomas M?ller，1997修改）

（4） 判斷21PP 和21QQ 的關(guān)系，如果兩者有重疊部分，則提取重疊線段即為所求，否則說明兩三角形是相離的。

（5） 對于交線21PP （或21QQ ）的生成采用空間線段與無限平面求交來實(shí)現(xiàn)。

1.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

本文數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)采用面向?qū)ο笏枷?，以類的形式體現(xiàn)。考慮到書寫方便這里不再詳細(xì)介紹點(diǎn)、線段、三角形、四面體四種幾何基元以及TIN類、相交算法等類的數(shù)據(jù)結(jié)構(gòu)，僅給出類體系框圖一張，如圖3所示，本算法的類作為基類存在于該類系中。圖中的類服務(wù)于“資源場”（“資源場”：顧及到人類對地理空間的認(rèn)知，把整個地理空間（上至大氣層、構(gòu)筑物、地表、下到地下空間的地質(zhì)體、構(gòu)筑物等等）定義為一個資源場，且為唯一資源[4]）?！百Y源場”下有工程對象和地質(zhì)對象兩種幾何對象。

圖3 混合數(shù)據(jù)模型

1.3 算法特點(diǎn)

本算法是基于空間三角形與三角形之間的相交實(shí)現(xiàn)的，且以約束 Delaunay算法重構(gòu)三角網(wǎng)，特別地在做約束Delaunay剖分時(shí)，算法中引入從局部平面 Delaunay剖分到整體三維Delaunay剖分的思想，很好地解決了三維空間約束條件下的Delaunay剖分生成問題，這個本質(zhì)決定了以此算法為基礎(chǔ)的分析功能的特色，即能靈活的設(shè)定曲面形狀與方向，且能夠顧及到復(fù)雜的約束條件。算法流程圖如圖4所示。

2 算法應(yīng)用實(shí)例

作為算法的驗(yàn)證實(shí)例，主要從驗(yàn)證算法的穩(wěn)定性、可靠性和實(shí)用性角度選用實(shí)例，旨在驗(yàn)證該算法做為開發(fā)系統(tǒng)底層算法的基本功能，這與工程的復(fù)雜性是兩個概念，復(fù)雜的實(shí)例可基于這些基本功能擴(kuò)展而來，當(dāng)然任何一個底層基本算法不可能獨(dú)立運(yùn)行而不依賴其它達(dá)到整體效果。

基于實(shí)測鉆孔資料，應(yīng)用上述算法，可實(shí)現(xiàn)地層區(qū)域的任意剖切，本算法支持空間曲面剖分，能夠用任意方向，任意形狀的三維空間剖面對進(jìn)行地層剖切顯示，充分體現(xiàn)了算法區(qū)別其它算法的優(yōu)勢。

圖4 三維TIN與TIN相交算法流程圖

2.1 地層的任意剖切

本文從數(shù)據(jù)庫中提取某處地層的鉆孔數(shù)據(jù)共25個，含244個離散數(shù)據(jù)點(diǎn)，生成11層不同厚度和分布的土層，土層編號以上海標(biāo)準(zhǔn)土層為準(zhǔn)，用不同顏色加以區(qū)別，如圖5所示，地層中有一處尖滅和一處透鏡體，分別為第1⑤-1層（紅色表示）和第1⑥層土（黑色）。對該地層做任意剖切，其中剖切面（空間曲面）與地層關(guān)系如圖5所示。圖6(a)顯示了各地層界面與剖切面的交線和交點(diǎn)情況，圖6(b)是附加地層屬性信息后得到剖曲面處的地層信息，需要說明的是在圖6(b)中只顯示剖切面與地層公共部分，對多余剖面部分沒有顯示，這樣容易定位地層。

圖5 地層與剖曲面的關(guān)系

圖6 剖切曲面處地層信息

2.2 地下連續(xù)墻建模與分析

地下連續(xù)墻作為圍護(hù)結(jié)構(gòu)以及地下結(jié)構(gòu)的部分外墻，其本身的強(qiáng)度與穩(wěn)定直接關(guān)系到整個基坑工程的成敗。本文利用巖土工程勘測報(bào)告（2005）提供的地下連續(xù)墻槽段平面布置圖（圖7(a)）提取出槽段信息（圖 7(b)）作為地下連續(xù)墻建模的數(shù)據(jù)源，生成地下連續(xù)墻模型（圖8）。這點(diǎn)實(shí)現(xiàn)了從CAD圖到三維表達(dá)的自動生成，與設(shè)計(jì)單位習(xí)慣相符合。

施工中地下連續(xù)墻每個槽段處的地層信息很關(guān)健，本文利用生成的地下連續(xù)墻模型與三維地層模型（圖9）相疊加，得到每個槽段處的地層信息（圖10）。

圖7 地下連續(xù)墻槽段平面布置圖(巖土工程勘測報(bào)告2005)及提取出來的槽段信息

圖8 地下連續(xù)墻模型

圖9 三維地層表面模型

圖10 按槽段顯示地下連續(xù)墻的地層信息

3 結(jié) 束 語

三維TIN與TIN相交算法是幾何造型、計(jì)算機(jī)輔助設(shè)計(jì)、GIS空間分析和三維地質(zhì)建模系統(tǒng)中的基礎(chǔ)算法，本文根據(jù)已知地層鉆孔離散數(shù)據(jù)的特點(diǎn)，綜合兩個方法的優(yōu)點(diǎn)，編制實(shí)現(xiàn)了三維TIN與TIN相交算法。并采用面向?qū)ο笏枷耄瑢缀位跋嚓P(guān)算法類的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了設(shè)計(jì)，該算法既能靈活的設(shè)定曲面形狀與方向，又能夠顧及到復(fù)雜的約束條件。經(jīng)過實(shí)際工程應(yīng)用，驗(yàn)證了方法正確性和應(yīng)用價(jià)值。

[1]Martin Held, ERIT. A collection of efficient and reliable intersection tests [R]. Technical Report,University at Stony Brook, 1996.

[2]Tomas M?ller. A fast triangle-triangle intersection test [J].Journal of Graphics Tools, 1997, 2(2)：25-30.

[3]Olivier Devillers, Philippe Guigue. Faste triangle-tri angle intersection tests [R]. INRIA, 2002.

[4]張 芳. 場框架下的城市地下空間三維數(shù)據(jù)模型及相關(guān)算法研究[D]. 上海：同濟(jì)大學(xué), 2006.

3D TIN Intersection Algorithm and Its Application in Geotechnical Engineering

ZHANG Fang1, ZHU He-hua2

( 1. BGI Engineering Consultants LTD, Beijing 100038, China; 2.Department of Geotechnical Engineering, Key Laboratory of Geotechnical and Underground Engineering (Tongji University), Ministry of Education, Shanghai 200092, China )

The geology cross-section is one of the normal means to describe geological structure. In this paper, an intersection algorithm between 3D TIN and TIN is accomplished to cut arbitrary cross section from the 3D geology model. The principle of the algorithm, the design of data structure and the calculation process are described in details. The algorithm can arbitrarily set the boundary shape and direction of cross-section and regard the complicated stipulation condition as well. Finally, the validity and the application value of the algorithm is testified by its application in two projects.

computer application; 3D TIN’s intersection algorithm; section; spatial analysis

P 208

A

1003-0158(2010)05-0151-06

2008-12-20

張 芳（1976-），女，遼寧大連人，工程師，博士，主要研究方向?yàn)閹r土及地下工程數(shù)字化、水文地質(zhì)與工程地質(zhì)。