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
16class SkMatrix;
17
18/**
19 * Utilities for evaluating paths.
20 */
21namespace GrPathUtils {
22 // Very small tolerances will be increased to a minimum threshold value, to avoid division
23 // problems in subsequent math.
24 SkScalar scaleToleranceToSrc(SkScalar devTol,
25 const SkMatrix& viewM,
26 const SkRect& pathBounds);
27
28 int worstCasePointCount(const SkPath&,
29 int* subpaths,
30 SkScalar tol);
31
32 uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
33
34 uint32_t generateQuadraticPoints(const SkPoint& p0,
35 const SkPoint& p1,
36 const SkPoint& p2,
37 SkScalar tolSqd,
38 SkPoint** points,
39 uint32_t pointsLeft);
40
41 uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
42
43 uint32_t generateCubicPoints(const SkPoint& p0,
44 const SkPoint& p1,
45 const SkPoint& p2,
46 const SkPoint& p3,
47 SkScalar tolSqd,
48 SkPoint** points,
49 uint32_t pointsLeft);
50
51 // A 2x3 matrix that goes from the 2d space coordinates to UV space where
52 // u^2-v = 0 specifies the quad. The matrix is determined by the control
53 // points of the quadratic.
54 class QuadUVMatrix {
55 public:
56 QuadUVMatrix() {}
57 // Initialize the matrix from the control pts
58 QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); }
59 void set(const SkPoint controlPts[3]);
60
61 /**
62 * Applies the matrix to vertex positions to compute UV coords.
63 *
64 * vertices is a pointer to the first vertex.
65 * vertexCount is the number of vertices.
66 * stride is the size of each vertex.
67 * uvOffset is the offset of the UV values within each vertex.
68 */
69 void apply(void* vertices, int vertexCount, size_t stride, size_t uvOffset) const {
70 intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
71 intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + uvOffset;
72 float sx = fM[0];
73 float kx = fM[1];
74 float tx = fM[2];
75 float ky = fM[3];
76 float sy = fM[4];
77 float ty = fM[5];
78 for (int i = 0; i < vertexCount; ++i) {
79 const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr);
80 SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr);
81 uv->fX = sx * xy->fX + kx * xy->fY + tx;
82 uv->fY = ky * xy->fX + sy * xy->fY + ty;
83 xyPtr += stride;
84 uvPtr += stride;
85 }
86 }
87 private:
88 float fM[6];
89 };
90
91 // Input is 3 control points and a weight for a bezier conic. Calculates the
92 // three linear functionals (K,L,M) that represent the implicit equation of the
93 // conic, k^2 - lm.
94 //
95 // Output: klm holds the linear functionals K,L,M as row vectors:
96 //
97 // | ..K.. | | x | | k |
98 // | ..L.. | * | y | == | l |
99 // | ..M.. | | 1 | | m |
100 //
101 void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm);
102
103 // Converts a cubic into a sequence of quads. If working in device space
104 // use tolScale = 1, otherwise set based on stretchiness of the matrix. The
105 // result is sets of 3 points in quads. This will preserve the starting and
106 // ending tangent vectors (modulo FP precision).
107 void convertCubicToQuads(const SkPoint p[4],
108 SkScalar tolScale,
109 SkTArray<SkPoint, true>* quads);
110
111 // When we approximate a cubic {a,b,c,d} with a quadratic we may have to
112 // ensure that the new control point lies between the lines ab and cd. The
113 // convex path renderer requires this. It starts with a path where all the
114 // control points taken together form a convex polygon. It relies on this
115 // property and the quadratic approximation of cubics step cannot alter it.
116 // This variation enforces this constraint. The cubic must be simple and dir
117 // must specify the orientation of the contour containing the cubic.
118 void convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
119 SkScalar tolScale,
120 SkPathPriv::FirstDirection dir,
121 SkTArray<SkPoint, true>* quads);
122
123 enum class ExcludedTerm {
124 kNonInvertible,
125 kQuadraticTerm,
126 kLinearTerm
127 };
128
129 // Computes the inverse-transpose of the cubic's power basis matrix, after removing a specific
130 // row of coefficients.
131 //
132 // E.g. if the cubic is defined in power basis form as follows:
133 //
134 // | x3 y3 0 |
135 // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | x2 y2 0 |
136 // | x1 y1 0 |
137 // | x0 y0 1 |
138 //
139 // And the excluded term is "kQuadraticTerm", then the resulting inverse-transpose will be:
140 //
141 // | x3 y3 0 | -1 T
142 // | x1 y1 0 |
143 // | x0 y0 1 |
144 //
145 // (The term to exclude is chosen based on maximizing the resulting matrix determinant.)
146 //
147 // This can be used to find the KLM linear functionals:
148 //
149 // | ..K.. | | ..kcoeffs.. |
150 // | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix
151 // | ..M.. | | ..mcoeffs.. |
152 //
153 // NOTE: the same term that was excluded here must also be removed from the corresponding column
154 // of the klmcoeffs matrix.
155 //
156 // Returns which row of coefficients was removed, or kNonInvertible if the cubic was degenerate.
157 ExcludedTerm calcCubicInverseTransposePowerBasisMatrix(const SkPoint p[4], SkMatrix* out);
158
159 // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the
160 // curve (when facing in the direction of increasing parameter values) will be the area that
161 // satisfies:
162 //
163 // k^3 < l*m
164 //
165 // Output:
166 //
167 // klm: Holds the linear functionals K,L,M as row vectors:
168 //
169 // | ..K.. | | x | | k |
170 // | ..L.. | * | y | == | l |
171 // | ..M.. | | 1 | | m |
172 //
173 // NOTE: the KLM lines are calculated in the same space as the input control points. If you
174 // transform the points the lines will also need to be transformed. This can be done by mapping
175 // the lines with the inverse-transpose of the matrix used to map the points.
176 //
177 // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M
178 // intersect with K (See SkClassifyCubic).
179 //
180 // Returns the cubic's classification.
181 SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]);
182
183 // Chops the cubic bezier passed in by src, at the double point (intersection point)
184 // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
185 // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
186 // Return value:
187 // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics,
188 // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr
189 // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
190 // dst[0..3] and dst[3..6] if dst is not nullptr
191 // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
192 // src[0..3]
193 //
194 // Output:
195 //
196 // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().)
197 //
198 // loopIndex: This value will tell the caller which of the chopped sections (if any) are the
199 // actual loop. A value of -1 means there is no loop section. The caller can then use
200 // this value to decide how/if they want to flip the orientation of this section.
201 // The flip should be done by negating the k and l values as follows:
202 //
203 // KLM.postScale(-1, -1)
204 int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
205 int* loopIndex);
206
207 // When tessellating curved paths into linear segments, this defines the maximum distance
208 // in screen space which a segment may deviate from the mathmatically correct value.
209 // Above this value, the segment will be subdivided.
210 // This value was chosen to approximate the supersampling accuracy of the raster path (16
211 // samples, or one quarter pixel).
212 static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
213
214 // We guarantee that no quad or cubic will ever produce more than this many points
215 static const int kMaxPointsPerCurve = 1 << 10;
216};
217#endif
218