张 芳， 朱合华

（1. 北京市勘察设计研究院有限公司，北京 100038；2. 同济大学岩土及地下工程教育部重点实验室、地下建筑与工程系，上海 200092）

三维TIN与TIN相交算法及其在岩土工程中应用

张 芳1， 朱合华2

（1. 北京市勘察设计研究院有限公司，北京 100038；2. 同济大学岩土及地下工程教育部重点实验室、地下建筑与工程系，上海 200092）

地质剖面图或篱栅图是地质勘探人员了解描述地质结构的常规手段之一。该文实现了从三维地质模型中提取任意剖面图的基础算法，即三维TIN与TIN相交算法。该算法作为许多商业图形软件的核心算法，属于商业秘密。该文详细论述了该算法原理、数据结构设计、计算流程等。该算法作为实现自主知识产权的三维岩土工程系统的一部分，既能灵活的设定曲面形状与方向，又能够顾及到复杂的约束条件。最后针对具体的工程实例检验了算法的正确性和应用价值。

计算机应用；TIN与TIN相交算法；剖面；空间分析

地质剖面图或篱栅图是地质勘探人员了解地质结构常规的手段之一。为了从三维地质模型中获得剖面信息，通常采用任意剖面去切割地层模型，三维TIN与TIN相交算法是实现该项功能的基础算法之一，另外，该算法也是地层建模及人工交互、GIS空间分析等功能的支撑算法，是许多三维地质、油田和 GIS商业软件的核心算法。

此外，在几何造型、计算机模拟、GIS、计算机辅助设计等领域中，往往要处理大量的复杂图形布尔运算问题，尤其是三维问题涉及到大量的三维TIN与TIN的相交处理，现在世界流行的CAD图形平台 ACIS、PARASOLID、Open CAS.CADE、DESIGNBASE等都很好的解决了这个问题，但由于涉及核心算法，源代码没有公布。三维TIN与TIN相交算法与二维相交算法相比复杂程度有量级上的区别，作为核心，属于商业秘密，本文探索该算法在三维上的实现，作为实现自主知识产权的某三维岩土工程系统的一部分。

1 TIN与TIN相交算法

空间三角形与三角形的相交问题是研究三维TIN与TIN相交算法的基础（但不是全部），Martin Held[1]和 Tomas Möller[2]提出的算法在其中最具代表性，Olivier Devillers[3]对这两种算法进行了比较。本文根据已知地层钻孔离散数据的特点，考虑搜索半径与搜索效率，编制实现了三维TIN与TIN相交算法。

1.1 算法原理

（1） 根据文献Tomas Möller[2]首先写出平面π2(或π1)点法式方程（见图1）

（2） 分别利用三角形 T1(或 T2)的三点到平面π2(或π1)的有向距离()的正负还是零来判断三角间的平行、共面还是可能相交三种情况。

图1 三角形求交线（Tomas Möller，1997）

（3） 对于可能相交的三角形，会出现两种情况，如图2(a)是真实的相交，图2(b)是相离的。本文对这两种情况统一处理，首先生成三角形 T1（或T2）与平面π2（或π1）的交线P1P2，再生成三角形T2（或T1）与平面π1（或π2）的交线Q1Q2（如图2），显然二者都位于交线L上，是交线L的一部分。

图2 三角形求交线（Tomas Möller，1997修改）

（4） 判断21PP 和21QQ 的关系，如果两者有重叠部分，则提取重叠线段即为所求，否则说明两三角形是相离的。

（5） 对于交线21PP （或21QQ ）的生成采用空间线段与无限平面求交来实现。

1.2 数据结构设计

