This paper studies jump flooding as an algorithmic paradigm in general-purpose computation with GPUs. As an example application of jump flooding, the paper discusses a constant time algorithm on the GPU to compute an approximation to the Voronoi diagram of a given set of seeds in a 2D grid. The errors due to the differences between the approximation and the actual Voronoi diagram are hardly noticeable to the naked eye in all presented experiments. The same approach can also compute in constant time an approximation to the distance transform of a set of seeds in a 2D grid. In practice, such constant time algorithm is useful to many interactive applications involving, for example, rendering and image processing. Besides the experimental evidence, this paper also confirms quantitatively the effectiveness of jump flooding by analyzing the occurrences of errors. The analysis is a showcase of insights to the jump flooding paradigm, and may be of independent interest to other applications of jump flooding. (Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform. Guodong Rong and Tiow-Seng Tan. To appear in 2006 SIGGRAPH Symposium on Interactive 3D Graphics and Games. [I3D 2006] )

## Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform

March 12th, 2006## Glift: Generic, Efficient, Random-Access GPU Data Structures

February 10th, 2006This paper presents Glift, an abstraction and generic template library for defining complex, random-access graphics processor (GPU) data structures. Like modern CPU data structure libraries, Glift enables GPU programmers to separate algorithms from data structure definitions; thereby greatly simplifying algorithmic development and enabling reusable and interchangeable data structures. We characterize a large body of previously published GPU data structures in terms of our abstraction and present several new GPU data structures. The structures, a stack, quadtree, and octree, are explained using simple Glift concepts and implemented using reusable Glift components. We also describe two applications of these structures not previously demonstrated on GPUs: adaptive shadow maps and octree 3D paint. Lastly, we show that our example Glift data structures perform comparably to handwritten implementations while requiring only a fraction of the programming effort. (Glift: Generic, Efficient, Random-Access GPU Data Structures. Aaron E. Lefohn, Joe Kniss, Robert Strzodka, Shubhabrata Sengupta, John D. Owens. ACM Transactions on Graphics, 25(1), Jan. 2006.)

## gDEBugger V2.3 Adds OpenGL Function Calls Statistics Information

February 10th, 2006gDEBugger is an OpenGL debugger and profiler that traces application activity on top of the OpenGL API and lets programmers see what is happening within the graphics system to help find bugs and optimize application performance. The new V2.3 introduces a Calls Statistics view that allows viewing the number of times each OpenGL function call was executed in the previous frame and its percentage of the total functions execution count. This information helps programmers locate redundant OpenGL function calls, state changes, etc. V2.3 also adds support for GL_ARB_texture_rectangle and GL_NV_texture_rectangle extensions. (http://www.gremedy.com)

## Dynamic Particle Coupling for GPU-based Fluid Simulation

February 10th, 2006This paper by Kolb and Cuntz from the computer graphics group of the University of Siegen describes a 3D flow simulation approach on the GPU. The flow simulation is modeled using the so-called *Smoothed Particle Hydrodynamics *approach. The presented technique combines the particle simulation, presented by Kipfer et.al. and Kolb et.al. at Graphics-Hardware 2004, with a grid based approach. 3D grids are used to store intermediate flow quantities that are distributed by the particles in their neighborhood. MRT is used to compute the contribution of a single particle to four texture slices simultaneously. Blending the individual contribution of all particles in 16bit textures yields the final 3D force fields used for the simulation of particle motion. (Dynamic Particle Coupling for GPU-based Fluid Simulation)

## Accelerator: A GPGPU system from Microsoft Research

January 17th, 2006This paper describes Accelerator, a system that simplifies the programming of GPUs for general-purpose uses. Accelerator provides a high-level data-parallel programming model as a library that is available from a conventional imperative programming language (C#). The library translates the data-parallel operations on-the-fly to optimized GPU pixel shader code and API calls. The authors describe the compilation techniques used to produce optimized pixel shader code, and demonstrate the effectiveness of the approach by providing results for a set of compute-intensive benchmarks drawn from image processing and computer vision. The speeds of the Accelerator versions of the benchmarks are typically within 50% of the speeds of hand-written pixel shader code. Some benchmarks significantly outperform C versions running on a CPU by up to 18x. (Accelerator: simplified programming of graphics processing units for general-purpose uses via data-parallelism. David Tarditi, Sidd Puri, Jose Oglesby. Microsoft Research Technical Report MSR-TR-2005-184. December 2005.)

## Generic Mesh Refinement On GPU

January 15th, 2006This paper by Boubekeur and Schlick of the INRIA IPARLA Team describes a simple and easy-to-integrate method for “on-GPU refinement” (tesselation + displacement), adapted to any programmable GPU. This solution to the refinement problem reduces the usual CPU->GPU bottleneck and memory consumption by using instantiation over a template refinement pattern. This approach is usuful for rendering objects that are represented as a simple mesh plus a detailed displacement requiring deep tesselation (high-res maps, smooth surfaces, procedural displacement, etc). (Generic Mesh Refinement on GPU. Tamy Boubekeur and Christophe Schlick. *Proceedings of Graphics Hardware 2005*).

## Ray Tracing News vol. 18 no. 1

December 13th, 2005Eric Haines has released the latest issue of his long-running “Ray Tracing News”. It’s chock full of news and interesting discussion about ray tracing implementation and optimization, kd-trees, and more. It also includes links to various ray-tracing work being done on GPUs. (Ray Tracing News volume 18, no. 1)

## gDEBugger Adds On-the-Fly Shader Editing, Linking and Validation

December 6th, 2005gDEBugger, an OpenGL debugger and profiler, traces application activity on top of the OpenGL API, letting programmers see what is happening within the graphics system implementation to find bugs and optimize application performance. The new V2.2 introduces a shader “Edit and Continue” ability which allows you to edit, save and compile shader source code, link and validate programs “on the fly”. This feature saves developer time required for rebuilding and re-running the debugged application. This version also adds support for 8 additional OpenGL extensions. (http://www.gremedy.com)

## GPU LU Decomposition Code Released

November 16th, 2005The code from the paper “LU-GPU: Algorithms for Dense Linear Systems on Graphics Hardware” has been released. The API is based on LAPACK and should be easy for anyone to use. (LUGPULIB)

## GPGPU Course Notes from IEEE Visualization 2005

November 13th, 2005The complete course notes have been posted for the full-day GPGPU course held at IEEE Visualization 2005. The course titled, “GPGPU: General Purpose Computing on Graphics Processors” was held on Sunday, October 23rd, 2005 in Minneapolis, Minnesota. The course begins with the architectural, economic, and programmatic motivations behind GPGPU. It then introduces the GPGPU programming model and describes GPGPU languages (Brook, Scout) as well as high-level data structures. Mathematical and algorithmic primitives are then presented, followed by descriptions of many of the low-level technical details required for effective real-world GPGPU programming. The course concludes with several case studies and a disscusion of the future architectual, application, and research possibilities for GPGPU. The course organizer was Aaron Lefohn, and the presenters were Ian Buck, Aaron Lefohn, John Owens, Tim Purcell, Patrick McCormick, and Robert Strzodka. ( “GPGPU: General

Purpose Computing on Graphics Processors,” IEEE Visualization 2005)