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. This 63 * has been templated so that the compiler can easliy unroll the loop 64 * and reorder to avoid stalling for loads. The assumption is that a 65 * path renderer will have a small fixed number of vertices that it 66 * uploads for each quad. 67 * 68 * N is the number of vertices. 69 * STRIDE is the size of each vertex. 70 * UV_OFFSET is the offset of the UV values within each vertex. 71 * vertices is a pointer to the first vertex. 72 */ 73 template <int N, size_t STRIDE, size_t UV_OFFSET> 74 void apply(const void* vertices) const { 75 intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices); 76 intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + UV_OFFSET; 77 float sx = fM[0]; 78 float kx = fM[1]; 79 float tx = fM[2]; 80 float ky = fM[3]; 81 float sy = fM[4]; 82 float ty = fM[5]; 83 for (int i = 0; i < N; ++i) { 84 const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr); 85 SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr); 86 uv->fX = sx * xy->fX + kx * xy->fY + tx; 87 uv->fY = ky * xy->fX + sy * xy->fY + ty; 88 xyPtr += STRIDE; 89 uvPtr += STRIDE; 90 } 91 } 92 private: 93 float fM[6]; 94 }; 95 96 // Input is 3 control points and a weight for a bezier conic. Calculates the 97 // three linear functionals (K,L,M) that represent the implicit equation of the 98 // conic, k^2 - lm. 99 // 100 // Output: klm holds the linear functionals K,L,M as row vectors: 101 // 102 // | ..K.. | | x | | k | 103 // | ..L.. | * | y | == | l | 104 // | ..M.. | | 1 | | m | 105 // 106 void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm); 107 108 // Converts a cubic into a sequence of quads. If working in device space 109 // use tolScale = 1, otherwise set based on stretchiness of the matrix. The 110 // result is sets of 3 points in quads. 111 void convertCubicToQuads(const SkPoint p[4], 112 SkScalar tolScale, 113 SkTArray<SkPoint, true>* quads); 114 115 // When we approximate a cubic {a,b,c,d} with a quadratic we may have to 116 // ensure that the new control point lies between the lines ab and cd. The 117 // convex path renderer requires this. It starts with a path where all the 118 // control points taken together form a convex polygon. It relies on this 119 // property and the quadratic approximation of cubics step cannot alter it. 120 // This variation enforces this constraint. The cubic must be simple and dir 121 // must specify the orientation of the contour containing the cubic. 122 void convertCubicToQuadsConstrainToTangents(const SkPoint p[4], 123 SkScalar tolScale, 124 SkPathPriv::FirstDirection dir, 125 SkTArray<SkPoint, true>* quads); 126 127 enum class ExcludedTerm { 128 kNonInvertible, 129 kQuadraticTerm, 130 kLinearTerm 131 }; 132 133 // Computes the inverse-transpose of the cubic's power basis matrix, after removing a specific 134 // row of coefficients. 135 // 136 // E.g. if the cubic is defined in power basis form as follows: 137 // 138 // | x3 y3 0 | 139 // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | x2 y2 0 | 140 // | x1 y1 0 | 141 // | x0 y0 1 | 142 // 143 // And the excluded term is "kQuadraticTerm", then the resulting inverse-transpose will be: 144 // 145 // | x3 y3 0 | -1 T 146 // | x1 y1 0 | 147 // | x0 y0 1 | 148 // 149 // (The term to exclude is chosen based on maximizing the resulting matrix determinant.) 150 // 151 // This can be used to find the KLM linear functionals: 152 // 153 // | ..K.. | | ..kcoeffs.. | 154 // | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix 155 // | ..M.. | | ..mcoeffs.. | 156 // 157 // NOTE: the same term that was excluded here must also be removed from the corresponding column 158 // of the klmcoeffs matrix. 159 // 160 // Returns which row of coefficients was removed, or kNonInvertible if the cubic was degenerate. 161 ExcludedTerm calcCubicInverseTransposePowerBasisMatrix(const SkPoint p[4], SkMatrix* out); 162 163 // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the 164 // curve (when facing in the direction of increasing parameter values) will be the area that 165 // satisfies: 166 // 167 // k^3 < l*m 168 // 169 // Output: 170 // 171 // klm: Holds the linear functionals K,L,M as row vectors: 172 // 173 // | ..K.. | | x | | k | 174 // | ..L.. | * | y | == | l | 175 // | ..M.. | | 1 | | m | 176 // 177 // NOTE: the KLM lines are calculated in the same space as the input control points. If you 178 // transform the points the lines will also need to be transformed. This can be done by mapping 179 // the lines with the inverse-transpose of the matrix used to map the points. 180 // 181 // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M 182 // intersect with K (See SkClassifyCubic). 183 // 184 // Returns the cubic's classification. 185 SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]); 186 187 // Chops the cubic bezier passed in by src, at the double point (intersection point) 188 // if the curve is a cubic loop. If it is a loop, there will be two parametric values for 189 // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1. 190 // Return value: 191 // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics, 192 // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr 193 // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics, 194 // dst[0..3] and dst[3..6] if dst is not nullptr 195 // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic, 196 // src[0..3] 197 // 198 // Output: 199 // 200 // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().) 201 // 202 // loopIndex: This value will tell the caller which of the chopped sections (if any) are the 203 // actual loop. A value of -1 means there is no loop section. The caller can then use 204 // this value to decide how/if they want to flip the orientation of this section. 205 // The flip should be done by negating the k and l values as follows: 206 // 207 // KLM.postScale(-1, -1) 208 int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm, 209 int* loopIndex); 210 211 // When tessellating curved paths into linear segments, this defines the maximum distance 212 // in screen space which a segment may deviate from the mathmatically correct value. 213 // Above this value, the segment will be subdivided. 214 // This value was chosen to approximate the supersampling accuracy of the raster path (16 215 // samples, or one quarter pixel). 216 static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25); 217 218 // We guarantee that no quad or cubic will ever produce more than this many points 219 static const int kMaxPointsPerCurve = 1 << 10; 220 }; 221 #endif 222
