1 /* 2 * Copyright 2013 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 #include "PathOpsTestCommon.h" 8 #include "SkIntersections.h" 9 #include "SkOpContour.h" 10 #include "SkOpSegment.h" 11 #include "SkRandom.h" 12 #include "SkTArray.h" 13 #include "SkTSort.h" 14 #include "Test.h" 15 16 static bool gPathOpsAngleIdeasVerbose = false; 17 static bool gPathOpsAngleIdeasEnableBruteCheck = false; 18 19 class PathOpsAngleTester { 20 public: 21 static int ConvexHullOverlaps(SkOpAngle& lh, SkOpAngle& rh) { 22 return lh.convexHullOverlaps(&rh); 23 } 24 25 static int EndsIntersect(SkOpAngle& lh, SkOpAngle& rh) { 26 return lh.endsIntersect(&rh); 27 } 28 }; 29 30 struct TRange { 31 double tMin1; 32 double tMin2; 33 double t1; 34 double t2; 35 double tMin; 36 double a1; 37 double a2; 38 bool ccw; 39 }; 40 41 static double testArc(skiatest::Reporter* reporter, const SkDQuad& quad, const SkDQuad& arcRef, 42 int octant) { 43 SkDQuad arc = arcRef; 44 SkDVector offset = {quad[0].fX, quad[0].fY}; 45 arc[0] += offset; 46 arc[1] += offset; 47 arc[2] += offset; 48 SkIntersections i; 49 i.intersect(arc, quad); 50 if (i.used() == 0) { 51 return -1; 52 } 53 int smallest = -1; 54 double t = 2; 55 for (int idx = 0; idx < i.used(); ++idx) { 56 if (i[0][idx] > 1 || i[0][idx] < 0) { 57 i.reset(); 58 i.intersect(arc, quad); 59 } 60 if (i[1][idx] > 1 || i[1][idx] < 0) { 61 i.reset(); 62 i.intersect(arc, quad); 63 } 64 if (t > i[1][idx]) { 65 smallest = idx; 66 t = i[1][idx]; 67 } 68 } 69 REPORTER_ASSERT(reporter, smallest >= 0); 70 REPORTER_ASSERT(reporter, t >= 0 && t <= 1); 71 return i[1][smallest]; 72 } 73 74 static void orderQuads(skiatest::Reporter* reporter, const SkDQuad& quad, double radius, 75 SkTArray<double, false>* tArray) { 76 double r = radius; 77 double s = r * SK_ScalarTanPIOver8; 78 double m = r * SK_ScalarRoot2Over2; 79 // construct circle from quads 80 const QuadPts circle[8] = {{{{ r, 0}, { r, -s}, { m, -m}}}, 81 {{{ m, -m}, { s, -r}, { 0, -r}}}, 82 {{{ 0, -r}, {-s, -r}, {-m, -m}}}, 83 {{{-m, -m}, {-r, -s}, {-r, 0}}}, 84 {{{-r, 0}, {-r, s}, {-m, m}}}, 85 {{{-m, m}, {-s, r}, { 0, r}}}, 86 {{{ 0, r}, { s, r}, { m, m}}}, 87 {{{ m, m}, { r, s}, { r, 0}}}}; 88 for (int octant = 0; octant < 8; ++octant) { 89 SkDQuad cQuad; 90 cQuad.debugSet(circle[octant].fPts); 91 double t = testArc(reporter, quad, cQuad, octant); 92 if (t < 0) { 93 continue; 94 } 95 for (int index = 0; index < tArray->count(); ++index) { 96 double matchT = (*tArray)[index]; 97 if (approximately_equal(t, matchT)) { 98 goto next; 99 } 100 } 101 tArray->push_back(t); 102 next: ; 103 } 104 } 105 106 static double quadAngle(skiatest::Reporter* reporter, const SkDQuad& quad, double t) { 107 const SkDVector& pt = quad.ptAtT(t) - quad[0]; 108 double angle = (atan2(pt.fY, pt.fX) + SK_ScalarPI) * 8 / (SK_ScalarPI * 2); 109 REPORTER_ASSERT(reporter, angle >= 0 && angle <= 8); 110 return angle; 111 } 112 113 static bool angleDirection(double a1, double a2) { 114 double delta = a1 - a2; 115 return (delta < 4 && delta > 0) || delta < -4; 116 } 117 118 static void setQuadHullSweep(const SkDQuad& quad, SkDVector sweep[2]) { 119 sweep[0] = quad[1] - quad[0]; 120 sweep[1] = quad[2] - quad[0]; 121 } 122 123 static double distEndRatio(double dist, const SkDQuad& quad) { 124 SkDVector v[] = {quad[2] - quad[0], quad[1] - quad[0], quad[2] - quad[1]}; 125 double longest = SkTMax(v[0].length(), SkTMax(v[1].length(), v[2].length())); 126 return longest / dist; 127 } 128 129 static bool checkParallel(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2) { 130 SkDVector sweep[2], tweep[2]; 131 setQuadHullSweep(quad1, sweep); 132 setQuadHullSweep(quad2, tweep); 133 // if the ctrl tangents are not nearly parallel, use them 134 // solve for opposite direction displacement scale factor == m 135 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 136 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 137 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 138 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 139 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 140 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 141 // m = v1.cross(v2) / v1.dot(v2) 142 double s0dt0 = sweep[0].dot(tweep[0]); 143 REPORTER_ASSERT(reporter, s0dt0 != 0); 144 double s0xt0 = sweep[0].crossCheck(tweep[0]); 145 double m = s0xt0 / s0dt0; 146 double sDist = sweep[0].length() * m; 147 double tDist = tweep[0].length() * m; 148 bool useS = fabs(sDist) < fabs(tDist); 149 double mFactor = fabs(useS ? distEndRatio(sDist, quad1) : distEndRatio(tDist, quad2)); 150 if (mFactor < 5000) { // empirically found limit 151 return s0xt0 < 0; 152 } 153 SkDVector m0 = quad1.ptAtT(0.5) - quad1[0]; 154 SkDVector m1 = quad2.ptAtT(0.5) - quad2[0]; 155 return m0.crossCheck(m1) < 0; 156 } 157 158 /* returns 159 -1 if overlaps 160 0 if no overlap cw 161 1 if no overlap ccw 162 */ 163 static int quadHullsOverlap(skiatest::Reporter* reporter, const SkDQuad& quad1, 164 const SkDQuad& quad2) { 165 SkDVector sweep[2], tweep[2]; 166 setQuadHullSweep(quad1, sweep); 167 setQuadHullSweep(quad2, tweep); 168 double s0xs1 = sweep[0].crossCheck(sweep[1]); 169 double s0xt0 = sweep[0].crossCheck(tweep[0]); 170 double s1xt0 = sweep[1].crossCheck(tweep[0]); 171 bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0; 172 double s0xt1 = sweep[0].crossCheck(tweep[1]); 173 double s1xt1 = sweep[1].crossCheck(tweep[1]); 174 tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; 175 double t0xt1 = tweep[0].crossCheck(tweep[1]); 176 if (tBetweenS) { 177 return -1; 178 } 179 if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1 180 return -1; 181 } 182 bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0; 183 sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; 184 if (sBetweenT) { 185 return -1; 186 } 187 // if all of the sweeps are in the same half plane, then the order of any pair is enough 188 if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { 189 return 0; 190 } 191 if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { 192 return 1; 193 } 194 // if the outside sweeps are greater than 180 degress: 195 // first assume the inital tangents are the ordering 196 // if the midpoint direction matches the inital order, that is enough 197 SkDVector m0 = quad1.ptAtT(0.5) - quad1[0]; 198 SkDVector m1 = quad2.ptAtT(0.5) - quad2[0]; 199 double m0xm1 = m0.crossCheck(m1); 200 if (s0xt0 > 0 && m0xm1 > 0) { 201 return 0; 202 } 203 if (s0xt0 < 0 && m0xm1 < 0) { 204 return 1; 205 } 206 REPORTER_ASSERT(reporter, s0xt0 != 0); 207 return checkParallel(reporter, quad1, quad2); 208 } 209 210 static double radianSweep(double start, double end) { 211 double sweep = end - start; 212 if (sweep > SK_ScalarPI) { 213 sweep -= 2 * SK_ScalarPI; 214 } else if (sweep < -SK_ScalarPI) { 215 sweep += 2 * SK_ScalarPI; 216 } 217 return sweep; 218 } 219 220 static bool radianBetween(double start, double test, double end) { 221 double startToEnd = radianSweep(start, end); 222 double startToTest = radianSweep(start, test); 223 double testToEnd = radianSweep(test, end); 224 return (startToTest <= 0 && testToEnd <= 0 && startToTest >= startToEnd) || 225 (startToTest >= 0 && testToEnd >= 0 && startToTest <= startToEnd); 226 } 227 228 static bool orderTRange(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 229 double r, TRange* result) { 230 SkTArray<double, false> t1Array, t2Array; 231 orderQuads(reporter, quad1, r, &t1Array); 232 orderQuads(reporter,quad2, r, &t2Array); 233 if (!t1Array.count() || !t2Array.count()) { 234 return false; 235 } 236 SkTQSort<double>(t1Array.begin(), t1Array.end() - 1); 237 SkTQSort<double>(t2Array.begin(), t2Array.end() - 1); 238 double t1 = result->tMin1 = t1Array[0]; 239 double t2 = result->tMin2 = t2Array[0]; 240 double a1 = quadAngle(reporter,quad1, t1); 241 double a2 = quadAngle(reporter,quad2, t2); 242 if (approximately_equal(a1, a2)) { 243 return false; 244 } 245 bool refCCW = angleDirection(a1, a2); 246 result->t1 = t1; 247 result->t2 = t2; 248 result->tMin = SkTMin(t1, t2); 249 result->a1 = a1; 250 result->a2 = a2; 251 result->ccw = refCCW; 252 return true; 253 } 254 255 static bool equalPoints(const SkDPoint& pt1, const SkDPoint& pt2, double max) { 256 return approximately_zero_when_compared_to(pt1.fX - pt2.fX, max) 257 && approximately_zero_when_compared_to(pt1.fY - pt2.fY, max); 258 } 259 260 static double maxDist(const SkDQuad& quad) { 261 SkDRect bounds; 262 bounds.setBounds(quad); 263 SkDVector corner[4] = { 264 { bounds.fLeft - quad[0].fX, bounds.fTop - quad[0].fY }, 265 { bounds.fRight - quad[0].fX, bounds.fTop - quad[0].fY }, 266 { bounds.fLeft - quad[0].fX, bounds.fBottom - quad[0].fY }, 267 { bounds.fRight - quad[0].fX, bounds.fBottom - quad[0].fY } 268 }; 269 double max = 0; 270 for (unsigned index = 0; index < SK_ARRAY_COUNT(corner); ++index) { 271 max = SkTMax(max, corner[index].length()); 272 } 273 return max; 274 } 275 276 static double maxQuad(const SkDQuad& quad) { 277 double max = 0; 278 for (int index = 0; index < 2; ++index) { 279 max = SkTMax(max, fabs(quad[index].fX)); 280 max = SkTMax(max, fabs(quad[index].fY)); 281 } 282 return max; 283 } 284 285 static bool bruteMinT(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 286 TRange* lowerRange, TRange* upperRange) { 287 double maxRadius = SkTMin(maxDist(quad1), maxDist(quad2)); 288 double maxQuads = SkTMax(maxQuad(quad1), maxQuad(quad2)); 289 double r = maxRadius / 2; 290 double rStep = r / 2; 291 SkDPoint best1 = {SK_ScalarInfinity, SK_ScalarInfinity}; 292 SkDPoint best2 = {SK_ScalarInfinity, SK_ScalarInfinity}; 293 int bestCCW = -1; 294 double bestR = maxRadius; 295 upperRange->tMin = 0; 296 lowerRange->tMin = 1; 297 do { 298 do { // find upper bounds of single result 299 TRange tRange; 300 bool stepUp = orderTRange(reporter, quad1, quad2, r, &tRange); 301 if (stepUp) { 302 SkDPoint pt1 = quad1.ptAtT(tRange.t1); 303 if (equalPoints(pt1, best1, maxQuads)) { 304 break; 305 } 306 best1 = pt1; 307 SkDPoint pt2 = quad2.ptAtT(tRange.t2); 308 if (equalPoints(pt2, best2, maxQuads)) { 309 break; 310 } 311 best2 = pt2; 312 if (gPathOpsAngleIdeasVerbose) { 313 SkDebugf("u bestCCW=%d ccw=%d bestMin=%1.9g:%1.9g r=%1.9g tMin=%1.9g\n", 314 bestCCW, tRange.ccw, lowerRange->tMin, upperRange->tMin, r, 315 tRange.tMin); 316 } 317 if (bestCCW >= 0 && bestCCW != (int) tRange.ccw) { 318 if (tRange.tMin < upperRange->tMin) { 319 upperRange->tMin = 0; 320 } else { 321 stepUp = false; 322 } 323 } 324 if (upperRange->tMin < tRange.tMin) { 325 bestCCW = tRange.ccw; 326 bestR = r; 327 *upperRange = tRange; 328 } 329 if (lowerRange->tMin > tRange.tMin) { 330 *lowerRange = tRange; 331 } 332 } 333 r += stepUp ? rStep : -rStep; 334 rStep /= 2; 335 } while (rStep > FLT_EPSILON); 336 if (bestCCW < 0) { 337 if (bestR >= maxRadius) { 338 SkDebugf(""); 339 } 340 REPORTER_ASSERT(reporter, bestR < maxRadius); 341 return false; 342 } 343 double lastHighR = bestR; 344 r = bestR / 2; 345 rStep = r / 2; 346 do { // find lower bounds of single result 347 TRange tRange; 348 bool success = orderTRange(reporter, quad1, quad2, r, &tRange); 349 if (success) { 350 if (gPathOpsAngleIdeasVerbose) { 351 SkDebugf("l bestCCW=%d ccw=%d bestMin=%1.9g:%1.9g r=%1.9g tMin=%1.9g\n", 352 bestCCW, tRange.ccw, lowerRange->tMin, upperRange->tMin, r, 353 tRange.tMin); 354 } 355 if (bestCCW != (int) tRange.ccw || upperRange->tMin < tRange.tMin) { 356 bestCCW = tRange.ccw; 357 *upperRange = tRange; 358 bestR = lastHighR; 359 break; // need to establish a new upper bounds 360 } 361 SkDPoint pt1 = quad1.ptAtT(tRange.t1); 362 SkDPoint pt2 = quad2.ptAtT(tRange.t2); 363 if (equalPoints(pt1, best1, maxQuads)) { 364 goto breakOut; 365 } 366 best1 = pt1; 367 if (equalPoints(pt2, best2, maxQuads)) { 368 goto breakOut; 369 } 370 best2 = pt2; 371 if (equalPoints(pt1, pt2, maxQuads)) { 372 success = false; 373 } else { 374 if (upperRange->tMin < tRange.tMin) { 375 *upperRange = tRange; 376 } 377 if (lowerRange->tMin > tRange.tMin) { 378 *lowerRange = tRange; 379 } 380 } 381 lastHighR = SkTMin(r, lastHighR); 382 } 383 r += success ? -rStep : rStep; 384 rStep /= 2; 385 } while (rStep > FLT_EPSILON); 386 } while (rStep > FLT_EPSILON); 387 breakOut: 388 if (gPathOpsAngleIdeasVerbose) { 389 SkDebugf("l a2-a1==%1.9g\n", lowerRange->a2 - lowerRange->a1); 390 } 391 return true; 392 } 393 394 static void bruteForce(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 395 bool ccw) { 396 if (!gPathOpsAngleIdeasEnableBruteCheck) { 397 return; 398 } 399 TRange lowerRange, upperRange; 400 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); 401 REPORTER_ASSERT(reporter, result); 402 double angle = fabs(lowerRange.a2 - lowerRange.a1); 403 REPORTER_ASSERT(reporter, angle > 3.998 || ccw == upperRange.ccw); 404 } 405 406 static bool bruteForceCheck(skiatest::Reporter* reporter, const SkDQuad& quad1, 407 const SkDQuad& quad2, bool ccw) { 408 TRange lowerRange, upperRange; 409 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange); 410 REPORTER_ASSERT(reporter, result); 411 return ccw == upperRange.ccw; 412 } 413 414 static void makeSegment(SkOpContour* contour, const SkDQuad& quad, SkPoint shortQuad[3]) { 415 shortQuad[0] = quad[0].asSkPoint(); 416 shortQuad[1] = quad[1].asSkPoint(); 417 shortQuad[2] = quad[2].asSkPoint(); 418 contour->addQuad(shortQuad); 419 } 420 421 static void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2, 422 int testNo, SkArenaAlloc* allocator) { 423 SkPoint shortQuads[2][3]; 424 425 SkOpContourHead contour; 426 SkOpGlobalState state(&contour, allocator SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr)); 427 contour.init(&state, false, false); 428 makeSegment(&contour, quad1, shortQuads[0]); 429 makeSegment(&contour, quad1, shortQuads[1]); 430 SkOpSegment* seg1 = contour.first(); 431 seg1->debugAddAngle(0, 1); 432 SkOpSegment* seg2 = seg1->next(); 433 seg2->debugAddAngle(0, 1); 434 int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(*seg1->debugLastAngle(), 435 *seg2->debugLastAngle()); 436 const SkDPoint& origin = quad1[0]; 437 REPORTER_ASSERT(reporter, origin == quad2[0]); 438 double a1s = atan2(origin.fY - quad1[1].fY, quad1[1].fX - origin.fX); 439 double a1e = atan2(origin.fY - quad1[2].fY, quad1[2].fX - origin.fX); 440 double a2s = atan2(origin.fY - quad2[1].fY, quad2[1].fX - origin.fX); 441 double a2e = atan2(origin.fY - quad2[2].fY, quad2[2].fX - origin.fX); 442 bool oldSchoolOverlap = radianBetween(a1s, a2s, a1e) 443 || radianBetween(a1s, a2e, a1e) || radianBetween(a2s, a1s, a2e) 444 || radianBetween(a2s, a1e, a2e); 445 int overlap = quadHullsOverlap(reporter, quad1, quad2); 446 bool realMatchesOverlap = realOverlap == overlap || SK_ScalarPI - fabs(a2s - a1s) < 0.002; 447 if (realOverlap != overlap) { 448 SkDebugf("\nSK_ScalarPI - fabs(a2s - a1s) = %1.9g\n", SK_ScalarPI - fabs(a2s - a1s)); 449 } 450 if (!realMatchesOverlap) { 451 DumpQ(quad1, quad2, testNo); 452 } 453 REPORTER_ASSERT(reporter, realMatchesOverlap); 454 if (oldSchoolOverlap != (overlap < 0)) { 455 overlap = quadHullsOverlap(reporter, quad1, quad2); // set a breakpoint and debug if assert fires 456 REPORTER_ASSERT(reporter, oldSchoolOverlap == (overlap < 0)); 457 } 458 SkDVector v1s = quad1[1] - quad1[0]; 459 SkDVector v1e = quad1[2] - quad1[0]; 460 SkDVector v2s = quad2[1] - quad2[0]; 461 SkDVector v2e = quad2[2] - quad2[0]; 462 double vDir[2] = { v1s.cross(v1e), v2s.cross(v2e) }; 463 bool ray1In2 = v1s.cross(v2s) * vDir[1] <= 0 && v1s.cross(v2e) * vDir[1] >= 0; 464 bool ray2In1 = v2s.cross(v1s) * vDir[0] <= 0 && v2s.cross(v1e) * vDir[0] >= 0; 465 if (overlap >= 0) { 466 // verify that hulls really don't overlap 467 REPORTER_ASSERT(reporter, !ray1In2); 468 REPORTER_ASSERT(reporter, !ray2In1); 469 bool ctrl1In2 = v1e.cross(v2s) * vDir[1] <= 0 && v1e.cross(v2e) * vDir[1] >= 0; 470 REPORTER_ASSERT(reporter, !ctrl1In2); 471 bool ctrl2In1 = v2e.cross(v1s) * vDir[0] <= 0 && v2e.cross(v1e) * vDir[0] >= 0; 472 REPORTER_ASSERT(reporter, !ctrl2In1); 473 // check answer against reference 474 bruteForce(reporter, quad1, quad2, overlap > 0); 475 } 476 // continue end point rays and see if they intersect the opposite curve 477 SkDLine rays[] = {{{origin, quad2[2]}}, {{origin, quad1[2]}}}; 478 const SkDQuad* quads[] = {&quad1, &quad2}; 479 SkDVector midSpokes[2]; 480 SkIntersections intersect[2]; 481 double minX, minY, maxX, maxY; 482 minX = minY = SK_ScalarInfinity; 483 maxX = maxY = -SK_ScalarInfinity; 484 double maxWidth = 0; 485 bool useIntersect = false; 486 double smallestTs[] = {1, 1}; 487 for (unsigned index = 0; index < SK_ARRAY_COUNT(quads); ++index) { 488 const SkDQuad& q = *quads[index]; 489 midSpokes[index] = q.ptAtT(0.5) - origin; 490 minX = SkTMin(SkTMin(SkTMin(minX, origin.fX), q[1].fX), q[2].fX); 491 minY = SkTMin(SkTMin(SkTMin(minY, origin.fY), q[1].fY), q[2].fY); 492 maxX = SkTMax(SkTMax(SkTMax(maxX, origin.fX), q[1].fX), q[2].fX); 493 maxY = SkTMax(SkTMax(SkTMax(maxY, origin.fY), q[1].fY), q[2].fY); 494 maxWidth = SkTMax(maxWidth, SkTMax(maxX - minX, maxY - minY)); 495 intersect[index].intersectRay(q, rays[index]); 496 const SkIntersections& i = intersect[index]; 497 REPORTER_ASSERT(reporter, i.used() >= 1); 498 bool foundZero = false; 499 double smallT = 1; 500 for (int idx2 = 0; idx2 < i.used(); ++idx2) { 501 double t = i[0][idx2]; 502 if (t == 0) { 503 foundZero = true; 504 continue; 505 } 506 if (smallT > t) { 507 smallT = t; 508 } 509 } 510 REPORTER_ASSERT(reporter, foundZero == true); 511 if (smallT == 1) { 512 continue; 513 } 514 SkDVector ray = q.ptAtT(smallT) - origin; 515 SkDVector end = rays[index][1] - origin; 516 if (ray.fX * end.fX < 0 || ray.fY * end.fY < 0) { 517 continue; 518 } 519 double rayDist = ray.length(); 520 double endDist = end.length(); 521 double delta = fabs(rayDist - endDist) / maxWidth; 522 if (delta > 1e-4) { 523 useIntersect ^= true; 524 } 525 smallestTs[index] = smallT; 526 } 527 bool firstInside; 528 if (useIntersect) { 529 int sIndex = (int) (smallestTs[1] < 1); 530 REPORTER_ASSERT(reporter, smallestTs[sIndex ^ 1] == 1); 531 double t = smallestTs[sIndex]; 532 const SkDQuad& q = *quads[sIndex]; 533 SkDVector ray = q.ptAtT(t) - origin; 534 SkDVector end = rays[sIndex][1] - origin; 535 double rayDist = ray.length(); 536 double endDist = end.length(); 537 SkDVector mid = q.ptAtT(t / 2) - origin; 538 double midXray = mid.crossCheck(ray); 539 if (gPathOpsAngleIdeasVerbose) { 540 SkDebugf("rayDist>endDist:%d sIndex==0:%d vDir[sIndex]<0:%d midXray<0:%d\n", 541 rayDist > endDist, sIndex == 0, vDir[sIndex] < 0, midXray < 0); 542 } 543 SkASSERT(SkScalarSignAsInt(SkDoubleToScalar(midXray)) 544 == SkScalarSignAsInt(SkDoubleToScalar(vDir[sIndex]))); 545 firstInside = (rayDist > endDist) ^ (sIndex == 0) ^ (vDir[sIndex] < 0); 546 } else if (overlap >= 0) { 547 return; // answer has already been determined 548 } else { 549 firstInside = checkParallel(reporter, quad1, quad2); 550 } 551 if (overlap < 0) { 552 SkDEBUGCODE(int realEnds =) 553 PathOpsAngleTester::EndsIntersect(*seg1->debugLastAngle(), 554 *seg2->debugLastAngle()); 555 SkASSERT(realEnds == (firstInside ? 1 : 0)); 556 } 557 bruteForce(reporter, quad1, quad2, firstInside); 558 } 559 560 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) { 561 SkSTArenaAlloc<4096> allocator; 562 // gPathOpsAngleIdeasVerbose = true; 563 const QuadPts quads[] = { 564 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875}, {736.8936767578125, -350.717529296875}}}, 565 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125}, {-509.62615966796875, 576.1182861328125}}} 566 }; 567 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) { 568 SkDQuad quad0, quad1; 569 quad0.debugSet(quads[index].fPts); 570 quad1.debugSet(quads[index + 1].fPts); 571 testQuadAngles(reporter, quad0, quad1, 0, &allocator); 572 } 573 } 574 575 DEF_TEST(PathOpsAngleOverlapHulls, reporter) { 576 SkSTArenaAlloc<4096> allocator; 577 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 578 return; 579 } 580 SkRandom ran; 581 for (int index = 0; index < 100000; ++index) { 582 if (index % 1000 == 999) SkDebugf("."); 583 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}; 584 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 585 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 586 if (quad1.fPts[0] == quad1.fPts[2]) { 587 continue; 588 } 589 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 590 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 591 if (quad2.fPts[0] == quad2.fPts[2]) { 592 continue; 593 } 594 SkIntersections i; 595 SkDQuad q1, q2; 596 q1.debugSet(quad1.fPts); 597 q2.debugSet(quad2.fPts); 598 i.intersect(q1, q2); 599 REPORTER_ASSERT(reporter, i.used() >= 1); 600 if (i.used() > 1) { 601 continue; 602 } 603 testQuadAngles(reporter, q1, q2, index, &allocator); 604 } 605 } 606 607 DEF_TEST(PathOpsAngleBruteT, reporter) { 608 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 609 return; 610 } 611 SkRandom ran; 612 double smaller = SK_Scalar1; 613 SkDQuad small[2]; 614 SkDEBUGCODE(int smallIndex = 0); 615 for (int index = 0; index < 100000; ++index) { 616 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}; 617 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 618 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 619 if (quad1.fPts[0] == quad1.fPts[2]) { 620 continue; 621 } 622 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}, 623 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 624 if (quad2.fPts[0] == quad2.fPts[2]) { 625 continue; 626 } 627 SkDQuad q1, q2; 628 q1.debugSet(quad1.fPts); 629 q2.debugSet(quad2.fPts); 630 SkIntersections i; 631 i.intersect(q1, q2); 632 REPORTER_ASSERT(reporter, i.used() >= 1); 633 if (i.used() > 1) { 634 continue; 635 } 636 TRange lowerRange, upperRange; 637 bool result = bruteMinT(reporter, q1, q2, &lowerRange, &upperRange); 638 REPORTER_ASSERT(reporter, result); 639 double min = SkTMin(upperRange.t1, upperRange.t2); 640 if (smaller > min) { 641 small[0] = q1; 642 small[1] = q2; 643 SkDEBUGCODE(smallIndex = index); 644 smaller = min; 645 } 646 } 647 #ifdef SK_DEBUG 648 DumpQ(small[0], small[1], smallIndex); 649 #endif 650 } 651 652 DEF_TEST(PathOpsAngleBruteTOne, reporter) { 653 // gPathOpsAngleIdeasVerbose = true; 654 const QuadPts qPts[] = { 655 {{{-770.8492431640625, 948.2369384765625}, {-853.37066650390625, 972.0301513671875}, {-200.62042236328125, -26.7174072265625}}}, 656 {{{-770.8492431640625, 948.2369384765625}, {513.602783203125, 578.8681640625}, {960.641357421875, -813.69757080078125}}}, 657 {{{563.8267822265625, -107.4566650390625}, {-44.67724609375, -136.57452392578125}, {492.3856201171875, -268.79644775390625}}}, 658 {{{563.8267822265625, -107.4566650390625}, {708.049072265625, -100.77789306640625}, {-48.88226318359375, 967.9022216796875}}}, 659 {{{598.857421875, 846.345458984375}, {-644.095703125, -316.12921142578125}, {-97.64599609375, 20.6158447265625}}}, 660 {{{598.857421875, 846.345458984375}, {715.7142333984375, 955.3599853515625}, {-919.9478759765625, 691.611328125}}}, 661 }; 662 TRange lowerRange, upperRange; 663 SkDQuad quads[SK_ARRAY_COUNT(qPts)]; 664 for (int index = 0; index < (int) SK_ARRAY_COUNT(qPts); ++index) { 665 quads[index].debugSet(qPts[index].fPts); 666 } 667 bruteMinT(reporter, quads[0], quads[1], &lowerRange, &upperRange); 668 bruteMinT(reporter, quads[2], quads[3], &lowerRange, &upperRange); 669 bruteMinT(reporter, quads[4], quads[5], &lowerRange, &upperRange); 670 } 671 672 /* 673 The sorting problem happens when the inital tangents are not a true indicator of the curve direction 674 Nearly always, the initial tangents do give the right answer, 675 so the trick is to figure out when the initial tangent cannot be trusted. 676 If the convex hulls of both curves are in the same half plane, and not overlapping, sorting the 677 hulls is enough. 678 If the hulls overlap, and have the same general direction, then intersect the shorter end point ray 679 with the opposing curve, and see on which side of the shorter curve the opposing intersection lies. 680 Otherwise, if the control vector is extremely short, likely the point on curve must be computed 681 If moving the control point slightly can change the sign of the cross product, either answer could 682 be "right". 683 We need to determine how short is extremely short. Move the control point a set percentage of 684 the largest length to determine how stable the curve is vis-a-vis the initial tangent. 685 */ 686 687 static const QuadPts extremeTests[][2] = { 688 { 689 {{{-708.0077926931004,-154.61669472244046}, 690 {-707.9234268635319,-154.30459999551294}, 691 {505.58447265625,-504.9130859375}}}, 692 {{{-708.0077926931004,-154.61669472244046}, 693 {-711.127526325141,-163.9446090624656}, 694 {-32.39227294921875,-906.3277587890625}}}, 695 }, { 696 {{{-708.0077926931004,-154.61669472244046}, 697 {-708.2875337527566,-154.36676458635623}, 698 {505.58447265625,-504.9130859375}}}, 699 {{{-708.0077926931004,-154.61669472244046}, 700 {-708.4111557216864,-154.5366642875255}, 701 {-32.39227294921875,-906.3277587890625}}}, 702 }, { 703 {{{-609.0230951752058,-267.5435593490574}, 704 {-594.1120809906336,-136.08492475411555}, 705 {505.58447265625,-504.9130859375}}}, 706 {{{-609.0230951752058,-267.5435593490574}, 707 {-693.7467719138988,-341.3259237831895}, 708 {-32.39227294921875,-906.3277587890625}}} 709 }, { 710 {{{-708.0077926931004,-154.61669472244046}, 711 {-707.9994640658723,-154.58588461064852}, 712 {505.58447265625,-504.9130859375}}}, 713 {{{-708.0077926931004,-154.61669472244046}, 714 {-708.0239418990758,-154.6403553507124}, 715 {-32.39227294921875,-906.3277587890625}}} 716 }, { 717 {{{-708.0077926931004,-154.61669472244046}, 718 {-707.9993222215099,-154.55999389855003}, 719 {68.88981098017803,296.9273945411635}}}, 720 {{{-708.0077926931004,-154.61669472244046}, 721 {-708.0509091919608,-154.64675214697067}, 722 {-777.4871194247767,-995.1470120113145}}} 723 }, { 724 {{{-708.0077926931004,-154.61669472244046}, 725 {-708.0060491116379,-154.60889321524968}, 726 {229.97088707895057,-430.0569357467175}}}, 727 {{{-708.0077926931004,-154.61669472244046}, 728 {-708.013911296257,-154.6219143988058}, 729 {138.13162892614037,-573.3689311737394}}} 730 }, { 731 {{{-543.2570545751013,-237.29243831075053}, 732 {-452.4119186056987,-143.47223056267802}, 733 {229.97088707895057,-430.0569357467175}}}, 734 {{{-543.2570545751013,-237.29243831075053}, 735 {-660.5330371214436,-362.0016148388}, 736 {138.13162892614037,-573.3689311737394}}}, 737 }, 738 }; 739 740 static double endCtrlRatio(const SkDQuad quad) { 741 SkDVector longEdge = quad[2] - quad[0]; 742 double longLen = longEdge.length(); 743 SkDVector shortEdge = quad[1] - quad[0]; 744 double shortLen = shortEdge.length(); 745 return longLen / shortLen; 746 } 747 748 static void computeMV(const SkDQuad& quad, const SkDVector& v, double m, SkDVector mV[2]) { 749 SkDPoint mPta = {quad[1].fX - m * v.fY, quad[1].fY + m * v.fX}; 750 SkDPoint mPtb = {quad[1].fX + m * v.fY, quad[1].fY - m * v.fX}; 751 mV[0] = mPta - quad[0]; 752 mV[1] = mPtb - quad[0]; 753 } 754 755 static double mDistance(skiatest::Reporter* reporter, bool agrees, const SkDQuad& q1, 756 const SkDQuad& q2) { 757 if (1 && agrees) { 758 return SK_ScalarMax; 759 } 760 // how close is the angle from inflecting in the opposite direction? 761 SkDVector v1 = q1[1] - q1[0]; 762 SkDVector v2 = q2[1] - q2[0]; 763 double dir = v1.crossCheck(v2); 764 REPORTER_ASSERT(reporter, dir != 0); 765 // solve for opposite direction displacement scale factor == m 766 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x 767 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] 768 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x) 769 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x) 770 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x 771 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) 772 // m = v1.cross(v2) / v1.dot(v2) 773 double div = v1.dot(v2); 774 REPORTER_ASSERT(reporter, div != 0); 775 double m = dir / div; 776 SkDVector mV1[2], mV2[2]; 777 computeMV(q1, v1, m, mV1); 778 computeMV(q2, v2, m, mV2); 779 double dist1 = v1.length() * m; 780 double dist2 = v2.length() * m; 781 if (gPathOpsAngleIdeasVerbose) { 782 SkDebugf("%c r1=%1.9g r2=%1.9g m=%1.9g dist1=%1.9g dist2=%1.9g " 783 " dir%c 1a=%1.9g 1b=%1.9g 2a=%1.9g 2b=%1.9g\n", agrees ? 'T' : 'F', 784 endCtrlRatio(q1), endCtrlRatio(q2), m, dist1, dist2, dir > 0 ? '+' : '-', 785 mV1[0].crossCheck(v2), mV1[1].crossCheck(v2), 786 mV2[0].crossCheck(v1), mV2[1].crossCheck(v1)); 787 } 788 if (1) { 789 bool use1 = fabs(dist1) < fabs(dist2); 790 if (gPathOpsAngleIdeasVerbose) { 791 SkDebugf("%c dist=%1.9g r=%1.9g\n", agrees ? 'T' : 'F', use1 ? dist1 : dist2, 792 use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2)); 793 } 794 return fabs(use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2)); 795 } 796 return SK_ScalarMax; 797 } 798 799 static void midPointAgrees(skiatest::Reporter* reporter, const SkDQuad& q1, const SkDQuad& q2, 800 bool ccw) { 801 SkDPoint mid1 = q1.ptAtT(0.5); 802 SkDVector m1 = mid1 - q1[0]; 803 SkDPoint mid2 = q2.ptAtT(0.5); 804 SkDVector m2 = mid2 - q2[0]; 805 REPORTER_ASSERT(reporter, ccw ? m1.crossCheck(m2) < 0 : m1.crossCheck(m2) > 0); 806 } 807 808 DEF_TEST(PathOpsAngleExtreme, reporter) { 809 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 810 return; 811 } 812 double maxR = SK_ScalarMax; 813 for (int index = 0; index < (int) SK_ARRAY_COUNT(extremeTests); ++index) { 814 const QuadPts& qu1 = extremeTests[index][0]; 815 const QuadPts& qu2 = extremeTests[index][1]; 816 SkDQuad quad1, quad2; 817 quad1.debugSet(qu1.fPts); 818 quad2.debugSet(qu2.fPts); 819 if (gPathOpsAngleIdeasVerbose) { 820 SkDebugf("%s %d\n", __FUNCTION__, index); 821 } 822 REPORTER_ASSERT(reporter, quad1[0] == quad2[0]); 823 SkIntersections i; 824 i.intersect(quad1, quad2); 825 REPORTER_ASSERT(reporter, i.used() == 1); 826 REPORTER_ASSERT(reporter, i.pt(0) == quad1[0]); 827 int overlap = quadHullsOverlap(reporter, quad1, quad2); 828 REPORTER_ASSERT(reporter, overlap >= 0); 829 SkDVector sweep[2], tweep[2]; 830 setQuadHullSweep(quad1, sweep); 831 setQuadHullSweep(quad2, tweep); 832 double s0xt0 = sweep[0].crossCheck(tweep[0]); 833 REPORTER_ASSERT(reporter, s0xt0 != 0); 834 bool ccw = s0xt0 < 0; 835 bool agrees = bruteForceCheck(reporter, quad1, quad2, ccw); 836 maxR = SkTMin(maxR, mDistance(reporter, agrees, quad1, quad2)); 837 if (agrees) { 838 continue; 839 } 840 midPointAgrees(reporter, quad1, quad2, !ccw); 841 SkDQuad q1 = quad1; 842 SkDQuad q2 = quad2; 843 double loFail = 1; 844 double hiPass = 2; 845 // double vectors until t passes 846 do { 847 q1[1].fX = quad1[0].fX * (1 - hiPass) + quad1[1].fX * hiPass; 848 q1[1].fY = quad1[0].fY * (1 - hiPass) + quad1[1].fY * hiPass; 849 q2[1].fX = quad2[0].fX * (1 - hiPass) + quad2[1].fX * hiPass; 850 q2[1].fY = quad2[0].fY * (1 - hiPass) + quad2[1].fY * hiPass; 851 agrees = bruteForceCheck(reporter, q1, q2, ccw); 852 maxR = SkTMin(maxR, mDistance(reporter, agrees, q1, q2)); 853 if (agrees) { 854 break; 855 } 856 midPointAgrees(reporter, quad1, quad2, !ccw); 857 loFail = hiPass; 858 hiPass *= 2; 859 } while (true); 860 // binary search to find minimum pass 861 double midTest = (loFail + hiPass) / 2; 862 double step = (hiPass - loFail) / 4; 863 while (step > FLT_EPSILON) { 864 q1[1].fX = quad1[0].fX * (1 - midTest) + quad1[1].fX * midTest; 865 q1[1].fY = quad1[0].fY * (1 - midTest) + quad1[1].fY * midTest; 866 q2[1].fX = quad2[0].fX * (1 - midTest) + quad2[1].fX * midTest; 867 q2[1].fY = quad2[0].fY * (1 - midTest) + quad2[1].fY * midTest; 868 agrees = bruteForceCheck(reporter, q1, q2, ccw); 869 maxR = SkTMin(maxR, mDistance(reporter, agrees, q1, q2)); 870 if (!agrees) { 871 midPointAgrees(reporter, quad1, quad2, !ccw); 872 } 873 midTest += agrees ? -step : step; 874 step /= 2; 875 } 876 #ifdef SK_DEBUG 877 // DumpQ(q1, q2, 999); 878 #endif 879 } 880 if (gPathOpsAngleIdeasVerbose) { 881 SkDebugf("maxR=%1.9g\n", maxR); 882 } 883 } 884
