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

doi:10.11996/JG.j.2095-302X.2025020437

图学学报 ›› 2025, Vol. 46 ›› Issue (2): 437-448.DOI: 10.11996/JG.j.2095-302X.2025020437

• 计算机图形学与虚拟现实 • 上一篇下一篇

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

王文嵩¹(), 周子珺¹, 辛士庆¹(), 屠长河¹, 王文平²

1.山东大学计算机科学与技术学院，山东青岛 266011
2.德克萨斯农工大学计算机科学与工程系，德克萨斯大学城 77843-3112

收稿日期:2024-10-25 接受日期:2024-11-06 出版日期:2025-04-30 发布日期:2025-04-24
通讯作者:辛士庆(1979-)，男，教授，博士。主要研究方向为计算图形学、机器人路径规划、三维智能检测等。E-mail：xinshiqing@sdu.edu.cn
第一作者:王文嵩(1998-)，女，硕士研究生。主要研究方向为计算机图形学。E-mail：wensong.chris@qq.com
基金资助:
国家重点研发计划(2022YFB3303200);国家自然科学基金(62272277);国家自然科学基金(U23A20312);国家自然科学基金(62072284);山东省国家自然科学基金(ZR2020MF036)

Tracing high-quality isolines for discrete geodesic distance fields

WANG Wensong¹(), ZHOU Zijun¹, XIN Shiqing¹(), TU Changhe¹, WANG Wenping²

1. School of Computer Science and Technology, Shandong University, Qingdao Shandong 266011, China
2. Texas Agricultural and Mechanical University Department of Computer Science and Engineering, College Station Texas 77843-3112, United States

Received:2024-10-25 Accepted:2024-11-06 Published:2025-04-30 Online:2025-04-24
First author：WANG Wensong (1998-), master student. Her main research interest covers computer graphics. E-mail：wensong.chris@qq.com
Supported by:
National Key R&D Program of China(2022YFB3303200);National Natural Science Foundation of China(62272277);National Natural Science Foundation of China(U23A20312);National Natural Science Foundation of China(62072284);NSF of Shandong Province(ZR2020MF036)

摘要/Abstract

摘要：

测地等值线在可视化几何形状的内在度量变化方面以及验证给定测地算法的准确性上，具有重要的意义。通常，在线性三角网格上绘制测地等值线的具体做法是通过在三角形的内部根据顶点的距离值进行简单的线性插值。该方法因易于实现而被广泛应用，但由于测地距离场具有高度的非线性特征，其精度受到限制。因此，使用线性插值得到的等值线常常会出现各种失真现象，尽管可对输入网格进行极高分辨率的细分，依然难以捕捉到真实等值线的拓扑特征，如捕获尖锐的拐角部分很困难。考虑到脊线能够有效地表征测地路径的不连续过渡，提出了一种新的思路：类似于中轴面可以通过密集边界采样点的维诺图进行编码，测地等值线的几何和拓扑特征同样可以借助阿波罗尼乌斯图进行编码。具体而言，采用三次函数来逼近每条网格边上的距离函数变化，并依据分布在网格边的一组加权采样点生成阿波罗尼乌斯图。随后，将每个三角形根据生成的阿波罗尼乌斯图划分为若干个子区域，使得每个子区域内的距离场可以用线性函数进行有效近似。通过大量实验，验证了该方法的有效性，结果显示在较少的额外计算成本下，所生成的测地等值线相较于传统的线性插值方法，具有更高的准确性。

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

Abstract:

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.

Key words: computational geometry, isolines, geodesic distance, Apollonius diagram, ridge curve

中图分类号:

TP391
P283

王文嵩, 周子珺, 辛士庆, 屠长河, 王文平. 离散测地距离场的高精度等值线提取[J]. 图学学报, 2025, 46(2): 437-448.

WANG Wensong, ZHOU Zijun, XIN Shiqing, TU Changhe, WANG Wenping. Tracing high-quality isolines for discrete geodesic distance fields[J]. Journal of Graphics, 2025, 46(2): 437-448.

图/表 15

图1 本文方法相较于线性插值法的优势((a)本文方法；(b)线性插值法)

Fig. 1 Our method compared with linear interpolation method ((a) The present method; (b) Linear interpolation method)

图2 具有不同权重的2个站点的阿波罗尼乌斯图(绿色为平分线)

Fig. 2 The Apollonius diagram for two sites with different weights (green is the bisector line)

图3 站点P1统治子区域S1 (阿波罗尼乌斯顶点以黄色显示，阿波罗尼乌斯边以绿色显示)

Fig. 3 The site P1 dominates the subregion S1 (the Apollonius vertices are shown in yellow, and the Apollonius edge are shown in green)

