改进的三角网格表面近似测地线算法

三角网格表面的测地线计算问题可转化为三角网格表面两点间的最短路径计算问题,为了快速地计算三角网格表面测地线,提出一种基于缩小最短路径搜索区域的三角网格表面近似测地线算法。将三角网格沿坐标系三坐标轴方向进行空间单元划分,使用A*算法求出两点间的最短路径盒子序列,进而得到新的搜索区域,计算三角网格上两点间的最短路径,迭代细分最短路径邻域内的边以构造新的网格求解测地线。实验结果表明,该算法能够快速准确地计算出三角网格表面任意两点间的近似测地线,有效解决大型三角网格上最短路径计算速度慢的问题,计算速度较改进前的算法提高了10倍~59倍。将该算法应用到虚拟肝脏手术系统的区域标定中,可满足虚拟场景中对计算实时性和效果真实性的要求。     

点云模型上近似测地线的计算

为了有效计算点云模型上任意两点间的近似测地线,将点云模型沿着直角坐标系中三坐标轴方向进行空间栅格划分后,建立表示点云模型的带权图,采用Dijkstra算法计算带权图上任意给定两点间的最短路径作为初始测地线;然后通过使能量函数最小化,用共轭梯度方法对初始测地线迭代优化,计算得到点云模型上任意给定两点间的近似测地线。该算法无需对点云模型进行网格化,无需对点云模型进行局部或全局的曲面重建,适合大规模点云模型上测地线的计算。     

三角网格模型上任意两点间的近似最短路径算法研究

提出一种任意三角网格模型上两点间的近似最短路径算法．该算法首先将三角网格模型表示为带权图结构，然后用Dijkstra算法计算带权图中两顶点间的最短路径，并将其作为网格模型上该两点间最短路径的初始近似．通过不断地迭代对相关三角形边进行自适应细分，并构造每次细分后新的带权图，从而对网格模型上的两点间最短路径进行迭代逼近．该算法效率高，可以很好地控制精度，适用于大型三角网格模型两点间最短路径寻找．文中还讨论了该算法在任意三角网格模型区域划分中的应用．     

曲面上任意两点的近似最短路径算法研究

为了提高曲面上任意两点间近似最短路径的计算效率,提出了求解曲面上任意两点间近似最短路径的算法,该算法首先利用三角形网格模型表示曲面,并形成相应的带权图结构,然后采用FSPA(快速最短路径法)动态计算带权图上两点的最短路径,再通过迭代细分最短路径周围的三角形网格上的边,最后由这些边构造新的子图来不断逼近曲面上两点间的最短路径。为验证该算法效果,还给出了该算法两个应用实例。应用结果表明,该算法效率高,容易实现,并可用网格尺寸和细分参数γ来控制近似精度。     

三角网格表面任意两点间并行近似测地线算法

为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销,提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径,并用源分割法映射子网格数据;所有处理器并行执行,对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作;最后基于局部细化后的细分图并行,求得所有点对间的近似测地线长度和路径。实验结果表明,该并行近似测地线算法能够有效降低求解该类问题的计算时间,计算效率大大提高。     

三角网格表面近似测地线的计算

为了有效地计算三角网格表面任意两点间的近似测地线,将三角网格模型表示成带权图,计算带权图上两点间的最短路径,并迭代细分最短路径邻域内的边以构造新的带权图求解.改进了细分顶点的生成策略,提出了邻域扩展的方法,提高了迭代运算速度,有效地解决了迭代细分算法容易陷入局部最优的问题;并把测地线距离应用于径向基函数,实现了一种曲面变形算法.实验表明该算法达到了较好的效果.     

热测地场控制的近似刚性网格变形技术

为保持三维模型局部细节,修正近似刚性网格变形算法(ARAP)应用于大尺度以及 非完全刚性变形中出现的扭曲、翻折问题,提出了一种基于测地场约束的近似刚性变形方法。 首先对模型进行 Laplacian 变形,并通过奇异值分解求得局部单位的旋转矩阵,计算模型刚性变 形能量;然后通过求解稀疏线性系统,更新变形点,再通过求解两次稀疏线性系统,计算变形 过程中产生的测地场偏差,并修正变形网格,得到与原始网格测地场接近的变形结果;反复迭 代上述步骤,直到热测地场偏差满足一定要求,获得最终变形结果。结果表明,该方法能在网 格变形过程中快速地完成网格点修正功能,在应用于大尺度变形中也能有效地避免网格出现翻 折问题。     

任意姿态虚拟人网格模型骨骼提取算法

