一种基于拓扑搜索的三角网求交算法

在地质构模以及各种地下工程设计等三维表达、分析领域,大规模的复杂三角形网的求交计算是三维表面模型建模的一个关键算法。根据三角形网中相邻三角形之间的拓扑邻接关系以及交线的连续性,提出了一种基于拓扑搜索的三角网求交算法。该算法引入空间辅助网格对原始三角网中的三角形进行筛选,并在候选三角形集合中依次追踪、计算构成交线的交线线段,在获得每个交线线段的同时完成了线段之间的连接。实验表明,该算法不仅效率高而且可靠性好。     

基于八叉树和混合搜索树的地质曲面快速求交方法

为处理地质界面之间的空间相交关系,提出一种新的针对三角地质曲面的快速求交方法。该方法融合优化八叉树法和OBB搜索树方法,可以更快速准确地剔除远离交线的其他三角形。求交剩余的三角形得到交线,应用三角网局部重构和网格优化算法修正交线附近的三角网,最终分割交线两侧的地质曲面,完成2个地质曲面的离散化求交过程。与AABB、OBB和空间分解法相比,该方法在大数据量三角曲面求交中效率优势明显,可以快速准确处理地质模型构建和分析中的曲面求交问题,为三维地质模型自动化构建的实现提供有效支撑。     

约束Delaunay三角网模型的插入约束线段算法浅析

在一次性构建约束Delaunay三角网算法构建的DEM模型基础上,研究并实现了快速、高效的插入约束线数据,从而达到对DEM模型进行局部动态修改的目的.     

基于空间索引与碰撞检测的TIN求交算法

针对三维矿床地质模型构建及后续应用分析中的需求,提出一种基于空间索引与碰撞检测的不规则三角网(TIN)快速求交算法。通过建立TIN模型的空间格网索引,将相交测试与计算限定在映射于同一个空间格网单元内的三角形对之间,在求交计算过程中,应用包围盒碰撞检测方法快速剔除不相交三角形对,并分别采用边-面及改进的边-边求交算法计算异面与共面三角形交线,并根据交线段之间的空间邻接关系完成交线的快速分离。实验及应用结果表明,该算法效率高、运行稳定、计算结果可靠,能够满足大规模TIN快速求交计算的需要。     

Delaunay三角网剖分的约束边嵌入改进算法

重点研究约束边强行嵌入D-三角网的问题。约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法,而CD-三角网才能真实地虚拟地形地貌。针对基于凸凹判定的对角线交换算法存在的缺陷,提出"分裂约束边"的思想完善算法的健壮性,并引入快速点定位算法以提高算法的执行效率。     

建筑物边界约束的航空影像DSM优化

针对航空影像密集匹配生成点云数据边界模糊的问题,提出了一种基于DSM灰度影像矢量边界与DEM无约束D-三角网嵌套生成具有精确边界的建筑物表面模型的方法。通过逐点内插法建立实验区点云数据的DSM深度影像图;根据计算机视觉中的边缘检测算子,提取深度影像中建筑物的准确边界;建立DEM的无约束D-三角网,将准确建筑物边界作为硬边界嵌入三角网中,最终将建筑物三角网和地面点三角网拼合,生成"纯净"建筑物表面模型。实验结果表明,优化后的建筑物高度和平面信息无精度损失,该方法有较强实用性。     

Delaunay三角网剖分中的约束边嵌入算法

约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法，而CD-三角网才能真实地虚拟地形地貌。该文研究了约束边嵌入D-三角网的问题，介绍了约束边嵌入算法的一些基本概念，分析了现存算法的特点，提出了改进的约束边嵌入算法——“插入－交换”算法。该算法能有效地处理各种特殊情况，程序实现简单，符合工程需求。     

对多面体造型中一种快速拼合运算的探讨

在多面体几何造型过程中，当拼合的体素位置处于特定情况下时，本文给出一种快速拼合运算方法──放并、放差拼合运算和阵列放并、放差拼合运算。给出了并、交、差和放并、放差运算的定义，并介绍了实现放并、放差拼合运算和阵列放并、放差拼合运算的算法流程。     

TIN快速求交算法及其应用研究*

煤矿床地表与地质层面模型通常采用TIN表示,交线作为层面模型交叉部分的特征描述,在模型构建及后续的应用分析中都具有十分重要的作用。根据基于层面模型编制露天煤矿采剥计划的需要,提出并实现了一种基于空间索引与碰撞检测的TIN快速求交算法,算法通过建立TIN空间格网索引,使相交测试仅限于映射在同一个空间格网单元内的三角形对之间,在计算交线时,进一步应用AABB包围盒碰撞检测技术快速剔除不相交三角形对,并分别采用“边—面”及改进的“边—边”求交算法计算异面与共面三角形交线,最后,根据交线段之间的空间邻接关系实现交线的快速分离。实验分析表明,算法整体时间效率较基于OBBTree的TIN求交算法高,并在露天煤矿采剥计划CAD软件系统中应用于计划线生成、运输道路设计、追踪等值线、切割剖面等设计实践,提高了在三维图形环境下采剥计划设计的精度与可靠性。     

三维网格模型的稳定布尔运算算法

给出一种稳定、高效的三维网格模型的布尔运算算法。该算法首先,基于网格模型原始的拓扑关系,结合层次包围盒相交检测实现网格模型相交区域快速定位;然后,采用改进的空间三角形求交算法求解离散交线段数据,并对单个三角形重新进行Delaunay三角剖分;最后,通过建立交线段与相交三角形间的拓扑关系对交线快速跟踪提取,通过局部区域快速分类组合,实现三角网格模型的精确布尔运算。该算法能有效地处理各种特殊情况且运行稳定;程序实现简单,实例证明符合工程需求。     

Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。     

