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