Glift: Generic Data Structures for Graphics Hardware

This thesis presents Glift, an abstraction and generic template library for parallel, random-access data structures on graphics hardware. We demonstrate that a data structure abstraction for graphics processing units (GPUs) can simplify the description of new and existing data structures, stimulate development of complex GPU algorithms, and perform equivalently to hand-coded implementations. Glift defines the GPGPU computation model in terms of parallel iteration over data structure elements and demonstrates iteration over complex structures. This thesis also presents a case that future interactive rendering solutions will be an inseparable mix of general-purpose, parallel GPU programming (GPGPU) and traditional graphics programming. We describe the use of Glift in four novel interactive rendering algorithms with complex data structure and iterator requirements: octree 3D paint, adaptive shadow maps, resolution-matched shadow maps and a heat-diffusion depth-of-field algorithm