Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms
Discrete geodesic graph (DGG) is an emerging technique for computing geodesic distances and paths on polyhedral surfaces. DGG has many advantages, such as information reuse, accuracy control, ease of parallelization, good scalability, and guaranteed metric, fast linear time SSAD search. To...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2017
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/70313 |
| _version_ | 1811676473559351296 |
|---|---|
| author | Adikusuma, Yohanes Yudhi Zheng, Fang |
| author2 | He Ying |
| author_facet | He Ying Adikusuma, Yohanes Yudhi Zheng, Fang |
| author_sort | Adikusuma, Yohanes Yudhi |
| collection | NTU |
| description | Discrete geodesic graph (DGG) is an emerging technique for computing geodesic distances and paths on polyhedral surfaces.
DGG has many advantages, such as information reuse, accuracy control, ease of parallelization, good scalability, and guaranteed metric,
fast linear time SSAD search.
To construct DGG, the existing method by Wang et al. firstly finds a large graph with the user-specified accuracy,
and then iteratively prunes the redundant edges from it.
Finally, it adds pseudo vertices and edges to the graph for the poorly sampled regions.
Computational results show that for real-world meshes,
more than 80\% of the candidate edges do not contribute to the final graph and are hereby deleted.
Moreover, for anisotropic meshes, a large amount of pseudo vertices and edges (up to 40 times the original vertex number)
in order to maintain the graph quality, which significantly increases the graph complexity by up to 400x larger.
As a result, the existing indirect approach is conservative and far from optimal.
This paper aims at improving the performance of DGG construction on general meshes models.
Towards this goal, we develop a novel accuracy aware window propagation scheme, allowing us to compute DGG edges in a direct manner.
We prove that the new method greatly improving the time complexity of Wang et al's approach. Our method is memory efficient and it scales very well.
Through extensive evaluation, we demonstrate that our method produces DGGs with comparable or better accuracy than the existing method,
but running up to 2 orders of magnitude faster on common meshes with millions of vertices.In sharp contrast to Wang et al's algorithm,
our algorithm can handle anisotropic meshes well without adding pseudo vertices or edges, thanks to its better understanding of the theoretical underpinning of Discrete Geodesic Graph. This effectively generalize DGG to other highly anisotropic and non-uniform cases of polyhedron with a far better time complexity. This novel improvements also brings DGG to be a better performing algorithm than all existing practical approaches - such as SVG or heat method, not only in term of its SSAD solving time, but also in its initial construction time. |
| first_indexed | 2024-10-01T02:22:02Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/70313 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:22:02Z |
| publishDate | 2017 |
| record_format | dspace |
| spelling | ntu-10356/703132023-03-03T20:27:56Z Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms Adikusuma, Yohanes Yudhi Zheng, Fang He Ying School of Computer Science and Engineering DRNTU::Engineering Discrete geodesic graph (DGG) is an emerging technique for computing geodesic distances and paths on polyhedral surfaces. DGG has many advantages, such as information reuse, accuracy control, ease of parallelization, good scalability, and guaranteed metric, fast linear time SSAD search. To construct DGG, the existing method by Wang et al. firstly finds a large graph with the user-specified accuracy, and then iteratively prunes the redundant edges from it. Finally, it adds pseudo vertices and edges to the graph for the poorly sampled regions. Computational results show that for real-world meshes, more than 80\% of the candidate edges do not contribute to the final graph and are hereby deleted. Moreover, for anisotropic meshes, a large amount of pseudo vertices and edges (up to 40 times the original vertex number) in order to maintain the graph quality, which significantly increases the graph complexity by up to 400x larger. As a result, the existing indirect approach is conservative and far from optimal. This paper aims at improving the performance of DGG construction on general meshes models. Towards this goal, we develop a novel accuracy aware window propagation scheme, allowing us to compute DGG edges in a direct manner. We prove that the new method greatly improving the time complexity of Wang et al's approach. Our method is memory efficient and it scales very well. Through extensive evaluation, we demonstrate that our method produces DGGs with comparable or better accuracy than the existing method, but running up to 2 orders of magnitude faster on common meshes with millions of vertices.In sharp contrast to Wang et al's algorithm, our algorithm can handle anisotropic meshes well without adding pseudo vertices or edges, thanks to its better understanding of the theoretical underpinning of Discrete Geodesic Graph. This effectively generalize DGG to other highly anisotropic and non-uniform cases of polyhedron with a far better time complexity. This novel improvements also brings DGG to be a better performing algorithm than all existing practical approaches - such as SVG or heat method, not only in term of its SSAD solving time, but also in its initial construction time. Bachelor of Engineering (Computer Science) 2017-04-19T04:28:46Z 2017-04-19T04:28:46Z 2017 Final Year Project (FYP) http://hdl.handle.net/10356/70313 en Nanyang Technological University 39 p. application/pdf |
| spellingShingle | DRNTU::Engineering Adikusuma, Yohanes Yudhi Zheng, Fang Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| title | Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| title_full | Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| title_fullStr | Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| title_full_unstemmed | Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| title_short | Fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| title_sort | fast construction of discrete geodesic graph as generalized discrete geodesic approximation algorithms |
| topic | DRNTU::Engineering |
| url | http://hdl.handle.net/10356/70313 |
| work_keys_str_mv | AT adikusumayohanesyudhi fastconstructionofdiscretegeodesicgraphasgeneralizeddiscretegeodesicapproximationalgorithms AT zhengfang fastconstructionofdiscretegeodesicgraphasgeneralizeddiscretegeodesicapproximationalgorithms |