Fast Radial Search for Progressive Photon Mapping

Information

• Publication Type: Bachelor Thesis
• Workgroup(s)/Project(s):
  • Superhumans - Walking Through Walls
• Date: September 2021
• Date (Start): 15. September 2021
• Date (End): 15. March 2022
• Matrikelnummer: 11777774
• First Supervisor: Stefan Ohrhallinger
• Keywords: k-nearest neighbors, photon mapping, parallel optimization

Abstract

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". Tasks

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.

Requirements

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

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

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

Additional Files and Images

Weblinks

No further information available.

BibTeX

@bachelorsthesis{rait_alexius-2021-baa,
  title =      "Fast Radial Search for Progressive Photon Mapping",
  author =     "Alexius Rait",
  year =       "2021",
  abstract =   "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". Tasks      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.  Requirements  Good optimizing
               skills. Shader or CUDA experience is a bonus. Environment 
               C/C++ and CUDA, platform-independent, LGPL license  A bonus
               of €500 if completed to satisfaction within an agreed
               time-frame of 6 months.",
  month =      sep,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Research Unit of Computer Graphics, Institute of Visual
               Computing and Human-Centered Technology, Faculty of
               Informatics, TU Wien ",
  keywords =   "k-nearest neighbors, photon mapping, parallel optimization",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2021/rait_alexius-2021-baa/",
}