平面域中散乱点的Delaunay三角化算法

基于三角网生长算法和分治算法的思想,提出并实现了一个平面域散乱点的三角网格重构算法.算法首先利用分治算法的思想将散乱点集进行分割,然后在四个极值点确定初始三角形的基础上,基于边的扩展原则构造新的三角形,使网格不断向周围扩展直到所有的待扩展的边全部能构成三角形为止,最终构造出整个散乱点集的三角网格.     

由区域生长算法实现四边形网格划分

针对当前各种三角形网格转化为四边形网格算法的缺陷，提出一种实现这种转化的算法——区域生长算法．该算法通过有选择地合并三角形来获得高质量的四边形网格，并且对两个三角形的合并增加约束条件以避免在生成四边形网格的过程中产生残余三角形；同时对生成的四边形网格进行一系列的质量改善操作。     

一种改进的区域扩张三角网格面逆向重构算法

三角网格面重构是逆向工程中常用的曲面重构方法之一．本文提出了一种基于局部信息的区域扩张算法（LIBRG），用以解决由离散点云重构三角网格面的问题．该算法由一个初始三角片开始，扩张式地搜索满足要求的点以生成新的三角片．算法充分利用了区域扩张过程中的局部空间信息，所以能很好地适应曲率的变化并自动筛选掉一些无效点；同时LIBRG算法也针对传统算法中的全程遍历搜索方式进行了改进，以获得较高的时间效率．     

基于重新划分的三角形网格简化的一种改进算法

基于重新划分的三角形网格简化方法能自动生成多细节层次模型，它的基本思想是:根据三角形网格的局部几何和拓扑特征将一定数量的点分布到原网格上,生成一个中间网格,移去中间网格中的老顶点,并对产生的多边形区域进行局部三角化,最后形成以新点为顶点的三角形网格.本文在已有算法的基础上,提出了一种分布新点的算法,从而克服了原有方法的局限性.它利用三角形顶点的曲率和三角形的面积两个因素来反映网格在每个三角形处的特征.文中给出的一组实例说明了算法的有效性.     

基于能量评估的网格简化算法及其应用

网格简化是曲面重构和多细节层次构造中的一个重要步骤，本文提出了一个基于局部能量评估的网格简化算法，能够大量地删除密集网格的三角形面片．为了加速算法的执行还提出了一种简单有效的采样方法．算法自动化程度高，能有效地支持多细节层次模型的建立．     

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

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

一种基于多区域并行的网格模型简化的两步法

针对三角形网格模型简化中保持细节特征的要求,引入了图像的区域分割原理,提出了一种基于区域生长的网格模型区域分割方法．在此基础之上,提出了一种基于多区域并行的自适应三角网格模型简化的两步法,对于不同的区域采取按照比例进行简化的并行机制．此方法的特点是保持模型细节的基础上,大大地加快了模型的简化速度．另外,还提出了一种基于多区域并行的累进网格模型的实现方法,有效地实现了保持细节特征的多分辨率模型,并实现了具有细节特征的多分辨模型间的层次过渡．经实验证明,该方法能够快速有效地对三角形网格模型进行简化,并具有保持模型的三角形网格密度分布的特点．     

散乱点云的三角网格重构

基于增量扩散法的思想,提出并实现了一个散乱点云的三角网格重构算法,算法首先利用体素网格的散列表对散乱点进行组织,然后在确定了初始种子三角形的基础上,基于活动边扩展规则构造新的三角形,使网格不断向周围扩展直到活动边表空为止,最后算法合并棱边并计算每个三角形的顶点法矢,最终构造出散乱点云的三角网格。     

点云重构三角网格的生长型神经气算法

为克服点云噪声、不均匀分布和复杂拓扑结构对三角网格重构的限制,改进了生长型神经气重构算法.以样本在网格局部投影作为神经元插入判据,自适应调节网格增长速度,保持几何变换与拓扑变换的协调.利用非流形边检测机制删除冗余连接,保持网格的拓扑有效性.网络学习过程中动态更新三角片结构,且在孔洞修复阶段扩大近邻查找范围,连接近邻节点中的边界点,直到网格收敛,最终得到正确的欧拉示性数.算例表明,改进的算法对带噪声点云具有鲁棒性,可根据非均匀点云的分布自动调整网格密度,且能重构具有复杂拓扑结构的曲面.重构的三角网格对曲面逼近精度较高,网格出度均匀,三角形近似等边.     

结合Delaunay 三角面分离法与搜索球策略的三维曲面重建算法

基于曲面重建在计算机图形学、三维GIS、逆向工程等领域有重要应用,结合区 域生长法与Delaunay 三角剖分的优势,提出了一种新的散乱点云曲面重建算法。首先根据曲面 中轴性质提出了分离角定义并推导了相关结论,利用局部Delaunay 三角形分离角性质抽取大量 位于模型表面三角形,从而构建种子三角网增加初始区域的生长面积其次运用自适应搜索球法 加快邻域三角形搜索并识别曲面边界。对比传统的基于Delaunay 法和传统区域生长法,该方法 只需要一次三角剖分,无需极点与法向量计算,重建速度快,具有Delaunay 三角网格的优良结 构特性,孔洞数量少,重建出的三维模型几何信息与拓扑关系准确。实验表明,结合Delaunay 三角剖分与区域生长法重构有向的流形三角网格模型,能够提高三维模型的重建效果与速度, 有效地自动识别曲面边界。     

基于点邻域平坦度的网格重构算法

