基于局部三维Delaunay的插值网格边界增量构造算法

网格构造的质量和效率是插值于大规模测量点三角网格构造算法的关键,但在算法中既保证插值网格的三维Delaunay性质又实现网格的线性构造仍存在困难。笔者针对此问题,提出了基于局部三维Delaunay的插值网格边界增量构造算法,利用网格的局部Delaunay构造及其边界的循环膨胀、分裂及自裁减操作实现整个模型的自动构造。应用实例表明,算法在保证构造网格满足三维Delaunay性质的同时,线性构造任意拓扑结构的三角网格模型。     

三角网格曲面模型的拟均匀细化算法

提出了一种无需计算曲面解析表示形式的三角网格曲面模型拟均匀细化算法.该算法首先将曲面体表面离散化得到初始网格;然后对初始网格进行区域标定,得到互斥子区域,藉此将空间网格曲面拟均匀细化问题转化为一系列的平面网格细化问题;其次再根据给定的网格细化间距对每个子区域进行拟均匀细化;最后对所有网格进行整体优化,从而实现了任意网格曲面模型的拟均匀细化.实验证明,提出的算法操作简单,效率高,细化后得到的网格质量高.     

二维任意域约束Delaunay三角化的实现

本文设计了一种逐点加入一局部换边法,提出并证明了二维约束边在约束Ｄｅｌａｕｎａｙ三角化中存在的条件,并据此用中点加点法实现了二维任意域的Ｄｅｌａｕｎａｙ三角剖分,生成的网格均符合Ｄｅｌａｕｎａｙ优化准则,网格的优化在网格生成过程中完成,算法复杂度与点数呈近似线性关系,给出了算法在平面域剖分和包含复杂断层的石油地质勘探散乱数据点集剖分的应用实例。     

点序对Delaunay三角剖分局部优化的影响

局部变换法和Watson算法是属于逐点添加、局部优化的离散点集Delaunay三角剖分的常用方法,不同的加点次序对这两种算法的局部优化影响较大。研究发现按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,点数大于50000时,相邻次序加点方法局部优化三角形的总量是随机次序加点方法的1.6倍以上。建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。     

面向大型复杂焊接结构仿真的组合式自适应四面体网格生成算法

目的 研究高质量、高效率的网格生成技术以实现大型复杂结构的焊接工艺仿真优化。方法 提出一种组合式的自适应四面体网格划分算法,即在高效生成各个零部件四面体网格的基础上,根据焊缝中心面的几何信息自动对焊缝附近网格进行细分,再缝合成高质量的大型复杂焊接结构的整体四面体网格,并集成到自主可控的商用网格划分软件Vision Mesh中。提出了摄动几何边界的方法,解决了大型复杂结构STL几何体在存在几何错误时网格难以生成的问题。提出了基于BVH树结构表达的背景网格表达方法,解决了多条焊缝同时高效、自动细分的难题,并通过“四面体分割–四面体合并–四面体翻转–点平滑优化”方法,实现了四面体网格的高质量优化。结果 算法网格效率可以达到200万个/h,生成的四面体99%以上均接近正四面体。可以由多个零部件一步组合生成大型结构的整体网格,并可对焊缝区域进行自动细分,大幅度简化了划分流程。将生成的网格导入国产焊接仿真软件InteWeld中进行测试,验证算法可用于大型复杂焊接结构整体应力变形的计算中。结论 实现了大型复杂焊接结构的高质量自适应四面体网格划分,使用简便操作得到了高质量网格,为焊接结构件工艺仿真优化...     

基于Voronoi最小邻近点集的Delaunay三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay三角化生成算法,该算法以Delaunay三角形及其对偶Voronoi图的局部性特征为基础,通过在局部搜索最小Voronoi邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用领域。     

三维点集Delaunay三角剖分的自动生成与修改算法

本文在已有算法的基础上，提出了一个三维点集Ｄｅｌａｕｎａｙ三角剖分的自动生成及其修改算法。自动生成算法对点在空间的位置没有任何限制，修改算法充分利用已完成的计算量，当动态增加或减少一点时，仅在局部进行适当的调整即可保证整体三角剖分符合Ｄｅ－ｌａｕｎａｙ性质。文中给出了算法正确性的证明。     

二维约束点集Delaunay三角剖分算法研究

在已有算法基础上，提出了任意二维约束点集Delaunay三角剖分的新算法，算法仅在局部产生少量新点，并在局部对三角剖分进行修改，便可保证整体三角剖分符合Delaunay性质。     

三角网格曲面的球面参数化

提出了一种球面参数化三角网格曲面的方法。结合平面凸参数化和球面参数化,计算出封闭网格的切割线边界,网格边界映射到球面的凸区域边界上。然后分别参数化各子网格,最后将三角网格内部点映射到球面上。并用实例验证了此方法的可行性和有效性。     

三重三角网格细分算法研究

标准的二值细分操作会在那些特殊顶点相关联处产生极大的曲率,这个缺陷可以通过对细分操作的特征值施加一个限定的曲率频谱来消除,但会扩大对那些超出了二价的顶点的支持.三重细分方案将网格的边一分为三,上述情况不会发生.该文中,作者推广了二阶连续的四次样条的三重细分到任意的三角形.该细分算法具有有界的曲率,并且被设计成能够维持凸包的属性.     

