Fast Approximate Geodesic Paths on Triangle Mesh

被引：11

作者：

Tang, Jie ^{[1
]}

Wu, Gang-Shan ^{[1
]}

Zhang, Fu-Yan ^{[1
]}

Zhang, Ming-Min ^{[2
]}

机构：

[1] Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210093, Jiangsu, Peoples R China

[2] Zhejiang Univ, Sch Comp Sci, Hangzhou 310027, Zhejiang, Peoples R China

来源：

INTERNATIONAL JOURNAL OF AUTOMATION AND COMPUTING | 2007年 / 4卷 / 01期

关键词：

Triangle mesh; geodesic path; virtual reality;

D O I：

10.1007/s11633-007-0008-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a new algorithm to compute a geodesic path over a triangle mesh. Based on Novotni's propagating wavefront method which is similar to the well known Dijkstra algorithm, we made some improvements which Novotni had missed and we also gave the method to find out the geodesic path which Novotni had not. It can handle both convex and non-convex surfaces or even with boundaries. Experiment results show that our method works very well both in efficiency and precision.

引用

页码：8 / 13

页数：6

共 14 条

[1] Shortest paths on a polyhedron .1. Computing shortest paths [J].

Chen, JD ;

Han, YJ .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1996, 6 (02) :127-144

[2]

Hilaga M, 2001, COMP GRAPH, P203, DOI 10.1145/383259.383282

[3] Approximate shortest path on a polyhedral surface and its applications [J].

Kanai, T ;

Suzuki, H .

COMPUTER-AIDED DESIGN, 2001, 33 (11) :801-811

[4]

Kaneva B., 2000, Proceedings of the 12th Annual Canadian Conference on Computational Geometry, P139

[5]

Kapoor S., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P770, DOI 10.1145/301250.301449

[6] Hierarchical mesh decomposition using fuzzy clustering and cuts [J].

Katz, S ;

Tal, A .

ACM TRANSACTIONS ON GRAPHICS, 2003, 22 (03) :954-961

[7] Computing geodesic paths on manifolds [J].

Kimmel, R ;

Sethian, JA .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1998, 95 (15) :8431-8435

[8] Computing geodesics on triangular meshes [J].

Martínez, D ;

Velho, L ;

Carvalho, PC .

COMPUTERS & GRAPHICS-UK, 2005, 29 (05) :667-675

[9] THE DISCRETE GEODESIC PROBLEM [J].

MITCHELL, JSB ;

MOUNT, DM ;

PAPADIMITRIOU, CH .

SIAM JOURNAL ON COMPUTING, 1987, 16 (04) :647-668

[10]

Novotni M, 2002, WSCG'2002, VOLS I AND II, CONFERENCE PROCEEDINGS, P341

← 1 2 →