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 "SkOpTAllocator.h"
     13 #include "SkPathOpsBounds.h"
     14 #include "SkPathOpsCubic.h"
     15 #include "SkPathOpsCurve.h"
     16 
     17 struct SkDCurve;
     18 class SkOpCoincidence;
     19 class SkOpContour;
     20 enum class SkOpRayDir;
     21 struct SkOpRayHit;
     22 class SkPathWriter;
     23 
     24 class SkOpSegment {
     25 public:
     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 
    408 private:
    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