跨越开边界的测地距离传播

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

图学学报 ›› 2025, Vol. 46 ›› Issue (5): 1042-1049.DOI: 10.11996/JG.j.2095-302X.2025051042

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

跨越开边界的测地距离传播

岳子佳¹(), 王文嵩², 陈双敏¹(), 辛士庆², 屠长河²

¹ 青岛科技大学信息科学技术学院，山东青岛 266061
² 山东大学计算机科学与技术学院，山东青岛 266000

收稿日期:2024-11-15 接受日期:2025-03-26 出版日期:2025-10-30 发布日期:2025-09-10
通讯作者:陈双敏(1982-)，女，副教授，博士。主要研究方向为计算机图形学、深度几何处理等。E-mail：csmqq@163.com
第一作者:岳子佳(2000-)，女，硕士研究生。主要研究方向为计算机图形学。E-mail：4022110095@mails.qust.edu.cn
基金资助:
国家重点研发计划(2022YFB3303200);国家自然科学基金(62272277);国家自然科学基金(U23A20312)

Geodesic distance propagation across open boundaries

YUE Zijia¹(), WANG Wensong², CHEN Shuangmin¹(), XIN Shiqing², TU Changhe²

¹ School of Information Science and Technology, Qingdao University of Science and Technology, Qingdao Shandong 266061, China
² School of Computer Science and Technology, Shandong University, Qingdao Shandong 266000, China

Received:2024-11-15 Accepted:2025-03-26 Published:2025-10-30 Online:2025-09-10
First author：YUE Zijia (2000-), master student. Her main research interest covers computer graphics. E-mail：4022110095@mails.qust.edu.cn
Supported by:
National Key R&D Program of China(2022YFB3303200);National Natural Science Foundation of China(62272277);National Natural Science Foundation of China(U23A20312)

摘要/Abstract

摘要：

在数字几何处理领域，曲面上测地距离的计算是一项基本且关键的任务。在计算过程中，每个表面点同时扮演着接收器与发射器的角色，以实现整个曲面上的距离传播。当存在开边界缺陷时，已有算法尝试在外蕴空间中填补孔洞和缝隙。然而，其在应对高度弯曲处出现的开边界缺陷时仍显不足。为此，提出在不补洞的情况下让距离传播自然跨越孔洞的新思路。观察发现，传统算法在跨越孔洞后，会形成一个“阴影”区域；该区域内的最短路径经由孔洞的边界，从而产生了比真正测地距离更大的结果。基于该观察，对经典的快速行进法(FMM)进行了3项重要改进：首先，仅将边界点视为距离接收器，阻止向其他点传播距离；其次，允许每个点向前后2个方向传播距离，使得阴影区域内的点可以从周边的可见点获得测地距离；最后，通过调整距离传播的优先级实现“由近及远”和“从可见区域到阴影区域”这2种传播方式之间的平衡。实验证明，即使是极为复杂的开边界缺陷，该方法依然产生接近于真解(模型没有缺陷情况下)的测地距离。

关键词: 计算几何, 测地距离, 快速行进法, 缺陷网格, 开边界

Abstract:

In the field of digital geometry processing, the computation of geodesic distances on surfaces is a fundamental and crucial task. During the calculation process, each surface point serves as both a receiver and a transmitter to propagate distances across the entire surface. When there are open boundary defects, existing algorithms attempt to fill holes and gaps in the ambient space. However, this approach remains inadequate when dealing with open-boundary defects occurring in highly curved regions. To address this, a new approach was proposed allowing geodesic distance propagation to naturally traverse holes without filling them. It was observed that traditional algorithms, after crossing holes, formed a “shadow” region. In this region, the shortest path was found to pass through the hole’s boundary, producing distances larger than the true geodesic distance. Based on this observation, three significant improvements were made to the classical fast marching method (FMM): First, boundary points are treated solely as distance receivers, preventing them from propagating distances to other points. Second, each point was allowed to propagate distances in both forward and backward directions, enabling points in the shadow region to obtain geodesic distances from the surrounding visible points. Finally, a balance was achieved between “near to far” and “visible region to shadow region” propagation modes by adjusting the priority of distance propagation. Experimental results demonstrated that even with highly complex open boundary defects, our method produced geodesic distances closely approximating the true solution (the solution for a model without defects).

Key words: computational geometry, geodesic distance, fast marching method, broken mesh, open boundary

中图分类号:

TP391.41

岳子佳, 王文嵩, 陈双敏, 辛士庆, 屠长河. 跨越开边界的测地距离传播[J]. 图学学报, 2025, 46(5): 1042-1049.

