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 "SkPathOpsBounds.h"
13#include "SkPathOpsCurve.h"
14#include "SkTArray.h"
15#include "SkTDArray.h"
16
17class SkPathWriter;
18
19class SkOpSegment {
20public:
21    SkOpSegment() {
22#if DEBUG_DUMP
23        fID = ++gSegmentID;
24#endif
25    }
26
27    bool operator<(const SkOpSegment& rh) const {
28        return fBounds.fTop < rh.fBounds.fTop;
29    }
30
31    const SkPathOpsBounds& bounds() const {
32        return fBounds;
33    }
34
35    // OPTIMIZE
36    // when the edges are initially walked, they don't automatically get the prior and next
37    // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
38    // and would additionally remove the need for similar checks in condition edges. It would
39    // also allow intersection code to assume end of segment intersections (maybe?)
40    bool complete() const {
41        int count = fTs.count();
42        return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
43    }
44
45    int count() const {
46        return fTs.count();
47    }
48
49    bool done() const {
50        SkASSERT(fDoneSpans <= fTs.count());
51        return fDoneSpans == fTs.count();
52    }
53
54    bool done(int min) const {
55        return fTs[min].fDone;
56    }
57
58    bool done(const SkOpAngle* angle) const {
59        return done(SkMin32(angle->start(), angle->end()));
60    }
61
62    SkVector dxdy(int index) const {
63        return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT);
64    }
65
66    SkScalar dy(int index) const {
67        return dxdy(index).fY;
68    }
69
70    bool intersected() const {
71        return fTs.count() > 0;
72    }
73
74    bool isCanceled(int tIndex) const {
75        return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
76    }
77
78    bool isConnected(int startIndex, int endIndex) const {
79        return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32;
80    }
81
82    bool isHorizontal() const {
83        return fBounds.fTop == fBounds.fBottom;
84    }
85
86    bool isVertical() const {
87        return fBounds.fLeft == fBounds.fRight;
88    }
89
90    bool isVertical(int start, int end) const {
91        return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end);
92    }
93
94    bool operand() const {
95        return fOperand;
96    }
97
98    int oppSign(const SkOpAngle* angle) const {
99        SkASSERT(angle->segment() == this);
100        return oppSign(angle->start(), angle->end());
101    }
102
103    int oppSign(int startIndex, int endIndex) const {
104        int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue;
105#if DEBUG_WIND_BUMP
106        SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
107#endif
108        return result;
109    }
110
111    int oppSum(int tIndex) const {
112        return fTs[tIndex].fOppSum;
113    }
114
115    int oppSum(const SkOpAngle* angle) const {
116        int lesser = SkMin32(angle->start(), angle->end());
117        return fTs[lesser].fOppSum;
118    }
119
120    int oppValue(int tIndex) const {
121        return fTs[tIndex].fOppValue;
122    }
123
124    int oppValue(const SkOpAngle* angle) const {
125        int lesser = SkMin32(angle->start(), angle->end());
126        return fTs[lesser].fOppValue;
127    }
128
129    const SkOpSegment* other(int index) const {
130        return fTs[index].fOther;
131    }
132
133    // was used only by right angle winding finding
134    SkPoint ptAtT(double mid) const {
135        return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
136    }
137
138    const SkPoint* pts() const {
139        return fPts;
140    }
141
142    void reset() {
143        init(NULL, (SkPath::Verb) -1, false, false);
144        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
145        fTs.reset();
146    }
147
148    void setOppXor(bool isOppXor) {
149        fOppXor = isOppXor;
150    }
151
152    void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
153        int deltaSum = spanSign(index, endIndex);
154        *maxWinding = *sumWinding;
155        *sumWinding -= deltaSum;
156    }
157
158    // OPTIMIZATION: mark as debugging only if used solely by tests
159    const SkOpSpan& span(int tIndex) const {
160        return fTs[tIndex];
161    }
162
163    // OPTIMIZATION: mark as debugging only if used solely by tests
164    const SkTDArray<SkOpSpan>& spans() const {
165        return fTs;
166    }
167
168    int spanSign(const SkOpAngle* angle) const {
169        SkASSERT(angle->segment() == this);
170        return spanSign(angle->start(), angle->end());
171    }
172
173    int spanSign(int startIndex, int endIndex) const {
174        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue;
175#if DEBUG_WIND_BUMP
176        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
177#endif
178        return result;
179    }
180
181    // OPTIMIZATION: mark as debugging only if used solely by tests
182    double t(int tIndex) const {
183        return fTs[tIndex].fT;
184    }
185
186    double tAtMid(int start, int end, double mid) const {
187        return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
188    }
189
190    bool unsortable(int index) const {
191        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
192    }
193
194    void updatePts(const SkPoint pts[]) {
195        fPts = pts;
196    }
197
198    SkPath::Verb verb() const {
199        return fVerb;
200    }
201
202    int windSum(int tIndex) const {
203        return fTs[tIndex].fWindSum;
204    }
205
206    int windValue(int tIndex) const {
207        return fTs[tIndex].fWindValue;
208    }
209
210    SkScalar xAtT(int index) const {
211        return xAtT(&fTs[index]);
212    }
213
214    SkScalar xAtT(const SkOpSpan* span) const {
215        return xyAtT(span).fX;
216    }
217
218    const SkPoint& xyAtT(const SkOpSpan* span) const {
219        return span->fPt;
220    }
221
222    const SkPoint& xyAtT(int index) const {
223        return xyAtT(&fTs[index]);
224    }
225
226    SkScalar yAtT(int index) const {
227        return yAtT(&fTs[index]);
228    }
229
230    SkScalar yAtT(const SkOpSpan* span) const {
231        return xyAtT(span).fY;
232    }
233
234    bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
235    SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
236    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
237    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
238                  int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
239                  int* oppMaxWinding, int* oppSumWinding);
240    bool activeWinding(int index, int endIndex);
241    bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
242    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
243    void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
244    void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
245    void addOtherT(int index, double otherT, int otherIndex);
246    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
247    int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
248    int addT(SkOpSegment* other, const SkPoint& pt, double newT);
249    void addTCancel(double startT, double endT, SkOpSegment* other, double oStartT, double oEndT);
250    void addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT,
251                        double oEndT);
252    void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
253    void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
254                  const SkPoint& oPt);
255    int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT);
256    bool betweenTs(int lesser, double testT, int greater) const;
257    void checkEnds();
258    int computeSum(int startIndex, int endIndex, bool binary);
259    int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
260                     double mid, bool opp, bool current) const;
261    SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
262                            bool* unsortable, SkPathOp op, const int xorMiMask,
263                            const int xorSuMask);
264    SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
265                                 bool* unsortable);
266    SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
267    void findTooCloseToCall();
268    SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
269    void fixOtherTIndex();
270    void initWinding(int start, int end);
271    void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
272            SkScalar hitOppDx);
273    bool isLinear(int start, int end) const;
274    bool isMissing(double startT) const;
275    bool isSimple(int end) const;
276    bool isTiny(const SkOpAngle* angle) const;
277    bool isTiny(int index) const;
278    SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
279    SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
280    SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
281    SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
282                        bool activeAngle, const SkOpAngle* angle);
283    void markDone(int index, int winding);
284    void markDoneBinary(int index);
285    void markDoneUnary(int index);
286    SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
287    SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
288    void markWinding(int index, int winding);
289    void markWinding(int index, int winding, int oppWinding);
290    bool nextCandidate(int* start, int* end) const;
291    int nextExactSpan(int from, int step) const;
292    int nextSpan(int from, int step) const;
293    void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
294            int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
295    enum SortAngleKind {
296        kMustBeOrdered_SortAngleKind, // required for winding calc
297        kMayBeUnordered_SortAngleKind // ok for find top
298    };
299    static bool SortAngles(const SkTArray<SkOpAngle, true>& angles,
300                           SkTArray<SkOpAngle*, true>* angleList,
301                           SortAngleKind );
302    bool subDivide(int start, int end, SkPoint edge[4]) const;
303    bool subDivide(int start, int end, SkDCubic* result) const;
304    void undoneSpan(int* start, int* end);
305    int updateOppWindingReverse(const SkOpAngle* angle) const;
306    int updateWindingReverse(const SkOpAngle* angle) const;
307    static bool UseInnerWinding(int outerWinding, int innerWinding);
308    int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
309    int windSum(const SkOpAngle* angle) const;
310    int windValue(const SkOpAngle* angle) const;
311
312#if DEBUG_DUMP
313    int debugID() const {
314        return fID;
315    }
316#endif
317#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
318    void debugShowActiveSpans() const;
319#endif
320#if DEBUG_SORT || DEBUG_SWAP_TOP
321    void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
322            const int contourWinding, const int oppContourWinding, bool sortable) const;
323    void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
324            bool sortable);
325#endif
326#if DEBUG_CONCIDENT
327    void debugShowTs() const;
328#endif
329#if DEBUG_SHOW_WINDING
330    int debugShowWindingValues(int slotCount, int ofInterest) const;
331#endif
332
333private:
334    bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
335    bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
336    void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
337    void addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd);
338    void addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other, double oEnd);
339    void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
340    int advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex);
341    int advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index);
342    void buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
343    void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
344    int bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index,
345                           SkTArray<double, true>* outsideTs);
346    int bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex,
347                            SkTArray<double, true>* oOutsideTs);
348    bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
349    bool clockwise(int tStart, int tEnd) const;
350    void decrementSpan(SkOpSpan* span);
351    bool equalPoints(int greaterTIndex, int lesserTIndex);
352    int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
353    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
354    void matchWindingValue(int tIndex, double t, bool borrowWind);
355    SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
356    SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
357    SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
358    SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
359    SkOpSpan* markAngle(int maxWinding, int sumWinding, bool activeAngle, const SkOpAngle* angle);
360    void markDoneBinary(int index, int winding, int oppWinding);
361    SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
362    void markOneDone(const char* funName, int tIndex, int winding);
363    void markOneDoneBinary(const char* funName, int tIndex);
364    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
365    void markOneDoneUnary(const char* funName, int tIndex);
366    void markUnsortable(int start, int end);
367    bool monotonicInY(int tStart, int tEnd) const;
368    bool multipleSpans(int end) const;
369    SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
370    bool serpentine(int tStart, int tEnd) const;
371    void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
372    static void TrackOutside(SkTArray<double, true>* outsideTs, double end, double start);
373    int updateOppWinding(int index, int endIndex) const;
374    int updateOppWinding(const SkOpAngle* angle) const;
375    int updateWinding(int index, int endIndex) const;
376    int updateWinding(const SkOpAngle* angle) const;
377    SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
378    SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
379    int windValueAt(double t) const;
380    void zeroSpan(SkOpSpan* span);
381
382#if DEBUG_SWAP_TOP
383    bool controlsContainedByEnds(int tStart, int tEnd) const;
384#endif
385#if DEBUG_CONCIDENT
386     void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
387#endif
388#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
389    void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
390    void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
391#endif
392#if DEBUG_WINDING
393    static char as_digit(int value) {
394        return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
395    }
396#endif
397    void debugValidate() const;
398
399    const SkPoint* fPts;
400    SkPathOpsBounds fBounds;
401    // FIXME: can't convert to SkTArray because it uses insert
402    SkTDArray<SkOpSpan> fTs;  // two or more (always includes t=0 t=1)
403    // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
404    int fDoneSpans;  // quick check that segment is finished
405    // OPTIMIZATION: force the following to be byte-sized
406    SkPath::Verb fVerb;
407    bool fOperand;
408    bool fXor;  // set if original contour had even-odd fill
409    bool fOppXor;  // set if opposite operand had even-odd fill
410#if DEBUG_DUMP
411    int fID;
412#endif
413};
414
415#endif
416