Fast KNN in Screenspace on GPGPU

Information

• Publication Type: Bachelor Thesis
• Workgroup(s)/Project(s):
  • Rendering and Modeling
• Date: April 2016
• Date (Start): 5. March 2014
• Date (End): 30. June 2014
• Matrikelnummer: e1027470
• First Supervisor: Stefan Ohrhallinger
• Second Supervisor: Stefan Ohrhallinger
• Keywords: cuda, gpu, nearest neighbor search, knn, screen space

Abstract

Virtualization of realworld objects and scenes became very popular in recent years due to af- fordable laser-scanning technology. Nowadays it’s not only possible to capture static frames but also realtime frame sequences. Rendering of those captures is difficult because visually ap- pealing renderings involve the computation of local surface reconstruction from pointclouds and therefore a lot of preprocessing. This is usually not possible in realtime. One important processing step is the computation of nearest neighbours for each 3d-point. The neighbourhood information is not only used for normal reconstruction and local surface estimation, but can also be utilized for collision detection. In this paper we present a method for computing the k-nearest-neighbor sets for pointclouds in realtime. To achieve high frame rates we parallelize the algorithm on the GPU, using the Nvidia CUDA parallel computation framework. Furthermore computations are limited to op- erate in screen-space, to reduce computational complexity even further, and effectively prevent rendering invisible geometry. We also utilize the invented FastKnn algorithm to estimate local surface reconstruction for splat rendering of pointclouds in realtime and show how it compares to a state of the art algorithm.

Additional Files and Images

Weblinks

• SVN repository

BibTeX

@bachelorsthesis{schoerkhuber_dominik-2016-baa,
  title =      "Fast KNN in Screenspace on GPGPU",
  author =     "Dominik Sch\"{o}rkhuber",
  year =       "2016",
  abstract =   "Virtualization of realworld objects and scenes became very
               popular in recent years due to af- fordable laser-scanning
               technology. Nowadays it’s not only possible to capture
               static frames but also realtime frame sequences. Rendering
               of those captures is difficult because visually ap- pealing
               renderings involve the computation of local surface
               reconstruction from pointclouds and therefore a lot of
               preprocessing. This is usually not possible in realtime. One
               important processing step is the computation of nearest
               neighbours for each 3d-point. The neighbourhood information
               is not only used for normal reconstruction and local surface
               estimation, but can also be utilized for collision
               detection. In this paper we present a method for computing
               the k-nearest-neighbor sets for pointclouds in realtime. To
               achieve high frame rates we parallelize the algorithm on the
               GPU, using the Nvidia CUDA parallel computation framework.
               Furthermore computations are limited to op- erate in
               screen-space, to reduce computational complexity even
               further, and effectively prevent rendering invisible
               geometry. We also utilize the invented FastKnn algorithm to
               estimate local surface reconstruction for splat rendering of
               pointclouds in realtime and show how it compares to a state
               of the art algorithm.",
  month =      apr,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  keywords =   "cuda, gpu, nearest neighbor search, knn, screen space",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2016/schoerkhuber_dominik-2016-baa/",
}