| OLD | NEW |
| 1 // from http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c | 1 // from http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c |
| 2 /* | 2 /* |
| 3 * Roots3And4.c | 3 * Roots3And4.c |
| 4 * | 4 * |
| 5 * Utility functions to find cubic and quartic roots, | 5 * Utility functions to find cubic and quartic roots, |
| 6 * coefficients are passed like this: | 6 * coefficients are passed like this: |
| 7 * | 7 * |
| 8 * c[0] + c[1]*x + c[2]*x^2 + c[3]*x^3 + c[4]*x^4 = 0 | 8 * c[0] + c[1]*x + c[2]*x^2 + c[3]*x^3 + c[4]*x^4 = 0 |
| 9 * | 9 * |
| 10 * The functions return the number of non-complex roots and | 10 * The functions return the number of non-complex roots and |
| (...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 64 int num = SkDCubic::RootsReal(t4, t3, t2, t1, roots); | 64 int num = SkDCubic::RootsReal(t4, t3, t2, t1, roots); |
| 65 for (int i = 0; i < num; ++i) { | 65 for (int i = 0; i < num; ++i) { |
| 66 if (approximately_zero(roots[i])) { | 66 if (approximately_zero(roots[i])) { |
| 67 return num; | 67 return num; |
| 68 } | 68 } |
| 69 } | 69 } |
| 70 roots[num++] = 0; | 70 roots[num++] = 0; |
| 71 return num; | 71 return num; |
| 72 } | 72 } |
| 73 if (oneHint) { | 73 if (oneHint) { |
| 74 SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0)); // 1 is on
e root | 74 SkASSERT(approximately_zero_double(t4 + t3 + t2 + t1 + t0) || |
| 75 approximately_zero_when_compared_to(t4 + t3 + t2 + t1 + t0, //
1 is one root |
| 76 SkTMax(fabs(t4), SkTMax(fabs(t3), SkTMax(fabs(t2), SkTMax(fabs(t
1), fabs(t0))))))); |
| 75 // note that -C == A + B + D + E | 77 // note that -C == A + B + D + E |
| 76 int num = SkDCubic::RootsReal(t4, t4 + t3, -(t1 + t0), -t0, roots); | 78 int num = SkDCubic::RootsReal(t4, t4 + t3, -(t1 + t0), -t0, roots); |
| 77 for (int i = 0; i < num; ++i) { | 79 for (int i = 0; i < num; ++i) { |
| 78 if (approximately_equal(roots[i], 1)) { | 80 if (approximately_equal(roots[i], 1)) { |
| 79 return num; | 81 return num; |
| 80 } | 82 } |
| 81 } | 83 } |
| 82 roots[num++] = 1; | 84 roots[num++] = 1; |
| 83 return num; | 85 return num; |
| 84 } | 86 } |
| 85 return -1; | 87 return -1; |
| 86 } | 88 } |
| 87 | 89 |
| 88 int SkQuarticRootsReal(int firstCubicRoot, const double A, const double B, const
double C, | 90 int SkQuarticRootsReal(int firstCubicRoot, const double A, const double B, const
double C, |
| 89 const double D, const double E, double s[4]) { | 91 const double D, const double E, double s[4]) { |
| 90 double u, v; | 92 double u, v; |
| 91 /* normal form: x^4 + Ax^3 + Bx^2 + Cx + D = 0 */ | 93 /* normal form: x^4 + Ax^3 + Bx^2 + Cx + D = 0 */ |
| 92 const double invA = 1 / A; | 94 const double invA = 1 / A; |
| 93 const double a = B * invA; | 95 const double a = B * invA; |
| 94 const double b = C * invA; | 96 const double b = C * invA; |
| 95 const double c = D * invA; | 97 const double c = D * invA; |
| 96 const double d = E * invA; | 98 const double d = E * invA; |
| 97 /* substitute x = y - a/4 to eliminate cubic term: | 99 /* substitute x = y - a/4 to eliminate cubic term: |
| 98 x^4 + px^2 + qx + r = 0 */ | 100 x^4 + px^2 + qx + r = 0 */ |
| 99 const double a2 = a * a; | 101 const double a2 = a * a; |
| 100 const double p = -3 * a2 / 8 + b; | 102 const double p = -3 * a2 / 8 + b; |
| 101 const double q = a2 * a / 8 - a * b / 2 + c; | 103 const double q = a2 * a / 8 - a * b / 2 + c; |
| 102 const double r = -3 * a2 * a2 / 256 + a2 * b / 16 - a * c / 4 + d; | 104 const double r = -3 * a2 * a2 / 256 + a2 * b / 16 - a * c / 4 + d; |
| 103 int num; | 105 int num; |
| 104 if (approximately_zero(r)) { | 106 double largest = SkTMax(fabs(p), fabs(q)); |
| 107 if (approximately_zero_when_compared_to(r, largest)) { |
| 105 /* no absolute term: y(y^3 + py + q) = 0 */ | 108 /* no absolute term: y(y^3 + py + q) = 0 */ |
| 106 num = SkDCubic::RootsReal(1, 0, p, q, s); | 109 num = SkDCubic::RootsReal(1, 0, p, q, s); |
| 107 s[num++] = 0; | 110 s[num++] = 0; |
| 108 } else { | 111 } else { |
| 109 /* solve the resolvent cubic ... */ | 112 /* solve the resolvent cubic ... */ |
| 110 double cubicRoots[3]; | 113 double cubicRoots[3]; |
| 111 int roots = SkDCubic::RootsReal(1, -p / 2, -r, r * p / 2 - q * q / 8, cu
bicRoots); | 114 int roots = SkDCubic::RootsReal(1, -p / 2, -r, r * p / 2 - q * q / 8, cu
bicRoots); |
| 112 int index; | 115 int index; |
| 113 /* ... and take one real solution ... */ | 116 /* ... and take one real solution ... */ |
| 114 double z; | 117 double z; |
| (...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 156 if (j < --num) { | 159 if (j < --num) { |
| 157 s[j] = s[num]; | 160 s[j] = s[num]; |
| 158 } | 161 } |
| 159 } else { | 162 } else { |
| 160 ++j; | 163 ++j; |
| 161 } | 164 } |
| 162 } | 165 } |
| 163 } | 166 } |
| 164 return num; | 167 return num; |
| 165 } | 168 } |
| OLD | NEW |