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 // We have to pre-clip the line to fit in a SkFixed, so we just chop 51 // the line. TODO find a way to actually draw beyond that range. 52 { 53 SkRect fixedBounds; 54 const SkScalar max = SkIntToScalar(32767); 55 fixedBounds.set(-max, -max, max, max); 56 if (!SkLineClipper::IntersectLine(pts, fixedBounds, pts)) { 57 return; 58 } 59 } 60 61 if (clip) { 62 // Perform a clip in scalar space, so we catch huge values which might 63 // be missed after we convert to SkFDot6 (overflow) 64 r.set(clip->getBounds()); 65 if (!SkLineClipper::IntersectLine(pts, r, pts)) { 66 return; 67 } 68 } 69 70 SkFDot6 x0 = SkScalarToFDot6(pts[0].fX); 71 SkFDot6 y0 = SkScalarToFDot6(pts[0].fY); 72 SkFDot6 x1 = SkScalarToFDot6(pts[1].fX); 73 SkFDot6 y1 = SkScalarToFDot6(pts[1].fY); 74 75 SkASSERT(canConvertFDot6ToFixed(x0)); 76 SkASSERT(canConvertFDot6ToFixed(y0)); 77 SkASSERT(canConvertFDot6ToFixed(x1)); 78 SkASSERT(canConvertFDot6ToFixed(y1)); 79 80 if (clip) { 81 // now perform clipping again, as the rounding to dot6 can wiggle us 82 // our rects are really dot6 rects, but since we've already used 83 // lineclipper, we know they will fit in 32bits (26.6) 84 const SkIRect& bounds = clip->getBounds(); 85 86 clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop), 87 SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom)); 88 ptsR.set(x0, y0, x1, y1); 89 ptsR.sort(); 90 91 // outset the right and bottom, to account for how hairlines are 92 // actually drawn, which may hit the pixel to the right or below of 93 // the coordinate 94 ptsR.fRight += SK_FDot6One; 95 ptsR.fBottom += SK_FDot6One; 96 97 if (!SkIRect::Intersects(ptsR, clipR)) { 98 return; 99 } 100 if (clip->isRect() && clipR.contains(ptsR)) { 101 clip = NULL; 102 } else { 103 blitter = clipper.apply(blitter, clip); 104 } 105 } 106 107 SkFDot6 dx = x1 - x0; 108 SkFDot6 dy = y1 - y0; 109 110 if (SkAbs32(dx) > SkAbs32(dy)) { // mostly horizontal 111 if (x0 > x1) { // we want to go left-to-right 112 SkTSwap<SkFDot6>(x0, x1); 113 SkTSwap<SkFDot6>(y0, y1); 114 } 115 int ix0 = SkFDot6Round(x0); 116 int ix1 = SkFDot6Round(x1); 117 if (ix0 == ix1) {// too short to draw 118 return; 119 } 120 121 SkFixed slope = SkFixedDiv(dy, dx); 122 SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6); 123 124 horiline(ix0, ix1, startY, slope, blitter); 125 } else { // mostly vertical 126 if (y0 > y1) { // we want to go top-to-bottom 127 SkTSwap<SkFDot6>(x0, x1); 128 SkTSwap<SkFDot6>(y0, y1); 129 } 130 int iy0 = SkFDot6Round(y0); 131 int iy1 = SkFDot6Round(y1); 132 if (iy0 == iy1) { // too short to draw 133 return; 134 } 135 136 SkFixed slope = SkFixedDiv(dx, dy); 137 SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6); 138 139 vertline(iy0, iy1, startX, slope, blitter); 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) 146 void 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 194 static int compute_int_quad_dist(const SkPoint pts[3]) { 195 // compute the vector between the control point ([1]) and the middle of the 196 // line connecting the start and end ([0] and [2]) 197 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX; 198 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY; 199 // we want everyone to be positive 200 dx = SkScalarAbs(dx); 201 dy = SkScalarAbs(dy); 202 // convert to whole pixel values (use ceiling to be conservative) 203 int idx = SkScalarCeilToInt(dx); 204 int idy = SkScalarCeilToInt(dy); 205 // use the cheap approx for distance 206 if (idx > idy) { 207 return idx + (idy >> 1); 208 } else { 209 return idy + (idx >> 1); 210 } 211 } 212 213 typedef void (*LineProc)(const SkPoint&, const SkPoint&, const SkRegion*, 214 SkBlitter*); 215 216 static void hairquad(const SkPoint pts[3], const SkRegion* clip, 217 SkBlitter* blitter, int level, LineProc lineproc) { 218 if (level > 0) { 219 SkPoint tmp[5]; 220 221 SkChopQuadAtHalf(pts, tmp); 222 hairquad(tmp, clip, blitter, level - 1, lineproc); 223 hairquad(&tmp[2], clip, blitter, level - 1, lineproc); 224 } else { 225 lineproc(pts[0], pts[2], clip, blitter); 226 } 227 } 228 229 static void haircubic(const SkPoint pts[4], const SkRegion* clip, 230 SkBlitter* blitter, int level, LineProc lineproc) { 231 if (level > 0) { 232 SkPoint tmp[7]; 233 234 SkChopCubicAt(pts, tmp, SK_Scalar1/2); 235 haircubic(tmp, clip, blitter, level - 1, lineproc); 236 haircubic(&tmp[3], clip, blitter, level - 1, lineproc); 237 } else { 238 lineproc(pts[0], pts[3], clip, blitter); 239 } 240 } 241 242 #define kMaxCubicSubdivideLevel 6 243 #define kMaxQuadSubdivideLevel 5 244 245 static int compute_quad_level(const SkPoint pts[3]) { 246 int d = compute_int_quad_dist(pts); 247 /* quadratics approach the line connecting their start and end points 248 4x closer with each subdivision, so we compute the number of 249 subdivisions to be the minimum need to get that distance to be less 250 than a pixel. 251 */ 252 int level = (33 - SkCLZ(d)) >> 1; 253 // sanity check on level (from the previous version) 254 if (level > kMaxQuadSubdivideLevel) { 255 level = kMaxQuadSubdivideLevel; 256 } 257 return level; 258 } 259 260 static void hair_path(const SkPath& path, const SkRasterClip& rclip, 261 SkBlitter* blitter, LineProc lineproc) { 262 if (path.isEmpty()) { 263 return; 264 } 265 266 SkAAClipBlitterWrapper wrap; 267 const SkRegion* clip = NULL; 268 269 { 270 SkIRect ibounds; 271 path.getBounds().roundOut(&ibounds); 272 ibounds.inset(-1, -1); 273 274 if (rclip.quickReject(ibounds)) { 275 return; 276 } 277 if (!rclip.quickContains(ibounds)) { 278 if (rclip.isBW()) { 279 clip = &rclip.bwRgn(); 280 } else { 281 wrap.init(rclip, blitter); 282 blitter = wrap.getBlitter(); 283 clip = &wrap.getRgn(); 284 } 285 } 286 } 287 288 SkPath::Iter iter(path, false); 289 SkPoint pts[4]; 290 SkPath::Verb verb; 291 SkAutoConicToQuads converter; 292 293 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 294 switch (verb) { 295 case SkPath::kMove_Verb: 296 break; 297 case SkPath::kLine_Verb: 298 lineproc(pts[0], pts[1], clip, blitter); 299 break; 300 case SkPath::kQuad_Verb: 301 hairquad(pts, clip, blitter, compute_quad_level(pts), lineproc); 302 break; 303 case SkPath::kConic_Verb: { 304 // how close should the quads be to the original conic? 305 const SkScalar tol = SK_Scalar1 / 4; 306 const SkPoint* quadPts = converter.computeQuads(pts, 307 iter.conicWeight(), tol); 308 for (int i = 0; i < converter.countQuads(); ++i) { 309 int level = compute_quad_level(quadPts); 310 hairquad(quadPts, clip, blitter, level, lineproc); 311 quadPts += 2; 312 } 313 break; 314 } 315 case SkPath::kCubic_Verb: 316 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc); 317 break; 318 case SkPath::kClose_Verb: 319 break; 320 case SkPath::kDone_Verb: 321 break; 322 } 323 } 324 } 325 326 void SkScan::HairPath(const SkPath& path, const SkRasterClip& clip, 327 SkBlitter* blitter) { 328 hair_path(path, clip, blitter, SkScan::HairLineRgn); 329 } 330 331 void SkScan::AntiHairPath(const SkPath& path, const SkRasterClip& clip, 332 SkBlitter* blitter) { 333 hair_path(path, clip, blitter, SkScan::AntiHairLineRgn); 334 } 335 336 /////////////////////////////////////////////////////////////////////////////// 337 338 void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize, 339 const SkRasterClip& clip, SkBlitter* blitter) { 340 SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0); 341 342 if (strokeSize.fX < 0 || strokeSize.fY < 0) { 343 return; 344 } 345 346 const SkScalar dx = strokeSize.fX; 347 const SkScalar dy = strokeSize.fY; 348 SkScalar rx = SkScalarHalf(dx); 349 SkScalar ry = SkScalarHalf(dy); 350 SkRect outer, tmp; 351 352 outer.set(r.fLeft - rx, r.fTop - ry, 353 r.fRight + rx, r.fBottom + ry); 354 355 if (r.width() <= dx || r.height() <= dx) { 356 SkScan::FillRect(outer, clip, blitter); 357 return; 358 } 359 360 tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy); 361 SkScan::FillRect(tmp, clip, blitter); 362 tmp.fTop = outer.fBottom - dy; 363 tmp.fBottom = outer.fBottom; 364 SkScan::FillRect(tmp, clip, blitter); 365 366 tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy); 367 SkScan::FillRect(tmp, clip, blitter); 368 tmp.fLeft = outer.fRight - dx; 369 tmp.fRight = outer.fRight; 370 SkScan::FillRect(tmp, clip, blitter); 371 } 372 373 void SkScan::HairLine(const SkPoint& p0, const SkPoint& p1, 374 const SkRasterClip& clip, SkBlitter* blitter) { 375 if (clip.isBW()) { 376 HairLineRgn(p0, p1, &clip.bwRgn(), blitter); 377 } else { 378 const SkRegion* clipRgn = NULL; 379 SkRect r; 380 SkIRect ir; 381 r.set(p0.fX, p0.fY, p1.fX, p1.fY); 382 r.sort(); 383 r.inset(-SK_ScalarHalf, -SK_ScalarHalf); 384 r.roundOut(&ir); 385 386 SkAAClipBlitterWrapper wrap; 387 if (!clip.quickContains(ir)) { 388 wrap.init(clip, blitter); 389 blitter = wrap.getBlitter(); 390 clipRgn = &wrap.getRgn(); 391 } 392 HairLineRgn(p0, p1, clipRgn, blitter); 393 } 394 } 395 396 void SkScan::AntiHairLine(const SkPoint& p0, const SkPoint& p1, 397 const SkRasterClip& clip, SkBlitter* blitter) { 398 if (clip.isBW()) { 399 AntiHairLineRgn(p0, p1, &clip.bwRgn(), blitter); 400 } else { 401 const SkRegion* clipRgn = NULL; 402 SkRect r; 403 SkIRect ir; 404 r.set(p0.fX, p0.fY, p1.fX, p1.fY); 405 r.sort(); 406 r.roundOut(&ir); 407 ir.inset(-1, -1); 408 409 SkAAClipBlitterWrapper wrap; 410 if (!clip.quickContains(ir)) { 411 wrap.init(clip, blitter); 412 blitter = wrap.getBlitter(); 413 clipRgn = &wrap.getRgn(); 414 } 415 AntiHairLineRgn(p0, p1, clipRgn, blitter); 416 } 417 } 418
