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