Related Experiment Video
Updated: Jun 17, 2026

Extracting Metrics for Three-dimensional Root Systems: Volume and Surface Analysis from In-soil X-ray Computed Tomography Data
Published on: April 26, 2016
A fast sweeping method for computing geodesics on triangular manifolds
Song-Gang Xu1, Yun-Xiang Zhang, Jun-Hai Yong
1Institute of Computer Graphics and Computer Aided Design Laboratory (CG&CAD), School of Software, Tsinghua University, Room 824, The Main Building, Beijing 100084, PR China. xsg06@mails.tsinghua.edu.cn
Abstract:
A wide range of applications in computer intelligence and computer graphics require computing geodesics accurately and efficiently. The fast marching method (FMM) is widely used to solve this problem, of which the complexity is O(N\log N), where N is the total number of nodes on the manifold. A fast sweeping method (FSM) is proposed and applied on arbitrary triangular manifolds of which the complexity is reduced to O(N). By traversing the undigraph, four orderings are built to produce two groups of interfering waves, which cover all directions of characteristics. The correctness of this method is proved by analyzing the coverage of characteristics. The convergence and error estimation are also presented.
More Related Videos
Related Concept Videos
Quadric Surfaces
Divergence Theorem in 3D Space
Tangent Planes to Surfaces
Tangent Planes to a Parametric Surface
Parametric Surfaces
Tangent Planes to Level Surfaces

