Phan Thanh An"Straightest Geodesics for Finding Shortest Paths inside a Triangle Sequence in 3D" We present an efficient algorithm for finding the exact shortest path between two points inside a triangle sequence in three-dimensional space. Firstly, the concept of "funnels" inside a sequence of faces in 3D that is a generalization of funnels in 2D is introduced. Secondly, the method of orienting straightest geodesics for determining funnels is presented. It includes the concepts of "final straightest geodesics" and "orienting straightest geodesics" (the special cases of straightest geodesics) inside a so-called extended funnel. Consequently, the exact shortest path is determined by paths of orienting straightest geodesics of the funnels and a final straightest geodesic of the final funnel. It takes O(n^{2}) time without planar unfolding and is visualized by JavaView software. Related work: Xin & Wang's method (Computer-Aided Design, V.39, 2007) takes O(n^{2}) complexity, but using planar unfolding for the triangle sequence. Authors: P.T. An (Hanoi), D.T. Giang (Lisbon), T.V. Hoai (HCM City), H. X. Phu (Hanoi), K. Polthier (Berlin). |