michael@0: // from http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c
michael@0: /*
michael@0:  *  Roots3And4.c
michael@0:  *
michael@0:  *  Utility functions to find cubic and quartic roots,
michael@0:  *  coefficients are passed like this:
michael@0:  *
michael@0:  *      c[0] + c[1]*x + c[2]*x^2 + c[3]*x^3 + c[4]*x^4 = 0
michael@0:  *
michael@0:  *  The functions return the number of non-complex roots and
michael@0:  *  put the values into the s array.
michael@0:  *
michael@0:  *  Author:         Jochen Schwarze (schwarze@isa.de)
michael@0:  *
michael@0:  *  Jan 26, 1990    Version for Graphics Gems
michael@0:  *  Oct 11, 1990    Fixed sign problem for negative q's in SolveQuartic
michael@0:  *                  (reported by Mark Podlipec),
michael@0:  *                  Old-style function definitions,
michael@0:  *                  IsZero() as a macro
michael@0:  *  Nov 23, 1990    Some systems do not declare acos() and cbrt() in
michael@0:  *                  <math.h>, though the functions exist in the library.
michael@0:  *                  If large coefficients are used, EQN_EPS should be
michael@0:  *                  reduced considerably (e.g. to 1E-30), results will be
michael@0:  *                  correct but multiple roots might be reported more
michael@0:  *                  than once.
michael@0:  */
michael@0: 
michael@0: #include "SkPathOpsCubic.h"
michael@0: #include "SkPathOpsQuad.h"
michael@0: #include "SkQuarticRoot.h"
michael@0: 
michael@0: int SkReducedQuarticRoots(const double t4, const double t3, const double t2, const double t1,
michael@0:         const double t0, const bool oneHint, double roots[4]) {
michael@0: #ifdef SK_DEBUG
michael@0:     // create a string mathematica understands
michael@0:     // GDB set print repe 15 # if repeated digits is a bother
michael@0:     //     set print elements 400 # if line doesn't fit
michael@0:     char str[1024];
michael@0:     sk_bzero(str, sizeof(str));
michael@0:     SK_SNPRINTF(str, sizeof(str),
michael@0:             "Solve[%1.19g x^4 + %1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]",
michael@0:             t4, t3, t2, t1, t0);
michael@0:     SkPathOpsDebug::MathematicaIze(str, sizeof(str));
michael@0: #if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA
michael@0:     SkDebugf("%s\n", str);
michael@0: #endif
michael@0: #endif
michael@0:     if (approximately_zero_when_compared_to(t4, t0)  // 0 is one root
michael@0:             && approximately_zero_when_compared_to(t4, t1)
michael@0:             && approximately_zero_when_compared_to(t4, t2)) {
michael@0:         if (approximately_zero_when_compared_to(t3, t0)
michael@0:             && approximately_zero_when_compared_to(t3, t1)
michael@0:             && approximately_zero_when_compared_to(t3, t2)) {
michael@0:             return SkDQuad::RootsReal(t2, t1, t0, roots);
michael@0:         }
michael@0:         if (approximately_zero_when_compared_to(t4, t3)) {
michael@0:             return SkDCubic::RootsReal(t3, t2, t1, t0, roots);
michael@0:         }
michael@0:     }
michael@0:     if ((approximately_zero_when_compared_to(t0, t1) || approximately_zero(t1))  // 0 is one root
michael@0:       //      && approximately_zero_when_compared_to(t0, t2)
michael@0:             && approximately_zero_when_compared_to(t0, t3)
michael@0:             && approximately_zero_when_compared_to(t0, t4)) {
michael@0:         int num = SkDCubic::RootsReal(t4, t3, t2, t1, roots);
michael@0:         for (int i = 0; i < num; ++i) {
michael@0:             if (approximately_zero(roots[i])) {
michael@0:                 return num;
michael@0:             }
michael@0:         }
michael@0:         roots[num++] = 0;
michael@0:         return num;
michael@0:     }
michael@0:     if (oneHint) {
michael@0:         SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0));  // 1 is one root
michael@0:         // note that -C == A + B + D + E
michael@0:         int num = SkDCubic::RootsReal(t4, t4 + t3, -(t1 + t0), -t0, roots);
michael@0:         for (int i = 0; i < num; ++i) {
michael@0:             if (approximately_equal(roots[i], 1)) {
michael@0:                 return num;
michael@0:             }
michael@0:         }
michael@0:         roots[num++] = 1;
michael@0:         return num;
michael@0:     }
michael@0:     return -1;
michael@0: }
michael@0: 
michael@0: int SkQuarticRootsReal(int firstCubicRoot, const double A, const double B, const double C,
michael@0:         const double D, const double E, double s[4]) {
michael@0:     double  u, v;
michael@0:     /* normal form: x^4 + Ax^3 + Bx^2 + Cx + D = 0 */
michael@0:     const double invA = 1 / A;
michael@0:     const double a = B * invA;
michael@0:     const double b = C * invA;
michael@0:     const double c = D * invA;
michael@0:     const double d = E * invA;
michael@0:     /*  substitute x = y - a/4 to eliminate cubic term:
michael@0:     x^4 + px^2 + qx + r = 0 */
michael@0:     const double a2 = a * a;
michael@0:     const double p = -3 * a2 / 8 + b;
michael@0:     const double q = a2 * a / 8 - a * b / 2 + c;
michael@0:     const double r = -3 * a2 * a2 / 256 + a2 * b / 16 - a * c / 4 + d;
michael@0:     int num;
michael@0:     if (approximately_zero(r)) {
michael@0:     /* no absolute term: y(y^3 + py + q) = 0 */
michael@0:         num = SkDCubic::RootsReal(1, 0, p, q, s);
michael@0:         s[num++] = 0;
michael@0:     } else {
michael@0:         /* solve the resolvent cubic ... */
michael@0:         double cubicRoots[3];
michael@0:         int roots = SkDCubic::RootsReal(1, -p / 2, -r, r * p / 2 - q * q / 8, cubicRoots);
michael@0:         int index;
michael@0:         /* ... and take one real solution ... */
michael@0:         double z;
michael@0:         num = 0;
michael@0:         int num2 = 0;
michael@0:         for (index = firstCubicRoot; index < roots; ++index) {
michael@0:             z = cubicRoots[index];
michael@0:             /* ... to build two quadric equations */
michael@0:             u = z * z - r;
michael@0:             v = 2 * z - p;
michael@0:             if (approximately_zero_squared(u)) {
michael@0:                 u = 0;
michael@0:             } else if (u > 0) {
michael@0:                 u = sqrt(u);
michael@0:             } else {
michael@0:                 continue;
michael@0:             }
michael@0:             if (approximately_zero_squared(v)) {
michael@0:                 v = 0;
michael@0:             } else if (v > 0) {
michael@0:                 v = sqrt(v);
michael@0:             } else {
michael@0:                 continue;
michael@0:             }
michael@0:             num = SkDQuad::RootsReal(1, q < 0 ? -v : v, z - u, s);
michael@0:             num2 = SkDQuad::RootsReal(1, q < 0 ? v : -v, z + u, s + num);
michael@0:             if (!((num | num2) & 1)) {
michael@0:                 break;  // prefer solutions without single quad roots
michael@0:             }
michael@0:         }
michael@0:         num += num2;
michael@0:         if (!num) {
michael@0:             return 0;  // no valid cubic root
michael@0:         }
michael@0:     }
michael@0:     /* resubstitute */
michael@0:     const double sub = a / 4;
michael@0:     for (int i = 0; i < num; ++i) {
michael@0:         s[i] -= sub;
michael@0:     }
michael@0:     // eliminate duplicates
michael@0:     for (int i = 0; i < num - 1; ++i) {
michael@0:         for (int j = i + 1; j < num; ) {
michael@0:             if (AlmostDequalUlps(s[i], s[j])) {
michael@0:                 if (j < --num) {
michael@0:                     s[j] = s[num];
michael@0:                 }
michael@0:             } else {
michael@0:                 ++j;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return num;
michael@0: }