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