图4 黄色的点是脊点，因为该点存在2条到源点相等距离的测地路径

Fig. 4 The yellow point is a ridge point since the geodesic paths have totally different configurations for the points around the yellow point

图5 考虑的3种情况的证明

Fig. 5 The proof of the three cases considered

图6 线性插值的等值线(顶部)和真实等值线(底部)

Fig. 6 Isolines using linear interpolation (top) and real isolines (bottom)

图7 算法流程图((a)显示输入模型；(b)显示网格三角形和测地线路径(红色)并使用三次函数插值；(c)显示了三角形中的一组点(红色点是三等分点，蓝色点是满足k=1的插值点)；(d)为这些站点构建阿波罗尼乌斯图；(e)构建阿波罗尼乌斯顶点和采样点的三角剖分；(f)显示测地距离场的等值线)

Fig. 7 Algorithmic pipeline ((a) Shows the input model; (b) Shows a mesh triangle and a geodesic path (in red) and uses the cubic function interpolation; (c) Shows a set of sites (red points are trisection points and blue ones are interpolated points satisfying k=1) in triangle; (d) Builds Apollonius diagram for those sites; (e) Builds the Apollonius vertices and Steiner point triangulation; (f) Shows the isolines of the geodesic distance field)

图8 测地距离场等距曲线的几何特征图((a)精准等值线；(b)线性插值法无法捕捉脊点等几何特征；(c)本文方法产生高质量的近似等值曲线)

Fig. 8 Geometric features of iso-distance curves of geodesic distance field ((a) Accurate contour lines; (b) The linear interpolation method cannot capture geometric features such as ridges; (c) The method presented in this paper generates high-quality approximate contour curves)

图9 本文方法时间和空间的效率图((a)~(b)在具有2 000~20 000个顶点和0，2，10，20，50个Steiner点的Buddha和Gargoyle模型上计算等值线的运行时间；(c)~(d) 5 000~350 000个顶点的较大规模的Armadillo和Gargoyle模型的内存消耗)

Fig. 9 Efficiency of time and space for the proposed method ((a)~(b) The running time of our method to compute isolines on the Buddha and Gargoyle model with 2 000 to 20 000 vertices and 0, 2, 10, 20, 50 Steiner points; (c)~(d) Plotting the memory consumption on larger scaled Armadillo and Gargoyle models with 5 000 to 350 000 vertices)

表1 本文方法和线性插值的误差比较

Table 1 Comparison of errors between ours method and linear interpolation

Model	\|V\|/K	t/s	RAM/MB	$ε ¯ / % (O u r s)$	$ε ¯ / % (L i n e a r)$
Beetle	0.6	0.012 0.015	0.02	0.170 0.120	0.516
Beetle	5.0	0.246 0.265	0.18	0.082 0.019	0.223
Bottle	1.0	0.037 0.041	0.04	0.132 0.096	0.425
Bottle	10.0	0.584 0.624	0.34	0.021 0.009	0.096
Fertility	1.2	0.044 0.059	0.06	0.097 0.037	0.227
Fertility	12.0	0.855 1.101	0.47	0.038 0.037	0.140
Gargoyle	5	0.195 0.212	0.13	0.039 0.030	0.199
Gargoyle	50	2.861 3.855	2.27	0.005 0.004	0.019
Buddha	5	0.187 0.199	0.11	0.055 0.028	0.100
Buddha	50	2.682 2.891	0.52	0.012 0.004	0.035

表1 本文方法和线性插值的误差比较

Table 1 Comparison of errors between ours method and linear interpolation

Model	\|V\|/K	t/s	RAM/MB	$ε ¯ / % (O u r s)$	$ε ¯ / % (L i n e a r)$
Beetle	0.6	0.012 0.015	0.02	0.170 0.120	0.516
Beetle	5.0	0.246 0.265	0.18	0.082 0.019	0.223
Bottle	1.0	0.037 0.041	0.04	0.132 0.096	0.425
Bottle	10.0	0.584 0.624	0.34	0.021 0.009	0.096
Fertility	1.2	0.044 0.059	0.06	0.097 0.037	0.227
Fertility	12.0	0.855 1.101	0.47	0.038 0.037	0.140
Gargoyle	5	0.195 0.212	0.13	0.039 0.030	0.199
Gargoyle	50	2.861 3.855	2.27	0.005 0.004	0.019
Buddha	5	0.187 0.199	0.11	0.055 0.028	0.100
Buddha	50	2.682 2.891	0.52	0.012 0.004	0.035

图10 本文方法和分段线性方法之间的平均误差作比较

Fig. 10 The comparison of mean error between our method and the piecewise linear method

图11 当k=2时，采取本文方法生成结果。本文结果和线性插值法的结果分别以黑色和红色呈现

