测地线是曲面和任意流形上直线这一概念的一般化,求解三角网格模型的测地线在计算机图形学和模式识别研究以及工业设计和制造领域都有广泛的应用。随着离散网格模型越来越多的应用,理论研究和工业设计都要求设计准确和高效的求解测地线算法。　　 测地线在光滑曲面上有很好的几何性质,也有相应的测地线偏微分方程表达以及一些解析的方法来求解。在离散模型上,测地线不能完全保持连续情况下的所有几何性质,因而产生了不同的定义。目前,在离散网格上研究最多是求解最短测地线的方法,主要有三类解决方案。一类是[3]引入的连续Dijkastra算法,它们从源点开始把测地线经过的多边形序列展开到一个平面上的。这些算法的绝对近似性能比都是1,根据所采用的策略和数据结构不同,时间复杂度从O(n2logn)到O(nlogn)不等。第二类算法用一种前端面向前传播的方式,每一步在三角形上求解测地线微分方程来更新测地距离,比连续Dijkastra算法有更好的绝对近似性能比。基于不同的准确性要求算法的时间复杂度从O(nlogn)到O(n)不等。最后一类方案在当前Dijkastra最短路关联的三角形序列上,构造新的细分子图并求解新的Dijkastra最短路,直到所需的精度。它的时间和空间花费比较大。其中,实际应用最多的FMM(Fast Marching Method)是第二类方法。　　 最直测地线有更完整的微分几何定义和理论系统,在图形学领域内,对它的研究和应用还比较少。有关的算法有根据定义的左右曲面角相等,法截面法和切向投影等。这些方法的精度都局限在一阶截断误差,在离散的网格上有严重的累积误差。我们提出了两个个实际的线性时间的算法求解三角网格上一点开始沿给定切方向的最直测地线。我们的算法不需要额外的钝角三角形处理,并且在网格顶点和网格边处有统一的计算,在凹模型和凸模型上都得到了更好的准确性和效率,很大程度上解决了已有算法的累积误差问题。　　 本文的主要贡献有:　　 1)系统的研究了测地线的微分几何定义和离散网格上两种最主要的定义最短测地线和最直测地线。分析了测地线微分几何性质和行为,最短测地线与最直测地线之间的关系以及不同的特点和求解方式。　　 2)完整的定义了求解最直测地线的法截面方法,从几何的角度解释了算法的有效性和误差来源。通过实验和理论证明了算法具有一阶截断误差,相当于连续曲面上求解测地线的欧拉法。　　 3)提出切向法向调整算法求解最直测地线,很好的解决了已有算法的累积误差问题,在粗糙的网格上取得了连续曲面上的四阶龙格-库塔法的准确性。分析和验证了算法对法向的鲁棒性,求解步长对算法正确性的影响以及算法在NURBs曲面上的结果。