blob: e9dee7316a9a5938e5f0ace2075f9ae05b214c5f [file] [log] [blame]
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +00001/*
epoger@google.comec3ed6a2011-07-28 14:26:00 +00002 * 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.
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +00006 */
7
8#ifndef GrPathUtils_DEFINED
9#define GrPathUtils_DEFINED
10
Chris Daltonfebbffa2017-06-08 13:12:02 -060011#include "SkGeometry.h"
commit-bot@chromium.orgfd03d4a2013-07-17 21:39:42 +000012#include "SkRect.h"
reed026beb52015-06-10 14:23:15 -070013#include "SkPathPriv.h"
bsalomon@google.com69cc6ad2012-01-17 14:25:10 +000014#include "SkTArray.h"
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +000015
bsalomon@google.comb9086a02012-11-01 18:02:54 +000016class SkMatrix;
17
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +000018/**
19 * Utilities for evaluating paths.
20 */
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000021namespace GrPathUtils {
Brian Osman25294d72017-05-09 16:36:41 -040022 // Very small tolerances will be increased to a minimum threshold value, to avoid division
23 // problems in subsequent math.
bsalomon@google.com81712882012-11-01 17:12:34 +000024 SkScalar scaleToleranceToSrc(SkScalar devTol,
bsalomon@google.comb9086a02012-11-01 18:02:54 +000025 const SkMatrix& viewM,
commit-bot@chromium.orgfd03d4a2013-07-17 21:39:42 +000026 const SkRect& pathBounds);
tomhudson@google.comc10a8882011-06-28 15:19:32 +000027
bsalomon@google.com8d033a12012-04-27 15:52:53 +000028 int worstCasePointCount(const SkPath&,
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000029 int* subpaths,
bsalomon@google.com81712882012-11-01 17:12:34 +000030 SkScalar tol);
bsalomon@google.com19713172012-03-15 13:51:08 +000031
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000032 uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
bsalomon@google.com19713172012-03-15 13:51:08 +000033
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000034 uint32_t generateQuadraticPoints(const SkPoint& p0,
35 const SkPoint& p1,
36 const SkPoint& p2,
bsalomon@google.com81712882012-11-01 17:12:34 +000037 SkScalar tolSqd,
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000038 SkPoint** points,
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000039 uint32_t pointsLeft);
bsalomon@google.com19713172012-03-15 13:51:08 +000040
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000041 uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
bsalomon@google.com19713172012-03-15 13:51:08 +000042
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000043 uint32_t generateCubicPoints(const SkPoint& p0,
44 const SkPoint& p1,
45 const SkPoint& p2,
46 const SkPoint& p3,
bsalomon@google.com81712882012-11-01 17:12:34 +000047 SkScalar tolSqd,
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000048 SkPoint** points,
bsalomon@google.com181e9bd2011-09-07 18:42:30 +000049 uint32_t pointsLeft);
bsalomon@google.com19713172012-03-15 13:51:08 +000050
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:
Mike Kleinfc6c37b2016-09-27 09:34:10 -040056 QuadUVMatrix() {}
bsalomon@google.com19713172012-03-15 13:51:08 +000057 // Initialize the matrix from the control pts
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000058 QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); }
59 void set(const SkPoint controlPts[3]);
bsalomon@google.com19713172012-03-15 13:51:08 +000060
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>
joshualitt144c3c82015-11-30 12:30:13 -080074 void apply(const void* vertices) const {
bsalomon@google.com19713172012-03-15 13:51:08 +000075 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) {
commit-bot@chromium.org972f9cd2014-03-28 17:58:28 +000084 const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr);
85 SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr);
bsalomon@google.com19713172012-03-15 13:51:08 +000086 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
commit-bot@chromium.org13948402013-08-20 17:55:43 +000096 // 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
csmartdaltoncc261272017-03-23 13:38:45 -060098 // conic, k^2 - lm.
commit-bot@chromium.org13948402013-08-20 17:55:43 +000099 //
csmartdaltoncc261272017-03-23 13:38:45 -0600100 // 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);
bsalomon@google.coma51ab842012-07-10 19:53:34 +0000107
bsalomon@google.com69cc6ad2012-01-17 14:25:10 +0000108 // 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
bsalomon18fab302016-02-16 08:00:05 -0800110 // result is sets of 3 points in quads.
111 void convertCubicToQuads(const SkPoint p[4],
112 SkScalar tolScale,
113 SkTArray<SkPoint, true>* quads);
114
bsalomon@google.coma51ab842012-07-10 19:53:34 +0000115 // 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.
bsalomon18fab302016-02-16 08:00:05 -0800120 // 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);
commit-bot@chromium.org858638d2013-08-20 14:45:45 +0000126
Chris Daltonfebbffa2017-06-08 13:12:02 -0600127 // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the
128 // curve (when facing in the direction of increasing parameter values) will be the area that
129 // satisfies:
commit-bot@chromium.org858638d2013-08-20 14:45:45 +0000130 //
Chris Daltonfebbffa2017-06-08 13:12:02 -0600131 // k^3 < l*m
commit-bot@chromium.org858638d2013-08-20 14:45:45 +0000132 //
csmartdaltoncc261272017-03-23 13:38:45 -0600133 // Output:
134 //
135 // klm: Holds the linear functionals K,L,M as row vectors:
136 //
137 // | ..K.. | | x | | k |
138 // | ..L.. | * | y | == | l |
139 // | ..M.. | | 1 | | m |
140 //
Chris Daltonfebbffa2017-06-08 13:12:02 -0600141 // NOTE: the KLM lines are calculated in the same space as the input control points. If you
142 // transform the points the lines will also need to be transformed. This can be done by mapping
143 // the lines with the inverse-transpose of the matrix used to map the points.
144 //
145 // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M
146 // intersect with K (See SkClassifyCubic).
147 //
148 // Returns the cubic's classification.
Chris Dalton390f6cd2017-06-12 11:22:54 -0600149 SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]);
Chris Daltonfebbffa2017-06-08 13:12:02 -0600150
151 // Chops the cubic bezier passed in by src, at the double point (intersection point)
152 // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
153 // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
154 // Return value:
155 // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics,
156 // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr
157 // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
158 // dst[0..3] and dst[3..6] if dst is not nullptr
159 // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
160 // src[0..3]
161 //
162 // Output:
163 //
164 // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().)
165 //
csmartdaltoncc261272017-03-23 13:38:45 -0600166 // loopIndex: This value will tell the caller which of the chopped sections (if any) are the
167 // actual loop. A value of -1 means there is no loop section. The caller can then use
168 // this value to decide how/if they want to flip the orientation of this section.
169 // The flip should be done by negating the k and l values as follows:
170 //
Chris Daltonfebbffa2017-06-08 13:12:02 -0600171 // KLM.postScale(-1, -1)
172 int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
173 int* loopIndex);
senorblanco2b4bb072015-04-22 13:45:18 -0700174
175 // When tessellating curved paths into linear segments, this defines the maximum distance
176 // in screen space which a segment may deviate from the mathmatically correct value.
177 // Above this value, the segment will be subdivided.
178 // This value was chosen to approximate the supersampling accuracy of the raster path (16
179 // samples, or one quarter pixel).
180 static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
Brian Osman49b7b6f2017-06-20 14:43:58 -0400181
182 // We guarantee that no quad or cubic will ever produce more than this many points
183 static const int kMaxPointsPerCurve = 1 << 10;
senorblanco@chromium.org9d18b782011-03-28 20:47:09 +0000184};
185#endif