人体骨骼动画技术是虚拟人物建模中的研究重点。在现有人体骨骼动画的制作过程中,动画师必需手工标定人体各主要关节点位置及人体骨架每一关键帧的姿态,工作量巨大。因此提出一种自动提取人体任意姿态网格模型骨架结构的方法。该方法首先利用模型各顶点间测地距离的几何关系自动识别人体位于四肢和头顶末端的5个特征点,再以特征点为起点生成等测地距离曲线族,利用等测地距离曲线将人体四肢和躯干区分开来,将这些相邻等测地线中心连接起来生成5条骨骼中心线,最后在中心线上根据中心夹角极小值及等测地距离曲线似圆率来确定人体关节的确切位置。实验结果表明,该算法能适应不同姿态的人体模型,计算结果准确性高,能完全自动实现关节点定位和骨骼提取。     

测地切割磨光曲线的生成

提出任意拓扑网格模型上离散测地线算法和测地切割磨光曲线算法,研究测地切割磨光曲线的重要性质.通过实例表明,所提出的两个算法正确、稳定、快速且容易实现,具有较好仿真效果.     

一种基于改进地貌形状上下文的形状匹配方法

在基于地貌形状上下文的形状匹配方法中,计算地貌空间测地距离消耗时间较高,对应形状特征提取过程的效率较低.针对这一问题,本文提出了一种基于地貌模糊形状上下文的快速形状匹配方法.在形状特征提取过程中,通过引入最短路径算法对轮廓采样点间的测地距离进行快速计算.在此基础上结合对数极坐标模糊直方图构造地貌模糊形状上下文,其能够更好地描述轮廓点分布情况进而有效提升形状描述符的表达能力.考虑到轮廓点集顺序已知,进一步引入动态规划分析不同地貌空间下形状片段间的对应关系,以获取准确的形状匹配结果.通过对不同的数据集进行实验仿真分析,验证了本文方法能够有效地提升运算效率并取得较好形状检索精度.     

Iso-scallop tool path planning for triangular mesh surfaces in multi-axis machining

Triangular mesh enables the flexible construction of complex surface geometry and has become a general representation of 3D objects in computer graphics. However, the creation of a tool path with constant residual scallop height on triangular mesh surfaces in multi-axis machining is not a convenient task for current algorithms. In this study, an isoscallop tool path planning method for triangular mesh surfaces, in which the tool path is derived directly from the contours of a normalized geodesic distance field (GDF), without any post-processing is proposed. First, the GDF is built to determine the shortest geodesic distance from each vertex to the mesh boundary. Then, the normalizing process is performed on the GDF to ensure that its first contour meets the isoscallop height requirement considering the mesh curvature and effective cutter radius. To improve the computational efficiency, the GDF is only built in the mesh area related to the first contour by specifying a stop distance. Moreover, an adaptive refinement process is conducted on the mesh to improve the smoothness and accuracy of the tool path. Finally, the triangular mesh is trimmed along this first contour for a new round of tool path planning. The proposed method is organized recursively and terminated when no new paths are generated. Simulations and experiments are conducted to verify the effectiveness and superiority of the proposed tool path planning method.     

基于测地路径的牙齿模型交互分割算法研究

从3维牙颌模型中精确地分离出单颗牙齿是计算机辅助正畸治疗的重要步骤。由于牙齿有不同的形状并且不同个体之间有很大差异,其自动分离比较困难。为此,提出一种交互分割单颗牙齿的方法：首先,在牙颌模型上交互选定特征点,然后计算特征点间近似测地路径,待测地路径封闭后,利用区域生长方法从整个牙颌模型上精确分离出单颗牙齿。实验结果显示,该算法执行速度快,用户交互量少,且分割得到的牙齿边界线平滑,较好地满足口腔正畸的临床要求。     

Geometric accuracy analysis for discrete surface approximation

In geometric modeling and processing, computer graphics and computer vision, smooth surfaces are approximated by discrete triangular meshes reconstructed from sample points on the surfaces. A fundamental problem is to design rigorous algorithms to guarantee the geometric approximation accuracy by controlling the sampling density. This paper gives explicit formulae to the bounds of Hausdorff distance, normal distance and Riemannian metric distortion between the smooth surface and the discrete mesh in terms of principle curvature and the radii of geodesic circum-circle of the triangles. These formulae can be directly applied to design sampling density for data acquisitions and surface reconstructions. Furthermore, we prove that the meshes induced from the Delaunay triangulations of the dense samples on a smooth surface are convergent to the smooth surface under both Hausdorff distance and normal fields. The Riemannian metrics and the Laplace–Beltrami operators on the meshes are also convergent to those on the smooth surfaces. These theoretical results lay down the foundation for a broad class of reconstruction and approximation algorithms in geometric modeling and processing.Practical algorithms for approximating surface Delaunay triangulations are introduced based on global conformal surface parameterizations and planar Delaunay triangulations. Thorough experiments are conducted to support the theoretical results.     

A Gromov-Hausdorff Framework with Diffusion Geometry for Topologically-Robust Non-rigid Shape Matching

