Fast kNN in screen space on GPU

Description

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.

Task

• Optimize an existing CUDA implementation which reads coalesced points from a packed buffer.
• Read kNN candidates grouped of close points to minimize global memory accesses.
• Clean up code for release as an open source project.

Requirements

Good optimizing skills. Experience in shader programming. CUDA experience is a bonus.

Environment

C/C++ and CUDA, platform-independent

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