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