Line data    Source code

       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           0 :     const SkDPoint& operator[](int n) const {
      58           0 :         SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
      59           0 :         return fCubic[n];
      60             :     }
      61             : 
      62           0 :     SkDPoint& operator[](int n) {
      63           0 :         SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
      64           0 :         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           0 :     bool isCurve() const { return fIsCurve; }
      88           0 :     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           0 : static SkDPoint dline_xy_at_t(const SkPoint a[2], SkScalar , double t) {
     103             :     SkDLine line;
     104           0 :     line.set(a);
     105           0 :     return line.ptAtT(t);
     106             : }
     107             : 
     108           0 : static SkDPoint dquad_xy_at_t(const SkPoint a[3], SkScalar , double t) {
     109             :     SkDQuad quad;
     110           0 :     quad.set(a);
     111           0 :     return quad.ptAtT(t);
     112             : }
     113             : 
     114           0 : static SkDPoint dconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
     115             :     SkDConic conic;
     116           0 :     conic.set(a, weight);
     117           0 :     return conic.ptAtT(t);
     118             : }
     119             : 
     120           0 : static SkDPoint dcubic_xy_at_t(const SkPoint a[4], SkScalar , double t) {
     121             :     SkDCubic cubic;
     122           0 :     cubic.set(a);
     123           0 :     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           0 : static SkDPoint ddline_xy_at_t(const SkDCurve& c, double t) {
     135           0 :     return c.fLine.ptAtT(t);
     136             : }
     137             : 
     138           0 : static SkDPoint ddquad_xy_at_t(const SkDCurve& c, double t) {
     139           0 :     return c.fQuad.ptAtT(t);
     140             : }
     141             : 
     142           0 : static SkDPoint ddconic_xy_at_t(const SkDCurve& c, double t) {
     143           0 :     return c.fConic.ptAtT(t);
     144             : }
     145             : 
     146           0 : static SkDPoint ddcubic_xy_at_t(const SkDCurve& c, double t) {
     147           0 :     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           0 : static SkPoint fline_xy_at_t(const SkPoint a[2], SkScalar weight, double t) {
     159           0 :     return dline_xy_at_t(a, weight, t).asSkPoint();
     160             : }
     161             : 
     162           0 : static SkPoint fquad_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
     163           0 :     return dquad_xy_at_t(a, weight, t).asSkPoint();
     164             : }
     165             : 
     166           0 : static SkPoint fconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
     167           0 :     return dconic_xy_at_t(a, weight, t).asSkPoint();
     168             : }
     169             : 
     170           0 : static SkPoint fcubic_xy_at_t(const SkPoint a[4], SkScalar weight, double t) {
     171           0 :     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           0 : static SkDVector dline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
     183             :     SkDLine line;
     184           0 :     line.set(a);
     185           0 :     return line[1] - line[0];
     186             : }
     187             : 
     188           0 : static SkDVector dquad_dxdy_at_t(const SkPoint a[3], SkScalar , double t) {
     189             :     SkDQuad quad;
     190           0 :     quad.set(a);
     191           0 :     return quad.dxdyAtT(t);
     192             : }
     193             : 
     194           0 : static SkDVector dconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
     195             :     SkDConic conic;
     196           0 :     conic.set(a, weight);
     197           0 :     return conic.dxdyAtT(t);
     198             : }
     199             : 
     200           0 : static SkDVector dcubic_dxdy_at_t(const SkPoint a[4], SkScalar , double t) {
     201             :     SkDCubic cubic;
     202           0 :     cubic.set(a);
     203           0 :     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           0 : static SkDVector ddline_dxdy_at_t(const SkDCurve& c, double ) {
     215           0 :     return c.fLine.fPts[1] - c.fLine.fPts[0];
     216             : }
     217             : 
     218           0 : static SkDVector ddquad_dxdy_at_t(const SkDCurve& c, double t) {
     219           0 :     return c.fQuad.dxdyAtT(t);
     220             : }
     221             : 
     222           0 : static SkDVector ddconic_dxdy_at_t(const SkDCurve& c, double t) {
     223           0 :     return c.fConic.dxdyAtT(t);
     224             : }
     225             : 
     226           0 : static SkDVector ddcubic_dxdy_at_t(const SkDCurve& c, double t) {
     227           0 :     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           0 : static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
     239           0 :     return a[1] - a[0];
     240             : }
     241             : 
     242           0 : static SkVector fquad_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
     243           0 :     return dquad_dxdy_at_t(a, weight, t).asSkVector();
     244             : }
     245             : 
     246           0 : static SkVector fconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
     247           0 :     return dconic_dxdy_at_t(a, weight, t).asSkVector();
     248             : }
     249             : 
     250           0 : static SkVector fcubic_dxdy_at_t(const SkPoint a[4], SkScalar weight, double t) {
     251           0 :     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           0 : static bool line_is_vertical(const SkPoint a[2], SkScalar , double startT, double endT) {
     263             :     SkDLine line;
     264           0 :     line.set(a);
     265           0 :     SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) };
     266           0 :     return AlmostEqualUlps(dst[0].fX, dst[1].fX);
     267             : }
     268             : 
     269           0 : static bool quad_is_vertical(const SkPoint a[3], SkScalar , double startT, double endT) {
     270             :     SkDQuad quad;
     271           0 :     quad.set(a);
     272           0 :     SkDQuad dst = quad.subDivide(startT, endT);
     273           0 :     return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
     274             : }
     275             : 
     276           0 : static bool conic_is_vertical(const SkPoint a[3], SkScalar weight, double startT, double endT) {
     277             :     SkDConic conic;
     278           0 :     conic.set(a, weight);
     279           0 :     SkDConic dst = conic.subDivide(startT, endT);
     280           0 :     return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
     281             : }
     282             : 
     283           0 : static bool cubic_is_vertical(const SkPoint a[4], SkScalar , double startT, double endT) {
     284             :     SkDCubic cubic;
     285           0 :     cubic.set(a);
     286           0 :     SkDCubic dst = cubic.subDivide(startT, endT);
     287           0 :     return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX)
     288           0 :             && 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           0 : static void line_intersect_ray(const SkPoint a[2], SkScalar , const SkDLine& ray,
     300             :         SkIntersections* i) {
     301             :     SkDLine line;
     302           0 :     line.set(a);
     303           0 :     i->intersectRay(line, ray);
     304           0 : }
     305             : 
     306           0 : static void quad_intersect_ray(const SkPoint a[3], SkScalar , const SkDLine& ray,
     307             :         SkIntersections* i) {
     308             :     SkDQuad quad;
     309           0 :     quad.set(a);
     310           0 :     i->intersectRay(quad, ray);
     311           0 : }
     312             : 
     313           0 : static void conic_intersect_ray(const SkPoint a[3], SkScalar weight, const SkDLine& ray,
     314             :         SkIntersections* i) {
     315             :     SkDConic conic;
     316           0 :     conic.set(a, weight);
     317           0 :     i->intersectRay(conic, ray);
     318           0 : }
     319             : 
     320           0 : static void cubic_intersect_ray(const SkPoint a[4], SkScalar , const SkDLine& ray,
     321             :         SkIntersections* i) {
     322             :     SkDCubic cubic;
     323           0 :     cubic.set(a);
     324           0 :     i->intersectRay(cubic, ray);
     325           0 : }
     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           0 : static void dline_intersect_ray(const SkDCurve& c, const SkDLine& ray,  SkIntersections* i) {
     337           0 :     i->intersectRay(c.fLine, ray);
     338           0 : }
     339             : 
     340           0 : static void dquad_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
     341           0 :     i->intersectRay(c.fQuad, ray);
     342           0 : }
     343             : 
     344           0 : static void dconic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
     345           0 :     i->intersectRay(c.fConic, ray);
     346           0 : }
     347             : 
     348           0 : static void dcubic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
     349           0 :     i->intersectRay(c.fCubic, ray);
     350           0 : }
     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           0 : static int line_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
     361             :     SkDLine line;
     362           0 :     roots[0] = SkIntersections::HorizontalIntercept(line.set(a), y);
     363           0 :     return between(0, roots[0], 1);
     364             : }
     365             : 
     366           0 : static int line_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
     367             :     SkDLine line;
     368           0 :     roots[0] = SkIntersections::VerticalIntercept(line.set(a), x);
     369           0 :     return between(0, roots[0], 1);
     370             : }
     371             : 
     372           0 : static int quad_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
     373             :     SkDQuad quad;
     374           0 :     return SkIntersections::HorizontalIntercept(quad.set(a), y, roots);
     375             : }
     376             : 
     377           0 : static int quad_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
     378             :     SkDQuad quad;
     379           0 :     return SkIntersections::VerticalIntercept(quad.set(a), x, roots);
     380             : }
     381             : 
     382           0 : static int conic_intercept_h(const SkPoint a[2], SkScalar w, SkScalar y, double* roots) {
     383             :     SkDConic conic;
     384           0 :     return SkIntersections::HorizontalIntercept(conic.set(a, w), y, roots);
     385             : }
     386             : 
     387           0 : static int conic_intercept_v(const SkPoint a[2], SkScalar w, SkScalar x, double* roots) {
     388             :     SkDConic conic;
     389           0 :     return SkIntersections::VerticalIntercept(conic.set(a, w), x, roots);
     390             : }
     391             : 
     392           0 : static int cubic_intercept_h(const SkPoint a[3], SkScalar , SkScalar y, double* roots) {
     393             :     SkDCubic cubic;
     394           0 :     return cubic.set(a).horizontalIntersect(y, roots);
     395             : }
     396             : 
     397           0 : static int cubic_intercept_v(const SkPoint a[3], SkScalar , SkScalar x, double* roots) {
     398             :     SkDCubic cubic;
     399           0 :     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