三角网格表面等残留高度刀轨生成算法

针对截平面法规划的三角网格表面的刀轨长度较长、加工表面残留高度不均匀的问题,提出一种基于改进截平面法的等残留高度刀轨生成算法.首先在估算刀触点轨迹线垂直方向曲率半径的基础上,计算刀触点轨迹投影线并对其进行修正,去除其中冗余的投影点;然后由修正后的刀触点轨迹投影线构造驱动表面,利用驱动表面和网格表面迭代计算刀触点轨迹线;最后由刀触点轨迹线计算无干涉刀轨.与截平面法生成的刀轨进行比较分析的结果表明,文中算法生成的刀轨长度较小且获得的残留高度保持均匀,适合于三角网格表面表示的复杂表面的精加工.     

Smooth tool path generation for 5-axis machining of triangular mesh surface with nonzero genus

NC machining of a nonzero genus triangular mesh surface is being more widely confronted than before in the manufacturing field. At present, due to the complexity of geometry computation related to tool path generation, only one path pattern of iso-planar type is adopted in real machining of such surface. To improve significantly 5-axis machining of the nonzero genus mesh surface, it is necessary to develop a more efficient and robust tool path generation method. In this paper, a new method of generating spiral or contour-parallel tool path is proposed, which is inspired by the cylindrical helix or circle which are a set of parallel lines on the rectangular region obtained by unwrapping the cylinder. According to this idea, the effective data structure and algorithm are first designed to transform a nonzero genus surface into a genus-0 surface such that the conformal map method can be used to build the bidirectional mapping between the genus-0 surface and the rectangular region. In this rectangular region, the issues of spiral or contour-parallel tool path generation fall into the category of simple straight path planning. Accordingly, the formula for calculating the parameter increment for the guide line is derived by the difference scheme on the mesh surface and an accuracy improvement method is proposed based on the edge curve interpolation for determining the cutter contact (CC) point. These guarantee that the generated tool path can meet nicely the machining requirement. To improve further the kinematic and dynamic performance of 5-axis machine tool, a method for optimizing tool orientation is also preliminarily investigated. Finally, the experiments are performed to demonstrate the proposed method and show that it can generate nicely the spiral tool path or contour-parallel tool path on the nonzero genus mesh surface and also can guarantee the smooth change of tool orientation.     

Reduce the stretch in surface flattening by finding cutting paths to the surface boundary

This paper presents a method for finding cutting paths on a 3D triangular mesh surface to reduce the stretch in the flattened surface. The cutting paths link the surface boundary and the nodes where the Gaussian curvature is high, and their total length is minimized. First, a linear algorithm for computing an approximate boundary geodesic distance map is introduced; the map encapsulates the undirected geodesic distance from every triangular node to the surface boundary approximately. This is followed by determining the undirected shortest paths passing through all the nodes where the Gaussian curvature is larger than a threshold. The cutting paths walk along the triangular edges of the given surface. Compared with other similar approaches, our method reaches a faster speed, and can deal with surfaces with widely distributed curvatures.     

A mapping-based approach to eliminating self-intersection of offset paths on mesh surfaces for CNC machining

Geometrically, a tool path can be generated by successively offsetting its adjacent path on the surface with a given path interval, which preferably starts from one of the surface boundaries or a primary curve. The key issues involved in offset path planning are the generation of raw offset paths and the elimination of the self-intersection of raw offset paths. Most researches available in this area are focused on how to generate the raw offset paths, however, the latter, especially how to eliminate the self-intersection of the offset paths on mesh surfaces, has not been sufficiently addressed. In this paper, a mapping-based approach to eliminating the self-intersection of offset paths is proposed for the CNC machining of mesh surfaces. The method first flattens the mesh surface onto a predefined plane by using a mesh mapping technique, and then taking the mapping as a guide, the offset paths are also naturally mapped onto the plane, from which those invalid self-intersection loops can be effectively identified and eliminated. To handle the issue of self-intersection for all types of offset path, a notion of local loop is introduced to detect and eliminate the invalid self-intersection loops. After that the planar paths are inversely mapped into the physical space and the final tool paths used for the machining of mesh surface are obtained. Meanwhile, in order to improve the kinematic and dynamic performance of the machine tool when machining along the generated offset paths, a method for rounding the sharp corners of tool paths, which result from the process of eliminating the self-intersection of raw offset paths, is also preliminarily investigated. Finally, the proposed method is validated by the results of simulations and machining experiments.     

