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/private/SkTArray.h"
8 #include "include/utils/SkRandom.h"
9 #include "src/core/SkTSort.h"
10 #include "src/pathops/SkIntersections.h"
11 #include "src/pathops/SkOpContour.h"
12 #include "src/pathops/SkOpSegment.h"
13 #include "tests/PathOpsTestCommon.h"
14 #include "tests/Test.h"
15
16 static bool gPathOpsAngleIdeasVerbose = false;
17 static bool gPathOpsAngleIdeasEnableBruteCheck = false;
18
19 class PathOpsAngleTester {
20 public:
ConvexHullOverlaps(SkOpAngle & lh,SkOpAngle & rh)21 static int ConvexHullOverlaps(SkOpAngle& lh, SkOpAngle& rh) {
22 return lh.convexHullOverlaps(&rh);
23 }
24
EndsIntersect(SkOpAngle & lh,SkOpAngle & rh)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
testArc(skiatest::Reporter * reporter,const SkDQuad & quad,const SkDQuad & arcRef,int octant)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
orderQuads(skiatest::Reporter * reporter,const SkDQuad & quad,double radius,SkTArray<double,false> * tArray)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
quadAngle(skiatest::Reporter * reporter,const SkDQuad & quad,double t)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
angleDirection(double a1,double a2)113 static bool angleDirection(double a1, double a2) {
114 double delta = a1 - a2;
115 return (delta < 4 && delta > 0) || delta < -4;
116 }
117
setQuadHullSweep(const SkDQuad & quad,SkDVector sweep[2])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
distEndRatio(double dist,const SkDQuad & quad)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 = std::max(v[0].length(), std::max(v[1].length(), v[2].length()));
126 return longest / dist;
127 }
128
checkParallel(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2)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 */
quadHullsOverlap(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2)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
radianSweep(double start,double end)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
radianBetween(double start,double test,double end)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
orderTRange(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,double r,TRange * result)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());
237 SkTQSort<double>(t2Array.begin(), t2Array.end());
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 = std::min(t1, t2);
249 result->a1 = a1;
250 result->a2 = a2;
251 result->ccw = refCCW;
252 return true;
253 }
254
equalPoints(const SkDPoint & pt1,const SkDPoint & pt2,double max)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
maxDist(const SkDQuad & quad)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 = std::max(max, corner[index].length());
272 }
273 return max;
274 }
275
maxQuad(const SkDQuad & quad)276 static double maxQuad(const SkDQuad& quad) {
277 double max = 0;
278 for (int index = 0; index < 2; ++index) {
279 max = std::max(max, fabs(quad[index].fX));
280 max = std::max(max, fabs(quad[index].fY));
281 }
282 return max;
283 }
284
bruteMinT(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,TRange * lowerRange,TRange * upperRange)285 static bool bruteMinT(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2,
286 TRange* lowerRange, TRange* upperRange) {
287 double maxRadius = std::min(maxDist(quad1), maxDist(quad2));
288 double maxQuads = std::max(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 REPORTER_ASSERT(reporter, bestR < maxRadius);
338 return false;
339 }
340 double lastHighR = bestR;
341 r = bestR / 2;
342 rStep = r / 2;
343 do { // find lower bounds of single result
344 TRange tRange;
345 bool success = orderTRange(reporter, quad1, quad2, r, &tRange);
346 if (success) {
347 if (gPathOpsAngleIdeasVerbose) {
348 SkDebugf("l bestCCW=%d ccw=%d bestMin=%1.9g:%1.9g r=%1.9g tMin=%1.9g\n",
349 bestCCW, tRange.ccw, lowerRange->tMin, upperRange->tMin, r,
350 tRange.tMin);
351 }
352 if (bestCCW != (int) tRange.ccw || upperRange->tMin < tRange.tMin) {
353 bestCCW = tRange.ccw;
354 *upperRange = tRange;
355 bestR = lastHighR;
356 break; // need to establish a new upper bounds
357 }
358 SkDPoint pt1 = quad1.ptAtT(tRange.t1);
359 SkDPoint pt2 = quad2.ptAtT(tRange.t2);
360 if (equalPoints(pt1, best1, maxQuads)) {
361 goto breakOut;
362 }
363 best1 = pt1;
364 if (equalPoints(pt2, best2, maxQuads)) {
365 goto breakOut;
366 }
367 best2 = pt2;
368 if (equalPoints(pt1, pt2, maxQuads)) {
369 success = false;
370 } else {
371 if (upperRange->tMin < tRange.tMin) {
372 *upperRange = tRange;
373 }
374 if (lowerRange->tMin > tRange.tMin) {
375 *lowerRange = tRange;
376 }
377 }
378 lastHighR = std::min(r, lastHighR);
379 }
380 r += success ? -rStep : rStep;
381 rStep /= 2;
382 } while (rStep > FLT_EPSILON);
383 } while (rStep > FLT_EPSILON);
384 breakOut:
385 if (gPathOpsAngleIdeasVerbose) {
386 SkDebugf("l a2-a1==%1.9g\n", lowerRange->a2 - lowerRange->a1);
387 }
388 return true;
389 }
390
bruteForce(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,bool ccw)391 static void bruteForce(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2,
392 bool ccw) {
393 if (!gPathOpsAngleIdeasEnableBruteCheck) {
394 return;
395 }
396 TRange lowerRange, upperRange;
397 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange);
398 REPORTER_ASSERT(reporter, result);
399 double angle = fabs(lowerRange.a2 - lowerRange.a1);
400 REPORTER_ASSERT(reporter, angle > 3.998 || ccw == upperRange.ccw);
401 }
402
bruteForceCheck(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,bool ccw)403 static bool bruteForceCheck(skiatest::Reporter* reporter, const SkDQuad& quad1,
404 const SkDQuad& quad2, bool ccw) {
405 TRange lowerRange, upperRange;
406 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange);
407 REPORTER_ASSERT(reporter, result);
408 return ccw == upperRange.ccw;
409 }
410
makeSegment(SkOpContour * contour,const SkDQuad & quad,SkPoint shortQuad[3])411 static void makeSegment(SkOpContour* contour, const SkDQuad& quad, SkPoint shortQuad[3]) {
412 shortQuad[0] = quad[0].asSkPoint();
413 shortQuad[1] = quad[1].asSkPoint();
414 shortQuad[2] = quad[2].asSkPoint();
415 contour->addQuad(shortQuad);
416 }
417
testQuadAngles(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,int testNo,SkArenaAlloc * allocator)418 static void testQuadAngles(skiatest::Reporter* reporter, const SkDQuad& quad1, const SkDQuad& quad2,
419 int testNo, SkArenaAlloc* allocator) {
420 SkPoint shortQuads[2][3];
421
422 SkOpContourHead contour;
423 SkOpGlobalState state(&contour, allocator SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr));
424 contour.init(&state, false, false);
425 makeSegment(&contour, quad1, shortQuads[0]);
426 makeSegment(&contour, quad1, shortQuads[1]);
427 SkOpSegment* seg1 = contour.first();
428 seg1->debugAddAngle(0, 1);
429 SkOpSegment* seg2 = seg1->next();
430 seg2->debugAddAngle(0, 1);
431 int realOverlap = PathOpsAngleTester::ConvexHullOverlaps(*seg1->debugLastAngle(),
432 *seg2->debugLastAngle());
433 const SkDPoint& origin = quad1[0];
434 REPORTER_ASSERT(reporter, origin == quad2[0]);
435 double a1s = atan2(origin.fY - quad1[1].fY, quad1[1].fX - origin.fX);
436 double a1e = atan2(origin.fY - quad1[2].fY, quad1[2].fX - origin.fX);
437 double a2s = atan2(origin.fY - quad2[1].fY, quad2[1].fX - origin.fX);
438 double a2e = atan2(origin.fY - quad2[2].fY, quad2[2].fX - origin.fX);
439 bool oldSchoolOverlap = radianBetween(a1s, a2s, a1e)
440 || radianBetween(a1s, a2e, a1e) || radianBetween(a2s, a1s, a2e)
441 || radianBetween(a2s, a1e, a2e);
442 int overlap = quadHullsOverlap(reporter, quad1, quad2);
443 bool realMatchesOverlap = realOverlap == overlap || SK_ScalarPI - fabs(a2s - a1s) < 0.002;
444 if (realOverlap != overlap) {
445 SkDebugf("\nSK_ScalarPI - fabs(a2s - a1s) = %1.9g\n", SK_ScalarPI - fabs(a2s - a1s));
446 }
447 if (!realMatchesOverlap) {
448 DumpQ(quad1, quad2, testNo);
449 }
450 REPORTER_ASSERT(reporter, realMatchesOverlap);
451 if (oldSchoolOverlap != (overlap < 0)) {
452 overlap = quadHullsOverlap(reporter, quad1, quad2); // set a breakpoint and debug if assert fires
453 REPORTER_ASSERT(reporter, oldSchoolOverlap == (overlap < 0));
454 }
455 SkDVector v1s = quad1[1] - quad1[0];
456 SkDVector v1e = quad1[2] - quad1[0];
457 SkDVector v2s = quad2[1] - quad2[0];
458 SkDVector v2e = quad2[2] - quad2[0];
459 double vDir[2] = { v1s.cross(v1e), v2s.cross(v2e) };
460 bool ray1In2 = v1s.cross(v2s) * vDir[1] <= 0 && v1s.cross(v2e) * vDir[1] >= 0;
461 bool ray2In1 = v2s.cross(v1s) * vDir[0] <= 0 && v2s.cross(v1e) * vDir[0] >= 0;
462 if (overlap >= 0) {
463 // verify that hulls really don't overlap
464 REPORTER_ASSERT(reporter, !ray1In2);
465 REPORTER_ASSERT(reporter, !ray2In1);
466 bool ctrl1In2 = v1e.cross(v2s) * vDir[1] <= 0 && v1e.cross(v2e) * vDir[1] >= 0;
467 REPORTER_ASSERT(reporter, !ctrl1In2);
468 bool ctrl2In1 = v2e.cross(v1s) * vDir[0] <= 0 && v2e.cross(v1e) * vDir[0] >= 0;
469 REPORTER_ASSERT(reporter, !ctrl2In1);
470 // check answer against reference
471 bruteForce(reporter, quad1, quad2, overlap > 0);
472 }
473 // continue end point rays and see if they intersect the opposite curve
474 SkDLine rays[] = {{{origin, quad2[2]}}, {{origin, quad1[2]}}};
475 const SkDQuad* quads[] = {&quad1, &quad2};
476 SkDVector midSpokes[2];
477 SkIntersections intersect[2];
478 double minX, minY, maxX, maxY;
479 minX = minY = SK_ScalarInfinity;
480 maxX = maxY = -SK_ScalarInfinity;
481 double maxWidth = 0;
482 bool useIntersect = false;
483 double smallestTs[] = {1, 1};
484 for (unsigned index = 0; index < SK_ARRAY_COUNT(quads); ++index) {
485 const SkDQuad& q = *quads[index];
486 midSpokes[index] = q.ptAtT(0.5) - origin;
487 minX = std::min(std::min(std::min(minX, origin.fX), q[1].fX), q[2].fX);
488 minY = std::min(std::min(std::min(minY, origin.fY), q[1].fY), q[2].fY);
489 maxX = std::max(std::max(std::max(maxX, origin.fX), q[1].fX), q[2].fX);
490 maxY = std::max(std::max(std::max(maxY, origin.fY), q[1].fY), q[2].fY);
491 maxWidth = std::max(maxWidth, std::max(maxX - minX, maxY - minY));
492 intersect[index].intersectRay(q, rays[index]);
493 const SkIntersections& i = intersect[index];
494 REPORTER_ASSERT(reporter, i.used() >= 1);
495 bool foundZero = false;
496 double smallT = 1;
497 for (int idx2 = 0; idx2 < i.used(); ++idx2) {
498 double t = i[0][idx2];
499 if (t == 0) {
500 foundZero = true;
501 continue;
502 }
503 if (smallT > t) {
504 smallT = t;
505 }
506 }
507 REPORTER_ASSERT(reporter, foundZero == true);
508 if (smallT == 1) {
509 continue;
510 }
511 SkDVector ray = q.ptAtT(smallT) - origin;
512 SkDVector end = rays[index][1] - origin;
513 if (ray.fX * end.fX < 0 || ray.fY * end.fY < 0) {
514 continue;
515 }
516 double rayDist = ray.length();
517 double endDist = end.length();
518 double delta = fabs(rayDist - endDist) / maxWidth;
519 if (delta > 1e-4) {
520 useIntersect ^= true;
521 }
522 smallestTs[index] = smallT;
523 }
524 bool firstInside;
525 if (useIntersect) {
526 int sIndex = (int) (smallestTs[1] < 1);
527 REPORTER_ASSERT(reporter, smallestTs[sIndex ^ 1] == 1);
528 double t = smallestTs[sIndex];
529 const SkDQuad& q = *quads[sIndex];
530 SkDVector ray = q.ptAtT(t) - origin;
531 SkDVector end = rays[sIndex][1] - origin;
532 double rayDist = ray.length();
533 double endDist = end.length();
534 SkDVector mid = q.ptAtT(t / 2) - origin;
535 double midXray = mid.crossCheck(ray);
536 if (gPathOpsAngleIdeasVerbose) {
537 SkDebugf("rayDist>endDist:%d sIndex==0:%d vDir[sIndex]<0:%d midXray<0:%d\n",
538 rayDist > endDist, sIndex == 0, vDir[sIndex] < 0, midXray < 0);
539 }
540 SkASSERT(SkScalarSignAsInt(SkDoubleToScalar(midXray))
541 == SkScalarSignAsInt(SkDoubleToScalar(vDir[sIndex])));
542 firstInside = (rayDist > endDist) ^ (sIndex == 0) ^ (vDir[sIndex] < 0);
543 } else if (overlap >= 0) {
544 return; // answer has already been determined
545 } else {
546 firstInside = checkParallel(reporter, quad1, quad2);
547 }
548 if (overlap < 0) {
549 SkDEBUGCODE(int realEnds =)
550 PathOpsAngleTester::EndsIntersect(*seg1->debugLastAngle(),
551 *seg2->debugLastAngle());
552 SkASSERT(realEnds == (firstInside ? 1 : 0));
553 }
554 bruteForce(reporter, quad1, quad2, firstInside);
555 }
556
DEF_TEST(PathOpsAngleOverlapHullsOne,reporter)557 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) {
558 SkSTArenaAlloc<4096> allocator;
559 // gPathOpsAngleIdeasVerbose = true;
560 const QuadPts quads[] = {
561 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875}, {736.8936767578125, -350.717529296875}}},
562 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125}, {-509.62615966796875, 576.1182861328125}}}
563 };
564 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) {
565 SkDQuad quad0, quad1;
566 quad0.debugSet(quads[index].fPts);
567 quad1.debugSet(quads[index + 1].fPts);
568 testQuadAngles(reporter, quad0, quad1, 0, &allocator);
569 }
570 }
571
DEF_TEST(PathOpsAngleOverlapHulls,reporter)572 DEF_TEST(PathOpsAngleOverlapHulls, reporter) {
573 SkSTArenaAlloc<4096> allocator;
574 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
575 return;
576 }
577 SkRandom ran;
578 for (int index = 0; index < 100000; ++index) {
579 if (index % 1000 == 999) SkDebugf(".");
580 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)};
581 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
582 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
583 if (quad1.fPts[0] == quad1.fPts[2]) {
584 continue;
585 }
586 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
587 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
588 if (quad2.fPts[0] == quad2.fPts[2]) {
589 continue;
590 }
591 SkIntersections i;
592 SkDQuad q1, q2;
593 q1.debugSet(quad1.fPts);
594 q2.debugSet(quad2.fPts);
595 i.intersect(q1, q2);
596 REPORTER_ASSERT(reporter, i.used() >= 1);
597 if (i.used() > 1) {
598 continue;
599 }
600 testQuadAngles(reporter, q1, q2, index, &allocator);
601 }
602 }
603
DEF_TEST(PathOpsAngleBruteT,reporter)604 DEF_TEST(PathOpsAngleBruteT, reporter) {
605 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
606 return;
607 }
608 SkRandom ran;
609 double smaller = SK_Scalar1;
610 SkDQuad small[2];
611 SkDEBUGCODE(int smallIndex = 0);
612 for (int index = 0; index < 100000; ++index) {
613 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)};
614 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
615 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
616 if (quad1.fPts[0] == quad1.fPts[2]) {
617 continue;
618 }
619 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
620 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
621 if (quad2.fPts[0] == quad2.fPts[2]) {
622 continue;
623 }
624 SkDQuad q1, q2;
625 q1.debugSet(quad1.fPts);
626 q2.debugSet(quad2.fPts);
627 SkIntersections i;
628 i.intersect(q1, q2);
629 REPORTER_ASSERT(reporter, i.used() >= 1);
630 if (i.used() > 1) {
631 continue;
632 }
633 TRange lowerRange, upperRange;
634 bool result = bruteMinT(reporter, q1, q2, &lowerRange, &upperRange);
635 REPORTER_ASSERT(reporter, result);
636 double min = std::min(upperRange.t1, upperRange.t2);
637 if (smaller > min) {
638 small[0] = q1;
639 small[1] = q2;
640 SkDEBUGCODE(smallIndex = index);
641 smaller = min;
642 }
643 }
644 #ifdef SK_DEBUG
645 DumpQ(small[0], small[1], smallIndex);
646 #endif
647 }
648
DEF_TEST(PathOpsAngleBruteTOne,reporter)649 DEF_TEST(PathOpsAngleBruteTOne, reporter) {
650 // gPathOpsAngleIdeasVerbose = true;
651 const QuadPts qPts[] = {
652 {{{-770.8492431640625, 948.2369384765625}, {-853.37066650390625, 972.0301513671875}, {-200.62042236328125, -26.7174072265625}}},
653 {{{-770.8492431640625, 948.2369384765625}, {513.602783203125, 578.8681640625}, {960.641357421875, -813.69757080078125}}},
654 {{{563.8267822265625, -107.4566650390625}, {-44.67724609375, -136.57452392578125}, {492.3856201171875, -268.79644775390625}}},
655 {{{563.8267822265625, -107.4566650390625}, {708.049072265625, -100.77789306640625}, {-48.88226318359375, 967.9022216796875}}},
656 {{{598.857421875, 846.345458984375}, {-644.095703125, -316.12921142578125}, {-97.64599609375, 20.6158447265625}}},
657 {{{598.857421875, 846.345458984375}, {715.7142333984375, 955.3599853515625}, {-919.9478759765625, 691.611328125}}},
658 };
659 TRange lowerRange, upperRange;
660 SkDQuad quads[SK_ARRAY_COUNT(qPts)];
661 for (int index = 0; index < (int) SK_ARRAY_COUNT(qPts); ++index) {
662 quads[index].debugSet(qPts[index].fPts);
663 }
664 bruteMinT(reporter, quads[0], quads[1], &lowerRange, &upperRange);
665 bruteMinT(reporter, quads[2], quads[3], &lowerRange, &upperRange);
666 bruteMinT(reporter, quads[4], quads[5], &lowerRange, &upperRange);
667 }
668
669 /*
670 The sorting problem happens when the inital tangents are not a true indicator of the curve direction
671 Nearly always, the initial tangents do give the right answer,
672 so the trick is to figure out when the initial tangent cannot be trusted.
673 If the convex hulls of both curves are in the same half plane, and not overlapping, sorting the
674 hulls is enough.
675 If the hulls overlap, and have the same general direction, then intersect the shorter end point ray
676 with the opposing curve, and see on which side of the shorter curve the opposing intersection lies.
677 Otherwise, if the control vector is extremely short, likely the point on curve must be computed
678 If moving the control point slightly can change the sign of the cross product, either answer could
679 be "right".
680 We need to determine how short is extremely short. Move the control point a set percentage of
681 the largest length to determine how stable the curve is vis-a-vis the initial tangent.
682 */
683
684 static const QuadPts extremeTests[][2] = {
685 {
686 {{{-708.0077926931004,-154.61669472244046},
687 {-707.9234268635319,-154.30459999551294},
688 {505.58447265625,-504.9130859375}}},
689 {{{-708.0077926931004,-154.61669472244046},
690 {-711.127526325141,-163.9446090624656},
691 {-32.39227294921875,-906.3277587890625}}},
692 }, {
693 {{{-708.0077926931004,-154.61669472244046},
694 {-708.2875337527566,-154.36676458635623},
695 {505.58447265625,-504.9130859375}}},
696 {{{-708.0077926931004,-154.61669472244046},
697 {-708.4111557216864,-154.5366642875255},
698 {-32.39227294921875,-906.3277587890625}}},
699 }, {
700 {{{-609.0230951752058,-267.5435593490574},
701 {-594.1120809906336,-136.08492475411555},
702 {505.58447265625,-504.9130859375}}},
703 {{{-609.0230951752058,-267.5435593490574},
704 {-693.7467719138988,-341.3259237831895},
705 {-32.39227294921875,-906.3277587890625}}}
706 }, {
707 {{{-708.0077926931004,-154.61669472244046},
708 {-707.9994640658723,-154.58588461064852},
709 {505.58447265625,-504.9130859375}}},
710 {{{-708.0077926931004,-154.61669472244046},
711 {-708.0239418990758,-154.6403553507124},
712 {-32.39227294921875,-906.3277587890625}}}
713 }, {
714 {{{-708.0077926931004,-154.61669472244046},
715 {-707.9993222215099,-154.55999389855003},
716 {68.88981098017803,296.9273945411635}}},
717 {{{-708.0077926931004,-154.61669472244046},
718 {-708.0509091919608,-154.64675214697067},
719 {-777.4871194247767,-995.1470120113145}}}
720 }, {
721 {{{-708.0077926931004,-154.61669472244046},
722 {-708.0060491116379,-154.60889321524968},
723 {229.97088707895057,-430.0569357467175}}},
724 {{{-708.0077926931004,-154.61669472244046},
725 {-708.013911296257,-154.6219143988058},
726 {138.13162892614037,-573.3689311737394}}}
727 }, {
728 {{{-543.2570545751013,-237.29243831075053},
729 {-452.4119186056987,-143.47223056267802},
730 {229.97088707895057,-430.0569357467175}}},
731 {{{-543.2570545751013,-237.29243831075053},
732 {-660.5330371214436,-362.0016148388},
733 {138.13162892614037,-573.3689311737394}}},
734 },
735 };
736
endCtrlRatio(const SkDQuad quad)737 static double endCtrlRatio(const SkDQuad quad) {
738 SkDVector longEdge = quad[2] - quad[0];
739 double longLen = longEdge.length();
740 SkDVector shortEdge = quad[1] - quad[0];
741 double shortLen = shortEdge.length();
742 return longLen / shortLen;
743 }
744
computeMV(const SkDQuad & quad,const SkDVector & v,double m,SkDVector mV[2])745 static void computeMV(const SkDQuad& quad, const SkDVector& v, double m, SkDVector mV[2]) {
746 SkDPoint mPta = {quad[1].fX - m * v.fY, quad[1].fY + m * v.fX};
747 SkDPoint mPtb = {quad[1].fX + m * v.fY, quad[1].fY - m * v.fX};
748 mV[0] = mPta - quad[0];
749 mV[1] = mPtb - quad[0];
750 }
751
mDistance(skiatest::Reporter * reporter,bool agrees,const SkDQuad & q1,const SkDQuad & q2)752 static double mDistance(skiatest::Reporter* reporter, bool agrees, const SkDQuad& q1,
753 const SkDQuad& q2) {
754 if (1 && agrees) {
755 return SK_ScalarMax;
756 }
757 // how close is the angle from inflecting in the opposite direction?
758 SkDVector v1 = q1[1] - q1[0];
759 SkDVector v2 = q2[1] - q2[0];
760 double dir = v1.crossCheck(v2);
761 REPORTER_ASSERT(reporter, dir != 0);
762 // solve for opposite direction displacement scale factor == m
763 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
764 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
765 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
766 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
767 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
768 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
769 // m = v1.cross(v2) / v1.dot(v2)
770 double div = v1.dot(v2);
771 REPORTER_ASSERT(reporter, div != 0);
772 double m = dir / div;
773 SkDVector mV1[2], mV2[2];
774 computeMV(q1, v1, m, mV1);
775 computeMV(q2, v2, m, mV2);
776 double dist1 = v1.length() * m;
777 double dist2 = v2.length() * m;
778 if (gPathOpsAngleIdeasVerbose) {
779 SkDebugf("%c r1=%1.9g r2=%1.9g m=%1.9g dist1=%1.9g dist2=%1.9g "
780 " dir%c 1a=%1.9g 1b=%1.9g 2a=%1.9g 2b=%1.9g\n", agrees ? 'T' : 'F',
781 endCtrlRatio(q1), endCtrlRatio(q2), m, dist1, dist2, dir > 0 ? '+' : '-',
782 mV1[0].crossCheck(v2), mV1[1].crossCheck(v2),
783 mV2[0].crossCheck(v1), mV2[1].crossCheck(v1));
784 }
785 if (1) {
786 bool use1 = fabs(dist1) < fabs(dist2);
787 if (gPathOpsAngleIdeasVerbose) {
788 SkDebugf("%c dist=%1.9g r=%1.9g\n", agrees ? 'T' : 'F', use1 ? dist1 : dist2,
789 use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2));
790 }
791 return fabs(use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2));
792 }
793 return SK_ScalarMax;
794 }
795
midPointAgrees(skiatest::Reporter * reporter,const SkDQuad & q1,const SkDQuad & q2,bool ccw)796 static void midPointAgrees(skiatest::Reporter* reporter, const SkDQuad& q1, const SkDQuad& q2,
797 bool ccw) {
798 SkDPoint mid1 = q1.ptAtT(0.5);
799 SkDVector m1 = mid1 - q1[0];
800 SkDPoint mid2 = q2.ptAtT(0.5);
801 SkDVector m2 = mid2 - q2[0];
802 REPORTER_ASSERT(reporter, ccw ? m1.crossCheck(m2) < 0 : m1.crossCheck(m2) > 0);
803 }
804
DEF_TEST(PathOpsAngleExtreme,reporter)805 DEF_TEST(PathOpsAngleExtreme, reporter) {
806 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
807 return;
808 }
809 double maxR = SK_ScalarMax;
810 for (int index = 0; index < (int) SK_ARRAY_COUNT(extremeTests); ++index) {
811 const QuadPts& qu1 = extremeTests[index][0];
812 const QuadPts& qu2 = extremeTests[index][1];
813 SkDQuad quad1, quad2;
814 quad1.debugSet(qu1.fPts);
815 quad2.debugSet(qu2.fPts);
816 if (gPathOpsAngleIdeasVerbose) {
817 SkDebugf("%s %d\n", __FUNCTION__, index);
818 }
819 REPORTER_ASSERT(reporter, quad1[0] == quad2[0]);
820 SkIntersections i;
821 i.intersect(quad1, quad2);
822 REPORTER_ASSERT(reporter, i.used() == 1);
823 REPORTER_ASSERT(reporter, i.pt(0) == quad1[0]);
824 int overlap = quadHullsOverlap(reporter, quad1, quad2);
825 REPORTER_ASSERT(reporter, overlap >= 0);
826 SkDVector sweep[2], tweep[2];
827 setQuadHullSweep(quad1, sweep);
828 setQuadHullSweep(quad2, tweep);
829 double s0xt0 = sweep[0].crossCheck(tweep[0]);
830 REPORTER_ASSERT(reporter, s0xt0 != 0);
831 bool ccw = s0xt0 < 0;
832 bool agrees = bruteForceCheck(reporter, quad1, quad2, ccw);
833 maxR = std::min(maxR, mDistance(reporter, agrees, quad1, quad2));
834 if (agrees) {
835 continue;
836 }
837 midPointAgrees(reporter, quad1, quad2, !ccw);
838 SkDQuad q1 = quad1;
839 SkDQuad q2 = quad2;
840 double loFail = 1;
841 double hiPass = 2;
842 // double vectors until t passes
843 do {
844 q1[1].fX = quad1[0].fX * (1 - hiPass) + quad1[1].fX * hiPass;
845 q1[1].fY = quad1[0].fY * (1 - hiPass) + quad1[1].fY * hiPass;
846 q2[1].fX = quad2[0].fX * (1 - hiPass) + quad2[1].fX * hiPass;
847 q2[1].fY = quad2[0].fY * (1 - hiPass) + quad2[1].fY * hiPass;
848 agrees = bruteForceCheck(reporter, q1, q2, ccw);
849 maxR = std::min(maxR, mDistance(reporter, agrees, q1, q2));
850 if (agrees) {
851 break;
852 }
853 midPointAgrees(reporter, quad1, quad2, !ccw);
854 loFail = hiPass;
855 hiPass *= 2;
856 } while (true);
857 // binary search to find minimum pass
858 double midTest = (loFail + hiPass) / 2;
859 double step = (hiPass - loFail) / 4;
860 while (step > FLT_EPSILON) {
861 q1[1].fX = quad1[0].fX * (1 - midTest) + quad1[1].fX * midTest;
862 q1[1].fY = quad1[0].fY * (1 - midTest) + quad1[1].fY * midTest;
863 q2[1].fX = quad2[0].fX * (1 - midTest) + quad2[1].fX * midTest;
864 q2[1].fY = quad2[0].fY * (1 - midTest) + quad2[1].fY * midTest;
865 agrees = bruteForceCheck(reporter, q1, q2, ccw);
866 maxR = std::min(maxR, mDistance(reporter, agrees, q1, q2));
867 if (!agrees) {
868 midPointAgrees(reporter, quad1, quad2, !ccw);
869 }
870 midTest += agrees ? -step : step;
871 step /= 2;
872 }
873 #ifdef SK_DEBUG
874 // DumpQ(q1, q2, 999);
875 #endif
876 }
877 if (gPathOpsAngleIdeasVerbose) {
878 SkDebugf("maxR=%1.9g\n", maxR);
879 }
880 }
881