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