caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 1 | // Another approach is to start with the implicit form of one curve and solve |
| 2 | // (seek implicit coefficients in QuadraticParameter.cpp |
| 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. |
| 5 | // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormula.html#step |
| 6 | |
| 7 | |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 8 | #include "CubicUtilities.h" |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 9 | #include "CurveIntersection.h" |
| 10 | #include "Intersections.h" |
| 11 | #include "QuadraticParameterization.h" |
| 12 | #include "QuarticRoot.h" |
| 13 | #include "QuadraticUtilities.h" |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 14 | #include "TSearch.h" |
| 15 | |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 16 | #if SK_DEBUG |
| 17 | #include "LineUtilities.h" |
| 18 | #endif |
| 19 | |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 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) |
| 22 | * y = dt^2 + et + f |
skia.committer@gmail.com | 055c7c2 | 2012-09-15 02:01:41 +0000 | [diff] [blame] | 23 | * then |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 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 | */ |
skia.committer@gmail.com | 15dd300 | 2013-01-18 07:07:28 +0000 | [diff] [blame] | 26 | |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 27 | static int findRoots(const QuadImplicitForm& i, const Quadratic& q2, double roots[4], |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 28 | bool oneHint) { |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 29 | double a, b, c; |
| 30 | set_abc(&q2[0].x, a, b, c); |
| 31 | double d, e, f; |
| 32 | set_abc(&q2[0].y, d, e, f); |
| 33 | const double t4 = i.x2() * a * a |
| 34 | + i.xy() * a * d |
| 35 | + i.y2() * d * d; |
| 36 | const double t3 = 2 * i.x2() * a * b |
| 37 | + i.xy() * (a * e + b * d) |
| 38 | + 2 * i.y2() * d * e; |
| 39 | const double t2 = i.x2() * (b * b + 2 * a * c) |
| 40 | + i.xy() * (c * d + b * e + a * f) |
| 41 | + i.y2() * (e * e + 2 * d * f) |
| 42 | + i.x() * a |
| 43 | + i.y() * d; |
| 44 | const double t1 = 2 * i.x2() * b * c |
| 45 | + i.xy() * (c * e + b * f) |
| 46 | + 2 * i.y2() * e * f |
| 47 | + i.x() * b |
| 48 | + i.y() * e; |
| 49 | const double t0 = i.x2() * c * c |
| 50 | + i.xy() * c * f |
| 51 | + i.y2() * f * f |
| 52 | + i.x() * c |
| 53 | + i.y() * f |
| 54 | + i.c(); |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 55 | int rootCount = reducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots); |
| 56 | if (rootCount >= 0) { |
| 57 | return rootCount; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 58 | } |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 59 | return quarticRootsReal(t4, t3, t2, t1, t0, roots); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 60 | } |
| 61 | |
| 62 | static void addValidRoots(const double roots[4], const int count, const int side, Intersections& i) { |
| 63 | int index; |
| 64 | for (index = 0; index < count; ++index) { |
| 65 | if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_less(roots[index])) { |
| 66 | continue; |
| 67 | } |
| 68 | double t = 1 - roots[index]; |
| 69 | if (approximately_less_than_zero(t)) { |
| 70 | t = 0; |
| 71 | } else if (approximately_greater_than_one(t)) { |
| 72 | t = 1; |
| 73 | } |
| 74 | i.insertOne(t, side); |
| 75 | } |
| 76 | } |
| 77 | |
caryclark@google.com | 6aea33f | 2012-10-09 14:11:58 +0000 | [diff] [blame] | 78 | static bool onlyEndPtsInCommon(const Quadratic& q1, const Quadratic& q2, Intersections& i) { |
| 79 | // the idea here is to see at minimum do a quick reject by rotating all points |
| 80 | // to either side of the line formed by connecting the endpoints |
| 81 | // if the opposite curves points are on the line or on the other side, the |
| 82 | // curves at most intersect at the endpoints |
| 83 | for (int oddMan = 0; oddMan < 3; ++oddMan) { |
| 84 | const _Point* endPt[2]; |
| 85 | for (int opp = 1; opp < 3; ++opp) { |
| 86 | int end = oddMan ^ opp; |
| 87 | if (end == 3) { |
| 88 | end = opp; |
| 89 | } |
| 90 | endPt[opp - 1] = &q1[end]; |
| 91 | } |
| 92 | double origX = endPt[0]->x; |
| 93 | double origY = endPt[0]->y; |
| 94 | double adj = endPt[1]->x - origX; |
| 95 | double opp = endPt[1]->y - origY; |
| 96 | double sign = (q1[oddMan].y - origY) * adj - (q1[oddMan].x - origX) * opp; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 97 | if (approximately_zero(sign)) { |
| 98 | goto tryNextHalfPlane; |
| 99 | } |
caryclark@google.com | 6aea33f | 2012-10-09 14:11:58 +0000 | [diff] [blame] | 100 | for (int n = 0; n < 3; ++n) { |
| 101 | double test = (q2[n].y - origY) * adj - (q2[n].x - origX) * opp; |
| 102 | if (test * sign > 0) { |
| 103 | goto tryNextHalfPlane; |
| 104 | } |
| 105 | } |
| 106 | for (int i1 = 0; i1 < 3; i1 += 2) { |
| 107 | for (int i2 = 0; i2 < 3; i2 += 2) { |
| 108 | if (q1[i1] == q2[i2]) { |
caryclark@google.com | fb51afb | 2012-10-19 15:54:16 +0000 | [diff] [blame] | 109 | i.insert(i1 >> 1, i2 >> 1); |
caryclark@google.com | 6aea33f | 2012-10-09 14:11:58 +0000 | [diff] [blame] | 110 | } |
| 111 | } |
| 112 | } |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 113 | SkASSERT(i.fUsed < 3); |
caryclark@google.com | 6aea33f | 2012-10-09 14:11:58 +0000 | [diff] [blame] | 114 | return true; |
| 115 | tryNextHalfPlane: |
| 116 | ; |
| 117 | } |
| 118 | return false; |
| 119 | } |
| 120 | |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 121 | // returns false if there's more than one intercept or the intercept doesn't match the point |
skia.committer@gmail.com | cdcb2ce | 2013-01-29 07:05:52 +0000 | [diff] [blame] | 122 | // returns true if the intercept was successfully added or if the |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 123 | // original quads need to be subdivided |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 124 | static bool addIntercept(const Quadratic& q1, const Quadratic& q2, double tMin, double tMax, |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 125 | Intersections& i, bool* subDivide) { |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 126 | double tMid = (tMin + tMax) / 2; |
| 127 | _Point mid; |
| 128 | xy_at_t(q2, tMid, mid.x, mid.y); |
| 129 | _Line line; |
| 130 | line[0] = line[1] = mid; |
caryclark@google.com | 05c4bad | 2013-01-19 13:22:39 +0000 | [diff] [blame] | 131 | _Point dxdy; |
| 132 | dxdy_at_t(q2, tMid, dxdy); |
| 133 | line[0].x -= dxdy.x; |
| 134 | line[0].y -= dxdy.y; |
| 135 | line[1].x += dxdy.x; |
| 136 | line[1].y += dxdy.y; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 137 | Intersections rootTs; |
| 138 | int roots = intersect(q1, line, rootTs); |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 139 | if (roots == 0) { |
| 140 | if (subDivide) { |
| 141 | *subDivide = true; |
| 142 | } |
| 143 | return true; |
| 144 | } |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 145 | if (roots == 2) { |
| 146 | return false; |
| 147 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 148 | _Point pt2; |
| 149 | xy_at_t(q1, rootTs.fT[0][0], pt2.x, pt2.y); |
| 150 | if (!pt2.approximatelyEqual(mid)) { |
| 151 | return false; |
| 152 | } |
| 153 | i.add(rootTs.fT[0][0], tMid); |
| 154 | return true; |
| 155 | } |
| 156 | |
| 157 | static bool isLinearInner(const Quadratic& q1, double t1s, double t1e, const Quadratic& q2, |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 158 | double t2s, double t2e, Intersections& i, bool* subDivide) { |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 159 | Quadratic hull; |
| 160 | sub_divide(q1, t1s, t1e, hull); |
| 161 | _Line line = {hull[2], hull[0]}; |
| 162 | const _Line* testLines[] = { &line, (const _Line*) &hull[0], (const _Line*) &hull[1] }; |
| 163 | size_t testCount = sizeof(testLines) / sizeof(testLines[0]); |
| 164 | SkTDArray<double> tsFound; |
| 165 | for (size_t index = 0; index < testCount; ++index) { |
| 166 | Intersections rootTs; |
| 167 | int roots = intersect(q2, *testLines[index], rootTs); |
| 168 | for (int idx2 = 0; idx2 < roots; ++idx2) { |
| 169 | double t = rootTs.fT[0][idx2]; |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 170 | #if SK_DEBUG |
| 171 | _Point qPt, lPt; |
| 172 | xy_at_t(q2, t, qPt.x, qPt.y); |
| 173 | xy_at_t(*testLines[index], rootTs.fT[1][idx2], lPt.x, lPt.y); |
| 174 | SkASSERT(qPt.approximatelyEqual(lPt)); |
| 175 | #endif |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 176 | if (approximately_negative(t - t2s) || approximately_positive(t - t2e)) { |
| 177 | continue; |
| 178 | } |
| 179 | *tsFound.append() = rootTs.fT[0][idx2]; |
| 180 | } |
| 181 | } |
| 182 | int tCount = tsFound.count(); |
| 183 | if (!tCount) { |
| 184 | return true; |
| 185 | } |
| 186 | double tMin, tMax; |
| 187 | _Point dxy1, dxy2; |
| 188 | if (tCount == 1) { |
| 189 | tMin = tMax = tsFound[0]; |
| 190 | } else if (tCount > 1) { |
| 191 | QSort<double>(tsFound.begin(), tsFound.end() - 1); |
| 192 | tMin = tsFound[0]; |
| 193 | tMax = tsFound[1]; |
| 194 | } |
| 195 | _Point end; |
| 196 | xy_at_t(q2, t2s, end.x, end.y); |
caryclark@google.com | beda389 | 2013-02-07 13:13:41 +0000 | [diff] [blame^] | 197 | bool startInTriangle = point_in_hull(hull, end); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 198 | if (startInTriangle) { |
| 199 | tMin = t2s; |
skia.committer@gmail.com | 15dd300 | 2013-01-18 07:07:28 +0000 | [diff] [blame] | 200 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 201 | xy_at_t(q2, t2e, end.x, end.y); |
caryclark@google.com | beda389 | 2013-02-07 13:13:41 +0000 | [diff] [blame^] | 202 | bool endInTriangle = point_in_hull(hull, end); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 203 | if (endInTriangle) { |
| 204 | tMax = t2e; |
| 205 | } |
| 206 | int split = 0; |
| 207 | if (tMin != tMax || tCount > 2) { |
caryclark@google.com | 05c4bad | 2013-01-19 13:22:39 +0000 | [diff] [blame] | 208 | dxdy_at_t(q2, tMin, dxy2); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 209 | for (int index = 1; index < tCount; ++index) { |
| 210 | dxy1 = dxy2; |
caryclark@google.com | 05c4bad | 2013-01-19 13:22:39 +0000 | [diff] [blame] | 211 | dxdy_at_t(q2, tsFound[index], dxy2); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 212 | double dot = dxy1.dot(dxy2); |
| 213 | if (dot < 0) { |
| 214 | split = index - 1; |
| 215 | break; |
| 216 | } |
| 217 | } |
skia.committer@gmail.com | 15dd300 | 2013-01-18 07:07:28 +0000 | [diff] [blame] | 218 | |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 219 | } |
| 220 | if (split == 0) { // there's one point |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 221 | if (addIntercept(q1, q2, tMin, tMax, i, subDivide)) { |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 222 | return true; |
| 223 | } |
| 224 | i.swap(); |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 225 | return isLinearInner(q2, tMin, tMax, q1, t1s, t1e, i, subDivide); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 226 | } |
| 227 | // At this point, we have two ranges of t values -- treat each separately at the split |
| 228 | bool result; |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 229 | if (addIntercept(q1, q2, tMin, tsFound[split - 1], i, subDivide)) { |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 230 | result = true; |
| 231 | } else { |
| 232 | i.swap(); |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 233 | result = isLinearInner(q2, tMin, tsFound[split - 1], q1, t1s, t1e, i, subDivide); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 234 | } |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 235 | if (addIntercept(q1, q2, tsFound[split], tMax, i, subDivide)) { |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 236 | result = true; |
| 237 | } else { |
| 238 | i.swap(); |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 239 | result |= isLinearInner(q2, tsFound[split], tMax, q1, t1s, t1e, i, subDivide); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 240 | } |
| 241 | return result; |
| 242 | } |
| 243 | |
| 244 | static double flatMeasure(const Quadratic& q) { |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 245 | _Point mid = q[1]; |
| 246 | mid -= q[0]; |
| 247 | _Point dxy = q[2]; |
| 248 | dxy -= q[0]; |
| 249 | double length = dxy.length(); // OPTIMIZE: get rid of sqrt |
| 250 | return fabs(mid.cross(dxy) / length); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 251 | } |
| 252 | |
| 253 | // FIXME ? should this measure both and then use the quad that is the flattest as the line? |
| 254 | static bool isLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) { |
| 255 | double measure = flatMeasure(q1); |
| 256 | // OPTIMIZE: (get rid of sqrt) use approximately_zero |
| 257 | if (!approximately_zero_sqrt(measure)) { |
| 258 | return false; |
| 259 | } |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 260 | return isLinearInner(q1, 0, 1, q2, 0, 1, i, NULL); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 261 | } |
| 262 | |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 263 | // FIXME: if flat measure is sufficiently large, then probably the quartic solution failed |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 264 | static void relaxedIsLinear(const Quadratic& q1, const Quadratic& q2, Intersections& i) { |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 265 | double m1 = flatMeasure(q1); |
| 266 | double m2 = flatMeasure(q2); |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 267 | #if SK_DEBUG |
| 268 | double min = SkTMin(m1, m2); |
| 269 | if (min > 5) { |
| 270 | SkDebugf("%s maybe not flat enough.. %1.9g\n", __FUNCTION__, min); |
| 271 | } |
| 272 | #endif |
caryclark@google.com | 05c4bad | 2013-01-19 13:22:39 +0000 | [diff] [blame] | 273 | i.reset(); |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 274 | const Quadratic& rounder = m2 < m1 ? q1 : q2; |
| 275 | const Quadratic& flatter = m2 < m1 ? q2 : q1; |
| 276 | bool subDivide = false; |
| 277 | isLinearInner(flatter, 0, 1, rounder, 0, 1, i, &subDivide); |
| 278 | if (subDivide) { |
| 279 | QuadraticPair pair; |
| 280 | chop_at(flatter, pair, 0.5); |
| 281 | Intersections firstI, secondI; |
| 282 | relaxedIsLinear(pair.first(), rounder, firstI); |
| 283 | for (int index = 0; index < firstI.used(); ++index) { |
| 284 | i.insert(firstI.fT[0][index] * 0.5, firstI.fT[1][index]); |
| 285 | } |
| 286 | relaxedIsLinear(pair.second(), rounder, secondI); |
| 287 | for (int index = 0; index < secondI.used(); ++index) { |
| 288 | i.insert(0.5 + secondI.fT[0][index] * 0.5, secondI.fT[1][index]); |
| 289 | } |
| 290 | } |
| 291 | if (m2 < m1) { |
| 292 | i.swapPts(); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 293 | } |
| 294 | } |
| 295 | |
| 296 | #if 0 |
| 297 | static void unsortableExpanse(const Quadratic& q1, const Quadratic& q2, Intersections& i) { |
| 298 | const Quadratic* qs[2] = { &q1, &q2 }; |
| 299 | // need t values for start and end of unsortable expanse on both curves |
| 300 | // try projecting lines parallel to the end points |
| 301 | i.fT[0][0] = 0; |
| 302 | i.fT[0][1] = 1; |
| 303 | int flip = -1; // undecided |
| 304 | for (int qIdx = 0; qIdx < 2; qIdx++) { |
| 305 | for (int t = 0; t < 2; t++) { |
| 306 | _Point dxdy; |
caryclark@google.com | 05c4bad | 2013-01-19 13:22:39 +0000 | [diff] [blame] | 307 | dxdy_at_t(*qs[qIdx], t, dxdy); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 308 | _Line perp; |
| 309 | perp[0] = perp[1] = (*qs[qIdx])[t == 0 ? 0 : 2]; |
| 310 | perp[0].x += dxdy.y; |
| 311 | perp[0].y -= dxdy.x; |
| 312 | perp[1].x -= dxdy.y; |
| 313 | perp[1].y += dxdy.x; |
| 314 | Intersections hitData; |
| 315 | int hits = intersectRay(*qs[qIdx ^ 1], perp, hitData); |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 316 | SkASSERT(hits <= 1); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 317 | if (hits) { |
| 318 | if (flip < 0) { |
| 319 | _Point dxdy2; |
caryclark@google.com | 05c4bad | 2013-01-19 13:22:39 +0000 | [diff] [blame] | 320 | dxdy_at_t(*qs[qIdx ^ 1], hitData.fT[0][0], dxdy2); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 321 | double dot = dxdy.dot(dxdy2); |
| 322 | flip = dot < 0; |
| 323 | i.fT[1][0] = flip; |
| 324 | i.fT[1][1] = !flip; |
| 325 | } |
| 326 | i.fT[qIdx ^ 1][t ^ flip] = hitData.fT[0][0]; |
| 327 | } |
| 328 | } |
| 329 | } |
| 330 | i.fUnsortable = true; // failed, probably coincident or near-coincident |
| 331 | i.fUsed = 2; |
| 332 | } |
| 333 | #endif |
| 334 | |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 335 | bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) { |
caryclark@google.com | 6aea33f | 2012-10-09 14:11:58 +0000 | [diff] [blame] | 336 | // if the quads share an end point, check to see if they overlap |
| 337 | |
| 338 | if (onlyEndPtsInCommon(q1, q2, i)) { |
caryclark@google.com | 6aea33f | 2012-10-09 14:11:58 +0000 | [diff] [blame] | 339 | return i.intersected(); |
| 340 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 341 | if (onlyEndPtsInCommon(q2, q1, i)) { |
| 342 | i.swapPts(); |
| 343 | return i.intersected(); |
| 344 | } |
| 345 | // see if either quad is really a line |
| 346 | if (isLinear(q1, q2, i)) { |
| 347 | return i.intersected(); |
| 348 | } |
| 349 | if (isLinear(q2, q1, i)) { |
| 350 | i.swapPts(); |
| 351 | return i.intersected(); |
| 352 | } |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 353 | QuadImplicitForm i1(q1); |
| 354 | QuadImplicitForm i2(q2); |
| 355 | if (i1.implicit_match(i2)) { |
| 356 | // FIXME: compute T values |
| 357 | // compute the intersections of the ends to find the coincident span |
| 358 | bool useVertical = fabs(q1[0].x - q1[2].x) < fabs(q1[0].y - q1[2].y); |
| 359 | double t; |
| 360 | if ((t = axialIntersect(q1, q2[0], useVertical)) >= 0) { |
| 361 | i.addCoincident(t, 0); |
| 362 | } |
| 363 | if ((t = axialIntersect(q1, q2[2], useVertical)) >= 0) { |
| 364 | i.addCoincident(t, 1); |
| 365 | } |
| 366 | useVertical = fabs(q2[0].x - q2[2].x) < fabs(q2[0].y - q2[2].y); |
| 367 | if ((t = axialIntersect(q2, q1[0], useVertical)) >= 0) { |
| 368 | i.addCoincident(0, t); |
| 369 | } |
| 370 | if ((t = axialIntersect(q2, q1[2], useVertical)) >= 0) { |
| 371 | i.addCoincident(1, t); |
| 372 | } |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 373 | SkASSERT(i.fCoincidentUsed <= 2); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 374 | return i.fCoincidentUsed > 0; |
| 375 | } |
| 376 | double roots1[4], roots2[4]; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 377 | bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0]; |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 378 | int rootCount = findRoots(i2, q1, roots1, useCubic); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 379 | // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 |
caryclark@google.com | 9f60291 | 2013-01-24 21:47:16 +0000 | [diff] [blame] | 380 | int rootCount2 = findRoots(i1, q2, roots2, useCubic); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 381 | addValidRoots(roots1, rootCount, 0, i); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 382 | addValidRoots(roots2, rootCount2, 1, i); |
caryclark@google.com | 0b7da43 | 2012-10-31 19:00:20 +0000 | [diff] [blame] | 383 | if (i.insertBalanced() && i.fUsed <= 1) { |
| 384 | if (i.fUsed == 1) { |
| 385 | _Point xy1, xy2; |
| 386 | xy_at_t(q1, i.fT[0][0], xy1.x, xy1.y); |
| 387 | xy_at_t(q2, i.fT[1][0], xy2.x, xy2.y); |
| 388 | if (!xy1.approximatelyEqual(xy2)) { |
| 389 | --i.fUsed; |
| 390 | --i.fUsed2; |
| 391 | } |
| 392 | } |
| 393 | return i.intersected(); |
| 394 | } |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 395 | _Point pts[4]; |
caryclark@google.com | 0b7da43 | 2012-10-31 19:00:20 +0000 | [diff] [blame] | 396 | int closest[4]; |
| 397 | double dist[4]; |
caryclark@google.com | d168874 | 2012-09-18 20:08:37 +0000 | [diff] [blame] | 398 | int index, ndex2; |
| 399 | for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { |
| 400 | xy_at_t(q2, i.fT[1][ndex2], pts[ndex2].x, pts[ndex2].y); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 401 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 402 | bool foundSomething = false; |
caryclark@google.com | 0b7da43 | 2012-10-31 19:00:20 +0000 | [diff] [blame] | 403 | for (index = 0; index < i.fUsed; ++index) { |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 404 | _Point xy; |
| 405 | xy_at_t(q1, i.fT[0][index], xy.x, xy.y); |
caryclark@google.com | 0b7da43 | 2012-10-31 19:00:20 +0000 | [diff] [blame] | 406 | dist[index] = DBL_MAX; |
| 407 | closest[index] = -1; |
caryclark@google.com | d168874 | 2012-09-18 20:08:37 +0000 | [diff] [blame] | 408 | for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) { |
caryclark@google.com | 0b7da43 | 2012-10-31 19:00:20 +0000 | [diff] [blame] | 409 | if (!pts[ndex2].approximatelyEqual(xy)) { |
| 410 | continue; |
| 411 | } |
| 412 | double dx = pts[ndex2].x - xy.x; |
| 413 | double dy = pts[ndex2].y - xy.y; |
| 414 | double distance = dx * dx + dy * dy; |
| 415 | if (dist[index] <= distance) { |
| 416 | continue; |
| 417 | } |
| 418 | for (int outer = 0; outer < index; ++outer) { |
| 419 | if (closest[outer] != ndex2) { |
| 420 | continue; |
| 421 | } |
| 422 | if (dist[outer] < distance) { |
| 423 | goto next; |
| 424 | } |
| 425 | closest[outer] = -1; |
| 426 | } |
| 427 | dist[index] = distance; |
| 428 | closest[index] = ndex2; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 429 | foundSomething = true; |
caryclark@google.com | 0b7da43 | 2012-10-31 19:00:20 +0000 | [diff] [blame] | 430 | next: |
| 431 | ; |
| 432 | } |
| 433 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 434 | if (i.fUsed && i.fUsed2 && !foundSomething) { |
caryclark@google.com | 85ec74c | 2013-01-28 19:25:51 +0000 | [diff] [blame] | 435 | relaxedIsLinear(q1, q2, i); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 436 | return i.intersected(); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 437 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 438 | double roots1Copy[4], roots2Copy[4]; |
| 439 | memcpy(roots1Copy, i.fT[0], i.fUsed * sizeof(double)); |
| 440 | memcpy(roots2Copy, i.fT[1], i.fUsed2 * sizeof(double)); |
| 441 | int used = 0; |
| 442 | do { |
| 443 | double lowest = DBL_MAX; |
| 444 | int lowestIndex = -1; |
| 445 | for (index = 0; index < i.fUsed; ++index) { |
| 446 | if (closest[index] < 0) { |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 447 | continue; |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 448 | } |
| 449 | if (roots1Copy[index] < lowest) { |
| 450 | lowestIndex = index; |
| 451 | lowest = roots1Copy[index]; |
| 452 | } |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 453 | } |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 454 | if (lowestIndex < 0) { |
| 455 | break; |
| 456 | } |
| 457 | i.fT[0][used] = roots1Copy[lowestIndex]; |
| 458 | i.fT[1][used] = roots2Copy[closest[lowestIndex]]; |
| 459 | closest[lowestIndex] = -1; |
| 460 | } while (++used < i.fUsed); |
| 461 | i.fUsed = i.fUsed2 = used; |
| 462 | i.fFlip = false; |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 463 | return i.intersected(); |
| 464 | } |