Information
- Publication Type: Bachelor Thesis
- Workgroup(s)/Project(s):
- Date: March 2017
- Date (to): 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
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 = "https://www.cg.tuwien.ac.at/research/publications/2017/reinwald-2017-baa/",
}