Visibility Analysis in a Point Cloud based on the Medial Axis Transform

Abstract

This thesis proposes a novel medial axis transform (MAT) based method to achieve visibility analysis in a point cloud. There are several advantages of this MAT based method. This method avoids surface reconstruction from a point cloud. It also works for the situation when there is surface missing in the input point cloud. For different point cloud datasets such as point cloud generated from meshes, AHN3 point cloud and point cloud generated from dense image matching, this method successfully deliver decent visibility result for all of them. The main challenge overcome in this thesis is the interior and exterior MAT separation. Two approaches, normal reorientation approach and bisector based approach are experimented in the thesis to separate MAT. The normal reorientation approach only works for point cloud generated from meshes. The bisector based approaches works for all the datasets testes. It successfully separates the interior and exterior MAT when there is surfacing missing. To speed up of the query process, spatial index is generated for interior MAT. In this thesis, two spatial indices are implemented, KD-Tree and R-Tree. Due to the limitation of my KD-Tree implementation, the KD-Tree does not improve the running speed obvious. There is a room to improve the KD-Tree implementation. The R-Tree achieves sharply improvement on running time of the queries. For 51567 points, the query based on R-Tree finished in 1880 ms. In a word, this thesis proposed an efficient MAT based method of visibility analysis in a point cloud.