在几何学中,曲面上连接两点的最短距离称为测地距离,连接两点的路径称为测地线。测地线是弯曲空间中两点的局部最短路径,被认为是直线在弯曲空间的推广。测地线是曲面上一个非常重要的内蕴量,是计算几何中的经典问题。测地线问题的研究在科学和工程领域有着深远意义,在计算机图形学、数字医疗、智能设备的运动规划、工业制造以及深度学习等许多方面有着广泛的应用。随着大数据时代的到来,人们迫切需要数字几何处理算法能够以更高的运行效能、空间效率、鲁棒性应对海量的三维数据。尽管测地线问题从最初引入开始就获得了人们大量的关注并对其进行了不断完善、提升,但是如何在分辨率不断提高的大尺度模型上,快速、准确地解决测地线问题仍然是数字几何处理领域有待解决的关键问题之一。在大数据时代背景下使用精确算法获得测地线的时间代价相对过大,在大多数应用场景下人们往往从实用角度出发,在计算精度满足需求的前提下尽可能高效的获得一条近似的测地线结果。因此当前测地线问题的研究热点从如何精确计算测地线变为如何找到一种能在计算精度,时间以及内存消耗上取得一定平衡的更加灵活、鲁棒的近似测地线算法。本学位论文针对上述热点的曲面近似测地线问题,研究如何在不同表达形式的曲面（连续光滑曲面和离散网格曲面）上高效计算精度可控的、鲁棒的近似测地距离（场）。结合提出的测地线计算方法,进一步重点研究了如何高效构造网格曲面上近似Voronoi图这一与测地度量紧密相关的应用。本文主要创新点和贡献如下:（1）基于改进的图方法快速计算离散网格曲面上的测地距离场基于斯坦纳点插入的图方法作为网格曲面上计算测地距离场的经典方法,由于其执行简单,误差容易控制等特点而受到人们的广泛关注。但是该类方法存在随着插入斯坦纳点数目增加,计算复杂度剧增的固有问题。在本学位论文中,借鉴精确测地线算法中的过滤规则,创新性的提出了图上冗余事件的过滤策略并应用到传统斯坦纳点插入的图方法中去,有效的解决了传统图方法中存在的时间效率问题。同时通过有效整合算法执行过程中获得的“轨道”信息,为测地路径追踪,等值线的计算等提供了更加精确的结果。该框架可以扩展到更加广泛的测地线变种问题,如带密度或各向异性度量的测地线计算等等。（2）三角网格曲面上近似测地Voronoi图的高效构建方法过往研究中,人们一般使用精确测地距离去构造网格曲面上的Voronoi图结构。局限于目前精确测地线算法计算效率相对较低,从而间接导致Voronoi图生成效率不高。为了解决这一问题,在本学位论文中提出了不同以往的测地Voronoi图构造方法。和大多数方法使用精确算法获取测地距离信息不同,本文使用上一工作中改进版本的图方法替代精确算法,高效地获取测地距离信息。这使得测地Voronoi图计算会更节省时间,占用更少的内存。通过控制网格上三角形边插入斯坦纳点的数目可以取得接近精确测地Voronoi图的结果。另外利用带权斯坦纳点构造的阿波罗图划分三角网格,可以提取线段和双曲线用于编码测地Voronoi图复杂的等分线结构。（3）基于优化变分框架计算连续扫掠曲面上的近似测地路径针对连续光滑扫掠曲面提出了一种基于优化策略解决测地线问题的新方法。该方法发扬了曲线渐进缩短的精神,当用户在扫掠曲面上指定了两个目标点后,以两点之间的路径长度的平方和为目标函数,在参数域而非欧氏空间中建立了目标函数。通过将目标函数和梯度输入到L-BFGS求解器中,经过迭代优化最终高效的计算出一条满足精度要求的测地路径。和其他相关方法比较,算法在误差控制,时间效率等方面具有优势。另外本文把该框架扩展应用到测地螺旋线,动画模拟中的路径演化等问题中,取得了不错的效果。