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