Fig. 11 Our results with k=2. Our results and the results of the linear interpolation method are rendered in black and red, respectively ((a) |V|=5K，ε=0.019%; (b) |V|=5K; (c) |V|=1K; (d) |V|=1.2K, ε=0.074%)

表2 文献[1]和本文方法运行时性能比较

Table 2 Runtime performance between Literature [1] and Ours

Model	\|V\|/K	文献[1]		Ours
Model	\|V\|/K	t/s	RAM/MB	t/s	RAM/MB
Beetle	0.6 5.0	0.327 2.831	0.7 14.4	0.236 2.284	0.02 0.18
Bottle	1.0 10.0	0.843 6.791	1.4 39.5	0.432 5.216	0.04 0.34
Fertility	1.2 12.0	0.727 7.287	2.1 58.8	0.657 5.433	0.06 0.47
Gargoyle	5.0 50.0	3.357 30.086	7.9 176.6	2.195 23.877	0.13 2.27
Buddha	5.0 50.0	3.574 32.439	9.0 153.6	2.736 27.372	0.11 0.52

图12 该三角形被划分为一组子区域，使得每个窗口通过计算关于根的阿波罗图来统治一个子区域

Fig. 12 The triangle is partitioned into a set of sub-regions such that each window dominates a sub-region via computing an Apollonius diagram w.r.t the roots

图13 本文方法((a)快速行进方法；(b)热方法。本文结果和线性插值结果分别着色为黑色和红色)

Fig. 13 Applying ours method ((a) The fast marching method; (b) The heat method. We color our results and the linear interpolation results in black and red, respectively)

参考文献 30

[1]	LIU Y J, CHEN Z Q, TANG K. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1502-1517.
[2]	VAN KREVELD M. Efficient methods for isoline extraction from a TIN[J]. International Journal of Geographical Information Systems, 1996, 10(5): 523-540.
[3]	XIN S Q, WANG G J. Applying the improved Chen and Han’s algorithm to different versions of shortest path problems on a polyhedral surface[J]. Computer-Aided Design, 2010, 42(10): 942-951.
[4]	SURAZHSKY V, SURAZHSKY T, KIRSANOV D, et al. Fast exact and approximate geodesics on meshes[J]. ACM Transactions on Graphics, 2005, 24(3): 553-560.
[5]	BIKTASHEV V N, HOLDEN A V. Re-entrant activity and its control in a model of mammalian ventricular tissue[J]. Proceedings of the Royal Society B: Biological Sciences, 1996, 263(1375): 1373-1382. PMID
[6]	SHARIR M, SCHORR A. On shortest paths in polyhedral spaces[C]// The 16th Annual ACM Symposium on Theory of Computing. New York: ACM, 1984: 144-153.
[7]	MELVÆR E L, REIMERS M. Geodesic polar coordinates on polygonal meshes[J]. Computer Graphics Forum, 2012, 31(8): 2423-2435.
[8]	KIMMEL R, SETHIAN J A. Computing geodesic paths on manifolds[J]. Proceedings of the National Academy of Sciences of the United States of America, 1998, 95(15): 8431-8435. PMID
[9]	CRANE K, WEISCHEDEL C, WARDETZKY M. Geodesics in heat: a new approach to computing distance based on heat flow[J]. ACM Transactions on Graphics, 2013, 32(5): 152.
[10]	NEWMAN T S, YI H. A survey of the marching cubes algorithm[J]. Computers & Graphics, 2006, 30(5): 854-879.
[11]	MITCHELL J S B, MOUNT D M, PAPADIMITRIOU C H. The discrete geodesic problem[J]. SIAM Journal on Computing, 1987, 16(4): 647-668.
[12]	GEHRE A, BOMMES D, KOBBELT L. Geodesic iso-curve signature[EB/OL]. [2024-08-25]. https://diglib.eg.org/items/8e9e0ae1-0edc-4d0e-8774-4a3801e5c429.
[13]	BOMMES D, KOBBELT L. Accurate computation of geodesic distance fields for polygonal curves on triangle meshes[EB/OL]. [2024-08-25]. https://www.graphics.rwth-aachen.de/publication/0363/.
[14]	CHEN J D, HAN Y J. Shortest paths on a polyhedron[C]// The 6th Annual Symposium on Computational Geometry. New York: ACM, 1990: 360-369.
[15]	LIU Y J, ZHOU Q Y, HU S M. Handling degenerate cases in exact geodesic computation on triangle meshes[J]. The Visual Computer, 2007, 23(9/11): 661-668.
[16]	XIN S Q, WANG G J. Improving Chen and Han's algorithm on the discrete geodesic problem[J]. ACM Transactions on Graphics, 2009, 28(4): 104.
[17]	YING X, XIN S Q, HE Y. Parallel Chen-Han algorithm for discrete geodesics[J]. ACM Transactions on Graphics, 2014, 33(1): 9.
[18]	SETHIAN J A, VLADIMIRSKY A. Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes[J]. Proceedings of the National Academy of Sciences of the United States of America, 2000, 97(11): 5699-5703.
[19]	MÉMOLI F, SAPIRO G. Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces[J]. Journal of Computational Physics, 2001, 173(2): 730-764.
[20]	SPIRA A, KIMMEL R. An efficient solution to the eikonal equation on parametric manifolds[J]. Interfaces and Free Boundaries, 2004, 6(3): 315-327.
[21]	WEBER O, DEVIR Y S, BRONSTEIN A M, et al. Parallel algorithms for approximation of distance maps on parametric surfaces[J]. ACM Transactions on Graphics, 2008, 27(4): 104.
[22]	CAMPEN M, KOBBELT L. Walking on broken mesh: defect‐tolerant geodesic distances and parameterizations[J]. Computer Graphics Forum, 2011, 30(2): 623-632.
[23]	XIN S Q, QUYNH D T P, YING X, et al. A global algorithm to compute defect-tolerant geodesic distance[C]// The SIGGRAPH Asia 2012 Technical Briefs. New York: ACM, 2012: 23.
[24]	XIN S Q, YING X, HE Y. Constant-time all-pairs geodesic distance query on triangle meshes[C]// The ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. New York: ACM, 2012: 31-38.
[25]	YING X, WANG X N, HE Y. Saddle vertex graph: a novel solution to the discrete geodesic problem[J]. ACM Transactions on Graphics, 2013, 32(6): 170.
[26]	WANG X N, FANG Z, WU J J, et al. Discrete geodesic graph for computing geodesic distances on polyhedral surfaces[J]. Computer Aided Geometric Design, 2017, 52-53: 262-284.
[27]	刘金义, 刘爽. Voronoi图应用综述[J]. 工程图学学报, 2004, 25(2): 125-132.
	LIU J Y, LIU S. A survey on applications of Voronoi diagrams[J]. Journal of Graphics, 2004, 25(2): 125-132 (in Chinese).
