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:
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 = SkTMax(v[0].length(), SkTMax(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() - 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
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 = SkTMax(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 = SkTMax(max, fabs(quad[index].fX));
280 max = SkTMax(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 = 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
bruteForce(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,bool ccw)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
bruteForceCheck(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,bool ccw)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
makeSegment(SkOpContour * contour,const SkDQuad & quad,SkPoint shortQuad[3])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
testQuadAngles(skiatest::Reporter * reporter,const SkDQuad & quad1,const SkDQuad & quad2,int testNo,SkArenaAlloc * allocator)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
DEF_TEST(PathOpsAngleOverlapHullsOne,reporter)560 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) {
561 char storage[4096];
562 SkArenaAlloc allocator(storage);
563 // gPathOpsAngleIdeasVerbose = true;
564 const QuadPts quads[] = {
565 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875}, {736.8936767578125, -350.717529296875}}},
566 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125}, {-509.62615966796875, 576.1182861328125}}}
567 };
568 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) {
569 SkDQuad quad0, quad1;
570 quad0.debugSet(quads[index].fPts);
571 quad1.debugSet(quads[index + 1].fPts);
572 testQuadAngles(reporter, quad0, quad1, 0, &allocator);
573 }
574 }
575
DEF_TEST(PathOpsAngleOverlapHulls,reporter)576 DEF_TEST(PathOpsAngleOverlapHulls, reporter) {
577 char storage[4096];
578 SkArenaAlloc allocator(storage);
579 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
580 return;
581 }
582 SkRandom ran;
583 for (int index = 0; index < 100000; ++index) {
584 if (index % 1000 == 999) SkDebugf(".");
585 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)};
586 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
587 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
588 if (quad1.fPts[0] == quad1.fPts[2]) {
589 continue;
590 }
591 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
592 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
593 if (quad2.fPts[0] == quad2.fPts[2]) {
594 continue;
595 }
596 SkIntersections i;
597 SkDQuad q1, q2;
598 q1.debugSet(quad1.fPts);
599 q2.debugSet(quad2.fPts);
600 i.intersect(q1, q2);
601 REPORTER_ASSERT(reporter, i.used() >= 1);
602 if (i.used() > 1) {
603 continue;
604 }
605 testQuadAngles(reporter, q1, q2, index, &allocator);
606 }
607 }
608
DEF_TEST(PathOpsAngleBruteT,reporter)609 DEF_TEST(PathOpsAngleBruteT, reporter) {
610 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
611 return;
612 }
613 SkRandom ran;
614 double smaller = SK_Scalar1;
615 SkDQuad small[2];
616 SkDEBUGCODE(int smallIndex);
617 for (int index = 0; index < 100000; ++index) {
618 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)};
619 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
620 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
621 if (quad1.fPts[0] == quad1.fPts[2]) {
622 continue;
623 }
624 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
625 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
626 if (quad2.fPts[0] == quad2.fPts[2]) {
627 continue;
628 }
629 SkDQuad q1, q2;
630 q1.debugSet(quad1.fPts);
631 q2.debugSet(quad2.fPts);
632 SkIntersections i;
633 i.intersect(q1, q2);
634 REPORTER_ASSERT(reporter, i.used() >= 1);
635 if (i.used() > 1) {
636 continue;
637 }
638 TRange lowerRange, upperRange;
639 bool result = bruteMinT(reporter, q1, q2, &lowerRange, &upperRange);
640 REPORTER_ASSERT(reporter, result);
641 double min = SkTMin(upperRange.t1, upperRange.t2);
642 if (smaller > min) {
643 small[0] = q1;
644 small[1] = q2;
645 SkDEBUGCODE(smallIndex = index);
646 smaller = min;
647 }
648 }
649 #ifdef SK_DEBUG
650 DumpQ(small[0], small[1], smallIndex);
651 #endif
652 }
653
DEF_TEST(PathOpsAngleBruteTOne,reporter)654 DEF_TEST(PathOpsAngleBruteTOne, reporter) {
655 // gPathOpsAngleIdeasVerbose = true;
656 const QuadPts qPts[] = {
657 {{{-770.8492431640625, 948.2369384765625}, {-853.37066650390625, 972.0301513671875}, {-200.62042236328125, -26.7174072265625}}},
658 {{{-770.8492431640625, 948.2369384765625}, {513.602783203125, 578.8681640625}, {960.641357421875, -813.69757080078125}}},
659 {{{563.8267822265625, -107.4566650390625}, {-44.67724609375, -136.57452392578125}, {492.3856201171875, -268.79644775390625}}},
660 {{{563.8267822265625, -107.4566650390625}, {708.049072265625, -100.77789306640625}, {-48.88226318359375, 967.9022216796875}}},
661 {{{598.857421875, 846.345458984375}, {-644.095703125, -316.12921142578125}, {-97.64599609375, 20.6158447265625}}},
662 {{{598.857421875, 846.345458984375}, {715.7142333984375, 955.3599853515625}, {-919.9478759765625, 691.611328125}}},
663 };
664 TRange lowerRange, upperRange;
665 SkDQuad quads[SK_ARRAY_COUNT(qPts)];
666 for (int index = 0; index < (int) SK_ARRAY_COUNT(qPts); ++index) {
667 quads[index].debugSet(qPts[index].fPts);
668 }
669 bruteMinT(reporter, quads[0], quads[1], &lowerRange, &upperRange);
670 bruteMinT(reporter, quads[2], quads[3], &lowerRange, &upperRange);
671 bruteMinT(reporter, quads[4], quads[5], &lowerRange, &upperRange);
672 }
673
674 /*
675 The sorting problem happens when the inital tangents are not a true indicator of the curve direction
676 Nearly always, the initial tangents do give the right answer,
677 so the trick is to figure out when the initial tangent cannot be trusted.
678 If the convex hulls of both curves are in the same half plane, and not overlapping, sorting the
679 hulls is enough.
680 If the hulls overlap, and have the same general direction, then intersect the shorter end point ray
681 with the opposing curve, and see on which side of the shorter curve the opposing intersection lies.
682 Otherwise, if the control vector is extremely short, likely the point on curve must be computed
683 If moving the control point slightly can change the sign of the cross product, either answer could
684 be "right".
685 We need to determine how short is extremely short. Move the control point a set percentage of
686 the largest length to determine how stable the curve is vis-a-vis the initial tangent.
687 */
688
689 static const QuadPts extremeTests[][2] = {
690 {
691 {{{-708.0077926931004,-154.61669472244046},
692 {-707.9234268635319,-154.30459999551294},
693 {505.58447265625,-504.9130859375}}},
694 {{{-708.0077926931004,-154.61669472244046},
695 {-711.127526325141,-163.9446090624656},
696 {-32.39227294921875,-906.3277587890625}}},
697 }, {
698 {{{-708.0077926931004,-154.61669472244046},
699 {-708.2875337527566,-154.36676458635623},
700 {505.58447265625,-504.9130859375}}},
701 {{{-708.0077926931004,-154.61669472244046},
702 {-708.4111557216864,-154.5366642875255},
703 {-32.39227294921875,-906.3277587890625}}},
704 }, {
705 {{{-609.0230951752058,-267.5435593490574},
706 {-594.1120809906336,-136.08492475411555},
707 {505.58447265625,-504.9130859375}}},
708 {{{-609.0230951752058,-267.5435593490574},
709 {-693.7467719138988,-341.3259237831895},
710 {-32.39227294921875,-906.3277587890625}}}
711 }, {
712 {{{-708.0077926931004,-154.61669472244046},
713 {-707.9994640658723,-154.58588461064852},
714 {505.58447265625,-504.9130859375}}},
715 {{{-708.0077926931004,-154.61669472244046},
716 {-708.0239418990758,-154.6403553507124},
717 {-32.39227294921875,-906.3277587890625}}}
718 }, {
719 {{{-708.0077926931004,-154.61669472244046},
720 {-707.9993222215099,-154.55999389855003},
721 {68.88981098017803,296.9273945411635}}},
722 {{{-708.0077926931004,-154.61669472244046},
723 {-708.0509091919608,-154.64675214697067},
724 {-777.4871194247767,-995.1470120113145}}}
725 }, {
726 {{{-708.0077926931004,-154.61669472244046},
727 {-708.0060491116379,-154.60889321524968},
728 {229.97088707895057,-430.0569357467175}}},
729 {{{-708.0077926931004,-154.61669472244046},
730 {-708.013911296257,-154.6219143988058},
731 {138.13162892614037,-573.3689311737394}}}
732 }, {
733 {{{-543.2570545751013,-237.29243831075053},
734 {-452.4119186056987,-143.47223056267802},
735 {229.97088707895057,-430.0569357467175}}},
736 {{{-543.2570545751013,-237.29243831075053},
737 {-660.5330371214436,-362.0016148388},
738 {138.13162892614037,-573.3689311737394}}},
739 },
740 };
741
endCtrlRatio(const SkDQuad quad)742 static double endCtrlRatio(const SkDQuad quad) {
743 SkDVector longEdge = quad[2] - quad[0];
744 double longLen = longEdge.length();
745 SkDVector shortEdge = quad[1] - quad[0];
746 double shortLen = shortEdge.length();
747 return longLen / shortLen;
748 }
749
computeMV(const SkDQuad & quad,const SkDVector & v,double m,SkDVector mV[2])750 static void computeMV(const SkDQuad& quad, const SkDVector& v, double m, SkDVector mV[2]) {
751 SkDPoint mPta = {quad[1].fX - m * v.fY, quad[1].fY + m * v.fX};
752 SkDPoint mPtb = {quad[1].fX + m * v.fY, quad[1].fY - m * v.fX};
753 mV[0] = mPta - quad[0];
754 mV[1] = mPtb - quad[0];
755 }
756
mDistance(skiatest::Reporter * reporter,bool agrees,const SkDQuad & q1,const SkDQuad & q2)757 static double mDistance(skiatest::Reporter* reporter, bool agrees, const SkDQuad& q1,
758 const SkDQuad& q2) {
759 if (1 && agrees) {
760 return SK_ScalarMax;
761 }
762 // how close is the angle from inflecting in the opposite direction?
763 SkDVector v1 = q1[1] - q1[0];
764 SkDVector v2 = q2[1] - q2[0];
765 double dir = v1.crossCheck(v2);
766 REPORTER_ASSERT(reporter, dir != 0);
767 // solve for opposite direction displacement scale factor == m
768 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
769 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
770 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
771 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
772 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
773 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
774 // m = v1.cross(v2) / v1.dot(v2)
775 double div = v1.dot(v2);
776 REPORTER_ASSERT(reporter, div != 0);
777 double m = dir / div;
778 SkDVector mV1[2], mV2[2];
779 computeMV(q1, v1, m, mV1);
780 computeMV(q2, v2, m, mV2);
781 double dist1 = v1.length() * m;
782 double dist2 = v2.length() * m;
783 if (gPathOpsAngleIdeasVerbose) {
784 SkDebugf("%c r1=%1.9g r2=%1.9g m=%1.9g dist1=%1.9g dist2=%1.9g "
785 " dir%c 1a=%1.9g 1b=%1.9g 2a=%1.9g 2b=%1.9g\n", agrees ? 'T' : 'F',
786 endCtrlRatio(q1), endCtrlRatio(q2), m, dist1, dist2, dir > 0 ? '+' : '-',
787 mV1[0].crossCheck(v2), mV1[1].crossCheck(v2),
788 mV2[0].crossCheck(v1), mV2[1].crossCheck(v1));
789 }
790 if (1) {
791 bool use1 = fabs(dist1) < fabs(dist2);
792 if (gPathOpsAngleIdeasVerbose) {
793 SkDebugf("%c dist=%1.9g r=%1.9g\n", agrees ? 'T' : 'F', use1 ? dist1 : dist2,
794 use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2));
795 }
796 return fabs(use1 ? distEndRatio(dist1, q1) : distEndRatio(dist2, q2));
797 }
798 return SK_ScalarMax;
799 }
800
midPointAgrees(skiatest::Reporter * reporter,const SkDQuad & q1,const SkDQuad & q2,bool ccw)801 static void midPointAgrees(skiatest::Reporter* reporter, const SkDQuad& q1, const SkDQuad& q2,
802 bool ccw) {
803 SkDPoint mid1 = q1.ptAtT(0.5);
804 SkDVector m1 = mid1 - q1[0];
805 SkDPoint mid2 = q2.ptAtT(0.5);
806 SkDVector m2 = mid2 - q2[0];
807 REPORTER_ASSERT(reporter, ccw ? m1.crossCheck(m2) < 0 : m1.crossCheck(m2) > 0);
808 }
809
DEF_TEST(PathOpsAngleExtreme,reporter)810 DEF_TEST(PathOpsAngleExtreme, reporter) {
811 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
812 return;
813 }
814 double maxR = SK_ScalarMax;
815 for (int index = 0; index < (int) SK_ARRAY_COUNT(extremeTests); ++index) {
816 const QuadPts& qu1 = extremeTests[index][0];
817 const QuadPts& qu2 = extremeTests[index][1];
818 SkDQuad quad1, quad2;
819 quad1.debugSet(qu1.fPts);
820 quad2.debugSet(qu2.fPts);
821 if (gPathOpsAngleIdeasVerbose) {
822 SkDebugf("%s %d\n", __FUNCTION__, index);
823 }
824 REPORTER_ASSERT(reporter, quad1[0] == quad2[0]);
825 SkIntersections i;
826 i.intersect(quad1, quad2);
827 REPORTER_ASSERT(reporter, i.used() == 1);
828 REPORTER_ASSERT(reporter, i.pt(0) == quad1[0]);
829 int overlap = quadHullsOverlap(reporter, quad1, quad2);
830 REPORTER_ASSERT(reporter, overlap >= 0);
831 SkDVector sweep[2], tweep[2];
832 setQuadHullSweep(quad1, sweep);
833 setQuadHullSweep(quad2, tweep);
834 double s0xt0 = sweep[0].crossCheck(tweep[0]);
835 REPORTER_ASSERT(reporter, s0xt0 != 0);
836 bool ccw = s0xt0 < 0;
837 bool agrees = bruteForceCheck(reporter, quad1, quad2, ccw);
838 maxR = SkTMin(maxR, mDistance(reporter, agrees, quad1, quad2));
839 if (agrees) {
840 continue;
841 }
842 midPointAgrees(reporter, quad1, quad2, !ccw);
843 SkDQuad q1 = quad1;
844 SkDQuad q2 = quad2;
845 double loFail = 1;
846 double hiPass = 2;
847 // double vectors until t passes
848 do {
849 q1[1].fX = quad1[0].fX * (1 - hiPass) + quad1[1].fX * hiPass;
850 q1[1].fY = quad1[0].fY * (1 - hiPass) + quad1[1].fY * hiPass;
851 q2[1].fX = quad2[0].fX * (1 - hiPass) + quad2[1].fX * hiPass;
852 q2[1].fY = quad2[0].fY * (1 - hiPass) + quad2[1].fY * hiPass;
853 agrees = bruteForceCheck(reporter, q1, q2, ccw);
854 maxR = SkTMin(maxR, mDistance(reporter, agrees, q1, q2));
855 if (agrees) {
856 break;
857 }
858 midPointAgrees(reporter, quad1, quad2, !ccw);
859 loFail = hiPass;
860 hiPass *= 2;
861 } while (true);
862 // binary search to find minimum pass
863 double midTest = (loFail + hiPass) / 2;
864 double step = (hiPass - loFail) / 4;
865 while (step > FLT_EPSILON) {
866 q1[1].fX = quad1[0].fX * (1 - midTest) + quad1[1].fX * midTest;
867 q1[1].fY = quad1[0].fY * (1 - midTest) + quad1[1].fY * midTest;
868 q2[1].fX = quad2[0].fX * (1 - midTest) + quad2[1].fX * midTest;
869 q2[1].fY = quad2[0].fY * (1 - midTest) + quad2[1].fY * midTest;
870 agrees = bruteForceCheck(reporter, q1, q2, ccw);
871 maxR = SkTMin(maxR, mDistance(reporter, agrees, q1, q2));
872 if (!agrees) {
873 midPointAgrees(reporter, quad1, quad2, !ccw);
874 }
875 midTest += agrees ? -step : step;
876 step /= 2;
877 }
878 #ifdef SK_DEBUG
879 // DumpQ(q1, q2, 999);
880 #endif
881 }
882 if (gPathOpsAngleIdeasVerbose) {
883 SkDebugf("maxR=%1.9g\n", maxR);
884 }
885 }
886