Efficient Spatial Binning on the GPU

Christopher Oat, Joshua Barczak, Jeremy Shopf
AMD, Inc.
AMD Technical Report, February 2009


   title={Efficient Spatial Binning on the GPU},

   author={Oat, C. and Barczak, J. and Shopf, J.},


   publisher={SIGGRAPH Asia}


Download Download (PDF)   View View   Source Source   



We present a new technique for sorting data into spatial bins or buckets using a graphics processing unit (GPU). Our method takes unsorted point data as input and scatters the points, in sorted order, into a set of bins. This is a key operation in the construction of spatial data structures, which are essential for applications such as particle simulation or collision detection. Our technique achieves better performance scaling than previous methods by exploiting geometry shaders to progressively trim the size of the working set. We also leverage predicated rendering functionality to allow early termination without CPU/GPU synchronization. Furthermore, unlike previous techniques, our method can guarantee sorted output without requiring sorted input. This allows our method to be used to implement a form of bucket sort using the GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: