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 "SkGeometry.h" 12 #include "SkRect.h" 13 #include "SkPathPriv.h" 14 #include "SkTArray.h" 15 16 class SkMatrix; 17 18 /** 19 * Utilities for evaluating paths. 20 */ 21 namespace GrPathUtils { 22 // Very small tolerances will be increased to a minimum threshold value, to avoid division 23 // problems in subsequent math. 24 SkScalar scaleToleranceToSrc(SkScalar devTol, 25 const SkMatrix& viewM, 26 const SkRect& pathBounds); 27 28 int worstCasePointCount(const SkPath&, 29 int* subpaths, 30 SkScalar tol); 31 32 uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol); 33 34 uint32_t generateQuadraticPoints(const SkPoint& p0, 35 const SkPoint& p1, 36 const SkPoint& p2, 37 SkScalar tolSqd, 38 SkPoint** points, 39 uint32_t pointsLeft); 40 41 uint32_t cubicPointCount(const SkPoint points[], SkScalar tol); 42 43 uint32_t generateCubicPoints(const SkPoint& p0, 44 const SkPoint& p1, 45 const SkPoint& p2, 46 const SkPoint& p3, 47 SkScalar tolSqd, 48 SkPoint** points, 49 uint32_t pointsLeft); 50 51 // A 2x3 matrix that goes from the 2d space coordinates to UV space where 52 // u^2-v = 0 specifies the quad. The matrix is determined by the control 53 // points of the quadratic. 54 class QuadUVMatrix { 55 public: 56 QuadUVMatrix() {} 57 // Initialize the matrix from the control pts 58 QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); } 59 void set(const SkPoint controlPts[3]); 60 61 /** 62 * Applies the matrix to vertex positions to compute UV coords. 63 * 64 * vertices is a pointer to the first vertex. 65 * vertexCount is the number of vertices. 66 * stride is the size of each vertex. 67 * uvOffset is the offset of the UV values within each vertex. 68 */ 69 void apply(void* vertices, int vertexCount, size_t stride, size_t uvOffset) const { 70 intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices); 71 intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + uvOffset; 72 float sx = fM[0]; 73 float kx = fM[1]; 74 float tx = fM[2]; 75 float ky = fM[3]; 76 float sy = fM[4]; 77 float ty = fM[5]; 78 for (int i = 0; i < vertexCount; ++i) { 79 const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr); 80 SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr); 81 uv->fX = sx * xy->fX + kx * xy->fY + tx; 82 uv->fY = ky * xy->fX + sy * xy->fY + ty; 83 xyPtr += stride; 84 uvPtr += stride; 85 } 86 } 87 private: 88 float fM[6]; 89 }; 90 91 // Input is 3 control points and a weight for a bezier conic. Calculates the 92 // three linear functionals (K,L,M) that represent the implicit equation of the 93 // conic, k^2 - lm. 94 // 95 // Output: klm holds the linear functionals K,L,M as row vectors: 96 // 97 // | ..K.. | | x | | k | 98 // | ..L.. | * | y | == | l | 99 // | ..M.. | | 1 | | m | 100 // 101 void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm); 102 103 // Converts a cubic into a sequence of quads. If working in device space 104 // use tolScale = 1, otherwise set based on stretchiness of the matrix. The 105 // result is sets of 3 points in quads. This will preserve the starting and 106 // ending tangent vectors (modulo FP precision). 107 void convertCubicToQuads(const SkPoint p[4], 108 SkScalar tolScale, 109 SkTArray<SkPoint, true>* quads); 110 111 // When we approximate a cubic {a,b,c,d} with a quadratic we may have to 112 // ensure that the new control point lies between the lines ab and cd. The 113 // convex path renderer requires this. It starts with a path where all the 114 // control points taken together form a convex polygon. It relies on this 115 // property and the quadratic approximation of cubics step cannot alter it. 116 // This variation enforces this constraint. The cubic must be simple and dir 117 // must specify the orientation of the contour containing the cubic. 118 void convertCubicToQuadsConstrainToTangents(const SkPoint p[4], 119 SkScalar tolScale, 120 SkPathPriv::FirstDirection dir, 121 SkTArray<SkPoint, true>* quads); 122 123 enum class ExcludedTerm { 124 kNonInvertible, 125 kQuadraticTerm, 126 kLinearTerm 127 }; 128 129 // Computes the inverse-transpose of the cubic's power basis matrix, after removing a specific 130 // row of coefficients. 131 // 132 // E.g. if the cubic is defined in power basis form as follows: 133 // 134 // | x3 y3 0 | 135 // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | x2 y2 0 | 136 // | x1 y1 0 | 137 // | x0 y0 1 | 138 // 139 // And the excluded term is "kQuadraticTerm", then the resulting inverse-transpose will be: 140 // 141 // | x3 y3 0 | -1 T 142 // | x1 y1 0 | 143 // | x0 y0 1 | 144 // 145 // (The term to exclude is chosen based on maximizing the resulting matrix determinant.) 146 // 147 // This can be used to find the KLM linear functionals: 148 // 149 // | ..K.. | | ..kcoeffs.. | 150 // | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix 151 // | ..M.. | | ..mcoeffs.. | 152 // 153 // NOTE: the same term that was excluded here must also be removed from the corresponding column 154 // of the klmcoeffs matrix. 155 // 156 // Returns which row of coefficients was removed, or kNonInvertible if the cubic was degenerate. 157 ExcludedTerm calcCubicInverseTransposePowerBasisMatrix(const SkPoint p[4], SkMatrix* out); 158 159 // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the 160 // curve (when facing in the direction of increasing parameter values) will be the area that 161 // satisfies: 162 // 163 // k^3 < l*m 164 // 165 // Output: 166 // 167 // klm: Holds the linear functionals K,L,M as row vectors: 168 // 169 // | ..K.. | | x | | k | 170 // | ..L.. | * | y | == | l | 171 // | ..M.. | | 1 | | m | 172 // 173 // NOTE: the KLM lines are calculated in the same space as the input control points. If you 174 // transform the points the lines will also need to be transformed. This can be done by mapping 175 // the lines with the inverse-transpose of the matrix used to map the points. 176 // 177 // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M 178 // intersect with K (See SkClassifyCubic). 179 // 180 // Returns the cubic's classification. 181 SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]); 182 183 // Chops the cubic bezier passed in by src, at the double point (intersection point) 184 // if the curve is a cubic loop. If it is a loop, there will be two parametric values for 185 // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1. 186 // Return value: 187 // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics, 188 // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr 189 // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics, 190 // dst[0..3] and dst[3..6] if dst is not nullptr 191 // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic, 192 // src[0..3] 193 // 194 // Output: 195 // 196 // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().) 197 // 198 // loopIndex: This value will tell the caller which of the chopped sections (if any) are the 199 // actual loop. A value of -1 means there is no loop section. The caller can then use 200 // this value to decide how/if they want to flip the orientation of this section. 201 // The flip should be done by negating the k and l values as follows: 202 // 203 // KLM.postScale(-1, -1) 204 int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm, 205 int* loopIndex); 206 207 // When tessellating curved paths into linear segments, this defines the maximum distance 208 // in screen space which a segment may deviate from the mathmatically correct value. 209 // Above this value, the segment will be subdivided. 210 // This value was chosen to approximate the supersampling accuracy of the raster path (16 211 // samples, or one quarter pixel). 212 static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25); 213 214 // We guarantee that no quad or cubic will ever produce more than this many points 215 static const int kMaxPointsPerCurve = 1 << 10; 216 }; 217 #endif 218