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