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" | |
10 | 9 |
11 // for abs | 10 // for abs |
12 #include <cmath> | 11 #include <cmath> |
13 | 12 |
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 | |
69 static inline Sk8f evaluateDerivativeLength(const Sk8f& ts, | 13 static inline Sk8f evaluateDerivativeLength(const Sk8f& ts, |
70 const Sk8f (&xCoeff)[3], | 14 const Sk8f (&xCoeff)[3], |
71 const Sk8f (&yCoeff)[3], | 15 const Sk8f (&yCoeff)[3], |
72 const SkSegType segType) { | 16 const SkSegType segType) { |
73 Sk8f x; | 17 Sk8f x; |
74 Sk8f y; | 18 Sk8f y; |
75 switch (segType) { | 19 switch (segType) { |
76 case kQuad_SegType: | 20 case kQuad_SegType: |
77 x = xCoeff[0]*ts + xCoeff[1]; | 21 x = xCoeff[0]*ts + xCoeff[1]; |
78 y = yCoeff[0]*ts + yCoeff[1]; | 22 y = yCoeff[0]*ts + yCoeff[1]; |
79 break; | 23 break; |
| 24 case kLine_SegType: |
| 25 SkDebugf("Unimplemented"); |
| 26 break; |
80 case kCubic_SegType: | 27 case kCubic_SegType: |
81 x = (xCoeff[0]*ts + xCoeff[1])*ts + xCoeff[2]; | 28 x = (xCoeff[0]*ts + xCoeff[1])*ts + xCoeff[2]; |
82 y = (yCoeff[0]*ts + yCoeff[1])*ts + yCoeff[2]; | 29 y = (yCoeff[0]*ts + yCoeff[1])*ts + yCoeff[2]; |
83 break; | 30 break; |
84 case kConic_SegType: | 31 case kConic_SegType: |
85 UNIMPLEMENTED; | 32 SkDebugf("Unimplemented"); |
86 break; | 33 break; |
87 default: | 34 default: |
88 UNIMPLEMENTED; | 35 SkDebugf("Unimplemented"); |
89 } | 36 } |
90 | 37 |
91 x = x * x; | 38 x = x * x; |
92 y = y * y; | 39 y = y * y; |
93 | 40 |
94 return (x + y).sqrt(); | 41 return (x + y).sqrt(); |
95 } | 42 } |
96 | |
97 ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType) | 43 ArcLengthIntegrator::ArcLengthIntegrator(const SkPoint* pts, SkSegType segType) |
98 : fSegType(segType) { | 44 : fSegType(segType) { |
99 switch (fSegType) { | 45 switch (fSegType) { |
100 case kQuad_SegType: { | 46 case kQuad_SegType: { |
101 float Ax = pts[0].x(); | 47 float Ax = pts[0].x(); |
102 float Bx = pts[1].x(); | 48 float Bx = pts[1].x(); |
103 float Cx = pts[2].x(); | 49 float Cx = pts[2].x(); |
104 float Ay = pts[0].y(); | 50 float Ay = pts[0].y(); |
105 float By = pts[1].y(); | 51 float By = pts[1].y(); |
106 float Cy = pts[2].y(); | 52 float Cy = pts[2].y(); |
107 | 53 |
108 // precompute coefficients for derivative | 54 // precompute coefficients for derivative |
109 xCoeff[0] = Sk8f(2.0f*(Ax - 2*Bx + Cx)); | 55 xCoeff[0] = Sk8f(2.0f*(Ax - 2*Bx + Cx)); |
110 xCoeff[1] = Sk8f(2.0f*(Bx - Ax)); | 56 xCoeff[1] = Sk8f(2.0f*(Bx - Ax)); |
111 | 57 |
112 yCoeff[0] = Sk8f(2.0f*(Ay - 2*By + Cy)); | 58 yCoeff[0] = Sk8f(2.0f*(Ay - 2*By + Cy)); |
113 yCoeff[1] = Sk8f(2.0f*(By - Ay)); | 59 yCoeff[1] = Sk8f(2.0f*(By - Ay)); |
114 } | 60 } |
115 break; | 61 break; |
| 62 case kLine_SegType: |
| 63 SkDEBUGF(("Unimplemented")); |
| 64 break; |
116 case kCubic_SegType: | 65 case kCubic_SegType: |
117 { | 66 { |
118 float Ax = pts[0].x(); | 67 float Ax = pts[0].x(); |
119 float Bx = pts[1].x(); | 68 float Bx = pts[1].x(); |
120 float Cx = pts[2].x(); | 69 float Cx = pts[2].x(); |
121 float Dx = pts[3].x(); | 70 float Dx = pts[3].x(); |
122 float Ay = pts[0].y(); | 71 float Ay = pts[0].y(); |
123 float By = pts[1].y(); | 72 float By = pts[1].y(); |
124 float Cy = pts[2].y(); | 73 float Cy = pts[2].y(); |
125 float Dy = pts[3].y(); | 74 float Dy = pts[3].y(); |
126 | 75 |
127 // precompute coefficients for derivative | |
128 xCoeff[0] = Sk8f(3.0f*(-Ax + 3.0f*(Bx - Cx) + Dx)); | 76 xCoeff[0] = Sk8f(3.0f*(-Ax + 3.0f*(Bx - Cx) + Dx)); |
129 xCoeff[1] = Sk8f(3.0f*(2.0f*(Ax - 2.0f*Bx + Cx))); | 77 xCoeff[1] = Sk8f(3.0f*(2.0f*(Ax - 2.0f*Bx + Cx))); |
130 xCoeff[2] = Sk8f(3.0f*(-Ax + Bx)); | 78 xCoeff[2] = Sk8f(3.0f*(-Ax + Bx)); |
131 | 79 |
132 yCoeff[0] = Sk8f(3.0f*(-Ay + 3.0f*(By - Cy) + Dy)); | 80 yCoeff[0] = Sk8f(3.0f*(-Ay + 3.0f*(By - Cy) + Dy)); |
133 yCoeff[1] = Sk8f(3.0f * -Ay + By + 2.0f*(Ay - 2.0f*By + Cy)); | 81 yCoeff[1] = Sk8f(3.0f * -Ay + By + 2.0f*(Ay - 2.0f*By + Cy)); |
134 yCoeff[2] = Sk8f(3.0f*(-Ay + By)); | 82 yCoeff[2] = Sk8f(3.0f*(-Ay + By)); |
135 } | 83 } |
136 break; | 84 break; |
137 case kConic_SegType: | 85 case kConic_SegType: |
138 UNIMPLEMENTED; | 86 SkDEBUGF(("Unimplemented")); |
139 break; | 87 break; |
140 default: | 88 default: |
141 UNIMPLEMENTED; | 89 SkDEBUGF(("Unimplemented")); |
142 } | 90 } |
143 } | 91 } |
144 | 92 |
145 // We use Gaussian quadrature | 93 // We use Gaussian quadrature |
146 // (https://en.wikipedia.org/wiki/Gaussian_quadrature) | 94 // (https://en.wikipedia.org/wiki/Gaussian_quadrature) |
147 // to approximate the arc length integral here, because it is amenable to SIMD. | 95 // to approximate the arc length integral here, because it is amenable to SIMD. |
148 SkScalar ArcLengthIntegrator::computeLength(SkScalar t) { | 96 SkScalar ArcLengthIntegrator::computeLength(SkScalar t) { |
149 SkScalar length = 0.0f; | 97 SkScalar length = 0.0f; |
150 | 98 |
151 Sk8f lengths = evaluateDerivativeLength(absc*t, xCoeff, yCoeff, fSegType); | 99 Sk8f lengths = evaluateDerivativeLength(absc*t, xCoeff, yCoeff, fSegType); |
(...skipping 10 matching lines...) Expand all Loading... |
162 | 110 |
163 SkCurveMeasure::SkCurveMeasure(const SkPoint* pts, SkSegType segType) | 111 SkCurveMeasure::SkCurveMeasure(const SkPoint* pts, SkSegType segType) |
164 : fSegType(segType) { | 112 : fSegType(segType) { |
165 switch (fSegType) { | 113 switch (fSegType) { |
166 case SkSegType::kQuad_SegType: | 114 case SkSegType::kQuad_SegType: |
167 for (size_t i = 0; i < 3; i++) { | 115 for (size_t i = 0; i < 3; i++) { |
168 fPts[i] = pts[i]; | 116 fPts[i] = pts[i]; |
169 } | 117 } |
170 break; | 118 break; |
171 case SkSegType::kLine_SegType: | 119 case SkSegType::kLine_SegType: |
172 fPts[0] = pts[0]; | 120 SkDebugf("Unimplemented"); |
173 fPts[1] = pts[1]; | |
174 fLength = (fPts[1] - fPts[0]).length(); | |
175 break; | 121 break; |
176 case SkSegType::kCubic_SegType: | 122 case SkSegType::kCubic_SegType: |
177 for (size_t i = 0; i < 4; i++) { | 123 for (size_t i = 0; i < 4; i++) { |
178 fPts[i] = pts[i]; | 124 fPts[i] = pts[i]; |
179 } | 125 } |
180 break; | 126 break; |
181 case SkSegType::kConic_SegType: | 127 case SkSegType::kConic_SegType: |
182 for (size_t i = 0; i < 4; i++) { | 128 SkDebugf("Unimplemented"); |
183 fPts[i] = pts[i]; | |
184 } | |
185 break; | 129 break; |
186 default: | 130 default: |
187 UNIMPLEMENTED; | 131 SkDEBUGF(("Unimplemented")); |
188 break; | 132 break; |
189 } | 133 } |
190 if (kLine_SegType != segType) { | 134 fIntegrator = ArcLengthIntegrator(fPts, fSegType); |
191 fIntegrator = ArcLengthIntegrator(fPts, fSegType); | |
192 } | |
193 } | 135 } |
194 | 136 |
195 SkScalar SkCurveMeasure::getLength() { | 137 SkScalar SkCurveMeasure::getLength() { |
196 if (-1.0f == fLength) { | 138 if (-1.0f == fLength) { |
197 fLength = fIntegrator.computeLength(1.0f); | 139 fLength = fIntegrator.computeLength(1.0f); |
198 } | 140 } |
199 return fLength; | 141 return fLength; |
200 } | 142 } |
201 | 143 |
202 // Given an arc length targetLength, we want to determine what t | 144 // Given an arc length targetLength, we want to determine what t |
203 // gives us the corresponding arc length along the curve. | 145 // gives us the corresponding arc length along the curve. |
204 // We do this by letting the arc length integral := f(t) and | 146 // We do this by letting the arc length integral := f(t) and |
205 // solving for the root of the equation f(t) - targetLength = 0 | 147 // solving for the root of the equation f(t) - targetLength = 0 |
206 // using Newton's method and lerp-bisection. | 148 // using Newton's method and lerp-bisection. |
207 // The computationally expensive parts are the integral approximation | 149 // The computationally expensive parts are the integral approximation |
208 // at each step, and computing the derivative of the arc length integral, | 150 // at each step, and computing the derivative of the arc length integral, |
209 // which is equal to the length of the tangent (so we have to do a sqrt). | 151 // which is equal to the length of the tangent (so we have to do a sqrt). |
210 | 152 |
211 SkScalar SkCurveMeasure::getTime(SkScalar targetLength) { | 153 SkScalar SkCurveMeasure::getTime(SkScalar targetLength) { |
212 if (targetLength == 0.0f) { | 154 if (targetLength == 0.0f) { |
213 return 0.0f; | 155 return 0.0f; |
214 } | 156 } |
215 | 157 |
216 SkScalar currentLength = getLength(); | 158 SkScalar currentLength = getLength(); |
217 | 159 |
218 if (SkScalarNearlyEqual(targetLength, currentLength)) { | 160 if (SkScalarNearlyEqual(targetLength, currentLength)) { |
219 return 1.0f; | 161 return 1.0f; |
220 } | 162 } |
221 if (kLine_SegType == fSegType) { | |
222 return targetLength / currentLength; | |
223 } | |
224 | 163 |
225 // initial estimate of t is percentage of total length | 164 // initial estimate of t is percentage of total length |
226 SkScalar currentT = targetLength / currentLength; | 165 SkScalar currentT = targetLength / currentLength; |
227 SkScalar prevT = -1.0f; | 166 SkScalar prevT = -1.0f; |
228 SkScalar newT; | 167 SkScalar newT; |
229 | 168 |
230 SkScalar minT = 0.0f; | 169 SkScalar minT = 0.0f; |
231 SkScalar maxT = 1.0f; | 170 SkScalar maxT = 1.0f; |
232 | 171 |
233 int iterations = 0; | 172 int iterations = 0; |
(...skipping 19 matching lines...) Expand all Loading... |
253 // on the t value | 192 // on the t value |
254 // because we may not have enough precision in the t to get close enough | 193 // because we may not have enough precision in the t to get close enough |
255 // in the length. | 194 // in the length. |
256 if ((std::abs(lengthDiff) < kTolerance) || | 195 if ((std::abs(lengthDiff) < kTolerance) || |
257 (std::abs(prevT - currentT) < kTolerance)) { | 196 (std::abs(prevT - currentT) < kTolerance)) { |
258 break; | 197 break; |
259 } | 198 } |
260 | 199 |
261 prevT = currentT; | 200 prevT = currentT; |
262 if (iterations < kNewtonIters) { | 201 if (iterations < kNewtonIters) { |
| 202 // TODO(hstern) switch here on curve type. |
263 // This is just newton's formula. | 203 // This is just newton's formula. |
264 SkScalar dt = evaluateDerivative(fPts, fSegType, currentT).length(); | 204 SkScalar dt = evaluateQuadDerivative(currentT).length(); |
265 newT = currentT - (lengthDiff / dt); | 205 newT = currentT - (lengthDiff / dt); |
266 | 206 |
267 // If newT is out of bounds, bisect inside newton. | 207 // If newT is out of bounds, bisect inside newton. |
268 if ((newT < 0.0f) || (newT > 1.0f)) { | 208 if ((newT < 0.0f) || (newT > 1.0f)) { |
269 newT = (minT + maxT) * 0.5f; | 209 newT = (minT + maxT) * 0.5f; |
270 } | 210 } |
271 } else if (iterations < kNewtonIters + kBisectIters) { | 211 } else if (iterations < kNewtonIters + kBisectIters) { |
272 if (lengthDiff > 0.0f) { | 212 if (lengthDiff > 0.0f) { |
273 maxT = currentT; | 213 maxT = currentT; |
274 } else { | 214 } else { |
275 minT = currentT; | 215 minT = currentT; |
276 } | 216 } |
277 // TODO(hstern) do a lerp here instead of a bisection | 217 // TODO(hstern) do a lerp here instead of a bisection |
278 newT = (minT + maxT) * 0.5f; | 218 newT = (minT + maxT) * 0.5f; |
279 } else { | 219 } else { |
280 SkDEBUGF(("%.7f %.7f didn't get close enough after bisection.\n", | 220 SkDEBUGF(("%.7f %.7f didn't get close enough after bisection.\n", |
281 currentT, currentLength)); | 221 currentT, currentLength)); |
282 break; | 222 break; |
283 } | 223 } |
284 currentT = newT; | 224 currentT = newT; |
285 | 225 |
286 SkASSERT(minT <= maxT); | 226 SkASSERT(minT <= maxT); |
287 | 227 |
288 iterations++; | 228 iterations++; |
289 } | 229 } |
290 | 230 |
291 // debug. is there an SKDEBUG or something for ifdefs? | 231 // debug. is there an SKDEBUG or something for ifdefs? |
292 fIters = iterations; | 232 fIters = iterations; |
293 | 233 |
294 return currentT; | 234 return currentT; |
295 } | 235 } |
296 | 236 |
297 void SkCurveMeasure::getPosTanTime(SkScalar targetLength, SkPoint* pos, | 237 void SkCurveMeasure::getPosTanTime(SkScalar targetLength, SkPoint* pos, |
298 SkVector* tan, SkScalar* time) { | 238 SkVector* tan, SkScalar* time) { |
299 SkScalar t = getTime(targetLength); | 239 SkScalar t = getTime(targetLength); |
300 | 240 |
301 if (time) { | 241 if (time) { |
302 *time = t; | 242 *time = t; |
303 } | 243 } |
304 if (pos) { | 244 if (pos) { |
305 *pos = evaluate(fPts, fSegType, t); | 245 // TODO(hstern) switch here on curve type. |
| 246 *pos = evaluateQuad(t); |
306 } | 247 } |
307 if (tan) { | 248 if (tan) { |
308 *tan = evaluateDerivative(fPts, fSegType, t); | 249 // TODO(hstern) switch here on curve type. |
| 250 *tan = evaluateQuadDerivative(t); |
309 } | 251 } |
310 } | 252 } |
| 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 |