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 SkPathOpsCurve_DEFINE 8 #define SkPathOpsCurve_DEFINE 9 10 #include "SkIntersections.h" 11 12 #ifndef SK_RELEASE 13 #include "SkPath.h" 14 #endif 15 16 struct SkPathOpsBounds; 17 18 struct SkOpCurve { 19 SkPoint fPts[4]; 20 SkScalar fWeight; 21 SkDEBUGCODE(SkPath::Verb fVerb); 22 23 const SkPoint& operator[](int n) const { 24 SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb)); 25 return fPts[n]; 26 } 27 28 void dump() const; 29 30 void set(const SkDQuad& quad) { 31 for (int index = 0; index < SkDQuad::kPointCount; ++index) { 32 fPts[index] = quad[index].asSkPoint(); 33 } 34 SkDEBUGCODE(fWeight = 1); 35 SkDEBUGCODE(fVerb = SkPath::kQuad_Verb); 36 } 37 38 void set(const SkDCubic& cubic) { 39 for (int index = 0; index < SkDCubic::kPointCount; ++index) { 40 fPts[index] = cubic[index].asSkPoint(); 41 } 42 SkDEBUGCODE(fWeight = 1); 43 SkDEBUGCODE(fVerb = SkPath::kCubic_Verb); 44 } 45 46 }; 47 48 struct SkDCurve { 49 union { 50 SkDLine fLine; 51 SkDQuad fQuad; 52 SkDConic fConic; 53 SkDCubic fCubic; 54 }; 55 SkDEBUGCODE(SkPath::Verb fVerb); 56 57 const SkDPoint& operator[](int n) const { 58 SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb)); 59 return fCubic[n]; 60 } 61 62 SkDPoint& operator[](int n) { 63 SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb)); 64 return fCubic[n]; 65 } 66 67 SkDPoint conicTop(const SkPoint curve[3], SkScalar curveWeight, 68 double s, double e, double* topT); 69 SkDPoint cubicTop(const SkPoint curve[4], SkScalar , double s, double e, double* topT); 70 void dump() const; 71 void dumpID(int ) const; 72 SkDPoint lineTop(const SkPoint[2], SkScalar , double , double , double* topT); 73 double nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const; 74 void offset(SkPath::Verb verb, const SkDVector& ); 75 SkDPoint quadTop(const SkPoint curve[3], SkScalar , double s, double e, double* topT); 76 77 void setConicBounds(const SkPoint curve[3], SkScalar curveWeight, 78 double s, double e, SkPathOpsBounds* ); 79 void setCubicBounds(const SkPoint curve[4], SkScalar , 80 double s, double e, SkPathOpsBounds* ); 81 void setQuadBounds(const SkPoint curve[3], SkScalar , 82 double s, double e, SkPathOpsBounds*); 83 }; 84 85 class SkDCurveSweep { 86 public: 87 bool isCurve() const { return fIsCurve; } 88 bool isOrdered() const { return fOrdered; } 89 void setCurveHullSweep(SkPath::Verb verb); 90 91 SkDCurve fCurve; 92 SkDVector fSweep[2]; 93 private: 94 bool fIsCurve; 95 bool fOrdered; // cleared when a cubic's control point isn't between the sweep vectors 96 97 }; 98 99 extern SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar cWeight, 100 double tStart, double tEnd, double* topT); 101 102 static SkDPoint dline_xy_at_t(const SkPoint a[2], SkScalar , double t) { 103 SkDLine line; 104 line.set(a); 105 return line.ptAtT(t); 106 } 107 108 static SkDPoint dquad_xy_at_t(const SkPoint a[3], SkScalar , double t) { 109 SkDQuad quad; 110 quad.set(a); 111 return quad.ptAtT(t); 112 } 113 114 static SkDPoint dconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) { 115 SkDConic conic; 116 conic.set(a, weight); 117 return conic.ptAtT(t); 118 } 119 120 static SkDPoint dcubic_xy_at_t(const SkPoint a[4], SkScalar , double t) { 121 SkDCubic cubic; 122 cubic.set(a); 123 return cubic.ptAtT(t); 124 } 125 126 static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], SkScalar , double ) = { 127 nullptr, 128 dline_xy_at_t, 129 dquad_xy_at_t, 130 dconic_xy_at_t, 131 dcubic_xy_at_t 132 }; 133 134 static SkDPoint ddline_xy_at_t(const SkDCurve& c, double t) { 135 return c.fLine.ptAtT(t); 136 } 137 138 static SkDPoint ddquad_xy_at_t(const SkDCurve& c, double t) { 139 return c.fQuad.ptAtT(t); 140 } 141 142 static SkDPoint ddconic_xy_at_t(const SkDCurve& c, double t) { 143 return c.fConic.ptAtT(t); 144 } 145 146 static SkDPoint ddcubic_xy_at_t(const SkDCurve& c, double t) { 147 return c.fCubic.ptAtT(t); 148 } 149 150 static SkDPoint (* const CurveDDPointAtT[])(const SkDCurve& , double ) = { 151 nullptr, 152 ddline_xy_at_t, 153 ddquad_xy_at_t, 154 ddconic_xy_at_t, 155 ddcubic_xy_at_t 156 }; 157 158 static SkPoint fline_xy_at_t(const SkPoint a[2], SkScalar weight, double t) { 159 return dline_xy_at_t(a, weight, t).asSkPoint(); 160 } 161 162 static SkPoint fquad_xy_at_t(const SkPoint a[3], SkScalar weight, double t) { 163 return dquad_xy_at_t(a, weight, t).asSkPoint(); 164 } 165 166 static SkPoint fconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) { 167 return dconic_xy_at_t(a, weight, t).asSkPoint(); 168 } 169 170 static SkPoint fcubic_xy_at_t(const SkPoint a[4], SkScalar weight, double t) { 171 return dcubic_xy_at_t(a, weight, t).asSkPoint(); 172 } 173 174 static SkPoint (* const CurvePointAtT[])(const SkPoint[], SkScalar , double ) = { 175 nullptr, 176 fline_xy_at_t, 177 fquad_xy_at_t, 178 fconic_xy_at_t, 179 fcubic_xy_at_t 180 }; 181 182 static SkDVector dline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) { 183 SkDLine line; 184 line.set(a); 185 return line[1] - line[0]; 186 } 187 188 static SkDVector dquad_dxdy_at_t(const SkPoint a[3], SkScalar , double t) { 189 SkDQuad quad; 190 quad.set(a); 191 return quad.dxdyAtT(t); 192 } 193 194 static SkDVector dconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) { 195 SkDConic conic; 196 conic.set(a, weight); 197 return conic.dxdyAtT(t); 198 } 199 200 static SkDVector dcubic_dxdy_at_t(const SkPoint a[4], SkScalar , double t) { 201 SkDCubic cubic; 202 cubic.set(a); 203 return cubic.dxdyAtT(t); 204 } 205 206 static SkDVector (* const CurveDSlopeAtT[])(const SkPoint[], SkScalar , double ) = { 207 nullptr, 208 dline_dxdy_at_t, 209 dquad_dxdy_at_t, 210 dconic_dxdy_at_t, 211 dcubic_dxdy_at_t 212 }; 213 214 static SkDVector ddline_dxdy_at_t(const SkDCurve& c, double ) { 215 return c.fLine.fPts[1] - c.fLine.fPts[0]; 216 } 217 218 static SkDVector ddquad_dxdy_at_t(const SkDCurve& c, double t) { 219 return c.fQuad.dxdyAtT(t); 220 } 221 222 static SkDVector ddconic_dxdy_at_t(const SkDCurve& c, double t) { 223 return c.fConic.dxdyAtT(t); 224 } 225 226 static SkDVector ddcubic_dxdy_at_t(const SkDCurve& c, double t) { 227 return c.fCubic.dxdyAtT(t); 228 } 229 230 static SkDVector (* const CurveDDSlopeAtT[])(const SkDCurve& , double ) = { 231 nullptr, 232 ddline_dxdy_at_t, 233 ddquad_dxdy_at_t, 234 ddconic_dxdy_at_t, 235 ddcubic_dxdy_at_t 236 }; 237 238 static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) { 239 return a[1] - a[0]; 240 } 241 242 static SkVector fquad_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) { 243 return dquad_dxdy_at_t(a, weight, t).asSkVector(); 244 } 245 246 static SkVector fconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) { 247 return dconic_dxdy_at_t(a, weight, t).asSkVector(); 248 } 249 250 static SkVector fcubic_dxdy_at_t(const SkPoint a[4], SkScalar weight, double t) { 251 return dcubic_dxdy_at_t(a, weight, t).asSkVector(); 252 } 253 254 static SkVector (* const CurveSlopeAtT[])(const SkPoint[], SkScalar , double ) = { 255 nullptr, 256 fline_dxdy_at_t, 257 fquad_dxdy_at_t, 258 fconic_dxdy_at_t, 259 fcubic_dxdy_at_t 260 }; 261 262 static bool line_is_vertical(const SkPoint a[2], SkScalar , double startT, double endT) { 263 SkDLine line; 264 line.set(a); 265 SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) }; 266 return AlmostEqualUlps(dst[0].fX, dst[1].fX); 267 } 268 269 static bool quad_is_vertical(const SkPoint a[3], SkScalar , double startT, double endT) { 270 SkDQuad quad; 271 quad.set(a); 272 SkDQuad dst = quad.subDivide(startT, endT); 273 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX); 274 } 275 276 static bool conic_is_vertical(const SkPoint a[3], SkScalar weight, double startT, double endT) { 277 SkDConic conic; 278 conic.set(a, weight); 279 SkDConic dst = conic.subDivide(startT, endT); 280 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX); 281 } 282 283 static bool cubic_is_vertical(const SkPoint a[4], SkScalar , double startT, double endT) { 284 SkDCubic cubic; 285 cubic.set(a); 286 SkDCubic dst = cubic.subDivide(startT, endT); 287 return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX) 288 && AlmostEqualUlps(dst[2].fX, dst[3].fX); 289 } 290 291 static bool (* const CurveIsVertical[])(const SkPoint[], SkScalar , double , double) = { 292 nullptr, 293 line_is_vertical, 294 quad_is_vertical, 295 conic_is_vertical, 296 cubic_is_vertical 297 }; 298 299 static void line_intersect_ray(const SkPoint a[2], SkScalar , const SkDLine& ray, 300 SkIntersections* i) { 301 SkDLine line; 302 line.set(a); 303 i->intersectRay(line, ray); 304 } 305 306 static void quad_intersect_ray(const SkPoint a[3], SkScalar , const SkDLine& ray, 307 SkIntersections* i) { 308 SkDQuad quad; 309 quad.set(a); 310 i->intersectRay(quad, ray); 311 } 312 313 static void conic_intersect_ray(const SkPoint a[3], SkScalar weight, const SkDLine& ray, 314 SkIntersections* i) { 315 SkDConic conic; 316 conic.set(a, weight); 317 i->intersectRay(conic, ray); 318 } 319 320 static void cubic_intersect_ray(const SkPoint a[4], SkScalar , const SkDLine& ray, 321 SkIntersections* i) { 322 SkDCubic cubic; 323 cubic.set(a); 324 i->intersectRay(cubic, ray); 325 } 326 327 static void (* const CurveIntersectRay[])(const SkPoint[] , SkScalar , const SkDLine& , 328 SkIntersections* ) = { 329 nullptr, 330 line_intersect_ray, 331 quad_intersect_ray, 332 conic_intersect_ray, 333 cubic_intersect_ray 334 }; 335 336 static void dline_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 337 i->intersectRay(c.fLine, ray); 338 } 339 340 static void dquad_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 341 i->intersectRay(c.fQuad, ray); 342 } 343 344 static void dconic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 345 i->intersectRay(c.fConic, ray); 346 } 347 348 static void dcubic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 349 i->intersectRay(c.fCubic, ray); 350 } 351 352 static void (* const CurveDIntersectRay[])(const SkDCurve& , const SkDLine& , SkIntersections* ) = { 353 nullptr, 354 dline_intersect_ray, 355 dquad_intersect_ray, 356 dconic_intersect_ray, 357 dcubic_intersect_ray 358 }; 359 360 static int line_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) { 361 SkDLine line; 362 roots[0] = SkIntersections::HorizontalIntercept(line.set(a), y); 363 return between(0, roots[0], 1); 364 } 365 366 static int line_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) { 367 SkDLine line; 368 roots[0] = SkIntersections::VerticalIntercept(line.set(a), x); 369 return between(0, roots[0], 1); 370 } 371 372 static int quad_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) { 373 SkDQuad quad; 374 return SkIntersections::HorizontalIntercept(quad.set(a), y, roots); 375 } 376 377 static int quad_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) { 378 SkDQuad quad; 379 return SkIntersections::VerticalIntercept(quad.set(a), x, roots); 380 } 381 382 static int conic_intercept_h(const SkPoint a[2], SkScalar w, SkScalar y, double* roots) { 383 SkDConic conic; 384 return SkIntersections::HorizontalIntercept(conic.set(a, w), y, roots); 385 } 386 387 static int conic_intercept_v(const SkPoint a[2], SkScalar w, SkScalar x, double* roots) { 388 SkDConic conic; 389 return SkIntersections::VerticalIntercept(conic.set(a, w), x, roots); 390 } 391 392 static int cubic_intercept_h(const SkPoint a[3], SkScalar , SkScalar y, double* roots) { 393 SkDCubic cubic; 394 return cubic.set(a).horizontalIntersect(y, roots); 395 } 396 397 static int cubic_intercept_v(const SkPoint a[3], SkScalar , SkScalar x, double* roots) { 398 SkDCubic cubic; 399 return cubic.set(a).verticalIntersect(x, roots); 400 } 401 402 static int (* const CurveIntercept[])(const SkPoint[] , SkScalar , SkScalar , double* ) = { 403 nullptr, 404 nullptr, 405 line_intercept_h, 406 line_intercept_v, 407 quad_intercept_h, 408 quad_intercept_v, 409 conic_intercept_h, 410 conic_intercept_v, 411 cubic_intercept_h, 412 cubic_intercept_v, 413 }; 414 415 #endif 416