In this paper, the problem of non-rigid shape recognition is studied from the perspective of metric geometry. In particular, we explore the applicability of diffusion distances within the Gromov-Hausdorff framework. While the traditionally used geodesic distance exploits the shortest path between points on the surface, the diffusion distance averages all paths connecting the points. The diffusion distance constitutes an intrinsic metric which is robust, in particular, to topological changes. Such changes in the form of shortcuts, holes, and missing data may be a result of natural non-rigid deformations as well as acquisition and representation noise due to inaccurate surface construction. The presentation of the proposed framework is complemented with examples demonstrating that in addition to the relatively low complexity involved in the computation of the diffusion distances between surface points, its recognition and matching performances favorably compare to the classical geodesic distances in the presence of topological changes between the non-rigid shapes.     

Enhancing 3D mesh topological skeletons with discrete contour constrictions

This paper describes a unified and fully automatic algorithm for Reeb graph construction and simplification as well as constriction approximation on triangulated surfaces. The key idea of the algorithm is that discrete contours – curves carried by the edges of the mesh and approximating the continuous contours of a mapping function – encode both topological and geometrical shape characteristics. Therefore, a new concise shape representation, enhanced topological skeletons, is proposed, encoding the contours’ topological and geometrical evolution. First, mesh feature points are computed. Then they are used as geodesic origins for the computation of an invariant mapping function that reveals the shape most significant features. Next, for each vertex in the mesh, its discrete contour is computed. As the set of discrete contours recovers the whole surface, each of them can be analyzed, both to detect topological changes and constrictions. Constriction approximations enable Reeb graphs refinement into more visually meaningful skeletons, which we refer to as enhanced topological skeletons. Extensive experiments showed that, without any preprocessing stage, proposed algorithms are fast in practice, affine-invariant and robust to a variety of surface degradations (surface noise, mesh sampling and model pose variations). These properties make enhanced topological skeletons interesting shape abstractions for many computer graphics applications.     

Efficiently computing exact geodesic loops within finite steps

Closed geodesics, or geodesic loops, are crucial to the study of differential topology and differential geometry. Although the existence and properties of closed geodesics on smooth surfaces have been widely studied in mathematics community, relatively little progress has been made on how to compute them on polygonal surfaces. Most existing algorithms simply consider the mesh as a graph and so the resultant loops are restricted only on mesh edges, which are far from the actual geodesics. This paper is the first to prove the existence and uniqueness of geodesic loop restricted on a closed face sequence; it contributes also with an efficient algorithm to iteratively evolve an initial closed path on a given mesh into an exact geodesic loop within finite steps. Our proposed algorithm takes only an O(k) space complexity and an O(mk) time complexity (experimentally), where m is the number of vertices in the region bounded by the initial loop and the resultant geodesic loop, and k is the average number of edges in the edge sequences that the evolving loop passes through. In contrast to the existing geodesic curvature flow methods which compute an approximate geodesic loop within a predefined threshold, our method is exact and can apply directly to triangular meshes without needing to solve any differential equation with a numerical solver; it can run at interactive speed, e.g., in the order of milliseconds, for a mesh with around 50K vertices, and hence, significantly outperforms existing algorithms. Actually, our algorithm could run at interactive speed even for larger meshes. Besides the complexity of the input mesh, the geometric shape could also affect the number of evolving steps, i.e., the performance. We motivate our algorithm with an interactive shape segmentation example shown later in the paper.     

水平集网格简化算法在遗址场景中的应用

将水平集方法引入到三维模型网格简化中,构造符号距离函数,函数的零集定义为初始曲面;引入一个能量泛涵,通过对其极小化诱导出一个水平集形式的二阶几何偏微分方程,从而将网格简化过程转化为隐式模型的体素扩散过程。该方法目前已经用于文化遗产数字化的大场景和文物的模型简化中。对水平集网格简化算法和现常用的基于点对收缩的网格简化算法在视觉质量和几何误差方面做了比较和分析,实验表明该方法适用于任意拓扑形状的网格模型,使得模型大规模简化后,在保持较低误差的同时,仍然能够保持相当多的重要几何特征和较好的整体视觉效果。     

基于支撑域的网格简化算法

提出一种基于2次误差测度（QEM）的网格简化改进算法。算法首先对折叠边所产生的新顶点定义其在初始网格上的简化支撑域,从而建立新顶点与初始网格之间的联系;然后计算新顶点到支撑域的2次距离误差作为该顶点的全局简化误差,并将原始QEM中的误差作为局部简化误差;最后将两个误差之和作为新的折叠代价目标函数以实现对原有QEM算法的改进。多个模型的简化实验表明,改进算法能较好地保留初始网格的细节特征,并且较为明显地降低简化误差。     

点集表面的共形参数化

基于点的图形系统成为图形学研究中的一个热点。该文介绍了一种无组织点集表面的共形参数化方法,在该参数化方法中,传统算法中经常使用的欧氏距离被测地线距离所代替。相对于欧氏距离,测地线距离能够更好地描述点集所隐含的表面,减少由点集表面无拓扑性质带来的误差,保持点集曲面的形状不变,提高参数化的质量。