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 
17 struct SkDCurve;
18 class SkOpCoincidence;
19 class SkOpContour;
20 enum class SkOpRayDir;
21 struct SkOpRayHit;
22 class SkPathWriter;
23 
24 class SkOpSegment {
25 public:
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 
addConic(SkPoint pts[3],SkScalar weight,SkOpContour * parent)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 
addCubic(SkPoint pts[4],SkOpContour * parent)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 
addEndSpan()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 
addLine(SkPoint pts[2],SkOpContour * parent)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 
addStartSpan()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 
addQuad(SkPoint pts[3],SkOpContour * parent)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 
bounds()98     const SkPathOpsBounds& bounds() const {
99         return fBounds;
100     }
101 
bumpCount()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 
contour()119     SkOpContour* contour() const {
120         return fContour;
121     }
122 
count()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 
debugID()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 
debugVisited()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 
done()189     bool done() const {
190         SkOPASSERT(fDoneCount <= fCount);
191         return fDoneCount == fCount;
192     }
193 
done(const SkOpAngle * angle)194     bool done(const SkOpAngle* angle) const {
195         return angle->start()->starter(angle->end())->done();
196     }
197 
dPtAtT(double mid)198     SkDPoint dPtAtT(double mid) const {
199         return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
200     }
201 
dSlopeAtT(double mid)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 
head()223     const SkOpSpan* head() const {
224         return &fHead;
225     }
226 
head()227     SkOpSpan* head() {
228         return &fHead;
229     }
230 
231     void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
232 
insert(SkOpSpan * prev)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 
isHorizontal()250     bool isHorizontal() const {
251         return fBounds.fTop == fBounds.fBottom;
252     }
253 
isSimple(SkOpSpanBase ** end,int * step)254     SkOpSegment* isSimple(SkOpSpanBase** end, int* step) const {
255         return nextChase(end, step, nullptr, nullptr);
256     }
257 
isVertical()258     bool isVertical() const {
259         return fBounds.fLeft == fBounds.fRight;
260     }
261 
isVertical(SkOpSpanBase * start,SkOpSpanBase * end)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 
joinEnds(SkOpSegment * start)268     void joinEnds(SkOpSegment* start) {
269         fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT());
270     }
271 
lastPt()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 
next()293     SkOpSegment* next() const {
294         return fNext;
295     }
296 
297     SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
298     bool operand() const;
299 
OppSign(const SkOpSpanBase * start,const SkOpSpanBase * end)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 
prev()308     const SkOpSegment* prev() const {
309         return fPrev;
310     }
311 
ptAtT(double mid)312     SkPoint ptAtT(double mid) const {
313         return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
314     }
315 
pts()316     const SkPoint* pts() const {
317         return fPts;
318     }
319 
ptsDisjoint(const SkOpPtT & span,const SkOpPtT & test)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 
ptsDisjoint(const SkOpPtT & span,double t,const SkPoint & pt)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
resetDebugVisited()337     void resetDebugVisited() const {
338         fDebugVisited = false;
339     }
340 #endif
341 
resetVisited()342     void resetVisited() {
343         fVisited = false;
344     }
345 
setContour(SkOpContour * contour)346     void setContour(SkOpContour* contour) {
347         fContour = contour;
348     }
349 
setNext(SkOpSegment * next)350     void setNext(SkOpSegment* next) {
351         fNext = next;
352     }
353 
setPrev(SkOpSegment * prev)354     void setPrev(SkOpSegment* prev) {
355         fPrev = prev;
356     }
357 
setUpWinding(SkOpSpanBase * start,SkOpSpanBase * end,int * maxWinding,int * sumWinding)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 
SpanSign(const SkOpSpanBase * start,const SkOpSpanBase * end)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 
spanToAngle(SkOpSpanBase * start,SkOpSpanBase * end)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 
tail()387     const SkOpSpanBase* tail() const {
388         return &fTail;
389     }
390 
tail()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 
verb()408     SkPath::Verb verb() const {
409         return fVerb;
410     }
411 
412     // look for two different spans that point to the same opposite segment
visited()413     bool visited() {
414         if (!fVisited) {
415             fVisited = true;
416             return false;
417         }
418         return true;
419     }
420 
weight()421     SkScalar weight() const {
422         return fWeight;
423     }
424 
425     SkOpSpan* windingSpanAtT(double tHit);
426     int windSum(const SkOpAngle* angle) const;
427 
428 private:
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