多边形三角剖分与三角细分的研究与实现

多边形是构成三维模型表面的基本元素,多边形的三角剖分及三角形的三角细分是计算机三维快速建模及纹理帖图的基本技术。本文在研究平面多边形的三角剖分及其三角网格化相关理论的基础上,利用面向对象技术及递归程序设计方法,实现多边形的三角剖分及其三角细分的算法设计,并对该算法的执行效率进行分析。实验结果表明,该算法具有较高的运算效率及实用价值,对实际应用有较好的参考作用。     

一个通用的快速三角化算法

提出了一个适用于任意平面多边形区域及散乱点集的通用三角化算法。当算法应用于多边形区域时,首先对各个顶点和区域内部的散乱点按扫描方式排序,然后依次扫描各点,扩展生成新的三角形,从而获得局部已剖分区域,并最终完成整个区域的三角化。将上述过程作适当改动后,可被用于平面散乱点集的三角网格化,该通用算法除了具有快速三角化的特点之外,还采用局部域的优化组合来体现最优化准则,因此算法更具有可操作性和实用性。     

简单多边形三角剖分的一种快速算法及应用

提出了一种内角动态判定的简单多边形三角剖分算法,该算法的思想是对多边形相邻三角点构成的内角进行动态判断,如果小于180度且组成的三角形是否包含其它点,则连成三角形,并设计了有利于算法快速实现的数据结构.算法思路简单,易于编程实现,且剖分速度快,最后用该算法应用于地层模型的剖面生成.     

求解简单多边形间最小距离的一个线性时间算法

计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题。为了更快地求解简单多边形的最小距离,提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法。该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包围框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形。为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置。该算法的时间复杂度是线性的。     

简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。     

凹多边形的矢量-三角形法自动识别与剖分

凹多边形的三角剖分及其后续填充处理，在计算机图形学及地学问题三维建模领域有着广泛地应用，文中在总结已有的凹多边形识别技术基础上，提出矢量－三角形法。利用矢量－三角形法，先定位凹多边形凹点，再判断其为单域凹多边形还是自相关凹多边形，然后采用构造以凸点为顶点的三角形并层剥去的方法，有效地实现了凹多边形的三角剖分及其后续填充处理。     

简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分，在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上，提出了一种时间复杂度为O（mn）的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优，并进行了理论上的严格证明，对算法的时间复杂度进行了分析，并给出了一个实例。实验结果表明，该方法对于随机生成的简单多边形域三角化速度快，平均计算时间呈近似线性。     

基于贪心算法与多边形剖分的印鉴匹配算法

将计算几何中平面点集的三角剖分方法之一贪心算法与多边形三角剖分方法引入印鉴匹配,研究了一种基于三角网格(用贪心算法进行平面点集的三角剖分)的印鉴匹配方法.用贪心算法对基于线条的细节点集进行三角剖分,而对于基于多边形的细节点直接进行多边形的三角剖分.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行三角划分,把空间上位置相近的细节点按照一定的规则相连,得到三角形网格.然后基于该网格寻找若干参考点对,并根据获得的参考点对将两幅印鉴图像进行姿势调整.最后使用获得的参考点时实现基于点模式的印鉴匹配,经分析该方法是一种行之有效的印鉴识别方法.     

多连通多边形三角化找桥算法的研究及实现

已有的多边形三角化剖分算法,对多连通任意多边形的处理方法不一,算法大多复杂,可靠性低,而且往往只适合于特定的多边形剖分。本文结合现有的多边形三角剖分算法,提出了一个简洁高效、高可靠性的多连通任意多边形三角化剖分的找桥算法,该算法可用于各种多连通任意多边形的三角化剖分处理,并且成功运用于本单位研制开发的城市三维数码景观系统中,收到了较好的效果。     

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

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

一种基于特征点识别的曲线离散化方法

提出了曲线局部特征点的概念，并根据平行线原理给出了一种快速求取特征点的算法。通过对局部特征点进行优化，得到所需的局部特征点集，实现了曲线的离散。该方法在离散过程中充分考虑了离散精度误差与逼近弦长对后续三角化质量的影响。实验结果表明，由这些特征点组成的多边形可较好地逼近曲线，算法效率较高。     

基于三角形骨架坐标的图象渐变算法

