OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2016 Google Inc. | 2 * Copyright 2016 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "SkCurveMeasure.h" | 8 #include "SkCurveMeasure.h" |
| 9 #include "SkGeometry.h" |
9 | 10 |
10 // for abs | 11 // for abs |
11 #include <cmath> | 12 #include <cmath> |
12 | 13 |
| 14 #define UNIMPLEMENTED SkDEBUGF(("%s:%d unimplemented\n", __FILE__, __LINE__)) |
| 15 |
| 16 /// Used inside SkCurveMeasure::getTime's Newton's iteration |
| 17 static inline SkPoint evaluate(const SkPoint pts[4], SkSegType segType, |
| 18 SkScalar t) { |
| 19 SkPoint pos; |
| 20 switch (segType) { |
| 21 case kQuad_SegType: |
| 22 pos = SkEvalQuadAt(pts, t); |
| 23 break; |
| 24 case kLine_SegType: |
| 25 pos = SkPoint::Make(SkScalarInterp(pts[0].x(), pts[1].x(), t), |
| 26 SkScalarInterp(pts[0].y(), pts[1].y(), t)); |
| 27 break; |
| 28 case kCubic_SegType: |
| 29 SkEvalCubicAt(pts, t, &pos, nullptr, nullptr); |
| 30 break; |
| 31 case kConic_SegType: { |
| 32 SkConic conic(pts, pts[3].x()); |
| 33 conic.evalAt(t, &pos); |
| 34 } |
| 35 break; |
| 36 default: |
| 37 UNIMPLEMENTED; |
| 38 } |
| 39 |
| 40 return pos; |
| 41 } |
| 42 |
| 43 /// Used inside SkCurveMeasure::getTime's Newton's iteration |
| 44 static inline SkVector evaluateDerivative(const SkPoint pts[4], |
| 45 SkSegType segType, SkScalar t) { |
| 46 SkVector tan; |
| 47 switch (segType) { |
| 48 case kQuad_SegType: |
| 49 tan = SkEvalQuadTangentAt(pts, t); |
| 50 break; |
| 51 case kLine_SegType: |
| 52 tan = pts[1] - pts[0]; |
| 53 break; |
| 54 case kCubic_SegType: |
| 55 SkEvalCubicAt(pts, t, nullptr, &tan, nullptr); |
| 56 break; |
| 57 case kConic_SegType: { |
| 58 SkConic conic(pts, pts[3].x()); |
| 59 conic.evalAt(t, nullptr, &tan); |
| 60 } |
| 61 break; |
| 62 default: |
| 63 UNIMPLEMENTED; |
| 64 } |
| 65 |
| 66 return tan; |
| 67 } |
| 68 /// Used in ArcLengthIntegrator::computeLength |
13 static inline Sk8f evaluateDerivativeLength(const Sk8f& ts, | 69 static inline Sk8f evaluateDerivativeLength(const Sk8f& ts, |
14 const Sk8f (&xCoeff)[3], | 70 const Sk8f (&xCoeff)[3], |
15 const Sk8f (&yCoeff)[3], | 71 const Sk8f (&yCoeff)[3], |
16 const SkSegType segType) { | 72 const SkSegType segType) { |
17 Sk8f x; | 73 Sk8f x; |
18 Sk8f y; | 74 Sk8f y; |
19 switch (segType) { | 75 switch (segType) { |
20 case kQuad_SegType: | 76 case kQuad_SegType: |
21 x = xCoeff[0]*ts + xCoeff[1]; | 77 x = xCoeff[0]*ts + xCoeff[1]; |
22 y = yCoeff[0]*ts + yCoeff[1]; | 78 y = yCoeff[0]*ts + yCoeff[1]; |
23 break; | 79 break; |
24 case kLine_SegType: | 80 case kLine_SegType: |
25 SkDebugf("Unimplemented"); | 81 // length of line derivative is constant |
26 break; | 82 // and we precompute it in the constructor |
| 83 return xCoeff[0]; |
27 case kCubic_SegType: | 84 case kCubic_SegType: |
28 x = (xCoeff[0]*ts + xCoeff[1])*ts + xCoeff[2]; | 85 x = (xCoeff[0]*ts + xCoeff[1])*ts + xCoeff[2]; |
29 y = (yCoeff[0]*ts + yCoeff[1])*ts + yCoeff[2]; | 86 y = (yCoeff[0]*ts + yCoeff[1])*ts + yCoeff[2]; |
30 break; | 87 break; |
31 case kConic_SegType: | 88 case kConic_SegType: |
32 SkDebugf("Unimplemented"); | 89 UNIMPLEMENTED; |
33 break; | 90 break; |
34 default: | 91 default: |
35 SkDebugf("Unimplemented"); | 92 UNIMPLEMENTED; |
36 } | 93 } |
37 | 94 |
38 x = x * x; | 95 x = x * x; |
39 y = y * y; | 96 y = y * y; |
40 | 97 |
41 return (x + y).sqrt(); | 98 return (x + y).sqrt(); |
42 } | 99 } |
| 100 |
43 ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType) | 101 ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType) |
44 : fSegType(segType) { | 102 : fSegType(segType) { |
45 switch (fSegType) { | 103 switch (fSegType) { |
46 case kQuad_SegType: { | 104 case kQuad_SegType: { |
47 float Ax = pts[0].x(); | 105 float Ax = pts[0].x(); |
48 float Bx = pts[1].x(); | 106 float Bx = pts[1].x(); |
49 float Cx = pts[2].x(); | 107 float Cx = pts[2].x(); |
50 float Ay = pts[0].y(); | 108 float Ay = pts[0].y(); |
51 float By = pts[1].y(); | 109 float By = pts[1].y(); |
52 float Cy = pts[2].y(); | 110 float Cy = pts[2].y(); |
53 | 111 |
54 // precompute coefficients for derivative | 112 // precompute coefficients for derivative |
55 xCoeff[0] = Sk8f(2.0f*(Ax - 2*Bx + Cx)); | 113 xCoeff[0] = Sk8f(2.0f*(Ax - 2*Bx + Cx)); |
56 xCoeff[1] = Sk8f(2.0f*(Bx - Ax)); | 114 xCoeff[1] = Sk8f(2.0f*(Bx - Ax)); |
57 | 115 |
58 yCoeff[0] = Sk8f(2.0f*(Ay - 2*By + Cy)); | 116 yCoeff[0] = Sk8f(2.0f*(Ay - 2*By + Cy)); |
59 yCoeff[1] = Sk8f(2.0f*(By - Ay)); | 117 yCoeff[1] = Sk8f(2.0f*(By - Ay)); |
60 } | 118 } |
61 break; | 119 break; |
62 case kLine_SegType: | 120 case kLine_SegType: { |
63 SkDEBUGF(("Unimplemented")); | 121 // the length of the derivative of a line is constant |
| 122 // we put in in both coeff arrays for consistency's sake |
| 123 SkScalar length = (pts[1] - pts[0]).length(); |
| 124 xCoeff[0] = Sk8f(length); |
| 125 yCoeff[0] = Sk8f(length); |
| 126 } |
64 break; | 127 break; |
65 case kCubic_SegType: | 128 case kCubic_SegType: |
66 { | 129 { |
67 float Ax = pts[0].x(); | 130 float Ax = pts[0].x(); |
68 float Bx = pts[1].x(); | 131 float Bx = pts[1].x(); |
69 float Cx = pts[2].x(); | 132 float Cx = pts[2].x(); |
70 float Dx = pts[3].x(); | 133 float Dx = pts[3].x(); |
71 float Ay = pts[0].y(); | 134 float Ay = pts[0].y(); |
72 float By = pts[1].y(); | 135 float By = pts[1].y(); |
73 float Cy = pts[2].y(); | 136 float Cy = pts[2].y(); |
74 float Dy = pts[3].y(); | 137 float Dy = pts[3].y(); |
75 | 138 |
| 139 // precompute coefficients for derivative |
76 xCoeff[0] = Sk8f(3.0f*(-Ax + 3.0f*(Bx - Cx) + Dx)); | 140 xCoeff[0] = Sk8f(3.0f*(-Ax + 3.0f*(Bx - Cx) + Dx)); |
77 xCoeff[1] = Sk8f(3.0f*(2.0f*(Ax - 2.0f*Bx + Cx))); | 141 xCoeff[1] = Sk8f(3.0f*(2.0f*(Ax - 2.0f*Bx + Cx))); |
78 xCoeff[2] = Sk8f(3.0f*(-Ax + Bx)); | 142 xCoeff[2] = Sk8f(3.0f*(-Ax + Bx)); |
79 | 143 |
80 yCoeff[0] = Sk8f(3.0f*(-Ay + 3.0f*(By - Cy) + Dy)); | 144 yCoeff[0] = Sk8f(3.0f*(-Ay + 3.0f*(By - Cy) + Dy)); |
81 yCoeff[1] = Sk8f(3.0f * -Ay + By + 2.0f*(Ay - 2.0f*By + Cy)); | 145 yCoeff[1] = Sk8f(3.0f * -Ay + By + 2.0f*(Ay - 2.0f*By + Cy)); |
82 yCoeff[2] = Sk8f(3.0f*(-Ay + By)); | 146 yCoeff[2] = Sk8f(3.0f*(-Ay + By)); |
83 } | 147 } |
84 break; | 148 break; |
85 case kConic_SegType: | 149 case kConic_SegType: |
86 SkDEBUGF(("Unimplemented")); | 150 UNIMPLEMENTED; |
87 break; | 151 break; |
88 default: | 152 default: |
89 SkDEBUGF(("Unimplemented")); | 153 UNIMPLEMENTED; |
90 } | 154 } |
91 } | 155 } |
92 | 156 |
93 // We use Gaussian quadrature | 157 // We use Gaussian quadrature |
94 // (https://en.wikipedia.org/wiki/Gaussian_quadrature) | 158 // (https://en.wikipedia.org/wiki/Gaussian_quadrature) |
95 // to approximate the arc length integral here, because it is amenable to SIMD. | 159 // to approximate the arc length integral here, because it is amenable to SIMD. |
96 SkScalar ArcLengthIntegrator::computeLength(SkScalar t) { | 160 SkScalar ArcLengthIntegrator::computeLength(SkScalar t) { |
97 SkScalar length = 0.0f; | 161 SkScalar length = 0.0f; |
98 | 162 |
99 Sk8f lengths = evaluateDerivativeLength(absc*t, xCoeff, yCoeff, fSegType); | 163 Sk8f lengths = evaluateDerivativeLength(absc*t, xCoeff, yCoeff, fSegType); |
(...skipping 10 matching lines...) Expand all Loading... |
110 | 174 |
111 SkCurveMeasure::SkCurveMeasure(const SkPoint* pts, SkSegType segType) | 175 SkCurveMeasure::SkCurveMeasure(const SkPoint* pts, SkSegType segType) |
112 : fSegType(segType) { | 176 : fSegType(segType) { |
113 switch (fSegType) { | 177 switch (fSegType) { |
114 case SkSegType::kQuad_SegType: | 178 case SkSegType::kQuad_SegType: |
115 for (size_t i = 0; i < 3; i++) { | 179 for (size_t i = 0; i < 3; i++) { |
116 fPts[i] = pts[i]; | 180 fPts[i] = pts[i]; |
117 } | 181 } |
118 break; | 182 break; |
119 case SkSegType::kLine_SegType: | 183 case SkSegType::kLine_SegType: |
120 SkDebugf("Unimplemented"); | 184 fPts[0] = pts[0]; |
| 185 fPts[1] = pts[1]; |
121 break; | 186 break; |
122 case SkSegType::kCubic_SegType: | 187 case SkSegType::kCubic_SegType: |
123 for (size_t i = 0; i < 4; i++) { | 188 for (size_t i = 0; i < 4; i++) { |
124 fPts[i] = pts[i]; | 189 fPts[i] = pts[i]; |
125 } | 190 } |
126 break; | 191 break; |
127 case SkSegType::kConic_SegType: | 192 case SkSegType::kConic_SegType: |
128 SkDebugf("Unimplemented"); | 193 for (size_t i = 0; i < 4; i++) { |
| 194 fPts[i] = pts[i]; |
| 195 } |
129 break; | 196 break; |
130 default: | 197 default: |
131 SkDEBUGF(("Unimplemented")); | 198 UNIMPLEMENTED; |
132 break; | 199 break; |
133 } | 200 } |
134 fIntegrator = ArcLengthIntegrator(fPts, fSegType); | 201 fIntegrator = ArcLengthIntegrator(fPts, fSegType); |
135 } | 202 } |
136 | 203 |
137 SkScalar SkCurveMeasure::getLength() { | 204 SkScalar SkCurveMeasure::getLength() { |
138 if (-1.0f == fLength) { | 205 if (-1.0f == fLength) { |
139 fLength = fIntegrator.computeLength(1.0f); | 206 fLength = fIntegrator.computeLength(1.0f); |
140 } | 207 } |
141 return fLength; | 208 return fLength; |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
192 // on the t value | 259 // on the t value |
193 // because we may not have enough precision in the t to get close enough | 260 // because we may not have enough precision in the t to get close enough |
194 // in the length. | 261 // in the length. |
195 if ((std::abs(lengthDiff) < kTolerance) || | 262 if ((std::abs(lengthDiff) < kTolerance) || |
196 (std::abs(prevT - currentT) < kTolerance)) { | 263 (std::abs(prevT - currentT) < kTolerance)) { |
197 break; | 264 break; |
198 } | 265 } |
199 | 266 |
200 prevT = currentT; | 267 prevT = currentT; |
201 if (iterations < kNewtonIters) { | 268 if (iterations < kNewtonIters) { |
202 // TODO(hstern) switch here on curve type. | |
203 // This is just newton's formula. | 269 // This is just newton's formula. |
204 SkScalar dt = evaluateQuadDerivative(currentT).length(); | 270 SkScalar dt = evaluateDerivative(fPts, fSegType, currentT).length(); |
205 newT = currentT - (lengthDiff / dt); | 271 newT = currentT - (lengthDiff / dt); |
206 | 272 |
207 // If newT is out of bounds, bisect inside newton. | 273 // If newT is out of bounds, bisect inside newton. |
208 if ((newT < 0.0f) || (newT > 1.0f)) { | 274 if ((newT < 0.0f) || (newT > 1.0f)) { |
209 newT = (minT + maxT) * 0.5f; | 275 newT = (minT + maxT) * 0.5f; |
210 } | 276 } |
211 } else if (iterations < kNewtonIters + kBisectIters) { | 277 } else if (iterations < kNewtonIters + kBisectIters) { |
212 if (lengthDiff > 0.0f) { | 278 if (lengthDiff > 0.0f) { |
213 maxT = currentT; | 279 maxT = currentT; |
214 } else { | 280 } else { |
215 minT = currentT; | 281 minT = currentT; |
216 } | 282 } |
217 // TODO(hstern) do a lerp here instead of a bisection | 283 // TODO(hstern) do a lerp here instead of a bisection |
218 newT = (minT + maxT) * 0.5f; | 284 newT = (minT + maxT) * 0.5f; |
219 } else { | 285 } else { |
220 SkDEBUGF(("%.7f %.7f didn't get close enough after bisection.\n", | 286 SkDEBUGF(("%.7f %.7f didn't get close enough after bisection.\n", |
221 currentT, currentLength)); | 287 currentT, currentLength)); |
222 break; | 288 break; |
223 } | 289 } |
224 currentT = newT; | 290 currentT = newT; |
225 | 291 |
226 SkASSERT(minT <= maxT); | 292 SkASSERT(minT <= maxT); |
227 | 293 |
228 iterations++; | 294 iterations++; |
229 } | 295 } |
230 | 296 |
231 // debug. is there an SKDEBUG or something for ifdefs? | 297 // debug. is there an SKDEBUG or something for ifdefs? |
232 fIters = iterations; | 298 fIters = iterations; |
233 | 299 |
234 return currentT; | 300 return currentT; |
235 } | 301 } |
236 | 302 |
237 void SkCurveMeasure::getPosTanTime(SkScalar targetLength, SkPoint* pos, | 303 void SkCurveMeasure::getPosTanTime(SkScalar targetLength, SkPoint* pos, |
238 SkVector* tan, SkScalar* time) { | 304 SkVector* tan, SkScalar* time) { |
239 SkScalar t = getTime(targetLength); | 305 SkScalar t = getTime(targetLength); |
240 | 306 |
241 if (time) { | 307 if (time) { |
242 *time = t; | 308 *time = t; |
243 } | 309 } |
244 if (pos) { | 310 if (pos) { |
245 // TODO(hstern) switch here on curve type. | 311 *pos = evaluate(fPts, fSegType, t); |
246 *pos = evaluateQuad(t); | |
247 } | 312 } |
248 if (tan) { | 313 if (tan) { |
249 // TODO(hstern) switch here on curve type. | 314 *tan = evaluateDerivative(fPts, fSegType, t); |
250 *tan = evaluateQuadDerivative(t); | |
251 } | 315 } |
252 } | 316 } |
253 | |
254 // this is why I feel that the ArcLengthIntegrator should be combined | |
255 // with some sort of evaluator that caches the constants computed from the | |
256 // control points. this is basically the same code in ArcLengthIntegrator | |
257 SkPoint SkCurveMeasure::evaluateQuad(SkScalar t) { | |
258 SkScalar ti = 1.0f - t; | |
259 | |
260 SkScalar Ax = fPts[0].x(); | |
261 SkScalar Bx = fPts[1].x(); | |
262 SkScalar Cx = fPts[2].x(); | |
263 SkScalar Ay = fPts[0].y(); | |
264 SkScalar By = fPts[1].y(); | |
265 SkScalar Cy = fPts[2].y(); | |
266 | |
267 SkScalar x = Ax*ti*ti + 2.0f*Bx*t*ti + Cx*t*t; | |
268 SkScalar y = Ay*ti*ti + 2.0f*By*t*ti + Cy*t*t; | |
269 return SkPoint::Make(x, y); | |
270 } | |
271 | |
272 SkVector SkCurveMeasure::evaluateQuadDerivative(SkScalar t) { | |
273 SkScalar Ax = fPts[0].x(); | |
274 SkScalar Bx = fPts[1].x(); | |
275 SkScalar Cx = fPts[2].x(); | |
276 SkScalar Ay = fPts[0].y(); | |
277 SkScalar By = fPts[1].y(); | |
278 SkScalar Cy = fPts[2].y(); | |
279 | |
280 SkScalar A2BCx = 2.0f*(Ax - 2*Bx + Cx); | |
281 SkScalar A2BCy = 2.0f*(Ay - 2*By + Cy); | |
282 SkScalar ABx = 2.0f*(Bx - Ax); | |
283 SkScalar ABy = 2.0f*(By - Ay); | |
284 | |
285 return SkPoint::Make(A2BCx*t + ABx, A2BCy*t + ABy); | |
286 } | |
OLD | NEW |