Jump flooding algorithm on graphics hardware and its applications

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.