• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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