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

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

一种快速三维散乱点云的三角剖分算法

改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领域推广使用。     

一种散乱点云空间直接剖分算法

散乱点云的三角剖分在曲面重建中发挥着重要作用。在对三角剖分基本方法深入分析的基础上对此类点云提出了一种高效的重构算法。本算法将基于动态球策略的搜索算法引入到曲面重建中,源于增量式计算的思想,结合约束准则和设计的顶点度量函数,从基础三角面片开始扩展到覆盖整个物体表面。分析及实验结果表明,该算法能有效地对点云数据进行三角网格化,同时剖分后的三角网格曲面最大限度地保持了原有曲面的特性,证明了提出的基于动态球的曲面重构算法应用于散乱点云曲面重构问题的可行性。     

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

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

散乱点云的快速增量网格重建算法

散乱数据的网格重建是数字几何处理的基础性技术之一.本文提出一种快速增量式散乱点云网格重建算法,运用波前( Wave Front)方法渐进地由点云数据生成物体表面的网格模型.该算法以一个”种子”三角形初始化搜索队列,以逐渐生成的新边为搜索元素,借助Kd-树空间划分技术和搜索约束条件,快速完成优化点的评估及三角面片重建,可在保证网格质量的同时,过滤部分对重建效果意义不大的点.实验表明,该算法能够高效、可靠地生成具有不同几何复杂度的原始曲面二维流形三角网格逼近,适用于海量数据点的网格重建.     

散乱点云的三角划分算法研究

通过对当前的三角网格划分方法进行比较分析,提出了一种散乱点云的3D三角网格划分算法。该算法不需如同二维划分方法那样要对散乱点云对应的自由曲面分片投影,而是直接在3D空间,根据离散点集所对应的曲面形态变化,利用网格扩展、边界环分裂和边界环封闭,逐层收缩生成三角网格。该算法能方便地处理空间多种曲面的散乱点云数据,并且生成的三角网格形态优良,布局合理。     

基于三维重建技术的三角剖分

在分析已有算法的基础上,利用增量法与分治法相结合的思想,实现了直接对空间散乱点的三角剖分.通过对空间散乱点的三角剖分,最终得到满足所要重建物体的三角网格模型,且网格非常均匀,该模型直观、清晰地再现了实体模型.实验证明了算法的可行性.     

一种基于点云数据的快速曲面重构方法

研究激光扫描中的点云数据重构技术,提出一种基于规则点云数据的快速曲面重构方法。分析相邻扫描线之间数据点的相对位置关系,在三角剖分的基础上,设计改进的扫描线剖分算法,根据激光逐行扫描的特点,对点云数据进行不规则三角网格划分,利用几何关系进行配对构网,并在所建三角模型的基础上实现三角网格的局部优化和纹理映射,得到重建模型。实验结果表明,与传统Delaunay空间三角剖分算法相比,该算法可明显提高三角构网速度和质量,消除空洞,改善重建效果。     

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

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

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

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

大规模离散点集Delaunay三角剖分加点策略的分析

局部变换法和Watson算法是离散点集Delaunay三角剖分的常用算法,算法过程中逐点添加、局部优化是三角网格生成速度的重要影响因素.按位置相邻次序逐点添加时易产生外接圆较大的扁平三角形,引起较大范围的局部优化,三角网格的生成速度下降.在位置相邻次序的点集中随机选择部分点生成相对匀称的初始三角网格,再依次添加数据点,可有效减少局部优化消耗的时间,提高三角网格的生成速度.以激光扫描测量数据为例,切分为不同数量的点集进行三角剖分测试,当数据点数大于20000点时,采用部分随机点优化策略,其三角剖分速度比直接按位置相邻次序添加的方法提高一倍以上,且数据量越大,效率越高.     

Feature aligned quad dominant remeshing using iterative local updates

In this paper we present a new algorithm which turns an unstructured triangle mesh into a quad dominant mesh with edges well aligned to the principal directions of the underlying surface. Instead of computing a globally smooth parameterization or integrating curvature lines along a tangent vector field, we simply apply an iterative relaxation scheme which incrementally aligns the mesh edges to the principal directions. We further obtain the quad dominant mesh by dropping the not-aligned diagonal edges from the triangle mesh. A post-processing stage is introduced to further improve the results. The major advantage of our algorithm is its conceptual simplicity since it is merely based on elementary mesh operations such as edge collapse, flip, and split. Various results are presented in the paper; they show a good alignment to surface features and rather uniform distribution of mesh vertices. This makes them well suited, e.g., as Catmull-Clark Subdivision control meshes.     

