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    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
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
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
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
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
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
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
98    template<typename T> T* allocateArray(int count) {
99        return SkOpTAllocator<T>::AllocateArray(this->globalState()->allocator(), count);
100    }
101
102    const SkPathOpsBounds& bounds() const {
103        return fBounds;
104    }
105
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
123    SkOpContour* contour() const {
124        return fContour;
125    }
126
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
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
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
193    bool done() const {
194        SkOPASSERT(fDoneCount <= fCount);
195        return fDoneCount == fCount;
196    }
197
198    bool done(const SkOpAngle* angle) const {
199        return angle->start()->starter(angle->end())->done();
200    }
201
202    SkDPoint dPtAtT(double mid) const {
203        return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
204    }
205
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
227    const SkOpSpan* head() const {
228        return &fHead;
229    }
230
231    SkOpSpan* head() {
232        return &fHead;
233    }
234
235    void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
236
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
254    bool isHorizontal() const {
255        return fBounds.fTop == fBounds.fBottom;
256    }
257
258    SkOpSegment* isSimple(SkOpSpanBase** end, int* step) {
259        return nextChase(end, step, nullptr, nullptr);
260    }
261
262    bool isVertical() const {
263        return fBounds.fLeft == fBounds.fRight;
264    }
265
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
272    void joinEnds(SkOpSegment* start) {
273        fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT());
274    }
275
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
297    SkOpSegment* next() const {
298        return fNext;
299    }
300
301    SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const;
302    bool operand() const;
303
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
312    const SkOpSegment* prev() const {
313        return fPrev;
314    }
315
316    SkPoint ptAtT(double mid) const {
317        return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
318    }
319
320    const SkPoint* pts() const {
321        return fPts;
322    }
323
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
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
341    void resetDebugVisited() const {
342        fDebugVisited = false;
343    }
344#endif
345
346    void resetVisited() {
347        fVisited = false;
348    }
349
350    void setContour(SkOpContour* contour) {
351        fContour = contour;
352    }
353
354    void setNext(SkOpSegment* next) {
355        fNext = next;
356    }
357
358    void setPrev(SkOpSegment* prev) {
359        fPrev = prev;
360    }
361
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
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
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
391    const SkOpSpanBase* tail() const {
392        return &fTail;
393    }
394
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
412    SkPath::Verb verb() const {
413        return fVerb;
414    }
415
416    // look for two different spans that point to the same opposite segment
417    bool visited() {
418        if (!fVisited) {
419            fVisited = true;
420            return false;
421        }
422        return true;
423    }
424
425    SkScalar weight() const {
426        return fWeight;
427    }
428
429    SkOpSpan* windingSpanAtT(double tHit);
430    int windSum(const SkOpAngle* angle) const;
431
432private:
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