Improved Partition Algorithm between Triangulated Irregular Network
-
摘要: 三角网切割是实现三维地质建模和模型分析的关键算法, 它的效率直接决定了建模算法的效率.通过建立三角网的方向包围盒(oriented bounding box, OBB) 树实现曲面间的碰撞检测, 然后对发生相交的三角形对统一计算交点, 通过对顶点坐标归一化完成曲面切割后的快速重构, 并针对不同的曲面类型采用不同的切割分类方法进行2侧切割结果的划分.阐述了算法的实现过程并展示了切割后的图形效果.Abstract: The partition algorithms between triangulated irregular network are key algorithms for building and analyzing 3D geology models. Their efficiency determines the model building efficiency. To improve the algorithm, this paper first realizes collision detection by building OBB (oriented-bounding box) trees, and then calculates the intersection points of cutting triangle pairs. Through normalizing the vertex coordinates, the algorithm provides a method for the rapid reconstruction of the geology model. The algorithm uses different partition methods based on different partition types. This paper gives a detailed description of the algorithm's process and demonstrates a cut effect of triangulated irregular network.
-
Key words:
- TIN /
- intesection /
- OBBT /
- normalization /
- partition /
- projection
-
不规则三角网(TIN) 是通过从不规则分布的数据点生成连续三角面来逼近真实实体的表面.在复杂的地质模型中, 断层与断层、断层与地层之间经常会发生相交关系, 断层面将地层面分割成不同的三维曲面.为了更为真实地反映出地下空间的地层和断层的分布情况, 建立准确的地下三维地质结构模型, 利用不规则三角网(TIN) 来模拟断层面和地层面, 采用不规则三角网格曲面之间的切割算法来计算切割后新的曲面模型.国外的许多地质软件都已开发出自己的切割算法, 如石油地质软件gocad开发了使用地质约束引入了相交计算算法和光线追踪算法(Lindenbeck, 2002), 来实现三维地质模型建模前的切割.笔者综合运用OBB树生成、碰撞检测、Delaunay三角化和空间数据归一化等算法, 给出了一个不规则三角网格曲面之间的切割算法, 并对算法的一些细节进行了改进, 提高了曲面切割的效率.
1. 数据准备
不规则曲面切割需要具有拓扑关系的不规则三角网数据, 笔者的实验曲面是利用钻孔的地层数据和断层数据, 经过GIS软件MAPGIS的不规则三角网TIN生成模块得到.为了减少存储空间, TIN采用顶点索引模式, 即采用三角形的顶点坐标和顶点编号分开存储的方法, 顶点坐标统一存储, 不允许出现重复点, 顶点索引表示每个三角形使用的顶点编号(Tomas, 1997).
2. 不规则三角网格曲面的切割
2.1 算法基本思想
切割算法主要包括3个方面: 切割前的碰撞检测、相交三角形对的求交运算和切割后的处理. (1) 碰撞检测即判断被切割面与切割面中的哪些三角形发生相交, 即确定2个曲面的所有相交三角形对; (2) 相交三角形对的求交运算是为了完成曲面网格的切割, 反映到单个图元上, 就是计算三角形与三角形的交点; (3) 切割后的处理包括2个方面: 一是完成切割后的三角网重构; 二是完成曲面切割后的2边网格的重新划分, 即三角网分边.
不规则三角网的切割示意如图 1所示, 其中垂直方向上的面表示被切割面, 水平方向上的面表示切割面, 被切割面被一分为二, 并保留切割面下方的部分.
2.2 算法步骤
首先根据碰撞检测算法, 确定2个三角网中发生切割的三角形对, 逐一对这些三角形对进行求交运算, 计算它们的交点.然后去除重复的交点, 并将所有的点(包括顶点和交点) 归一化到[0, 1]范围的二位平面上, 对网格进行重新三角化, 计算出曲面之间的切割交线.最后根据设定的分边条件, 将三角化后的被切割面一分为二.具体步骤如下:
(1) 三角网与三角网之间的三维碰撞检测.2个三角网曲面之间位置关系判断是进行三角网切割的关键.通过对2个曲面中的每个三角形求交来判断是否发生碰撞, 速度太慢.而通过碰撞检测算法则可以大大提高算法效率.常见的碰撞检测算法有很多, 如轴向方向包围盒法(AABB)、包围球法(sphere)、二叉树BSP法、固定方向凸包的包围盒(FDH) 法和方向包围盒法(OBB) 等.综合考虑算法的效率和可扩展性, 笔者采用了方向包围盒法(OBB), 对三角网曲面建立方向包围盒, 形成树, 利用树来判断三角形之间的切割关系.
方向包围盒(oriented bounding box, OBB) 的基本描述参数包括: 原点ori (oriX, oriY, oriZ)、方向dir (dirX, dirY, dirZ) 和大小siz (sizX, sizY, sizZ).OBB树(OBB tree, OBBT) 是利用OBB建立的树结构.OBBT建立的过程: 首先建立整个曲面的OBB, 然后将其分解成2个OBB, 并将这2个节点作为该节点的孩子节点, 以此类推, 直到它的最小单元是不可再分割的OBB, 即只含有一个三角形的OBB.OBBT是一种特殊的二叉树(图 2).
OBB树的建立过程如图 3所示.对2个三角网曲面分别建立OBBT后, 即可对其进行碰撞检测, 确定二者发生相交的三角形对.
对于相交三角形对tp (tr11, tr12), 其中, 三角形tr1属于曲面surf1, 三角形tr2属于曲面surf2.笔者通过对被切割曲面和切割曲面建立方向包围盒树OBBT来确定相交三角形对.建立OBBT的方法, 判断2个曲面的OBBT是否发生碰撞的流程(图 4) 经过OBBT进行碰撞检测后, 2个曲面的相交三角形对就可以快速确定下来.
(2) 曲面的切割计算(图 5).三角网格曲面切割的最小计算单位是三角形与三角形之间的位置关系计算.根据OBBT确定的三角形对(tp1, tp2, …, tpn), 求出每个三角形对的交点.这些交点可以确定2个曲面之间的交线.在Paul (1998) 提到了一种简单的计算三角形之间的交点的算法.即先拿tr2的3条边和tr1平面相交, 再拿tr1的3条边和tr2平面相交.这样对每个三角形对需要作6 (3+3=6) 个直线与平面的相交测试操作.只有在三角面内的交点才保留, 其余的要舍去, 并且保证重复的交点只记录一次.
由于判断交点是否重复, 需要指定一个阈值.而不同的曲面数据, 阈值的大小是不一样的.因此这种方法的精度不能满足要求, 而且计算效率低. 笔者对上述方法进行了改进: 根据Tomas (1997)提出的方法, 快速判断发生碰撞的三角形对是否相交, 再根据已经确定发生相交的边, 计算出相应的交点.同时, 算法的速度也有所提高(丁永祥等, 1994).
所有三角形切割完成后, 可以得到求交运算产生的交点.交点的排序是通过三角形的邻接关系来实现.通过将这些交点进行排序, 就可以计算出曲面切割产生的相交线, 相交线可能是连续的一条, 也可能是不连续的多条.在三维地质建模中, 断层面与地层面之间的交线可以用来表示地层与断层的界限.
(3) 切割后的三角剖分.切割后的曲面, 由于内部增加了许多交点, 需要重新进行三角剖分, 才能满足TIN网格的要求.为了利用Delaunay三角剖分法则(杨杰, 2000), 采用参数化算法, 将顶点坐标经过归一化来实现切割后曲面的重构.即将曲面上的点变换到某一个曲面上, 使得在该曲面上, 顶点的z坐标值是唯一的, 并且顶点的(x, y, z) 坐标值都在(0, 1) 区间内.最简单的三角剖分方法是求交一个三角形对, 重新三角化一个区域.这样算法表述简单, 但效率很低.笔者先计算出所有的切割线交点, 再将被切割曲面上的所有点(包括原始点和交点) 重新进行三角化.三角化时, 需要引进原始曲面的边界和2条曲面之间的交线作为约束条件.
(4) 切割后的网格分边.一个曲面被另一个曲面切割, 被分为2部分, 准确确定2部分曲面是完成切割算法的最后关键一步.常用的空间点分边算法有: 曲线分边法、平面分边法、曲面分边法和多面体分边法等.这些分边算法不能一概而论, 判断方法主要是由切割面的类型决定的. (a) 如果切割面是平面网格, 可以采用平面分边法判断.即采用空间点与平面的位置关系判断算法, 用计算点到平面的有向距离来判断; (b) 如果切割面是任意曲面, 可以采用空间点与曲面的位置关系判断算法.方法是从测试点向曲面发出一条射线, 统计射线与曲面交点的个数的奇偶性: 为奇数, 表示在切割面的一侧; 为偶数, 表示在另一侧; (c) 如果切割面是多面体网格, 可以采用点与多面体的位置关系判断算法.方法是从测试点向多面体发出射线, 找出离测试点最近的三角形, 计算出此三角形的法向与射线方向的点积, 为正, 表示在多面体内; 为负, 表示在多面体外. (d) 如果切割面在水平面上的投影是一条折线或者闭合曲线, 这可以通过点与曲线的位置关系来判断. (e) 如果被切割面是具有完整拓扑信息的曲面, 则在切割完成后, 可根据邻接三角形, 找出切割面一侧的所有三角形, 剩下的是切割面另一侧的三角形, 这种方法速度最快, 但对数据的拓扑性要求很高.
判断切割后三角形的方位时, 不需要计算出三角形的每个顶点相对于切割面的方位, 只需要计算出三角形中的任意一点比如说重心点即可.因为经过切割后形成的不规则三角网, 每个三角形只可能属于切割面的一侧, 故可以用一个点代替整个三角面进行判断(图 5).
3. 算法的数据结构与测试效果
3.1 数据结构
这里主要列举3个数据结构: 三角网中顶点结构、三角网结构、相交三角形对结构和单条交线信息结构.每个结构的基本定义如下:
typedef struct {// 三角网中顶点结构
double fDem X, fDemY, fDemZ; // 点的X、Y、Z值
shortw Code; // 地性特征
}TinPntStrcT;
typedef struct {/ / 三角网结构
long lVerTex 1, lVe rTex2, lVer Tex3;// 三角形三顶点序号(按逆时针)
long lTriNo1, lTriN o2, lTriNo3;// 三角形三边对应的三角形序号
}TinNetStrcT; // 三角形序号是其在三角形表中的序号
typedef struct {//相交三角形对结构
long lTri1;//第一个面的三角形号
long lTri2;//第二个面的三角形号
}TriCutPair;
typedef struct CutLinInfo {//单条交线信息结构
long *plLinPntNo; //交线的顶点序号
long lPntNum; //本交线的顶点数目
}CutLinInfo.
3.2 测试结果
笔者利用钻孔数据建立三维地层模型, 并在模型上画一条剖面线, 形成切割面(图 6).为了效果逼真, 三维地层模型的顶部可贴上遥感影像, 并以实体加上光照方式显示.
4. 算法改进
在三维地质建模与地下隧道剖面等应用中, 不规则三角网格曲面相当复杂, 且数据量大, 所以切割算法的效率直接影响了三维建模的效率.笔者在实际的应用中, 在实施算法的每一步细节中, 都进行了一定的改进.具体表现在:
(1) 三角网的碰撞检测算法采用建OBB树的方法进行判断(Gottschalk and Lin, 1996), 在三角形对进行求交运算前, 首先对三角形进行碰撞检测, 再根据记录的碰撞信息进行交点计算, 比普通直接利用线段与三角形求交的算法效率大大提高.
(2) 切割后网格的三角化: 切割后网格存在多Z值, 简单方法是在单个三角形内进行手工三角化, 这样效率很低(任建波, 2005).本文先将曲面上所有点的坐标参数化到不含多Z值的三维曲面上, 再利用Denaulay三角化算法进行一次性三角剖分.Denaulay算法可以设置约束线, 并且生成三角网的质量好, 速度快.这样既提高了三角化的速度, 又改善了三角化后网格的质量.
(3) 针对切割面的不同性质, 因地制宜, 采用不同的算法对被切割后的曲面进行分边.
-
[1] Ding, Y. X., Xia, J. C., Wang, Y., et al., 1994. Arbitrary polygon delaunay triangulation. Joural of Computer, 17 (4): 270 -275 (in Chinese with English abstract). [2] Gottschalk, S. G., Lin, M., 1996. OBB tree: A hierarchical structure for rapid interference. ACM Siggraph' 96, [s. n. ]. 171 -180. [3] Lindenbeck, C. H., 2002. A program to clip triangle meshes using the rapid and triangle libraries and the visualization toolkit. Computers & Geosciences, 28: 841 -850. [4] Paul, B., 1989. Intersection point of two lines (2 dimensions). http://local.wasp.uwa.edu.au. [5] Ren, J. B., 2005. Irregular triangulation based on plane polygon. Journal of Gansu Sciences, 17 (1): 65 -68 (in Chi-nese with English abstract). [6] Tomas, M., 1997. A fast triangle-triangle intersection test. Journal of Graphics Tools, 2 (2): 1 -5. doi: 10.1080/10867651.1997.10487470 [7] Yang, J., 2000. Simple polygon triangulation based on scraggy vertex determinant. Minitype Computer System, 21 (9): 974 -975 (in Chinese with English abstract). [8] 丁永祥, 夏巨谌, 王英, 等, 1994. 任意多边形的Delaunay三角剖分. 计算机学报, 17 (4): 270 -275. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX404.004.htm [9] 任建波, 2005. 基于平面多边形的不规则三角网分割. 甘肃科学学报, 17 (1): 65 -68. doi: 10.3969/j.issn.1004-0366.2005.01.018 [10] 杨杰, 2000. 基于凸凹顶点判定的简单多边形的三角剖分. 小型微型计算机系统, 21 (9): 974 -975. doi: 10.3969/j.issn.1000-1220.2000.09.022 -
下载:
下载:
点击查看大图
计量
- 文章访问数: 144
- HTML全文浏览量: 50
- PDF下载量: 3
- 被引次数: 0
