离散测地距离场的高精度等值线提取  

Tracing high-quality isolines for discrete geodesic distance fields

作　　者：王文嵩 周子珺 辛士庆 屠长河[1] 王文平 WANG Wensong;ZHOU Zijun;XIN Shiqing;TU Changhe;WANG Wenping(School of Computer Science and Technology,Shandong University,Qingdao Shandong 266011,China;Texas Agricultural and Mechanical University Department of Computer Science and Engineering,College Station Texas 77843-3112,United States)

机构地区：[1]山东大学计算机科学与技术学院,山东青岛266011 [2]德克萨斯农工大学计算机科学与工程系,德克萨斯大学城77843-3112

出　　处：《图学学报》2025年第2期437-448,共12页Journal of Graphics

基　　金：国家重点研发计划(2022YFB3303200);国家自然科学基金(62272277,U23A20312,62072284);山东省国家自然科学基金(ZR2020MF036)。

摘　　要：测地等值线在可视化几何形状的内在度量变化方面以及验证给定测地算法的准确性上,具有重要的意义。通常,在线性三角网格上绘制测地等值线的具体做法是通过在三角形的内部根据顶点的距离值进行简单的线性插值。该方法因易于实现而被广泛应用,但由于测地距离场具有高度的非线性特征,其精度受到限制。因此,使用线性插值得到的等值线常常会出现各种失真现象,尽管可对输入网格进行极高分辨率的细分,依然难以捕捉到真实等值线的拓扑特征,如捕获尖锐的拐角部分很困难。考虑到脊线能够有效地表征测地路径的不连续过渡,提出了一种新的思路:类似于中轴面可以通过密集边界采样点的维诺图进行编码,测地等值线的几何和拓扑特征同样可以借助阿波罗尼乌斯图进行编码。具体而言,采用三次函数来逼近每条网格边上的距离函数变化,并依据分布在网格边的一组加权采样点生成阿波罗尼乌斯图。随后,将每个三角形根据生成的阿波罗尼乌斯图划分为若干个子区域,使得每个子区域内的距离场可以用线性函数进行有效近似。通过大量实验,验证了该方法的有效性,结果显示在较少的额外计算成本下,所生成的测地等值线相较于传统的线性插值方法,具有更高的准确性。Geodesic isolines play an important role in visualizing intrinsic metric variations of geometric shapes and in verifying the accuracy of given geodesic algorithms.Typically,geodesic isolines are drawn on a linear triangular mesh by performing simple linear interpolation based on vertex distance values within each triangle.This approach is widely used due to its simplicity,but it is limited in precision due to the highly nonlinear geodesic distance field.As a result,isolines obtained through linear interpolation often exhibit various distortions.Even with high-resolution subdivision of the input mesh,it remains challenging to capture the true topology of the isolines,such as sharp corner features.Given that ridges effectively represent discontinuous transitions in geodesic paths,a novel approach was proposed:Similar to how a medial axis can be encoded using a Voronoi diagram of densely sampled boundary points,the geometric and topological characteristics of geodesic isolines can similarly be encoded using an Apollonian diagram.Specifically,a cubic function was employed to approximate the distance function variation along each edge of the mesh,and an Apollonian diagram was generated based on a set of weighted sample points distributed along the mesh edges.Then,each triangle was divided into several subregions according to the generated Apollonian diagram,allowing the distance field within each subregion to be effectively approximated using a linear function.Extensive experiments have validated the effectiveness of this method.The results demonstrated that,with relatively low additional computational cost,the generated geodesic isolines are more accurate than those produced using traditional linear interpolation methods.

关 键 词：计算几何 等值线 测地距离 阿波罗尼乌斯图 脊线 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] P283[自动化与计算机技术—计算机科学与技术]