A reliable triangular mesh intersection algorithm and its application in geological modelling

We introduce a reliable intersection algorithm for manifold surface meshes. The proposed algorithm builds conforming surface meshes from a set of intersecting triangulated surfaces. This algorithm effectively handles all degenerate triangle–triangle intersection cases. The key idea of the algorithm is based on an extensive set of triangle–edge intersection cases, combined with an intersection curve tracking method. The intersection operations do not rely on global spatial search operations and no remeshing steps are needed. The intersection curves are introduced into each surface mesh using a unique curve imprinting algorithm. The imprinting algorithm naturally handles degenerate intersection cases of many surfaces at an edge or at a point. The algorithm produces a consistent mesh data structure for subsequent mesh optimization operations. The mesh intersection algorithm is used within a general framework for modelling and meshing of geological formations, which are essential for reliable mathematical modelling of oil reservoirs.     

基于灰度分布的图像三角网格化算法

借助于小波图像分解,提出一种基于图像内容的三角网格表示方法——基于双向模板的图像三角网格化算法.算法考虑图像的灰度分布,利用小波的图像分解能够将图像的各个方向的细节表现出来这一特性,给出符合原始图像灰度分布的三角划分,再对图像的三角划分进行三角网格化,最后获取整幅图像的网格划分.为了得到更好的重建图像质量,对该初始网格进行了细分,并针对三角网格规模的减小做出优化算法.同时提出一种记录模板号和细分点的数据存储结构,用二进制数据流来存储三角网格.通过实验数据对比,该算法能够很好的表示图像,在三角网格规模以及重建图像质量上较其它算法都有一定的优势,是一种极其有效的图像表示方法.     

基于控制点误差控制的网格简化算法

提出了一种基于控制点误差控制的网格简化算法，以初始网格三角形的中心点作为第一类控制点，以特征边的顶点作为第二类控制点，控制点与受控三角形之间的距离作为简化误差。根据设定的三角形权重，按照顺序进行三角形折叠操作，简化操作后必须满足控制点到受控三角形的距离小于阈值。     

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

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

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.     

动态调节圆半径曲面重建算法的改进

为实现对散乱数据点划分三角形网格的曲面重建,克服实体表面存在阶跃边缘而难以确定圆半径的问题,改进用动态调节圆半径产生三角形网格并实现曲面重建的算法,将散乱数据点转化为二维图像数据,并进行三角形网格划分.实验结果表明,虽然改进算法效率有所下降,但对表面存在阶跃边缘的实体有较好的重建效果.     

一种基于八叉剖分的近似曲率的边折叠简化算法*

为了提高三角网格模型简化的速度,满足实时显示的要求,并且有效地克服边折叠简化算法在低分辨率的状态下易丢失模型重要几何特征的问题,提出了一种基于八叉剖分的近似曲率的边折叠简化算法。采用八叉树结构自适应地分割网格模型空间,同时在各个区域中采用近似曲率的边折叠算法并行地进行边折叠操作。实验证明,该算法取得了不错的效果。     

基于三角网下的仿射不变几何约束的图像匹配算法研究

针对当前图像匹配方法在进行图像匹配时,主要通过度量特征向量之间的距离来完成图像匹配,导致算法鲁棒性差、误配率较高及效率较低等不足,本文提出了基于三角网下的仿射不变几何约束的图像匹配算法。首先,在尺度空间上通过Hessian矩阵对特征点进行检测,利用子块的三角特征与对角特征对SUR机制进行改进,用以生成新的特征描述子,并通过定义阀值评估策略,对图像特征点匹配,从而生成了初始匹配点;然后,引入 三角网,对初始匹配点进行聚类,以获取匹配三角形,将三角形以外的无效特征点剔除。最后,引入仿射不变几何约束,对匹配三角形进行细化,通过细化的匹配三角形获取最终的匹配特征点,有效剔除误配点,进一步提高配准精度。仿真结果表明,与当前图像匹配算法相比,本文算法具有更好的鲁棒性,且其具有更佳的匹配精度与效率,有效剔除了误配点。