reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame^] | 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 | |
| 23 | static void horiline(int x, int stopx, SkFixed fy, SkFixed dy, SkBlitter* blitter) |
| 24 | { |
| 25 | SkASSERT(x < stopx); |
| 26 | |
| 27 | do { |
| 28 | blitter->blitH(x, fy >> 16, 1); |
| 29 | fy += dy; |
| 30 | } while (++x < stopx); |
| 31 | } |
| 32 | |
| 33 | static void vertline(int y, int stopy, SkFixed fx, SkFixed dx, SkBlitter* blitter) |
| 34 | { |
| 35 | SkASSERT(y < stopy); |
| 36 | |
| 37 | do { |
| 38 | blitter->blitH(fx >> 16, y, 1); |
| 39 | fx += dx; |
| 40 | } while (++y < stopy); |
| 41 | } |
| 42 | |
| 43 | void SkScan::HairLine(const SkPoint& pt0, const SkPoint& pt1, const SkRegion* clip, SkBlitter* blitter) |
| 44 | { |
| 45 | SkBlitterClipper clipper; |
| 46 | |
| 47 | SkFDot6 x0 = SkScalarToFDot6(pt0.fX); |
| 48 | SkFDot6 y0 = SkScalarToFDot6(pt0.fY); |
| 49 | SkFDot6 x1 = SkScalarToFDot6(pt1.fX); |
| 50 | SkFDot6 y1 = SkScalarToFDot6(pt1.fY); |
| 51 | |
| 52 | if (clip) |
| 53 | { |
| 54 | SkRect r; |
| 55 | SkIRect ir; |
| 56 | SkPoint pts[2]; |
| 57 | |
| 58 | pts[0] = pt0; |
| 59 | pts[1] = pt1; |
| 60 | r.set(pts, 2); |
| 61 | r.roundOut(&ir); |
| 62 | |
| 63 | // if we're given a horizontal or vertical line |
| 64 | // this rect could be empty (in area), in which case |
| 65 | // clip->quickReject() will always return true. |
| 66 | // hence we bloat the rect to avoid that case |
| 67 | if (ir.width() == 0) |
| 68 | ir.fRight += 1; |
| 69 | if (ir.height() == 0) |
| 70 | ir.fBottom += 1; |
| 71 | |
| 72 | if (clip->quickReject(ir)) |
| 73 | return; |
| 74 | if (clip->quickContains(ir)) |
| 75 | clip = NULL; |
| 76 | else |
| 77 | { |
| 78 | blitter = clipper.apply(blitter, clip); |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | SkFDot6 dx = x1 - x0; |
| 83 | SkFDot6 dy = y1 - y0; |
| 84 | |
| 85 | if (SkAbs32(dx) > SkAbs32(dy)) // mostly horizontal |
| 86 | { |
| 87 | if (x0 > x1) // we want to go left-to-right |
| 88 | { |
| 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 | SkFixed slope = SkFixedDiv(dy, dx); |
| 98 | SkFixed startY = SkFDot6ToFixed(y0) + (slope * ((32 - x0) & 63) >> 6); |
| 99 | |
| 100 | horiline(ix0, ix1, startY, slope, blitter); |
| 101 | } |
| 102 | else // mostly vertical |
| 103 | { |
| 104 | if (y0 > y1) // we want to go top-to-bottom |
| 105 | { |
| 106 | SkTSwap<SkFDot6>(x0, x1); |
| 107 | SkTSwap<SkFDot6>(y0, y1); |
| 108 | } |
| 109 | int iy0 = SkFDot6Round(y0); |
| 110 | int iy1 = SkFDot6Round(y1); |
| 111 | if (iy0 == iy1) // too short to draw |
| 112 | return; |
| 113 | |
| 114 | SkFixed slope = SkFixedDiv(dx, dy); |
| 115 | SkFixed startX = SkFDot6ToFixed(x0) + (slope * ((32 - y0) & 63) >> 6); |
| 116 | |
| 117 | vertline(iy0, iy1, startX, slope, blitter); |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | // we don't just draw 4 lines, 'cause that can leave a gap in the bottom-right |
| 122 | // and double-hit the top-left. |
| 123 | void SkScan::HairRect(const SkRect& rect, const SkRegion* clip, SkBlitter* blitter) |
| 124 | { |
| 125 | SkBlitterClipper clipper; |
| 126 | SkIRect r; |
| 127 | |
| 128 | r.set(SkScalarToFixed(rect.fLeft) >> 16, |
| 129 | SkScalarToFixed(rect.fTop) >> 16, |
| 130 | (SkScalarToFixed(rect.fRight) >> 16) + 1, |
| 131 | (SkScalarToFixed(rect.fBottom) >> 16) + 1); |
| 132 | |
| 133 | if (clip) |
| 134 | { |
| 135 | if (clip->quickReject(r)) |
| 136 | return; |
| 137 | if (!clip->quickContains(r)) |
| 138 | blitter = clipper.apply(blitter, clip); |
| 139 | } |
| 140 | |
| 141 | int width = r.width(); |
| 142 | int height = r.height(); |
| 143 | |
| 144 | if ((width | height) == 0) |
| 145 | return; |
| 146 | if (width <= 2 || height <= 2) |
| 147 | { |
| 148 | blitter->blitRect(r.fLeft, r.fTop, width, height); |
| 149 | return; |
| 150 | } |
| 151 | // if we get here, we know we have 4 segments to draw |
| 152 | blitter->blitH(r.fLeft, r.fTop, width); // top |
| 153 | blitter->blitRect(r.fLeft, r.fTop + 1, 1, height - 2); // left |
| 154 | blitter->blitRect(r.fRight - 1, r.fTop + 1, 1, height - 2); // right |
| 155 | blitter->blitH(r.fLeft, r.fBottom - 1, width); // bottom |
| 156 | } |
| 157 | |
| 158 | ///////////////////////////////////////////////////////////////////////////////////////////////// |
| 159 | |
| 160 | #include "SkPath.h" |
| 161 | #include "SkGeometry.h" |
| 162 | |
| 163 | static bool quad_too_curvy(const SkPoint pts[3]) |
| 164 | { |
| 165 | return true; |
| 166 | } |
| 167 | |
| 168 | static int compute_int_quad_dist(const SkPoint pts[3]) { |
| 169 | // compute the vector between the control point ([1]) and the middle of the |
| 170 | // line connecting the start and end ([0] and [2]) |
| 171 | SkScalar dx = SkScalarHalf(pts[0].fX + pts[2].fX) - pts[1].fX; |
| 172 | SkScalar dy = SkScalarHalf(pts[0].fY + pts[2].fY) - pts[1].fY; |
| 173 | // we want everyone to be positive |
| 174 | dx = SkScalarAbs(dx); |
| 175 | dy = SkScalarAbs(dy); |
| 176 | // convert to whole pixel values (use ceiling to be conservative) |
| 177 | int idx = SkScalarCeil(dx); |
| 178 | int idy = SkScalarCeil(dy); |
| 179 | // use the cheap approx for distance |
| 180 | if (idx > idy) { |
| 181 | return idx + (idy >> 1); |
| 182 | } else { |
| 183 | return idy + (idx >> 1); |
| 184 | } |
| 185 | } |
| 186 | |
| 187 | static void hairquad(const SkPoint pts[3], const SkRegion* clip, SkBlitter* blitter, int level, |
| 188 | void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion* clip, SkBlitter*)) |
| 189 | { |
| 190 | #if 1 |
| 191 | if (level > 0 && quad_too_curvy(pts)) |
| 192 | { |
| 193 | SkPoint tmp[5]; |
| 194 | |
| 195 | SkChopQuadAtHalf(pts, tmp); |
| 196 | hairquad(tmp, clip, blitter, level - 1, lineproc); |
| 197 | hairquad(&tmp[2], clip, blitter, level - 1, lineproc); |
| 198 | } |
| 199 | else |
| 200 | lineproc(pts[0], pts[2], clip, blitter); |
| 201 | #else |
| 202 | int count = 1 << level; |
| 203 | const SkScalar dt = SkFixedToScalar(SK_Fixed1 >> level); |
| 204 | SkScalar t = dt; |
| 205 | SkPoint prevPt = pts[0]; |
| 206 | for (int i = 1; i < count; i++) { |
| 207 | SkPoint nextPt; |
| 208 | SkEvalQuadAt(pts, t, &nextPt); |
| 209 | lineproc(prevPt, nextPt, clip, blitter); |
| 210 | t += dt; |
| 211 | prevPt = nextPt; |
| 212 | } |
| 213 | // draw the last line explicitly to 1.0, in case t didn't match that exactly |
| 214 | lineproc(prevPt, pts[2], clip, blitter); |
| 215 | #endif |
| 216 | } |
| 217 | |
| 218 | static bool cubic_too_curvy(const SkPoint pts[4]) |
| 219 | { |
| 220 | return true; |
| 221 | } |
| 222 | |
| 223 | static void haircubic(const SkPoint pts[4], const SkRegion* clip, SkBlitter* blitter, int level, |
| 224 | void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*)) |
| 225 | { |
| 226 | if (level > 0 && cubic_too_curvy(pts)) |
| 227 | { |
| 228 | SkPoint tmp[7]; |
| 229 | |
| 230 | SkChopCubicAt(pts, tmp, SK_Scalar1/2); |
| 231 | haircubic(tmp, clip, blitter, level - 1, lineproc); |
| 232 | haircubic(&tmp[3], clip, blitter, level - 1, lineproc); |
| 233 | } |
| 234 | else |
| 235 | lineproc(pts[0], pts[3], clip, blitter); |
| 236 | } |
| 237 | |
| 238 | #define kMaxCubicSubdivideLevel 6 |
| 239 | #define kMaxQuadSubdivideLevel 5 |
| 240 | |
| 241 | static void hair_path(const SkPath& path, const SkRegion* clip, SkBlitter* blitter, |
| 242 | void (*lineproc)(const SkPoint&, const SkPoint&, const SkRegion*, SkBlitter*)) |
| 243 | { |
| 244 | if (path.isEmpty()) |
| 245 | return; |
| 246 | |
| 247 | const SkIRect* clipR = NULL; |
| 248 | |
| 249 | if (clip) |
| 250 | { |
| 251 | SkRect bounds; |
| 252 | SkIRect ibounds; |
| 253 | |
| 254 | path.computeBounds(&bounds, SkPath::kFast_BoundsType); |
| 255 | bounds.roundOut(&ibounds); |
| 256 | ibounds.inset(-1, -1); |
| 257 | |
| 258 | if (clip->quickReject(ibounds)) |
| 259 | return; |
| 260 | |
| 261 | if (clip->quickContains(ibounds)) |
| 262 | clip = NULL; |
| 263 | else |
| 264 | clipR = &clip->getBounds(); |
| 265 | } |
| 266 | |
| 267 | SkPath::Iter iter(path, false); |
| 268 | SkPoint pts[4]; |
| 269 | SkPath::Verb verb; |
| 270 | |
| 271 | while ((verb = iter.next(pts)) != SkPath::kDone_Verb) |
| 272 | { |
| 273 | switch (verb) { |
| 274 | case SkPath::kLine_Verb: |
| 275 | lineproc(pts[0], pts[1], clip, blitter); |
| 276 | break; |
| 277 | case SkPath::kQuad_Verb: { |
| 278 | int d = compute_int_quad_dist(pts); |
| 279 | /* quadratics approach the line connecting their start and end points |
| 280 | 4x closer with each subdivision, so we compute the number of |
| 281 | subdivisions to be the minimum need to get that distance to be less |
| 282 | than a pixel. |
| 283 | */ |
| 284 | int level = (33 - SkCLZ(d)) >> 1; |
| 285 | // SkDebugf("----- distance %d computedLevel %d\n", d, computedLevel); |
| 286 | // sanity check on level (from the previous version) |
| 287 | if (level > kMaxQuadSubdivideLevel) { |
| 288 | level = kMaxQuadSubdivideLevel; |
| 289 | } |
| 290 | hairquad(pts, clip, blitter, level, lineproc); |
| 291 | break; |
| 292 | } |
| 293 | case SkPath::kCubic_Verb: |
| 294 | haircubic(pts, clip, blitter, kMaxCubicSubdivideLevel, lineproc); |
| 295 | break; |
| 296 | default: |
| 297 | break; |
| 298 | } |
| 299 | } |
| 300 | } |
| 301 | |
| 302 | void SkScan::HairPath(const SkPath& path, const SkRegion* clip, SkBlitter* blitter) |
| 303 | { |
| 304 | hair_path(path, clip, blitter, SkScan::HairLine); |
| 305 | } |
| 306 | |
| 307 | void SkScan::AntiHairPath(const SkPath& path, const SkRegion* clip, SkBlitter* blitter) |
| 308 | { |
| 309 | hair_path(path, clip, blitter, SkScan::AntiHairLine); |
| 310 | } |
| 311 | |
| 312 | //////////////////////////////////////////////////////////////////////////////// |
| 313 | |
| 314 | void SkScan::FrameRect(const SkRect& r, SkScalar diameter, const SkRegion* clip, SkBlitter* blitter) |
| 315 | { |
| 316 | SkASSERT(diameter > 0); |
| 317 | |
| 318 | if (r.isEmpty()) |
| 319 | return; |
| 320 | |
| 321 | SkScalar radius = diameter / 2; |
| 322 | SkRect outer, tmp; |
| 323 | |
| 324 | outer.set( r.fLeft - radius, r.fTop - radius, |
| 325 | r.fRight + radius, r.fBottom + radius); |
| 326 | |
| 327 | if (r.width() <= diameter || r.height() <= diameter) |
| 328 | { |
| 329 | SkScan::FillRect(outer, clip, blitter); |
| 330 | return; |
| 331 | } |
| 332 | |
| 333 | tmp.set(outer.fLeft, outer.fTop, outer.fRight, outer.fTop + diameter); |
| 334 | SkScan::FillRect(tmp, clip, blitter); |
| 335 | tmp.fTop = outer.fBottom - diameter; |
| 336 | tmp.fBottom = outer.fBottom; |
| 337 | SkScan::FillRect(tmp, clip, blitter); |
| 338 | |
| 339 | tmp.set(outer.fLeft, outer.fTop + diameter, outer.fLeft + diameter, outer.fBottom - diameter); |
| 340 | SkScan::FillRect(tmp, clip, blitter); |
| 341 | tmp.fLeft = outer.fRight - diameter; |
| 342 | tmp.fRight = outer.fRight; |
| 343 | SkScan::FillRect(tmp, clip, blitter); |
| 344 | } |
| 345 | |