[28]	AURENHAMMER F. Power diagrams: properties, algorithms and applications[J]. SIAM Journal on Computing, 1987, 16(1): 78-96.
[29]	方澍, 骆晨丹, 胡凯, 等. 阿波罗尼斯圆定理, 性质及应用探究[J]. 创新教育研究, 2023, 11: 431-438.
	FANG S, LUO C D, HU K, et al. Apollonius circle theorem, properties and applications[J]. Creative Education Studies, 2023, 11: 431-438 (in Chinese).
[30]	EMIRIS I Z, KARAVELAS M I. The predicates of the Apollonius diagram: algorithmic analysis and implementation[J]. Computational Geometry, 2006, 33(1/2): 18-57.

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

Tracing high-quality isolines for discrete geodesic distance fields

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 30

相关文章 10

编辑推荐

Metrics

本文评价

[1]	宁阳，张云峰，高珊珊，迟静，张彩明. 基于三角区域有理函数的图像自适应插值[J]. 图学学报, 2015, 36(3): 444-451.
[2]	赵元棣，孙禾，王洁宁，李桃. 终端区航迹簇的中心航迹提取方法研究[J]. 图学学报, 2014, 35(3): 379-386.
[3]	乔要宾，朱定强，郑才浪. 火箭发动机喷流辐射场可视化[J]. 图学学报, 2013, 34(6): 11-16.
[4]	周敏，郑国磊，陈树林. 二维图形最狭长包络矩形的求解原理及方法[J]. 图学学报, 2013, 34(4): 46-53.
[5]	贾雨，王莹，姚兴苗. 交互式等值线图纸矢量化方法[J]. 图学学报, 2013, 34(3): 25-28.
[6]	王结臣，蒲英霞，崔璨，陈刚，马劲松. 一种基于点集自适应分组构建Voronoi 图的并行算法[J]. 图学学报, 2012, 33(6): 7-13.
[7]	李红军，张晓鹏. 离散点集最小包围圆算法分析与改进[J]. 图学学报, 2012, 33(2): 34-38.
[8]	陈海，王新民，焦裕松，李俨. 一种求凸多边形宽度的优化算法[J]. 图学学报, 2011, 32(2): 5-9.
[9]	朱二喜，何援军. 一种利用图形内角的多边形布尔运算新算法[J]. 图学学报, 2011, 32(2): 10-19.
[10]	宋伟杰，崔俊芝，叶正麟. 基于面图标的三维对称张量场可视化研究[J]. 图学学报, 2010, 31(6): 146-150.