| 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 |