Optimization of Raycasting Algorithms on dynamic surface point cloud using GPU

This Bachelorthesis is about calculating the intersection between a ray and a surface that is represented by a 3D point cloud. An algorithm that solves this task was developed and implemented in C++ and CUDA. Both implementations were examined based on the runtime of an intersection calculation to find out if they allow realtime intersection calculation.

Description

Point clouds allow to represent complete environments in 3D and sensors like the Microsoft Kinect can record point clouds of the vicinty in real time. This can be used in robotics for instance to gather information about the vicinity of the robot. Another use case is VR where a virtual scene could be portrayed by a point cloud. In both cases it could be useful to determine the intersection between a ray and the point cloud of the vicinity. You could for instance mark an object by pointing a virtual laser pointer at it or check whether the line of sight between two objects is blocked by an obstacle. Because the intersection between a ray and a point cloud is calculated the topic of this thesis is closely related to ray tracing and especially ray tracing on point clouds. There are already a few approaches for ray tracing on point clouds and the most promising for the scenario of this thesis is the surface splatting approach. However, the problem with ray tracing approaches is that they were made for static point clouds. For that reason the surface splatting approach was adapted in this thesis for single ray casts on dynamic point clouds. Moreover, dynamic point clouds complicate the usage of acceleration data structures, because they have to be updated every time the point cloud changes. Consequently, this thesis examines whether the usage of such a data structure can be omitted by parallelising the intersection calculation with CUDA. For that reason a CUDA implemention is compared to a sequential CPU implementation. Additionally it is assumed, that no surface normals are available.

Results

The result of this thesis is that the CPU implemenation of the algorithm allows realtime calculation of intersections with point clouds up to 700000 points while the CUDA implementation can handle point clouds with up to 2.5 * 10^6 points. The image below shows a graph of the time necessray for a single intersection calculation in relation to the point cloud size. Since this bachelor thesis deals with dynamic point clouds, the acceleration data structures creation time is included in the graph of the CPU implementation.

Files

Full version of the bachelor thesis (German only)

Here is a movie, that shows the intersection calculation between a ray and a point cloud. The point cloud is streamed from a Microsoft Kinect:

License

This original work is copyright by University of Bremen.
Any software of this work is covered by the European Union Public Licence v1.2. To view a copy of this license, visit eur-lex.europa.eu.
The Thesis provided above (as PDF file) is licensed under Attribution-NonCommercial-NoDerivatives 4.0 International.
Any other assets (3D models, movies, documents, etc.) are covered by the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. To view a copy of this license, visit creativecommons.org.
If you use any of the assets or software to produce a publication, then you must give credit and put a reference in your publication.
If you would like to use our software in proprietary software, you can obtain an exception from the above license (aka. dual licensing). Please contact zach at cs.uni-bremen dot de.