点云模型上测地线的计算

给定点云模型上2点，将点云数据沿与xyz三坐标轴垂直方向进行单元剖分后，采用Dijkstra算法求出2点间的最短路径作为初始测地线；然后通过带弧长最短约束的平方距离最小化方法对初始测地线进行迭代优化，计算得到点云模型上给定2点间的一条样条表示的精确测地线．文中算法只需局部拟合抛物曲面，无需对点云模型进行三角化或曲面重建，适合大规模点云数据模型上测地线的计算．     

旋转面计算机辅助缠绕设计中的拟测地线算法

本文提出了旋转面上的拟测地线的打滑系数计算公式,并可以运用拟测地线样条作缠绕路径设计。从而提出了计算机辅助缠绕设计中的一个稳定,快速的算法－拟测地线算法,该算法充分开发自由度,并能显示装示,增加灵活性,使得整个缠绕过程成为一个统一的,可预先加以控制的操作过程。     

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

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

过测地线的近似极小直纹曲面设计

为了在服装鞋帽制造业及材料剪裁中采用过给定测地线且具有近似最小面积的直纹曲面,提出一种直纹曲面算法.该算法将过给定测地线的曲面设计和近似极小曲面的逼近技术进行有机结合,把直纹曲面表示成含2个参变量的形式;利用变分法的思想进行最优化,并分别在弧长参数和一般参数下对其进行了讨论.最后通过一些实例验证了文中算法的正确性和有效性.     

改进的局部加权窗口匹配代价算法

稠密匹配可以看做匹配代价最小化的过程,而匹配代价的计算是各种稠密匹配算法的必要步骤。分析取得良好效果的测地线距离局部加权窗口匹配算法,针对测地线权值计算的核心部分进行改进,提出一种环式的测地线权值计算方法,并详细介绍改进后的权值计算方法应用于局部加权匹配的性能优势。最后通过对比实验证明：在不损失精度的前提下,改进后的匹配代价整体计算时间提高了近1/2。     

圆环面上纤维轨迹的计算机辅助设计

曲面上的曲线造型是计算机图形领域的一个新的研究热点,而且它们在纤维织物编织,三维服装裁剪以及复合材料的纤维缠绕轨迹设计等领域有十分广泛的应用,为了解决圆环面上纤维轨迹的计算机辅助设计问题,研究了圆环面上测地线的解析解以及拟测地线数值求解的具体算法并给出了其表达式,测地线是曲面上两点之间最短距离的曲线段,在一般曲面上没有解析解,但是在圆环面上却可求出其精确的解析解,但在曲面的边沿部分,测地线因不能实现自然的折返过渡,于是拟测地线就被引进到曲面上的曲线造型设计之中,在拟测地线分析研究基础上,给出了圆环面上拟测地线的方程及数值解法,通过其在一个实例中的应用结果证明,该方法可获得织物的纺织条纹以及缠绕物体的纤维轨迹。     

基于测地线区域模型的图像分割修正算法研究

为提高区域模型的分割精度,在测地线活动区域模型的交互式图像分割的基础上,提出了一种基于标记点的修正算法,主要是对所得到的区域和边界概率模型进行修正。可以实现对图像中的弱势样本点,例如边缘、小区域等进行修正,从而克服计算区域和边界概率时建模不准确的缺点,使得测地线活动区域模型的初始曲线能够演化到正确的目标边界上。     

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

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

基于MMP三角曲面测地线算法研究

测地线的计算在计算机图形处理等方面有着广泛的应用。采用基于MMP（Mitchell, Mount,Papadimitrious）方法,实现了三角曲面上测地线的计算,修正了Vitaly Surazhsky等采用的测地线算法中的误差。该方法首先在窗口传播上摒弃了原有的近似结束条件,采用光源射线法。特别在窗口相交处理过程中采用多种情况的分层枚举,补充了Vitaly Surazhsky讲述的单一情况,窗函数多交点时的测地线偏差情况,并且提供简洁的回溯方法。实验结果表明,该方法所需时间相当于Vitaly Surazhsky算法,可以代替Vitaly Surazhsky采用的算法。     