Heat method of non-uniform diffusion for computing geodesic distance on images and surfaces

This paper presents a non-uniform heat method to calculate geodesic distance and geodesic curves on the images and surfaces. Different from the varadhan’s formula-based heat method, our non-uniform heat method first finds the direction of distance increases by heat diffusion, and then recovers the geodesic distance by solving a Poisson equation. Various heat diffusion metrics obtained from different potentials and tensors, such as intensity-based metrics, gradient-based metrics, and anisotropy metrics et., describe the differences of geodesic distances in various regions. Combined with automatic geodesic segmentation technology, our heat method can be effectively and quickly applied to centerlines extraction and salient curves detection in images, skeleton extraction of shapes, and 3D path planning on surfaces. Two categories of discretization algorithms on scattered points and triangle meshes are more flexible and can often be used to more complicated cases. The algorithm is robust and simple to implement since it is based on solving a pair of standard sparse linear systems. Pre-calculation also greatly reduces time consumption and memory footprint.

     

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

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

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.     

复杂三角网格模型刀具组合优化加工研究

在满足复杂三角网格模型数控加工的精度要求下,为提高加工效率,提出了刀具组合优化方法。该方法以刀具轨迹长度最短为目标,并综合考虑模型微分几何信息对加工效率和精度的影响。首先根据面片法矢和曲率将模型分割为多个特征子区域,不同类型的特征子区域采用不同的刀具轨迹生成策略;建立各类型子区域的精确轨迹长度估算模型;选取合适的标准刀具组合并估算轨迹长度,拟合三次B样条曲线,求取曲线一阶导矢得到最小值,选择对应的标准刀具尺寸作为最优刀具尺寸。算法在VC++环境下进行了编程实现和算例验证,结果表明该方法是可行有效的。     

Mesh Snapping: Robust Interactive Mesh Cutting Using Fast Geodesic Curvature Flow

This paper considers the problem of interactively finding the cutting contour to extract components from a given mesh. Some existing methods support cuts of arbitrary shape but require careful and tedious input from the user. Others need little user input however they are sensitive to user input and need a postprocessing step to smooth the generated jaggy cutting contours. The popular geometric snake can be used to optimize the cutting contour, but it cannot deal with the topology change. In this paper, we propose a geodesic curvature flow based framework to overcome all these problems. Since in many cases the meaningful cutting contour on a 3D mesh is locally shortest in the sense of some weighted curve length, the geodesic curvature flow is an ideal tool for our problem. It evolves the cutting contour to the nearby local minimum. We should mention that the previous numerical scheme, discretized geodesic curvature flow (dGCF) is too slow and has not been applied to mesh segmentation. With a careful observation to dGCF, we devise here a fast computation scheme called fast geodesic curvature flow (FGCF), which only needs to solve a smaller and easier problem. The initial cutting contour is generated by a variant of random walks algorithm, which is very fast and gives reasonable cutting result with little user input. Experiment results on the benchmark mesh segmentation data set show that our proposed framework is robust to user input and capable of producing good results reflecting geometric features and human shape perception.     

基于非均匀热扩散的交互式图像分割算法

