Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1)

Side by Side Diff: src/utils/SkCurveMeasure.cpp

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

Powered by Google App Engine
This is Rietveld 408576698