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 SkIntersections_DEFINE 8 #define SkIntersections_DEFINE 9 10 #include "SkPathOpsConic.h" 11 #include "SkPathOpsCubic.h" 12 #include "SkPathOpsLine.h" 13 #include "SkPathOpsPoint.h" 14 #include "SkPathOpsQuad.h" 15 16 class SkIntersections { 17 public: 18 SkIntersections(SkDEBUGCODE(SkOpGlobalState* globalState = nullptr)) 19 : fSwap(0) 20 #ifdef SK_DEBUG 21 SkDEBUGPARAMS(fDebugGlobalState(globalState)) 22 , fDepth(0) 23 #endif 24 { 25 sk_bzero(fPt, sizeof(fPt)); 26 sk_bzero(fPt2, sizeof(fPt2)); 27 sk_bzero(fT, sizeof(fT)); 28 sk_bzero(fNearlySame, sizeof(fNearlySame)); 29 #if DEBUG_T_SECT_LOOP_COUNT 30 sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount)); 31 #endif 32 reset(); 33 fMax = 0; // require that the caller set the max 34 } 35 36 class TArray { 37 public: 38 explicit TArray(const double ts[10]) : fTArray(ts) {} 39 double operator[](int n) const { 40 return fTArray[n]; 41 } 42 const double* fTArray; 43 }; 44 TArray operator[](int n) const { return TArray(fT[n]); } 45 46 void allowNear(bool nearAllowed) { 47 fAllowNear = nearAllowed; 48 } 49 50 void clearCoincidence(int index) { 51 SkASSERT(index >= 0); 52 int bit = 1 << index; 53 fIsCoincident[0] &= ~bit; 54 fIsCoincident[1] &= ~bit; 55 } 56 57 int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right, 58 SkScalar y, bool flipped) { 59 SkDConic conic; 60 conic.set(a, weight); 61 fMax = 2; 62 return horizontal(conic, left, right, y, flipped); 63 } 64 65 int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom, 66 SkScalar x, bool flipped) { 67 SkDConic conic; 68 conic.set(a, weight); 69 fMax = 2; 70 return vertical(conic, top, bottom, x, flipped); 71 } 72 73 int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) { 74 SkDConic conic; 75 conic.set(a, weight); 76 SkDLine line; 77 line.set(b); 78 fMax = 3; // 2; permit small coincident segment + non-coincident intersection 79 return intersect(conic, line); 80 } 81 82 int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y, 83 bool flipped) { 84 SkDCubic cubic; 85 cubic.set(a); 86 fMax = 3; 87 return horizontal(cubic, left, right, y, flipped); 88 } 89 90 int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { 91 SkDCubic cubic; 92 cubic.set(a); 93 fMax = 3; 94 return vertical(cubic, top, bottom, x, flipped); 95 } 96 97 int cubicLine(const SkPoint a[4], const SkPoint b[2]) { 98 SkDCubic cubic; 99 cubic.set(a); 100 SkDLine line; 101 line.set(b); 102 fMax = 3; 103 return intersect(cubic, line); 104 } 105 106 #ifdef SK_DEBUG 107 SkOpGlobalState* globalState() const { return fDebugGlobalState; } 108 #endif 109 110 bool hasT(double t) const { 111 SkASSERT(t == 0 || t == 1); 112 return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1); 113 } 114 115 bool hasOppT(double t) const { 116 SkASSERT(t == 0 || t == 1); 117 return fUsed > 0 && (fT[1][0] == t || fT[1][fUsed - 1] == t); 118 } 119 120 int insertSwap(double one, double two, const SkDPoint& pt) { 121 if (fSwap) { 122 return insert(two, one, pt); 123 } else { 124 return insert(one, two, pt); 125 } 126 } 127 128 bool isCoincident(int index) { 129 return (fIsCoincident[0] & 1 << index) != 0; 130 } 131 132 int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y, 133 bool flipped) { 134 SkDLine line; 135 line.set(a); 136 fMax = 2; 137 return horizontal(line, left, right, y, flipped); 138 } 139 140 int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { 141 SkDLine line; 142 line.set(a); 143 fMax = 2; 144 return vertical(line, top, bottom, x, flipped); 145 } 146 147 int lineLine(const SkPoint a[2], const SkPoint b[2]) { 148 SkDLine aLine, bLine; 149 aLine.set(a); 150 bLine.set(b); 151 fMax = 2; 152 return intersect(aLine, bLine); 153 } 154 155 bool nearlySame(int index) const { 156 SkASSERT(index == 0 || index == 1); 157 return fNearlySame[index]; 158 } 159 160 const SkDPoint& pt(int index) const { 161 return fPt[index]; 162 } 163 164 const SkDPoint& pt2(int index) const { 165 return fPt2[index]; 166 } 167 168 int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y, 169 bool flipped) { 170 SkDQuad quad; 171 quad.set(a); 172 fMax = 2; 173 return horizontal(quad, left, right, y, flipped); 174 } 175 176 int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) { 177 SkDQuad quad; 178 quad.set(a); 179 fMax = 2; 180 return vertical(quad, top, bottom, x, flipped); 181 } 182 183 int quadLine(const SkPoint a[3], const SkPoint b[2]) { 184 SkDQuad quad; 185 quad.set(a); 186 SkDLine line; 187 line.set(b); 188 return intersect(quad, line); 189 } 190 191 // leaves swap, max alone 192 void reset() { 193 fAllowNear = true; 194 fUsed = 0; 195 sk_bzero(fIsCoincident, sizeof(fIsCoincident)); 196 } 197 198 void set(bool swap, int tIndex, double t) { 199 fT[(int) swap][tIndex] = t; 200 } 201 202 void setMax(int max) { 203 SkASSERT(max <= (int) SK_ARRAY_COUNT(fPt)); 204 fMax = max; 205 } 206 207 void swap() { 208 fSwap ^= true; 209 } 210 211 bool swapped() const { 212 return fSwap; 213 } 214 215 int used() const { 216 return fUsed; 217 } 218 219 void downDepth() { 220 SkASSERT(--fDepth >= 0); 221 } 222 223 bool unBumpT(int index) { 224 SkASSERT(fUsed == 1); 225 fT[0][index] = fT[0][index] * (1 + BUMP_EPSILON * 2) - BUMP_EPSILON; 226 if (!between(0, fT[0][index], 1)) { 227 fUsed = 0; 228 return false; 229 } 230 return true; 231 } 232 233 void upDepth() { 234 SkASSERT(++fDepth < 16); 235 } 236 237 void alignQuadPts(const SkPoint a[3], const SkPoint b[3]); 238 int cleanUpCoincidence(); 239 int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const; 240 void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1, 241 const SkDCubic& c2); 242 void flip(); 243 int horizontal(const SkDLine&, double left, double right, double y, bool flipped); 244 int horizontal(const SkDQuad&, double left, double right, double y, bool flipped); 245 int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]); 246 int horizontal(const SkDCubic&, double y, double tRange[3]); 247 int horizontal(const SkDConic&, double left, double right, double y, bool flipped); 248 int horizontal(const SkDCubic&, double left, double right, double y, bool flipped); 249 int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]); 250 static double HorizontalIntercept(const SkDLine& line, double y); 251 static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots); 252 static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots); 253 // FIXME : does not respect swap 254 int insert(double one, double two, const SkDPoint& pt); 255 void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2); 256 // start if index == 0 : end if index == 1 257 int insertCoincident(double one, double two, const SkDPoint& pt); 258 int intersect(const SkDLine&, const SkDLine&); 259 int intersect(const SkDQuad&, const SkDLine&); 260 int intersect(const SkDQuad&, const SkDQuad&); 261 int intersect(const SkDConic&, const SkDLine&); 262 int intersect(const SkDConic&, const SkDQuad&); 263 int intersect(const SkDConic&, const SkDConic&); 264 int intersect(const SkDCubic&, const SkDLine&); 265 int intersect(const SkDCubic&, const SkDQuad&); 266 int intersect(const SkDCubic&, const SkDConic&); 267 int intersect(const SkDCubic&, const SkDCubic&); 268 int intersectRay(const SkDLine&, const SkDLine&); 269 int intersectRay(const SkDQuad&, const SkDLine&); 270 int intersectRay(const SkDConic&, const SkDLine&); 271 int intersectRay(const SkDCubic&, const SkDLine&); 272 void merge(const SkIntersections& , int , const SkIntersections& , int ); 273 int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const; 274 void removeOne(int index); 275 void setCoincident(int index); 276 int vertical(const SkDLine&, double top, double bottom, double x, bool flipped); 277 int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped); 278 int vertical(const SkDConic&, double top, double bottom, double x, bool flipped); 279 int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped); 280 static double VerticalIntercept(const SkDLine& line, double x); 281 static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots); 282 static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots); 283 284 int depth() const { 285 #ifdef SK_DEBUG 286 return fDepth; 287 #else 288 return 0; 289 #endif 290 } 291 292 enum DebugLoop { 293 kIterations_DebugLoop, 294 kCoinCheck_DebugLoop, 295 kComputePerp_DebugLoop, 296 }; 297 298 void debugBumpLoopCount(DebugLoop ); 299 int debugCoincidentUsed() const; 300 int debugLoopCount(DebugLoop ) const; 301 void debugResetLoopCount(); 302 void dump() const; // implemented for testing only 303 304 private: 305 bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2); 306 bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2); 307 void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& ); 308 void cleanUpParallelLines(bool parallel); 309 void computePoints(const SkDLine& line, int used); 310 311 SkDPoint fPt[13]; // FIXME: since scans store points as SkPoint, this should also 312 SkDPoint fPt2[2]; // used by nearly same to store alternate intersection point 313 double fT[2][13]; 314 uint16_t fIsCoincident[2]; // bit set for each curve's coincident T 315 bool fNearlySame[2]; // true if end points nearly match 316 unsigned char fUsed; 317 unsigned char fMax; 318 bool fAllowNear; 319 bool fSwap; 320 #ifdef SK_DEBUG 321 SkOpGlobalState* fDebugGlobalState; 322 int fDepth; 323 #endif 324 #if DEBUG_T_SECT_LOOP_COUNT 325 int fDebugLoopCount[3]; 326 #endif 327 }; 328 329 #endif 330
