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: SkOpContour()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 addCross(const SkOpContour * crosser)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 addCubic(const SkPoint pts[4])57 void addCubic(const SkPoint pts[4]) { 58 fSegments.push_back().addCubic(pts, fOperand, fXor); 59 fContainsCurves = fContainsCubics = true; 60 } 61 addLine(const SkPoint pts[2])62 int addLine(const SkPoint pts[2]) { 63 fSegments.push_back().addLine(pts, fOperand, fXor); 64 return fSegments.count(); 65 } 66 addOtherT(int segIndex,int tIndex,double otherT,int otherIndex)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 addQuad(const SkPoint pts[3])74 int addQuad(const SkPoint pts[3]) { 75 fSegments.push_back().addQuad(pts, fOperand, fXor); 76 fContainsCurves = true; 77 return fSegments.count(); 78 } 79 addT(int segIndex,SkOpContour * other,int otherIndex,const SkPoint & pt,double newT)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 addSelfT(int segIndex,const SkPoint & pt,double newT)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 alignCoincidence(const SkOpSegment::AlignedSpan & aligned)94 void alignCoincidence(const SkOpSegment::AlignedSpan& aligned) { 95 alignCoincidence(aligned, &fCoincidences); 96 alignCoincidence(aligned, &fPartialCoincidences); 97 } 98 alignMultiples(SkTDArray<SkOpSegment::AlignedSpan> * aligned)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 bounds()112 const SkPathOpsBounds& bounds() const { 113 return fBounds; 114 } 115 116 bool calcAngles(); 117 bool calcCoincidentWinding(); 118 void calcPartialCoincidentWinding(); 119 checkDuplicates()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 checkEnds()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 checkMultiples()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 checkSmall()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 checkTiny()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 complete()183 void complete() { 184 setBounds(); 185 fContainsIntercepts = false; 186 } 187 containsCubics()188 bool containsCubics() const { 189 return fContainsCubics; 190 } 191 crosses(const SkOpContour * crosser)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 done()201 bool done() const { 202 return fDone; 203 } 204 end()205 const SkPoint& end() const { 206 const SkOpSegment& segment = fSegments.back(); 207 return segment.pts()[SkPathOpsVerbToPoints(segment.verb())]; 208 } 209 fixOtherTIndex()210 void fixOtherTIndex() { 211 int segmentCount = fSegments.count(); 212 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 213 fSegments[sIndex].fixOtherTIndex(); 214 } 215 } 216 hasMultiples()217 bool hasMultiples() const { 218 return fMultiples; 219 } 220 joinCoincidence()221 void joinCoincidence() { 222 joinCoincidence(fCoincidences, false); 223 joinCoincidence(fPartialCoincidences, true); 224 } 225 226 SkOpSegment* nonVerticalSegment(int* start, int* end); 227 operand()228 bool operand() const { 229 return fOperand; 230 } 231 reset()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 segments()240 SkTArray<SkOpSegment>& segments() { 241 return fSegments; 242 } 243 setContainsIntercepts()244 void setContainsIntercepts() { 245 fContainsIntercepts = true; 246 } 247 setOperand(bool isOp)248 void setOperand(bool isOp) { 249 fOperand = isOp; 250 } 251 setOppXor(bool isOppXor)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 setXor(bool isXor)260 void setXor(bool isXor) { 261 fXor = isXor; 262 } 263 264 void sortAngles(); 265 void sortSegments(); 266 start()267 const SkPoint& start() const { 268 return fSegments.front().pts()[0]; 269 } 270 271 void toPath(SkPathWriter* path) const; 272 toPartialBackward(SkPathWriter * path)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 toPartialForward(SkPathWriter * path)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 updateSegment(int index,const SkPoint * pts)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 debugSegments()297 SkTArray<SkOpSegment>& debugSegments() { 298 return fSegments; 299 } 300 #endif 301 302 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY debugShowActiveSpans()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 debugID()350 int debugID() const { return fID; } 351 int fID; 352 #else debugID()353 int debugID() const { return -1; } 354 #endif 355 }; 356 357 #endif 358