Home Tsinghua Science and Technology Article
PDF (18.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

An Efficient Algorithm for Approximate Polyline-Sourced Offset Computation on Triangulated Surfaces

School of Computer Science and Technology, Harbin Institute of Technology, Weihai 264209, China
Show Author Information

Abstract

The computation of polyline-sourced geodesic offset holds significant importance in a variety of applications, including but not limited to solid modeling, tool path generation for computer numerical control (CNC) machining, and parametrization. The traditional approaches for geodesic offsets have typically relied on the availability of an exact geodesic metric. Nevertheless, the computation of exact geodesics is characterized by its time-consuming nature and substantial memory usage. To tackle the limitation, our study puts forward a novel approach that seeks to circumvent the reliance on exact geodesic metrics. The proposed method entails a reformulated graph method that incorporates Steiner point insertion, serving as an effective solution for obtaining geodesic distances. By leveraging the aforementioned strategies, we present an efficient and robust algorithm designed for the computation of polyline-sourced geodesic offsets. The experimental evaluation, conducted on a diverse set of three-dimensional models, demonstrates significant improvements in computational speed and memory requirements compared to established state-of-the-art methods.

Keywords

geodesic offsetsgraph-based algorithmcomputer numerical control (CNC) millingtool path planning

References

[1]

J. R. Rossignac and A. A. G. Requicha, Offsetting operations in solid modelling, Computer Aided Geometric Design, vol. 3, no. 2, pp. 129–148, 1986.

Crossref Google Scholar
[2]
M. Forsyth, Shelling and offsetting bodies, in Proc. Third ACM Symp. Solid Modeling and Applications, Salt Lake City, UT, USA, 1995, pp. 373–381.
Crossref
[3]

T. Maekawa, An overview of offset curves and surfaces, Comput.-Aided Des., vol. 31, no. 3, pp. 165–173, 1999.

Crossref Google Scholar
[4]

S. Q. Xin, X. Ying, and Y. He, Efficiently computing geodesic offsets on triangle meshes by the extended Xin–Wang algorithm, Comput.-Aided Des., vol. 43, no. 11, pp. 1468–1476, 2011.

Crossref Google Scholar
[5]

L. A. Piegl and W. Tiller, Computing offsets of NURBS curves and surfaces, Comput.-Aided Des., vol. 31, no. 2, pp. 147–156, 1999.

Crossref Google Scholar
[6]

T. Lozano-Pérez and M. A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Commun. ACM, vol. 22, no. 10, pp. 560–570, 1979.

Crossref Google Scholar
[7]

C. Wu, C. Dai, X. Gong, Y. J. Liu, J. Wang, X. D. Gu, and C. C. L. Wang, Energy-efficient coverage path planning for general terrain surfaces, IEEE Robot. Autom. Lett., vol. 4, no. 3, pp. 2584–2591, 2019.

Crossref Google Scholar
[8]

H. Shen, J. Fu, Z. Chen, and Y. Fan, Generation of offset surface for tool path in NC machining through level set methods, Int. J. Adv. Manuf. Technol., vol. 46, nos. 9−12, pp. 1043–1047, 2010.

Crossref Google Scholar
[9]

F. Liang, C. Kang, and F. Fang, Tool path planning on triangular mesh surfaces based on the shortest boundary path graph, Int. J. Prod. Res., vol. 60, no. 9, pp. 2683–2702, 2022.

Crossref Google Scholar
[10]

N. M. Patrikalakis and L. Bardis, Offsets of curves on rational B-spline surfaces, Eng. Comput., vol. 5, no. 1, pp. 39–46, 1989.

Crossref Google Scholar
[11]

A. Hatna, R. J. Grieve, and P. Broomhead, Offsetting 3D contours on parametric surfaces, Int. J. Adv. Manuf. Technol., vol. 16, no. 3, pp. 189–195, 2000.

Crossref Google Scholar
[12]

J. K. Seong, G. Elber, and M. S. Kim, Trimming local and global self-intersections in offset curves/surfaces using distance maps, Comput.-Aided Des., vol. 38, no. 3, pp. 183–193, 2006.

Crossref Google Scholar
[13]

W. Zhuo and J. Rossignac, Curvature-based offset distance: Implementations and applications, Comput. Graph., vol. 36, no. 5, pp. 445–454, 2012.

Crossref Google Scholar
[14]
S. H. Lee, Offsetting operations on non-manifold boundary representation models with simple geometry, in Proc. Fifth ACM Symp. Solid Modeling and Applications, Ann Arbor, MI, USA, 1999, pp. 42–53.
Crossref
[15]

N. Medimegh, S. Belaid, and N. Werghi, A survey of the 3D triangular mesh watermarking techniques, Int. J. Multimed., vol. 1, no. 1, pp. 33–39, 2015.

Google Scholar
[16]

Y. Yu, K. Zhou, D. Xu, X. Shi, H. Bao, B. Guo, and H. Y. Shum, Mesh editing with poisson-based gradient field manipulation, ACM Trans. Graph., vol. 23, no. 3, pp. 644–651, 2004.

Crossref Google Scholar
[17]

Y. Liu, W. Wang, B. Lévy, F. Sun, D. M. Yan, L. Lu, and C. Yang, On centroidal voronoi tessellation—energy smoothness and fast computation, ACM Trans. Graph., vol. 28, no. 4, p. 101, 2009.

Crossref Google Scholar
[18]
D. Bommes and L. Kobbelt, Accurate computation of geodesic distance fields for polygonal curves on triangle meshes, in Proc. Vision, Modeling, and Visualization Conf. 2007, Saarbrücken, Germany, 2007, pp. 151–160.
[19]

C. Xu, Y. J. Liu, Q. Sun, J. Li, and Y. He, Polyline-sourced geodesic voronoi diagrams on triangle meshes, Comput. Graph. Forum, vol. 33, no. 7, pp. 161–170, 2014.

Crossref Google Scholar
[20]

S. Q. Xin and G. J. Wang, Improving Chen and Han’s algorithm on the discrete geodesic problem, ACM Trans. Graph., vol. 28, no. 4, p. 104, 2009.

Crossref Google Scholar
[21]

V. Surazhsky, T. Surazhsky, D. Kirsanov, S. J. Gortler, and H. Hoppe, Fast exact and approximate geodesics on meshes, ACM Trans. Graph., vol. 24, no. 3, pp. 553–560, 2005.

Crossref Google Scholar
[22]

R. Kimmel and J. A. Sethian, Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci. USA, vol. 95, no. 15, pp. 8431–8435, 1998.

Crossref Google Scholar
[23]

D. L. Chopp, Some improvements of the fast marching method, SIAM J. Sci. Comput., vol. 23, no. 1, pp. 230–244, 2001.

Crossref Google Scholar
[24]

N. Yuan, P. Wang, W. Meng, S. Chen, J. Xu, S. Xin, Y. He, and W. Wang, A variational framework for curve shortening in various geometric domains, IEEE Trans. Vis. Comput. Graph., vol. 29, no. 4, pp. 1951–1963, 2023.

Crossref Google Scholar
[25]

R. Liu, F. Xiao, and W. Meng, Efficiently computing shortest paths on curved surfaces with Newton’s method, Eng. Lett., vol. 31, no. 1, p. 338, 2023.

Google Scholar
[26]

M. Lanthier, A. Maheshwari, and J. R. Sack, Approximating shortest paths on weighted polyhedral surfaces, Algorithmica, vol. 30, no. 4, pp. 527–562, 2001.

Crossref Google Scholar
[27]

X. Ying, X. Wang, and Y. He, Saddle vertex graph (SVG): A novel solution to the discrete geodesic problem, ACM Trans. Graph., vol. 32, no. 6, p. 170, 2013.

Crossref Google Scholar
[28]

W. Meng, S. Xin, C. Tu, S. Chen, Y. He, and W. Wang, Geodesic tracks: Computing discrete geodesics with track-based steiner point propagation, IEEE Trans. Vis. Comput. Graph., vol. 28, no. 12, pp. 4887–4901, 2022.

Crossref Google Scholar
[29]
L. Aleksandrov, M. Lanthier, A. Maheshwari, and J. R. Sack, An ε—approximation algorithm for weighted shortest paths on polyhedral surfaces, in Proc. 6 th Scandinavian Workshop on Algorithm Theory, Stockholm, Sweden, 1998, pp. 11–22.
Crossref
[30]
M. Lanthier, A. Maheshwari, and J. R. Sack, Approximating weighted shortest paths on polyhedral surfaces, in Proc. Thirteenth Annu. Symp. Computational Geometry, Nice, France, 1997, pp. 485–486.
Crossref
[31]

L. Aleksandrov, A. Maheshwari, and J. R. Sack, Determining approximate shortest paths on weighted polyhedral surfaces, J. ACM, vol. 52, no. 1, pp. 25–53, 2005.

Crossref Google Scholar
[32]

C. Y. Xu, J. R. Li, Q. H. Wang, and G. H. Hu, Contour parallel tool path planning based on conformal parameterisation utilising mapping stretch factors, Int. J. Prod. Res., vol. 57, no. 1, pp. 1–15, 2019.

Crossref Google Scholar
[33]

X. Liang, G. Meng, Y. Xu, and H. Luo, A geometrical path planning method for unmanned aerial vehicle in 2D/3D complex environment, Intel. Serv. Robot., vol. 11, no. 3, pp. 301–312, 2018.

Crossref Google Scholar
[34]

J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou, The discrete geodesic problem, SIAM J. Comput., vol. 16, no. 4, pp. 647–668, 1987.

Crossref Google Scholar
[35]

P. Bose, A. Maheshwari, C. Shu, and S. Wuhrer, A survey of geodesic paths on 3D surfaces, Computational Geometry, vol. 44, no. 9, pp. 486–498, 2011.

Crossref Google Scholar
[36]
K. Crane, M. Livesu, E. Puppo, and Y. Qin, A survey of algorithms for geodesic paths and distances, arXiv preprint arXiv: 2007.10430, 2020.
[37]
J. Chen and Y. Han, Shortest paths on a polyhedron, in Proc. Sixth Annu. Symp. Computational Geometry, Berkley, CA, USA, 1990, pp. 360–369.
Crossref
[38]

Y. Qin, X. Han, H. Yu, Y. Yu, and J. Zhang, Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation, ACM Trans. Graph., vol. 35, no. 4, p. 125, 2016.

Crossref Google Scholar
[39]

C. Xu, T. Y. Wang, Y. J. Liu, L. Liu, and Y. He, Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes, IEEE Trans. Vis. Comput. Graph., vol. 21, no. 7, pp. 822–834, 2015.

Crossref Google Scholar
[40]

J. Du, Y. He, Z. Fang, W. Meng, and S. Q. Xin, On the vertex-oriented triangle propagation (VTP) algorithm: Parallelization and approximation, Comput.-Aided Des., vol. 130, p. 102943, 2021.

Crossref Google Scholar
[41]

K. Crane, C. Weischedel, and M. Wardetzky, Geodesics in heat: A new approach to computing distance based on heat flow, ACM Trans. Graph., vol. 32, no. 5, p. 152, 2013.

Crossref Google Scholar
[42]

O. Weber, Y. S. Devir, A. M. Bronstein, M. M. Bronstein, and R. Kimmel, Parallel algorithms for approximation of distance maps on parametric surfaces, ACM Trans. Graph., vol. 27, no. 4, p. 104, 2008.

Crossref Google Scholar
[43]
S. Q. Xin, X. Ying, and Y. He, Constant-time all-pairs geodesic distance query on triangle meshes, in Proc. ACM SIGGRAPH Symp. Interactive 3D Graphics and Games, Costa Mesa, CA, USA, 2012, pp. 31–38.
Crossref
[44]

Y. Y. Adikusuma, Z. Fang, and Y. He, Fast construction of discrete geodesic graphs, ACM Trans. Graph., vol. 39, no. 2, p. 14, 2020.

Crossref Google Scholar
[45]

B. Pham, Offset curves and surfaces: A brief survey, Comput.-Aided Des., vol. 24, no. 4, pp. 223–229, 1992.

Crossref Google Scholar
[46]

T. Rausch, F. E. Wolter, and O. Sniehotta, Computation of medial curves on surfaces, The Mathematics of Surfaces, vol. 7, pp. 43–68, 1997.

Google Scholar
[47]
Z. M. Chen, Y. G. Chen, and F. J. Liang, A new offset approach for curves on triangle mesh surfaces, in Proc. 2006 Int. Technology and Innovation Conf., Hangzhou, China, 2006, pp. 202–208.
Crossref
[48]

V. D. Holla, K. G. Shastry, and B. G. Prakash, Offset of curves on tessellated surfaces, Comput.-Aided Des., vol. 35, no. 12, pp. 1099–1108, 2003.

Crossref Google Scholar
[49]

A. Boschetto and L. Bottini, Triangular mesh offset aiming to enhance fused deposition modeling accuracy, Int. J. Adv. Manuf. Technol., vol. 80, no. 1, pp. 99–111, 2015.

Crossref Google Scholar
[50]
M. De Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry : Algorithms and Applications. 2nd ed. Berlin, Heidelberg: Springer, 2000.
Crossref
[51]
Q. Zhou and A. Jacobson, Thingi10K: A dataset of 10, 000 3D-printing models, arXiv preprint arXiv: 1605.04797, 2016.
[52]

S. H. Lo, A new mesh generation scheme for arbitrary planar domains, Int. J. Numer. Methods Eng., vol. 21, no. 8, pp. 1403–1426, 1985.

Crossref Google Scholar
[53]

J. Xu, Y. Sun, and S. Wang, Tool path generation by offsetting curves on polyhedral surfaces based on mesh flattening, Int. J. Adv. Manuf. Technol., vol. 64, nos. 9–12, pp. 1201–1212, 2013.

Crossref Google Scholar
Tsinghua Science and Technology
Volume 30 Issue 4,
August 2025
Pages 1744-1761
DOI: 10.26599/TST.2024.9010239
Cite this article:
Meng W, Yu H, Geng Y, et al. An Efficient Algorithm for Approximate Polyline-Sourced Offset Computation on Triangulated Surfaces. Tsinghua Science and Technology, 2025, 30(4): 1744-1761. https://doi.org/10.26599/TST.2024.9010239
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return