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