[Back]

S. Marek:
"Normal Estimation of Very Large Point Clouds";
Supervisor: M. Wimmer; Institut für Computergraphik und Algorithmen, 2011.

This diploma thesis introduces methods for external sorting and fast k nearest neighbor searching for very large point clouds. Very large point clouds are datasets that can not be processed in main memory. This leads to certain requirements for any used reconstruction technique. The most important ones are out-of-core memory management and sequential data handling algorithms. The paper "Stream- Processing Points" by Renato Pajarola shows a way to design a framework which allows to process a subset of very large point clouds. A subset is defined as a spatially continuous region holding a predefined number of points. This diploma thesis is based on the aforementioned paper and improves on the stream processing pipeline presented therein. The proposed algorithm for searching the k nearest neighbors has a complexity of O(N log(M)), where N are all points in the point cloud and M are all points in main memory, which is similar to current state of the art algorithms for in-core processed data sets.

Normal estimation, Out-of-Core algorithms, Point-based rendering

http://publik.tuwien.ac.at/files/PubDat_201263.pdf