SkScan_Hairline.cpp revision 761fb62b0eb174783316d2a8b933fba896ca6355
1/* libs/graphics/sgl/SkScan_Hairline.cpp 2** 3** Copyright 2006, The Android Open Source Project 4** 5** Licensed under the Apache License, Version 2.0 (the "License"); 6** you may not use this file except in compliance with the License. 7** You may obtain a copy of the License at 8** 9** http://www.apache.org/licenses/LICENSE-2.0 10** 11** Unless required by applicable law or agreed to in writing, software 12** distributed under the License is distributed on an "AS IS" BASIS, 13** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14** See the License for the specific language governing permissions and 15** limitations under the License. 16*/ 17 18#include "SkScan.h" 19#include "SkBlitter.h" 20#include "SkRegion.h" 21#include "SkFDot6.h" 22#include "SkLineClipper.h" 23 24static void horiline(int x, int stopx, SkFixed fy, SkFixed dy, SkBlitter* blitter) 25{ 26 SkASSERT(x < stopx); 27 28 do { 29 blitter->blitH(x, fy >> 16, 1); 30 fy += dy; 31 } while (++x < stopx); 32} 33 34static void vertline(int y, int stopy, SkFixed fx, SkFixed dx, SkBlitter* blitter) 35{ 36 SkASSERT(y < stopy); 37 38 do { 39 blitter->blitH(fx >> 16, y, 1); 40 fx += dx; 41 } while (++y < stopy); 42} 43 44void SkScan::HairLine(const SkPoint& pt0, const SkPoint& pt1, const SkRegion* clip, SkBlitter* blitter) 45{ 46 SkBlitterClipper clipper; 47 SkRect r; 48 SkIRect clipR, ptsR; 49 SkPoint pts[2] = { pt0, pt1 }; 50 51 if (clip) { 52 // Perform a clip in scalar space, so we catch huge values which might 53 // be missed after we convert to SkFDot6 (overflow) 54 r.set(clip->getBounds()); 55 if (!SkLineClipper::IntersectLine(pts, r, pts)) { 56 return; 57 } 58 } 59 60 SkFDot6 x0 = SkScalarToFDot6(pts[0].fX); 61 SkFDot6 y0 = SkScalarToFDot6(pts[0].fY); 62 SkFDot6 x1 = SkScalarToFDot6(pts[1].fX); 63 SkFDot6 y1 = SkScalarToFDot6(pts[1].fY); 64 65 if (clip) { 66 // now perform clipping again, as the rounding to dot6 can wiggle us 67 // our rects are really dot6 rects, but since we've already used 68 // lineclipper, we know they will fit in 32bits (26.6) 69 const SkIRect& bounds = clip->getBounds(); 70 71 clipR.set(SkIntToFDot6(bounds.fLeft), SkIntToFDot6(bounds.fTop), 72 SkIntToFDot6(bounds.fRight), SkIntToFDot6(bounds.fBottom)); 73 ptsR.set(x0, y0, x1, y1); 74 ptsR.sort(); 75 76 // outset the right and bottom, to account for how hairlines are 77 // actually drawn, which may hit the pixel to the right or below of 78 // the coordinate 79 ptsR.fRight += SK_FDot61; 80 ptsR.fBottom += SK_FDot61; 81 82 if (!SkIRect::Intersects(ptsR, clipR)) { 83 return; 84 } 85 if (clip->isRect() && clipR.contains(ptsR)) { 86 clip = NULL; 87 } else { 88 blitter = clipper.apply(blitter, clip); 89 } 90 } 91 92 SkFDot6 dx = x1 - x0; 93 SkFDot6 dy = y1 - y0; 94 95 if (SkAbs32(dx) > SkAbs32(dy)) // mostly horizontal 96 { 97 if (x0 > x1) // we want to go left-to-right 98 { 99 SkTSwap<SkFDot6>(x0, x1); 100 SkTSwap<SkFDot6>(y0, y1); 101 } 102 int ix0 = SkFDot6Round(x0); 103 int ix1 = SkFDot6Round(x1); 104 if (ix0 == ix1) // too short to draw 105 return; 106 107 SkFixed slope = SkFixedDiv(dy, dx); 108 SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6); 109 110 horiline(ix0, ix1, startY, slope, blitter); 111 } 112 else // mostly vertical 113 { 114 if (y0 > y1) // we want to go top-to-bottom 115 { 116 SkTSwap<SkFDot6>(x0, x1); 117 SkTSwap<SkFDot6>(y0, y1); 118 } 119 int iy0 = SkFDot6Round(y0); 120 int iy1 = SkFDot6Round(y1); 121 if (iy0 == iy1) // too short to draw 122 return; 123 124 SkFixed slope = SkFixedDiv(dx, dy); 125 SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6); 126 127 vertline(iy0, iy1, startX, slope, blitter); 128 } 129} 130 131// we don't just draw 4 lines, 'cause that can leave a gap in the bottom-right 132// and double-hit the top-left. 133// TODO: handle huge coordinates on rect (before calling SkScalarToFixed) 134void SkScan::HairRect(const SkRect& rect, const SkRegion* clip, SkBlitter* blitter) 135{ 136 SkBlitterClipper clipper; 137 SkIRect r; 138 139 r.set(SkScalarToFixed(rect.fLeft) >> 16, 140 SkScalarToFixed(rect.fTop) >> 16, 141 (SkScalarToFixed(rect.fRight) >> 16) + 1, 142 (SkScalarToFixed(rect.fBottom) >> 16) + 1); 143 144 if (clip) 145 { 146 if (clip->quickReject(r)) 147 return; 148 if (!clip->quickContains(r)) 149 blitter = clipper.apply(blitter, clip); 150 } 151 152 int width = r.width(); 153 int height = r.height(); 154 155 if ((width | height) == 0) 156 return; 157 if (width <= 2 || height <= 2) 158 { 159 blitter->blitRect(r.fLeft, r.fTop, width, height); 160 return; 161 } 162 // if we get here, we know we have 4 segments to draw 163 blitter->blitH(r.fLeft, r.fTop, width); // top 164 blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left 165 blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right 166 blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom 167} 168 169///////////////////////////////////////////////////////////////////////////////////////////////// 170 171#include "SkPath.h" 172#include "SkGeometry.h" 173 174static bool quad_too_curvy(const SkPoint pts[3]) 175{ 176 return true; 177} 178 179static int compute_int_quad_dist(const SkPoint pts[3]) { 180 // compute the vector between the control point ([1]) and the middle of the 181 // line connecting the start and end ([0] and [2]) 182 SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX; 183 SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY; 184 // we want everyone to be positive 185 dx = SkScalarAbs(dx); 186 dy = SkScalarAbs(dy); 187 // convert to whole pixel values (use ceiling to be conservative) 188 int idx = SkScalarCeil(dx); 189 int idy = SkScalarCeil(dy); 190 // use the cheap approx for distance 191 if (idx > idy) { 192 return idx + (idy >> 1); 193 } else { 194 return idy + (idx >> 1); 195 } 196} 197 198static void hairquad(const SkPoint pts[3], const SkRegion* clip, SkBlitter* blitter, int level, 199 void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion* clip, SkBlitter*)) 200{ 201#if 1 202 if (level > 0 && quad_too_curvy(pts)) 203 { 204 SkPoint tmp[5]; 205 206 SkChopQuadAtHalf(pts, tmp); 207 hairquad(tmp, clip, blitter, level - 1, lineproc); 208 hairquad(&tmp[2], clip, blitter, level - 1, lineproc); 209 } 210 else 211 lineproc(pts[0], pts[2], clip, blitter); 212#else 213 int count = 1 << level; 214 const SkScalar dt = SkFixedToScalar(SK_Fixed1 >> level); 215 SkScalar t = dt; 216 SkPoint prevPt = pts[0]; 217 for (int i = 1; i < count; i++) { 218 SkPoint nextPt; 219 SkEvalQuadAt(pts, t, &nextPt); 220 lineproc(prevPt, nextPt, clip, blitter); 221 t += dt; 222 prevPt = nextPt; 223 } 224 // draw the last line explicitly to 1.0, in case t didn't match that exactly 225 lineproc(prevPt, pts[2], clip, blitter); 226#endif 227} 228 229static bool cubic_too_curvy(const SkPoint pts[4]) 230{ 231 return true; 232} 233 234static void haircubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter, int level, 235 void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*)) 236{ 237 if (level > 0 && cubic_too_curvy(pts)) 238 { 239 SkPoint tmp[7]; 240 241 SkChopCubicAt(pts, tmp, SK_Scalar1/2); 242 haircubic(tmp, clip, blitter, level - 1, lineproc); 243 haircubic(&tmp[3], clip, blitter, level - 1, lineproc); 244 } 245 else 246 lineproc(pts[0], pts[3], clip, blitter); 247} 248 249#define kMaxCubicSubdivideLevel 6 250#define kMaxQuadSubdivideLevel 5 251 252static void hair_path(const SkPath& path, const SkRegion* clip, SkBlitter* blitter, 253 void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*)) 254{ 255 if (path.isEmpty()) 256 return; 257 258 const SkIRect* clipR = NULL; 259 260 if (clip) 261 { 262 SkIRect ibounds; 263 path.getBounds().roundOut(&ibounds); 264 ibounds.inset(-1, -1); 265 266 if (clip->quickReject(ibounds)) 267 return; 268 269 if (clip->quickContains(ibounds)) 270 clip = NULL; 271 else 272 clipR = &clip->getBounds(); 273 } 274 275 SkPath::Iter iter(path, false); 276 SkPoint pts[4]; 277 SkPath::Verb verb; 278 279 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) 280 { 281 switch (verb) { 282 case SkPath::kLine_Verb: 283 lineproc(pts[0], pts[1], clip, blitter); 284 break; 285 case SkPath::kQuad_Verb: { 286 int d = compute_int_quad_dist(pts); 287 /* quadratics approach the line connecting their start and end points 288 4x closer with each subdivision, so we compute the number of 289 subdivisions to be the minimum need to get that distance to be less 290 than a pixel. 291 */ 292 int level = (33 - SkCLZ(d)) >> 1; 293// SkDebugf("----- distance %d computedLevel %d\n", d, computedLevel); 294 // sanity check on level (from the previous version) 295 if (level > kMaxQuadSubdivideLevel) { 296 level = kMaxQuadSubdivideLevel; 297 } 298 hairquad(pts, clip, blitter, level, lineproc); 299 break; 300 } 301 case SkPath::kCubic_Verb: 302 haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc); 303 break; 304 default: 305 break; 306 } 307 } 308} 309 310void SkScan::HairPath(const SkPath& path, const SkRegion* clip, SkBlitter* blitter) 311{ 312 hair_path(path, clip, blitter, SkScan::HairLine); 313} 314 315void SkScan::AntiHairPath(const SkPath& path, const SkRegion* clip, SkBlitter* blitter) 316{ 317 hair_path(path, clip, blitter, SkScan::AntiHairLine); 318} 319 320/////////////////////////////////////////////////////////////////////////////// 321 322void SkScan::FrameRect(const SkRect& r, const SkPoint& strokeSize, 323 const SkRegion* clip, SkBlitter* blitter) { 324 SkASSERT(strokeSize.fX >= 0 && strokeSize.fY >= 0); 325 326 if (strokeSize.fX < 0 || strokeSize.fY < 0) { 327 return; 328 } 329 330 const SkScalar dx = strokeSize.fX; 331 const SkScalar dy = strokeSize.fY; 332 SkScalar rx = SkScalarHalf(dx); 333 SkScalar ry = SkScalarHalf(dy); 334 SkRect outer, tmp; 335 336 outer.set(r.fLeft - rx, r.fTop - ry, 337 r.fRight + rx, r.fBottom + ry); 338 339 if (r.width() <= dx || r.height() <= dx) { 340 SkScan::FillRect(outer, clip, blitter); 341 return; 342 } 343 344 tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + dy); 345 SkScan::FillRect(tmp, clip, blitter); 346 tmp.fTop = outer.fBottom - dy; 347 tmp.fBottom = outer.fBottom; 348 SkScan::FillRect(tmp, clip, blitter); 349 350 tmp.set(outer.fLeft, outer.fTop + dy, outer.fLeft + dx, outer.fBottom - dy); 351 SkScan::FillRect(tmp, clip, blitter); 352 tmp.fLeft = outer.fRight - dx; 353 tmp.fRight = outer.fRight; 354 SkScan::FillRect(tmp, clip, blitter); 355} 356 357