提出一种对散乱数据点进行网格重构的区域扩张算法．首先计算每个点的邻域平坦度,并在平坦区域构造一个种子三角面片;然后优先选取落在平坦区域的活动边进行扩张,并在扩张过程中引入平坦趋势作为最佳点选择的准则;最后通过后续处理构造出二维流形网格．实验结果表明,该算法能充分利用点邻域的平坦信息减少拓扑和几何错误发生的概率,较好地保持实体模型的尖锐特征．     

基于调制度信息的网格重构算法

提出一种基于调制度的网格重构算法,首先对调制度进行等级量化,在调制度高的区域构造种子三角面片;然后优先选取测点调制度高的活动边进行增长,依据加权最小长度准则选择最佳候选点;在径向基函数孔洞修补之前根据三角面片几何属性对孔洞边界进行预处理.实验结果表明,该算法对平坦和高曲率区域都能有效地重构出形态比较均匀的二维流形网格,较好地保持了模型的细节尖锐特征.     

图像中任意三角形检测方法

提出了一种基于加窗Hough变化的任意三角形检测方法。选择适当大小窗口在图像中滑动,以窗口中心为坐标原点对窗口内图像作Hough变换,在图像的Hough域中检测直线段,从检测出的直线段中找出满足三角形条件的线段组合,然后定位这些线段构成的三角形。实验表明该算法能够有效检测出任意三角形,改变线段的长度条件或角度条件还可以检测直角三角形、等腰三角形、等边三角形等特殊三角形。该算法还可以实现在图像中检索三角形目标的功能。     

A mesh reconstruction algorithm driven by an intrinsic property of a point cloud

This paper presents an algorithm for reconstructing a triangle mesh surface from a given point cloud. Starting with a seed triangle, the algorithm grows a partially reconstructed triangle mesh by selecting a new point based on an intrinsic property of the point cloud, namely, the sampling uniformity degree. The reconstructed mesh is essentially an approximate minimum-weight triangulation to the point cloud constrained to be on a two-dimensional manifold. Thus, the reconstructed surface has only small topological difference from the surface of the sampled object. Topological correct reconstruction can be guaranteed by adding a post-processing step.     

一种基于边指针搜索及区域划分的三角剖分算法

针对大规模数据处理时Delaunay三角剖分过于耗时的问题,本文提出了一种基于边指针搜索及区域划分的三角剖分算法.基于边指针设计了一种能够反映三角形之间位置关系的数据结构,并优化了目标三角形的搜索路径.基于该数据结构,利用区域划分进一步降低目标三角形的搜索深度.超级三角形所在的正方形被划分成具有相同尺寸的区域,目标三角...     

基于Delaunay三角网的等值线绘制算法*

提出了一种快速构建Delaunay三角网算法（QGDTN）。在每次迭代中,该算法从点集P最左边的两点中,选取离凸边中点距离最近的一点与凸边构成Delaunay三角形,并加入三角网中,算法实现简单,且时间复杂度为O(n)。基于Delaunay三角网,根据三角形的各边上是否有等值点,用内插值法求出等值点坐标,跟踪、连接等值点生成等值线;最后,采用三次方Bezier曲线平滑等值线。实验证明,基于Delaunay三角网的等值线绘制算法是高效的,并且具有一定的实用价值。     

基于形状信息的三角形交通标志检测方法

提出一种基于快速辐射对称性和Hough变换的三角形交通标志检测方法。利用快速辐射对称性检测三角形的内心,在内心处设置一个窗口对窗口内图像作Hough变换,在图像的Hough域中检测三角形交通标志。实验结果表明,该算法能有效弥补现有同类算法的缺陷,具有较高的检测效率。     

An efficient and robust contact algorithm for a compliant contact force model between bodies of complex geometry

Dynamic analysis of many mechanical systems often involves contacts among rigid bodies. When calculating the contact force with a compliant contact force model, a penetration depth and a contact reference frame (a contact point and normal and tangent directions) should be determined from the geometrical information of the rigid body surfaces. In order to improve the speed and robustness of the contact analysis, this paper proposes a contact search algorithm for surfaces composed of triangles. This algorithm is divided into two parts, the pre-search and the detailed search. In the pre-search, a bounding box tree and an overlap test are used to find intersecting triangle pairs, and triangle connectivity information is used to identify and separate multiple contact regions. Then an efficient and robust detailed search algorithm is proposed, where the penetration depth and contact reference frame are determined from the results of the pre-search. Finally, the contact force for each contact region is calculated from a modified compliant contact force model. Numerical examples are also presented to illustrate the accuracy and performance.     

摄影测量中一种非编码点的自动匹配方法

在极限约束法基础上提出了一种非编码点匹配的改进算法,首先采用极限约束法得到候选匹配对应点,然后按编码点位置将图像Delaunay三角化,缩小匹配范用。在对应Delaunay三角形内确定匹配点,若在三角形范围内仍不能唯一的确定匹配点,则通过交比不变性来实现对应点的匹配。本方法不限制标志点的粘贴位置,满足摄影测量中实际应用要求。     

WSN中基于最小信号强度和的APIT定位算法

针对传统APIT算法存在边界效应的问题,提出了一种基于最小信号强度和的新的三角形内点测试算法NAPIT。该算法首先在锚节点组成的三角形中找到一点,使得该点收到三个锚节点的信号强度之和最小;然后将最小值作为阈值来判定有效三角形;最后利用网格扫描算法来确定未知节点的坐标位置。仿真结果表明,NAPIT算法能够在一定程度上减少In-To-Out Error和Out-To-In Error的发生次数,有效提高了节点定位精度,并且很大程度地提升了节点定位覆盖率。