交互式图像分割是图像分割中的重要分支,在现实生活和医学领域都有着广泛的应用。该文基于计算测地距离的热方法,引入了热扩散系数,提出了一种基于非均匀热扩散的交互式图像分割算法。该算法利用图像的颜色信息构造三角网格作为热扩散的媒介,首先由热方程找到距离增加的方向,再利用泊松方程还原测地距离。将前景中人工交互区域上的热流扩散速度增加,则前景不同部分之间的测地距离变小,消除了内部边界,通过设置外部边界分割限制条件,即可实现完整的前景分割。算法仅需求解两个稀疏线性方程组,鲁棒性强、精度高且更易于操作。同时,拉普拉斯算子和梯度算子的预计算可以被多次重用,减少了内存占用和时间消耗。大量交互式图像分割实验结果表明:该算法无需过多的用户交互信息,即可将现实图像中的复杂前景快速准确地分割出来。     

Fast approximate geodesic paths on triangle mesh

We present a new algorithm to compute a geodesic path over a triangle mesh.Based on Novotni's propagating wavefront method which is similar to the well known Dijkstra algorithm,we made some improvements which Novotni had missed and we also gave the method to find out the geodesic path which Novotni had not.It can handle both convex and non-convex surfaces or even with boundaries.Experiment results show that our method works very well both in efficiency and precision.     

基于聚类的本征距离简化以及测地距估算

测地距是曲面上两点之间最短的距离,它在几何分析和运算中起非常重要的作用。目前精确计算测地距方法的时间复杂度非常大,为了加快测地距的估算,提出了通过分析网格模型的本征距离来快速估算任意两点间测地距的算法。首先根据网格模型的第一基本式对其进行聚类分块,然后通过调整其参数化方式将每块的共形参数模型简化为二次曲面模型,最后通过共形参数对测地距进行快速估算。实验结果表明,该方法可以极大地减少计算时间,快速地估算出网格模型上位于不同块上的任意两点间测地距。     

自然地形环境下移动机器人的一种路径规划方法

本文给出了一种规划移动机器人在自然地形中运动的新方法，该方法利用ＮＵＲＢＳ曲面模拟自然地形地貌，以ＴｒｉｍｍｅｄＮＵＲＢＳ曲面描述带有障碍物或不可逾越区域的地形，在综合考虑机器人动力学、地形及障碍描述和曲面特性等各方面因素的情形下，运用测地线的概念和计算方法以及Ａ＊搜索算法，获得了在自然地形环境下任意两点间的距离最短路径和时间最优路径，所有的路径均由ＮＵＲＢＳ曲线表示，实验结果表明，该方法在性能与效率上均十分令人满意．     

三角网格模型上测地线算法的研究

对三角网格模型上测地线的算法进行研究,分为近似测地线算法和精确测地线算法．其中近似算法介绍经典的FastMarching算法,精确算法以经典的MMP算法为主．并且对两种算法得到的测地线在准确度和时间复杂度上进行对比分析．得出实验数据．并对其应用进行简单介绍。     

Tool path generation for multi-axis freeform surface finishing with the LKH TSP solver

In freeform surface finishing, there are three major types of tool path topologies: the direction-parallel type, the contour–parallel type and the space-filling curve (SFC) type. The SFC topology is capable of covering the whole surface with only one path. In this paper, we present a new way of planning the SFC type tool path by formulating the planning task as a traveling salesman problem (TSP). The optimal path is generated in two steps. Firstly, a set of regular cutter contact (CC) points is generated on the input surface. A cutting simulation method is developed to evaluate the scallop error and determine the position of the next CC point in cross-feed direction. This method is free of local surface curvature assumptions and is therefore accurate for big cutters. Secondly, the obtained CC points are input into an efficient TSP solver LHK for the optimal CC point linking sequences. To stop the CC points from diagonal linking or penetrating linking, the Euclidean distance evaluation function for two CC points is redefined in LHK. The proposed tool path generation method is verified with several freeform surface examples; the results show that the method can automatically find the optimal feed direction and it can generate shorter tool path than the traditional SFC method. The feasibility of the proposed method is also verified by a cutting experiment.     

On Geodesic Curvature Flow with Level Set Formulation Over Triangulated Surfaces

