Elastons: Moving Least Squares | Geometry saves the Earth!

I’m jumping a bit ahead in the paper since this is the part I’m currently working on (both understanding and implementing). In this post I’ll quickly cover the basic idea of Elastons as I understand it and continue moving towards the Generalized Moving Least Squares approach presented in the paper.

Elastons

The basic idea of how the function describing the displacement of the object is solved numerically is to evaluate it at certain points in space. These points are at the center of a small volume referred to as an Elaston. One part of the paper deals with how the positions, sizes and orientations of the Elastons are determined for any kind of object, but since I will first (and probably only) implement a grid of Elastons, I’ll skip that part.

Moving Least Squares

The next step towards computing the displacement is by using a Moving Least Squares (MLS) approach. The next section is based on a good overview paper by Andrew Nealen (who was working as a tutor in a computer graphics lecture I attended during my studies) which can be found here.

The basic Least Squares approach is used to approximate a function based on some sample values. It uses a polynomial function $f$ which is fitted to the samples by minimizing an error function which is squared (therefore the least squares). The minimization problem this is based on can be written down as

$\begin{array}{c}min \\ f\epsilon \prod^{d}_{m}\end{array} \sum_{i}||f(x_{i})-f_{i}||^{2}$

where $f(x)$ is the approximation function and $f_{i}$ are the samples for the values $x_{i}$ . The coefficients of the polynomial can be computed by solving a system of linear equations (see the linked paper for details).

Moving on, Weighted Least Squares (WLS) introduces the idea that the approximation is only computed for an area around a given point, leading to approximation functions that are defined locally.

Finally, Moving Least Squares builds upon WLS in that it constructs a WLS approximation function for each point and evaluates this as the approximation in that point.