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
17struct SkDCurve;
18class SkOpCoincidence;
19class SkOpContour;
20enum class SkOpRayDir;
21struct SkOpRayHit;
22class SkPathWriter;
23
24class SkOpSegment {
25public:
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
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
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
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
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
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
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
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
108    const SkPathOpsBounds& bounds() const {
109        return fBounds;
110    }
111
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
124    SkOpContour* contour() const {
125        return fContour;
126    }
127
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
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
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
179    bool done() const {
180        SkASSERT(fDoneCount <= fCount);
181        return fDoneCount == fCount;
182    }
183
184    bool done(const SkOpAngle* angle) const {
185        return angle->start()->starter(angle->end())->done();
186    }
187
188    SkDPoint dPtAtT(double mid) const {
189        return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
190    }
191
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
213    const SkOpSpan* head() const {
214        return &fHead;
215    }
216
217    SkOpSpan* head() {
218        return &fHead;
219    }
220
221    void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
222
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
238    bool isHorizontal() const {
239        return fBounds.fTop == fBounds.fBottom;
240    }
241
242    SkOpSegment* isSimple(SkOpSpanBase** end, int* step) {
243        return nextChase(end, step, nullptr, nullptr);
244    }
245
246    bool isVertical() const {
247        return fBounds.fLeft == fBounds.fRight;
248    }
249
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
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
277    SkOpSegment* next() const {
278        return fNext;
279    }
280
281    SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
282    bool operand() const;
283
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
292    const SkOpSegment* prev() const {
293        return fPrev;
294    }
295
296    SkPoint ptAtT(double mid) const {
297        return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
298    }
299
300    const SkPoint* pts() const {
301        return fPts;
302    }
303
304    bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const {
305        return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt);
306    }
307
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
317    void resetVisited() {
318        fVisited = false;
319    }
320
321    void setContour(SkOpContour* contour) {
322        fContour = contour;
323    }
324
325    void setNext(SkOpSegment* next) {
326        fNext = next;
327    }
328
329    void setPrev(SkOpSegment* prev) {
330        fPrev = prev;
331    }
332
333    void setVisited() {
334        fVisited = true;
335    }
336
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
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
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
363    const SkOpSpanBase* tail() const {
364        return &fTail;
365    }
366
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
384    SkPath::Verb verb() const {
385        return fVerb;
386    }
387
388    // look for two different spans that point to the same opposite segment
389    bool visited() {
390        if (!fVisited) {
391            fVisited = true;
392            return false;
393        }
394        return true;
395    }
396
397    SkScalar weight() const {
398        return fWeight;
399    }
400
401    SkOpSpan* windingSpanAtT(double tHit);
402    int windSum(const SkOpAngle* angle) const;
403
404    SkPoint* writablePt(bool end) {
405        return &fPts[end ? SkPathOpsVerbToPoints(fVerb) : 0];
406    }
407
408private:
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