[OGRE-461] QDUDecomposition - speed improvement

[paroj]

[reporter="8F114CC9F53256B4", created="Thu, 27 Nov 2014 10:59:57 +0100"]

In Matrix3::QDUDecomposition , we have a section of the function to extract a 3x3 matrix - The process involves 3 separate steps:

/* #1 - X Axis */
Real fInvLength = Math::InvSqrt(m[0][0]*m[0][0] + m[1][0]*m[1][0] + m[2][0]*m[2][0]);
kQ[0][0] = m[0][0]*fInvLength;
kQ[1][0] = m[1][0]*fInvLength;
kQ[2][0] = m[2][0]*fInvLength;
/* #2 - Y Axis */
Real fDot = kQ[0][0]*m[0][1] + kQ[1][0]*m[1][1] + kQ[2][0]*m[2][1];
kQ[0][1] = m[0][1]-fDot*kQ[0][0];
kQ[1][1] = m[1][1]-fDot*kQ[1][0];
kQ[2][1] = m[2][1]-fDot*kQ[2][0];
fInvLength = Math::InvSqrt(kQ[0][1]*kQ[0][1] + kQ[1][1]*kQ[1][1] + kQ[2][1]*kQ[2][1]);
kQ[0][1] *= fInvLength;
kQ[1][1] *= fInvLength;
kQ[2][1] *= fInvLength;
/* #3 - Z Axis */
fDot = kQ[0][0]*m[0][2] + kQ[1][0]*m[1][2] + kQ[2][0]*m[2][2];
kQ[0][2] = m[0][2]-fDot*kQ[0][0];
kQ[1][2] = m[1][2]-fDot*kQ[1][0];
kQ[2][2] = m[2][2]-fDot*kQ[2][0];
fDot = kQ[0][1]*m[0][2] + kQ[1][1]*m[1][2] + kQ[2][1]*m[2][2];
kQ[0][2] -= fDot*kQ[0][1];
kQ[1][2] -= fDot*kQ[1][1];
kQ[2][2] -= fDot*kQ[2][1];
fInvLength = Math::InvSqrt(kQ[0][2]*kQ[0][2] + kQ[1][2]*kQ[1][2] + kQ[2][2]*kQ[2][2]);
kQ[0][2] *= fInvLength;
kQ[1][2] *= fInvLength;
kQ[2][2] *= fInvLength;

Consider:
#1: It is trivial - X-axis is set, normalized.
#2: Because we need to make Y-axis perpendicular to X-axis, so we apply the given algorithm, and finally set it, normalized.
#3: Now we want to obtain the Z-axis (which (needless to say) must be perpendicular to both X-axis and Y-axis). But, because by now we have both X-axis and Y-axis being normal vectors and also being perpendicular to each other, we can very simply use cross product (and we don't even have to normalize it!).

In other words, for Step #3, rather than "correcting" Z-axis (by subtracting the vector with vectors-from-dot-products), we reconstruct Z-axis (by cross-product of X-axis and Y-axis).

My patch:

/* #1 - X Axis */
Real fInvLength = Math::InvSqrt(m[0][0]*m[0][0] + m[1][0]*m[1][0] + m[2][0]*m[2][0]);
kQ[0][0] = m[0][0]*fInvLength;
kQ[1][0] = m[1][0]*fInvLength;
kQ[2][0] = m[2][0]*fInvLength;
Vector3 lAxis(kQ[0][0],kQ[1][0],kQ[2][0]); /* Will reuse this variable, below */
/* #2 - Y Axis */
Real fDot = kQ[0][0]*m[0][1] + kQ[1][0]*m[1][1] + kQ[2][0]*m[2][1];
kQ[0][1] = m[0][1]-fDot*kQ[0][0];
kQ[1][1] = m[1][1]-fDot*kQ[1][0];
kQ[2][1] = m[2][1]-fDot*kQ[2][0];
fInvLength = Math::InvSqrt(kQ[0][1]*kQ[0][1] + kQ[1][1]*kQ[1][1] + kQ[2][1]*kQ[2][1]);
kQ[0][1] *= fInvLength;
kQ[1][1] *= fInvLength;
kQ[2][1] *= fInvLength;
/* #3 - Z Axis */
lAxis=lAxis.crossProduct(Vector3(kQ[0][1],kQ[1][1],kQ[2][1])); /* Z = X x Y */
kQ[0][2] = lAxis.x; /* There is no need to normalize */
kQ[1][2] = lAxis.y;
kQ[2][2] = lAxis.z;

With this algorithm instead, it saves you 2 counts of vector subtraction operations and 1 count of square-root operation.

Of course, this is to my analysis. If anyone has better math programming experience, feel free to write your opinion.

Have a nice day!

[paroj]

can be even further optimized as:
https://github.com/google/filament/blob/c9fcedb40bcad7cfa35d02a541e2d15aac5604de/libs/math/include/math/mat3.h#L254

[paroj]

unfortunately the cross product will incorrectly mask any reflection that is in m. See test in #1388