为快速进行不规则多边形区域内的数字图象渐变处理,提出了一种基于三角形骨架坐标的图象渐变算法,即先将图象区域分割为若干个三角形区域,再逐个对这些三角形区域建立象素点的骨架坐标,这样三角形骨架外壳的改变就会带动其内部图象的渐变,并根据骨架坐标变换,推导三角形区域内象素点坐标随外壳三角形顶点改变的计算公式,进而建立了骨架外壳改变后的新象素点与原始象素点间的颜色对应关系。利用该不规则多边形区域内的图象渐变算法,可解决运动模拟等常见图象的变形问题。     

基于斯坦纳树和泰森多边形的连通恢复算法

针对无线传感器网络容易遭受恶劣环境破坏，连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题，提出基于斯坦纳树和泰森多边形的连通恢复算法（CRAST）。首先，将被分割的节点分区抽象为离散点，枚举出离散点区域内的所有非退化四边形，再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。然后，用关键节点构建Delaunay三角网，通过Delaunay三角网构建出整个无线传感器网络的泰森多边形拓扑结构。最后，在泰森多边形所有顶点部署可移动的备用中继节点，在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点，移动备用中继节点替换损坏的关键节点。整个算法能使传感器网络以最少的代价实现连通恢复，并且拥有较强的高效性和健壮性。     

映射相关边概念的多边形内外点判别算法

提出映射相关边、密切边的概念，将点在多边形内外的判别转化为点与密切边关系的判别．通过X方向的一次映射快速求取判别点的相关边，对相关边的二次映射可得到判别点的密切边．证明了根据密切边的矢量方向就可以判别点在多边形内外．在运算效率上对射线法进行改进，当多边形的边数较多时，更能体现文中算法优越性．     

Optimality and competitiveness of exploring polygons by mobile robots

A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot “sees” (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics.We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point.     

曲线插值约束的LOOP细分曲面

提出基于Loop细分方法的曲线插值方法,不需要修改细分规则,只需以插值曲线的控制多边形为中心多边形,向其两侧构造对称三角网格带,该对称三角网格带将收敛于插值曲线。因此,包含有该三角网格带的多面体网格的极限曲面将经过插值曲线。若要插值多条相交曲线只需在交点处构造全对称三角网格。运用该方法可在三角网格生成的细分曲面中插值多达六条的相交曲线。     

多分辨率三维建筑群建模与实时绘制技术

将纹理特征分析技术引入到多边形网格建模中,提出一种基于高程特征值进行曲面细分的算法以构建多分辨率虚拟建筑群模型。该算法给出一种三角边与纹理特征曲线相交的三角面分裂方法构造自适应细分三角网格。通过设计细分三角网格的二叉树数据结构和开发测试程序进行测试,表明该算法具有自适应网格速度快和保持几何特征较好的特点,可以满足在PC机上实现三维建筑群的大范围建模和实时交互显示要求。     

Polygon Laplacian Made Simple

The discrete Laplace-Beltrami operator for surface meshes is a fundamental building block for many (if not most) geometry processing algorithms. While Laplacians on triangle meshes have been researched intensively, yielding the cotangent discretization as the de-facto standard, the case of general polygon meshes has received much less attention. We present a discretization of the Laplace operator which is consistent with its expression as the composition of divergence and gradient operators, and is applicable to general polygon meshes, including meshes with non-convex, and even non-planar, faces. By virtually inserting a carefully placed point we implicitly refine each polygon into a triangle fan, but then hide the refinement within the matrix assembly. The resulting operator generalizes the cotangent Laplacian, inherits its advantages, and is empirically shown to be on par or even better than the recent polygon Laplacian of Alexa and Wardetzky [AW11] — while being simpler to compute.     

曲率约束的隐式曲面三角网格化

提出一种有效的隐式曲面三角网格化算法。从隐式曲面上的一个种子点开始,生成网格的边界作为扩张多边形,且该多边形最小角对应的顶点为扩张点,计算从扩张点处欲生成的三角网格,为了防止新生成的三角网格和已经存在的三角网格重叠,要进行冲突检测。在隐式曲面三角网格化的过程中,扩张多边形是不断变化的,需要重复上述步骤,直至没有扩张多边形时结束。该算法分别应用于解析隐式曲面和变分隐式曲面的三角网格化。实验结果表明,该算法不需要重新网格化的步骤,生成的三角网格具有较高的质量,且三角网格随曲率适应性变化,因此说明了该算法的有效性。