Comparing Least Squares Methods for Three-Dimensional Modelling

Abstract

In this thesis we will compare three numerical methods that are used for function approximation based on sampled input points, within the context of three-dimensional modelling, namely the Least Squares, Weighted Least Squares and Moving Least Squares methods. Firstly, we shall explain the workings of the three methods, find the algorithmic complexity of each method and show that finding a bound for the theoretical stability of the methods is difficult, but that we can numerically compute one. Next, we will examine how the methods are used in practice for three-dimensional modelling, by looking at their role in point cloud and polygon soup reconstruction. Finally, we will implement the methods and perform numerical experiments. These show how the accuracy, stability and speed of each method hold up in practice. We also implement the point cloud reconstruction algorithm discussed earlier, which shows us how the methods compare in a three-dimensional modelling situation. We conclude that the methods have different benefits in specific situations, but that further research is needed to definitively state which method is the best for certain applications within the field of three-dimensional modelling.