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 // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the 128 // curve (when facing in the direction of increasing parameter values) will be the area that 129 // satisfies: 130 // 131 // k^3 < l*m 132 // 133 // Output: 134 // 135 // klm: Holds the linear functionals K,L,M as row vectors: 136 // 137 // | ..K.. | | x | | k | 138 // | ..L.. | * | y | == | l | 139 // | ..M.. | | 1 | | m | 140 // 141 // NOTE: the KLM lines are calculated in the same space as the input control points. If you 142 // transform the points the lines will also need to be transformed. This can be done by mapping 143 // the lines with the inverse-transpose of the matrix used to map the points. 144 // 145 // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M 146 // intersect with K (See SkClassifyCubic). 147 // 148 // Returns the cubic's classification. 149 SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]); 150 151 // Chops the cubic bezier passed in by src, at the double point (intersection point) 152 // if the curve is a cubic loop. If it is a loop, there will be two parametric values for 153 // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1. 154 // Return value: 155 // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics, 156 // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr 157 // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics, 158 // dst[0..3] and dst[3..6] if dst is not nullptr 159 // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic, 160 // src[0..3] 161 // 162 // Output: 163 // 164 // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().) 165 // 166 // loopIndex: This value will tell the caller which of the chopped sections (if any) are the 167 // actual loop. A value of -1 means there is no loop section. The caller can then use 168 // this value to decide how/if they want to flip the orientation of this section. 169 // The flip should be done by negating the k and l values as follows: 170 // 171 // KLM.postScale(-1, -1) 172 int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm, 173 int* loopIndex); 174 175 // When tessellating curved paths into linear segments, this defines the maximum distance 176 // in screen space which a segment may deviate from the mathmatically correct value. 177 // Above this value, the segment will be subdivided. 178 // This value was chosen to approximate the supersampling accuracy of the raster path (16 179 // samples, or one quarter pixel). 180 static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25); 181 182 // We guarantee that no quad or cubic will ever produce more than this many points 183 static const int kMaxPointsPerCurve = 1 << 10; 184 }; 185 #endif 186
