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 #if defined(SK_DEBUG) || !FORCE_RELEASE
  14 #include "SkThread.h"
  15 #endif
  16
  17 class SkIntersections;
  18 class SkOpContour;
  19 class SkPathWriter;
  20
  21 struct SkCoincidence {
  22     SkOpContour* fOther;
  23     int fSegments[2];
  24     double fTs[2][2];
  25     SkPoint fPts[2][2];
  26     int fNearly[2];
  27 };
  28
  29 class SkOpContour {
  30 public:
  31     SkOpContour() {
  32         reset();
  33 #if defined(SK_DEBUG) || !FORCE_RELEASE
  34         fID = sk_atomic_inc(&SkPathOpsDebug::gContourID);
  35 #endif
  36     }
  37
  38     bool operator<(const SkOpContour& rh) const {
  39         return fBounds.fTop == rh.fBounds.fTop
  40                 ? fBounds.fLeft < rh.fBounds.fLeft
  41                 : fBounds.fTop < rh.fBounds.fTop;
  42     }
  43
  44     bool addCoincident(int index, SkOpContour* other, int otherIndex,
  45                        const SkIntersections& ts, bool swap);
  46     void addCoincidentPoints();
  47
  48     void addCross(const SkOpContour* crosser) {
  49 #ifdef DEBUG_CROSS
  50         for (int index = 0; index < fCrosses.count(); ++index) {
  51             SkASSERT(fCrosses[index] != crosser);
  52         }
  53 #endif
  54         fCrosses.push_back(crosser);
  55     }
  56
  57     void addCubic(const SkPoint pts[4]) {
  58         fSegments.push_back().addCubic(pts, fOperand, fXor);
  59         fContainsCurves = fContainsCubics = true;
  60     }
  61
  62     int addLine(const SkPoint pts[2]) {
  63         fSegments.push_back().addLine(pts, fOperand, fXor);
  64         return fSegments.count();
  65     }
  66
  67     void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
  68         fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
  69     }
  70
  71     bool addPartialCoincident(int index, SkOpContour* other, int otherIndex,
  72                        const SkIntersections& ts, int ptIndex, bool swap);
  73
  74     int addQuad(const SkPoint pts[3]) {
  75         fSegments.push_back().addQuad(pts, fOperand, fXor);
  76         fContainsCurves = true;
  77         return fSegments.count();
  78     }
  79
  80     int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
  81         setContainsIntercepts();
  82         return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
  83     }
  84
  85     int addSelfT(int segIndex, const SkPoint& pt, double newT) {
  86         setContainsIntercepts();
  87         return fSegments[segIndex].addSelfT(pt, newT);
  88     }
  89
  90     void align(const SkOpSegment::AlignedSpan& aligned, bool swap, SkCoincidence* coincidence);
  91     void alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
  92             SkTArray<SkCoincidence, true>* coincidences);
  93
  94     void alignCoincidence(const SkOpSegment::AlignedSpan& aligned) {
  95         alignCoincidence(aligned, &fCoincidences);
  96         alignCoincidence(aligned, &fPartialCoincidences);
  97     }
  98
  99     void alignMultiples(SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
 100         int segmentCount = fSegments.count();
 101         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 102             SkOpSegment& segment = fSegments[sIndex];
 103             if (segment.hasMultiples()) {
 104                 segment.alignMultiples(aligned);
 105             }
 106         }
 107     }
 108
 109     void alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
 110                   bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const;
 111
 112     const SkPathOpsBounds& bounds() const {
 113         return fBounds;
 114     }
 115
 116     bool calcAngles();
 117     bool calcCoincidentWinding();
 118     void calcPartialCoincidentWinding();
 119
 120     void checkDuplicates() {
 121         int segmentCount = fSegments.count();
 122         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 123             SkOpSegment& segment = fSegments[sIndex];
 124             if (segment.count() > 2) {
 125                 segment.checkDuplicates();
 126             }
 127         }
 128     }
 129
 130     void checkEnds() {
 131         if (!fContainsCurves) {
 132             return;
 133         }
 134         int segmentCount = fSegments.count();
 135         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 136             SkOpSegment* segment = &fSegments[sIndex];
 137             if (segment->verb() == SkPath::kLine_Verb) {
 138                 continue;
 139             }
 140             if (segment->done()) {
 141                 continue;   // likely coincident, nothing to do
 142             }
 143             segment->checkEnds();
 144         }
 145     }
 146
 147     void checkMultiples() {
 148         int segmentCount = fSegments.count();
 149         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 150             SkOpSegment& segment = fSegments[sIndex];
 151             if (segment.count() > 2) {
 152                 segment.checkMultiples();
 153                 fMultiples |= segment.hasMultiples();
 154             }
 155         }
 156     }
 157
 158     void checkSmall() {
 159         int segmentCount = fSegments.count();
 160         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 161             SkOpSegment& segment = fSegments[sIndex];
 162             // OPTIMIZATION : skip segments that are done?
 163             if (segment.hasSmall()) {
 164                 segment.checkSmall();
 165             }
 166         }
 167     }
 168
 169     // if same point has different T values, choose a common T
 170     void checkTiny() {
 171         int segmentCount = fSegments.count();
 172         if (segmentCount <= 2) {
 173             return;
 174         }
 175         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 176             SkOpSegment& segment = fSegments[sIndex];
 177             if (segment.hasTiny()) {
 178                 segment.checkTiny();
 179             }
 180         }
 181     }
 182
 183     void complete() {
 184         setBounds();
 185         fContainsIntercepts = false;
 186     }
 187
 188     bool containsCubics() const {
 189         return fContainsCubics;
 190     }
 191
 192     bool crosses(const SkOpContour* crosser) const {
 193         for (int index = 0; index < fCrosses.count(); ++index) {
 194             if (fCrosses[index] == crosser) {
 195                 return true;
 196             }
 197         }
 198         return false;
 199     }
 200
 201     bool done() const {
 202         return fDone;
 203     }
 204
 205     const SkPoint& end() const {
 206         const SkOpSegment& segment = fSegments.back();
 207         return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
 208     }
 209
 210     void fixOtherTIndex() {
 211         int segmentCount = fSegments.count();
 212         for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
 213             fSegments[sIndex].fixOtherTIndex();
 214         }
 215     }
 216
 217     bool hasMultiples() const {
 218         return fMultiples;
 219     }
 220
 221     void joinCoincidence() {
 222         joinCoincidence(fCoincidences, false);
 223         joinCoincidence(fPartialCoincidences, true);
 224     }
 225
 226     SkOpSegment* nonVerticalSegment(int* start, int* end);
 227
 228     bool operand() const {
 229         return fOperand;
 230     }
 231
 232     void reset() {
 233         fSegments.reset();
 234         fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
 235         fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = fMultiples = false;
 236     }
 237
 238     void resolveNearCoincidence();
 239
 240     SkTArray<SkOpSegment>& segments() {
 241         return fSegments;
 242     }
 243
 244     void setContainsIntercepts() {
 245         fContainsIntercepts = true;
 246     }
 247
 248     void setOperand(bool isOp) {
 249         fOperand = isOp;
 250     }
 251
 252     void setOppXor(bool isOppXor) {
 253         fOppXor = isOppXor;
 254         int segmentCount = fSegments.count();
 255         for (int test = 0; test < segmentCount; ++test) {
 256             fSegments[test].setOppXor(isOppXor);
 257         }
 258     }
 259
 260     void setXor(bool isXor) {
 261         fXor = isXor;
 262     }
 263
 264     void sortAngles();
 265     void sortSegments();
 266
 267     const SkPoint& start() const {
 268         return fSegments.front().pts()[0];
 269     }
 270
 271     void toPath(SkPathWriter* path) const;
 272
 273     void toPartialBackward(SkPathWriter* path) const {
 274         int segmentCount = fSegments.count();
 275         for (int test = segmentCount - 1; test >= 0; --test) {
 276             fSegments[test].addCurveTo(1, 0, path, true);
 277         }
 278     }
 279
 280     void toPartialForward(SkPathWriter* path) const {
 281         int segmentCount = fSegments.count();
 282         for (int test = 0; test < segmentCount; ++test) {
 283             fSegments[test].addCurveTo(0, 1, path, true);
 284         }
 285     }
 286
 287     void topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, SkOpSegment** topStart);
 288     SkOpSegment* undoneSegment(int* start, int* end);
 289
 290     int updateSegment(int index, const SkPoint* pts) {
 291         SkOpSegment& segment = fSegments[index];
 292         segment.updatePts(pts);
 293         return SkPathOpsVerbToPoints(segment.verb()) + 1;
 294     }
 295
 296 #if DEBUG_TEST
 297     SkTArray<SkOpSegment>& debugSegments() {
 298         return fSegments;
 299     }
 300 #endif
 301
 302 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
 303     void debugShowActiveSpans() {
 304         for (int index = 0; index < fSegments.count(); ++index) {
 305             fSegments[index].debugShowActiveSpans();
 306         }
 307     }
 308 #endif
 309
 310 #if DEBUG_SHOW_WINDING
 311     int debugShowWindingValues(int totalSegments, int ofInterest);
 312     static void debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList);
 313 #endif
 314
 315     // available to test routines only
 316     void dump() const;
 317     void dumpAngles() const;
 318     void dumpCoincidence(const SkCoincidence& ) const;
 319     void dumpCoincidences() const;
 320     void dumpPt(int ) const;
 321     void dumpPts() const;
 322     void dumpSpan(int ) const;
 323     void dumpSpans() const;
 324
 325 private:
 326     void alignPt(int index, SkPoint* point, int zeroPt) const;
 327     int alignT(bool swap, int tIndex, SkIntersections* ts) const;
 328     bool calcCommonCoincidentWinding(const SkCoincidence& );
 329     void checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
 330                              const SkCoincidence& twoCoin, int twoIdx, bool partial);
 331     void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
 332     void setBounds();
 333
 334     SkTArray<SkOpSegment> fSegments;
 335     SkTArray<SkOpSegment*, true> fSortedSegments;
 336     int fFirstSorted;
 337     SkTArray<SkCoincidence, true> fCoincidences;
 338     SkTArray<SkCoincidence, true> fPartialCoincidences;
 339     SkTArray<const SkOpContour*, true> fCrosses;
 340     SkPathOpsBounds fBounds;
 341     bool fContainsIntercepts;  // FIXME: is this used by anybody?
 342     bool fContainsCubics;
 343     bool fContainsCurves;
 344     bool fDone;
 345     bool fMultiples;  // set if some segment has multiple identical intersections with other curves
 346     bool fOperand;  // true for the second argument to a binary operator
 347     bool fXor;
 348     bool fOppXor;
 349 #if defined(SK_DEBUG) || !FORCE_RELEASE
 350     int debugID() const { return fID; }
 351     int fID;
 352 #else
 353     int debugID() const { return -1; }
 354 #endif
 355 };
 356
 357 #endif