在机检测中三角网格拓扑重建方法的研究

对STL（Stereo Lithographic）模型中三角面片进行拓扑重建是解决在机检测系统中对零件模型表面进行曲面划分的前提条件之一。在建立点-边拓扑关系的基础上,将原有基于顶点坐标值浮点数比较的半边匹配结构转化为基于索引值的整型数匹配,并提出了基于关联-散列结构三角网格拓扑重建方法。该方法采用散列结构为辅助数据结构来减少STL模型顶点归并和边界归并的计算量,利用STL模型相邻网格单元数据相关性降低哈希函数的构建难度并提高冲突处理效率,在滤除冗余数据的同时完成拓扑关系的建立。计算实例验证了该算法的高效性和有效性。     

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

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

基于边长的三维形状插值

形状插值在计算机图形学和几何处理中是一个极其重要而基础的问题,在计算机动画等领域有 着广泛应用。注意到在平面三角网格和三维四面体网格插值问题中,对边长平方插值等价于对回拉度量进行插 值,因此具有等距扭曲和共形扭曲同时有界的良好性质。通过将其推广至曲面三角网格,提出了一种完全基于 边长的曲面三角网格插值算法。给定边长,在重建网格阶段,使用牛顿法对边长误差能量进行优化。并且给出 了其海森矩阵的解析正定化形式,从而避免了高代价的特征值分解步骤。注意到四面体网格的边长平方插值结 果具有极低曲率,意味着只需少许修改即可将其压平从而嵌入三维空间。因此提出先将曲面三角网格四面体化, 再从四面体网格的插值结果提取表面。然后将这表面作为初始化用于边长误差能量的牛顿迭代,从而使得收敛 结果更加接近全局最优。在一系列三角网格上进行了实验,结果说明了本文方法比之前方法的边长误差更小, 且得到的结果还是有界扭曲的。     

特征驱动的曲面重建

提出了基于散乱空间点集进行曲面重建的新方法,从点集的空间位置信息中提取待建曲面的内蕴特征量——法向和曲率,利用点集的这些特征信息来确定拓扑重建的搜索空间,采用面片生长的方式重建曲面。该方法在快速获得正确拓扑连接的同时,直接生成了用较少的面片就能保持曲面特征的优化网格。     

特征驱动的曲面重建*

提出了基于散乱空间点集进行曲面重建的新方法,从点集的空间位置信息中提取待建曲面的内蕴特征量——法向和曲率,利用点集的这些特征信息来确定拓扑重建的搜索空间,采用面片生长的方式重建曲面。该方法在快速获得正确拓扑连接的同时,直接生成了用较少的面片就能保持曲面特征的优化网格。     

一种点面混合的复杂三维模型加速绘制方法

在主流个人计算机硬件条件下，为加速百万以上三角面片构成的复杂稠密几何模型的绘制速度，综合基于几何的建模与绘制方法GBMR和基于点的建模与绘制方法PBMR的优点，提出了一种同时使用三角面片和点作为基本单元进行对象建模与绘制的点面混合方法．在预处理阶段，对模型表面进行网格分割，存储子块三角面片和顶点点云数据，同时对顶点点云按顶点重要度排序并序列化为线性结构．在实时绘制阶段，进行视相关的裁剪和背面剔除，不同子块按视点距离分别由三角形或点进行绘制．以上过程充分利用图形处理单元GPU，实现了基于GPU的点面混合的对象连续多分辨率绘制，有效地提高了复杂模型的绘制效率．     

基于Powell-Sabin细分的参数曲面重建方法

将复杂几何体网格转换为参数曲面是CAD几何引擎设计中的关键问题.针对赋予四边形粗剖分结构的三角网格模型,提出一种基于Powell-Sabin细分的参数曲面重建方法.首先利用均值参数化方法建立每个粗四边形结构M_T到参数域D的映射,同时得到D的三角剖分Δ;然后对Δ进行一次Powell-Sabin细分得到加细三角剖分Δ^S,并且利用M_T的几何信息构造二元一次样条函数空间S(Δ^S)中的插值函数S;对D均匀采样之后,利用插值函数S得到规则型值点作为参数曲面表面点的近似;最后建立具有光顺性质的能量函数,求解出双三次B样条曲面的控制点网格,完成曲面重建.实验给出了柱面、鞍面等基础曲面和人头模型等自由曲面的重建结果.数值结果表明,与自适应算法相比,所提方法能够捕获由给定三角网格呈现的几何细节,重建复杂模型的点距均方误差减小38%.     

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

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

海量点云曲面增量拓扑重建

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

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

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

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

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

A new approach to solid modeling with trivariate T-splines based on mesh optimization

We present a new method to construct a trivariate T-spline representation of complex genus-zero solids for the application of isogeometric analysis. The proposed technique only demands a surface triangulation of the solid as input data. The key of this method lies in obtaining a volumetric parameterization between the solid and the parametric domain, the unitary cube. To do that, an adaptive tetrahedral mesh of the parametric domain is isomorphically transformed onto the solid by applying a mesh untangling and smoothing procedure. The control points of the trivariate T-spline are calculated by imposing the interpolation conditions on points sited both on the inner and on the surface of the solid. The distribution of the interpolating points is adapted to the singularities of the domain in order to preserve the features of the surface triangulation.     

On surface reconstruction: A priority driven approach

To reconstruct an object surface from a set of surface points, a fast, practical, and efficient priority driven algorithm is presented. The key idea of the method is to consider the shape changes of an object at the boundary of the mesh growing area and to create a priority queue to the advancing front of the mesh area according to the changes. The mesh growing process is then driven by the priority queue for efficient surface reconstruction. New and practical triangulation criteria are also developed to support the priority driven strategy and to construct a new triangle at each step of mesh growing in real time. The quality and correctness of the created triangles will be guaranteed by the triangulation criteria and topological operations. The algorithm can reconstruct an object surface from unorganized surface points in a fast and reliable manner. Moreover, it can successfully construct the surface of the objects with complex geometry or topology. The efficiency and robustness of the proposed algorithm is validated by extensive experiments.     

