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#ifndef SkOpSegment_DEFINE
8#define SkOpSegment_DEFINE
9
10#include "src/core/SkArenaAlloc.h"
11#include "src/pathops/SkOpAngle.h"
12#include "src/pathops/SkOpSpan.h"
13#include "src/pathops/SkPathOpsBounds.h"
14#include "src/pathops/SkPathOpsCubic.h"
15#include "src/pathops/SkPathOpsCurve.h"
16
17struct SkDCurve;
18class SkOpCoincidence;
19class SkOpContour;
20enum class SkOpRayDir;
21struct SkOpRayHit;
22class SkPathWriter;
23
24class SkOpSegment {
25public:
26 bool operator<(const SkOpSegment& rh) const {
27 return fBounds.fTop < rh.fBounds.fTop;
28 }
29
30 SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
31 bool* done);
32 SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
33 SkOpSpanBase** endPtr, bool* done);
34 SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
35 SkOpSpanBase** endPtr, bool* done);
36 bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
37 SkPathOp op);
38 bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op,
39 int* sumMiWinding, int* sumSuWinding);
40
41 bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end);
42 bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding);
43
44 SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) {
45 init(pts, weight, parent, SkPath::kConic_Verb);
46 SkDCurve curve;
47 curve.fConic.set(pts, weight);
48 curve.setConicBounds(pts, weight, 0, 1, &fBounds);
49 return this;
50 }
51
52 SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) {
53 init(pts, 1, parent, SkPath::kCubic_Verb);
54 SkDCurve curve;
55 curve.fCubic.set(pts);
56 curve.setCubicBounds(pts, 1, 0, 1, &fBounds);
57 return this;
58 }
59
60 bool addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path) const;
61
62 SkOpAngle* addEndSpan() {
63 SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
64 angle->set(&fTail, fTail.prev());
65 fTail.setFromAngle(angle);
66 return angle;
67 }
68
69 bool addExpanded(double newT, const SkOpSpanBase* test, bool* startOver);
70
71 SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) {
72 SkASSERT(pts[0] != pts[1]);
73 init(pts, 1, parent, SkPath::kLine_Verb);
74 fBounds.setBounds(pts, 2);
75 return this;
76 }
77
78 SkOpPtT* addMissing(double t, SkOpSegment* opp, bool* allExist);
79
80 SkOpAngle* addStartSpan() {
81 SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
82 angle->set(&fHead, fHead.next());
83 fHead.setToAngle(angle);
84 return angle;
85 }
86
87 SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) {
88 init(pts, 1, parent, SkPath::kQuad_Verb);
89 SkDCurve curve;
90 curve.fQuad.set(pts);
91 curve.setQuadBounds(pts, 1, 0, 1, &fBounds);
92 return this;
93 }
94
95 SkOpPtT* addT(double t);
96 SkOpPtT* addT(double t, const SkPoint& pt);
97
98 const SkPathOpsBounds& bounds() const {
99 return fBounds;
100 }
101
102 void bumpCount() {
103 ++fCount;
104 }
105
106 void calcAngles();
107 SkOpSpanBase::Collapsed collapsed(double startT, double endT) const;
108 static bool ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
109 SkOpAngle::IncludeType );
110 static bool ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
111 SkOpAngle::IncludeType );
112 int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType);
113
114 void clearAll();
115 void clearOne(SkOpSpan* span);
116 static void ClearVisited(SkOpSpanBase* span);
117 bool contains(double t) const;
118
119 SkOpContour* contour() const {
120 return fContour;
121 }
122
123 int count() const {
124 return fCount;
125 }
126
127 void debugAddAngle(double startT, double endT);
128#if DEBUG_COIN
129 const SkOpPtT* debugAddT(double t, SkPathOpsDebug::GlitchLog* ) const;
130#endif
131 const SkOpAngle* debugAngle(int id) const;
132#if DEBUG_ANGLE
133 void debugCheckAngleCoin() const;
134#endif
135#if DEBUG_COIN
136 void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const;
137 void debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const;
138 void debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const;
139#endif
140 const SkOpCoincidence* debugCoincidence() const;
141 SkOpContour* debugContour(int id) const;
142
143 int debugID() const {
144 return SkDEBUGRELEASE(fID, -1);
145 }
146
147 SkOpAngle* debugLastAngle();
148#if DEBUG_COIN
149 void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* glitches) const;
150 void debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const;
151 void debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const;
152#endif
153 const SkOpPtT* debugPtT(int id) const;
154 void debugReset();
155 const SkOpSegment* debugSegment(int id) const;
156
157#if DEBUG_ACTIVE_SPANS
158 void debugShowActiveSpans(SkString* str) const;
159#endif
160#if DEBUG_MARK_DONE
161 void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding);
162 void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding);
163#endif
164
165 const SkOpSpanBase* debugSpan(int id) const;
166 void debugValidate() const;
167
168#if DEBUG_COINCIDENCE_ORDER
169 void debugResetCoinT() const;
170 void debugSetCoinT(int, SkScalar ) const;
171#endif
172
173#if DEBUG_COIN
174 static void DebugClearVisited(const SkOpSpanBase* span);
175
176 bool debugVisited() const {
177 if (!fDebugVisited) {
178 fDebugVisited = true;
179 return false;
180 }
181 return true;
182 }
183#endif
184
185#if DEBUG_ANGLE
186 double distSq(double t, const SkOpAngle* opp) const;
187#endif
188
189 bool done() const {
190 SkOPASSERT(fDoneCount <= fCount);
191 return fDoneCount == fCount;
192 }
193
194 bool done(const SkOpAngle* angle) const {
195 return angle->start()->starter(angle->end())->done();
196 }
197
198 SkDPoint dPtAtT(double mid) const {
199 return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
200 }
201
202 SkDVector dSlopeAtT(double mid) const {
203 return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
204 }
205
206 void dump() const;
207 void dumpAll() const;
208 void dumpAngles() const;
209 void dumpCoin() const;
210 void dumpPts(const char* prefix = "seg") const;
211 void dumpPtsInner(const char* prefix = "seg") const;
212
213 const SkOpPtT* existing(double t, const SkOpSegment* opp) const;
214 SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
215 SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
216 SkPathOp op, int xorMiMask, int xorSuMask);
217 SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
218 SkOpSpanBase** nextEnd, bool* unsortable);
219 SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable);
220 SkOpSpan* findSortableTop(SkOpContour* );
221 SkOpGlobalState* globalState() const;
222
223 const SkOpSpan* head() const {
224 return &fHead;
225 }
226
227 SkOpSpan* head() {
228 return &fHead;
229 }
230
231 void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
232
233 SkOpSpan* insert(SkOpSpan* prev) {
234 SkOpGlobalState* globalState = this->globalState();
235 globalState->setAllocatedOpSpan();
236 SkOpSpan* result = globalState->allocator()->make<SkOpSpan>();
237 SkOpSpanBase* next = prev->next();
238 result->setPrev(prev);
239 prev->setNext(result);
240 SkDEBUGCODE(result->ptT()->fT = 0);
241 result->setNext(next);
242 if (next) {
243 next->setPrev(result);
244 }
245 return result;
246 }
247
248 bool isClose(double t, const SkOpSegment* opp) const;
249
250 bool isHorizontal() const {
251 return fBounds.fTop == fBounds.fBottom;
252 }
253
254 SkOpSegment* isSimple(SkOpSpanBase** end, int* step) const {
255 return nextChase(end, step, nullptr, nullptr);
256 }
257
258 bool isVertical() const {
259 return fBounds.fLeft == fBounds.fRight;
260 }
261
262 bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const {
263 return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
264 }
265
266 bool isXor() const;
267
268 void joinEnds(SkOpSegment* start) {
269 fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT());
270 }
271
272 const SkPoint& lastPt() const {
273 return fPts[SkPathOpsVerbToPoints(fVerb)];
274 }
275
276 void markAllDone();
277 bool markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found);
278 bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
279 SkOpSpanBase** lastPtr);
280 bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
281 int oppWinding, SkOpSpanBase** lastPtr);
282 bool markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle, SkOpSpanBase** result);
283 bool markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
284 const SkOpAngle* angle, SkOpSpanBase** result);
285 void markDone(SkOpSpan* );
286 bool markWinding(SkOpSpan* , int winding);
287 bool markWinding(SkOpSpan* , int winding, int oppWinding);
288 bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const;
289 bool missingCoincidence();
290 bool moveMultiples();
291 bool moveNearby();
292
293 SkOpSegment* next() const {
294 return fNext;
295 }
296
297 SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
298 bool operand() const;
299
300 static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
301 int result = start->t() < end->t() ? -start->upCast()->oppValue()
302 : end->upCast()->oppValue();
303 return result;
304 }
305
306 bool oppXor() const;
307
308 const SkOpSegment* prev() const {
309 return fPrev;
310 }
311
312 SkPoint ptAtT(double mid) const {
313 return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
314 }
315
316 const SkPoint* pts() const {
317 return fPts;
318 }
319
320 bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const {
321 SkASSERT(this == span.segment());
322 SkASSERT(this == test.segment());
323 return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
324 }
325
326 bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const {
327 SkASSERT(this == span.segment());
328 return ptsDisjoint(span.fT, span.fPt, t, pt);
329 }
330
331 bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const;
332
333 void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*);
334 void release(const SkOpSpan* );
335
336#if DEBUG_COIN
337 void resetDebugVisited() const {
338 fDebugVisited = false;
339 }
340#endif
341
342 void resetVisited() {
343 fVisited = false;
344 }
345
346 void setContour(SkOpContour* contour) {
347 fContour = contour;
348 }
349
350 void setNext(SkOpSegment* next) {
351 fNext = next;
352 }
353
354 void setPrev(SkOpSegment* prev) {
355 fPrev = prev;
356 }
357
358 void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) {
359 int deltaSum = SpanSign(start, end);
360 *maxWinding = *sumWinding;
361 if (*sumWinding == SK_MinS32) {
362 return;
363 }
364 *sumWinding -= deltaSum;
365 }
366
367 void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
368 int* maxWinding, int* sumWinding);
369 void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding,
370 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
371 bool sortAngles();
372 bool spansNearby(const SkOpSpanBase* ref, const SkOpSpanBase* check, bool* found) const;
373
374 static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) {
375 int result = start->t() < end->t() ? -start->upCast()->windValue()
376 : end->upCast()->windValue();
377 return result;
378 }
379
380 SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) {
381 SkASSERT(start != end);
382 return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
383 }
384
385 bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const;
386
387 const SkOpSpanBase* tail() const {
388 return &fTail;
389 }
390
391 SkOpSpanBase* tail() {
392 return &fTail;
393 }
394
395 bool testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, const SkOpSpanBase* prior,
396 const SkOpSpanBase* spanBase, const SkOpSegment* opp) const;
397
398 SkOpSpan* undoneSpan();
399 int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const;
400 int updateOppWinding(const SkOpAngle* angle) const;
401 int updateOppWindingReverse(const SkOpAngle* angle) const;
402 int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end);
403 int updateWinding(SkOpAngle* angle);
404 int updateWindingReverse(const SkOpAngle* angle);
405
406 static bool UseInnerWinding(int outerWinding, int innerWinding);
407
408 SkPath::Verb verb() const {
409 return fVerb;
410 }
411
412 // look for two different spans that point to the same opposite segment
413 bool visited() {
414 if (!fVisited) {
415 fVisited = true;
416 return false;
417 }
418 return true;
419 }
420
421 SkScalar weight() const {
422 return fWeight;
423 }
424
425 SkOpSpan* windingSpanAtT(double tHit);
426 int windSum(const SkOpAngle* angle) const;
427
428private:
429 SkOpSpan fHead; // the head span always has its t set to zero
430 SkOpSpanBase fTail; // the tail span always has its t set to one
431 SkOpContour* fContour;
432 SkOpSegment* fNext; // forward-only linked list used by contour to walk the segments
433 const SkOpSegment* fPrev;
434 SkPoint* fPts; // pointer into array of points owned by edge builder that may be tweaked
435 SkPathOpsBounds fBounds; // tight bounds
436 SkScalar fWeight;
437 int fCount; // number of spans (one for a non-intersecting segment)
438 int fDoneCount; // number of processed spans (zero initially)
439 SkPath::Verb fVerb;
440 bool fVisited; // used by missing coincidence check
441#if DEBUG_COIN
442 mutable bool fDebugVisited; // used by debug missing coincidence check
443#endif
444#if DEBUG_COINCIDENCE_ORDER
445 mutable int fDebugBaseIndex;
446 mutable SkScalar fDebugBaseMin; // if > 0, the 1st t value in this seg vis-a-vis the ref seg
447 mutable SkScalar fDebugBaseMax;
448 mutable int fDebugLastIndex;
449 mutable SkScalar fDebugLastMin; // if > 0, the last t -- next t val - base has same sign
450 mutable SkScalar fDebugLastMax;
451#endif
452 SkDEBUGCODE(int fID);
453};
454
455#endif
456