Fast kNN in Screen Space on GPU

Information

• Publication Type: Bachelor Thesis
• Workgroup(s)/Project(s):
  • Real-Time Shape Acquisition with Sensor-Specific Precision
• Date: March 2017
• Date (Start): 21. March 2017
• Date (End): 12. March 2019
• Matrikelnummer: 1126981
• Note: 1
• First Supervisor: Stefan Ohrhallinger
• Keywords: k-nearest neighbors, surface reconstruction, parallel optimization

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

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 =        "https://www.cg.tuwien.ac.at/research/publications/2017/reinwald-2017-baa/",
}