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