基于Delaunay三角剖分的层析图像离散数据表面重建算法

提出一种基于Delaunay三角剖分思想的层析图像离散数据的表面重建算法。该算法考虑了组成最优重建表面的三角片的形态特点,以三角片集的内角矢量最大为优化目标,根据Delaunay三角剖分思想,采用局部判定的方法,逐次选取最佳几何形态的三角片,组成最优的重建表面。     

应用等高线构建Delaunay三角网算法的研究与实现

部队的执勤和战斗行动都是在一定的地形条件下实施的,都要受到地形条件的影响和制约。基于等高线构建的Delaunay三角网可以很好的对数字高程模型(DET)进行表示,从而易于指挥员对地貌的识别和对地形进行分析。提出了一种基于等高线一次性构建Delaunay三角网的算法。相对于传统算法,该算法省去了嵌入等高线线段及定位点重新构网的时间。采用VC 6.0对该算法进行了编程与实现。     

一种利用Delaunay三角剖分的碰撞检测算法

虚拟现实中物体对象分布及运动情况呈现复杂多样,碰撞检测算法很难达到实时性和准确性的要求.提出了一种基于Delaunay三角剖分的多物体碰撞检测实时算法.该算法运用包围体紧密拟合物体对象,以包围体的中心构建离散数据点集,生成Delaunay三角网格,实施碰撞检测,避免层次包围盒和空间划分的不利因素,物体的更新等操作限定在局部的三角形内.实验表明在多物体的碰撞检测中,即使存在若干移动物体,算法能够满足实时性和准确性的要求.     

飞行器RCS计算中曲面剖分技术研究与实现

飞行器RCS预估计算是隐身技术研究中的重要研究内容。论述了利用飞行器外形的特点,在满足飞行器设计误差的前提下使用平面和柱面对飞行器的整机作NURBS曲面逼近,然后用柱面和平面剖分代替曲面的剖分。实现了飞行器整机模型的指定边长的三角剖分。这种方法不同于有限元计算的网格剖分,具有网格单元与曲面曲率无关和剖分速度快等特点。     

Efficient surface reconstruction from contours based on two‐dimensional Delaunay triangulation

This paper introduces an efficient method for surface reconstruction from sectional contours. The surface between neighbouring sections is reconstructed based on the consistent utilization of the two‐dimensional constrained Delaunay triangulation. The triangulation is used to extract the parametric domain and to solve the problems associated with correspondence, tiling and branching in a general framework. Natural distance interpolations are performed in order to complete the mapping of the added intermediate points. Surface smoothing and remeshing are conducted to optimize the initial surface triangulations. Several examples are presented to demonstrate the effectiveness and efficiency of the proposed approach. Copyright © 2005 John Wiley & Sons, Ltd.     

3D boundary recovery by constrained Delaunay tetrahedralization

Three‐dimensional boundary recovery is a fundamental problem in mesh generation. In this paper, we propose a practical algorithm for solving this problem. Our algorithm is based on the construction of a constrained Delaunay tetrahedralization (CDT) for a set of constraints (segments and facets). The algorithm adds additional points (so‐called Steiner points) on segments only. The Steiner points are chosen in such a way that the resulting subsegments are Delaunay and their lengths are not unnecessarily short. It is theoretically guaranteed that the facets can be recovered without using Steiner points. The complexity of this algorithm is analyzed. The proposed algorithm has been implemented. Its performance is reported through various application examples. Copyright © 2010 John Wiley & Sons, Ltd.     

Boundary recovery after 3D Delaunay tetrahedralization without adding extra nodes

In this paper, we investigate boundary recovery, the problem that has troubled researchers ever since Delaunay-based methods were applied to generate mesh. There are a number of algorithms for boundary recovery already and most of them depend heavily on adding extra nodes. In this paper, we make an effort to seek a method to recover boundaries without using extra nodes. It was noted that some previous algorithms imposed artificial boundary constraints on a meshing problem at the recovering stage; we first try to discard these artificial constraints and thus make things easier. Then a new method is proposed by which the boundaries can be recovered by means of two operations: (1) creating a segment in the mesh and (2) removing a segment from the mesh. Both operations are special cases of a general local transformation called small polyhedron reconnection operation. The method works well when coupled with the sphere-packing method proposed by the first author. If the mesh sizing function is suitable, a good configuration of nodes will be created accordingly by the sphere-packing method and the boundary can be recovered by the local transformation presented here without inserting extra nodes. Copyright © 2007 John Wiley & Sons, Ltd.     

Variational surface reconstruction based on Delaunay triangulation and graph cut

A novel method for surface reconstruction from an unorganized point set is presented. An energy functional based on a weighted minimal surface model is proposed for surface reconstruction, which is efficiently minimized by graph cut methods. By solving the minimization problem on the graph dual to a Delaunay‐based tetrahedral mesh, the advantages of explicit and implicit methods for surface reconstruction are well integrated. A triangular surface mesh homeomorphic to the original surface can be extracted directly from the tetrahedral mesh provided a sufficient sampling density exists. Difficult cases involving undersampling, non‐uniformity, noises and topological complexities can be handled effectively as well. Furthermore, for the first time, multi‐phase surface reconstruction is realized based on the graph cut methods. Various examples are included for demonstrating the efficiency and effectiveness of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.