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