SkOpSegment.h revision 7eaa53d8f7e48fd17d02b5e3bd91f90e9c1899ef 
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#ifdef SK_DEBUG
23        fID = ++SkPathOpsDebug::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    // used only by partial coincidence detection
63    SkDPoint dPtAtT(double mid) const {
64        return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
65    }
66
67    SkVector dxdy(int index) const {
68        return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT);
69    }
70
71    SkScalar dy(int index) const {
72        return dxdy(index).fY;
73    }
74
75    bool intersected() const {
76        return fTs.count() > 0;
77    }
78
79    bool isCanceled(int tIndex) const {
80        return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0;
81    }
82
83    bool isConnected(int startIndex, int endIndex) const {
84        return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32;
85    }
86
87    bool isHorizontal() const {
88        return fBounds.fTop == fBounds.fBottom;
89    }
90
91    bool isVertical() const {
92        return fBounds.fLeft == fBounds.fRight;
93    }
94
95    bool isVertical(int start, int end) const {
96        return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end);
97    }
98
99    bool operand() const {
100        return fOperand;
101    }
102
103    int oppSign(const SkOpAngle* angle) const {
104        SkASSERT(angle->segment() == this);
105        return oppSign(angle->start(), angle->end());
106    }
107
108    int oppSign(int startIndex, int endIndex) const {
109        int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue;
110#if DEBUG_WIND_BUMP
111        SkDebugf("%s oppSign=%d\n", __FUNCTION__, result);
112#endif
113        return result;
114    }
115
116    int oppSum(int tIndex) const {
117        return fTs[tIndex].fOppSum;
118    }
119
120    int oppSum(const SkOpAngle* angle) const {
121        int lesser = SkMin32(angle->start(), angle->end());
122        return fTs[lesser].fOppSum;
123    }
124
125    int oppValue(int tIndex) const {
126        return fTs[tIndex].fOppValue;
127    }
128
129    int oppValue(const SkOpAngle* angle) const {
130        int lesser = SkMin32(angle->start(), angle->end());
131        return fTs[lesser].fOppValue;
132    }
133
134    const SkOpSegment* other(int index) const {
135        return fTs[index].fOther;
136    }
137
138    // was used only by right angle winding finding
139    SkPoint ptAtT(double mid) const {
140        return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
141    }
142
143    const SkPoint* pts() const {
144        return fPts;
145    }
146
147    void reset() {
148        init(NULL, (SkPath::Verb) -1, false, false);
149        fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
150        fTs.reset();
151    }
152
153    void setOppXor(bool isOppXor) {
154        fOppXor = isOppXor;
155    }
156
157    void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
158        int deltaSum = spanSign(index, endIndex);
159        *maxWinding = *sumWinding;
160        *sumWinding -= deltaSum;
161    }
162
163    // OPTIMIZATION: mark as debugging only if used solely by tests
164    const SkOpSpan& span(int tIndex) const {
165        return fTs[tIndex];
166    }
167
168    // OPTIMIZATION: mark as debugging only if used solely by tests
169    const SkTDArray<SkOpSpan>& spans() const {
170        return fTs;
171    }
172
173    int spanSign(const SkOpAngle* angle) const {
174        SkASSERT(angle->segment() == this);
175        return spanSign(angle->start(), angle->end());
176    }
177
178    int spanSign(int startIndex, int endIndex) const {
179        int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue;
180#if DEBUG_WIND_BUMP
181        SkDebugf("%s spanSign=%d\n", __FUNCTION__, result);
182#endif
183        return result;
184    }
185
186    // OPTIMIZATION: mark as debugging only if used solely by tests
187    double t(int tIndex) const {
188        return fTs[tIndex].fT;
189    }
190
191    double tAtMid(int start, int end, double mid) const {
192        return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
193    }
194
195    bool unsortable(int index) const {
196        return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
197    }
198
199    void updatePts(const SkPoint pts[]) {
200        fPts = pts;
201    }
202
203    SkPath::Verb verb() const {
204        return fVerb;
205    }
206
207    int windSum(int tIndex) const {
208        return fTs[tIndex].fWindSum;
209    }
210
211    int windValue(int tIndex) const {
212        return fTs[tIndex].fWindValue;
213    }
214
215    SkScalar xAtT(int index) const {
216        return xAtT(&fTs[index]);
217    }
218
219    SkScalar xAtT(const SkOpSpan* span) const {
220        return xyAtT(span).fX;
221    }
222
223    const SkPoint& xyAtT(const SkOpSpan* span) const {
224        return span->fPt;
225    }
226
227    const SkPoint& xyAtT(int index) const {
228        return xyAtT(&fTs[index]);
229    }
230
231    SkScalar yAtT(int index) const {
232        return yAtT(&fTs[index]);
233    }
234
235    SkScalar yAtT(const SkOpSpan* span) const {
236        return xyAtT(span).fY;
237    }
238
239    bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
240    SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
241    bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
242    bool activeWinding(int index, int endIndex);
243    void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
244    void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
245    void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
246    void addOtherT(int index, double otherT, int otherIndex);
247    void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
248    int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
249    int addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear);
250    void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
251    void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
252            SkOpSegment* other);
253    void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
254    bool betweenTs(int lesser, double testT, int greater) const;
255    void checkEnds();
256    bool checkSmall(int index) const;
257    void checkTiny();
258    int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
259                    SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
260    int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
261                     double mid, bool opp, bool current) const;
262    SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
263                            bool* unsortable, SkPathOp op, const int xorMiMask,
264                            const int xorSuMask);
265    SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
266                                 bool* unsortable);
267    SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
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 isMissing(double startT, const SkPoint& pt) const;
274    bool isTiny(const SkOpAngle* angle) const;
275    SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
276    SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
277    SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
278    SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
279                        bool activeAngle, const SkOpAngle* angle);
280    void markDone(int index, int winding);
281    void markDoneBinary(int index);
282    void markDoneUnary(int index);
283    bool nextCandidate(int* start, int* end) const;
284    int nextSpan(int from, int step) const;
285    void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
286            int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
287    enum SortAngleKind {
288        kMustBeOrdered_SortAngleKind, // required for winding calc
289        kMayBeUnordered_SortAngleKind // ok for find top
290    };
291    static bool SortAngles(const SkTArray<SkOpAngle, true>& angles,  // FIXME: replace with
292                           SkTArray<SkOpAngle*, true>* angleList,    //  Sort Angles 2
293                           SortAngleKind );
294    static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
295                            SkTArray<SkOpAngle*, true>* angleList);
296    bool subDivide(int start, int end, SkPoint edge[4]) const;
297    bool subDivide(int start, int end, SkDCubic* result) const;
298    void undoneSpan(int* start, int* end);
299    int updateOppWindingReverse(const SkOpAngle* angle) const;
300    int updateWindingReverse(const SkOpAngle* angle) const;
301    static bool UseInnerWinding(int outerWinding, int innerWinding);
302    int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
303    int windSum(const SkOpAngle* angle) const;
304
305#ifdef SK_DEBUG
306    int debugID() const {
307        return fID;
308    }
309#endif
310#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
311    void debugShowActiveSpans() const;
312#endif
313#if DEBUG_SORT || DEBUG_SWAP_TOP
314    void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
315            const int contourWinding, const int oppContourWinding, bool sortable) const;
316    void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
317            bool sortable);
318#endif
319#if DEBUG_CONCIDENT
320    void debugShowTs(const char* prefix) const;
321#endif
322#if DEBUG_SHOW_WINDING
323    int debugShowWindingValues(int slotCount, int ofInterest) const;
324#endif
325
326private:
327    struct MissingSpan  {
328        enum Command {
329            kNoAction,
330            kAddMissing,
331            kRemoveNear,
332            kZeroSpan,
333        } fCommand;
334        double fT;
335        double fEndT;
336        SkOpSegment* fSegment;
337        SkOpSegment* fOther;
338        double fOtherT;
339        SkPoint fPt;
340    };
341
342    bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
343    bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
344    bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
345                  int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
346                  int* oppMaxWinding, int* oppSumWinding);
347    bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
348    void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
349    void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
350    void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
351    void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
352                  const SkPoint& oPt);
353    void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
354    void adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt,
355                           SkTArray<MissingSpan, true>* );
356    void adjustNear(double startT, const SkPoint& endPt, SkTArray<MissingSpan, true>* );
357    void adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
358                         SkTArray<MissingSpan, true>* );
359    MissingSpan::Command adjustThisNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
360                                        SkTArray<MissingSpan, true>* );
361    int advanceCoincidentOther(double oEndT, int oIndex);
362    int advanceCoincidentThis(int index);
363    bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
364    bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
365    void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
366    void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
367                           SkTArray<SkPoint, true>* outsideTs);
368    bool bumpCoincident(SkOpSpan* test, bool bigger, bool binary);
369    void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
370                           SkTArray<SkPoint, true>* outsideTs);
371    bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
372    bool clockwise(int tStart, int tEnd) const;
373    static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
374                              SkOpAngle::IncludeType );
375    static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
376                                     SkOpAngle::IncludeType );
377    bool decrementSpan(SkOpSpan* span);
378    int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
379    void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
380    bool isSimple(int end) const;
381    bool isTiny(int index) const;
382    void matchWindingValue(int tIndex, double t, bool borrowWind);
383    SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
384    SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
385    SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
386    SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
387    SkOpSpan* markAngle(int maxWinding, int sumWinding, bool activeAngle, const SkOpAngle* angle);
388    void markDoneBinary(int index, int winding, int oppWinding);
389    SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
390    void markOneDone(const char* funName, int tIndex, int winding);
391    void markOneDoneBinary(const char* funName, int tIndex);
392    void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
393    void markOneDoneUnary(const char* funName, int tIndex);
394    SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
395    SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
396    void markWinding(int index, int winding);
397    void markWinding(int index, int winding, int oppWinding);
398    void markUnsortable(int start, int end);
399    bool monotonicInY(int tStart, int tEnd) const;
400    double missingNear(double otherT, const SkOpSegment* other, const SkPoint& startPt,
401                     const SkPoint& endPt) const;
402    bool multipleSpans(int end) const;
403    SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
404    int nextExactSpan(int from, int step) const;
405    bool serpentine(int tStart, int tEnd) const;
406    void setUpWindings(int index, int endIndex, int* sumMiWinding,
407            int* maxWinding, int* sumWinding);
408    void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
409    static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt,
410            const SkPoint& startPt);
411    static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt);
412    int updateOppWinding(int index, int endIndex) const;
413    int updateOppWinding(const SkOpAngle* angle) const;
414    int updateWinding(int index, int endIndex) const;
415    int updateWinding(const SkOpAngle* angle) const;
416    int updateWindingReverse(int index, int endIndex) const;
417    static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
418    SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
419    SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
420    int windValue(const SkOpAngle* angle) const;
421    int windValueAt(double t) const;
422    void zeroSpan(SkOpSpan* span);
423
424#if DEBUG_SWAP_TOP
425    bool controlsContainedByEnds(int tStart, int tEnd) const;
426#endif
427#if DEBUG_CONCIDENT
428     void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
429#endif
430#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
431    void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
432    void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
433#endif
434#if DEBUG_WINDING
435    static char as_digit(int value) {
436        return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
437    }
438#endif
439    void debugValidate() const;
440#ifdef SK_DEBUG
441    void dumpPts() const;
442    void dumpDPts() const;
443    void dumpSpans() const;
444#endif
445
446    const SkPoint* fPts;
447    SkPathOpsBounds fBounds;
448    // FIXME: can't convert to SkTArray because it uses insert
449    SkTDArray<SkOpSpan> fTs;  // two or more (always includes t=0 t=1)
450    // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
451    int fDoneSpans;  // quick check that segment is finished
452    // OPTIMIZATION: force the following to be byte-sized
453    SkPath::Verb fVerb;
454    bool fOperand;
455    bool fXor;  // set if original contour had even-odd fill
456    bool fOppXor;  // set if opposite operand had even-odd fill
457#ifdef SK_DEBUG
458    int fID;
459#endif
460};
461
462#endif
463