senorblanco@chromium.org | 9d18b78 | 2011-03-28 20:47:09 +0000 | [diff] [blame] | 1 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 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. |
senorblanco@chromium.org | 9d18b78 | 2011-03-28 20:47:09 +0000 | [diff] [blame] | 6 | */ |
| 7 | |
| 8 | #ifndef GrPathUtils_DEFINED |
| 9 | #define GrPathUtils_DEFINED |
| 10 | |
Chris Dalton | febbffa | 2017-06-08 13:12:02 -0600 | [diff] [blame] | 11 | #include "SkGeometry.h" |
commit-bot@chromium.org | fd03d4a | 2013-07-17 21:39:42 +0000 | [diff] [blame] | 12 | #include "SkRect.h" |
reed | 026beb5 | 2015-06-10 14:23:15 -0700 | [diff] [blame] | 13 | #include "SkPathPriv.h" |
bsalomon@google.com | 69cc6ad | 2012-01-17 14:25:10 +0000 | [diff] [blame] | 14 | #include "SkTArray.h" |
senorblanco@chromium.org | 9d18b78 | 2011-03-28 20:47:09 +0000 | [diff] [blame] | 15 | |
bsalomon@google.com | b9086a0 | 2012-11-01 18:02:54 +0000 | [diff] [blame] | 16 | class SkMatrix; |
| 17 | |
senorblanco@chromium.org | 9d18b78 | 2011-03-28 20:47:09 +0000 | [diff] [blame] | 18 | /** |
| 19 | * Utilities for evaluating paths. |
| 20 | */ |
bsalomon@google.com | 181e9bd | 2011-09-07 18:42:30 +0000 | [diff] [blame] | 21 | namespace GrPathUtils { |
Brian Osman | 25294d7 | 2017-05-09 16:36:41 -0400 | [diff] [blame] | 22 | // Very small tolerances will be increased to a minimum threshold value, to avoid division |
| 23 | // problems in subsequent math. |
bsalomon@google.com | 8171288 | 2012-11-01 17:12:34 +0000 | [diff] [blame] | 24 | SkScalar scaleToleranceToSrc(SkScalar devTol, |
bsalomon@google.com | b9086a0 | 2012-11-01 18:02:54 +0000 | [diff] [blame] | 25 | const SkMatrix& viewM, |
commit-bot@chromium.org | fd03d4a | 2013-07-17 21:39:42 +0000 | [diff] [blame] | 26 | const SkRect& pathBounds); |
tomhudson@google.com | c10a888 | 2011-06-28 15:19:32 +0000 | [diff] [blame] | 27 | |
bsalomon@google.com | 8d033a1 | 2012-04-27 15:52:53 +0000 | [diff] [blame] | 28 | int worstCasePointCount(const SkPath&, |
bsalomon@google.com | 181e9bd | 2011-09-07 18:42:30 +0000 | [diff] [blame] | 29 | int* subpaths, |
bsalomon@google.com | 8171288 | 2012-11-01 17:12:34 +0000 | [diff] [blame] | 30 | SkScalar tol); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 31 | |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 32 | uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 33 | |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 34 | uint32_t generateQuadraticPoints(const SkPoint& p0, |
| 35 | const SkPoint& p1, |
| 36 | const SkPoint& p2, |
bsalomon@google.com | 8171288 | 2012-11-01 17:12:34 +0000 | [diff] [blame] | 37 | SkScalar tolSqd, |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 38 | SkPoint** points, |
bsalomon@google.com | 181e9bd | 2011-09-07 18:42:30 +0000 | [diff] [blame] | 39 | uint32_t pointsLeft); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 40 | |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 41 | uint32_t cubicPointCount(const SkPoint points[], SkScalar tol); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 42 | |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 43 | uint32_t generateCubicPoints(const SkPoint& p0, |
| 44 | const SkPoint& p1, |
| 45 | const SkPoint& p2, |
| 46 | const SkPoint& p3, |
bsalomon@google.com | 8171288 | 2012-11-01 17:12:34 +0000 | [diff] [blame] | 47 | SkScalar tolSqd, |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 48 | SkPoint** points, |
bsalomon@google.com | 181e9bd | 2011-09-07 18:42:30 +0000 | [diff] [blame] | 49 | uint32_t pointsLeft); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 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: |
Mike Klein | fc6c37b | 2016-09-27 09:34:10 -0400 | [diff] [blame] | 56 | QuadUVMatrix() {} |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 57 | // Initialize the matrix from the control pts |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 58 | QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); } |
| 59 | void set(const SkPoint controlPts[3]); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 60 | |
| 61 | /** |
Brian Osman | 568bec7 | 2018-12-26 16:48:25 -0500 | [diff] [blame] | 62 | * Applies the matrix to vertex positions to compute UV coords. |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 63 | * |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 64 | * vertices is a pointer to the first vertex. |
Brian Osman | 568bec7 | 2018-12-26 16:48:25 -0500 | [diff] [blame] | 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. |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 68 | */ |
Brian Osman | 568bec7 | 2018-12-26 16:48:25 -0500 | [diff] [blame] | 69 | void apply(void* vertices, int vertexCount, size_t stride, size_t uvOffset) const { |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 70 | intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices); |
Brian Osman | 568bec7 | 2018-12-26 16:48:25 -0500 | [diff] [blame] | 71 | intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + uvOffset; |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 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]; |
Brian Osman | 568bec7 | 2018-12-26 16:48:25 -0500 | [diff] [blame] | 78 | for (int i = 0; i < vertexCount; ++i) { |
commit-bot@chromium.org | 972f9cd | 2014-03-28 17:58:28 +0000 | [diff] [blame] | 79 | const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr); |
| 80 | SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr); |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 81 | uv->fX = sx * xy->fX + kx * xy->fY + tx; |
| 82 | uv->fY = ky * xy->fX + sy * xy->fY + ty; |
Brian Osman | 568bec7 | 2018-12-26 16:48:25 -0500 | [diff] [blame] | 83 | xyPtr += stride; |
| 84 | uvPtr += stride; |
bsalomon@google.com | 1971317 | 2012-03-15 13:51:08 +0000 | [diff] [blame] | 85 | } |
| 86 | } |
| 87 | private: |
| 88 | float fM[6]; |
| 89 | }; |
| 90 | |
commit-bot@chromium.org | 1394840 | 2013-08-20 17:55:43 +0000 | [diff] [blame] | 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 |
csmartdalton | cc26127 | 2017-03-23 13:38:45 -0600 | [diff] [blame] | 93 | // conic, k^2 - lm. |
commit-bot@chromium.org | 1394840 | 2013-08-20 17:55:43 +0000 | [diff] [blame] | 94 | // |
csmartdalton | cc26127 | 2017-03-23 13:38:45 -0600 | [diff] [blame] | 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); |
bsalomon@google.com | a51ab84 | 2012-07-10 19:53:34 +0000 | [diff] [blame] | 102 | |
bsalomon@google.com | 69cc6ad | 2012-01-17 14:25:10 +0000 | [diff] [blame] | 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 |
Brian Salomon | 3ac1f95 | 2018-09-07 13:47:49 -0400 | [diff] [blame] | 105 | // result is sets of 3 points in quads. This will preserve the starting and |
| 106 | // ending tangent vectors (modulo FP precision). |
bsalomon | 18fab30 | 2016-02-16 08:00:05 -0800 | [diff] [blame] | 107 | void convertCubicToQuads(const SkPoint p[4], |
| 108 | SkScalar tolScale, |
| 109 | SkTArray<SkPoint, true>* quads); |
| 110 | |
bsalomon@google.com | a51ab84 | 2012-07-10 19:53:34 +0000 | [diff] [blame] | 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. |
bsalomon | 18fab30 | 2016-02-16 08:00:05 -0800 | [diff] [blame] | 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); |
commit-bot@chromium.org | 858638d | 2013-08-20 14:45:45 +0000 | [diff] [blame] | 122 | |
Chris Dalton | 695db40 | 2017-08-28 11:29:49 -0600 | [diff] [blame] | 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 | |
Chris Dalton | febbffa | 2017-06-08 13:12:02 -0600 | [diff] [blame] | 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: |
commit-bot@chromium.org | 858638d | 2013-08-20 14:45:45 +0000 | [diff] [blame] | 162 | // |
Chris Dalton | febbffa | 2017-06-08 13:12:02 -0600 | [diff] [blame] | 163 | // k^3 < l*m |
commit-bot@chromium.org | 858638d | 2013-08-20 14:45:45 +0000 | [diff] [blame] | 164 | // |
csmartdalton | cc26127 | 2017-03-23 13:38:45 -0600 | [diff] [blame] | 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 | // |
Chris Dalton | febbffa | 2017-06-08 13:12:02 -0600 | [diff] [blame] | 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. |
Chris Dalton | 390f6cd | 2017-06-12 11:22:54 -0600 | [diff] [blame] | 181 | SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]); |
Chris Dalton | febbffa | 2017-06-08 13:12:02 -0600 | [diff] [blame] | 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 | // |
csmartdalton | cc26127 | 2017-03-23 13:38:45 -0600 | [diff] [blame] | 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 | // |
Chris Dalton | febbffa | 2017-06-08 13:12:02 -0600 | [diff] [blame] | 203 | // KLM.postScale(-1, -1) |
| 204 | int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm, |
| 205 | int* loopIndex); |
senorblanco | 2b4bb07 | 2015-04-22 13:45:18 -0700 | [diff] [blame] | 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); |
Brian Osman | 49b7b6f | 2017-06-20 14:43:58 -0400 | [diff] [blame] | 213 | |
| 214 | // We guarantee that no quad or cubic will ever produce more than this many points |
| 215 | static const int kMaxPointsPerCurve = 1 << 10; |
senorblanco@chromium.org | 9d18b78 | 2011-03-28 20:47:09 +0000 | [diff] [blame] | 216 | }; |
| 217 | #endif |