Line data Source code
1 : /*
2 : * Copyright 2014 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 : #ifndef SkPathOpsTSect_DEFINED
8 : #define SkPathOpsTSect_DEFINED
9 :
10 : #include "SkArenaAlloc.h"
11 : #include "SkPathOpsBounds.h"
12 : #include "SkPathOpsRect.h"
13 : #include "SkIntersections.h"
14 : #include "SkTSort.h"
15 :
16 : #ifdef SK_DEBUG
17 : typedef uint8_t SkOpDebugBool;
18 : #else
19 : typedef bool SkOpDebugBool;
20 : #endif
21 :
22 : /* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */
23 : template<typename TCurve, typename OppCurve>
24 : class SkTCoincident {
25 : public:
26 0 : SkTCoincident() {
27 0 : this->init();
28 0 : }
29 :
30 0 : void debugInit() {
31 : #ifdef SK_DEBUG
32 0 : this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN;
33 0 : this->fPerpT = SK_ScalarNaN;
34 0 : this->fMatch = 0xFF;
35 : #endif
36 0 : }
37 :
38 : char dumpIsCoincidentStr() const;
39 : void dump() const;
40 :
41 0 : bool isMatch() const {
42 0 : SkASSERT(!!fMatch == fMatch);
43 0 : return SkToBool(fMatch);
44 : }
45 :
46 0 : void init() {
47 0 : fPerpT = -1;
48 0 : fMatch = false;
49 0 : fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
50 0 : }
51 :
52 0 : void markCoincident() {
53 0 : if (!fMatch) {
54 0 : fPerpT = -1;
55 : }
56 0 : fMatch = true;
57 0 : }
58 :
59 0 : const SkDPoint& perpPt() const {
60 0 : return fPerpPt;
61 : }
62 :
63 0 : double perpT() const {
64 0 : return fPerpT;
65 : }
66 :
67 : void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& );
68 :
69 : private:
70 : SkDPoint fPerpPt;
71 : double fPerpT; // perpendicular intersection on opposite curve
72 : SkOpDebugBool fMatch;
73 : };
74 :
75 : template<typename TCurve, typename OppCurve> class SkTSect;
76 : template<typename TCurve, typename OppCurve> class SkTSpan;
77 :
78 : template<typename TCurve, typename OppCurve>
79 : struct SkTSpanBounded {
80 : SkTSpan<TCurve, OppCurve>* fBounded;
81 : SkTSpanBounded* fNext;
82 : };
83 :
84 : /* Curve is either TCurve or SkDCubic */
85 : template<typename TCurve, typename OppCurve>
86 0 : class SkTSpan {
87 : public:
88 : void addBounded(SkTSpan<OppCurve, TCurve>* , SkArenaAlloc* );
89 : double closestBoundedT(const SkDPoint& pt) const;
90 : bool contains(double t) const;
91 :
92 : void debugInit() {
93 : TCurve dummy;
94 : dummy.debugInit();
95 : init(dummy);
96 : initBounds(dummy);
97 : fCoinStart.init();
98 : fCoinEnd.init();
99 : }
100 :
101 : const SkTSect<OppCurve, TCurve>* debugOpp() const;
102 :
103 : #ifdef SK_DEBUG
104 0 : void debugSetGlobalState(SkOpGlobalState* state) {
105 0 : fDebugGlobalState = state;
106 0 : }
107 : #endif
108 :
109 : const SkTSpan* debugSpan(int ) const;
110 : const SkTSpan* debugT(double t) const;
111 : #ifdef SK_DEBUG
112 : bool debugIsBefore(const SkTSpan* span) const;
113 : #endif
114 : void dump() const;
115 : void dumpAll() const;
116 : void dumpBounded(int id) const;
117 : void dumpBounds() const;
118 : void dumpCoin() const;
119 :
120 0 : double endT() const {
121 0 : return fEndT;
122 : }
123 :
124 : SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const;
125 :
126 0 : SkTSpan<OppCurve, TCurve>* findOppT(double t) const {
127 0 : SkTSpan<OppCurve, TCurve>* result = oppT(t);
128 0 : SkOPASSERT(result);
129 0 : return result;
130 : }
131 :
132 0 : SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; })
133 :
134 0 : bool hasOppT(double t) const {
135 0 : return SkToBool(oppT(t));
136 : }
137 :
138 : int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart);
139 : void init(const TCurve& );
140 : bool initBounds(const TCurve& );
141 :
142 0 : bool isBounded() const {
143 0 : return fBounded != nullptr;
144 : }
145 :
146 : bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span);
147 : double linearT(const SkDPoint& ) const;
148 :
149 0 : void markCoincident() {
150 0 : fCoinStart.markCoincident();
151 0 : fCoinEnd.markCoincident();
152 0 : }
153 :
154 0 : const SkTSpan* next() const {
155 0 : return fNext;
156 : }
157 :
158 : bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start,
159 : bool* oppStart, bool* ptsInCommon);
160 :
161 0 : const TCurve& part() const {
162 0 : return fPart;
163 : }
164 :
165 : bool removeAllBounded();
166 : bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp);
167 :
168 0 : void reset() {
169 0 : fBounded = nullptr;
170 0 : }
171 :
172 0 : void resetBounds(const TCurve& curve) {
173 0 : fIsLinear = fIsLine = false;
174 0 : initBounds(curve);
175 0 : }
176 :
177 0 : bool split(SkTSpan* work, SkArenaAlloc* heap) {
178 0 : return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap);
179 : }
180 :
181 : bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap);
182 :
183 0 : double startT() const {
184 0 : return fStartT;
185 : }
186 :
187 : private:
188 :
189 : // implementation is for testing only
190 : int debugID() const {
191 : return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
192 : }
193 :
194 : void dumpID() const;
195 :
196 : int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart);
197 : int linearIntersects(const OppCurve& ) const;
198 : SkTSpan<OppCurve, TCurve>* oppT(double t) const;
199 :
200 : void validate() const;
201 : void validateBounded() const;
202 : void validatePerpT(double oppT) const;
203 : void validatePerpPt(double t, const SkDPoint& ) const;
204 :
205 : TCurve fPart;
206 : SkTCoincident<TCurve, OppCurve> fCoinStart;
207 : SkTCoincident<TCurve, OppCurve> fCoinEnd;
208 : SkTSpanBounded<OppCurve, TCurve>* fBounded;
209 : SkTSpan* fPrev;
210 : SkTSpan* fNext;
211 : SkDRect fBounds;
212 : double fStartT;
213 : double fEndT;
214 : double fBoundsMax;
215 : SkOpDebugBool fCollapsed;
216 : SkOpDebugBool fHasPerp;
217 : SkOpDebugBool fIsLinear;
218 : SkOpDebugBool fIsLine;
219 : SkOpDebugBool fDeleted;
220 : SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
221 : SkDEBUGCODE(SkTSect<TCurve, OppCurve>* fDebugSect);
222 : PATH_OPS_DEBUG_T_SECT_CODE(int fID);
223 : friend class SkTSect<TCurve, OppCurve>;
224 : friend class SkTSect<OppCurve, TCurve>;
225 : friend class SkTSpan<OppCurve, TCurve>;
226 : };
227 :
228 : template<typename TCurve, typename OppCurve>
229 0 : class SkTSect {
230 : public:
231 : SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
232 : static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2,
233 : SkIntersections* intersections);
234 :
235 0 : SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; })
236 : // for testing only
237 : bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const;
238 :
239 : const SkTSect<OppCurve, TCurve>* debugOpp() const {
240 : return SkDEBUGRELEASE(fOppSect, nullptr);
241 : }
242 :
243 : const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const;
244 : const SkTSpan<TCurve, OppCurve>* debugT(double t) const;
245 : void dump() const;
246 : void dumpBoth(SkTSect<OppCurve, TCurve>* ) const;
247 : void dumpBounded(int id) const;
248 : void dumpBounds() const;
249 : void dumpCoin() const;
250 : void dumpCoinCurves() const;
251 : void dumpCurves() const;
252 :
253 : private:
254 : enum {
255 : kZeroS1Set = 1,
256 : kOneS1Set = 2,
257 : kZeroS2Set = 4,
258 : kOneS2Set = 8
259 : };
260 :
261 : SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior);
262 : void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t);
263 : SkTSpan<TCurve, OppCurve>* addOne();
264 :
265 0 : SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) {
266 0 : SkTSpan<TCurve, OppCurve>* result = this->addOne();
267 0 : SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
268 0 : result->splitAt(span, t, &fHeap);
269 0 : result->initBounds(fCurve);
270 0 : span->initBounds(fCurve);
271 0 : return result;
272 : }
273 :
274 : bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t,
275 : double* oppT);
276 : SkTSpan<TCurve, OppCurve>* boundsMax() const;
277 : bool coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
278 : void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e);
279 : bool coincidentHasT(double t);
280 : int collapsed() const;
281 : void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
282 : SkTSpan<TCurve, OppCurve>* last);
283 : int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
284 : SkTSpan<TCurve, OppCurve>** last) const;
285 :
286 : int debugID() const {
287 : return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
288 : }
289 :
290 : bool deleteEmptySpans();
291 : void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const;
292 : void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const;
293 : static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2,
294 : SkIntersections* );
295 : bool extractCoincident(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
296 : SkTSpan<TCurve, OppCurve>* last, SkTSpan<TCurve, OppCurve>** result);
297 : SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first,
298 : SkTSpan<TCurve, OppCurve>** lastPtr);
299 : int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
300 : SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult);
301 : bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* opp) const;
302 : int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
303 : SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* );
304 : bool markSpanGone(SkTSpan<TCurve, OppCurve>* span);
305 : bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const;
306 : void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2,
307 : bool* calcMatched, bool* oppMatched) const;
308 : void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2);
309 : SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
310 : void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
311 : void recoverCollapsed();
312 : void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
313 : void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span,
314 : SkTSect<OppCurve, TCurve>* opp);
315 : bool removeSpan(SkTSpan<TCurve, OppCurve>* span);
316 : void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last);
317 : void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
318 : void removedEndCheck(SkTSpan<TCurve, OppCurve>* span);
319 :
320 0 : void resetRemovedEnds() {
321 0 : fRemovedStartT = fRemovedEndT = false;
322 0 : }
323 :
324 : SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan);
325 : SkTSpan<TCurve, OppCurve>* tail();
326 : bool trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
327 : void unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
328 : bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
329 : SkTSpan<OppCurve, TCurve>* oppFirst);
330 : void validate() const;
331 : void validateBounded() const;
332 :
333 : const TCurve& fCurve;
334 : SkArenaAlloc fHeap;
335 : SkTSpan<TCurve, OppCurve>* fHead;
336 : SkTSpan<TCurve, OppCurve>* fCoincident;
337 : SkTSpan<TCurve, OppCurve>* fDeleted;
338 : int fActiveCount;
339 : bool fRemovedStartT;
340 : bool fRemovedEndT;
341 : SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
342 : SkDEBUGCODE(SkTSect<OppCurve, TCurve>* fOppSect);
343 : PATH_OPS_DEBUG_T_SECT_CODE(int fID);
344 : PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount);
345 : #if DEBUG_T_SECT
346 : int fDebugAllocatedCount;
347 : #endif
348 : friend class SkTSpan<TCurve, OppCurve>;
349 : friend class SkTSpan<OppCurve, TCurve>;
350 : friend class SkTSect<OppCurve, TCurve>;
351 : };
352 :
353 : #define COINCIDENT_SPAN_COUNT 9
354 :
355 : template<typename TCurve, typename OppCurve>
356 0 : void SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t,
357 : const SkDPoint& cPt, const OppCurve& c2) {
358 0 : SkDVector dxdy = c1.dxdyAtT(t);
359 0 : SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
360 0 : SkIntersections i SkDEBUGCODE((c1.globalState()));
361 0 : int used = i.intersectRay(c2, perp);
362 : // only keep closest
363 0 : if (used == 0 || used == 3) {
364 0 : this->init();
365 0 : return;
366 : }
367 0 : fPerpT = i[0][0];
368 0 : fPerpPt = i.pt(0);
369 0 : SkASSERT(used <= 2);
370 0 : if (used == 2) {
371 0 : double distSq = (fPerpPt - cPt).lengthSquared();
372 0 : double dist2Sq = (i.pt(1) - cPt).lengthSquared();
373 0 : if (dist2Sq < distSq) {
374 0 : fPerpT = i[0][1];
375 0 : fPerpPt = i.pt(1);
376 : }
377 : }
378 : #if DEBUG_T_SECT
379 : SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
380 : t, cPt.fX, cPt.fY,
381 : cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
382 : #endif
383 0 : fMatch = cPt.approximatelyEqual(fPerpPt);
384 : #if DEBUG_T_SECT
385 : if (fMatch) {
386 : SkDebugf(""); // allow setting breakpoint
387 : }
388 : #endif
389 : }
390 :
391 : template<typename TCurve, typename OppCurve>
392 0 : void SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkArenaAlloc* heap) {
393 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = heap->make<SkTSpanBounded<OppCurve, TCurve>>();
394 0 : bounded->fBounded = span;
395 0 : bounded->fNext = fBounded;
396 0 : fBounded = bounded;
397 0 : }
398 :
399 : template<typename TCurve, typename OppCurve>
400 0 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing(
401 : SkTSpan<TCurve, OppCurve>* prior) {
402 0 : SkTSpan<TCurve, OppCurve>* result = this->addOne();
403 0 : SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
404 0 : result->fStartT = prior ? prior->fEndT : 0;
405 0 : SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead;
406 0 : result->fEndT = next ? next->fStartT : 1;
407 0 : result->fPrev = prior;
408 0 : result->fNext = next;
409 0 : if (prior) {
410 0 : prior->fNext = result;
411 : } else {
412 0 : fHead = result;
413 : }
414 0 : if (next) {
415 0 : next->fPrev = result;
416 : }
417 0 : result->resetBounds(fCurve);
418 0 : result->validate();
419 0 : return result;
420 : }
421 :
422 : template<typename TCurve, typename OppCurve>
423 0 : void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) {
424 0 : if (!span->hasOppT(t)) {
425 : SkTSpan<TCurve, OppCurve>* priorSpan;
426 0 : SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan);
427 0 : if (!opp) {
428 0 : opp = this->addFollowing(priorSpan);
429 : #if DEBUG_PERP
430 : SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
431 : priorSpan->debugID() : -1, t, opp->debugID());
432 : #endif
433 : }
434 : #if DEBUG_PERP
435 : opp->dump(); SkDebugf("\n");
436 : SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
437 : priorSpan->debugID() : -1, opp->debugID());
438 : #endif
439 0 : opp->addBounded(span, &fHeap);
440 0 : span->addBounded(opp, &fHeap);
441 : }
442 0 : this->validate();
443 : #if DEBUG_T_SECT
444 : span->validatePerpT(t);
445 : #endif
446 0 : }
447 :
448 : template<typename TCurve, typename OppCurve>
449 0 : double SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const {
450 0 : double result = -1;
451 0 : double closest = DBL_MAX;
452 0 : const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
453 0 : while (testBounded) {
454 0 : const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
455 0 : double startDist = test->fPart[0].distanceSquared(pt);
456 0 : if (closest > startDist) {
457 0 : closest = startDist;
458 0 : result = test->fStartT;
459 : }
460 0 : double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt);
461 0 : if (closest > endDist) {
462 0 : closest = endDist;
463 0 : result = test->fEndT;
464 : }
465 0 : testBounded = testBounded->fNext;
466 : }
467 0 : SkASSERT(between(0, result, 1));
468 0 : return result;
469 : }
470 :
471 : #ifdef SK_DEBUG
472 : template<typename TCurve, typename OppCurve>
473 : bool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const {
474 : const SkTSpan* work = this;
475 : do {
476 : if (span == work) {
477 : return true;
478 : }
479 : } while ((work = work->fNext));
480 : return false;
481 : }
482 : #endif
483 :
484 : template<typename TCurve, typename OppCurve>
485 0 : bool SkTSpan<TCurve, OppCurve>::contains(double t) const {
486 0 : const SkTSpan* work = this;
487 0 : do {
488 0 : if (between(work->fStartT, t, work->fEndT)) {
489 0 : return true;
490 : }
491 : } while ((work = work->fNext));
492 0 : return false;
493 : }
494 :
495 : template<typename TCurve, typename OppCurve>
496 : const SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const {
497 : return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr);
498 : }
499 :
500 : template<typename TCurve, typename OppCurve>
501 0 : SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan(
502 : const SkTSpan<OppCurve, TCurve>* opp) const {
503 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
504 0 : while (bounded) {
505 0 : SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
506 0 : if (opp == test) {
507 0 : return test;
508 : }
509 0 : bounded = bounded->fNext;
510 : }
511 0 : return nullptr;
512 : }
513 :
514 : // returns 0 if no hull intersection
515 : // 1 if hulls intersect
516 : // 2 if hulls only share a common endpoint
517 : // -1 if linear and further checking is required
518 : template<typename TCurve, typename OppCurve>
519 0 : int SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp,
520 : bool* start, bool* oppStart) {
521 0 : if (fIsLinear) {
522 0 : return -1;
523 : }
524 : bool ptsInCommon;
525 0 : if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) {
526 0 : SkASSERT(ptsInCommon);
527 0 : return 2;
528 : }
529 : bool linear;
530 0 : if (fPart.hullIntersects(opp->fPart, &linear)) {
531 0 : if (!linear) { // check set true if linear
532 0 : return 1;
533 : }
534 0 : fIsLinear = true;
535 0 : fIsLine = fPart.controlsInside();
536 0 : return ptsInCommon ? 1 : -1;
537 : } else { // hull is not linear; check set true if intersected at the end points
538 0 : return ((int) ptsInCommon) << 1; // 0 or 2
539 : }
540 : return 0;
541 : }
542 :
543 : // OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
544 : // use line intersection to guess a better split than 0.5
545 : // OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
546 : template<typename TCurve, typename OppCurve>
547 0 : int SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp,
548 : bool* start, bool* oppStart) {
549 0 : if (!fBounds.intersects(opp->fBounds)) {
550 0 : return 0;
551 : }
552 0 : int hullSect = this->hullCheck(opp, start, oppStart);
553 0 : if (hullSect >= 0) {
554 0 : return hullSect;
555 : }
556 0 : hullSect = opp->hullCheck(this, oppStart, start);
557 0 : if (hullSect >= 0) {
558 0 : return hullSect;
559 : }
560 0 : return -1;
561 : }
562 :
563 : template<typename TCurve, typename OppCurve>
564 0 : void SkTSpan<TCurve, OppCurve>::init(const TCurve& c) {
565 0 : fPrev = fNext = nullptr;
566 0 : fStartT = 0;
567 0 : fEndT = 1;
568 0 : fBounded = nullptr;
569 0 : resetBounds(c);
570 0 : }
571 :
572 : template<typename TCurve, typename OppCurve>
573 0 : bool SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) {
574 0 : fPart = c.subDivide(fStartT, fEndT);
575 0 : fBounds.setBounds(fPart);
576 0 : fCoinStart.init();
577 0 : fCoinEnd.init();
578 0 : fBoundsMax = SkTMax(fBounds.width(), fBounds.height());
579 0 : fCollapsed = fPart.collapsed();
580 0 : fHasPerp = false;
581 0 : fDeleted = false;
582 : #if DEBUG_T_SECT
583 : if (fCollapsed) {
584 : SkDebugf(""); // for convenient breakpoints
585 : }
586 : #endif
587 0 : return fBounds.valid();
588 : }
589 :
590 : template<typename TCurve, typename OppCurve>
591 0 : bool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) {
592 0 : int result = this->linearIntersects(span->fPart);
593 0 : if (result <= 1) {
594 0 : return SkToBool(result);
595 : }
596 0 : SkASSERT(span->fIsLinear);
597 0 : result = span->linearIntersects(this->fPart);
598 : // SkASSERT(result <= 1);
599 0 : return SkToBool(result);
600 : }
601 :
602 : template<typename TCurve, typename OppCurve>
603 : double SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const {
604 : SkDVector len = fPart[TCurve::kPointLast] - fPart[0];
605 : return fabs(len.fX) > fabs(len.fY)
606 : ? (pt.fX - fPart[0].fX) / len.fX
607 : : (pt.fY - fPart[0].fY) / len.fY;
608 : }
609 :
610 : template<typename TCurve, typename OppCurve>
611 0 : int SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const {
612 : // looks like q1 is near-linear
613 0 : int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes
614 0 : if (!fPart.controlsInside()) {
615 0 : double dist = 0; // if there's any question, compute distance to find best outsiders
616 0 : for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) {
617 0 : for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) {
618 0 : double test = (fPart[outer] - fPart[inner]).lengthSquared();
619 0 : if (dist > test) {
620 0 : continue;
621 : }
622 0 : dist = test;
623 0 : start = outer;
624 0 : end = inner;
625 : }
626 : }
627 : }
628 : // see if q2 is on one side of the line formed by the extreme points
629 0 : double origX = fPart[start].fX;
630 0 : double origY = fPart[start].fY;
631 0 : double adj = fPart[end].fX - origX;
632 0 : double opp = fPart[end].fY - origY;
633 0 : double maxPart = SkTMax(fabs(adj), fabs(opp));
634 0 : double sign = 0; // initialization to shut up warning in release build
635 0 : for (int n = 0; n < OppCurve::kPointCount; ++n) {
636 0 : double dx = q2[n].fY - origY;
637 0 : double dy = q2[n].fX - origX;
638 0 : double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy)));
639 0 : double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
640 0 : if (precisely_zero_when_compared_to(test, maxVal)) {
641 0 : return 1;
642 : }
643 0 : if (approximately_zero_when_compared_to(test, maxVal)) {
644 0 : return 3;
645 : }
646 0 : if (n == 0) {
647 0 : sign = test;
648 0 : continue;
649 : }
650 0 : if (test * sign < 0) {
651 0 : return 1;
652 : }
653 : }
654 0 : return 0;
655 : }
656 :
657 : template<typename TCurve, typename OppCurve>
658 0 : bool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp,
659 : bool* start, bool* oppStart, bool* ptsInCommon) {
660 0 : if (opp->fPart[0] == fPart[0]) {
661 0 : *start = *oppStart = true;
662 0 : } else if (opp->fPart[0] == fPart[TCurve::kPointLast]) {
663 0 : *start = false;
664 0 : *oppStart = true;
665 0 : } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) {
666 0 : *start = true;
667 0 : *oppStart = false;
668 0 : } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) {
669 0 : *start = *oppStart = false;
670 : } else {
671 0 : *ptsInCommon = false;
672 0 : return false;
673 : }
674 0 : *ptsInCommon = true;
675 : const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1];
676 0 : int baseIndex = *start ? 0 : TCurve::kPointLast;
677 0 : fPart.otherPts(baseIndex, otherPts);
678 0 : opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts);
679 0 : const SkDPoint& base = fPart[baseIndex];
680 0 : for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) {
681 0 : SkDVector v1 = *otherPts[o1] - base;
682 0 : for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) {
683 0 : SkDVector v2 = *oppOtherPts[o2] - base;
684 0 : if (v2.dot(v1) >= 0) {
685 0 : return false;
686 : }
687 : }
688 : }
689 0 : return true;
690 : }
691 :
692 : template<typename TCurve, typename OppCurve>
693 0 : SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const {
694 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
695 0 : while (bounded) {
696 0 : SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
697 0 : if (between(test->fStartT, t, test->fEndT)) {
698 0 : return test;
699 : }
700 0 : bounded = bounded->fNext;
701 : }
702 0 : return nullptr;
703 : }
704 :
705 : template<typename TCurve, typename OppCurve>
706 0 : bool SkTSpan<TCurve, OppCurve>::removeAllBounded() {
707 0 : bool deleteSpan = false;
708 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
709 0 : while (bounded) {
710 0 : SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded;
711 0 : deleteSpan |= opp->removeBounded(this);
712 0 : bounded = bounded->fNext;
713 : }
714 0 : return deleteSpan;
715 : }
716 :
717 : template<typename TCurve, typename OppCurve>
718 0 : bool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) {
719 0 : if (fHasPerp) {
720 0 : bool foundStart = false;
721 0 : bool foundEnd = false;
722 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
723 0 : while (bounded) {
724 0 : SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
725 0 : if (opp != test) {
726 0 : foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
727 0 : foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
728 : }
729 0 : bounded = bounded->fNext;
730 : }
731 0 : if (!foundStart || !foundEnd) {
732 0 : fHasPerp = false;
733 0 : fCoinStart.init();
734 0 : fCoinEnd.init();
735 : }
736 : }
737 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
738 0 : SkTSpanBounded<OppCurve, TCurve>* prev = nullptr;
739 0 : while (bounded) {
740 0 : SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext;
741 0 : if (opp == bounded->fBounded) {
742 0 : if (prev) {
743 0 : prev->fNext = boundedNext;
744 0 : return false;
745 : } else {
746 0 : fBounded = boundedNext;
747 0 : return fBounded == nullptr;
748 : }
749 : }
750 0 : prev = bounded;
751 0 : bounded = boundedNext;
752 : }
753 0 : SkOPASSERT(0);
754 0 : return false;
755 : }
756 :
757 : template<typename TCurve, typename OppCurve>
758 0 : bool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) {
759 0 : fStartT = t;
760 0 : fEndT = work->fEndT;
761 0 : if (fStartT == fEndT) {
762 0 : fCollapsed = true;
763 0 : return false;
764 : }
765 0 : work->fEndT = t;
766 0 : if (work->fStartT == work->fEndT) {
767 0 : work->fCollapsed = true;
768 0 : return false;
769 : }
770 0 : fPrev = work;
771 0 : fNext = work->fNext;
772 0 : fIsLinear = work->fIsLinear;
773 0 : fIsLine = work->fIsLine;
774 :
775 0 : work->fNext = this;
776 0 : if (fNext) {
777 0 : fNext->fPrev = this;
778 : }
779 0 : this->validate();
780 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded;
781 0 : fBounded = nullptr;
782 0 : while (bounded) {
783 0 : this->addBounded(bounded->fBounded, heap);
784 0 : bounded = bounded->fNext;
785 : }
786 0 : bounded = fBounded;
787 0 : while (bounded) {
788 0 : bounded->fBounded->addBounded(this, heap);
789 0 : bounded = bounded->fNext;
790 : }
791 0 : return true;
792 : }
793 :
794 : template<typename TCurve, typename OppCurve>
795 0 : void SkTSpan<TCurve, OppCurve>::validate() const {
796 : #if DEBUG_VALIDATE
797 : SkASSERT(this != fPrev);
798 : SkASSERT(this != fNext);
799 : SkASSERT(fNext == nullptr || fNext != fPrev);
800 : SkASSERT(fNext == nullptr || this == fNext->fPrev);
801 : SkASSERT(fPrev == nullptr || this == fPrev->fNext);
802 : this->validateBounded();
803 : #endif
804 : #if DEBUG_T_SECT
805 : SkASSERT(fBounds.width() || fBounds.height() || fCollapsed);
806 : SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF);
807 : SkASSERT(0 <= fStartT);
808 : SkASSERT(fEndT <= 1);
809 : SkASSERT(fStartT <= fEndT);
810 : SkASSERT(fBounded || fCollapsed == 0xFF);
811 : if (fHasPerp) {
812 : if (fCoinStart.isMatch()) {
813 : validatePerpT(fCoinStart.perpT());
814 : validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt());
815 : }
816 : if (fCoinEnd.isMatch()) {
817 : validatePerpT(fCoinEnd.perpT());
818 : validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt());
819 : }
820 : }
821 : #endif
822 0 : }
823 :
824 : template<typename TCurve, typename OppCurve>
825 : void SkTSpan<TCurve, OppCurve>::validateBounded() const {
826 : #if DEBUG_VALIDATE
827 : const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
828 : while (testBounded) {
829 : SkDEBUGCODE(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded);
830 : SkASSERT(!overlap->fDeleted);
831 : #if DEBUG_T_SECT
832 : SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
833 : SkASSERT(overlap->findOppSpan(this));
834 : #endif
835 : testBounded = testBounded->fNext;
836 : }
837 : #endif
838 : }
839 :
840 : template<typename TCurve, typename OppCurve>
841 : void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const {
842 : const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
843 : while (testBounded) {
844 : const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded;
845 : if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) {
846 : return;
847 : }
848 : testBounded = testBounded->fNext;
849 : }
850 : SkASSERT(0);
851 : }
852 :
853 : template<typename TCurve, typename OppCurve>
854 : void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const {
855 : SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
856 : }
857 :
858 :
859 : template<typename TCurve, typename OppCurve>
860 0 : SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c
861 : SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState)
862 : PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
863 : : fCurve(c)
864 : , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4)
865 : , fCoincident(nullptr)
866 : , fDeleted(nullptr)
867 : , fActiveCount(0)
868 0 : SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState))
869 : PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
870 : PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
871 : PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
872 : {
873 0 : this->resetRemovedEnds();
874 0 : fHead = this->addOne();
875 0 : SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
876 0 : fHead->init(c);
877 0 : }
878 :
879 : template<typename TCurve, typename OppCurve>
880 0 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() {
881 : SkTSpan<TCurve, OppCurve>* result;
882 0 : if (fDeleted) {
883 0 : result = fDeleted;
884 0 : fDeleted = result->fNext;
885 : } else {
886 0 : result = fHeap.make<SkTSpan<TCurve, OppCurve>>();
887 : #if DEBUG_T_SECT
888 : ++fDebugAllocatedCount;
889 : #endif
890 : }
891 0 : result->reset();
892 0 : result->fHasPerp = false;
893 0 : result->fDeleted = false;
894 0 : ++fActiveCount;
895 : PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
896 0 : SkDEBUGCODE(result->fDebugSect = this);
897 : #ifdef SK_DEBUG
898 0 : result->fPart.debugInit();
899 0 : result->fCoinStart.debugInit();
900 0 : result->fCoinEnd.debugInit();
901 0 : result->fPrev = result->fNext = nullptr;
902 0 : result->fBounds.debugInit();
903 0 : result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN;
904 0 : result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF;
905 : #endif
906 0 : return result;
907 : }
908 :
909 : template<typename TCurve, typename OppCurve>
910 0 : bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart,
911 : double tStep, double* resultT, double* oppT) {
912 0 : SkTSpan<TCurve, OppCurve> work;
913 0 : double result = work.fStartT = work.fEndT = tStart;
914 0 : SkDEBUGCODE(work.fDebugSect = this);
915 0 : SkDPoint last = fCurve.ptAtT(tStart);
916 : SkDPoint oppPt;
917 0 : bool flip = false;
918 0 : bool contained = false;
919 0 : SkDEBUGCODE(bool down = tStep < 0);
920 0 : const OppCurve& opp = sect2->fCurve;
921 : do {
922 0 : tStep *= 0.5;
923 0 : work.fStartT += tStep;
924 0 : if (flip) {
925 0 : tStep = -tStep;
926 0 : flip = false;
927 : }
928 0 : work.initBounds(fCurve);
929 0 : if (work.fCollapsed) {
930 0 : return false;
931 : }
932 0 : if (last.approximatelyEqual(work.fPart[0])) {
933 0 : break;
934 : }
935 0 : last = work.fPart[0];
936 0 : work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
937 0 : if (work.fCoinStart.isMatch()) {
938 : #if DEBUG_T_SECT
939 : work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt());
940 : #endif
941 0 : double oppTTest = work.fCoinStart.perpT();
942 0 : if (sect2->fHead->contains(oppTTest)) {
943 0 : *oppT = oppTTest;
944 0 : oppPt = work.fCoinStart.perpPt();
945 0 : contained = true;
946 0 : SkASSERT(down ? result > work.fStartT : result < work.fStartT);
947 0 : result = work.fStartT;
948 0 : continue;
949 : }
950 : }
951 0 : tStep = -tStep;
952 0 : flip = true;
953 : } while (true);
954 0 : if (!contained) {
955 0 : return false;
956 : }
957 0 : if (last.approximatelyEqual(fCurve[0])) {
958 0 : result = 0;
959 0 : } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) {
960 0 : result = 1;
961 : }
962 0 : if (oppPt.approximatelyEqual(opp[0])) {
963 0 : *oppT = 0;
964 0 : } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) {
965 0 : *oppT = 1;
966 : }
967 0 : *resultT = result;
968 0 : return true;
969 : }
970 :
971 : // OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
972 : // so that each quad sect has a pointer to the largest, and can update it as spans
973 : // are split
974 : template<typename TCurve, typename OppCurve>
975 0 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const {
976 0 : SkTSpan<TCurve, OppCurve>* test = fHead;
977 0 : SkTSpan<TCurve, OppCurve>* largest = fHead;
978 0 : bool lCollapsed = largest->fCollapsed;
979 0 : while ((test = test->fNext)) {
980 0 : bool tCollapsed = test->fCollapsed;
981 0 : if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
982 0 : largest->fBoundsMax < test->fBoundsMax)) {
983 0 : largest = test;
984 0 : lCollapsed = test->fCollapsed;
985 : }
986 : }
987 0 : return largest;
988 : }
989 :
990 : template<typename TCurve, typename OppCurve>
991 0 : bool SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) {
992 0 : SkTSpan<TCurve, OppCurve>* first = fHead;
993 0 : if (!first) {
994 0 : return false;
995 : }
996 : SkTSpan<TCurve, OppCurve>* last, * next;
997 0 : do {
998 0 : int consecutive = this->countConsecutiveSpans(first, &last);
999 0 : next = last->fNext;
1000 0 : if (consecutive < COINCIDENT_SPAN_COUNT) {
1001 0 : continue;
1002 : }
1003 0 : this->validate();
1004 0 : sect2->validate();
1005 0 : this->computePerpendiculars(sect2, first, last);
1006 0 : this->validate();
1007 0 : sect2->validate();
1008 : // check to see if a range of points are on the curve
1009 0 : SkTSpan<TCurve, OppCurve>* coinStart = first;
1010 0 : do {
1011 0 : bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
1012 0 : if (!success) {
1013 0 : return false;
1014 : }
1015 0 : } while (coinStart && !last->fDeleted);
1016 0 : if (!fHead || !sect2->fHead) {
1017 : break;
1018 : }
1019 0 : if (!next || next->fDeleted) {
1020 : break;
1021 : }
1022 : } while ((first = next));
1023 0 : return true;
1024 : }
1025 :
1026 : template<typename TCurve, typename OppCurve>
1027 0 : void SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2,
1028 : double start1s, double start1e) {
1029 0 : SkTSpan<TCurve, OppCurve>* first = fHead;
1030 0 : SkTSpan<TCurve, OppCurve>* last = this->tail();
1031 0 : SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead;
1032 0 : SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail();
1033 0 : bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
1034 0 : deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
1035 0 : this->removeSpanRange(first, last);
1036 0 : sect2->removeSpanRange(oppFirst, oppLast);
1037 0 : first->fStartT = start1s;
1038 0 : first->fEndT = start1e;
1039 0 : first->resetBounds(fCurve);
1040 0 : first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
1041 0 : first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve);
1042 0 : bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
1043 0 : double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT());
1044 0 : double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT());
1045 0 : if (!oppMatched) {
1046 0 : SkTSwap(oppStartT, oppEndT);
1047 : }
1048 0 : oppFirst->fStartT = oppStartT;
1049 0 : oppFirst->fEndT = oppEndT;
1050 0 : oppFirst->resetBounds(sect2->fCurve);
1051 0 : this->removeCoincident(first, false);
1052 0 : sect2->removeCoincident(oppFirst, true);
1053 0 : if (deleteEmptySpans) {
1054 0 : this->deleteEmptySpans();
1055 0 : sect2->deleteEmptySpans();
1056 : }
1057 0 : }
1058 :
1059 : template<typename TCurve, typename OppCurve>
1060 0 : bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) {
1061 0 : SkTSpan<TCurve, OppCurve>* test = fCoincident;
1062 0 : while (test) {
1063 0 : if (between(test->fStartT, t, test->fEndT)) {
1064 0 : return true;
1065 : }
1066 0 : test = test->fNext;
1067 : }
1068 0 : return false;
1069 : }
1070 :
1071 : template<typename TCurve, typename OppCurve>
1072 0 : int SkTSect<TCurve, OppCurve>::collapsed() const {
1073 0 : int result = 0;
1074 0 : const SkTSpan<TCurve, OppCurve>* test = fHead;
1075 0 : while (test) {
1076 0 : if (test->fCollapsed) {
1077 0 : ++result;
1078 : }
1079 0 : test = test->next();
1080 : }
1081 0 : return result;
1082 : }
1083 :
1084 : template<typename TCurve, typename OppCurve>
1085 0 : void SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2,
1086 : SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
1087 0 : const OppCurve& opp = sect2->fCurve;
1088 0 : SkTSpan<TCurve, OppCurve>* work = first;
1089 0 : SkTSpan<TCurve, OppCurve>* prior = nullptr;
1090 : do {
1091 0 : if (!work->fHasPerp && !work->fCollapsed) {
1092 0 : if (prior) {
1093 0 : work->fCoinStart = prior->fCoinEnd;
1094 : } else {
1095 0 : work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp);
1096 : }
1097 0 : if (work->fCoinStart.isMatch()) {
1098 0 : double perpT = work->fCoinStart.perpT();
1099 0 : if (sect2->coincidentHasT(perpT)) {
1100 0 : work->fCoinStart.init();
1101 : } else {
1102 0 : sect2->addForPerp(work, perpT);
1103 : }
1104 : }
1105 0 : work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp);
1106 0 : if (work->fCoinEnd.isMatch()) {
1107 0 : double perpT = work->fCoinEnd.perpT();
1108 0 : if (sect2->coincidentHasT(perpT)) {
1109 0 : work->fCoinEnd.init();
1110 : } else {
1111 0 : sect2->addForPerp(work, perpT);
1112 : }
1113 : }
1114 0 : work->fHasPerp = true;
1115 : }
1116 0 : if (work == last) {
1117 0 : break;
1118 : }
1119 0 : prior = work;
1120 0 : work = work->fNext;
1121 0 : SkASSERT(work);
1122 : } while (true);
1123 0 : }
1124 :
1125 : template<typename TCurve, typename OppCurve>
1126 0 : int SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
1127 : SkTSpan<TCurve, OppCurve>** lastPtr) const {
1128 0 : int consecutive = 1;
1129 0 : SkTSpan<TCurve, OppCurve>* last = first;
1130 : do {
1131 0 : SkTSpan<TCurve, OppCurve>* next = last->fNext;
1132 0 : if (!next) {
1133 0 : break;
1134 : }
1135 0 : if (next->fStartT > last->fEndT) {
1136 0 : break;
1137 : }
1138 0 : ++consecutive;
1139 0 : last = next;
1140 : } while (true);
1141 0 : *lastPtr = last;
1142 0 : return consecutive;
1143 : }
1144 :
1145 : template<typename TCurve, typename OppCurve>
1146 0 : bool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const {
1147 0 : const SkTSpan<TCurve, OppCurve>* test = fHead;
1148 0 : if (!test) {
1149 0 : return false;
1150 : }
1151 0 : do {
1152 0 : if (test->findOppSpan(span)) {
1153 0 : return true;
1154 : }
1155 : } while ((test = test->next()));
1156 0 : return false;
1157 : }
1158 :
1159 : template<typename TCurve, typename OppCurve>
1160 0 : bool SkTSect<TCurve, OppCurve>::deleteEmptySpans() {
1161 : SkTSpan<TCurve, OppCurve>* test;
1162 0 : SkTSpan<TCurve, OppCurve>* next = fHead;
1163 0 : int safetyHatch = 1000;
1164 0 : while ((test = next)) {
1165 0 : next = test->fNext;
1166 0 : if (!test->fBounded) {
1167 0 : if (!this->removeSpan(test)) {
1168 0 : return false;
1169 : }
1170 : }
1171 0 : if (--safetyHatch < 0) {
1172 0 : return false;
1173 : }
1174 : }
1175 0 : return true;
1176 : }
1177 :
1178 : template<typename TCurve, typename OppCurve>
1179 0 : bool SkTSect<TCurve, OppCurve>::extractCoincident(
1180 : SkTSect<OppCurve, TCurve>* sect2,
1181 : SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
1182 : SkTSpan<TCurve, OppCurve>** result) {
1183 0 : first = findCoincidentRun(first, &last);
1184 0 : if (!first || !last) {
1185 0 : *result = nullptr;
1186 0 : return true;
1187 : }
1188 : // march outwards to find limit of coincidence from here to previous and next spans
1189 0 : double startT = first->fStartT;
1190 0 : double oppStartT SK_INIT_TO_AVOID_WARNING;
1191 0 : double oppEndT SK_INIT_TO_AVOID_WARNING;
1192 0 : SkTSpan<TCurve, OppCurve>* prev = first->fPrev;
1193 0 : SkASSERT(first->fCoinStart.isMatch());
1194 0 : SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT());
1195 0 : SkOPASSERT(last->fCoinEnd.isMatch());
1196 0 : bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
1197 : double coinStart;
1198 : SkDEBUGCODE(double coinEnd);
1199 : SkTSpan<OppCurve, TCurve>* cutFirst;
1200 0 : if (prev && prev->fEndT == startT
1201 0 : && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
1202 : &oppStartT)
1203 0 : && prev->fStartT < coinStart && coinStart < startT
1204 0 : && (cutFirst = prev->oppT(oppStartT))) {
1205 0 : oppFirst = cutFirst;
1206 0 : first = this->addSplitAt(prev, coinStart);
1207 0 : first->markCoincident();
1208 0 : prev->fCoinEnd.markCoincident();
1209 0 : if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
1210 0 : SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
1211 0 : if (oppMatched) {
1212 0 : oppFirst->fCoinEnd.markCoincident();
1213 0 : oppHalf->markCoincident();
1214 0 : oppFirst = oppHalf;
1215 : } else {
1216 0 : oppFirst->markCoincident();
1217 0 : oppHalf->fCoinStart.markCoincident();
1218 : }
1219 : }
1220 : } else {
1221 0 : SkDEBUGCODE(coinStart = first->fStartT);
1222 0 : FAIL_IF(!oppFirst);
1223 0 : SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
1224 : }
1225 : // FIXME: incomplete : if we're not at the end, find end of coin
1226 : SkTSpan<OppCurve, TCurve>* oppLast;
1227 0 : SkOPASSERT(last->fCoinEnd.isMatch());
1228 0 : oppLast = last->findOppT(last->fCoinEnd.perpT());
1229 0 : SkDEBUGCODE(coinEnd = last->fEndT);
1230 : #ifdef SK_DEBUG
1231 0 : if (!this->globalState() || !this->globalState()->debugSkipAssert()) {
1232 0 : oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT;
1233 : }
1234 : #endif
1235 0 : if (!oppMatched) {
1236 0 : SkTSwap(oppFirst, oppLast);
1237 0 : SkTSwap(oppStartT, oppEndT);
1238 : }
1239 0 : SkOPASSERT(oppStartT < oppEndT);
1240 0 : SkASSERT(coinStart == first->fStartT);
1241 0 : SkASSERT(coinEnd == last->fEndT);
1242 0 : SkOPASSERT(oppStartT == oppFirst->fStartT);
1243 0 : SkOPASSERT(oppEndT == oppLast->fEndT);
1244 0 : if (!oppFirst) {
1245 0 : *result = nullptr;
1246 0 : return true;
1247 : }
1248 0 : if (!oppLast) {
1249 0 : *result = nullptr;
1250 0 : return true;
1251 : }
1252 : // reduce coincident runs to single entries
1253 0 : this->validate();
1254 0 : sect2->validate();
1255 0 : bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
1256 0 : deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
1257 0 : this->removeSpanRange(first, last);
1258 0 : sect2->removeSpanRange(oppFirst, oppLast);
1259 0 : first->fEndT = last->fEndT;
1260 0 : first->resetBounds(this->fCurve);
1261 0 : first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve);
1262 0 : first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve);
1263 0 : oppStartT = first->fCoinStart.perpT();
1264 0 : oppEndT = first->fCoinEnd.perpT();
1265 0 : if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
1266 0 : if (!oppMatched) {
1267 0 : SkTSwap(oppStartT, oppEndT);
1268 : }
1269 0 : oppFirst->fStartT = oppStartT;
1270 0 : oppFirst->fEndT = oppEndT;
1271 0 : oppFirst->resetBounds(sect2->fCurve);
1272 : }
1273 0 : this->validateBounded();
1274 0 : sect2->validateBounded();
1275 0 : last = first->fNext;
1276 0 : this->removeCoincident(first, false);
1277 0 : sect2->removeCoincident(oppFirst, true);
1278 0 : if (deleteEmptySpans) {
1279 0 : if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
1280 0 : *result = nullptr;
1281 0 : return false;
1282 : }
1283 : }
1284 0 : this->validate();
1285 0 : sect2->validate();
1286 0 : *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
1287 0 : return true;
1288 : }
1289 :
1290 : template<typename TCurve, typename OppCurve>
1291 0 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun(
1292 : SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) {
1293 0 : SkTSpan<TCurve, OppCurve>* work = first;
1294 0 : SkTSpan<TCurve, OppCurve>* lastCandidate = nullptr;
1295 0 : first = nullptr;
1296 : // find the first fully coincident span
1297 : do {
1298 0 : if (work->fCoinStart.isMatch()) {
1299 : #if DEBUG_T_SECT
1300 : work->validatePerpT(work->fCoinStart.perpT());
1301 : work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
1302 : #endif
1303 0 : SkOPASSERT(work->hasOppT(work->fCoinStart.perpT()));
1304 0 : if (!work->fCoinEnd.isMatch()) {
1305 0 : break;
1306 : }
1307 0 : lastCandidate = work;
1308 0 : if (!first) {
1309 0 : first = work;
1310 : }
1311 0 : } else if (first && work->fCollapsed) {
1312 0 : *lastPtr = lastCandidate;
1313 0 : return first;
1314 : } else {
1315 0 : lastCandidate = nullptr;
1316 0 : SkOPASSERT(!first);
1317 : }
1318 0 : if (work == *lastPtr) {
1319 0 : return first;
1320 : }
1321 0 : work = work->fNext;
1322 0 : if (!work) {
1323 0 : return nullptr;
1324 : }
1325 : } while (true);
1326 0 : if (lastCandidate) {
1327 0 : *lastPtr = lastCandidate;
1328 : }
1329 0 : return first;
1330 : }
1331 :
1332 : template<typename TCurve, typename OppCurve>
1333 0 : int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span,
1334 : SkTSect<OppCurve, TCurve>* opp,
1335 : SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) {
1336 : bool spanStart, oppStart;
1337 0 : int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
1338 0 : if (hullResult >= 0) {
1339 0 : if (hullResult == 2) { // hulls have one point in common
1340 0 : if (!span->fBounded || !span->fBounded->fNext) {
1341 0 : SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan);
1342 0 : if (spanStart) {
1343 0 : span->fEndT = span->fStartT;
1344 : } else {
1345 0 : span->fStartT = span->fEndT;
1346 : }
1347 : } else {
1348 0 : hullResult = 1;
1349 : }
1350 0 : if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) {
1351 0 : SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span);
1352 0 : if (oppStart) {
1353 0 : oppSpan->fEndT = oppSpan->fStartT;
1354 : } else {
1355 0 : oppSpan->fStartT = oppSpan->fEndT;
1356 : }
1357 0 : *oppResult = 2;
1358 : } else {
1359 0 : *oppResult = 1;
1360 : }
1361 : } else {
1362 0 : *oppResult = 1;
1363 : }
1364 0 : return hullResult;
1365 : }
1366 0 : if (span->fIsLine && oppSpan->fIsLine) {
1367 0 : SkIntersections i;
1368 0 : int sects = this->linesIntersect(span, opp, oppSpan, &i);
1369 0 : if (sects == 2) {
1370 0 : return *oppResult = 1;
1371 : }
1372 0 : if (!sects) {
1373 0 : return -1;
1374 : }
1375 0 : this->removedEndCheck(span);
1376 0 : span->fStartT = span->fEndT = i[0][0];
1377 0 : opp->removedEndCheck(oppSpan);
1378 0 : oppSpan->fStartT = oppSpan->fEndT = i[1][0];
1379 0 : return *oppResult = 2;
1380 : }
1381 0 : if (span->fIsLinear || oppSpan->fIsLinear) {
1382 0 : return *oppResult = (int) span->linearsIntersect(oppSpan);
1383 : }
1384 0 : return *oppResult = 1;
1385 : }
1386 :
1387 : template<typename TCurve>
1388 0 : static bool is_parallel(const SkDLine& thisLine, const TCurve& opp) {
1389 0 : if (!opp.IsConic()) {
1390 0 : return false; // FIXME : breaks a lot of stuff now
1391 : }
1392 0 : int finds = 0;
1393 : SkDLine thisPerp;
1394 0 : thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
1395 0 : thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
1396 0 : thisPerp.fPts[1] = thisLine.fPts[1];
1397 0 : SkIntersections perpRayI;
1398 0 : perpRayI.intersectRay(opp, thisPerp);
1399 0 : for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
1400 0 : finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]);
1401 : }
1402 0 : thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
1403 0 : thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
1404 0 : thisPerp.fPts[0] = thisLine.fPts[0];
1405 0 : perpRayI.intersectRay(opp, thisPerp);
1406 0 : for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
1407 0 : finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]);
1408 : }
1409 0 : return finds >= 2;
1410 : }
1411 :
1412 : // while the intersection points are sufficiently far apart:
1413 : // construct the tangent lines from the intersections
1414 : // find the point where the tangent line intersects the opposite curve
1415 : template<typename TCurve, typename OppCurve>
1416 0 : int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
1417 : SkTSect<OppCurve, TCurve>* opp,
1418 : SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) {
1419 0 : SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState));
1420 0 : SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState));
1421 0 : SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }};
1422 0 : SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }};
1423 0 : int loopCount = 0;
1424 0 : double bestDistSq = DBL_MAX;
1425 0 : if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
1426 0 : return 0;
1427 : }
1428 0 : if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
1429 0 : return 0;
1430 : }
1431 : // if the ends of each line intersect the opposite curve, the lines are coincident
1432 0 : if (thisRayI.used() > 1) {
1433 0 : int ptMatches = 0;
1434 0 : for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
1435 0 : for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
1436 0 : ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
1437 : }
1438 : }
1439 0 : if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) {
1440 0 : return 2;
1441 : }
1442 : }
1443 0 : if (oppRayI.used() > 1) {
1444 0 : int ptMatches = 0;
1445 0 : for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
1446 0 : for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
1447 0 : ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
1448 : }
1449 : }
1450 0 : if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) {
1451 0 : return 2;
1452 : }
1453 : }
1454 : do {
1455 : // pick the closest pair of points
1456 0 : double closest = DBL_MAX;
1457 0 : int closeIndex SK_INIT_TO_AVOID_WARNING;
1458 0 : int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
1459 0 : for (int index = 0; index < oppRayI.used(); ++index) {
1460 0 : if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
1461 0 : continue;
1462 : }
1463 0 : for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
1464 0 : if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
1465 0 : continue;
1466 : }
1467 0 : double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
1468 0 : if (closest > distSq) {
1469 0 : closest = distSq;
1470 0 : closeIndex = index;
1471 0 : oppCloseIndex = oIndex;
1472 : }
1473 : }
1474 : }
1475 0 : if (closest == DBL_MAX) {
1476 0 : break;
1477 : }
1478 0 : const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
1479 0 : const SkDPoint& iPt = oppRayI.pt(closeIndex);
1480 0 : if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
1481 0 : && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
1482 0 : && oppIPt.approximatelyEqual(iPt)) {
1483 0 : i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
1484 0 : return i->used();
1485 : }
1486 0 : double distSq = oppIPt.distanceSquared(iPt);
1487 0 : if (bestDistSq < distSq || ++loopCount > 5) {
1488 0 : return 0;
1489 : }
1490 0 : bestDistSq = distSq;
1491 0 : double oppStart = oppRayI[0][closeIndex];
1492 0 : thisLine[0] = fCurve.ptAtT(oppStart);
1493 0 : thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
1494 0 : if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
1495 0 : break;
1496 : }
1497 0 : double start = thisRayI[0][oppCloseIndex];
1498 0 : oppLine[0] = opp->fCurve.ptAtT(start);
1499 0 : oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
1500 0 : if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
1501 0 : break;
1502 0 : }
1503 : } while (true);
1504 : // convergence may fail if the curves are nearly coincident
1505 0 : SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE;
1506 0 : oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve);
1507 0 : oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve);
1508 0 : double tStart = oCoinS.perpT();
1509 0 : double tEnd = oCoinE.perpT();
1510 0 : bool swap = tStart > tEnd;
1511 0 : if (swap) {
1512 0 : SkTSwap(tStart, tEnd);
1513 : }
1514 0 : tStart = SkTMax(tStart, span->fStartT);
1515 0 : tEnd = SkTMin(tEnd, span->fEndT);
1516 0 : if (tStart > tEnd) {
1517 0 : return 0;
1518 : }
1519 : SkDVector perpS, perpE;
1520 0 : if (tStart == span->fStartT) {
1521 0 : SkTCoincident<TCurve, OppCurve> coinS;
1522 0 : coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve);
1523 0 : perpS = span->fPart[0] - coinS.perpPt();
1524 0 : } else if (swap) {
1525 0 : perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast];
1526 : } else {
1527 0 : perpS = oCoinS.perpPt() - oppSpan->fPart[0];
1528 : }
1529 0 : if (tEnd == span->fEndT) {
1530 0 : SkTCoincident<TCurve, OppCurve> coinE;
1531 0 : coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve);
1532 0 : perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt();
1533 0 : } else if (swap) {
1534 0 : perpE = oCoinS.perpPt() - oppSpan->fPart[0];
1535 : } else {
1536 0 : perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast];
1537 : }
1538 0 : if (perpS.dot(perpE) >= 0) {
1539 0 : return 0;
1540 : }
1541 0 : SkTCoincident<TCurve, OppCurve> coinW;
1542 0 : double workT = tStart;
1543 0 : double tStep = tEnd - tStart;
1544 : SkDPoint workPt;
1545 : do {
1546 0 : tStep *= 0.5;
1547 0 : if (precisely_zero(tStep)) {
1548 0 : return 0;
1549 : }
1550 0 : workT += tStep;
1551 0 : workPt = fCurve.ptAtT(workT);
1552 0 : coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
1553 0 : double perpT = coinW.perpT();
1554 0 : if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
1555 0 : continue;
1556 : }
1557 0 : SkDVector perpW = workPt - coinW.perpPt();
1558 0 : if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
1559 0 : tStep = -tStep;
1560 : }
1561 0 : if (workPt.approximatelyEqual(coinW.perpPt())) {
1562 0 : break;
1563 0 : }
1564 : } while (true);
1565 0 : double oppTTest = coinW.perpT();
1566 0 : if (!opp->fHead->contains(oppTTest)) {
1567 0 : return 0;
1568 : }
1569 0 : i->setMax(1);
1570 0 : i->insert(workT, oppTTest, workPt);
1571 0 : return 1;
1572 : }
1573 :
1574 :
1575 : template<typename TCurve, typename OppCurve>
1576 0 : bool SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) {
1577 0 : if (--fActiveCount < 0) {
1578 0 : return false;
1579 : }
1580 0 : span->fNext = fDeleted;
1581 0 : fDeleted = span;
1582 0 : SkOPASSERT(!span->fDeleted);
1583 0 : span->fDeleted = true;
1584 0 : return true;
1585 : }
1586 :
1587 : template<typename TCurve, typename OppCurve>
1588 : bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2,
1589 : double t2) const {
1590 : SkDVector dxdy = this->fCurve.dxdyAtT(t);
1591 : SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
1592 : return dxdy.dot(dxdy2) >= 0;
1593 : }
1594 :
1595 : template<typename TCurve, typename OppCurve>
1596 : void SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2,
1597 : double t2, bool* calcMatched, bool* oppMatched) const {
1598 : if (*calcMatched) {
1599 : SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
1600 : } else {
1601 : *oppMatched = this->matchedDirection(t, sect2, t2);
1602 : *calcMatched = true;
1603 : }
1604 : }
1605 :
1606 : template<typename TCurve, typename OppCurve>
1607 0 : void SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) {
1608 0 : double smallLimit = 0;
1609 : do {
1610 : // find the smallest unprocessed span
1611 0 : SkTSpan<TCurve, OppCurve>* smaller = nullptr;
1612 0 : SkTSpan<TCurve, OppCurve>* test = fCoincident;
1613 0 : do {
1614 0 : if (!test) {
1615 0 : return;
1616 : }
1617 0 : if (test->fStartT < smallLimit) {
1618 0 : continue;
1619 : }
1620 0 : if (smaller && smaller->fEndT < test->fStartT) {
1621 0 : continue;
1622 : }
1623 0 : smaller = test;
1624 : } while ((test = test->fNext));
1625 0 : if (!smaller) {
1626 0 : return;
1627 : }
1628 0 : smallLimit = smaller->fEndT;
1629 : // find next larger span
1630 0 : SkTSpan<TCurve, OppCurve>* prior = nullptr;
1631 0 : SkTSpan<TCurve, OppCurve>* larger = nullptr;
1632 0 : SkTSpan<TCurve, OppCurve>* largerPrior = nullptr;
1633 0 : test = fCoincident;
1634 0 : do {
1635 0 : if (test->fStartT < smaller->fEndT) {
1636 0 : continue;
1637 : }
1638 0 : SkOPASSERT(test->fStartT != smaller->fEndT);
1639 0 : if (larger && larger->fStartT < test->fStartT) {
1640 0 : continue;
1641 : }
1642 0 : largerPrior = prior;
1643 0 : larger = test;
1644 : } while ((prior = test), (test = test->fNext));
1645 0 : if (!larger) {
1646 0 : continue;
1647 : }
1648 : // check middle t value to see if it is coincident as well
1649 0 : double midT = (smaller->fEndT + larger->fStartT) / 2;
1650 0 : SkDPoint midPt = fCurve.ptAtT(midT);
1651 0 : SkTCoincident<TCurve, OppCurve> coin;
1652 0 : coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
1653 0 : if (coin.isMatch()) {
1654 0 : smaller->fEndT = larger->fEndT;
1655 0 : smaller->fCoinEnd = larger->fCoinEnd;
1656 0 : if (largerPrior) {
1657 0 : largerPrior->fNext = larger->fNext;
1658 0 : largerPrior->validate();
1659 : } else {
1660 0 : fCoincident = larger->fNext;
1661 : }
1662 0 : }
1663 : } while (true);
1664 : }
1665 :
1666 : template<typename TCurve, typename OppCurve>
1667 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev(
1668 : SkTSpan<TCurve, OppCurve>* span) const {
1669 : SkTSpan<TCurve, OppCurve>* result = nullptr;
1670 : SkTSpan<TCurve, OppCurve>* test = fHead;
1671 : while (span != test) {
1672 : result = test;
1673 : test = test->fNext;
1674 : SkASSERT(test);
1675 : }
1676 : return result;
1677 : }
1678 :
1679 : template<typename TCurve, typename OppCurve>
1680 0 : void SkTSect<TCurve, OppCurve>::recoverCollapsed() {
1681 0 : SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
1682 0 : while (deleted) {
1683 0 : SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext;
1684 0 : if (deleted->fCollapsed) {
1685 0 : SkTSpan<TCurve, OppCurve>** spanPtr = &fHead;
1686 0 : while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
1687 0 : spanPtr = &(*spanPtr)->fNext;
1688 : }
1689 0 : deleted->fNext = *spanPtr;
1690 0 : *spanPtr = deleted;
1691 : }
1692 0 : deleted = delNext;
1693 : }
1694 0 : }
1695 :
1696 : template<typename TCurve, typename OppCurve>
1697 0 : void SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep,
1698 : SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) {
1699 0 : const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
1700 0 : while (testBounded) {
1701 0 : SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded;
1702 0 : const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
1703 : // may have been deleted when opp did 'remove all but'
1704 0 : if (bounded != keep && !bounded->fDeleted) {
1705 0 : SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
1706 0 : if (bounded->removeBounded(span)) {
1707 0 : opp->removeSpan(bounded);
1708 : }
1709 : }
1710 0 : testBounded = next;
1711 : }
1712 0 : SkASSERT(!span->fDeleted);
1713 0 : SkASSERT(span->findOppSpan(keep));
1714 0 : SkASSERT(keep->findOppSpan(span));
1715 0 : }
1716 :
1717 : template<typename TCurve, typename OppCurve>
1718 0 : void SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) {
1719 0 : SkTSpan<TCurve, OppCurve>* test = fHead;
1720 : SkTSpan<TCurve, OppCurve>* next;
1721 0 : do {
1722 0 : next = test->fNext;
1723 0 : if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
1724 0 : continue;
1725 : }
1726 0 : SkDVector startV = test->fCoinStart.perpPt() - test->fPart[0];
1727 0 : SkDVector endV = test->fCoinEnd.perpPt() - test->fPart[TCurve::kPointLast];
1728 : #if DEBUG_T_SECT
1729 : SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
1730 : startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV));
1731 : #endif
1732 0 : if (startV.dot(endV) <= 0) {
1733 0 : continue;
1734 : }
1735 0 : this->removeSpans(test, opp);
1736 : } while ((test = next));
1737 0 : }
1738 :
1739 : template<typename TCurve, typename OppCurve>
1740 0 : void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) {
1741 0 : this->unlinkSpan(span);
1742 0 : if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
1743 0 : --fActiveCount;
1744 0 : span->fNext = fCoincident;
1745 0 : fCoincident = span;
1746 : } else {
1747 0 : this->markSpanGone(span);
1748 : }
1749 0 : }
1750 :
1751 : template<typename TCurve, typename OppCurve>
1752 0 : void SkTSect<TCurve, OppCurve>::removedEndCheck(SkTSpan<TCurve, OppCurve>* span) {
1753 0 : if (!span->fStartT) {
1754 0 : fRemovedStartT = true;
1755 : }
1756 0 : if (1 == span->fEndT) {
1757 0 : fRemovedEndT = true;
1758 : }
1759 0 : }
1760 :
1761 : template<typename TCurve, typename OppCurve>
1762 0 : bool SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {\
1763 0 : this->removedEndCheck(span);
1764 0 : this->unlinkSpan(span);
1765 0 : return this->markSpanGone(span);
1766 : }
1767 :
1768 : template<typename TCurve, typename OppCurve>
1769 0 : void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first,
1770 : SkTSpan<TCurve, OppCurve>* last) {
1771 0 : if (first == last) {
1772 0 : return;
1773 : }
1774 0 : SkTSpan<TCurve, OppCurve>* span = first;
1775 0 : SkASSERT(span);
1776 0 : SkTSpan<TCurve, OppCurve>* final = last->fNext;
1777 0 : SkTSpan<TCurve, OppCurve>* next = span->fNext;
1778 0 : while ((span = next) && span != final) {
1779 0 : next = span->fNext;
1780 0 : this->markSpanGone(span);
1781 : }
1782 0 : if (final) {
1783 0 : final->fPrev = first;
1784 : }
1785 0 : first->fNext = final;
1786 0 : first->validate();
1787 : }
1788 :
1789 : template<typename TCurve, typename OppCurve>
1790 0 : void SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span,
1791 : SkTSect<OppCurve, TCurve>* opp) {
1792 0 : SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded;
1793 0 : while (bounded) {
1794 0 : SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded;
1795 0 : SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext;
1796 0 : if (span->removeBounded(spanBounded)) { // shuffles last into position 0
1797 0 : this->removeSpan(span);
1798 : }
1799 0 : if (spanBounded->removeBounded(span)) {
1800 0 : opp->removeSpan(spanBounded);
1801 : }
1802 0 : SkASSERT(!span->fDeleted || !opp->debugHasBounded(span));
1803 0 : bounded = next;
1804 : }
1805 0 : }
1806 :
1807 : template<typename TCurve, typename OppCurve>
1808 0 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t,
1809 : SkTSpan<TCurve, OppCurve>** priorSpan) {
1810 0 : SkTSpan<TCurve, OppCurve>* test = fHead;
1811 0 : SkTSpan<TCurve, OppCurve>* prev = nullptr;
1812 0 : while (test && test->fEndT < t) {
1813 0 : prev = test;
1814 0 : test = test->fNext;
1815 : }
1816 0 : *priorSpan = prev;
1817 0 : return test && test->fStartT <= t ? test : nullptr;
1818 : }
1819 :
1820 : template<typename TCurve, typename OppCurve>
1821 0 : SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() {
1822 0 : SkTSpan<TCurve, OppCurve>* result = fHead;
1823 0 : SkTSpan<TCurve, OppCurve>* next = fHead;
1824 0 : while ((next = next->fNext)) {
1825 0 : if (next->fEndT > result->fEndT) {
1826 0 : result = next;
1827 : }
1828 : }
1829 0 : return result;
1830 : }
1831 :
1832 : /* Each span has a range of opposite spans it intersects. After the span is split in two,
1833 : adjust the range to its new size */
1834 : template<typename TCurve, typename OppCurve>
1835 0 : bool SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span,
1836 : SkTSect<OppCurve, TCurve>* opp) {
1837 0 : FAIL_IF(!span->initBounds(fCurve));
1838 0 : const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
1839 0 : while (testBounded) {
1840 0 : SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
1841 0 : const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
1842 0 : int oppSects, sects = this->intersects(span, opp, test, &oppSects);
1843 0 : if (sects >= 1) {
1844 0 : if (oppSects == 2) {
1845 0 : test->initBounds(opp->fCurve);
1846 0 : opp->removeAllBut(span, test, this);
1847 : }
1848 0 : if (sects == 2) {
1849 0 : span->initBounds(fCurve);
1850 0 : this->removeAllBut(test, span, opp);
1851 0 : return true;
1852 : }
1853 : } else {
1854 0 : if (span->removeBounded(test)) {
1855 0 : this->removeSpan(span);
1856 : }
1857 0 : if (test->removeBounded(span)) {
1858 0 : opp->removeSpan(test);
1859 : }
1860 : }
1861 0 : testBounded = next;
1862 : }
1863 0 : return true;
1864 : }
1865 :
1866 : template<typename TCurve, typename OppCurve>
1867 0 : void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
1868 0 : SkTSpan<TCurve, OppCurve>* prev = span->fPrev;
1869 0 : SkTSpan<TCurve, OppCurve>* next = span->fNext;
1870 0 : if (prev) {
1871 0 : prev->fNext = next;
1872 0 : if (next) {
1873 0 : next->fPrev = prev;
1874 0 : next->validate();
1875 : }
1876 : } else {
1877 0 : fHead = next;
1878 0 : if (next) {
1879 0 : next->fPrev = nullptr;
1880 : }
1881 : }
1882 0 : }
1883 :
1884 : template<typename TCurve, typename OppCurve>
1885 0 : bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first,
1886 : SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) {
1887 0 : SkTSpan<TCurve, OppCurve>* test = first;
1888 0 : const SkTSpan<TCurve, OppCurve>* final = last->next();
1889 0 : bool deleteSpan = false;
1890 0 : do {
1891 0 : deleteSpan |= test->removeAllBounded();
1892 0 : } while ((test = test->fNext) != final && test);
1893 0 : first->fBounded = nullptr;
1894 0 : first->addBounded(oppFirst, &fHeap);
1895 : // cannot call validate until remove span range is called
1896 0 : return deleteSpan;
1897 : }
1898 :
1899 :
1900 : template<typename TCurve, typename OppCurve>
1901 0 : void SkTSect<TCurve, OppCurve>::validate() const {
1902 : #if DEBUG_VALIDATE
1903 : int count = 0;
1904 : double last = 0;
1905 : if (fHead) {
1906 : const SkTSpan<TCurve, OppCurve>* span = fHead;
1907 : SkASSERT(!span->fPrev);
1908 : const SkTSpan<TCurve, OppCurve>* next;
1909 : do {
1910 : span->validate();
1911 : SkASSERT(span->fStartT >= last);
1912 : last = span->fEndT;
1913 : ++count;
1914 : next = span->fNext;
1915 : SkASSERT(next != span);
1916 : } while ((span = next) != nullptr);
1917 : }
1918 : SkASSERT(count == fActiveCount);
1919 : #endif
1920 : #if DEBUG_T_SECT
1921 : SkASSERT(fActiveCount <= fDebugAllocatedCount);
1922 : int deletedCount = 0;
1923 : const SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
1924 : while (deleted) {
1925 : ++deletedCount;
1926 : deleted = deleted->fNext;
1927 : }
1928 : const SkTSpan<TCurve, OppCurve>* coincident = fCoincident;
1929 : while (coincident) {
1930 : ++deletedCount;
1931 : coincident = coincident->fNext;
1932 : }
1933 : SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
1934 : #endif
1935 0 : }
1936 :
1937 : template<typename TCurve, typename OppCurve>
1938 0 : void SkTSect<TCurve, OppCurve>::validateBounded() const {
1939 : #if DEBUG_VALIDATE
1940 : if (!fHead) {
1941 : return;
1942 : }
1943 : const SkTSpan<TCurve, OppCurve>* span = fHead;
1944 : do {
1945 : span->validateBounded();
1946 : } while ((span = span->fNext) != nullptr);
1947 : #endif
1948 0 : }
1949 :
1950 : template<typename TCurve, typename OppCurve>
1951 0 : int SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1,
1952 : const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
1953 0 : int zeroOneSet = 0;
1954 0 : if (sect1->fCurve[0] == sect2->fCurve[0]) {
1955 0 : zeroOneSet |= kZeroS1Set | kZeroS2Set;
1956 0 : intersections->insert(0, 0, sect1->fCurve[0]);
1957 : }
1958 0 : if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) {
1959 0 : zeroOneSet |= kZeroS1Set | kOneS2Set;
1960 0 : intersections->insert(0, 1, sect1->fCurve[0]);
1961 : }
1962 0 : if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[0]) {
1963 0 : zeroOneSet |= kOneS1Set | kZeroS2Set;
1964 0 : intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]);
1965 : }
1966 0 : if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) {
1967 0 : zeroOneSet |= kOneS1Set | kOneS2Set;
1968 0 : intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]);
1969 : }
1970 : // check for zero
1971 0 : if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
1972 0 : && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
1973 0 : zeroOneSet |= kZeroS1Set | kZeroS2Set;
1974 0 : intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
1975 : }
1976 0 : if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
1977 0 : && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) {
1978 0 : zeroOneSet |= kZeroS1Set | kOneS2Set;
1979 0 : intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]);
1980 : }
1981 : // check for one
1982 0 : if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
1983 0 : && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) {
1984 0 : zeroOneSet |= kOneS1Set | kZeroS2Set;
1985 0 : intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]);
1986 : }
1987 0 : if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
1988 0 : && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[
1989 : OppCurve::kPointLast])) {
1990 0 : zeroOneSet |= kOneS1Set | kOneS2Set;
1991 0 : intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast],
1992 0 : sect2->fCurve[OppCurve::kPointLast]);
1993 : }
1994 0 : return zeroOneSet;
1995 : }
1996 :
1997 : template<typename TCurve, typename OppCurve>
1998 : struct SkClosestRecord {
1999 0 : bool operator<(const SkClosestRecord& rh) const {
2000 0 : return fClosest < rh.fClosest;
2001 : }
2002 :
2003 0 : void addIntersection(SkIntersections* intersections) const {
2004 0 : double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
2005 0 : double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
2006 0 : intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
2007 0 : }
2008 :
2009 0 : void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2,
2010 : int c1Index, int c2Index) {
2011 0 : const TCurve& c1 = span1->part();
2012 0 : const OppCurve& c2 = span2->part();
2013 0 : if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
2014 0 : return;
2015 : }
2016 0 : double dist = c1[c1Index].distanceSquared(c2[c2Index]);
2017 0 : if (fClosest < dist) {
2018 0 : return;
2019 : }
2020 0 : fC1Span = span1;
2021 0 : fC2Span = span2;
2022 0 : fC1StartT = span1->startT();
2023 0 : fC1EndT = span1->endT();
2024 0 : fC2StartT = span2->startT();
2025 0 : fC2EndT = span2->endT();
2026 0 : fC1Index = c1Index;
2027 0 : fC2Index = c2Index;
2028 0 : fClosest = dist;
2029 : }
2030 :
2031 0 : bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const {
2032 0 : SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
2033 : || mate.fC1Span->endT() <= fC1Span->startT());
2034 0 : SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
2035 : || mate.fC2Span->endT() <= fC2Span->startT());
2036 0 : return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
2037 0 : || fC1Span->startT() == mate.fC1Span->endT()
2038 0 : || fC2Span == mate.fC2Span
2039 0 : || fC2Span->endT() == mate.fC2Span->startT()
2040 0 : || fC2Span->startT() == mate.fC2Span->endT();
2041 : }
2042 :
2043 0 : void merge(const SkClosestRecord& mate) {
2044 0 : fC1Span = mate.fC1Span;
2045 0 : fC2Span = mate.fC2Span;
2046 0 : fClosest = mate.fClosest;
2047 0 : fC1Index = mate.fC1Index;
2048 0 : fC2Index = mate.fC2Index;
2049 0 : }
2050 :
2051 0 : void reset() {
2052 0 : fClosest = FLT_MAX;
2053 0 : SkDEBUGCODE(fC1Span = nullptr);
2054 0 : SkDEBUGCODE(fC2Span = nullptr);
2055 0 : SkDEBUGCODE(fC1Index = fC2Index = -1);
2056 0 : }
2057 :
2058 0 : void update(const SkClosestRecord& mate) {
2059 0 : fC1StartT = SkTMin(fC1StartT, mate.fC1StartT);
2060 0 : fC1EndT = SkTMax(fC1EndT, mate.fC1EndT);
2061 0 : fC2StartT = SkTMin(fC2StartT, mate.fC2StartT);
2062 0 : fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
2063 0 : }
2064 :
2065 : const SkTSpan<TCurve, OppCurve>* fC1Span;
2066 : const SkTSpan<OppCurve, TCurve>* fC2Span;
2067 : double fC1StartT;
2068 : double fC1EndT;
2069 : double fC2StartT;
2070 : double fC2EndT;
2071 : double fClosest;
2072 : int fC1Index;
2073 : int fC2Index;
2074 : };
2075 :
2076 : template<typename TCurve, typename OppCurve>
2077 0 : struct SkClosestSect {
2078 0 : SkClosestSect()
2079 0 : : fUsed(0) {
2080 0 : fClosest.push_back().reset();
2081 0 : }
2082 :
2083 0 : bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2
2084 : SkDEBUGPARAMS(SkIntersections* i)) {
2085 0 : SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed];
2086 0 : record->findEnd(span1, span2, 0, 0);
2087 0 : record->findEnd(span1, span2, 0, OppCurve::kPointLast);
2088 0 : record->findEnd(span1, span2, TCurve::kPointLast, 0);
2089 0 : record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast);
2090 0 : if (record->fClosest == FLT_MAX) {
2091 0 : return false;
2092 : }
2093 0 : for (int index = 0; index < fUsed; ++index) {
2094 0 : SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index];
2095 0 : if (test->matesWith(*record SkDEBUGPARAMS(i))) {
2096 0 : if (test->fClosest > record->fClosest) {
2097 0 : test->merge(*record);
2098 : }
2099 0 : test->update(*record);
2100 0 : record->reset();
2101 0 : return false;
2102 : }
2103 : }
2104 0 : ++fUsed;
2105 0 : fClosest.push_back().reset();
2106 0 : return true;
2107 : }
2108 :
2109 0 : void finish(SkIntersections* intersections) const {
2110 : SkSTArray<TCurve::kMaxIntersections * 3,
2111 0 : const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs;
2112 0 : for (int index = 0; index < fUsed; ++index) {
2113 0 : closestPtrs.push_back(&fClosest[index]);
2114 : }
2115 0 : SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end()
2116 0 : - 1);
2117 0 : for (int index = 0; index < fUsed; ++index) {
2118 0 : const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index];
2119 0 : test->addIntersection(intersections);
2120 : }
2121 0 : }
2122 :
2123 : // this is oversized so that an extra records can merge into final one
2124 : SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest;
2125 : int fUsed;
2126 : };
2127 :
2128 : // returns true if the rect is too small to consider
2129 : template<typename TCurve, typename OppCurve>
2130 0 : void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1,
2131 : SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
2132 : #if DEBUG_T_SECT_DUMP > 1
2133 : gDumpTSectNum = 0;
2134 : #endif
2135 0 : SkDEBUGCODE(sect1->fOppSect = sect2);
2136 0 : SkDEBUGCODE(sect2->fOppSect = sect1);
2137 0 : intersections->reset();
2138 0 : intersections->setMax(TCurve::kMaxIntersections + 4); // give extra for slop
2139 0 : SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead;
2140 0 : SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead;
2141 0 : int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
2142 : // SkASSERT(between(0, sect, 2));
2143 0 : if (!sect) {
2144 0 : return;
2145 : }
2146 0 : if (sect == 2 && oppSect == 2) {
2147 0 : (void) EndsEqual(sect1, sect2, intersections);
2148 0 : return;
2149 : }
2150 0 : span1->addBounded(span2, §1->fHeap);
2151 0 : span2->addBounded(span1, §2->fHeap);
2152 0 : const int kMaxCoinLoopCount = 8;
2153 0 : int coinLoopCount = kMaxCoinLoopCount;
2154 0 : double start1s SK_INIT_TO_AVOID_WARNING;
2155 0 : double start1e SK_INIT_TO_AVOID_WARNING;
2156 : do {
2157 : // find the largest bounds
2158 0 : SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax();
2159 0 : if (!largest1) {
2160 0 : break;
2161 : }
2162 0 : SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax();
2163 : // split it
2164 0 : if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
2165 0 : || (!largest1->fCollapsed && largest2->fCollapsed)))) {
2166 0 : if (largest1->fCollapsed) {
2167 0 : break;
2168 : }
2169 0 : sect1->resetRemovedEnds();
2170 0 : sect2->resetRemovedEnds();
2171 : // trim parts that don't intersect the opposite
2172 0 : SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne();
2173 0 : SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
2174 0 : if (!half1->split(largest1, §1->fHeap)) {
2175 0 : break;
2176 : }
2177 0 : if (!sect1->trim(largest1, sect2)) {
2178 0 : SkOPOBJASSERT(intersections, 0);
2179 0 : return;
2180 : }
2181 0 : if (!sect1->trim(half1, sect2)) {
2182 0 : SkOPOBJASSERT(intersections, 0);
2183 0 : return;
2184 0 : }
2185 : } else {
2186 0 : if (largest2->fCollapsed) {
2187 0 : break;
2188 : }
2189 0 : sect1->resetRemovedEnds();
2190 0 : sect2->resetRemovedEnds();
2191 : // trim parts that don't intersect the opposite
2192 0 : SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne();
2193 0 : SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
2194 0 : if (!half2->split(largest2, §2->fHeap)) {
2195 0 : break;
2196 : }
2197 0 : if (!sect2->trim(largest2, sect1)) {
2198 0 : SkOPOBJASSERT(intersections, 0);
2199 0 : return;
2200 : }
2201 0 : if (!sect2->trim(half2, sect1)) {
2202 0 : SkOPOBJASSERT(intersections, 0);
2203 0 : return;
2204 : }
2205 : }
2206 0 : sect1->validate();
2207 0 : sect2->validate();
2208 : #if DEBUG_T_SECT_LOOP_COUNT
2209 : intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
2210 : #endif
2211 : // if there are 9 or more continuous spans on both sects, suspect coincidence
2212 0 : if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
2213 0 : && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
2214 0 : if (coinLoopCount == kMaxCoinLoopCount) {
2215 0 : start1s = sect1->fHead->fStartT;
2216 0 : start1e = sect1->tail()->fEndT;
2217 : }
2218 0 : if (!sect1->coincidentCheck(sect2)) {
2219 0 : return;
2220 : }
2221 0 : sect1->validate();
2222 0 : sect2->validate();
2223 : #if DEBUG_T_SECT_LOOP_COUNT
2224 : intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
2225 : #endif
2226 0 : if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
2227 : /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
2228 : gets stuck in a loop. It adds an extension to allow a coincident end
2229 : perpendicular to track its intersection in the opposite curve. However,
2230 : the bounding box of the extension does not intersect the original curve,
2231 : so the extension is discarded, only to be added again the next time around. */
2232 0 : sect1->coincidentForce(sect2, start1s, start1e);
2233 0 : sect1->validate();
2234 0 : sect2->validate();
2235 : }
2236 : }
2237 0 : if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
2238 0 : && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
2239 0 : if (!sect1->fHead) {
2240 0 : return;
2241 : }
2242 0 : sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
2243 0 : if (!sect2->fHead) {
2244 0 : return;
2245 : }
2246 0 : sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
2247 0 : sect1->removeByPerpendicular(sect2);
2248 0 : sect1->validate();
2249 0 : sect2->validate();
2250 : #if DEBUG_T_SECT_LOOP_COUNT
2251 : intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
2252 : #endif
2253 0 : if (sect1->collapsed() > TCurve::kMaxIntersections) {
2254 0 : break;
2255 : }
2256 : }
2257 : #if DEBUG_T_SECT_DUMP
2258 : sect1->dumpBoth(sect2);
2259 : #endif
2260 0 : if (!sect1->fHead || !sect2->fHead) {
2261 : break;
2262 0 : }
2263 : } while (true);
2264 0 : SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident;
2265 0 : if (coincident) {
2266 : // if there is more than one coincident span, check loosely to see if they should be joined
2267 0 : if (coincident->fNext) {
2268 0 : sect1->mergeCoincidence(sect2);
2269 0 : coincident = sect1->fCoincident;
2270 : }
2271 0 : SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
2272 0 : do {
2273 0 : if (!coincident) {
2274 0 : return;
2275 : }
2276 0 : if (!coincident->fCoinStart.isMatch()) {
2277 0 : continue;
2278 : }
2279 0 : if (!coincident->fCoinEnd.isMatch()) {
2280 0 : continue;
2281 : }
2282 0 : double perpT = coincident->fCoinStart.perpT();
2283 0 : if (perpT < 0) {
2284 0 : return;
2285 : }
2286 : int index = intersections->insertCoincident(coincident->fStartT,
2287 0 : perpT, coincident->fPart[0]);
2288 0 : if ((intersections->insertCoincident(coincident->fEndT,
2289 : coincident->fCoinEnd.perpT(),
2290 0 : coincident->fPart[TCurve::kPointLast]) < 0) && index >= 0) {
2291 0 : intersections->clearCoincidence(index);
2292 : }
2293 : } while ((coincident = coincident->fNext));
2294 : }
2295 0 : int zeroOneSet = EndsEqual(sect1, sect2, intersections);
2296 : // if (!sect1->fHead || !sect2->fHead) {
2297 : // if the final iteration contains an end (0 or 1),
2298 0 : if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
2299 0 : SkTCoincident<TCurve, OppCurve> perp; // intersect perpendicular with opposite curve
2300 0 : perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
2301 0 : if (perp.isMatch()) {
2302 0 : intersections->insert(0, perp.perpT(), perp.perpPt());
2303 : }
2304 : }
2305 0 : if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
2306 0 : SkTCoincident<TCurve, OppCurve> perp;
2307 0 : perp.setPerp(sect1->fCurve, 1, sect1->fCurve[TCurve::kPointLast], sect2->fCurve);
2308 0 : if (perp.isMatch()) {
2309 0 : intersections->insert(1, perp.perpT(), perp.perpPt());
2310 : }
2311 : }
2312 0 : if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
2313 0 : SkTCoincident<OppCurve, TCurve> perp;
2314 0 : perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
2315 0 : if (perp.isMatch()) {
2316 0 : intersections->insert(perp.perpT(), 0, perp.perpPt());
2317 : }
2318 : }
2319 0 : if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
2320 0 : SkTCoincident<OppCurve, TCurve> perp;
2321 0 : perp.setPerp(sect2->fCurve, 1, sect2->fCurve[OppCurve::kPointLast], sect1->fCurve);
2322 0 : if (perp.isMatch()) {
2323 0 : intersections->insert(perp.perpT(), 1, perp.perpPt());
2324 : }
2325 : }
2326 : // }
2327 0 : if (!sect1->fHead || !sect2->fHead) {
2328 0 : return;
2329 : }
2330 0 : sect1->recoverCollapsed();
2331 0 : sect2->recoverCollapsed();
2332 0 : SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead;
2333 : // check heads and tails for zero and ones and insert them if we haven't already done so
2334 0 : const SkTSpan<TCurve, OppCurve>* head1 = result1;
2335 0 : if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
2336 0 : const SkDPoint& start1 = sect1->fCurve[0];
2337 0 : if (head1->isBounded()) {
2338 0 : double t = head1->closestBoundedT(start1);
2339 0 : if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
2340 0 : intersections->insert(0, t, start1);
2341 : }
2342 : }
2343 : }
2344 0 : const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead;
2345 0 : if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
2346 0 : const SkDPoint& start2 = sect2->fCurve[0];
2347 0 : if (head2->isBounded()) {
2348 0 : double t = head2->closestBoundedT(start2);
2349 0 : if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
2350 0 : intersections->insert(t, 0, start2);
2351 : }
2352 : }
2353 : }
2354 0 : const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail();
2355 0 : if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
2356 0 : const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast];
2357 0 : if (tail1->isBounded()) {
2358 0 : double t = tail1->closestBoundedT(end1);
2359 0 : if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
2360 0 : intersections->insert(1, t, end1);
2361 : }
2362 : }
2363 : }
2364 0 : const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail();
2365 0 : if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
2366 0 : const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast];
2367 0 : if (tail2->isBounded()) {
2368 0 : double t = tail2->closestBoundedT(end2);
2369 0 : if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
2370 0 : intersections->insert(t, 1, end2);
2371 : }
2372 : }
2373 : }
2374 0 : SkClosestSect<TCurve, OppCurve> closest;
2375 0 : do {
2376 0 : while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) {
2377 0 : result1 = result1->fNext;
2378 : }
2379 0 : if (!result1) {
2380 0 : break;
2381 : }
2382 0 : SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead;
2383 0 : bool found = false;
2384 0 : while (result2) {
2385 0 : found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections));
2386 0 : result2 = result2->fNext;
2387 : }
2388 : } while ((result1 = result1->fNext));
2389 0 : closest.finish(intersections);
2390 : // if there is more than one intersection and it isn't already coincident, check
2391 0 : int last = intersections->used() - 1;
2392 0 : for (int index = 0; index < last; ) {
2393 0 : if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
2394 0 : ++index;
2395 0 : continue;
2396 : }
2397 0 : double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
2398 0 : SkDPoint midPt = sect1->fCurve.ptAtT(midT);
2399 : // intersect perpendicular with opposite curve
2400 0 : SkTCoincident<TCurve, OppCurve> perp;
2401 0 : perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
2402 0 : if (!perp.isMatch()) {
2403 0 : ++index;
2404 0 : continue;
2405 : }
2406 0 : if (intersections->isCoincident(index)) {
2407 0 : intersections->removeOne(index);
2408 0 : --last;
2409 0 : } else if (intersections->isCoincident(index + 1)) {
2410 0 : intersections->removeOne(index + 1);
2411 0 : --last;
2412 : } else {
2413 0 : intersections->setCoincident(index++);
2414 : }
2415 0 : intersections->setCoincident(index);
2416 : }
2417 0 : SkOPOBJASSERT(intersections, intersections->used() <= TCurve::kMaxIntersections);
2418 : }
2419 :
2420 : #endif
|
