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