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 |