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