€500 Fast Radial Search for Progressive Photon Mapping

Bachelor Thesis
Student Project


In many applications, we need to find neighbors in a point cloud for a large number of locations, so we want to be able to do that quickly. This task can be achieved by locating the k-nearest neighbors (kNN) but just querying the interior of a fixed-sized ball - radius search - is faster since we do not have to iteratively adjust the search radius. For fast retrieval of points in 3D, Fast kNN projects the point cloud to a grid, e.g. screen space sized, and packs it densely so that points can be read consecutively from memory (see Bachelor thesis of Reinwald). An example application is described by Hachisuka et al. "Progressive Photon Mapping" and an open source implementation based on that is available here. Projective radial search is also described by Bewley and Upcroft "Advantages of exploiting projection structure for segmenting dense 3D point clouds".


  • Adapt the existing CUDA kNN implementation of Reinwald to a fixed search radius wiith thrust::count to create the packed buffer
  • Optimize the querying code for parallel processing
  • Compare with radius search and photon mapping implementations given above
  • Clean up code for release as an open source project.


Good optimizing skills. Shader or CUDA experience is a bonus.


C/C++ and CUDA, platform-independent, LGPL license

A bonus of €500 if completed to satisfaction within an agreed time-frame of 6 months.


For more information please contact Stefan Ohrhallinger, Michael Wimmer.