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

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

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

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

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

基于Delaunay三角化的噪声点云非均匀采样

针对基于Delaunay三角化曲面重建方法要求点云密度满足ε-sample条件,提出了一种基于Delaunay三角化的噪声点云非均匀采样算法。首先,利用k-邻近点的Voronoi顶点计算出各点的负极点来逼近曲面中轴(MA);然后,根据近似中轴估计出曲面局部特征尺度(LFS);最后,结合Bound Cocone算法,删除多余的非边界点。实例表明,该算法可以准确、稳健地简化噪声点云,同时可以很好地保留曲面边界特征,经简化后的点云适用于基于Delaunay三角化的曲面重建方法。     

基于局部修复的移动数据点Delaunay三角化快速更新方法

在移动数据点Delaunay三角化更新问题中,采用双三角单元过滤算法能够检测出大部分连接关系未发生改变的双三角单元结构,当在算法中出现反转三角单元时,需要重新计算所有数据点的Delaunay三角化.基于以上问题,提出一种具有局部修复的双三角单元过滤算法,通过在局部区域检查三角单元反转并进行修复,避免对所有数据点进行重新...     

边界保持的隐式曲面三角化方法

隐式曲面三角化是隐式曲面绘制的常用算法.对于开区域上散乱点数据重建的隐式曲面,常用的隐式曲面三角化方法得到网格模型不能很好地保持散乱点数据的边界.针对该问题,提出了一种边界保持的隐式曲面三角化方法.根据散乱点数据的空间分布,控制等值面的抽取范围,实现了边界保持.实验结果表明,该算法能够产生和散乱点数据边界一致的三角网格.     

点云的形状与曲线重建算法

针对平面无序带噪点云的曲线重建问题,给出了点云形状的定义并提出了构造点云形状的算法.该算法基于Delaunay三角剖分,在构造好点云的Delaunay三角剖分后对三角剖分进行细化,使得在点云中的点周围形成空间上的局部均匀采样;基于集合论中的基本概念定义点云中内点、外点和边界点,并且明确地定义了点云的形状,根据Delaunay三角剖分细化时,选择不同的参数得到不同层次的点云的形状;选择合适的参数得到相应形状后,通过薄化过程得到具有流形结构的曲线.实验结果表明,采用文中算法得到的重建曲线很好地反映了点云的形状,验证了该算法的有效性.     

基于EMST的平面点集Delaunay三角剖分

提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率.     

海量点云曲面增量拓扑重建EI北大核心CSCD

针对现有的曲面重建算法难以兼顾大规模采样数据的重建效率与重建曲面拓扑正确性的问题,提出一种基于局部Delaunay网格剖分的曲面增量重建算法.该算法采用波前扩展的策略,通过波前环的扩张、分裂、重叠面片的消除等步骤,将局部重建过程传播至每个样点的邻近区域,获得插值于采样点集的二维定向流形网格曲面,实现整个采样点集的增量拓扑重建;在曲面局部重建过程中,分别基于局部区域的Cocone算法与二维投影点集的Delaunay网格剖分方法重建曲面的尖锐区域与平坦区域,其中局部区域重建曲面网格的边界的正确性由区域之外的少量辅助样点保护.实验结果表明,文中算法具有较高的重建效率,适用于封闭和非封闭海量点云数据的重建;且在采样密度符合要求的情况下,重建的网格曲面与原表面拓扑同构.     

一种基于映射法的散乱点云Delaunay三角剖分算法

针对直接在三维空间构建海量点云的Delaunay三角网格效率低下,提出一种新的基于映射法的Delau-nay三角网格构建算法.首先提出一种基于区域增长法的点云分片方法,能够保证对分片后的点云数据进行映射而不产生重叠;然后保持空间点云之间的距离特性,将三维点云映射到二维平面;在二维平面内进行Delaunay三角剖分,再将结果返回到三维空间内.实验结果表明,算法能够构建质量较好的三角网格.由于该算法将点云的三角剖分转换到低维空间,通过实验结果对比本算法与其他算法效果,证明该方法能够更快地完成重构.     

基于曲面局平特性的散乱数据拓扑重建算法

提出了一种基于曲面局平特性的,以散乱点集及其密度指标作为输入,以三角形分片线性曲面作为输出的拓扑重建算法.算法利用曲面的局平特性,从散乱点集三维Delaunay三角剖分的邻域结构中完成每个样点周围的局部拓扑重建,并从局部重建的并集中删除不相容的三角形,最终得到一个二维流形拓扑曲面集作为重建结果.该算法适应于包括单侧曲面在内的任意不自交的拓扑曲面集,并且重建结果是相对优化的曲面三角形剖分,可以应用于科学计算可视化、雕塑曲面造型和反求工程等领域.     

Delaunay三角网构建方法比较研究

Delaunay三角网构建是3维场景可视化领域的一个热点也是难点问题。归纳总结了现有Delaunay三角网构建研究中的3类方法——逐点插入法、三角网生长法和分治法,以及在各自原理框架下的不同实现算法;比较分析了3种不同方法的优缺点和各自代表性算法的时间复杂度,并详细讨论了Delaunay三角网构建方法在大规模场景渲染和地形可视化领域中未来3个研究方向：混合算法研究、算法支撑技术研究和分布式并行算法研究。     

Delaunay meshing of isosurfaces

We present an isosurface meshing algorithm, DelIso, based on the Delaunay refinement paradigm. This paradigm has been successfully applied to mesh a variety of domains with guarantees for topology, geometry, mesh gradedness, and triangle shape. A restricted Delaunay triangulation, dual of the intersection between the surface and the three-dimensional Voronoi diagram, is often the main ingredient in Delaunay refinement. Computing and storing three-dimensional Voronoi/Delaunay diagrams become bottlenecks for Delaunay refinement techniques since isosurface computations generally have large input datasets and output meshes. A highlight of our algorithm is that we find a simple way to recover the restricted Delaunay triangulation of the surface without computing the full 3D structure. We employ techniques for efficient ray tracing of isosurfaces to generate surface sample points, and demonstrate the effectiveness of our implementation using a variety of volume datasets.     

面向并行的动态增量式Delaunay三角剖分算法

三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究，提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分，然后再根据对偶特性构建Voronoi图．该算法健壮性很高，适用于处理各种非完全共面三维点集．     

An almost distribution-independent incremental Delaunay triangulation algorithm

This paper presents a new incremental insertion algorithm for constructing a Delaunay triangulation. Firstly, the nearest point is found in order to speed up the location of a triangle containing a currently inserted point. A hash table and 1–3 deterministic skip lists, combined with a walking strategy, are used for this task. The obtained algorithm is compared with the most popular Delaunay triangulation algorithms. The algorithm has the following attractive features: it is fast and practically independent of the distribution of input points, it is not memory demanding, and it is numerically stable and easy to implement.     

平面域上离散点的三角化实现

简单回顾了生成Delaunay三角网的分治算法，逐点插入法，三角网生长法等三类主流算法，提出了一种基于逐点插入思想的快速，有效的分区逐点插入三角化算法，实现了平面域上离散数据点的三角化，网络的优化是在网格生成过程中完成的，生成的网格符合Delaunay准。     

Anisotropic surface meshing with conformal embedding

This paper introduces a parameterization-based approach for anisotropic surface meshing. Given an input surface equipped with an arbitrary Riemannian metric, this method generates a metric-adapted mesh with user-specified number of vertices. In the proposed method, the edge length of the input surface is directly adjusted according to the given Riemannian metric at first. Then the adjusted surface is conformally embedded into a parametric 2D domain and a weighted Centroidal Voronoi Tessellation and its dual Delaunay triangulation are computed on the parametric domain. Finally the generated Delaunay triangulation can be mapped from the parametric domain to the original space, and the triangulation exhibits the desired anisotropic property. We compute the high-quality remeshing results for surfaces with different types of topologies and compare our method with several state-of-the-art approaches in anisotropic surface meshing by using the standard measurement criteria.