src/third_party/skia/src/pathops/SkOpContour.h

   1 /*
   2  * Copyright 2013 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 SkOpContour_DEFINED
   8 #define SkOpContour_DEFINED
   9
  10 #include "SkOpSegment.h"
  11 #include "SkTArray.h"
  12
  13 class SkIntersections;
  14 class SkOpContour;
  15 class SkPathWriter;
  16
  17 struct SkCoincidence {
  18     SkOpContour* fOther;
  19     int fSegments[2];
  20     double fTs[2][2];
  21     SkPoint fPts[2];
  22 };
  23
  24 class SkOpContour {
  25 public:
  26     SkOpContour() {
  27         reset();
  28 #ifdef SK_DEBUG
  29         fID = ++SkPathOpsDebug::gContourID;
  30 #endif
  31     }
  32
  33     bool operator<(const SkOpContour& rh) const {
  34         return fBounds.fTop == rh.fBounds.fTop
  35                 ? fBounds.fLeft < rh.fBounds.fLeft
  36                 : fBounds.fTop < rh.fBounds.fTop;
  37     }
  38
  39     bool addCoincident(int index, SkOpContour* other, int otherIndex,
  40                        const SkIntersections& ts, bool swap);
  41     void addCoincidentPoints();
  42
  43     void addCross(const SkOpContour* crosser) {
  44 #ifdef DEBUG_CROSS
  45         for (int index = 0; index < fCrosses.count(); ++index) {
  46             SkASSERT(fCrosses[index] != crosser);
  47         }
  48 #endif
  49         fCrosses.push_back(crosser);
  50     }
  51
  52     void addCubic(const SkPoint pts[4]) {
  53         fSegments.push_back().addCubic(pts, fOperand, fXor);
  54         fContainsCurves = fContainsCubics = true;
  55     }
  56
  57     int addLine(const SkPoint pts[2]) {
  58         fSegments.push_back().addLine(pts, fOperand, fXor);
  59         return fSegments.count();
  60     }
  61
  62     void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
  63         fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
  64     }
  65
  66     bool addPartialCoincident(int index, SkOpContour* other, int otherIndex,
  67                        const SkIntersections& ts, int ptIndex, bool swap);
  68
  69     int addQuad(const SkPoint pts[3]) {
  70         fSegments.push_back().addQuad(pts, fOperand, fXor);
  71         fContainsCurves = true;
  72         return fSegments.count();
  73     }
  74
  75     int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT,
  76             bool isNear) {
  77         setContainsIntercepts();
  78         return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT, isNear);
  79     }
  80
  81     int addSelfT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
  82         setContainsIntercepts();
  83         return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT);
  84     }
  85
  86     const SkPathOpsBounds& bounds() const {
  87         return fBounds;
  88     }
  89
  90     void calcCoincidentWinding();
  91     void calcPartialCoincidentWinding();
  92
  93     void checkEnds() {
  94         if (!fContainsCurves) {
  95             return;
  96         }
  97         int segmentCount = fSegments.count();
  98         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
  99             SkOpSegment* segment = &fSegments[sIndex];
 100             if (segment->verb() == SkPath::kLine_Verb) {
 101                 continue;
 102             }
 103             if (segment->done()) {
 104                 continue;   // likely coincident, nothing to do
 105             }
 106             segment->checkEnds();
 107         }
 108     }
 109
 110     // if same point has different T values, choose a common T
 111     void checkTiny() {
 112         int segmentCount = fSegments.count();
 113         if (segmentCount <= 2) {
 114             return;
 115         }
 116         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 117             fSegments[sIndex].checkTiny();
 118         }
 119     }
 120
 121     void complete() {
 122         setBounds();
 123         fContainsIntercepts = false;
 124     }
 125
 126     bool containsCubics() const {
 127         return fContainsCubics;
 128     }
 129
 130     bool crosses(const SkOpContour* crosser) const {
 131         for (int index = 0; index < fCrosses.count(); ++index) {
 132             if (fCrosses[index] == crosser) {
 133                 return true;
 134             }
 135         }
 136         return false;
 137     }
 138
 139     bool done() const {
 140         return fDone;
 141     }
 142
 143     const SkPoint& end() const {
 144         const SkOpSegment& segment = fSegments.back();
 145         return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
 146     }
 147
 148     void fixOtherTIndex() {
 149         int segmentCount = fSegments.count();
 150         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 151             fSegments[sIndex].fixOtherTIndex();
 152         }
 153     }
 154
 155     void joinCoincidence() {
 156         joinCoincidence(fCoincidences, false);
 157         joinCoincidence(fPartialCoincidences, true);
 158     }
 159
 160     SkOpSegment* nonVerticalSegment(int* start, int* end);
 161
 162     bool operand() const {
 163         return fOperand;
 164     }
 165
 166     void reset() {
 167         fSegments.reset();
 168         fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
 169         fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false;
 170     }
 171
 172     SkTArray<SkOpSegment>& segments() {
 173         return fSegments;
 174     }
 175
 176     void setContainsIntercepts() {
 177         fContainsIntercepts = true;
 178     }
 179
 180     void setOperand(bool isOp) {
 181         fOperand = isOp;
 182     }
 183
 184     void setOppXor(bool isOppXor) {
 185         fOppXor = isOppXor;
 186         int segmentCount = fSegments.count();
 187         for (int test = 0; test < segmentCount; ++test) {
 188             fSegments[test].setOppXor(isOppXor);
 189         }
 190     }
 191
 192     void setXor(bool isXor) {
 193         fXor = isXor;
 194     }
 195
 196     void sortSegments();
 197
 198     const SkPoint& start() const {
 199         return fSegments.front().pts()[0];
 200     }
 201
 202     void toPath(SkPathWriter* path) const;
 203
 204     void toPartialBackward(SkPathWriter* path) const {
 205         int segmentCount = fSegments.count();
 206         for (int test = segmentCount - 1; test >= 0; --test) {
 207             fSegments[test].addCurveTo(1, 0, path, true);
 208         }
 209     }
 210
 211     void toPartialForward(SkPathWriter* path) const {
 212         int segmentCount = fSegments.count();
 213         for (int test = 0; test < segmentCount; ++test) {
 214             fSegments[test].addCurveTo(0, 1, path, true);
 215         }
 216     }
 217
 218     void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
 219     SkOpSegment* undoneSegment(int* start, int* end);
 220
 221     int updateSegment(int index, const SkPoint* pts) {
 222         SkOpSegment& segment = fSegments[index];
 223         segment.updatePts(pts);
 224         return SkPathOpsVerbToPoints(segment.verb()) + 1;
 225     }
 226
 227 #if DEBUG_TEST
 228     SkTArray<SkOpSegment>& debugSegments() {
 229         return fSegments;
 230     }
 231 #endif
 232
 233 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
 234     void debugShowActiveSpans() {
 235         for (int index = 0; index < fSegments.count(); ++index) {
 236             fSegments[index].debugShowActiveSpans();
 237         }
 238     }
 239 #endif
 240
 241 #if DEBUG_SHOW_WINDING
 242     int debugShowWindingValues(int totalSegments, int ofInterest);
 243     static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList);
 244 #endif
 245
 246 private:
 247     void calcCommonCoincidentWinding(const SkCoincidence& );
 248     void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
 249     void setBounds();
 250
 251     SkTArray<SkOpSegment> fSegments;
 252     SkTArray<SkOpSegment*, true> fSortedSegments;
 253     int fFirstSorted;
 254     SkTArray<SkCoincidence, true> fCoincidences;
 255     SkTArray<SkCoincidence, true> fPartialCoincidences;
 256     SkTArray<const SkOpContour*, true> fCrosses;
 257     SkPathOpsBounds fBounds;
 258     bool fContainsIntercepts;  // FIXME: is this used by anybody?
 259     bool fContainsCubics;
 260     bool fContainsCurves;
 261     bool fDone;
 262     bool fOperand;  // true for the second argument to a binary operator
 263     bool fXor;
 264     bool fOppXor;
 265 #ifdef SK_DEBUG
 266     int fID;
 267 #endif
 268 };
 269
 270 #endif