1/* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "SkScan.h" 9#include "SkBlitter.h" 10#include "SkRasterClip.h" 11#include "SkFDot6.h" 12#include "SkLineClipper.h" 13 14static void horiline(int x, int stopx, SkFixed fy, SkFixed dy, 15 SkBlitter* blitter) { 16 SkASSERT(x < stopx); 17 18 do { 19 blitter->blitH(x, fy >> 16, 1); 20 fy += dy; 21 } while (++x < stopx); 22} 23 24static void vertline(int y, int stopy, SkFixed fx, SkFixed dx, 25 SkBlitter* blitter) { 26 SkASSERT(y < stopy); 27 28 do { 29 blitter->blitH(fx >> 16, y, 1); 30 fx += dx; 31 } while (++y < stopy); 32} 33 34#ifdef SK_DEBUG 35static bool canConvertFDot6ToFixed(SkFDot6 x) { 36 const int maxDot6 = SK_MaxS32 >> (16 - 6); 37 return SkAbs32(x) <= maxDot6; 38} 39#endif 40 41void SkScan::HairLineRgn(const SkPoint array[], int arrayCount, const SkRegion* clip, 42 SkBlitter* origBlitter) { 43 SkBlitterClipper clipper; 44 SkIRect clipR, ptsR; 45 46 const SkScalar max = SkIntToScalar(32767); 47 const SkRect fixedBounds = SkRect::MakeLTRB(-max, -max, max, max); 48 49 SkRect clipBounds; 50 if (clip) { 51 clipBounds.set(clip->getBounds()); 52 } 53 54 for (int i = 0; i < arrayCount - 1; ++i) { 55 SkBlitter* blitter = origBlitter; 56 57 SkPoint pts[2]; 58 59 // We have to pre-clip the line to fit in a SkFixed, so we just chop 60 // the line. TODO find a way to actually draw beyond that range. 61 if (!SkLineClipper::IntersectLine(&array[i], fixedBounds, pts)) { 62 continue; 63 } 64 65 // Perform a clip in scalar space, so we catch huge values which might 66 // be missed after we convert to SkFDot6 (overflow) 67 if (clip && !SkLineClipper::IntersectLine(pts, clipBounds, pts)) { 68 continue; 69 } 70 71 SkFDot6 x0 = SkScalarToFDot6(pts[0].fX); 72 SkFDot6 y0 = SkScalarToFDot6(pts[0].fY); 73 SkFDot6 x1 = SkScalarToFDot6(pts[1].fX); 74 SkFDot6 y1 = SkScalarToFDot6(pts[1].fY); 75 76 SkASSERT(canConvertFDot6ToFixed(x0)); 77 SkASSERT(canConvertFDot6ToFixed(y0)); 78 SkASSERT(canConvertFDot6ToFixed(x1)); 79 SkASSERT(canConvertFDot6ToFixed(y1)); 80 81 if (clip) { 82 // now perform clipping again, as the rounding to dot6 can wiggle us 83 // our rects are really dot6 rects, but since we've already used 84 // lineclipper, we know they will fit in 32bits (26.6) 85 const SkIRect& bounds = clip->getBounds(); 86 87 clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop), 88 SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom)); 89 ptsR.set(x0, y0, x1, y1); 90 ptsR.sort(); 91 92 // outset the right and bottom, to account for how hairlines are 93 // actually drawn, which may hit the pixel to the right or below of 94 // the coordinate 95 ptsR.fRight += SK_FDot6One; 96 ptsR.fBottom += SK_FDot6One; 97 98 if (!SkIRect::Intersects(ptsR, clipR)) { 99 continue; 100 } 101 if (!clip->isRect() || !clipR.contains(ptsR)) { 102 blitter = clipper.apply(origBlitter, clip); 103 } 104 } 105 106 SkFDot6 dx = x1 - x0; 107 SkFDot6 dy = y1 - y0; 108 109 if (SkAbs32(dx) > SkAbs32(dy)) { // mostly horizontal 110 if (x0 > x1) { // we want to go left-to-right 111 SkTSwap<SkFDot6>(x0, x1); 112 SkTSwap<SkFDot6>(y0, y1); 113 } 114 int ix0 = SkFDot6Round(x0); 115 int ix1 = SkFDot6Round(x1); 116 if (ix0 == ix1) {// too short to draw 117 continue; 118 } 119 120 SkFixed slope = SkFixedDiv(dy, dx); 121 SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6); 122 123 horiline(ix0, ix1, startY, slope, blitter); 124 } else { // mostly vertical 125 if (y0 > y1) { // we want to go top-to-bottom 126 SkTSwap<SkFDot6>(x0, x1); 127 SkTSwap<SkFDot6>(y0, y1); 128 } 129 int iy0 = SkFDot6Round(y0); 130 int iy1 = SkFDot6Round(y1); 131 if (iy0 == iy1) { // too short to draw 132 continue; 133 } 134 135 SkFixed slope = SkFixedDiv(dx, dy); 136 SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6); 137 138 vertline(iy0, iy1, startX, slope, blitter); 139 } 140 } 141} 142 143// we don't just draw 4 lines, 'cause that can leave a gap in the bottom-right 144// and double-hit the top-left. 145// TODO: handle huge coordinates on rect (before calling SkScalarToFixed) 146void SkScan::HairRect(const SkRect& rect, const SkRasterClip& clip, 147 SkBlitter* blitter) { 148 SkAAClipBlitterWrapper wrapper; 149 SkBlitterClipper clipper; 150 SkIRect r; 151 152 r.set(SkScalarToFixed(rect.fLeft) >> 16, 153 SkScalarToFixed(rect.fTop) >> 16, 154 (SkScalarToFixed(rect.fRight) >> 16) + 1, 155 (SkScalarToFixed(rect.fBottom) >> 16) + 1); 156 157 if (clip.quickReject(r)) { 158 return; 159 } 160 if (!clip.quickContains(r)) { 161 const SkRegion* clipRgn; 162 if (clip.isBW()) { 163 clipRgn = &clip.bwRgn(); 164 } else { 165 wrapper.init(clip, blitter); 166 clipRgn = &wrapper.getRgn(); 167 blitter = wrapper.getBlitter(); 168 } 169 blitter = clipper.apply(blitter, clipRgn); 170 } 171 172 int width = r.width(); 173 int height = r.height(); 174 175 if ((width | height) == 0) { 176 return; 177 } 178 if (width <= 2 || height <= 2) { 179 blitter->blitRect(r.fLeft, r.fTop, width, height); 180 return; 181 } 182 // if we get here, we know we have 4 segments to draw 183 blitter->blitH(r.fLeft, r.fTop, width); // top 184 blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left 185 blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right 186 blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom 187} 188 189/////////////////////////////////////////////////////////////////////////////// 190 191#include "SkPath.h" 192#include "SkGeometry.h" 193#include "SkNx.h" 194 195#define kMaxCubicSubdivideLevel 6 196#define kMaxQuadSubdivideLevel 5 197 198static int compute_int_quad_dist(const SkPoint pts[3]) { 199 // compute the vector between the control point ([1]) and the middle of the 200 // line connecting the start and end ([0] and [2]) 201 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX; 202 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY; 203 // we want everyone to be positive 204 dx = SkScalarAbs(dx); 205 dy = SkScalarAbs(dy); 206 // convert to whole pixel values (use ceiling to be conservative) 207 int idx = SkScalarCeilToInt(dx); 208 int idy = SkScalarCeilToInt(dy); 209 // use the cheap approx for distance 210 if (idx > idy) { 211 return idx + (idy >> 1); 212 } else { 213 return idy + (idx >> 1); 214 } 215} 216 217static void hairquad(const SkPoint pts[3], const SkRegion* clip, 218 SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) { 219 SkASSERT(level <= kMaxQuadSubdivideLevel); 220 221 SkPoint coeff[3]; 222 SkQuadToCoeff(pts, coeff); 223 224 const int lines = 1 << level; 225 Sk2s t(0); 226 Sk2s dt(SK_Scalar1 / lines); 227 228 SkPoint tmp[(1 << kMaxQuadSubdivideLevel) + 1]; 229 SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp)); 230 231 tmp[0] = pts[0]; 232 Sk2s A = Sk2s::Load(&coeff[0].fX); 233 Sk2s B = Sk2s::Load(&coeff[1].fX); 234 Sk2s C = Sk2s::Load(&coeff[2].fX); 235 for (int i = 1; i < lines; ++i) { 236 t += dt; 237 ((A * t + B) * t + C).store(&tmp[i].fX); 238 } 239 tmp[lines] = pts[2]; 240 lineproc(tmp, lines + 1, clip, blitter); 241} 242 243static inline Sk2s abs(const Sk2s& value) { 244 return Sk2s::Max(value, -value); 245} 246 247static inline SkScalar max_component(const Sk2s& value) { 248 SkScalar components[2]; 249 value.store(components); 250 return SkTMax(components[0], components[1]); 251} 252 253static inline int compute_cubic_segs(const SkPoint pts[4]) { 254 Sk2s p0 = from_point(pts[0]); 255 Sk2s p1 = from_point(pts[1]); 256 Sk2s p2 = from_point(pts[2]); 257 Sk2s p3 = from_point(pts[3]); 258 259 const Sk2s oneThird(1.0f / 3.0f); 260 const Sk2s twoThird(2.0f / 3.0f); 261 262 Sk2s p13 = oneThird * p3 + twoThird * p0; 263 Sk2s p23 = oneThird * p0 + twoThird * p3; 264 265 SkScalar diff = max_component(Sk2s::Max(abs(p1 - p13), abs(p2 - p23))); 266 SkScalar tol = SK_Scalar1 / 8; 267 268 for (int i = 0; i < kMaxCubicSubdivideLevel; ++i) { 269 if (diff < tol) { 270 return 1 << i; 271 } 272 tol *= 4; 273 } 274 return 1 << kMaxCubicSubdivideLevel; 275} 276 277static bool lt_90(SkPoint p0, SkPoint pivot, SkPoint p2) { 278 return SkVector::DotProduct(p0 - pivot, p2 - pivot) >= 0; 279} 280 281// The off-curve points are "inside" the limits of the on-curve pts 282static bool quick_cubic_niceness_check(const SkPoint pts[4]) { 283 return lt_90(pts[1], pts[0], pts[3]) && 284 lt_90(pts[2], pts[0], pts[3]) && 285 lt_90(pts[1], pts[3], pts[0]) && 286 lt_90(pts[2], pts[3], pts[0]); 287} 288 289static void hair_cubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter, 290 SkScan::HairRgnProc lineproc) { 291 const int lines = compute_cubic_segs(pts); 292 SkASSERT(lines > 0); 293 if (1 == lines) { 294 SkPoint tmp[2] = { pts[0], pts[3] }; 295 lineproc(tmp, 2, clip, blitter); 296 return; 297 } 298 299 SkPoint coeff[4]; 300 SkCubicToCoeff(pts, coeff); 301 302 const Sk2s dt(SK_Scalar1 / lines); 303 Sk2s t(0); 304 305 SkPoint tmp[(1 << kMaxCubicSubdivideLevel) + 1]; 306 SkASSERT((unsigned)lines < SK_ARRAY_COUNT(tmp)); 307 308 tmp[0] = pts[0]; 309 Sk2s A = Sk2s::Load(&coeff[0].fX); 310 Sk2s B = Sk2s::Load(&coeff[1].fX); 311 Sk2s C = Sk2s::Load(&coeff[2].fX); 312 Sk2s D = Sk2s::Load(&coeff[3].fX); 313 for (int i = 1; i < lines; ++i) { 314 t += dt; 315 (((A * t + B) * t + C) * t + D).store(&tmp[i].fX); 316 } 317 tmp[lines] = pts[3]; 318 lineproc(tmp, lines + 1, clip, blitter); 319} 320 321static inline void haircubic(const SkPoint pts[4], const SkRegion* clip, 322 SkBlitter* blitter, int level, SkScan::HairRgnProc lineproc) { 323 if (quick_cubic_niceness_check(pts)) { 324 hair_cubic(pts, clip, blitter, lineproc); 325 } else { 326 SkPoint tmp[13]; 327 SkScalar tValues[3]; 328 329 int count = SkChopCubicAtMaxCurvature(pts, tmp, tValues); 330 for (int i = 0; i < count; i++) { 331 hair_cubic(&tmp[i * 3], clip, blitter, lineproc); 332 } 333 } 334} 335 336static int compute_quad_level(const SkPoint pts[3]) { 337 int d = compute_int_quad_dist(pts); 338 /* quadratics approach the line connecting their start and end points 339 4x closer with each subdivision, so we compute the number of 340 subdivisions to be the minimum need to get that distance to be less 341 than a pixel. 342 */ 343 int level = (33 - SkCLZ(d)) >> 1; 344 // sanity check on level (from the previous version) 345 if (level > kMaxQuadSubdivideLevel) { 346 level = kMaxQuadSubdivideLevel; 347 } 348 return level; 349} 350 351static void hair_path(const SkPath& path, const SkRasterClip& rclip, SkBlitter* blitter, 352 SkScan::HairRgnProc lineproc) { 353 if (path.isEmpty()) { 354 return; 355 } 356 357 SkAAClipBlitterWrapper wrap; 358 const SkRegion* clip = NULL; 359 360 { 361 const SkIRect ibounds = path.getBounds().roundOut().makeOutset(1, 1); 362 363 if (rclip.quickReject(ibounds)) { 364 return; 365 } 366 if (!rclip.quickContains(ibounds)) { 367 if (rclip.isBW()) { 368 clip = &rclip.bwRgn(); 369 } else { 370 wrap.init(rclip, blitter); 371 blitter = wrap.getBlitter(); 372 clip = &wrap.getRgn(); 373 } 374 } 375 } 376 377 SkPath::Iter iter(path, false); 378 SkPoint pts[4]; 379 SkPath::Verb verb; 380 SkAutoConicToQuads converter; 381 382 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 383 switch (verb) { 384 case SkPath::kMove_Verb: 385 break; 386 case SkPath::kLine_Verb: 387 lineproc(pts, 2, clip, blitter); 388 break; 389 case SkPath::kQuad_Verb: 390 hairquad(pts, clip, blitter, compute_quad_level(pts), lineproc); 391 break; 392 case SkPath::kConic_Verb: { 393 // how close should the quads be to the original conic? 394 const SkScalar tol = SK_Scalar1 / 4; 395 const SkPoint* quadPts = converter.computeQuads(pts, 396 iter.conicWeight(), tol); 397 for (int i = 0; i < converter.countQuads(); ++i) { 398 int level = compute_quad_level(quadPts); 399 hairquad(quadPts, clip, blitter, level, lineproc); 400 quadPts += 2; 401 } 402 break; 403 } 404 case SkPath::kCubic_Verb: { 405 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc); 406 } break; 407 case SkPath::kClose_Verb: 408 break; 409 case SkPath::kDone_Verb: 410 break; 411 } 412 } 413} 414 415void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) { 416 hair_path(path, clip, blitter, SkScan::HairLineRgn); 417} 418 419void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip, SkBlitter* blitter) { 420 hair_path(path, clip, blitter, SkScan::AntiHairLineRgn); 421} 422 423/////////////////////////////////////////////////////////////////////////////// 424 425void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize, 426 const SkRasterClip& clip, SkBlitter* blitter) { 427 SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0); 428 429 if (strokeSize.fX < 0 || strokeSize.fY < 0) { 430 return; 431 } 432 433 const SkScalar dx = strokeSize.fX; 434 const SkScalar dy = strokeSize.fY; 435 SkScalar rx = SkScalarHalf(dx); 436 SkScalar ry = SkScalarHalf(dy); 437 SkRect outer, tmp; 438 439 outer.set(r.fLeft - rx, r.fTop - ry, 440 r.fRight + rx, r.fBottom + ry); 441 442 if (r.width() <= dx || r.height() <= dx) { 443 SkScan::FillRect(outer, clip, blitter); 444 return; 445 } 446 447 tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy); 448 SkScan::FillRect(tmp, clip, blitter); 449 tmp.fTop = outer.fBottom - dy; 450 tmp.fBottom = outer.fBottom; 451 SkScan::FillRect(tmp, clip, blitter); 452 453 tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy); 454 SkScan::FillRect(tmp, clip, blitter); 455 tmp.fLeft = outer.fRight - dx; 456 tmp.fRight = outer.fRight; 457 SkScan::FillRect(tmp, clip, blitter); 458} 459 460void SkScan::HairLine(const SkPoint pts[], int count, const SkRasterClip& clip, 461 SkBlitter* blitter) { 462 if (clip.isBW()) { 463 HairLineRgn(pts, count, &clip.bwRgn(), blitter); 464 } else { 465 const SkRegion* clipRgn = NULL; 466 467 SkRect r; 468 r.set(pts, count); 469 r.outset(SK_ScalarHalf, SK_ScalarHalf); 470 471 SkAAClipBlitterWrapper wrap; 472 if (!clip.quickContains(r.roundOut())) { 473 wrap.init(clip, blitter); 474 blitter = wrap.getBlitter(); 475 clipRgn = &wrap.getRgn(); 476 } 477 HairLineRgn(pts, count, clipRgn, blitter); 478 } 479} 480 481void SkScan::AntiHairLine(const SkPoint pts[], int count, const SkRasterClip& clip, 482 SkBlitter* blitter) { 483 if (clip.isBW()) { 484 AntiHairLineRgn(pts, count, &clip.bwRgn(), blitter); 485 } else { 486 const SkRegion* clipRgn = NULL; 487 488 SkRect r; 489 r.set(pts, count); 490 491 SkAAClipBlitterWrapper wrap; 492 if (!clip.quickContains(r.roundOut().makeOutset(1, 1))) { 493 wrap.init(clip, blitter); 494 blitter = wrap.getBlitter(); 495 clipRgn = &wrap.getRgn(); 496 } 497 AntiHairLineRgn(pts, count, clipRgn, blitter); 498 } 499} 500