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 16struct SkPathOpsBounds; 17 18struct 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 48struct 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 85class SkDCurveSweep { 86public: 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]; 93private: 94 bool fIsCurve; 95 bool fOrdered; // cleared when a cubic's control point isn't between the sweep vectors 96 97}; 98 99extern SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar cWeight, 100 double tStart, double tEnd, double* topT); 101 102static 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 108static 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 114static 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 120static 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 126static 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 134static SkDPoint ddline_xy_at_t(const SkDCurve& c, double t) { 135 return c.fLine.ptAtT(t); 136} 137 138static SkDPoint ddquad_xy_at_t(const SkDCurve& c, double t) { 139 return c.fQuad.ptAtT(t); 140} 141 142static SkDPoint ddconic_xy_at_t(const SkDCurve& c, double t) { 143 return c.fConic.ptAtT(t); 144} 145 146static SkDPoint ddcubic_xy_at_t(const SkDCurve& c, double t) { 147 return c.fCubic.ptAtT(t); 148} 149 150static 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 158static 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 162static 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 166static 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 170static 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 174static 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 182static 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 188static 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 194static 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 200static 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 206static 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 214static SkDVector ddline_dxdy_at_t(const SkDCurve& c, double ) { 215 return c.fLine.fPts[1] - c.fLine.fPts[0]; 216} 217 218static SkDVector ddquad_dxdy_at_t(const SkDCurve& c, double t) { 219 return c.fQuad.dxdyAtT(t); 220} 221 222static SkDVector ddconic_dxdy_at_t(const SkDCurve& c, double t) { 223 return c.fConic.dxdyAtT(t); 224} 225 226static SkDVector ddcubic_dxdy_at_t(const SkDCurve& c, double t) { 227 return c.fCubic.dxdyAtT(t); 228} 229 230static 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 238static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) { 239 return a[1] - a[0]; 240} 241 242static 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 246static 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 250static 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 254static 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 262static 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 269static 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 276static 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 283static 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 291static 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 299static 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 306static 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 313static 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 320static 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 327static 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 336static void dline_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 337 i->intersectRay(c.fLine, ray); 338} 339 340static void dquad_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 341 i->intersectRay(c.fQuad, ray); 342} 343 344static void dconic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 345 i->intersectRay(c.fConic, ray); 346} 347 348static void dcubic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) { 349 i->intersectRay(c.fCubic, ray); 350} 351 352static 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 360static 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 366static 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 372static 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 377static 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 382static 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 387static 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 392static 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 397static 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 402static 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