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