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 "include/core/SkRect.h" 12 #include "include/private/base/SkTArray.h" 13 #include "src/core/SkGeometry.h" 14 #include "src/core/SkPathPriv.h" 15 #include "src/gpu/BufferWriter.h" 16 17 class SkMatrix; 18 19 /** 20 * Utilities for evaluating paths. 21 */ 22 namespace GrPathUtils { 23 24 // When tessellating curved paths into linear segments, this defines the maximum distance in screen 25 // space which a segment may deviate from the mathematically correct value. Above this value, the 26 // segment will be subdivided. 27 // This value was chosen to approximate the supersampling accuracy of the raster path (16 samples, 28 // or one quarter pixel). 29 static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25); 30 31 // We guarantee that no quad or cubic will ever produce more than this many points 32 static const int kMaxPointsPerCurve = 1 << 10; 33 34 // Very small tolerances will be increased to a minimum threshold value, to avoid division problems 35 // in subsequent math. 36 SkScalar scaleToleranceToSrc(SkScalar devTol, 37 const SkMatrix& viewM, 38 const SkRect& pathBounds); 39 40 // Returns the maximum number of vertices required when using a recursive chopping algorithm to 41 // linearize the quadratic Bezier (e.g. generateQuadraticPoints below) to the given error tolerance. 42 // This is a power of two and will not exceed kMaxPointsPerCurve. 43 uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol); 44 45 // Returns the number of points actually written to 'points', will be <= to 'pointsLeft' 46 uint32_t generateQuadraticPoints(const SkPoint& p0, 47 const SkPoint& p1, 48 const SkPoint& p2, 49 SkScalar tolSqd, 50 SkPoint** points, 51 uint32_t pointsLeft); 52 53 // Returns the maximum number of vertices required when using a recursive chopping algorithm to 54 // linearize the cubic Bezier (e.g. generateQuadraticPoints below) to the given error tolerance. 55 // This is a power of two and will not exceed kMaxPointsPerCurve. 56 uint32_t cubicPointCount(const SkPoint points[], SkScalar tol); 57 58 // Returns the number of points actually written to 'points', will be <= to 'pointsLeft' 59 uint32_t generateCubicPoints(const SkPoint& p0, 60 const SkPoint& p1, 61 const SkPoint& p2, 62 const SkPoint& p3, 63 SkScalar tolSqd, 64 SkPoint** points, 65 uint32_t pointsLeft); 66 67 // A 2x3 matrix that goes from the 2d space coordinates to UV space where u^2-v = 0 specifies the 68 // quad. The matrix is determined by the control points of the quadratic. 69 class QuadUVMatrix { 70 public: QuadUVMatrix()71 QuadUVMatrix() {} 72 // Initialize the matrix from the control pts QuadUVMatrix(const SkPoint controlPts[3])73 QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); } 74 void set(const SkPoint controlPts[3]); 75 76 /** 77 * Applies the matrix to vertex positions to compute UV coords. 78 * 79 * vertices is a pointer to the first vertex. 80 * vertexCount is the number of vertices. 81 * stride is the size of each vertex. 82 * uvOffset is the offset of the UV values within each vertex. 83 */ apply(void * vertices,int vertexCount,size_t stride,size_t uvOffset)84 void apply(void* vertices, int vertexCount, size_t stride, size_t uvOffset) const { 85 intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices); 86 intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + uvOffset; 87 float sx = fM[0]; 88 float kx = fM[1]; 89 float tx = fM[2]; 90 float ky = fM[3]; 91 float sy = fM[4]; 92 float ty = fM[5]; 93 for (int i = 0; i < vertexCount; ++i) { 94 const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr); 95 SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr); 96 uv->fX = sx * xy->fX + kx * xy->fY + tx; 97 uv->fY = ky * xy->fX + sy * xy->fY + ty; 98 xyPtr += stride; 99 uvPtr += stride; 100 } 101 } 102 private: 103 float fM[6]; 104 }; 105 106 // Input is 3 control points and a weight for a bezier conic. Calculates the three linear 107 // functionals (K,L,M) that represent the implicit equation of the conic, k^2 - lm. 108 // 109 // Output: klm holds the linear functionals K,L,M as row vectors: 110 // 111 // | ..K.. | | x | | k | 112 // | ..L.. | * | y | == | l | 113 // | ..M.. | | 1 | | m | 114 // 115 void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm); 116 117 // Converts a cubic into a sequence of quads. If working in device space use tolScale = 1, otherwise 118 // set based on stretchiness of the matrix. The result is sets of 3 points in quads. This will 119 // preserve the starting and ending tangent vectors (modulo FP precision). 120 void convertCubicToQuads(const SkPoint p[4], 121 SkScalar tolScale, 122 SkTArray<SkPoint, true>* quads); 123 124 // When we approximate a cubic {a,b,c,d} with a quadratic we may have to ensure that the new control 125 // point lies between the lines ab and cd. The convex path renderer requires this. It starts with a 126 // path where all the control points taken together form a convex polygon. It relies on this 127 // property and the quadratic approximation of cubics step cannot alter it. This variation enforces 128 // this constraint. The cubic must be simple and dir must specify the orientation of the contour 129 // containing the cubic. 130 void convertCubicToQuadsConstrainToTangents(const SkPoint p[4], 131 SkScalar tolScale, 132 SkPathFirstDirection dir, 133 SkTArray<SkPoint, true>* quads); 134 135 } // namespace GrPathUtils 136 137 #endif 138