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