Tracing high-quality isolines for discrete geodesic distance fields

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

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

CLC Number:

TP391
P283

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.

Figures/Tables 15

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

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

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

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

Fig. 5 The proof of the three cases considered

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

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)

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)

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)

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

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

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

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%)

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

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

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)

References 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.