YUE Zijia, WANG Wensong, CHEN Shuangmin, XIN Shiqing, TU Changhe. Geodesic distance propagation across open boundaries[J]. Journal of Graphics, 2025, 46(5): 1042-1049.

图/表 12

图1 经典的快速行进法(FMM)和本文方法分别与真解的比较((a) 快速行进法；(b) 本文方法)

Fig. 1 Comparison between FMM and our method against the ground truth value ((a) Fast marching method; (b) Ours)

图2 不同距离传播方面的差异((a) FMM；(b) 本文方法)

Fig. 2 The difference in distance propagation ((a) FMM; (b) Ours)

图3 FMM算法实现距离传播时的3种情况((a) 情形1；(b) 情形2；(c) 情形3)

Fig. 3 Three cases of distance propagation in the FMM algorithm ((a) Situation 1; (b) Situation 2; (c) Situation 3)

图4 本文方法实现距离传播时的3种情况((a) 情形1；(b) 情形2；(c) 情形3)

Fig. 4 The algorithm in this paper realizes three cases of distance propagation ((a) Situation 1; (b) Situation 2; (c) Situation 3)

图5 Δv1v2v3和Δv1v2v4二维坐标示意图

Fig. 5 Schematic diagram of Δv1v2v3 and Δv1v2v4 in a 2D coordinate system

图6 不同优先级设置的距离场比较((a) 优先级为FMM计算的距离；(b) 优先级为改进FMM计算的距离；(c) 优先级为(a)和(b)的加权(各取50%))

Fig. 6 Comparison of distance fields with different priority settings ((a) The priority is the distance calculated by FMM; (b) The priority is the improved calculated distance; (c) The priority is weighted by (a) and (b) (50 % each))

表1 本文方法与现有算法在5种不同分辨率的模型上的性能比较

Table 1 Performance comparison of the proposed method and existing algorithms on models with five different resolutions

Model	Vertex¹	VTP			文献[22]			FMM			Ours
Model	Vertex¹	Time/s²	RAM³	E_avg/%⁴	Time/s²	RAM³	E_avg/%⁴	Time/s²	RAM³	E_avg/%⁴	Time/s²	RAM³	E_avg/%⁴
Bunny	5	0.97	11/11	0.148	2.71	20/23	0.057	1.40	11/14	0.158	1.4+0.56	11/14	0.034
Camel	18	1.97	18/18	0.056	3.87	30/37	0.021	1.80	17/28	0.068	1.8+0.63	18/28	0.016
Bottle	20	2.03	20/20	0.136	3.72	42/46	0.021	1.81	17/28	0.149	1.81+0.62	18/28	0.026
Bimba	32	2.98	28/28	0.090	4.67	49/51	0.021	2.88	25/41	0.098	2.88+0.98	25/41	0.009
Kitten	38	3.26	34/34	0.130	5.05	51/57	0.027	4.18	29/47	0.132	4.18+0.71	29/47	0.013

图7 FMM与本文方法在不同参数值下的平均误差

Fig. 7 Mean error between the FMM and our method across various λ values

图8 结果与真实值的叠加效果对比

Fig. 8 Comparison of the superimposition effect between results and ground truth ((a) Kitten|V|=37 K; (b) Bunny|V|=5 K)

图9 复杂模型下的效果对比

Fig. 9 Comparison of effects under complex models ((a) FMM; (b) Ours)

图10 不同算法可视化结果对比((a) 文献[6]；(b) 文献[22]；(c) 本文方法；(d) 真实值的对比)

Fig. 10 Comparison of visualized results of different algorithms ((a) References [6]; (b) References [22]; (c) Ours; (d) Ground truth)

图11 每个子图中：左侧为FMM，右侧为本文方法。左上：Buddha，|V|=50 K，误差0.015%，3个孔洞。右上：Lucy，|V|=262 K，误差0.008%，3个孔洞。左下：Bottle，|V|=10 K，误差0.026%，3个孔洞。右下：Bunny，|V|=5 K，误差0.034%，2个孔洞

Fig. 11 Our results and the results of the fast marching method are right and left, respectively. Top Left: Buddha |V|=50 K, ?=0.015%, 3 holes. Top Right: Lucy |V|=262 K, ?=0.008%, 3 holes. Bottom Left: Bottle |V|=10 K, ?=0.026%, 3 holes. Bottom Right: Bunny |V|=5 K, ?=0.034%, 2 holes

参考文献 25