The geodesic curvature flow is an important concept in Riemannian geometry. The flow with level set formulation has many applications in image processing, computer vision, material sciences, etc. The existing discretizations on triangulated surfaces are based on either finite volume method or finite element method with piecewise linear function space, which are suitable for vertex-based two-phase problems. The contour (zero level set) in existing methods passes through triangles of the mesh. However, in some graphic applications, such as mesh segmentation (to divide a whole mesh into several sub-meshes without ambiguous triangular stripes), the cutting contour is needed to be along the edges of the mesh. Moreover, multi-phase segmentation by a single level set function is a difficult problem for a long time. In this paper, we try to tackle these two problems. We propose a new discretization which has simpler formulation and more sparse coefficient matrix. We prove the existence and uniqueness, regularization behavior and maximum–minimum principle of our discrete flow. Therein the maximum–minimum principal has not been presented before. Lots of experiments show that, the limit of the flow would be a piecewise constant solution with ’discontinuity set’ to be the closed geodesics of the surface. We therefore propose a constrained discrete geodesic curvature flow, which is also analyzed theoretically. The linear system of the constrained flow can be equivalently reformulated into a much smaller one (especially in the narrow band algorithm), which dramatically reduces the computation cost. Combined with a narrow band algorithm, the constrained flow with topologically correct initializations (easy to be got by simple existing methods or manual inputs) yields a multi-phase segmentation method by a single level set function. We test our two flows in closed curve evolution and multi-region segmentation applications. The numerical experiments are given to demonstrate the effectiveness.     

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.     

Anisotropic geodesics for live‐wire mesh segmentation

We present an interactive method for mesh segmentation that is inspired by the classical live‐wire interaction for image segmentation. The core contribution of the work is the definition and computation of wires on surfaces that are likely to lie at segment boundaries. We define wires as geodesics in a new tensor‐based anisotropic metric, which improves upon previous metrics in stability and feature‐awareness. We further introduce a simple but effective mesh embedding approach that allows geodesic paths in an anisotropic path to be computed efficiently using existing algorithms designed for Euclidean geodesics. Our tool is particularly suited for delineating segmentation boundaries that are aligned with features or curvature directions, and we demonstrate its use in creating artist‐guided segmentations.     

Generation of reciprocating tool motion in 5-axis flank milling based on particle swarm optimization

This paper proposes a novel method for generation of optimized tool path in 5-axis flank milling of ruled surfaces based on Particle Swarm Optimization (PSO). The 3D geometric problem, tool path generation, is transformed into a mathematical programming task with the machined surface error as the objective function in the optimization. This approach overcomes the limitation of greedy planning methods employed by most previous studies. By allowing the cutter to move backforward, reciprocating tool path produces smaller machining error compared with the traditional one consisting of only forward cutter movement. A cutting experiment is conducted with different tool paths and the CMM measurement verifies the effectiveness of the proposed method.     

Continuity-preserving tool path generation for minimizing machining errors in five-axis CNC flank milling of ruled surfaces

Five-axis CNC flank machining has been commonly used in the industry for shaping complex geometries. Geometrical errors typically occur in five-axis flank finishing of non-developable surfaces using a cylindrical cutter. Most existing tool path planning methods adjust discrete cutter locations to reduce these errors. An excessive change in the cutter center or axis between consecutive cutter locations may deteriorate the machined surface quality. This study developed a tool path generation method for minimizing geometrical errors on finished surfaces while preserving high-order continuity in the cutter motion. A tool path is described using the moving trajectory of the cutter center and changes in two rotational angles in compact curve representations. An optimization scheme is proposed to search for optimal curve control points and the resulting tool path. A curve subdivision mechanism progressively increases the control points during the search process. Simulation results confirm that the proposed method not only enhances the computational efficiency of tool path generation but also improves the machined surface finish. This study provides a computational approach for precision tool path planning in five-axis CNC flank finishing of ruled surfaces.