OLD | NEW |
1 // Another approach is to start with the implicit form of one curve and solve | 1 // Another approach is to start with the implicit form of one curve and solve |
2 // (seek implicit coefficients in QuadraticParameter.cpp | 2 // (seek implicit coefficients in QuadraticParameter.cpp |
3 // by substituting in the parametric form of the other. | 3 // by substituting in the parametric form of the other. |
4 // The downside of this approach is that early rejects are difficult to come by. | 4 // The downside of this approach is that early rejects are difficult to come by. |
5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu
la.html#step | 5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu
la.html#step |
6 | 6 |
7 | 7 |
8 #include "CubicUtilities.h" | 8 #include "CubicUtilities.h" |
9 #include "CurveIntersection.h" | 9 #include "CurveIntersection.h" |
10 #include "Intersections.h" | 10 #include "Intersections.h" |
11 #include "QuadraticParameterization.h" | 11 #include "QuadraticParameterization.h" |
12 #include "QuarticRoot.h" | 12 #include "QuarticRoot.h" |
13 #include "QuadraticUtilities.h" | 13 #include "QuadraticUtilities.h" |
14 #include "TSearch.h" | 14 #include "TSearch.h" |
15 | 15 |
16 #if SK_DEBUG | 16 #ifdef SK_DEBUG |
17 #include "LineUtilities.h" | 17 #include "LineUtilities.h" |
18 #endif | 18 #endif |
19 | 19 |
20 /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F | 20 /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F |
21 * and given x = at^2 + bt + c (the parameterized form) | 21 * and given x = at^2 + bt + c (the parameterized form) |
22 * y = dt^2 + et + f | 22 * y = dt^2 + et + f |
23 * then | 23 * then |
24 * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D
(at^2+bt+c)+E(dt^2+et+f)+F | 24 * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D
(at^2+bt+c)+E(dt^2+et+f)+F |
25 */ | 25 */ |
26 | 26 |
(...skipping 132 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
159 sub_divide(q1, t1s, t1e, hull); | 159 sub_divide(q1, t1s, t1e, hull); |
160 _Line line = {hull[2], hull[0]}; | 160 _Line line = {hull[2], hull[0]}; |
161 const _Line* testLines[] = { &line, (const _Line*) &hull[0], (const _Line*)
&hull[1] }; | 161 const _Line* testLines[] = { &line, (const _Line*) &hull[0], (const _Line*)
&hull[1] }; |
162 size_t testCount = sizeof(testLines) / sizeof(testLines[0]); | 162 size_t testCount = sizeof(testLines) / sizeof(testLines[0]); |
163 SkTDArray<double> tsFound; | 163 SkTDArray<double> tsFound; |
164 for (size_t index = 0; index < testCount; ++index) { | 164 for (size_t index = 0; index < testCount; ++index) { |
165 Intersections rootTs; | 165 Intersections rootTs; |
166 int roots = intersect(q2, *testLines[index], rootTs); | 166 int roots = intersect(q2, *testLines[index], rootTs); |
167 for (int idx2 = 0; idx2 < roots; ++idx2) { | 167 for (int idx2 = 0; idx2 < roots; ++idx2) { |
168 double t = rootTs.fT[0][idx2]; | 168 double t = rootTs.fT[0][idx2]; |
169 #if SK_DEBUG | 169 #ifdef SK_DEBUG |
170 _Point qPt, lPt; | 170 _Point qPt, lPt; |
171 xy_at_t(q2, t, qPt.x, qPt.y); | 171 xy_at_t(q2, t, qPt.x, qPt.y); |
172 xy_at_t(*testLines[index], rootTs.fT[1][idx2], lPt.x, lPt.y); | 172 xy_at_t(*testLines[index], rootTs.fT[1][idx2], lPt.x, lPt.y); |
173 SkASSERT(qPt.approximatelyEqual(lPt)); | 173 SkASSERT(qPt.approximatelyEqual(lPt)); |
174 #endif | 174 #endif |
175 if (approximately_negative(t - t2s) || approximately_positive(t - t2
e)) { | 175 if (approximately_negative(t - t2s) || approximately_positive(t - t2
e)) { |
176 continue; | 176 continue; |
177 } | 177 } |
178 *tsFound.append() = rootTs.fT[0][idx2]; | 178 *tsFound.append() = rootTs.fT[0][idx2]; |
179 } | 179 } |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
254 if (!approximately_zero_sqrt(measure)) { | 254 if (!approximately_zero_sqrt(measure)) { |
255 return false; | 255 return false; |
256 } | 256 } |
257 return isLinearInner(q1, 0, 1, q2, 0, 1, i, NULL); | 257 return isLinearInner(q1, 0, 1, q2, 0, 1, i, NULL); |
258 } | 258 } |
259 | 259 |
260 // FIXME: if flat measure is sufficiently large, then probably the quartic solut
ion failed | 260 // FIXME: if flat measure is sufficiently large, then probably the quartic solut
ion failed |
261 static void relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersecti
ons& i) { | 261 static void relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersecti
ons& i) { |
262 double m1 = flatMeasure(q1); | 262 double m1 = flatMeasure(q1); |
263 double m2 = flatMeasure(q2); | 263 double m2 = flatMeasure(q2); |
264 #if SK_DEBUG | 264 #ifdef SK_DEBUG |
265 double min = SkTMin(m1, m2); | 265 double min = SkTMin(m1, m2); |
266 if (min > 5) { | 266 if (min > 5) { |
267 SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min); | 267 SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min); |
268 } | 268 } |
269 #endif | 269 #endif |
270 i.reset(); | 270 i.reset(); |
271 const Quadratic& rounder = m2 < m1 ? q1 : q2; | 271 const Quadratic& rounder = m2 < m1 ? q1 : q2; |
272 const Quadratic& flatter = m2 < m1 ? q2 : q1; | 272 const Quadratic& flatter = m2 < m1 ? q2 : q1; |
273 bool subDivide = false; | 273 bool subDivide = false; |
274 isLinearInner(flatter, 0, 1, rounder, 0, 1, i, &subDivide); | 274 isLinearInner(flatter, 0, 1, rounder, 0, 1, i, &subDivide); |
(...skipping 288 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
563 if (lowestIndex < 0) { | 563 if (lowestIndex < 0) { |
564 break; | 564 break; |
565 } | 565 } |
566 i.insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], | 566 i.insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], |
567 pts1[lowestIndex]); | 567 pts1[lowestIndex]); |
568 closest[lowestIndex] = -1; | 568 closest[lowestIndex] = -1; |
569 } while (++used < r1Count); | 569 } while (++used < r1Count); |
570 i.fFlip = false; | 570 i.fFlip = false; |
571 return i.intersected(); | 571 return i.intersected(); |
572 } | 572 } |
OLD | NEW |