Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(62)

Side by Side Diff: src/pathops/SkQuarticRoot.cpp

Issue 131103009: update pathops to circle sort (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: disable old test that still fails on linux 32 release Created 6 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/pathops/SkPathWriter.h ('k') | tests/PathOpsAngleIdeas.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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 }
OLDNEW
« no previous file with comments | « src/pathops/SkPathWriter.h ('k') | tests/PathOpsAngleIdeas.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698