Efficient and practical algorithms for discrete geodesics

Computing exact geodesic distance plays an important role in many graphics applications. Many research studies have been undertaken in this area since the 1980s. However, the existing geodesic algorithms are not practical for large-scale models or time-critical applications. First, the existing algo...

Full description

Saved in:
Bibliographic Details
Main Author: Xiang, Ying
Other Authors: He Ying
Format: Theses and Dissertations
Language:English
Published: 2013
Subjects:
Online Access:https://hdl.handle.net/10356/54871
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:Computing exact geodesic distance plays an important role in many graphics applications. Many research studies have been undertaken in this area since the 1980s. However, the existing geodesic algorithms are not practical for large-scale models or time-critical applications. First, the existing algorithms compute exact geodesic in a serial manner due to the lack of a parallel structure. The computation of geodesic on a large-scale model could be very time-consuming. Second, the widely studied single-source all-destination geodesic algorithms are not elegant for all-pair geodesic queries. Thus, the efficiency and practicality of geodesic computation remain a challenge. To tackle these issues, we systematically studied the discrete geodesic problem. My study focuses on all-pairs geodesic distance, geodesic offsets, and parallel geodesic algorithm on modern GPUs. Furthermore, we propose the world’s first intrinsic and parallel Poisson-disk sampling method on surfaces, which is a time-critical application of discrete geodesics.