diff options
author | Svenn-Arne Dragly <svenn-arne.dragly@qt.io> | 2018-03-13 17:35:26 +0100 |
---|---|---|
committer | Svenn-Arne Dragly <svenn-arne.dragly@qt.io> | 2018-03-25 18:13:47 +0000 |
commit | c5a6d31c2a40a3e1bd976ff8162238a7cbc066b4 (patch) | |
tree | f4e88d603ad0433a510f160e018ffa764824f3ad /src/animation/backend/bezierevaluator.cpp | |
parent | 2bf1f907e9e6ac87fc039d674eaca5179c5029f6 (diff) |
Fix findCubicRoots for cases where coefficients are close to zero
The equation is a*x^3 + b*x^2 + c*x + d = 0.
Previously, we would divide by zero if a = ~0.
This change also makes sure that we return zero no roots in the case
where a = ~0 and c*c - 4*b*d < 0, and the case where a = b = c = ~0.
Finally, we return 0 or 1 if we're close enough to assume that it could
be a numerical error.
This change also adds tests for the above cases.
Change-Id: I426d2fc6175b3aff6fe099845bf63d433c158536
Co-authored-by: Christian Strømme <christian.stromme@qt.io>
Reviewed-by: Christian Stromme <christian.stromme@qt.io>
Diffstat (limited to 'src/animation/backend/bezierevaluator.cpp')
-rw-r--r-- | src/animation/backend/bezierevaluator.cpp | 51 |
1 files changed, 46 insertions, 5 deletions
diff --git a/src/animation/backend/bezierevaluator.cpp b/src/animation/backend/bezierevaluator.cpp index 9d81a2f2f..2752904fc 100644 --- a/src/animation/backend/bezierevaluator.cpp +++ b/src/animation/backend/bezierevaluator.cpp @@ -161,6 +161,13 @@ float BezierEvaluator::parameterForTime(float time) const return 0.0f; } +bool almostZero(float value, float threshold=1e-3f) +{ + // 1e-3 might seem excessively fuzzy, but any smaller value will make the + // factors a, b, and c large enough to knock out the cubic solver. + return value > -threshold && value < threshold; +} + /*! \internal @@ -171,17 +178,45 @@ float BezierEvaluator::parameterForTime(float time) const */ int BezierEvaluator::findCubicRoots(const float coeffs[4], float roots[3]) { + const float a = coeffs[3]; + const float b = coeffs[2]; + const float c = coeffs[1]; + const float d = coeffs[0]; + + // Simple cases with linear, quadratic or invalid equations + if (almostZero(a)) { + if (almostZero(b)) { + if (almostZero(c)) + return 0; + + roots[0] = -d / c; + return 1; + } + const float discriminant = c * c - 4.f * b * d; + if (discriminant < 0.f) + return 0; + + if (discriminant == 0.f) { + roots[0] = -c / (2.f * b); + return 1; + } + + roots[0] = (-c + std::sqrt(discriminant)) / (2.f * b); + roots[1] = (-c - std::sqrt(discriminant)) / (2.f * b); + return 2; + } + // See https://en.wikipedia.org/wiki/Cubic_function#General_solution_to_the_cubic_equation_with_real_coefficients // for a description. We depress the general cubic to a form that can more easily be solved. Solve it and then // substitue the results back to get the roots of the original cubic. - int numberOfRoots; + int numberOfRoots = 0; const double oneThird = 1.0 / 3.0; const double piByThree = M_PI / 3.0; // Put cubic into normal format: x^3 + Ax^2 + Bx + C = 0 - const double A = coeffs[ 2 ] / coeffs[ 3 ]; - const double B = coeffs[ 1 ] / coeffs[ 3 ]; - const double C = coeffs[ 0 ] / coeffs[ 3 ]; + const double A = double(b / a); + const double B = double(c / a); + const double C = double(d / a); // Substitute x = y - A/3 to eliminate quadratic term (depressed form): // x^3 + px + q = 0 @@ -226,8 +261,14 @@ int BezierEvaluator::findCubicRoots(const float coeffs[4], float roots[3]) // Substitute back in const double sub = oneThird * A; - for (int i = 0; i < numberOfRoots; ++i) + for (int i = 0; i < numberOfRoots; ++i) { roots[i] -= sub; + // Take care of cases where we are close to zero or one + if (almostZero(roots[i], 1e-6f)) + roots[i] = 0.f; + if (almostZero(roots[i] - 1.f, 1e-6f)) + roots[i] = 1.f; + } return numberOfRoots; } |