Approximating digital 3D shapes by rational Gaussian surfaces

A method for approximating spherical topology digital shapes by rational Gaussian (RaG) surfaces is presented. Points in a shape are parametrized by approximating the shape with a triangular mesh, determining parameter coordinates at mesh vertices, and finding parameter coordinates at shape points from interpolation of parameter coordinates at mesh vertices. Knowing the locations and parameter coordinates of the shape points, the control points of a RaG surface are determined to approximate the shape with a required accuracy. The process starts from a small set of control points and gradually increases the control points until the error between the surface and the digital shape reduces to a required tolerance. Both triangulation and surface approximation proceed from coarse to fine. Therefore, the method is particularly suitable for multiresolution creation and transmission of digital shapes over the Internet. Application of the proposed method in editing of 3D shapes is demonstrated.     

A high quality interpolation method for colocated polyhedral/polygonal control volume methods

A high quality and efficient interpolation method for polyhedral/polygonal control volume simulation data is presented. The proposed method utilizes a non-ambiguous and efficient mesh decomposition technique. A pseudo-Laplacian is used to solve an optimization problem to approximate the variation between discrete data points in a linear fashion. The interpolation method guarantees continuous interpolation data throughout the control volume mesh topology and faithfully reproduces the input control volume data. The interpolation connectivity is structured to mimic the interpolation methods utilized by the control volume discretization. The method only requires the geometry of the input data to perform interpolations. This allows key interpolation data to be calculated once and stored for efficient interpolations. The benefits of the proposed algorithm are highlighted by an interpolation test case which demonstrates the benefits of the current method compared to a popular interpolation method currently used in industry. Since the proposed method is designed to augment an existing mesh data structure it can be used to update existing control volume software.     

基于矩形网格追踪法的曲面主曲率等值线生成算法*

针对自由曲面在展开平面上的主曲率等值线生成问题,提出一种基于矩形网格追踪算法的等值线生成算法。利用面积坐标方法将曲面上的点及其极值曲率映射到优化展开平面上,在展开平面上采用遍历法得出等值点序列;利用矩形网格追踪法将等值点序列划分为连续无交叉的开等值线或连续封闭的闭等值线。最后以直纹面、锥形面和自由曲面为算例分别对算法进行计算验证,并与线性插值三角网格法进行对比。计算结果表明,基于矩形网格追踪的等值线生成算法具有计算速度快、精度高的特点。     

The meccano method for isogeometric solid modeling and applications

We present a new method to construct a trivariate T-spline representation of complex solids for the application of isogeometric analysis. We take a genus-zero solid as a basis of our study, but at the end of the work we explain the way to generalize the results to any genus solids. The proposed technique only demands a surface triangulation of the solid as input data. The key of this method lies in obtaining a volumetric parameterization between the solid and the parametric domain, the unitary cube. To do that, an adaptive tetrahedral mesh of the parametric domain is isomorphically transformed onto the solid by applying a mesh untangling and smoothing procedure. The control points of the trivariate T-spline are calculated by imposing the interpolation conditions on points sited both on the inner and on the surface of the solid. The distribution of the interpolating points is adapted to the singularities of the domain to preserve the features of the surface triangulation. We present some results of the application of isogeometric analysis with T-splines to the resolution of Poisson equation in solids parameterized with this technique.     

复杂非均质地层的等值线生成算法研究

等值线图是复杂油气藏地质研究中的一类重要表示形式。针对地层数据特点,研究和分析了复杂非均质地层数据等值线绘制方法的不足,提出一种新的分区方法,实现了带断层的数据集合划分。基于Delaunay三角剖分算法,并以几何多边形为雏形,建立了带约束的三角网格模型。采用约束Delaunay三角网的拓扑结构,选用改进的反距离加权插值算法,有效地解决了断层两侧高程值问题,并结合实际应用要求在VC++与OpenSceneGraph的开发环境下,实现了非均质带断层的地层等值线的绘制。通过对国内某采油厂的实际油气储集地层数据等值线图的绘制和可视化,证明了方法的可行性和准确性。     

基于黎曼度量的复杂参数曲面有限元网格生成方法

给出了三维空间的黎曼度量和曲面自身的黎曼度量相结合的三维复杂参数曲面自适应网格生成的改进波前推进算法.详细阐述了曲面参数域上任意一点的黎曼度量的计算和插值方法;采用可细化的栅格作为背景网格,在降低了程序实现的难度的同时提高了网格生成的速度;提出按层推进和按最短边推进相结合的方法,在保证边界网格质量的同时,提高曲面内部网格的质量.三维自适应黎曼度量的引入,提高了算法剖分复杂曲面的自适应性.算例表明,该算法对复杂曲面能够生成高质量的网格,而且整个算法具有很好的时间特性和可靠性.     

任意三角形网格的基于二元四次箱样条分片C1曲面

提出一种以任意三角剖分为控制网格的二元箱样条曲面算法.二元三方向剖分是方向最少的三角剖分,建立在其上的二元三向四次箱样条在CAGD等领域有着广泛的应用.其规范的箱样条曲面计算仅适用于控制点的价数均为6的网格.从规范的算法出发,提出了一种任意价数控制网格的曲面计算算法,并对算法的连续性等进行了详细的分析.生成的曲面具有保凸性,且是分片C¹连续的.该算法可进行3D离散点全局或局部插值,并可应用于3D曲面重构等领域.