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