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