Suppose you have a huge number of similar objects in world space. These objects can be represented as instances. But, the meshes of these objects are in world space and are represented as un-related objects. The meshes are given to be of identical geometry and topology and material assignment. Also, it is given that, the unknown transformation that happened in creating each of the mesh is of affine nature ( ie: one involving, scale, rotation, shearing and translation ). Given two similar meshes in world space, how can one guess the transformation that transforms one mesh to another?

Let the vertices of mesh be and the vertices of mesh be Each or is a row vector of the and components of the corresponding vertex. The component is always .

We have to where is an unknown matrix. Please consider as made up of four matrices, and .


Make a big matrix , where the row of is . Make a big matrix , where the row of is .

and are known. are unknown.

Since , the number of vertices is often a large number compared to the other matrix dimension which is , we have an over constrained system (ie too many knowns and too few unknowns). We can find the value of , which gives the minimum least squares error.

Let be the matrix which denotes the error,

Let be the matrix where the row is .

Note that

From ,

Let “” be the transpose operator.


From ,

Now and are each matrices and are the same. So can be written as,

Differentiate this matrix equation wrt. the unknown, ie . The minimum error occurs when the differentiated result is equal to zero, and the second differential is a positive definite matrix.

Please use the following equations from matrix calculus is doing the differentiation. Let be a matrix and let be a column vector.

Equating this above derivative to zero, we get a linear equation for , which we can solve using any of the popular numerical methods for solving linear equations.



Note that the second differential of is which is a positive definite matrix. so solving for the above value of will give us the least square minimum.

Similarly we can solve for , and separately, and thusly retrieve .

Ref: Practical Least Squares for Computer Graphics, Siggraph-07 Course.

blog comments powered by Disqus