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 // Converts the given line to a cubic bezier.
137 // NOTE: This method interpolates at 1/3 and 2/3, but if suitable in context, the cubic
138 // {p0, p0, p1, p1} may also work.
writeLineAsCubic(SkPoint startPt,SkPoint endPt,skgpu::VertexWriter * writer)139 inline void writeLineAsCubic(SkPoint startPt, SkPoint endPt, skgpu::VertexWriter* writer) {
140 using grvx::float2, skvx::bit_pun;
141 float2 p0 = bit_pun<float2>(startPt);
142 float2 p1 = bit_pun<float2>(endPt);
143 float2 v = (p1 - p0) * (1/3.f);
144 *writer << p0 << (p0 + v) << (p1 - v) << p1;
145 }
146
147 // Converts the given quadratic bezier to a cubic.
writeQuadAsCubic(const SkPoint p[3],skgpu::VertexWriter * writer)148 inline void writeQuadAsCubic(const SkPoint p[3], skgpu::VertexWriter* writer) {
149 using grvx::float2, skvx::bit_pun;
150 float2 p0 = bit_pun<float2>(p[0]);
151 float2 p1 = bit_pun<float2>(p[1]);
152 float2 p2 = bit_pun<float2>(p[2]);
153 float2 c = p1 * (2/3.f);
154 *writer << p0 << (p0*(1/3.f) + c) << (p2 * (1/3.f) + c) << p2;
155 }
convertQuadToCubic(const SkPoint p[3],SkPoint out[4])156 inline void convertQuadToCubic(const SkPoint p[3], SkPoint out[4]) {
157 skgpu::VertexWriter writer(out);
158 writeQuadAsCubic(p, &writer);
159 }
160
161 // Finds 0, 1, or 2 T values at which to chop the given curve in order to guarantee the resulting
162 // cubics are convex and rotate no more than 180 degrees.
163 //
164 // - If the cubic is "serpentine", then the T values are any inflection points in [0 < T < 1].
165 // - If the cubic is linear, then the T values are any 180-degree cusp points in [0 < T < 1].
166 // - Otherwise the T value is the point at which rotation reaches 180 degrees, iff in [0 < T < 1].
167 //
168 // 'areCusps' is set to true if the chop point occurred at a cusp (within tolerance), or if the chop
169 // point(s) occurred at 180-degree turnaround points on a degenerate flat line.
170 int findCubicConvex180Chops(const SkPoint[], float T[2], bool* areCusps);
171
172 // Returns true if the given conic (or quadratic) has a cusp point. The w value is not necessary in
173 // determining this. If there is a cusp, it can be found at the midtangent.
conicHasCusp(const SkPoint p[3])174 inline bool conicHasCusp(const SkPoint p[3]) {
175 SkVector a = p[1] - p[0];
176 SkVector b = p[2] - p[1];
177 // A conic of any class can only have a cusp if it is a degenerate flat line with a 180 degree
178 // turnarund. To detect this, the beginning and ending tangents must be parallel
179 // (a.cross(b) == 0) and pointing in opposite directions (a.dot(b) < 0).
180 return a.cross(b) == 0 && a.dot(b) < 0;
181 }
182
183 } // namespace GrPathUtils
184
185 #endif
186