测地切割磨光曲线的生成

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

Efficiently computing geodesic offsets on triangle meshes by the extended Xin–Wang algorithm

Geodesic offset curves are important for many industrial applications, such as solid modeling, robot-path planning, the generation of tool paths for NC machining, etc. Although the offset problem is well studied in classical differential geometry and computer-aided design, where the underlying surface is sufficiently smooth, very few algorithms are available for computing geodesic offsets on discrete representation, in which the input is typically a polyline curve restricted on a piecewise linear mesh. In this paper, we propose an efficient and exact algorithm to compute the geodesic offsets on triangle meshes by extending the Xin–Wang algorithm of discrete geodesics. We define a new data structure called parallel-source windows, and extend both the “one angle one split” and the filtering theorem to maintain the window tree. Similar to the original Xin–Wang algorithm, our extended algorithm has an O(n) space complexity and an O(n²logn) asymptotic time complexity, where n is the number of vertices on the input mesh. We tested our algorithm on numerous real-world models and showed that our algorithm is exact, efficient and robust, and can be applied to large scale models with complicated geometry and topology.     

Gradient geodesic and Newton geodesic HMP algorithms for the optimization of hybrid systems

This paper provides algorithms for the optimization of autonomous hybrid systems based on the geometrical properties of switching manifolds. By employing the notion of geodesic curves on switching manifolds, the Hybrid Maximum Principle (HMP) algorithm introduced in Shaikh and Caines (2007) is extended to the so-called gradient geodesic and Newton geodesic algorithms. The convergence analysis for the algorithms is based upon the Lasalle Invariance Principle and simulation results illustrate their efficacy.     

An intrinsic algorithm for computing geodesic distance fields on triangle meshes with holes

As a fundamental concept, geodesics play an important role in many geometric modeling applications. However, geodesics are highly sensitive to topological changes; a small topological shortcut may result in a significantly large change of geodesic distance and path. Most of the existing discrete geodesic algorithms can only be applied to noise-free meshes. In this paper, we present a new algorithm to compute the meaningful approximate geodesics on polygonal meshes with holes. Without the explicit hole filling, our algorithm is completely intrinsic and independent of the embedding space; thus, it has the potential for isometrically deforming objects as well as meshes in high dimensional space. Furthermore, our method can guarantee the exact solution if the surface is developable. We demonstrate the efficacy of our algorithm in both real-world and synthetic models.     

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.     

基于边界检测的多流形学习算法*

已知流形学习算法都假设数据分布于一个单流形,而现实中大部分数据都分布在多流形上,因此限制算法的实际应用.基于此种情况,文中提出基于边界检测的多流形学习算法,通过检测流形的边界处理分布于多流形的数据,并且可以较好地保持流形内、流形间的测地距离.算法首先检测流形边界,再分别降维处理各流形,最后将各低维坐标重置于一个全局坐标系中.在人工数据集和真实数据集上的对比实验表明文中算法的可行性和有效性.     

Point-in-polygon tests for geometric buffers

The point-in-polygon problem is often encountered in geographical information systems. The algorithms usually work on polygons defined by straight edges. In some situations, however, polygons containing circular arcs are applied. In geographical information systems these polygons are usually considered as geometric buffers, geodesic offsets, or geodesic parallels. This paper presents three algorithms suitable for providing information about the containment of a point in geometric buffers: the Ray-crossing method, the Cell-Based Algorithm and the Approximate approach. An extensive experimental section allows the reader to select the most efficient algorithm for practical problems.     

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.     

Fast and accurate geodesic distance transform by ordered propagation

In this paper, we present a new geodesic distance transform that uses a non-Euclidean metric suitable for non-convex discrete 2D domains. The geodesic metric used is defined as the shortest path length through a set of pixels called Locally Nearest Hidden Pixels, and manages visibility zones using bounding angles. The algorithm is designed using ordered propagation, which makes it extremely efficient and linear in the number of pixels in the domain. We have compared our algorithm with the four most similar geodesic distance transform techniques, and we show that our approach has higher accuracy and lower computational complexity.