Fast kNN in Screen Space on GPU

Information

Abstract

A common problem in computer science is to construct a spatial data structure (octree, kd-tree) and use it to search for k-nearest neighbors (kNN). In surface reconstruction from dynamic points (real-time), both construction and search time are critical. As points on a surface are a sparse distribution in 3D, this can be exploited by mapping them into screen space (2D), as shown in "Auto-splats" (Preiner 2012). Our approach is to also exploit spatial coherence in screen space to find kNN for points. The performance is maximized by a CUDA implementation designed to minimize memory-boundness. An preliminary implementation exists which constructs a packed quadtree and reads kNN from a quadtree node density estimate. A few improvements have to be made to optimize performance and to analyze results.

Additional Files and Images

Additional images and videos

Additional files

Weblinks

No further information available.

BibTeX

@bachelorsthesis{reinwald-2017-baa,
  title =      "Fast kNN in Screen Space on GPU",
  author =     "Siegfried Reinwald",
  year =       "2017",
  abstract =   "A common problem in computer science is to construct a
               spatial data structure (octree, kd-tree) and use it to
               search for k-nearest neighbors (kNN). In surface
               reconstruction from dynamic points (real-time), both
               construction and search time are critical. As points on a
               surface are a sparse distribution in 3D, this can be
               exploited by mapping them into screen space (2D), as shown
               in "Auto-splats" (Preiner 2012). Our approach is to also
               exploit spatial coherence in screen space to find kNN for
               points. The performance is maximized by a CUDA
               implementation designed to minimize memory-boundness. An
               preliminary implementation exists which constructs a packed
               quadtree and reads kNN from a quadtree node density
               estimate. A few improvements have to be made to optimize
               performance and to analyze results.",
  month =      mar,
  note =       "1",
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  keywords =   "k-nearest neighbors, surface reconstruction, parallel
               optimization",
  URL =        "/research/publications/2017/reinwald-2017-baa/",
}