1 /*
2 * Copyright 2012 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 "SkOpAngle.h"
8 #include "SkOpSegment.h"
9 #include "SkPathOpsCurve.h"
10 #include "SkTSort.h"
11
12 /* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
13 positive y. The largest angle has a positive x and a zero y. */
14
15 #if DEBUG_ANGLE
CompareResult(const char * func,SkString * bugOut,SkString * bugPart,int append,bool compare)16 static bool CompareResult(const char* func, SkString* bugOut, SkString* bugPart, int append,
17 bool compare) {
18 SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
19 SkDebugf("%sPart %s\n", func, bugPart[0].c_str());
20 SkDebugf("%sPart %s\n", func, bugPart[1].c_str());
21 SkDebugf("%sPart %s\n", func, bugPart[2].c_str());
22 return compare;
23 }
24
25 #define COMPARE_RESULT(append, compare) CompareResult(__FUNCTION__, &bugOut, bugPart, append, \
26 compare)
27 #else
28 #define COMPARE_RESULT(append, compare) compare
29 #endif
30
31 /* quarter angle values for sector
32
33 31 x > 0, y == 0 horizontal line (to the right)
34 0 x > 0, y == epsilon quad/cubic horizontal tangent eventually going +y
35 1 x > 0, y > 0, x > y nearer horizontal angle
36 2 x + e == y quad/cubic 45 going horiz
37 3 x > 0, y > 0, x == y 45 angle
38 4 x == y + e quad/cubic 45 going vert
39 5 x > 0, y > 0, x < y nearer vertical angle
40 6 x == epsilon, y > 0 quad/cubic vertical tangent eventually going +x
41 7 x == 0, y > 0 vertical line (to the top)
42
43 8 7 6
44 9 | 5
45 10 | 4
46 11 | 3
47 12 \ | / 2
48 13 | 1
49 14 | 0
50 15 --------------+------------- 31
51 16 | 30
52 17 | 29
53 18 / | \ 28
54 19 | 27
55 20 | 26
56 21 | 25
57 22 23 24
58 */
59
60 // return true if lh < this < rh
after(SkOpAngle * test)61 bool SkOpAngle::after(SkOpAngle* test) {
62 SkOpAngle* lh = test;
63 SkOpAngle* rh = lh->fNext;
64 SkASSERT(lh != rh);
65 #if DEBUG_ANGLE
66 SkString bugOut;
67 bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
68 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
69 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
70 lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
71 lh->fStart->t(), lh->fEnd->t(),
72 segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
73 rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
74 rh->fStart->t(), rh->fEnd->t());
75 SkString bugPart[3] = { lh->debugPart(), this->debugPart(), rh->debugPart() };
76 #endif
77 if (lh->fComputeSector && !lh->computeSector()) {
78 return COMPARE_RESULT(1, true);
79 }
80 if (fComputeSector && !this->computeSector()) {
81 return COMPARE_RESULT(2, true);
82 }
83 if (rh->fComputeSector && !rh->computeSector()) {
84 return COMPARE_RESULT(3, true);
85 }
86 #if DEBUG_ANGLE // reset bugOut with computed sectors
87 bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
88 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g"
89 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__,
90 lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSectorEnd,
91 lh->fStart->t(), lh->fEnd->t(),
92 segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t(), fEnd->t(),
93 rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSectorEnd,
94 rh->fStart->t(), rh->fEnd->t());
95 #endif
96 bool ltrOverlap = (lh->fSectorMask | rh->fSectorMask) & fSectorMask;
97 bool lrOverlap = lh->fSectorMask & rh->fSectorMask;
98 int lrOrder; // set to -1 if either order works
99 if (!lrOverlap) { // no lh/rh sector overlap
100 if (!ltrOverlap) { // no lh/this/rh sector overlap
101 return COMPARE_RESULT(4, (lh->fSectorEnd > rh->fSectorStart)
102 ^ (fSectorStart > lh->fSectorEnd) ^ (fSectorStart > rh->fSectorStart));
103 }
104 int lrGap = (rh->fSectorStart - lh->fSectorStart + 32) & 0x1f;
105 /* A tiny change can move the start +/- 4. The order can only be determined if
106 lr gap is not 12 to 20 or -12 to -20.
107 -31 ..-21 1
108 -20 ..-12 -1
109 -11 .. -1 0
110 0 shouldn't get here
111 11 .. 1 1
112 12 .. 20 -1
113 21 .. 31 0
114 */
115 lrOrder = lrGap > 20 ? 0 : lrGap > 11 ? -1 : 1;
116 } else {
117 lrOrder = (int) lh->orderable(rh);
118 if (!ltrOverlap) {
119 return COMPARE_RESULT(5, !lrOrder);
120 }
121 }
122 int ltOrder;
123 SkASSERT((lh->fSectorMask & fSectorMask) || (rh->fSectorMask & fSectorMask));
124 if (lh->fSectorMask & fSectorMask) {
125 ltOrder = (int) lh->orderable(this);
126 } else {
127 int ltGap = (fSectorStart - lh->fSectorStart + 32) & 0x1f;
128 ltOrder = ltGap > 20 ? 0 : ltGap > 11 ? -1 : 1;
129 }
130 int trOrder;
131 if (rh->fSectorMask & fSectorMask) {
132 trOrder = (int) orderable(rh);
133 } else {
134 int trGap = (rh->fSectorStart - fSectorStart + 32) & 0x1f;
135 trOrder = trGap > 20 ? 0 : trGap > 11 ? -1 : 1;
136 }
137 if (lrOrder >= 0 && ltOrder >= 0 && trOrder >= 0) {
138 return COMPARE_RESULT(7, lrOrder ? (ltOrder & trOrder) : (ltOrder | trOrder));
139 }
140 SkASSERT(lrOrder >= 0 || ltOrder >= 0 || trOrder >= 0);
141 // There's not enough information to sort. Get the pairs of angles in opposite planes.
142 // If an order is < 0, the pair is already in an opposite plane. Check the remaining pairs.
143 // FIXME : once all variants are understood, rewrite this more simply
144 if (ltOrder == 0 && lrOrder == 0) {
145 SkASSERT(trOrder < 0);
146 // FIXME : once this is verified to work, remove one opposite angle call
147 SkDEBUGCODE(bool lrOpposite = lh->oppositePlanes(rh));
148 bool ltOpposite = lh->oppositePlanes(this);
149 SkASSERT(lrOpposite != ltOpposite);
150 return COMPARE_RESULT(8, ltOpposite);
151 } else if (ltOrder == 1 && trOrder == 0) {
152 SkASSERT(lrOrder < 0);
153 SkDEBUGCODE(bool ltOpposite = lh->oppositePlanes(this));
154 bool trOpposite = oppositePlanes(rh);
155 SkASSERT(ltOpposite != trOpposite);
156 return COMPARE_RESULT(9, trOpposite);
157 } else if (lrOrder == 1 && trOrder == 1) {
158 SkASSERT(ltOrder < 0);
159 SkDEBUGCODE(bool trOpposite = oppositePlanes(rh));
160 bool lrOpposite = lh->oppositePlanes(rh);
161 SkASSERT(lrOpposite != trOpposite);
162 return COMPARE_RESULT(10, lrOpposite);
163 }
164 if (lrOrder < 0) {
165 if (ltOrder < 0) {
166 return COMPARE_RESULT(11, trOrder);
167 }
168 return COMPARE_RESULT(12, ltOrder);
169 }
170 return COMPARE_RESULT(13, !lrOrder);
171 }
172
173 // given a line, see if the opposite curve's convex hull is all on one side
174 // returns -1=not on one side 0=this CW of test 1=this CCW of test
allOnOneSide(const SkOpAngle * test)175 int SkOpAngle::allOnOneSide(const SkOpAngle* test) {
176 SkASSERT(!fIsCurve);
177 SkASSERT(test->fIsCurve);
178 const SkDPoint& origin = test->fCurvePart[0];
179 SkVector line;
180 if (segment()->verb() == SkPath::kLine_Verb) {
181 const SkPoint* linePts = segment()->pts();
182 int lineStart = fStart->t() < fEnd->t() ? 0 : 1;
183 line = linePts[lineStart ^ 1] - linePts[lineStart];
184 } else {
185 line = (fCurvePart[1] - fCurvePart[0]).asSkVector();
186 }
187 float crosses[3];
188 SkPath::Verb testVerb = test->segment()->verb();
189 int iMax = SkPathOpsVerbToPoints(testVerb);
190 // SkASSERT(origin == test.fCurveHalf[0]);
191 const SkDCurve& testCurve = test->fCurvePart;
192 for (int index = 1; index <= iMax; ++index) {
193 float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY));
194 float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX));
195 crosses[index - 1] = AlmostEqualUlps(xy1, xy2) ? 0 : xy1 - xy2;
196 }
197 if (crosses[0] * crosses[1] < 0) {
198 return -1;
199 }
200 if (SkPath::kCubic_Verb == testVerb) {
201 if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) {
202 return -1;
203 }
204 }
205 if (crosses[0]) {
206 return crosses[0] < 0;
207 }
208 if (crosses[1]) {
209 return crosses[1] < 0;
210 }
211 if (SkPath::kCubic_Verb == testVerb && crosses[2]) {
212 return crosses[2] < 0;
213 }
214 fUnorderable = true;
215 return -1;
216 }
217
checkCrossesZero() const218 bool SkOpAngle::checkCrossesZero() const {
219 int start = SkTMin(fSectorStart, fSectorEnd);
220 int end = SkTMax(fSectorStart, fSectorEnd);
221 bool crossesZero = end - start > 16;
222 return crossesZero;
223 }
224
checkParallel(SkOpAngle * rh)225 bool SkOpAngle::checkParallel(SkOpAngle* rh) {
226 SkDVector scratch[2];
227 const SkDVector* sweep, * tweep;
228 if (!this->fUnorderedSweep) {
229 sweep = this->fSweep;
230 } else {
231 scratch[0] = this->fCurvePart[1] - this->fCurvePart[0];
232 sweep = &scratch[0];
233 }
234 if (!rh->fUnorderedSweep) {
235 tweep = rh->fSweep;
236 } else {
237 scratch[1] = rh->fCurvePart[1] - rh->fCurvePart[0];
238 tweep = &scratch[1];
239 }
240 double s0xt0 = sweep->crossCheck(*tweep);
241 if (tangentsDiverge(rh, s0xt0)) {
242 return s0xt0 < 0;
243 }
244 // compute the perpendicular to the endpoints and see where it intersects the opposite curve
245 // if the intersections within the t range, do a cross check on those
246 bool inside;
247 if (!fCurvePart[SkPathOpsVerbToPoints(this->segment()->verb())].approximatelyEqual(
248 rh->fCurvePart[SkPathOpsVerbToPoints(rh->segment()->verb())])) {
249 if (this->endToSide(rh, &inside)) {
250 return inside;
251 }
252 if (rh->endToSide(this, &inside)) {
253 return !inside;
254 }
255 }
256 if (this->midToSide(rh, &inside)) {
257 return inside;
258 }
259 if (rh->midToSide(this, &inside)) {
260 return !inside;
261 }
262 // compute the cross check from the mid T values (last resort)
263 SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fCurvePart[0];
264 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fCurvePart[0];
265 double m0xm1 = m0.crossCheck(m1);
266 if (m0xm1 == 0) {
267 this->fUnorderable = true;
268 rh->fUnorderable = true;
269 return true;
270 }
271 return m0xm1 < 0;
272 }
273
274 // the original angle is too short to get meaningful sector information
275 // lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
276 // would cause it to intersect one of the adjacent angles
computeSector()277 bool SkOpAngle::computeSector() {
278 if (fComputedSector) {
279 return !fUnorderable;
280 }
281 fComputedSector = true;
282 bool stepUp = fStart->t() < fEnd->t();
283 const SkOpSpanBase* checkEnd = fEnd;
284 if (checkEnd->final() && stepUp) {
285 fUnorderable = true;
286 return false;
287 }
288 do {
289 // advance end
290 const SkOpSegment* other = checkEnd->segment();
291 const SkOpSpanBase* oSpan = other->head();
292 do {
293 if (oSpan->segment() != segment()) {
294 continue;
295 }
296 if (oSpan == checkEnd) {
297 continue;
298 }
299 if (!approximately_equal(oSpan->t(), checkEnd->t())) {
300 continue;
301 }
302 goto recomputeSector;
303 } while (!oSpan->final() && (oSpan = oSpan->upCast()->next()));
304 checkEnd = stepUp ? !checkEnd->final()
305 ? checkEnd->upCast()->next() : nullptr
306 : checkEnd->prev();
307 } while (checkEnd);
308 recomputeSector:
309 SkOpSpanBase* computedEnd = stepUp ? checkEnd ? checkEnd->prev() : fEnd->segment()->head()
310 : checkEnd ? checkEnd->upCast()->next() : fEnd->segment()->tail();
311 if (checkEnd == fEnd || computedEnd == fEnd || computedEnd == fStart) {
312 fUnorderable = true;
313 return false;
314 }
315 if (stepUp != (fStart->t() < computedEnd->t())) {
316 fUnorderable = true;
317 return false;
318 }
319 SkOpSpanBase* saveEnd = fEnd;
320 fComputedEnd = fEnd = computedEnd;
321 setSpans();
322 setSector();
323 fEnd = saveEnd;
324 return !fUnorderable;
325 }
326
convexHullOverlaps(const SkOpAngle * rh) const327 int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) const {
328 const SkDVector* sweep = this->fSweep;
329 const SkDVector* tweep = rh->fSweep;
330 double s0xs1 = sweep[0].crossCheck(sweep[1]);
331 double s0xt0 = sweep[0].crossCheck(tweep[0]);
332 double s1xt0 = sweep[1].crossCheck(tweep[0]);
333 bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0;
334 double s0xt1 = sweep[0].crossCheck(tweep[1]);
335 double s1xt1 = sweep[1].crossCheck(tweep[1]);
336 tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0;
337 double t0xt1 = tweep[0].crossCheck(tweep[1]);
338 if (tBetweenS) {
339 return -1;
340 }
341 if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1 equals t0 to t1
342 return -1;
343 }
344 bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0;
345 sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0;
346 if (sBetweenT) {
347 return -1;
348 }
349 // if all of the sweeps are in the same half plane, then the order of any pair is enough
350 if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) {
351 return 0;
352 }
353 if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) {
354 return 1;
355 }
356 // if the outside sweeps are greater than 180 degress:
357 // first assume the inital tangents are the ordering
358 // if the midpoint direction matches the inital order, that is enough
359 SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fCurvePart[0];
360 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fCurvePart[0];
361 double m0xm1 = m0.crossCheck(m1);
362 if (s0xt0 > 0 && m0xm1 > 0) {
363 return 0;
364 }
365 if (s0xt0 < 0 && m0xm1 < 0) {
366 return 1;
367 }
368 if (tangentsDiverge(rh, s0xt0)) {
369 return s0xt0 < 0;
370 }
371 return m0xm1 < 0;
372 }
373
374 // OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
distEndRatio(double dist) const375 double SkOpAngle::distEndRatio(double dist) const {
376 double longest = 0;
377 const SkOpSegment& segment = *this->segment();
378 int ptCount = SkPathOpsVerbToPoints(segment.verb());
379 const SkPoint* pts = segment.pts();
380 for (int idx1 = 0; idx1 <= ptCount - 1; ++idx1) {
381 for (int idx2 = idx1 + 1; idx2 <= ptCount; ++idx2) {
382 if (idx1 == idx2) {
383 continue;
384 }
385 SkDVector v;
386 v.set(pts[idx2] - pts[idx1]);
387 double lenSq = v.lengthSquared();
388 longest = SkTMax(longest, lenSq);
389 }
390 }
391 return sqrt(longest) / dist;
392 }
393
endsIntersect(SkOpAngle * rh)394 bool SkOpAngle::endsIntersect(SkOpAngle* rh) {
395 SkPath::Verb lVerb = this->segment()->verb();
396 SkPath::Verb rVerb = rh->segment()->verb();
397 int lPts = SkPathOpsVerbToPoints(lVerb);
398 int rPts = SkPathOpsVerbToPoints(rVerb);
399 SkDLine rays[] = {{{this->fCurvePart[0], rh->fCurvePart[rPts]}},
400 {{this->fCurvePart[0], this->fCurvePart[lPts]}}};
401 if (rays[0][1] == rays[1][1]) {
402 return checkParallel(rh);
403 }
404 double smallTs[2] = {-1, -1};
405 bool limited[2] = {false, false};
406 for (int index = 0; index < 2; ++index) {
407 SkPath::Verb cVerb = index ? rVerb : lVerb;
408 // if the curve is a line, then the line and the ray intersect only at their crossing
409 if (cVerb == SkPath::kLine_Verb) {
410 continue;
411 }
412 const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
413 SkIntersections i;
414 (*CurveIntersectRay[cVerb])(segment.pts(), segment.weight(), rays[index], &i);
415 double tStart = index ? rh->fStart->t() : this->fStart->t();
416 double tEnd = index ? rh->fComputedEnd->t() : this->fComputedEnd->t();
417 bool testAscends = tStart < (index ? rh->fComputedEnd->t() : this->fComputedEnd->t());
418 double t = testAscends ? 0 : 1;
419 for (int idx2 = 0; idx2 < i.used(); ++idx2) {
420 double testT = i[0][idx2];
421 if (!approximately_between_orderable(tStart, testT, tEnd)) {
422 continue;
423 }
424 if (approximately_equal_orderable(tStart, testT)) {
425 continue;
426 }
427 smallTs[index] = t = testAscends ? SkTMax(t, testT) : SkTMin(t, testT);
428 limited[index] = approximately_equal_orderable(t, tEnd);
429 }
430 }
431 bool sRayLonger = false;
432 SkDVector sCept = {0, 0};
433 double sCeptT = -1;
434 int sIndex = -1;
435 bool useIntersect = false;
436 for (int index = 0; index < 2; ++index) {
437 if (smallTs[index] < 0) {
438 continue;
439 }
440 const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
441 const SkDPoint& dPt = segment.dPtAtT(smallTs[index]);
442 SkDVector cept = dPt - rays[index][0];
443 // If this point is on the curve, it should have been detected earlier by ordinary
444 // curve intersection. This may be hard to determine in general, but for lines,
445 // the point could be close to or equal to its end, but shouldn't be near the start.
446 if ((index ? lPts : rPts) == 1) {
447 SkDVector total = rays[index][1] - rays[index][0];
448 if (cept.lengthSquared() * 2 < total.lengthSquared()) {
449 continue;
450 }
451 }
452 SkDVector end = rays[index][1] - rays[index][0];
453 if (cept.fX * end.fX < 0 || cept.fY * end.fY < 0) {
454 continue;
455 }
456 double rayDist = cept.length();
457 double endDist = end.length();
458 bool rayLonger = rayDist > endDist;
459 if (limited[0] && limited[1] && rayLonger) {
460 useIntersect = true;
461 sRayLonger = rayLonger;
462 sCept = cept;
463 sCeptT = smallTs[index];
464 sIndex = index;
465 break;
466 }
467 double delta = fabs(rayDist - endDist);
468 double minX, minY, maxX, maxY;
469 minX = minY = SK_ScalarInfinity;
470 maxX = maxY = -SK_ScalarInfinity;
471 const SkDCurve& curve = index ? rh->fCurvePart : this->fCurvePart;
472 int ptCount = index ? rPts : lPts;
473 for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
474 minX = SkTMin(minX, curve[idx2].fX);
475 minY = SkTMin(minY, curve[idx2].fY);
476 maxX = SkTMax(maxX, curve[idx2].fX);
477 maxY = SkTMax(maxY, curve[idx2].fY);
478 }
479 double maxWidth = SkTMax(maxX - minX, maxY - minY);
480 delta /= maxWidth;
481 if (delta > 1e-3 && (useIntersect ^= true)) { // FIXME: move this magic number
482 sRayLonger = rayLonger;
483 sCept = cept;
484 sCeptT = smallTs[index];
485 sIndex = index;
486 }
487 }
488 if (useIntersect) {
489 const SkDCurve& curve = sIndex ? rh->fCurvePart : this->fCurvePart;
490 const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment();
491 double tStart = sIndex ? rh->fStart->t() : fStart->t();
492 SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
493 double septDir = mid.crossCheck(sCept);
494 if (!septDir) {
495 return checkParallel(rh);
496 }
497 return sRayLonger ^ (sIndex == 0) ^ (septDir < 0);
498 } else {
499 return checkParallel(rh);
500 }
501 }
502
endToSide(const SkOpAngle * rh,bool * inside) const503 bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const {
504 const SkOpSegment* segment = this->segment();
505 SkPath::Verb verb = segment->verb();
506 SkDLine rayEnd;
507 rayEnd[0].set(this->fEnd->pt());
508 rayEnd[1] = rayEnd[0];
509 SkDVector slopeAtEnd = (*CurveDSlopeAtT[verb])(segment->pts(), segment->weight(),
510 this->fEnd->t());
511 rayEnd[1].fX += slopeAtEnd.fY;
512 rayEnd[1].fY -= slopeAtEnd.fX;
513 SkIntersections iEnd;
514 const SkOpSegment* oppSegment = rh->segment();
515 SkPath::Verb oppVerb = oppSegment->verb();
516 (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayEnd, &iEnd);
517 double endDist;
518 int closestEnd = iEnd.closestTo(rh->fStart->t(), rh->fEnd->t(), rayEnd[0], &endDist);
519 if (closestEnd < 0) {
520 return false;
521 }
522 if (!endDist) {
523 return false;
524 }
525 SkDPoint start;
526 start.set(this->fStart->pt());
527 // OPTIMIZATION: multiple times in the code we find the max scalar
528 double minX, minY, maxX, maxY;
529 minX = minY = SK_ScalarInfinity;
530 maxX = maxY = -SK_ScalarInfinity;
531 const SkDCurve& curve = rh->fCurvePart;
532 int oppPts = SkPathOpsVerbToPoints(oppVerb);
533 for (int idx2 = 0; idx2 <= oppPts; ++idx2) {
534 minX = SkTMin(minX, curve[idx2].fX);
535 minY = SkTMin(minY, curve[idx2].fY);
536 maxX = SkTMax(maxX, curve[idx2].fX);
537 maxY = SkTMax(maxY, curve[idx2].fY);
538 }
539 double maxWidth = SkTMax(maxX - minX, maxY - minY);
540 endDist /= maxWidth;
541 if (endDist < 5e-11) { // empirically found
542 return false;
543 }
544 const SkDPoint* endPt = &rayEnd[0];
545 SkDPoint oppPt = iEnd.pt(closestEnd);
546 SkDVector vLeft = *endPt - start;
547 SkDVector vRight = oppPt - start;
548 double dir = vLeft.crossCheck(vRight);
549 if (!dir) {
550 return false;
551 }
552 *inside = dir < 0;
553 return true;
554 }
555
556 /* y<0 y==0 y>0 x<0 x==0 x>0 xy<0 xy==0 xy>0
557 0 x x x
558 1 x x x
559 2 x x x
560 3 x x x
561 4 x x x
562 5 x x x
563 6 x x x
564 7 x x x
565 8 x x x
566 9 x x x
567 10 x x x
568 11 x x x
569 12 x x x
570 13 x x x
571 14 x x x
572 15 x x x
573 */
findSector(SkPath::Verb verb,double x,double y) const574 int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const {
575 double absX = fabs(x);
576 double absY = fabs(y);
577 double xy = SkPath::kLine_Verb == verb || !AlmostEqualUlps(absX, absY) ? absX - absY : 0;
578 // If there are four quadrants and eight octants, and since the Latin for sixteen is sedecim,
579 // one could coin the term sedecimant for a space divided into 16 sections.
580 // http://english.stackexchange.com/questions/133688/word-for-something-partitioned-into-16-parts
581 static const int sedecimant[3][3][3] = {
582 // y<0 y==0 y>0
583 // x<0 x==0 x>0 x<0 x==0 x>0 x<0 x==0 x>0
584 {{ 4, 3, 2}, { 7, -1, 15}, {10, 11, 12}}, // abs(x) < abs(y)
585 {{ 5, -1, 1}, {-1, -1, -1}, { 9, -1, 13}}, // abs(x) == abs(y)
586 {{ 6, 3, 0}, { 7, -1, 15}, { 8, 11, 14}}, // abs(x) > abs(y)
587 };
588 int sector = sedecimant[(xy >= 0) + (xy > 0)][(y >= 0) + (y > 0)][(x >= 0) + (x > 0)] * 2 + 1;
589 // SkASSERT(SkPath::kLine_Verb == verb || sector >= 0);
590 return sector;
591 }
592
globalState() const593 SkOpGlobalState* SkOpAngle::globalState() const {
594 return this->segment()->globalState();
595 }
596
597
598 // OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
599 // OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
insert(SkOpAngle * angle)600 void SkOpAngle::insert(SkOpAngle* angle) {
601 if (angle->fNext) {
602 if (loopCount() >= angle->loopCount()) {
603 if (!merge(angle)) {
604 return;
605 }
606 } else if (fNext) {
607 if (!angle->merge(this)) {
608 return;
609 }
610 } else {
611 angle->insert(this);
612 }
613 return;
614 }
615 bool singleton = nullptr == fNext;
616 if (singleton) {
617 fNext = this;
618 }
619 SkOpAngle* next = fNext;
620 if (next->fNext == this) {
621 if (singleton || angle->after(this)) {
622 this->fNext = angle;
623 angle->fNext = next;
624 } else {
625 next->fNext = angle;
626 angle->fNext = this;
627 }
628 debugValidateNext();
629 return;
630 }
631 SkOpAngle* last = this;
632 do {
633 SkASSERT(last->fNext == next);
634 if (angle->after(last)) {
635 last->fNext = angle;
636 angle->fNext = next;
637 debugValidateNext();
638 return;
639 }
640 last = next;
641 next = next->fNext;
642 if (last == this) {
643 if (next->fUnorderable) {
644 fUnorderable = true;
645 } else {
646 globalState()->setAngleCoincidence();
647 this->fNext = angle;
648 angle->fNext = next;
649 angle->fCheckCoincidence = true;
650 }
651 return;
652 }
653 } while (true);
654 }
655
lastMarked() const656 SkOpSpanBase* SkOpAngle::lastMarked() const {
657 if (fLastMarked) {
658 if (fLastMarked->chased()) {
659 return nullptr;
660 }
661 fLastMarked->setChased(true);
662 }
663 return fLastMarked;
664 }
665
loopContains(const SkOpAngle * angle) const666 bool SkOpAngle::loopContains(const SkOpAngle* angle) const {
667 if (!fNext) {
668 return false;
669 }
670 const SkOpAngle* first = this;
671 const SkOpAngle* loop = this;
672 const SkOpSegment* tSegment = angle->fStart->segment();
673 double tStart = angle->fStart->t();
674 double tEnd = angle->fEnd->t();
675 do {
676 const SkOpSegment* lSegment = loop->fStart->segment();
677 if (lSegment != tSegment) {
678 continue;
679 }
680 double lStart = loop->fStart->t();
681 if (lStart != tEnd) {
682 continue;
683 }
684 double lEnd = loop->fEnd->t();
685 if (lEnd == tStart) {
686 return true;
687 }
688 } while ((loop = loop->fNext) != first);
689 return false;
690 }
691
loopCount() const692 int SkOpAngle::loopCount() const {
693 int count = 0;
694 const SkOpAngle* first = this;
695 const SkOpAngle* next = this;
696 do {
697 next = next->fNext;
698 ++count;
699 } while (next && next != first);
700 return count;
701 }
702
merge(SkOpAngle * angle)703 bool SkOpAngle::merge(SkOpAngle* angle) {
704 SkASSERT(fNext);
705 SkASSERT(angle->fNext);
706 SkOpAngle* working = angle;
707 do {
708 if (this == working) {
709 return false;
710 }
711 working = working->fNext;
712 } while (working != angle);
713 do {
714 SkOpAngle* next = working->fNext;
715 working->fNext = nullptr;
716 insert(working);
717 working = next;
718 } while (working != angle);
719 // it's likely that a pair of the angles are unorderable
720 debugValidateNext();
721 return true;
722 }
723
midT() const724 double SkOpAngle::midT() const {
725 return (fStart->t() + fEnd->t()) / 2;
726 }
727
midToSide(const SkOpAngle * rh,bool * inside) const728 bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const {
729 const SkOpSegment* segment = this->segment();
730 SkPath::Verb verb = segment->verb();
731 const SkPoint& startPt = this->fStart->pt();
732 const SkPoint& endPt = this->fEnd->pt();
733 SkDPoint dStartPt;
734 dStartPt.set(startPt);
735 SkDLine rayMid;
736 rayMid[0].fX = (startPt.fX + endPt.fX) / 2;
737 rayMid[0].fY = (startPt.fY + endPt.fY) / 2;
738 rayMid[1].fX = rayMid[0].fX + (endPt.fY - startPt.fY);
739 rayMid[1].fY = rayMid[0].fY - (endPt.fX - startPt.fX);
740 SkIntersections iMid;
741 (*CurveIntersectRay[verb])(segment->pts(), segment->weight(), rayMid, &iMid);
742 int iOutside = iMid.mostOutside(this->fStart->t(), this->fEnd->t(), dStartPt);
743 if (iOutside < 0) {
744 return false;
745 }
746 const SkOpSegment* oppSegment = rh->segment();
747 SkPath::Verb oppVerb = oppSegment->verb();
748 SkIntersections oppMid;
749 (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayMid, &oppMid);
750 int oppOutside = oppMid.mostOutside(rh->fStart->t(), rh->fEnd->t(), dStartPt);
751 if (oppOutside < 0) {
752 return false;
753 }
754 SkDVector iSide = iMid.pt(iOutside) - dStartPt;
755 SkDVector oppSide = oppMid.pt(oppOutside) - dStartPt;
756 double dir = iSide.crossCheck(oppSide);
757 if (!dir) {
758 return false;
759 }
760 *inside = dir < 0;
761 return true;
762 }
763
oppositePlanes(const SkOpAngle * rh) const764 bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const {
765 int startSpan = SkTAbs(rh->fSectorStart - fSectorStart);
766 return startSpan >= 8;
767 }
768
orderable(SkOpAngle * rh)769 bool SkOpAngle::orderable(SkOpAngle* rh) {
770 int result;
771 if (!fIsCurve) {
772 if (!rh->fIsCurve) {
773 double leftX = fTangentHalf.dx();
774 double leftY = fTangentHalf.dy();
775 double rightX = rh->fTangentHalf.dx();
776 double rightY = rh->fTangentHalf.dy();
777 double x_ry = leftX * rightY;
778 double rx_y = rightX * leftY;
779 if (x_ry == rx_y) {
780 if (leftX * rightX < 0 || leftY * rightY < 0) {
781 return true; // exactly 180 degrees apart
782 }
783 goto unorderable;
784 }
785 SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- worth finding earlier
786 return x_ry < rx_y;
787 }
788 if ((result = allOnOneSide(rh)) >= 0) {
789 return result;
790 }
791 if (fUnorderable || approximately_zero(rh->fSide)) {
792 goto unorderable;
793 }
794 } else if (!rh->fIsCurve) {
795 if ((result = rh->allOnOneSide(this)) >= 0) {
796 return !result;
797 }
798 if (rh->fUnorderable || approximately_zero(fSide)) {
799 goto unorderable;
800 }
801 }
802 if ((result = convexHullOverlaps(rh)) >= 0) {
803 return result;
804 }
805 return endsIntersect(rh);
806 unorderable:
807 fUnorderable = true;
808 rh->fUnorderable = true;
809 return true;
810 }
811
812 // OPTIMIZE: if this shows up in a profile, add a previous pointer
813 // as is, this should be rarely called
previous() const814 SkOpAngle* SkOpAngle::previous() const {
815 SkOpAngle* last = fNext;
816 do {
817 SkOpAngle* next = last->fNext;
818 if (next == this) {
819 return last;
820 }
821 last = next;
822 } while (true);
823 }
824
segment() const825 SkOpSegment* SkOpAngle::segment() const {
826 return fStart->segment();
827 }
828
set(SkOpSpanBase * start,SkOpSpanBase * end)829 void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) {
830 fStart = start;
831 fComputedEnd = fEnd = end;
832 SkASSERT(start != end);
833 fNext = nullptr;
834 fComputeSector = fComputedSector = fCheckCoincidence = false;
835 setSpans();
836 setSector();
837 SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1);
838 }
839
setCurveHullSweep()840 void SkOpAngle::setCurveHullSweep() {
841 fUnorderedSweep = false;
842 fSweep[0] = fCurvePart[1] - fCurvePart[0];
843 const SkOpSegment* segment = fStart->segment();
844 if (SkPath::kLine_Verb == segment->verb()) {
845 fSweep[1] = fSweep[0];
846 return;
847 }
848 fSweep[1] = fCurvePart[2] - fCurvePart[0];
849 if (SkPath::kCubic_Verb != segment->verb()) {
850 if (!fSweep[0].fX && !fSweep[0].fY) {
851 fSweep[0] = fSweep[1];
852 }
853 return;
854 }
855 SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0];
856 if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
857 fSweep[0] = fSweep[1];
858 fSweep[1] = thirdSweep;
859 if (fSweep[0].fX == 0 && fSweep[0].fY == 0) {
860 fSweep[0] = fSweep[1];
861 fCurvePart[1] = fCurvePart[3];
862 fIsCurve = false;
863 }
864 return;
865 }
866 double s1x3 = fSweep[0].crossCheck(thirdSweep);
867 double s3x2 = thirdSweep.crossCheck(fSweep[1]);
868 if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vectors
869 return;
870 }
871 double s2x1 = fSweep[1].crossCheck(fSweep[0]);
872 // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in trouble
873 // probably such wide sweeps should be artificially subdivided earlier so that never happens
874 SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0);
875 if (s3x2 * s2x1 < 0) {
876 SkASSERT(s2x1 * s1x3 > 0);
877 fSweep[0] = fSweep[1];
878 fUnorderedSweep = true;
879 }
880 fSweep[1] = thirdSweep;
881 }
882
setSpans()883 void SkOpAngle::setSpans() {
884 fUnorderable = false;
885 fLastMarked = nullptr;
886 if (!fStart) {
887 fUnorderable = true;
888 return;
889 }
890 const SkOpSegment* segment = fStart->segment();
891 const SkPoint* pts = segment->pts();
892 SkDEBUGCODE(fCurvePart.fVerb = SkPath::kCubic_Verb);
893 SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
894 = SK_ScalarNaN);
895 SkDEBUGCODE(fCurvePart.fVerb = segment->verb());
896 segment->subDivide(fStart, fEnd, &fCurvePart);
897 setCurveHullSweep();
898 const SkPath::Verb verb = segment->verb();
899 if (verb != SkPath::kLine_Verb
900 && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) {
901 SkDLine lineHalf;
902 lineHalf[0].set(fCurvePart[0].asSkPoint());
903 lineHalf[1].set(fCurvePart[SkPathOpsVerbToPoints(verb)].asSkPoint());
904 fTangentHalf.lineEndPoints(lineHalf);
905 fSide = 0;
906 }
907 switch (verb) {
908 case SkPath::kLine_Verb: {
909 SkASSERT(fStart != fEnd);
910 const SkPoint& cP1 = pts[fStart->t() < fEnd->t()];
911 SkDLine lineHalf;
912 lineHalf[0].set(fStart->pt());
913 lineHalf[1].set(cP1);
914 fTangentHalf.lineEndPoints(lineHalf);
915 fSide = 0;
916 fIsCurve = false;
917 } return;
918 case SkPath::kQuad_Verb:
919 case SkPath::kConic_Verb: {
920 SkLineParameters tangentPart;
921 (void) tangentPart.quadEndPoints(fCurvePart.fQuad);
922 fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
923 } break;
924 case SkPath::kCubic_Verb: {
925 SkLineParameters tangentPart;
926 (void) tangentPart.cubicPart(fCurvePart.fCubic);
927 fSide = -tangentPart.pointDistance(fCurvePart[3]);
928 double testTs[4];
929 // OPTIMIZATION: keep inflections precomputed with cubic segment?
930 int testCount = SkDCubic::FindInflections(pts, testTs);
931 double startT = fStart->t();
932 double endT = fEnd->t();
933 double limitT = endT;
934 int index;
935 for (index = 0; index < testCount; ++index) {
936 if (!::between(startT, testTs[index], limitT)) {
937 testTs[index] = -1;
938 }
939 }
940 testTs[testCount++] = startT;
941 testTs[testCount++] = endT;
942 SkTQSort<double>(testTs, &testTs[testCount - 1]);
943 double bestSide = 0;
944 int testCases = (testCount << 1) - 1;
945 index = 0;
946 while (testTs[index] < 0) {
947 ++index;
948 }
949 index <<= 1;
950 for (; index < testCases; ++index) {
951 int testIndex = index >> 1;
952 double testT = testTs[testIndex];
953 if (index & 1) {
954 testT = (testT + testTs[testIndex + 1]) / 2;
955 }
956 // OPTIMIZE: could avoid call for t == startT, endT
957 SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT);
958 SkLineParameters tangentPart;
959 tangentPart.cubicEndPoints(fCurvePart.fCubic);
960 double testSide = tangentPart.pointDistance(pt);
961 if (fabs(bestSide) < fabs(testSide)) {
962 bestSide = testSide;
963 }
964 }
965 fSide = -bestSide; // compare sign only
966 } break;
967 default:
968 SkASSERT(0);
969 }
970 }
971
setSector()972 void SkOpAngle::setSector() {
973 if (!fStart) {
974 fUnorderable = true;
975 return;
976 }
977 const SkOpSegment* segment = fStart->segment();
978 SkPath::Verb verb = segment->verb();
979 fSectorStart = this->findSector(verb, fSweep[0].fX, fSweep[0].fY);
980 if (fSectorStart < 0) {
981 goto deferTilLater;
982 }
983 if (!fIsCurve) { // if it's a line or line-like, note that both sectors are the same
984 SkASSERT(fSectorStart >= 0);
985 fSectorEnd = fSectorStart;
986 fSectorMask = 1 << fSectorStart;
987 return;
988 }
989 SkASSERT(SkPath::kLine_Verb != verb);
990 fSectorEnd = this->findSector(verb, fSweep[1].fX, fSweep[1].fY);
991 if (fSectorEnd < 0) {
992 deferTilLater:
993 fSectorStart = fSectorEnd = -1;
994 fSectorMask = 0;
995 fComputeSector = true; // can't determine sector until segment length can be found
996 return;
997 }
998 if (fSectorEnd == fSectorStart
999 && (fSectorStart & 3) != 3) { // if the sector has no span, it can't be an exact angle
1000 fSectorMask = 1 << fSectorStart;
1001 return;
1002 }
1003 bool crossesZero = this->checkCrossesZero();
1004 int start = SkTMin(fSectorStart, fSectorEnd);
1005 bool curveBendsCCW = (fSectorStart == start) ^ crossesZero;
1006 // bump the start and end of the sector span if they are on exact compass points
1007 if ((fSectorStart & 3) == 3) {
1008 fSectorStart = (fSectorStart + (curveBendsCCW ? 1 : 31)) & 0x1f;
1009 }
1010 if ((fSectorEnd & 3) == 3) {
1011 fSectorEnd = (fSectorEnd + (curveBendsCCW ? 31 : 1)) & 0x1f;
1012 }
1013 crossesZero = this->checkCrossesZero();
1014 start = SkTMin(fSectorStart, fSectorEnd);
1015 int end = SkTMax(fSectorStart, fSectorEnd);
1016 if (!crossesZero) {
1017 fSectorMask = (unsigned) -1 >> (31 - end + start) << start;
1018 } else {
1019 fSectorMask = (unsigned) -1 >> (31 - start) | ((unsigned) -1 << end);
1020 }
1021 }
1022
starter()1023 SkOpSpan* SkOpAngle::starter() {
1024 return fStart->starter(fEnd);
1025 }
1026
tangentsDiverge(const SkOpAngle * rh,double s0xt0) const1027 bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) const {
1028 if (s0xt0 == 0) {
1029 return false;
1030 }
1031 // if the ctrl tangents are not nearly parallel, use them
1032 // solve for opposite direction displacement scale factor == m
1033 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x
1034 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1]
1035 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x)
1036 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.x)
1037 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x
1038 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y)
1039 // m = v1.cross(v2) / v1.dot(v2)
1040 const SkDVector* sweep = fSweep;
1041 const SkDVector* tweep = rh->fSweep;
1042 double s0dt0 = sweep[0].dot(tweep[0]);
1043 if (!s0dt0) {
1044 return true;
1045 }
1046 SkASSERT(s0dt0 != 0);
1047 double m = s0xt0 / s0dt0;
1048 double sDist = sweep[0].length() * m;
1049 double tDist = tweep[0].length() * m;
1050 bool useS = fabs(sDist) < fabs(tDist);
1051 double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
1052 return mFactor < 2400; // empirically found limit
1053 }
1054