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
id sg-ntu-dr.10356-54871
record_format dspace
spelling sg-ntu-dr.10356-548712023-03-04T00:37:17Z Efficient and practical algorithms for discrete geodesics Xiang, Ying He Ying School of Computer Engineering Game Lab DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics 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. DOCTOR OF PHILOSOPHY (SCE) 2013-09-30T09:18:37Z 2013-09-30T09:18:37Z 2012 2012 Thesis Xiang, Y. (2013). Efficient and practical algorithms for discrete geodesics. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/54871 10.32657/10356/54871 en 166 p. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics
spellingShingle DRNTU::Engineering::Computer science and engineering::Computing methodologies::Computer graphics
Xiang, Ying
Efficient and practical algorithms for discrete geodesics
description 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.
author2 He Ying
author_facet He Ying
Xiang, Ying
format Theses and Dissertations
author Xiang, Ying
author_sort Xiang, Ying
title Efficient and practical algorithms for discrete geodesics
title_short Efficient and practical algorithms for discrete geodesics
title_full Efficient and practical algorithms for discrete geodesics
title_fullStr Efficient and practical algorithms for discrete geodesics
title_full_unstemmed Efficient and practical algorithms for discrete geodesics
title_sort efficient and practical algorithms for discrete geodesics
publishDate 2013
url https://hdl.handle.net/10356/54871
_version_ 1759852986037698560