Efficient Histogram Generation Using Scattering on GPUs

Thorsten Scheuermann Justin Hensley
Graphics Product Group
Advanced Micro Devices Inc.
1st page screenshot


We present an efficient algorithm to compute image histograms entirely on the GPU. Unlike previous implementations that use a gather approach, we take advantage of scattering data through the vertex shader and of high-precision blending available on modern GPUs. This results in fewer operations executed per pixel and speeds up the computation.

Our approach allows us to create histograms with arbitrary numbers of buckets in a single rendering pass, and avoids the need for any communication from the GPU back to the CPU: The histogram stays in GPU memory and is immediately available for further processing.

We discuss solutions to dealing with the challenges of implementing our algorithm on GPUs that have limited computational and storage precision. Finally, we provide examples of the kinds of graphics algorithms that benefit from the high performance of our histogram generation approach.



Download paper (pdf, 2.8MB)
Download video (DivX, 32 MB)