本文数据结构的设计采用面向对象思想，以类的形式体现。考虑到书写方便这里不再详细介绍点、线段、三角形、四面体四种几何基元以及TIN类、相交算法等类的数据结构，仅给出类体系框图一张，如图3所示，本算法的类作为基类存在于该类系中。图中的类服务于“资源场”（“资源场”：顾及到人类对地理空间的认知，把整个地理空间（上至大气层、构筑物、地表、下到地下空间的地质体、构筑物等等）定义为一个资源场，且为唯一资源[4]）。“资源场”下有工程对象和地质对象两种几何对象。

图3 混合数据模型

1.3 算法特点

本算法是基于空间三角形与三角形之间的相交实现的，且以约束 Delaunay算法重构三角网，特别地在做约束Delaunay剖分时，算法中引入从局部平面 Delaunay剖分到整体三维Delaunay剖分的思想，很好地解决了三维空间约束条件下的Delaunay剖分生成问题，这个本质决定了以此算法为基础的分析功能的特色，即能灵活的设定曲面形状与方向，且能够顾及到复杂的约束条件。算法流程图如图4所示。

2 算法应用实例

作为算法的验证实例，主要从验证算法的稳定性、可靠性和实用性角度选用实例，旨在验证该算法做为开发系统底层算法的基本功能，这与工程的复杂性是两个概念，复杂的实例可基于这些基本功能扩展而来，当然任何一个底层基本算法不可能独立运行而不依赖其它达到整体效果。

基于实测钻孔资料，应用上述算法，可实现地层区域的任意剖切，本算法支持空间曲面剖分，能够用任意方向，任意形状的三维空间剖面对进行地层剖切显示，充分体现了算法区别其它算法的优势。

图4 三维TIN与TIN相交算法流程图

2.1 地层的任意剖切

本文从数据库中提取某处地层的钻孔数据共25个，含244个离散数据点，生成11层不同厚度和分布的土层，土层编号以上海标准土层为准，用不同颜色加以区别，如图5所示，地层中有一处尖灭和一处透镜体，分别为第1⑤-1层（红色表示）和第1⑥层土（黑色）。对该地层做任意剖切，其中剖切面（空间曲面）与地层关系如图5所示。图6(a)显示了各地层界面与剖切面的交线和交点情况，图6(b)是附加地层属性信息后得到剖曲面处的地层信息，需要说明的是在图6(b)中只显示剖切面与地层公共部分，对多余剖面部分没有显示，这样容易定位地层。

图5 地层与剖曲面的关系

图6 剖切曲面处地层信息

2.2 地下连续墙建模与分析

地下连续墙作为围护结构以及地下结构的部分外墙，其本身的强度与稳定直接关系到整个基坑工程的成败。本文利用岩土工程勘测报告（2005）提供的地下连续墙槽段平面布置图（图7(a)）提取出槽段信息（图 7(b)）作为地下连续墙建模的数据源，生成地下连续墙模型（图8）。这点实现了从CAD图到三维表达的自动生成，与设计单位习惯相符合。

施工中地下连续墙每个槽段处的地层信息很关健，本文利用生成的地下连续墙模型与三维地层模型（图9）相叠加，得到每个槽段处的地层信息（图10）。

图7 地下连续墙槽段平面布置图(岩土工程勘测报告2005)及提取出来的槽段信息

图8 地下连续墙模型

图9 三维地层表面模型

图10 按槽段显示地下连续墙的地层信息

3 结 束 语

三维TIN与TIN相交算法是几何造型、计算机辅助设计、GIS空间分析和三维地质建模系统中的基础算法，本文根据已知地层钻孔离散数据的特点，综合两个方法的优点，编制实现了三维TIN与TIN相交算法。并采用面向对象思想，对几何基元及相关算法类的数据结构进行了设计，该算法既能灵活的设定曲面形状与方向，又能够顾及到复杂的约束条件。经过实际工程应用，验证了方法正确性和应用价值。

[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]张 芳. 场框架下的城市地下空间三维数据模型及相关算法研究[D]. 上海：同济大学, 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-），女，辽宁大连人，工程师，博士，主要研究方向为岩土及地下工程数字化、水文地质与工程地质。