Moving least squares

Moving least squares is a method of reconstructing continuous functions from a set of unorganized point samples via the calculation of a weighted least squares measure biased towards the region around the point at which the reconstructed value is requested.

In computer graphics, the moving least squares method is useful for reconstructing a surface from a set of points. Often it is used to create a 3D surface from a point cloud through either downsampling or upsampling.

Definition

Here is a 2D example. The circles are the samples and the polygon is a linear interpolation. The blue curve is a smooth interpolation of order 3.

Consider a function $f: \mathbb{R}^n \to \mathbb{R}$ and a set of sample points $S = \{ (x_i,f_i) | f(x_i) = f_i \}$ where $x_i \in \mathbb{R}^n$ and the $f_i$ 's are real numbers. Then, the moving least square approximation of degree $m$ at the point $x$ is $\tilde{p}(x)$ where $\tilde{p}$ minimizes the weighted least-square error