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