方案。通过工程实例验证，在巷道曲面相交建模中，相比于层次有向包围盒（OBB）算法，圆柱体AABB双层包围盒在包围盒生成方面效率提高近50%，具有建模简单、检测时间短、顶层检测准确度高等特点。
关键词：巷道建模； 三角网划分； 圆柱体包围盒；三维布尔运算；网格优化
中图分类号： TP391
文献标志码：A
Abstract：
Aiming at the problems of too long operation time and complex modeling of the threedimensional roadway intersection modeling in geotechnical engineering， a method about cylinderAxis Aligned Bounding Box （AABB） twolevel bounding box detection was proposed according to the characteristics of tunnels shape. The proposed method could quickly find out the possible intersected triangular elements and established a new approach to solve the Irregular Triangular Network （TIN） modeling problem of tunnel intersection by combining the threeDimensional （3D） Boolean operation. The basic principles of the cylinderAABB double bounding box collision detection and the key technologies about Boolean operation to implement intersection modeling in 3D were described， and an optimization scheme for generated entity mesh was proposed. Through the engineering examples， it is proved that， compared with the Oriented Bounding Box （OBB） hierarchical bounding box method， the modeling method by cylinderAABB detection increases nearly 50% on the bounding box production efficiency in the roadway surface intersection modeling. The proposed method has the advantages of simple modeling， short detection time， high top detection accuracy， and so on.
英文关键词Key words：
tunnel modeling；triangulation；cylinder bounding box；threeDimensional （3D） Boolean operation；mesh optimization
0引言
曲面相交（Surface/Surface Intersection， SSI）算法是计算机辅助几何设计中一个重要研究内容，按处理的对象不同可以分为参数型和非参数型曲面相交算法[1]。非参数曲面，即不规则曲面，一般是由简单几何面片（如三角形、四边形等）构成的网格曲面，通常由采集的点云数据连接而成。这类曲面没有规律，通常不能用简单的数学公式进行表达，其中基于三角形的不规则曲面（Triangulated Irregular Network， TIN）相交算法的研究最为活跃。由于地下巷道布局复杂，构成TIN巷道的三角形单元很多，相交运算十分耗时。如何通过碰撞检测快速查找相交的三角形，成为影响算法的关键因素。
碰撞检测算法大体可以分为空间分解法和层次包围盒法。其中，层次包围盒，是指将元素通过包围球（Bounding Sphere）[2]、轴向包围盒（Axis Aligned Bounding Box， AABB）[3]、方向包围盒（Oriented Bounding Box， OBB）[4]、离散凸包包围盒（Discrete Orientation Polytopes， KDOPs）[5]等体积略大、几何特性简单的对象依次包围形成树形包含结构，检测时逐层逼近查找的方法。近年来，混合层次包围盒借助不同包围盒的几何特性分层定位查找，能够快速过滤掉大部分不相交的元素，得到了广大学者的青睐[6-9]。但通常的混合层次包围盒都只在意快速的判定元素是否相交，不能提取出相交的基本单元（如三角形），而如果对所有的基本单元都建立OBB，不仅前期处理复杂，相交判定也十分耗时。本文根据TIN巷道的几何特性，提出一种圆柱体AABB双层包围盒，通过三角形顶点与圆柱体的位置关系快速查找出所有可能相交的三角形单元，再对两实体中可能相交的三角形单元进行AABB相交检测，从而大幅减少三角形相交判定的时间。在此基础上，本文对巷道相交关键技术进行了详细的描述。
1主要思路
假设空间中两个TIN巷道实体A、B，根据布尔运算的基本思想，将具体的运算步骤划分为以下几个部分：
1）建立实体圆柱体包围盒和三角形AABB包围盒，通过两层包围盒的碰撞检测，确定可能相交的三角形对。
2）对上述可能相交的三角形对，通过Tomas Mller算法[10]进行准确的相交检测，对真正相交的三角形对计算交线段。
3）根据交线段对相交的三角形进行分割，形成新的三角形。
4）根据三角形面片与另一实体的位置关系进行归类，确定当前三角形与另一实体的包含关系，即在另一实体内部、外部还是边界上。
5）根据布尔运算中的并运算法则，保留所有在A、B实体边界及内部的单元，形成组合在一起的相交巷道实体。
6）对相交线附近的三角网进行优化。
算法主要活动图如图1所示。
1.1圆柱体AABB包围盒
对于空间中任意两TIN巷道A、B，规定三角形面片逆时针为正，面片外法向指向巷道内部。以巷道A的中轴线L为轴作圆柱体（底板半径为R）将整个巷道包围在内，该圆柱体定义为巷道A的圆柱体包围盒。图2以规则网格巷道为例说明，TIN巷道原理相同。
圆柱体AABB层次包围盒碰撞检测方法：取巷道B内一顶点P（x0，y0，z0），计算P到中轴线L的距离。设L的点向式方程为：
L=M0+Nt
（1）
其中：M0为直线上任意一点（x1，y1，z1）；N为L方向向量（l，m，n），则P到直线L的距离可表示为式（2）。
d=M0P×NN=D12+D22+D32l2+m2+n2
（2）
其中：
D1=y0-y1z0-z1mnD2=z0-z1x0-x1nl
D3=x0-x1y0-y1lm
如果d>R，则点P在巷道A圆柱包围盒外；
如果d≤R，设P到直线L的垂足为Mc（xc，yc，zc），则Mc满足：
xc=l×t+x1
yc=m×t+y1
zc=n×t+z1
由垂线向量（x0-xc，y0-yc，z0-zc）和L方向向量（l，m，n）的数量积为0，得：
l×（x0-xc）+m×（y0-yc）+n×（z0-zc）=0
（4）
联合式（3）和式（4）可以求出垂足对应的参数tc：
tc=l×（x0-x1）+m×（y0-y1）+n×（z0-z1）l2+m2+n2
（5）
设巷道A的起始点和终止点对应于轴线L的参数分别为t1、t2（设t1 根据上述方法，遍历巷道B全部顶点，查找出所有在A圆柱包围盒内部的顶点，组成集合VCB。同理，对巷道B建立圆柱包围盒，计算出所有巷道A在B圆柱包围盒内部的顶点集合VCA。 将巷道B中顶点包含VCB元素的所有三角形单元定义为集合TCB，巷道A中顶点包含VCA元素的所有三角形单元定义为集合TCA。 将TCA与TCB中的三角形依次作AABB碰撞检测，进一步确定可能相交的三角形对集合TIAB。 1.2三角形相交判定及交线提取 空间中三角形彼此相交问题最常用的求解方法可以分为标量判别型和矢量判别型两类，其中标量判别型有代表性的是Held算法[11]和Tomas Mller算法。本节中主要是在Tomas Mller算法基础上进行了改进，具体步骤如下： 1）设空间中两三角形面片T1和T2所在平面分别记作π1和π2。V10、V11、V12 和V20、V21、V22分别为T1、T2的顶点。 平面π2的点法式方程为： n2·X+d2=0 （6） 其中： n2=（OV21-OV20）×（OV22-OV20）为π2单位法向向量；d2=-n2·OV20（O为坐标原点）。 T1顶点到平面π2的有向距离公式为： dV1i=-n2·OV1i+d2； i=0，1，2 （7） 根据dV1i的符号可以判定三角形T1与π2的相对位置：当dV1i全为0时，T1与π2共面；符号相同（同正或同负），则T1与π2不相交；如果符号不完全相同，则T1与π2相交。 2）交线段（交点）提取。 设T1与π2相交于直线L′，其方程为： L=M1+Dt （8） 其中： M1为直线上任意一点；D=n1×n2，n1为平面π1的单位法向向量。如图3中所示，根据三角形相似性，得： k=dV11/dV12=V11P1/V12P1 （9） 求得V11V12与直线L′的交点P1： P1=V11+k1+k（OV12-OV11） （10） 将P1代入式（8）可求得参数t，记作t1。同理可求得P2对应得的参数t2。对t1、 t2排序，使得t1 1.3三角形分割 对于求得的交线段L′=M1+Dt（m1≤t≤m2），其与T1的相对关系主要分为两类：一类是L′与T1的一条边重合，即L′是T1一条边的一部分或全部，称之为边相交；另一类是L′与T1的三条边都不重合，即L′除端点外，其他点都在T1内部（L′的端点可能在T1的顶点、边或内部），称之为面相交。图4列出了所有边相交的分类及分割方法；以图4（c）和图4（d）为例，L′的一端为T1的顶点，另一端在边V0V1上，则L′将原三角形分割为△V0PV2和△PV1V2两个三角形。由于篇幅所限，面相交的分类及分割方法不再列举，方法和边相交类似。
1.4三角形归类及布尔运算
在经过了三角形相交及分割操作之后，可以将所有的三角形按以下8个组合进行分类：实体A的三角形标记为 （on A）（in B）、（on A）（out B）、（on A）（on B Same）、（on A） （on B Opposite）；实体B的三角形标记为 （in A）（on B）、（out A）（on B）、（on A Same）（on B）、（on A Opposite） （on B）。其中：on表示元素所属关系；Same表示共面且法向相同；Opposite表示共面但法向相反。out表示什么
具体方法为：取实体A中某三角面中心Q为原点，沿三角形法线方向引射线n1，求出与实体B边界三角形相交中距离最近的一个三角形T2，设n1与T2交于O点，如图5。计算数量积C=n1·n2（n2为T2所在平面的法向量），当向量n1与n2同侧时，α<π/2，C>0，说明Q在实体B内部；当n1与n2不在同侧时，α>π/2，C<0，则Q在实体B外部。若α=0且距离为0，则两三角形同向共面（Same），若α=π且距离为0，则反向共面（Opposite）。
当实体A和实体B中的所有元素的拓扑关系都已经分类后，需要对其进行布尔运算以决定元素的取舍：按表1所示规则对实体A与实体B取布尔“并”运算。
（Thiessen region criterion）、最小内角最大准则（maxmin angle criterion）、圆准则（circle criterion）等[12]。本文结合平面方法，按以下方法进行了局部优化（对布尔运算后的实体进行）：
1）合并准重合顶点。准重合顶点是指距离小于阈值Tmin的两个节点，本系统中取Tmin=min（dij）/30，其中dij为布尔运算前顶点点集V{Vi，i=1～n}中顶点Vi到Vj的距离（i≠j； i，j=1～n）。合并方法：设准重合顶点为V1、V2，遍历所有三角形，如果V1、V2均为某三角形的顶点，则删除该三角形；如果该三角形只包含顶点V2，则用V1替换V2。
2）合并邻边共线三角形。如图6所示三角形△V1V2V3与△V1V3 V4有相邻边V1V3，且V2V3与V3V4共线，则称两三角形为邻边共线三角形，图中两三角形可以合并为新三角形△V1V2V4。三角形边共线的判定方法为（以图6为例）：V2V3×V4V3=0 或V2V1×V4V1=0。这种合并方法并不符合Delaunay三角形划分规则，只适用于边界元数值模型，不符合有限元的划分要求。
3）换边法。Lawson[13]提出的局部优化过程（Local Optimization Procedure， LOP）是保证生成网格质量很重要的手段之一。LOP方法利用圆准则保证两个相邻三角形所形成的四边形的最小内角最大：先判断两三角形是否共面，然后计算四边形两对角之和，如果大于π，则交换四边形两对角线。
2系统主要类图
系统通过Visual C++.net/OpenGL混合编程实现，主要类图如图7所示，主要类及属性方法说明：
Solid：实体类，记录了实体所有顶点坐标和每个三角形顶点的编号，以及实体的序列化（储存）和反序列化（读取）方法。
Vector：向量类，由（x，y，z）表示一个三维向量，类中定义了向量的运算法则、向量单位化等方法。
Vertex：顶点类，继承自Vector类，除了向量信息外，同时包含该点的位置分类和颜色等信息。
Face：三角面片类，包含三角形三个顶点、位置分类等属性，以及求三角面积、求交线等方法。
Line：直线类，由一个源点（point）和一个方向向量组成，同时定义了两条直线的相交算法。
Segment：线段类，由一条直线Line和参数t1、t2组成。t1、t2分别表示线段两端点到直线Line源点的距离，该类还包括线段相交检测、线段与面相交检测等方法。
Object3D：三维模型类，由Solid类生成的三维模型，主要用于布尔运算，通过顶点集和面片集表示一个三维实体，主要的方法有面片分割、面片位置分类、创建三维模型等。
BooleanModeller：布尔运算模型类，包括两个三维模型A、B，以及布尔运算方法。
3工程实例
日本串木野地下水封石油洞库位于南九州鹿儿岛西部，是日本国家石油储备地下水封石油洞库之一。地下水封石油洞库是在稳定的地下水位以下的岩层中开挖出的洞穴用来储油，利用地下水的静压力使少量水通过岩石裂隙渗入洞穴，以阻止洞内油气外泄。图8为两条隧道的透视图和一条隧道的内部轮廓图。
由于工程需要，在图8中两条隧道之间准备打通一条新的半圆拱隧道，以便进行油路互通。由于隧道内部网格划分复杂，不能利用参数形网格相交算法进行建模。采用本文所述方法完成TIN隧道相交算法，相交之后的效果见图9。
本文算法在双核CPU（3.0GHz）、8GB内存、GeForce 9800GT显卡的环境中测试运行。表2列出了本文算法与AABB和OBB层次包围盒算法的实验对比。
其中：生成耗时为构造包围盒的时间；检测耗时为巷道相交检测的时间；顶层检测准确率为通过顶层包围盒检测相交的三角形中真正相交者所占比例。从实验结果可以看出，本文算法在生成效率、检测效率及准确率方面较OBB层次包围盒算法均有所提高。
4结语
圆柱体AABB双层包围盒通过圆柱体和AABB两次包围盒检测，很大程度减少了三角形相交检测的时间，当两隧道相交面很小时，时间复杂度趋向于O（2n），适合巷道相交建模应用。但该算法在相交面积很大时时间复杂度增长过快，今后需进一步研究完善。
参考文献：
[1]
HUANG S. Research and implementation of irregular surface intersection algorithm [D]. Beijing： Beijing University of Chemical Technology， 2011： 1-10. （黄松柏.不规则曲面相交算法的研究与实现[D].北京：北京化工大学，2011：1-10.）
[2]
PALMER I J， GRIMSDALE R L. Collision detection for animation using spheretrees [J]. Computer Graphics Forum， 1995， 14（2）： 105-116.
[3]
van den BERGEN G. Efficient collision detection of complex deformable models using AABB trees [J]. Journal of Graphics Tools， 1997， 2（4）： 1-14.
[4]
GOTTSCHALK S， LIN M C， MANOCHA D. OBBtree： a hierarchrical structure for rapid interference detection [EB/OL]. [20150420]. http：//www.stanfordlibraries.info/class/cs273/refs/obb.pdf.
[5]
KLOSOWSKI J， HELD M， MITEHELL J， et al. Efficient collision detection using bounding volume hierarchies of KDOPs [J]. IEEE Transactions on Visualization and Computer Graphics， 1998， 4（1）： 21-37.
[6]
CHEN X， YANG L， HUANG W， et al. Method of Boolean operation based on 3D grid model [J]. Journal of Computer Applications， 2011， 31（6）： 1543-1545， 1584. （陈学工，杨兰，黄伟，等.三维网格模型的布尔运算方法[J].计算机应用，2011，31（6）：1543-1545，1584.）
[7]
LIU W， LI Z， LI S. Hybrid bounding volume hierarchies collision detection in teleoperation robot system [J]. Machine Building and Automation， 2014， 43（6）： 169-171，183. （刘文聪，李作清，李世其.面向遥操作机器人的混合层次包围盒碰撞检测[J].机械制造与自动化，2014，43（6）：169-171，183.）
[8]
TAO X， SHEN X. Study of realistic modeling and virtual assembly of aircraft in virtual library [J]. Journal of System Simulation， 2014， 26（12）： 2905-2913. （陶新权，沈旭昆.虚拟图书馆中飞行器逼真建模与虚拟装配研究[J].系统仿真学报，2014，26（12）： 2905-2913.）
[9]
FANG B， WANG Z， GUO X. Fourdimensional space and time hierarchical collision detection method based on AABB bounding box [J]. Computer Measurement and Control， 2014， 22（2）： 397-399， 420. （方彬，王竹林，郭希维.基于AABB的四维时空层次包围盒碰撞检测方法[J].计算机测量与控制，2014，22（2）： 397-399，420.）
[10]
MLLER T. A fast triangletriangle intersection test [J]. Journal of Graphics Tools， 2012， 2（2）： 25-30.
[11]
HELD M. ERIT — a collection of efficient and reliable intersection tests [J]. Journal of Graphics Tools， 2012， 2（4）： 25-44.
[12]
WANG Q， LI A， MA S. Research and implementing of method for optimization algorithm for longnarrow triangular mesh [J]. Modular Machine Tool and Automatic Manufacturing Technique， 2004（4）： 40-41. （王群，李爱平，马淑梅.狭长三角网格优化方法的研究及实现[J].组合机床与自动化加工技术，2004（4）： 40-41.）
[13]
LAWSON C L. Transforming triangulations [J]. Discrete Mathematics， 1972， 3（4）：365-372.
相关热词搜索： 圆柱体 巷道 建模 相交 包围