Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/12974
Title: Jump flooding algorithm on graphics hardware and its applications
Authors: RONG GUODONG
Keywords: Graphics Hardware, GPGPU, Computational Geometry, Voronoi Diagram, Soft Shadow, Delaunay Triangulation
Issue Date: 1-Mar-2008
Citation: RONG GUODONG (2008-03-01). Jump flooding algorithm on graphics hardware and its applications. ScholarBank@NUS Repository.
Abstract: The graphics processing unit (GPU) has been developing at a very fast pace these few years. More and more researches have been done to utilize the ever increasing computability power of the GPU on general-purpose computations. This thesis proposes a new GPU algorithm -- jump flooding algorithm (JFA). JFA is a new paradigm of communication between pixels on the GPU. It can quickly propagate the information of certain pixels to the others. The speed of JFA is exponentially faster than that of the standard flooding algorithm, and is approximately independent to the input size. In this thesis, we explain the details of JFA and its variants. Some properties of JFA are proven in order to help us to understand this new algorithm better. Using JFA, we present a novel algorithm to compute the Voronoi diagram and the distance transform. This new algorithm is faster than previous ones, and its speed is mainly dependent on the resolution of the texture instead of the input size. According to our analysis and experiments, the error rate of the new algorithm is low enough for most applications. JFA is also applied on the computation of real-time soft shadows. Two purely image-based algorithms, JFA-L and JFA-E, are proposed. Inherited from JFA, the speeds of both JFA-L and JFA-E are similarly dependent on the resolution of the texture instead of the complexity of the scene. This makes them very useful for real-time applications such as games. Based on the discrete Voronoi diagram generated by JFA, we propose a new algorithm to compute the Delaunay triangulation in continuous space. This is the first attempt to use the GPU to solve a geometry problem in continuous space. The speed of the new algorithm exceeds that of the fastest Delaunay triangulation program to date.
URI: http://scholarbank.nus.edu.sg/handle/10635/12974
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Thesis_RGD.pdf2.34 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

623
checked on Dec 16, 2018

Download(s)

242
checked on Dec 16, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.