src/third_party/skia/src/gpu/GrPathUtils.h

   1 /*
   2  * Copyright 2011 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
   8 #ifndef GrPathUtils_DEFINED
   9 #define GrPathUtils_DEFINED
  10
  11 #include "GrPoint.h"
  12 #include "SkRect.h"
  13 #include "SkPath.h"
  14 #include "SkTArray.h"
  15
  16 class SkMatrix;
  17
  18 /**
  19  *  Utilities for evaluating paths.
  20  */
  21 namespace GrPathUtils {
  22     SkScalar scaleToleranceToSrc(SkScalar devTol,
  23                                  const SkMatrix& viewM,
  24                                  const SkRect& pathBounds);
  25
  26     /// Since we divide by tol if we're computing exact worst-case bounds,
  27     /// very small tolerances will be increased to gMinCurveTol.
  28     int worstCasePointCount(const SkPath&,
  29                             int* subpaths,
  30                             SkScalar tol);
  31
  32     /// Since we divide by tol if we're computing exact worst-case bounds,
  33     /// very small tolerances will be increased to gMinCurveTol.
  34     uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
  35
  36     uint32_t generateQuadraticPoints(const SkPoint& p0,
  37                                      const SkPoint& p1,
  38                                      const SkPoint& p2,
  39                                      SkScalar tolSqd,
  40                                      SkPoint** points,
  41                                      uint32_t pointsLeft);
  42
  43     /// Since we divide by tol if we're computing exact worst-case bounds,
  44     /// very small tolerances will be increased to gMinCurveTol.
  45     uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
  46
  47     uint32_t generateCubicPoints(const SkPoint& p0,
  48                                  const SkPoint& p1,
  49                                  const SkPoint& p2,
  50                                  const SkPoint& p3,
  51                                  SkScalar tolSqd,
  52                                  SkPoint** points,
  53                                  uint32_t pointsLeft);
  54
  55     // A 2x3 matrix that goes from the 2d space coordinates to UV space where
  56     // u^2-v = 0 specifies the quad. The matrix is determined by the control
  57     // points of the quadratic.
  58     class QuadUVMatrix {
  59     public:
  60         QuadUVMatrix() {};
  61         // Initialize the matrix from the control pts
  62         QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); }
  63         void set(const SkPoint controlPts[3]);
  64
  65         /**
  66          * Applies the matrix to vertex positions to compute UV coords. This
  67          * has been templated so that the compiler can easliy unroll the loop
  68          * and reorder to avoid stalling for loads. The assumption is that a
  69          * path renderer will have a small fixed number of vertices that it
  70          * uploads for each quad.
  71          *
  72          * N is the number of vertices.
  73          * STRIDE is the size of each vertex.
  74          * UV_OFFSET is the offset of the UV values within each vertex.
  75          * vertices is a pointer to the first vertex.
  76          */
  77         template <int N, size_t STRIDE, size_t UV_OFFSET>
  78         void apply(const void* vertices) {
  79             intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
  80             intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + UV_OFFSET;
  81             float sx = fM[0];
  82             float kx = fM[1];
  83             float tx = fM[2];
  84             float ky = fM[3];
  85             float sy = fM[4];
  86             float ty = fM[5];
  87             for (int i = 0; i < N; ++i) {
  88                 const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr);
  89                 SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr);
  90                 uv->fX = sx * xy->fX + kx * xy->fY + tx;
  91                 uv->fY = ky * xy->fX + sy * xy->fY + ty;
  92                 xyPtr += STRIDE;
  93                 uvPtr += STRIDE;
  94             }
  95         }
  96     private:
  97         float fM[6];
  98     };
  99
 100     // Input is 3 control points and a weight for a bezier conic. Calculates the
 101     // three linear functionals (K,L,M) that represent the implicit equation of the
 102     // conic, K^2 - LM.
 103     //
 104     // Output:
 105     //  K = (klm[0], klm[1], klm[2])
 106     //  L = (klm[3], klm[4], klm[5])
 107     //  M = (klm[6], klm[7], klm[8])
 108     void getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]);
 109
 110     // Converts a cubic into a sequence of quads. If working in device space
 111     // use tolScale = 1, otherwise set based on stretchiness of the matrix. The
 112     // result is sets of 3 points in quads (TODO: share endpoints in returned
 113     // array)
 114     // When we approximate a cubic {a,b,c,d} with a quadratic we may have to
 115     // ensure that the new control point lies between the lines ab and cd. The
 116     // convex path renderer requires this. It starts with a path where all the
 117     // control points taken together form a convex polygon. It relies on this
 118     // property and the quadratic approximation of cubics step cannot alter it.
 119     // Setting constrainWithinTangents to true enforces this property. When this
 120     // is true the cubic must be simple and dir must specify the orientation of
 121     // the cubic. Otherwise, dir is ignored.
 122     void convertCubicToQuads(const SkPoint p[4],
 123                              SkScalar tolScale,
 124                              bool constrainWithinTangents,
 125                              SkPath::Direction dir,
 126                              SkTArray<SkPoint, true>* quads);
 127
 128     // Chops the cubic bezier passed in by src, at the double point (intersection point)
 129     // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
 130     // the double point: ls and ms. We chop the cubic at these values if they are between 0 and 1.
 131     // Return value:
 132     // Value of 3: ls and ms are both between (0,1), and dst will contain the three cubics,
 133     //             dst[0..3], dst[3..6], and dst[6..9] if dst is not NULL
 134     // Value of 2: Only one of ls and ms are between (0,1), and dst will contain the two cubics,
 135     //             dst[0..3] and dst[3..6] if dst is not NULL
 136     // Value of 1: Neither ls or ms are between (0,1), and dst will contain the one original cubic,
 137     //             dst[0..3] if dst is not NULL
 138     //
 139     // Optional KLM Calculation:
 140     // The function can also return the KLM linear functionals for the chopped cubic implicit form
 141     // of K^3 - LM.
 142     // It will calculate a single set of KLM values that can be shared by all sub cubics, except
 143     // for the subsection that is "the loop" the K and L values need to be negated.
 144     // Output:
 145     // klm:     Holds the values for the linear functionals as:
 146     //          K = (klm[0], klm[1], klm[2])
 147     //          L = (klm[3], klm[4], klm[5])
 148     //          M = (klm[6], klm[7], klm[8])
 149     // klm_rev: These values are flags for the corresponding sub cubic saying whether or not
 150     //          the K and L values need to be flipped. A value of -1.f means flip K and L and
 151     //          a value of 1.f means do nothing.
 152     //          *****DO NOT FLIP M, JUST K AND L*****
 153     //
 154     // Notice that the klm lines are calculated in the same space as the input control points.
 155     // If you transform the points the lines will also need to be transformed. This can be done
 156     // by mapping the lines with the inverse-transpose of the matrix used to map the points.
 157     int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = NULL,
 158                                     SkScalar klm[9] = NULL, SkScalar klm_rev[3] = NULL);
 159
 160     // Input is p which holds the 4 control points of a non-rational cubic Bezier curve.
 161     // Output is the coefficients of the three linear functionals K, L, & M which
 162     // represent the implicit form of the cubic as f(x,y,w) = K^3 - LM. The w term
 163     // will always be 1. The output is stored in the array klm, where the values are:
 164     // K = (klm[0], klm[1], klm[2])
 165     // L = (klm[3], klm[4], klm[5])
 166     // M = (klm[6], klm[7], klm[8])
 167     //
 168     // Notice that the klm lines are calculated in the same space as the input control points.
 169     // If you transform the points the lines will also need to be transformed. This can be done
 170     // by mapping the lines with the inverse-transpose of the matrix used to map the points.
 171     void getCubicKLM(const SkPoint p[4], SkScalar klm[9]);
 172 };
 173 #endif