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/core/SkScan_Hairline.cpp

Issue 1084283003: Speeup hairline curves (quads and cubics) (patchset #7 id:120001 of https://codereview.chromium.org… (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 5 years, 8 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/core/SkGeometry.cpp ('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
2 /* 1 /*
3 * Copyright 2006 The Android Open Source Project 2 * Copyright 2006 The Android Open Source Project
4 * 3 *
5 * 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
6 * found in the LICENSE file. 5 * found in the LICENSE file.
7 */ 6 */
8 7
9
10 #include "SkScan.h" 8 #include "SkScan.h"
11 #include "SkBlitter.h" 9 #include "SkBlitter.h"
12 #include "SkRasterClip.h" 10 #include "SkRasterClip.h"
13 #include "SkFDot6.h" 11 #include "SkFDot6.h"
14 #include "SkLineClipper.h" 12 #include "SkLineClipper.h"
15 13
16 static void horiline(int x, int stopx, SkFixed fy, SkFixed dy, 14 static void horiline(int x, int stopx, SkFixed fy, SkFixed dy,
17 SkBlitter* blitter) { 15 SkBlitter* blitter) {
18 SkASSERT(x < stopx); 16 SkASSERT(x < stopx);
19 17
(...skipping 165 matching lines...) Expand 10 before | Expand all | Expand 10 after
185 blitter->blitH(r.fLeft, r.fTop, width); // top 183 blitter->blitH(r.fLeft, r.fTop, width); // top
186 blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left 184 blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left
187 blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right 185 blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right
188 blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom 186 blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom
189 } 187 }
190 188
191 /////////////////////////////////////////////////////////////////////////////// 189 ///////////////////////////////////////////////////////////////////////////////
192 190
193 #include "SkPath.h" 191 #include "SkPath.h"
194 #include "SkGeometry.h" 192 #include "SkGeometry.h"
193 #include "SkNx.h"
194
195 #define kMaxCubicSubdivideLevel 6
196 #define kMaxQuadSubdivideLevel 5
195 197
196 static int compute_int_quad_dist(const SkPoint pts[3]) { 198 static int compute_int_quad_dist(const SkPoint pts[3]) {
197 // compute the vector between the control point ([1]) and the middle of the 199 // compute the vector between the control point ([1]) and the middle of the
198 // line connecting the start and end ([0] and [2]) 200 // line connecting the start and end ([0] and [2])
199 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX; 201 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX;
200 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY; 202 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY;
201 // we want everyone to be positive 203 // we want everyone to be positive
202 dx = SkScalarAbs(dx); 204 dx = SkScalarAbs(dx);
203 dy = SkScalarAbs(dy); 205 dy = SkScalarAbs(dy);
204 // convert to whole pixel values (use ceiling to be conservative) 206 // convert to whole pixel values (use ceiling to be conservative)
205 int idx = SkScalarCeilToInt(dx); 207 int idx = SkScalarCeilToInt(dx);
206 int idy = SkScalarCeilToInt(dy); 208 int idy = SkScalarCeilToInt(dy);
207 // use the cheap approx for distance 209 // use the cheap approx for distance
208 if (idx > idy) { 210 if (idx > idy) {
209 return idx + (idy >> 1); 211 return idx + (idy >> 1);
210 } else { 212 } else {
211 return idy + (idx >> 1); 213 return idy + (idx >> 1);
212 } 214 }
213 } 215 }
214 216
215 static void hairquad(const SkPoint pts[3], const SkRegion* clip, 217 static void hairquad(const SkPoint pts[3], const SkRegion* clip,
216 SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc ) { 218 SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc ) {
219 SkASSERT(level <= kMaxQuadSubdivideLevel);
220
221 #ifdef SK_SUPPORT_LEGACY_BLITANTIH2V2
217 if (level > 0) { 222 if (level > 0) {
218 SkPoint tmp[5]; 223 SkPoint tmp[5];
219 224
220 SkChopQuadAtHalf(pts, tmp); 225 SkChopQuadAtHalf(pts, tmp);
221 hairquad(tmp, clip, blitter, level - 1, lineproc); 226 hairquad(tmp, clip, blitter, level - 1, lineproc);
222 hairquad(&tmp[2], clip, blitter, level - 1, lineproc); 227 hairquad(&tmp[2], clip, blitter, level - 1, lineproc);
223 } else { 228 } else {
224 SkPoint tmp[] = { pts[0], pts[2] }; 229 SkPoint tmp[] = { pts[0], pts[2] };
225 lineproc(tmp, 2, clip, blitter); 230 lineproc(tmp, 2, clip, blitter);
226 } 231 }
232 #else
233 SkPoint coeff[3];
234 SkQuadToCoeff(pts, coeff);
235
236 const int lines = 1 << level;
237 Sk2s t(0);
238 Sk2s dt(SK_Scalar1 / lines);
239
240 SkPoint tmp[(1 << kMaxQuadSubdivideLevel) + 1];
241 SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp));
242
243 tmp[0] = pts[0];
244 Sk2s A = Sk2s::Load(&coeff[0].fX);
245 Sk2s B = Sk2s::Load(&coeff[1].fX);
246 Sk2s C = Sk2s::Load(&coeff[2].fX);
247 for (int i = 1; i < lines; ++i) {
248 t += dt;
249 ((A * t + B) * t + C).store(&tmp[i].fX);
250 }
251 tmp[lines] = pts[2];
252 lineproc(tmp, lines + 1, clip, blitter);
253 #endif
227 } 254 }
228 255
229 static void haircubic(const SkPoint pts[4], const SkRegion* clip, 256 #ifndef SK_SUPPORT_LEGACY_BLITANTIH2V2
257 static inline Sk2s abs(const Sk2s& value) {
258 return Sk2s::Max(value, -value);
259 }
260
261 static inline SkScalar max_component(const Sk2s& value) {
262 SkScalar components[2];
263 value.store(components);
264 return SkTMax(components[0], components[1]);
265 }
266
267 static inline int compute_cubic_segs(const SkPoint pts[4]) {
268 Sk2s p0 = from_point(pts[0]);
269 Sk2s p1 = from_point(pts[1]);
270 Sk2s p2 = from_point(pts[2]);
271 Sk2s p3 = from_point(pts[3]);
272
273 const Sk2s oneThird(1.0f / 3.0f);
274 const Sk2s twoThird(2.0f / 3.0f);
275
276 Sk2s p13 = oneThird * p3 + twoThird * p0;
277 Sk2s p23 = oneThird * p0 + twoThird * p3;
278
279 SkScalar diff = max_component(Sk2s::Max(abs(p1 - p13), abs(p2 - p23)));
280 SkScalar tol = SK_Scalar1 / 8;
281
282 for (int i = 0; i < kMaxCubicSubdivideLevel; ++i) {
283 if (diff < tol) {
284 return 1 << i;
285 }
286 tol *= 4;
287 }
288 return 1 << kMaxCubicSubdivideLevel;
289 }
290
291 static bool lt_90(SkPoint p0, SkPoint pivot, SkPoint p2) {
292 return SkVector::DotProduct(p0 - pivot, p2 - pivot) >= 0;
293 }
294
295 // The off-curve points are "inside" the limits of the on-curve pts
296 static bool quick_cubic_niceness_check(const SkPoint pts[4]) {
297 return lt_90(pts[1], pts[0], pts[3]) &&
298 lt_90(pts[2], pts[0], pts[3]) &&
299 lt_90(pts[1], pts[3], pts[0]) &&
300 lt_90(pts[2], pts[3], pts[0]);
301 }
302
303 static void hair_cubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* bl itter,
304 SkScan::HairRgnProc lineproc) {
305 const int lines = compute_cubic_segs(pts);
306 SkASSERT(lines > 0);
307 if (1 == lines) {
308 SkPoint tmp[2] = { pts[0], pts[3] };
309 lineproc(tmp, 2, clip, blitter);
310 return;
311 }
312
313 SkPoint coeff[4];
314 SkCubicToCoeff(pts, coeff);
315
316 const Sk2s dt(SK_Scalar1 / lines);
317 Sk2s t(0);
318
319 SkPoint tmp[(1 << kMaxCubicSubdivideLevel) + 1];
320 SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp));
321
322 tmp[0] = pts[0];
323 Sk2s A = Sk2s::Load(&coeff[0].fX);
324 Sk2s B = Sk2s::Load(&coeff[1].fX);
325 Sk2s C = Sk2s::Load(&coeff[2].fX);
326 Sk2s D = Sk2s::Load(&coeff[3].fX);
327 for (int i = 1; i < lines; ++i) {
328 t += dt;
329 (((A * t + B) * t + C) * t + D).store(&tmp[i].fX);
330 }
331 tmp[lines] = pts[3];
332 lineproc(tmp, lines + 1, clip, blitter);
333 }
334 #endif
335
336 static inline void haircubic(const SkPoint pts[4], const SkRegion* clip,
230 SkBlitter* blitter, int level, SkScan::HairRgnProc linepro c) { 337 SkBlitter* blitter, int level, SkScan::HairRgnProc linepro c) {
338 #ifdef SK_SUPPORT_LEGACY_BLITANTIH2V2
231 if (level > 0) { 339 if (level > 0) {
232 SkPoint tmp[7]; 340 SkPoint tmp[7];
233 341
234 SkChopCubicAt(pts, tmp, SK_Scalar1/2); 342 SkChopCubicAt(pts, tmp, SK_Scalar1/2);
235 haircubic(tmp, clip, blitter, level - 1, lineproc); 343 haircubic(tmp, clip, blitter, level - 1, lineproc);
236 haircubic(&tmp[3], clip, blitter, level - 1, lineproc); 344 haircubic(&tmp[3], clip, blitter, level - 1, lineproc);
237 } else { 345 } else {
238 SkPoint tmp[] = { pts[0], pts[3] }; 346 SkPoint tmp[] = { pts[0], pts[3] };
239 lineproc(tmp, 2, clip, blitter); 347 lineproc(tmp, 2, clip, blitter);
240 } 348 }
349 #else
350 if (quick_cubic_niceness_check(pts)) {
351 hair_cubic(pts, clip, blitter, lineproc);
352 } else {
353 SkPoint tmp[13];
354 SkScalar tValues[3];
355
356 int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues);
357 for (int i = 0; i < count; i++) {
358 hair_cubic(&tmp[i * 3], clip, blitter, lineproc);
359 }
360 }
361 #endif
241 } 362 }
242 363
243 #define kMaxCubicSubdivideLevel 6
244 #define kMaxQuadSubdivideLevel 5
245
246 static int compute_quad_level(const SkPoint pts[3]) { 364 static int compute_quad_level(const SkPoint pts[3]) {
247 int d = compute_int_quad_dist(pts); 365 int d = compute_int_quad_dist(pts);
248 /* quadratics approach the line connecting their start and end points 366 /* quadratics approach the line connecting their start and end points
249 4x closer with each subdivision, so we compute the number of 367 4x closer with each subdivision, so we compute the number of
250 subdivisions to be the minimum need to get that distance to be less 368 subdivisions to be the minimum need to get that distance to be less
251 than a pixel. 369 than a pixel.
252 */ 370 */
253 int level = (33 - SkCLZ(d)) >> 1; 371 int level = (33 - SkCLZ(d)) >> 1;
254 // sanity check on level (from the previous version) 372 // sanity check on level (from the previous version)
255 if (level > kMaxQuadSubdivideLevel) { 373 if (level > kMaxQuadSubdivideLevel) {
(...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after
304 const SkScalar tol = SK_Scalar1 / 4; 422 const SkScalar tol = SK_Scalar1 / 4;
305 const SkPoint* quadPts = converter.computeQuads(pts, 423 const SkPoint* quadPts = converter.computeQuads(pts,
306 iter.conicWeight(), tol); 424 iter.conicWeight(), tol);
307 for (int i = 0; i < converter.countQuads(); ++i) { 425 for (int i = 0; i < converter.countQuads(); ++i) {
308 int level = compute_quad_level(quadPts); 426 int level = compute_quad_level(quadPts);
309 hairquad(quadPts, clip, blitter, level, lineproc); 427 hairquad(quadPts, clip, blitter, level, lineproc);
310 quadPts += 2; 428 quadPts += 2;
311 } 429 }
312 break; 430 break;
313 } 431 }
314 case SkPath::kCubic_Verb: 432 case SkPath::kCubic_Verb: {
315 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc) ; 433 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc) ;
316 break; 434 } break;
317 case SkPath::kClose_Verb: 435 case SkPath::kClose_Verb:
318 break; 436 break;
319 case SkPath::kDone_Verb: 437 case SkPath::kDone_Verb:
320 break; 438 break;
321 } 439 }
322 } 440 }
323 } 441 }
324 442
325 void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* b litter) { 443 void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* b litter) {
326 hair_path(path, clip, blitter, SkScan::HairLineRgn); 444 hair_path(path, clip, blitter, SkScan::HairLineRgn);
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after
400 518
401 SkAAClipBlitterWrapper wrap; 519 SkAAClipBlitterWrapper wrap;
402 if (!clip.quickContains(r.roundOut().makeOutset(1, 1))) { 520 if (!clip.quickContains(r.roundOut().makeOutset(1, 1))) {
403 wrap.init(clip, blitter); 521 wrap.init(clip, blitter);
404 blitter = wrap.getBlitter(); 522 blitter = wrap.getBlitter();
405 clipRgn = &wrap.getRgn(); 523 clipRgn = &wrap.getRgn();
406 } 524 }
407 AntiHairLineRgn(pts, count, clipRgn, blitter); 525 AntiHairLineRgn(pts, count, clipRgn, blitter);
408 } 526 }
409 } 527 }
OLDNEW
« no previous file with comments | « src/core/SkGeometry.cpp ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698