Line data Source code
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 "SkRect.h"
12 : #include "SkPathPriv.h"
13 : #include "SkTArray.h"
14 :
15 : class SkMatrix;
16 :
17 : /**
18 : * Utilities for evaluating paths.
19 : */
20 : namespace GrPathUtils {
21 : SkScalar scaleToleranceToSrc(SkScalar devTol,
22 : const SkMatrix& viewM,
23 : const SkRect& pathBounds);
24 :
25 : /// Since we divide by tol if we're computing exact worst-case bounds,
26 : /// very small tolerances will be increased to gMinCurveTol.
27 : int worstCasePointCount(const SkPath&,
28 : int* subpaths,
29 : SkScalar tol);
30 :
31 : /// Since we divide by tol if we're computing exact worst-case bounds,
32 : /// very small tolerances will be increased to gMinCurveTol.
33 : uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
34 :
35 : uint32_t generateQuadraticPoints(const SkPoint& p0,
36 : const SkPoint& p1,
37 : const SkPoint& p2,
38 : SkScalar tolSqd,
39 : SkPoint** points,
40 : uint32_t pointsLeft);
41 :
42 : /// Since we divide by tol if we're computing exact worst-case bounds,
43 : /// very small tolerances will be increased to gMinCurveTol.
44 : uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
45 :
46 : uint32_t generateCubicPoints(const SkPoint& p0,
47 : const SkPoint& p1,
48 : const SkPoint& p2,
49 : const SkPoint& p3,
50 : SkScalar tolSqd,
51 : SkPoint** points,
52 : uint32_t pointsLeft);
53 :
54 : // A 2x3 matrix that goes from the 2d space coordinates to UV space where
55 : // u^2-v = 0 specifies the quad. The matrix is determined by the control
56 : // points of the quadratic.
57 : class QuadUVMatrix {
58 : public:
59 : QuadUVMatrix() {}
60 : // Initialize the matrix from the control pts
61 0 : QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); }
62 : void set(const SkPoint controlPts[3]);
63 :
64 : /**
65 : * Applies the matrix to vertex positions to compute UV coords. This
66 : * has been templated so that the compiler can easliy unroll the loop
67 : * and reorder to avoid stalling for loads. The assumption is that a
68 : * path renderer will have a small fixed number of vertices that it
69 : * uploads for each quad.
70 : *
71 : * N is the number of vertices.
72 : * STRIDE is the size of each vertex.
73 : * UV_OFFSET is the offset of the UV values within each vertex.
74 : * vertices is a pointer to the first vertex.
75 : */
76 : template <int N, size_t STRIDE, size_t UV_OFFSET>
77 0 : void apply(const void* vertices) const {
78 0 : intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
79 0 : intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + UV_OFFSET;
80 0 : float sx = fM[0];
81 0 : float kx = fM[1];
82 0 : float tx = fM[2];
83 0 : float ky = fM[3];
84 0 : float sy = fM[4];
85 0 : float ty = fM[5];
86 0 : for (int i = 0; i < N; ++i) {
87 0 : const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr);
88 0 : SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr);
89 0 : uv->fX = sx * xy->fX + kx * xy->fY + tx;
90 0 : uv->fY = ky * xy->fX + sy * xy->fY + ty;
91 0 : xyPtr += STRIDE;
92 0 : uvPtr += STRIDE;
93 : }
94 0 : }
95 : private:
96 : float fM[6];
97 : };
98 :
99 : // Input is 3 control points and a weight for a bezier conic. Calculates the
100 : // three linear functionals (K,L,M) that represent the implicit equation of the
101 : // conic, k^2 - lm.
102 : //
103 : // Output: klm holds the linear functionals K,L,M as row vectors:
104 : //
105 : // | ..K.. | | x | | k |
106 : // | ..L.. | * | y | == | l |
107 : // | ..M.. | | 1 | | m |
108 : //
109 : void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm);
110 :
111 : // Converts a cubic into a sequence of quads. If working in device space
112 : // use tolScale = 1, otherwise set based on stretchiness of the matrix. The
113 : // result is sets of 3 points in quads.
114 : void convertCubicToQuads(const SkPoint p[4],
115 : SkScalar tolScale,
116 : SkTArray<SkPoint, true>* quads);
117 :
118 : // When we approximate a cubic {a,b,c,d} with a quadratic we may have to
119 : // ensure that the new control point lies between the lines ab and cd. The
120 : // convex path renderer requires this. It starts with a path where all the
121 : // control points taken together form a convex polygon. It relies on this
122 : // property and the quadratic approximation of cubics step cannot alter it.
123 : // This variation enforces this constraint. The cubic must be simple and dir
124 : // must specify the orientation of the contour containing the cubic.
125 : void convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
126 : SkScalar tolScale,
127 : SkPathPriv::FirstDirection dir,
128 : SkTArray<SkPoint, true>* quads);
129 :
130 : // Chops the cubic bezier passed in by src, at the double point (intersection point)
131 : // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
132 : // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
133 : // Return value:
134 : // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics,
135 : // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr
136 : // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
137 : // dst[0..3] and dst[3..6] if dst is not nullptr
138 : // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
139 : // dst[0..3] if dst is not nullptr
140 : //
141 : // Optional KLM Calculation:
142 : // The function can also return the KLM linear functionals for the cubic implicit form of
143 : // k^3 - lm. This can be shared by all chopped cubics.
144 : //
145 : // Output:
146 : //
147 : // klm: Holds the linear functionals K,L,M as row vectors:
148 : //
149 : // | ..K.. | | x | | k |
150 : // | ..L.. | * | y | == | l |
151 : // | ..M.. | | 1 | | m |
152 : //
153 : // loopIndex: This value will tell the caller which of the chopped sections (if any) are the
154 : // actual loop. A value of -1 means there is no loop section. The caller can then use
155 : // this value to decide how/if they want to flip the orientation of this section.
156 : // The flip should be done by negating the k and l values as follows:
157 : //
158 : // KLM.postScale(-1, -1)
159 : //
160 : // Notice that the KLM lines are calculated in the same space as the input control points.
161 : // If you transform the points the lines will also need to be transformed. This can be done
162 : // by mapping the lines with the inverse-transpose of the matrix used to map the points.
163 : int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = nullptr,
164 : SkMatrix* klm = nullptr, int* loopIndex = nullptr);
165 :
166 : // When tessellating curved paths into linear segments, this defines the maximum distance
167 : // in screen space which a segment may deviate from the mathmatically correct value.
168 : // Above this value, the segment will be subdivided.
169 : // This value was chosen to approximate the supersampling accuracy of the raster path (16
170 : // samples, or one quarter pixel).
171 : static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
172 : };
173 : #endif
|