[1]	POTAMIAS R A, ZHENG J L, PLOUMPIS S, et al. Learning to generate customized dynamic 3D facial expressions[C]// The 16th Computer Vision. Cham: Springer, 2020: 278-294.
[2]	DAS A, DATTA S, GKIOXARI G, et al. Embodied question answering[C]// 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2018: 1-10.
[3]	刘嘉玮, 陈双敏, 王晓丽, 等. 三维打印中喷头的最优路径规划[J]. 图学学报, 2017, 38(1): 34-38. DOI
	LIU J W, CHEN S M, WANG X L, et al. Optimal nozzle path planning in 3D printing[J]. Journal of Graphics, 2017, 38(1): 34-38 (in Chinese). DOI
[4]	LIU R, AIGERMAN N, KIM V G, et al. DA Wand: distortion- aware selection using neural mesh parameterization[C]// 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2023: 16739-16749.
[5]	宋琳, 高满屯, 王三民, 等. 融合区域和测地线的活动轮廓模型与图割相结合的自然图像分割[J]. 图学学报, 2015, 36(5): 756-762. DOI
	SONG L, GAO M T, WANG S M, et al. Combining region-based model with geodesic active contour for nature image segmentation using graph cut optimization[J]. Journal of Graphics, 2015, 36(5): 756-762 (in Chinese).
[6]	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.
[7]	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.
[8]	MITCHELL J S B, MOUNT D M, PAPADIMITRIOU C H. The discrete geodesic problem[J]. SIAM Journal on Computing, 1987, 16(4): 647-668.
[9]	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.
[10]	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.
[11]	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.
[12]	LIU Y J. Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures[J]. Computer-Aided Design, 2013, 45(3): 695-704.
[13]	XU C X, WANG T Y, LIU Y J, et al. Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes[J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(7): 822-834.
[14]	QIN Y P, HAN X G, YU H C, et al. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation[J]. ACM Transactions on Graphics, 2016, 35(4): 125.
[15]	ALEKSANDROV L, LANTHIER M, MAHESHWARI A, et al. An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces[C]// The 6th Scandinavian Workshop on Algorithm Theory. Cham: Springer, 1998: 11-22.
[16]	XIN S Q, YING X, HE Y. Constant-time all-pairs geodesic distance query on triangle meshes[C]// ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. New York: ACM, 2012: 31-38.
[17]	ADIKUSUMA Y Y, FANG Z, HE Y. Fast construction of discrete geodesic graphs[J]. ACM Transactions on Graphics, 2020, 39(2): 14.
[18]	YING X, WANG X N, HE Y. Saddle vertex graph (SVG): a novel solution to the discrete geodesic problem[J]. ACM Transactions on Graphics, 2013, 32(6): 170.
[19]	WANG X N, FANG Z, WU J J, et al. Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces[J]. Computer Aided Geometric Design, 2017, 52-53: 262-284.
[20]	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.
[21]	TAO J, ZHANG J Y, DENG B L, et al. Parallel and scalable heat methods for geodesic distance computation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(2): 579-594.
[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]// SIGGRAPH Asia 2012 Technical Briefs. New York: ACM, 2012: 23.
[24]	FENG N, CRANE K. A heat method for generalized signed distance[J]. ACM Transactions on Graphics, 2024, 43(4): 92.
[25]	DU J, HE Y, FANG Z, et al. On the vertex-oriented triangle propagation (VTP) algorithm: parallelization and approximation[J]. Computer-Aided Design, 2021, 130: 102943.

跨越开边界的测地距离传播

Geodesic distance propagation across open boundaries

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 25

相关文章 7

编辑推荐

Metrics

本文评价

[1]	王文嵩, 周子珺, 辛士庆, 屠长河, 王文平. 离散测地距离场的高精度等值线提取[J]. 图学学报, 2025, 46(2): 437-448.
[2]	赵元棣，孙禾，王洁宁，李桃. 终端区航迹簇的中心航迹提取方法研究[J]. 图学学报, 2014, 35(3): 379-386.
[3]	周敏，郑国磊，陈树林. 二维图形最狭长包络矩形的求解原理及方法[J]. 图学学报, 2013, 34(4): 46-53.
[4]	王结臣，蒲英霞，崔璨，陈刚，马劲松. 一种基于点集自适应分组构建Voronoi 图的并行算法[J]. 图学学报, 2012, 33(6): 7-13.
[5]	李红军，张晓鹏. 离散点集最小包围圆算法分析与改进[J]. 图学学报, 2012, 33(2): 34-38.
[6]	陈海，王新民，焦裕松，李俨. 一种求凸多边形宽度的优化算法[J]. 图学学报, 2011, 32(2): 5-9.
[7]	朱二喜，何援军. 一种利用图形内角的多边形布尔运算新算法[J]. 图学学报, 2011, 32(2): 10-19.