This University of Texas seminar, taught by Bill Mark, covers recent developments in graphics architectures and programming systems, and explores related topics from general-purpose parallel computation. The seminar also examines the connection between the algorithms used for real-time graphics and the architectures that are chosen to support them. (CS 295t: Real-time Graphics Architectures, Algorithms, and Programming Systems)
Abstract: The Sequenced Convex Subtraction (SCS) algorithm for Constructive Solid Geometry (CSG) sequentially subtracts convex volumes from the z-buffer. This paper presents an improvement to subtraction sequence generation which uses object space overlap information to give O(n) length sequences in the best case and (unchanged) O(n2) sequences in the worst case. (Improved CSG Rendering using Overlap Graph Subtraction Sequences. N. Stewart, G. Leach, S. John. International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia – GRAPHITE 2003, pp. 47-53)
This tutorial was presented at the 2003 Game Developers Conference by Greg James (NVIDIA) and Mark Harris (UNC). Topics included real-time fluid dynamics, reaction-diffusion, and cellular automata running on GPUs. On the web page you will find talk slides, demos, source code, and links relating to simulation and animation on the GPU.
This paper by Goodnight et al. at the University of Virginia demonstrates an implementation on two modern graphics architectures of the multigrid method for solving boundary value problems, such as the systems of partial differential equations that arise in physical simulation problems like fluid flow and heat transfer. (A Multigrid Solver for Boundary Value Problems Using Graphics Hardware. Nolan Goodnight, Gregory Lewin, David Luebke, and Kevin Skadron, University of Virginia Technical Report CS-2003-03 (January 2003).)
This paper by Lefohn et. al. at the University of Utah demonstrates a 3D level-set PDE solver implemented entirely on an ATI Radeon 8500 GPU. It shows that in addition to the basic level-set equations, the second-order mean curvature speed term can be successfully evaluated with only 8-bit textures. The paper demonstrates the solver segmenting the cortical surface from a 256 x 256 x 175 MRI volume and compares the results to a CPU implementation. The object oriented framework with which the solver was built, “Glift,” is also discussed. (A GPU-Based, Three-Dimensional Level Set Solver with Curvature Flow. Aaron Lefohn and Ross Whitaker. University of Utah tech report UUCS-02-017, December, 2002.)
This paper by Mustafa et al. examines the use of graphics hardware as a general purpose geometry engine to compute simplification of large geographic maps in real-time. (Hardware Assisted View Dependent Map Simplification. N. Mustafa, E. Koutsofios, S. Krishnan and S. Venkatasubramanian. 17th Annual ACM Symposium on Computational Geometry, June 2001)
This paper by Guha et al., to appear in the 2003 ACM SIGGRAPH Symposium on Interactive 3D graphics, shows how the shadow mapping operation in the new NVIDIA GeForce4 cards can be viewed as a two-sided depth test in order to do CSG rendering efficiently. The result is an algorithm that can perform a topological sweep over an arrangement of objects in three dimensions. It also shows the first lower bounds on the number of rendering passes required for a hardware-assisted computation. (Application of the Two-Sided Depth Test to CSG Rendering. S. Guha, K. Munagala, S. Krishnan and S. Venkatasubramanian. To appear in the 2003 ACM SIGGRAPH Symposium on Interactive 3D graphics.)
This paper by Krishnan et al. demonstrates a large class of non-parametric statistical analysis problems that can be solved using the graphics hardware. It shows how to do duality transforms and operations in primal and dual geometric planes in a robust way using the graphics pipeline. (Hardware-Assisted Computation of Depth Contours. S. Krishnan, N. Mustafa and S. Venkatasubramanian. 13th ACM-SIAM Symposium on Discrete Algorithms).
This paper by Li et al. of SUNY Stony Brook describes the acceleration of the computation of Lattice-Boltzmann methods on graphics hardware, by grouping particle packets into 2D textures and mapping the Boltzmann equations completely to the rasterization and frame buffer operations. The LBM is then used to simulate smoke.(Implementing Lattice Boltzmann Computation on Graphics Hardware. Wei Li, Xiaoming Wei, and Arie Kaufman. To appear in The Visual Computer.)
Peter Schröder taught a course in the fall of 2002 at the California Institute of Technology called Hacking The GPU. The subject matter of the course revolved around general purpose computation. Assignments included stable fluid simulation and mesh smoothing. The course notes page has some useful links.