Implement analytical error metric when 3D scale/shear is present

[nfrechette]

The current error metric approximates the error seen when deforming a sphere with a fixed radius (user supplied). It does this by measuring the error on 3 orthogonal points. The problem with this is that depending on the transform, these points may see an error far smaller than the actual error which can change quite dramatically when a parent transform is later applied/tweaked. To solve this, when scale isn't present, an analytical solution was found to measure the error on the point that sees the most deformation. This ensures an accurate measurement.

However, 3D scale and shear complicate things considerably. I was unable to find a nice geometric solution as the point that sees the most deformation is not always the one furthest away from the centre of the sphere. I did find an analytical solution through linear algebra which boils down to solving a quartic function. This is not easy to do, and not cheap to evaluate either.

I will detail here how to implement the solution along with notes.

The error formula is the following one: error = |(T * R * S * p) - p|
Here, we have:

• p is the point being evaluated
• S is the scale/shear 3x3 matrix
• R is the rotation 3x3 matrix (or quaternion)
• T is the translation 3x4 matrix

The problem then boils down to finding the p value that maximizes the resulting error. To find this, we need to find the derivative of the error function and solve its roots. When S is simply non-uniform scaling and we have no translation, the derivative ends up being a bi-quadratic function which isn't too hard to solve (a special form of a quartic where we have ax^4 + bx^2 + c = 0). However, once translation enters the mix, we have to solve the roots for a proper quartic which is far less trivial as some of the roots can be complex numbers. I suspect that introducing shear will similarly yield a quartic. Crucially, shear arises when non-uniform scale is rotated which will arise naturally when a transform is multiplied with a parent transform in a joint chain. Once the roots of the quartic are found, to find which one maximizes the error, we have to evaluate our error function at each root along with the boundary of the domain (p lives on the unit circle and so has [-1,1] as its domain.

As such, here are the steps needed to solve this:

• Implement complex number support in RTM
• Implement cubic real/complex root in RTM
• Implement a quartic solver (see fast quartic solver below), this needs robust unit testing
• Find the quartic that handles rotation, translation, non-uniform scale, and shear (use Wolfram Alpha, see rotation viewer for WIP details)
• Switch ACL to use VQM (see Migrate from QVV to VQM arithmetic #61) for proper scale/shear support
• Implement the error function derivative and solve its roots
• Implement the error function and evaluate its roots/domain boundary to find the maximizing point
• Validate result in rotation viewer app: https://github.com/nfrechette/3d-rotation-viewer
• Evaluate the impact on the quantization optimization algorithm (compressed size and compression time)

Closed form quartic formula: https://planetmath.org/QuarticFormula

Peter Strobach,
The fast quartic solver,
Journal of Computational and Applied Mathematics,
Volume 234, Issue 10,
2010,
Pages 3007-3024,
ISSN 0377-0427,
https://doi.org/10.1016/j.cam.2010.04.015.
(https://www.sciencedirect.com/science/article/pii/S0377042710002128)
Abstract: A fast and highly accurate algorithm for solving quartic equations is introduced. This new algorithm is more than six times as fast and several times more accurate than the quasi-standard Companion matrix eigenvalue quartic solver. Moreover, the method is exceptionally robust in cases of extreme root spread. The new algorithm is based on a factorization of the quartic in two quadratics, which are solved in closed form. The performance key at this point is a fixed-point iteration based fitting algorithm for backward optimization of the underlying quartic-to-quadratic polynomial decomposition. Detailed experimental results confirm our claims.
Keywords: Quartic function; Polynomial factorization; Polynomial rooting; Companion matrix; Eigenvalues