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