基于快速Delaunay三角化的散乱点曲面重建算法

针对现有三维重建算法速度较慢的问题,提出了一种基于快速Delaunay三角化的散乱数据点的三维重建算法。首先,提出一种新的平面Delaunay三角化插入点目标三角形定位算法,利用插入点的方向搜索线与三角形是否相交以及交点个数加速目标三角形定位,不用额外判断点是否在三角形内;其次,自动检测曲面漏洞,利用凸壳的边界拼接方法进行漏洞弥补。实验结果表明,本算法不仅能较好地重建出三维模型,而且有较高的效率。     

约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法

在不允许改变原有点集的场合,实现约束Ｄｅｌａｕｎａｙ 三角剖分的一种有效算法是：将边界点与内点一起进行标准Ｄｅｌａｕｎａｙ 三角剖分,然后强行嵌入不在剖分中的约束边,最后删除域外三角形．其中,任意一条待嵌入约束边所经三角形构成的多边形区域称为该约束边的影响域,影响域内部的每条边称为对角线．文中对一般形状影响域中对角线的可交换性进行了研究,并在此基础上,结合对已有算法的分析和借鉴,提出并证明了两种强行嵌入约束边的多对角线交换算法,即递减算法与循环算法．其中的循环算法具有编程简单和运算速度快的特点     

基于近平面合并的三角网格简化算法

提出一种基于近平面合并的三角网格简化算法,针对三维重建MarchingCubes算法中产生的大量三角片进行简化。首先依据近平面判断条件将近似共面的三角形合并成一个大的多边形,然后按相应的准则将其重新进行三角化得到更少的三角形面片,以达到简化的目的。该算法在最大化的保留图像细节的前提下,精简了三角片的数目,提高了重建后图像绘制和传输的速率,节省了存储空间和处理时间。     

基于Delaunay三角划分策略的WSN区域覆盖优化研究

针对无线传感器网络在对初次抛洒节点形成的覆盖漏洞进行二次部署的过程中,传统几何学方法难以运用于概率感知模型的问题,提出一种基于Delaunay三角划分策略的无线传感器网络区域覆盖优化算法——DPSO算法。首先对监测区域内随机抛洒的静态节点和监测区域边缘顶点进行Delaunay三角划分,以得到静态节点三角网,结合无线传感器网络节点的概率感知模型证明三角形内部存在完全未覆盖区域即覆盖漏洞;其次将通过筛选得到的三角形形心集合作为粒子群优化算法的初始解集,利用改进的粒子群优化算法完成对移动节点的二次部署,以达到修复覆盖漏洞的目的。实验表明,所提出的基于Delaunay三角划分策略的优化算法能够有效修复覆盖漏洞,使区域覆盖率得到显著提高。     

基于最优凸壳技术的Delaunay三角剖分算法

提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序，利用最优凸壳技术进行凸壳的生成和三角网联结，最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试，而且使得新加入点与凸壳边的平均比较次数不大于4，从而实现了高效的三角剖分。     

Algorithm for constrained delaunay triangulation

A direct algorithm for computing constrained Delaunay triangulation in 2-D is presented. The algorithm inserts points along the constrained edges (break lines) to maintain the Delaunay criterion. Since many different insertions are possible, the algorithm computes only those that are on the Delaunay circles of each intersected triangle. A shelling procedure is applied to put triangles together in such a way that completeness and correctness are guaranteed.     

复杂地质体中多值面的网格生成算法

针对现有的网格生成算法无法处理在自然界中大量存在的多值面地质现象，基于分割－归并方法，提出一种分裂－重构算法。在生成初始约束Delaunay三角形网格之后，遵循连续折线的正负区测试准则，对网格中的局部顶点进行分裂，重构相关的三角形的点、边以及三角形的拓扑关系。实验表明，该算法能够有效地生成多值面的网格。     

三维网格模型的布尔运算方法

提出了一种基于三维网格模型的布尔运算方法。首先通过基于方向包围盒（OBB）层次包围盒树的碰撞检测算法,得到实体的相交三角形对;接下来求出两相交三角形之间的交线,建立与三角形的交线拓扑关系;通过分类处理三种交线类型来对相交三角形进行区域划分,得到一系列多边形,并对多边形进行三角剖分形成结果区域;最后根据体的包含关系构建关系邻接表,判断多边形区域的相对于其他实体的内外关系并通过网格模型的拓扑关系,定位表面三角网格区域;同时根据交、并、差等布尔操作,对结果区域进行取舍,得到最终结果。实验结果表明相交部分的岩性与实体的岩性相吻合,验证了该算法的正确性以及可行性。     

一个利用法矢的散乱点三角剖分算法

曲面上散乱点的三角剖分在曲面重建中发挥着重要作用,借助于曲面上的法矢信息和三维Delaunay三角剖分算法,该文给出了一种新的散乱点三角剖分算法,输入一组散乱点以及所在曲面S在这些散乱点处的一致定向的法矢信息,该算法将产生一张插值散乱点的三角网格曲面M,并且曲面M可以近似地看成是曲面S的三角剖分,算法的主要步骤分为两步：首先通过曲面S的一致定向的法矢信息,在曲面S的同一侧添加辅助点,利用这些辅助点来剔除Delaunay三角剖分中产生的不需要的三角片;然后将剩余的三角片连接成一张完整的网格曲面,与基于中轴的三角剖分算法相比,该文算法需要更少和更简单的计算,与局部三角剖分算法相比,该文算法可以更有效地避免重建后的曲面产生自交,该文的算法可用于任意拓扑的光滑曲面重建。