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