کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952742 | 1442539 | 2017 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Discrete geodesic graph (DGG) for computing geodesic distances on polyhedral surfaces
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
گرافیک کامپیوتری و طراحی به کمک کامپیوتر
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and ε>0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has O(nε) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error O(ε). Computational results show that the actual error is less than 0.6ε on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) - another graph based method for discrete geodesics - in terms of graph size, accuracy control and runtime performance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Aided Geometric Design - Volumes 52â53, MarchâApril 2017, Pages 262-284
Journal: Computer Aided Geometric Design - Volumes 52â53, MarchâApril 2017, Pages 262-284
نویسندگان
Xiaoning Wang, Zheng Fang, Jiajun Wu, Shi-Qing Xin, Ying He,