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