The main goal of this project is to reconstruct piecewise linear curves and surfaces from unorganized sets of data points, also known as scattered data. This problem arises in a variety of applications, such as in geology, meteorology, cartography, computer graphics, medical imaging, and computer vision, where we may use laser range scanners and other technolologies for collecting sets of sample points from the surfaces of original objects and interpolate/approximate them.

Mathematically, we can formulate the problem we are addressing as follows. Given a set of N sample points p_i=(x_i,y_i,z_i), a function f(x,y,z), such that f(x_i,y_i,z_i) = p_i, is looked for. There is a large range of reconstruction methods, which may be roughly classified into two main classes: global method and local method. In a global method, the function f(x,y,z) at each sample point p_i depends on all of the data points; while in a local method, f(x,y,z) is a piecewise function in the sense that a sample point affects only a sub-domain of the reconstructed shape. In the former approach, one may deal with a huge poorly conditioned system of equations; and in the latter, control of topological consistency is usually a hardest task. For this reason, for very large data sets, local and global methods are often combined to produce reasonable results.

With regard to the function f(x,y,z), we may further distinguish three classes of representations: parametric, implicit (level set approach), and linear. Usually the a-priori known parametric or implicit equations f of the reconstructed surface are embedded in a functional I(f) and the problem is reduced to the determination of parameters of f that optimize I(f), such as energy minimization, distance minimization, and mean square distance minimization. Implicitly, the result represents the fit of the model to the sample data. Completely different from this minimization paradigm, iterative point insertion is applied in most multi-pass algorithms to obtain piecewise linear functions. These algorithms start with an initial piecewise linear approximation and refine the mesh by inserting one or more vertices at each pass under certain criteria, such as threshold and feature vertices.

In our project we investigate an iterative point insertion technique that allows for prevention of self-intersections, noise filtering, and control of the topological type. We believe that, emulating the viscose fluid (radial) flow movement, we may achieve this goal.