Home | History | Annotate | Download | only in pathops 
      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 
     17 class SkPathWriter;
     18 
     19 class SkOpSegment {
     20 public:
     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     double t(int tIndex) const {
    187         return fTs[tIndex].fT;
    188     }
    189 
    190     double tAtMid(int start, int end, double mid) const {
    191         return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
    192     }
    193 
    194     bool unsortable(int index) const {
    195         return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
    196     }
    197 
    198     void updatePts(const SkPoint pts[]) {
    199         fPts = pts;
    200     }
    201 
    202     SkPath::Verb verb() const {
    203         return fVerb;
    204     }
    205 
    206     int windSum(int tIndex) const {
    207         return fTs[tIndex].fWindSum;
    208     }
    209 
    210     int windValue(int tIndex) const {
    211         return fTs[tIndex].fWindValue;
    212     }
    213 
    214 #if defined(SK_DEBUG) || DEBUG_WINDING
    215     SkScalar xAtT(int index) const {
    216         return xAtT(&fTs[index]);
    217     }
    218 #endif
    219 
    220     const SkPoint& xyAtT(const SkOpSpan* span) const {
    221         return span->fPt;
    222     }
    223 
    224     const SkPoint& xyAtT(int index) const {
    225         return xyAtT(&fTs[index]);
    226     }
    227 
    228 #if defined(SK_DEBUG) || DEBUG_WINDING
    229     SkScalar yAtT(int index) const {
    230         return yAtT(&fTs[index]);
    231     }
    232 #endif
    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 activeWinding(int index, int endIndex);
    238     void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
    239     void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
    240     void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
    241     void addOtherT(int index, double otherT, int otherIndex);
    242     void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
    243     int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
    244     int addT(SkOpSegment* other, const SkPoint& pt, double newT);
    245     void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
    246     void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
    247             SkOpSegment* other);
    248     void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
    249     bool betweenTs(int lesser, double testT, int greater) const;
    250     void checkEnds();
    251     bool checkSmall(int index) const;
    252     void checkTiny();
    253     int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
    254                     SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
    255     int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
    256                      double mid, bool opp, bool current) const;
    257     bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,
    258                              int step, SkPoint* startPt, SkPoint* endPt, double* endT) const;
    259     SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
    260                             bool* unsortable, SkPathOp op, const int xorMiMask,
    261                             const int xorSuMask);
    262     SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
    263                                  bool* unsortable);
    264     SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
    265     int findT(double t, const SkOpSegment* ) const;
    266     SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
    267     void fixOtherTIndex();
    268     void initWinding(int start, int end);
    269     void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
    270                      SkScalar hitOppDx);
    271     bool isMissing(double startT, const SkPoint& pt) const;
    272     bool isTiny(const SkOpAngle* angle) const;
    273     bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);
    274     SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
    275     SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
    276     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
    277     SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding,
    278                         const SkOpAngle* angle);
    279     void markDone(int index, int winding);
    280     void markDoneBinary(int index);
    281     void markDoneUnary(int index);
    282     bool nextCandidate(int* start, int* end) const;
    283     int nextSpan(int from, int step) const;
    284     void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
    285             int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
    286     enum SortAngleKind {
    287         kMustBeOrdered_SortAngleKind, // required for winding calc
    288         kMayBeUnordered_SortAngleKind // ok for find top
    289     };
    290     static bool SortAngles(const SkTArray<SkOpAngle, true>& angles,  // FIXME: replace with
    291                            SkTArray<SkOpAngle*, true>* angleList,    //  Sort Angles 2
    292                            SortAngleKind );
    293     static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
    294                             SkTArray<SkOpAngle*, true>* angleList);
    295     bool subDivide(int start, int end, SkPoint edge[4]) const;
    296     bool subDivide(int start, int end, SkDCubic* result) const;
    297     void undoneSpan(int* start, int* end);
    298     int updateOppWindingReverse(const SkOpAngle* angle) const;
    299     int updateWindingReverse(const SkOpAngle* angle) const;
    300     static bool UseInnerWinding(int outerWinding, int innerWinding);
    301     int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
    302     int windSum(const SkOpAngle* angle) const;
    303 
    304 #ifdef SK_DEBUG
    305     int debugID() const {
    306         return fID;
    307     }
    308 #endif
    309 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
    310     void debugShowActiveSpans() const;
    311 #endif
    312 #if DEBUG_SORT || DEBUG_SWAP_TOP
    313     void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
    314             const int contourWinding, const int oppContourWinding, bool sortable) const;
    315     void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first,
    316             bool sortable);
    317 #endif
    318 #if DEBUG_CONCIDENT
    319     void debugShowTs(const char* prefix) const;
    320 #endif
    321 #if DEBUG_SHOW_WINDING
    322     int debugShowWindingValues(int slotCount, int ofInterest) const;
    323 #endif
    324 
    325 private:
    326     struct MissingSpan  {
    327         double fT;
    328         double fEndT;
    329         SkOpSegment* fSegment;
    330         SkOpSegment* fOther;
    331         double fOtherT;
    332         SkPoint fPt;
    333     };
    334 
    335     bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
    336     bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
    337     bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
    338                   int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
    339                   int* oppMaxWinding, int* oppSumWinding);
    340     bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
    341     void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
    342     void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
    343     void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
    344     void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
    345                   const SkPoint& oPt);
    346     void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
    347     bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
    348     bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
    349     void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
    350     void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
    351                            SkTArray<SkPoint, true>* outsideTs);
    352     void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
    353                            SkTArray<SkPoint, true>* outsideTs);
    354     bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
    355     bool clockwise(int tStart, int tEnd) const;
    356     static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
    357                               SkOpAngle::IncludeType );
    358     static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
    359                                      SkOpAngle::IncludeType );
    360     bool decrementSpan(SkOpSpan* span);
    361     int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
    362     void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
    363     bool isSimple(int end) const;
    364     bool isTiny(int index) const;
    365     void matchWindingValue(int tIndex, double t, bool borrowWind);
    366     SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
    367     SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
    368     SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding);
    369     SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding);
    370     SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle);
    371     void markDoneBinary(int index, int winding, int oppWinding);
    372     SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding);
    373     void markOneDone(const char* funName, int tIndex, int winding);
    374     void markOneDoneBinary(const char* funName, int tIndex);
    375     void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
    376     void markOneDoneUnary(const char* funName, int tIndex);
    377     SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
    378     SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
    379     void markWinding(int index, int winding);
    380     void markWinding(int index, int winding, int oppWinding);
    381     void markUnsortable(int start, int end);
    382     bool monotonicInY(int tStart, int tEnd) const;
    383     bool multipleSpans(int end) const;
    384     SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
    385     int nextExactSpan(int from, int step) const;
    386     bool serpentine(int tStart, int tEnd) const;
    387     void setUpWindings(int index, int endIndex, int* sumMiWinding,
    388             int* maxWinding, int* sumWinding);
    389     void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
    390     static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt,
    391             const SkPoint& startPt);
    392     static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt);
    393     int updateOppWinding(int index, int endIndex) const;
    394     int updateOppWinding(const SkOpAngle* angle) const;
    395     int updateWinding(int index, int endIndex) const;
    396     int updateWinding(const SkOpAngle* angle) const;
    397     int updateWindingReverse(int index, int endIndex) const;
    398     static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
    399     SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
    400     SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
    401 
    402     SkScalar xAtT(const SkOpSpan* span) const {
    403         return xyAtT(span).fX;
    404     }
    405 
    406     SkScalar yAtT(const SkOpSpan* span) const {
    407         return xyAtT(span).fY;
    408     }
    409 
    410     void zeroSpan(SkOpSpan* span);
    411 
    412 #if DEBUG_SWAP_TOP
    413     bool controlsContainedByEnds(int tStart, int tEnd) const;
    414 #endif
    415 #if DEBUG_CONCIDENT
    416      void debugAddTPair(double t, const SkOpSegment& other, double otherT) const;
    417 #endif
    418 #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
    419     void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
    420     void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
    421 #endif
    422 #if DEBUG_WINDING
    423     static char as_digit(int value) {
    424         return value < 0 ? '?' : value <= 9 ? '0' + value : '+';
    425     }
    426 #endif
    427     void debugValidate() const;
    428 #ifdef SK_DEBUG
    429     void dumpPts() const;
    430     void dumpDPts() const;
    431     void dumpSpans() const;
    432 #endif
    433 
    434     const SkPoint* fPts;
    435     SkPathOpsBounds fBounds;
    436     // FIXME: can't convert to SkTArray because it uses insert
    437     SkTDArray<SkOpSpan> fTs;  // two or more (always includes t=0 t=1)
    438     // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
    439     int fDoneSpans;  // quick check that segment is finished
    440     // OPTIMIZATION: force the following to be byte-sized
    441     SkPath::Verb fVerb;
    442     bool fOperand;
    443     bool fXor;  // set if original contour had even-odd fill
    444     bool fOppXor;  // set if opposite operand had even-odd fill
    445 #ifdef SK_DEBUG
    446     int fID;
    447 #endif
    448 };
    449 
    450 #endif
    451