epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2006 The Android Open Source Project |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 8 | |
| 9 | #ifndef SkScanPriv_DEFINED |
| 10 | #define SkScanPriv_DEFINED |
| 11 | |
Yuqian Li | ca50b87 | 2017-06-12 10:40:50 -0400 | [diff] [blame] | 12 | #include "SkPath.h" |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 13 | #include "SkScan.h" |
| 14 | #include "SkBlitter.h" |
| 15 | |
| 16 | class SkScanClipper { |
| 17 | public: |
reed@google.com | 5ee6491 | 2012-06-11 17:30:33 +0000 | [diff] [blame] | 18 | SkScanClipper(SkBlitter* blitter, const SkRegion* clip, const SkIRect& bounds, |
| 19 | bool skipRejectTest = false); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 20 | |
| 21 | SkBlitter* getBlitter() const { return fBlitter; } |
| 22 | const SkIRect* getClipRect() const { return fClipRect; } |
| 23 | |
| 24 | private: |
| 25 | SkRectClipBlitter fRectBlitter; |
| 26 | SkRgnClipBlitter fRgnBlitter; |
Mike Reed | 28930b4 | 2016-11-09 15:23:26 -0500 | [diff] [blame] | 27 | #ifdef SK_DEBUG |
Yuqian Li | 99bba9e | 2016-11-21 09:44:59 -0500 | [diff] [blame] | 28 | SkRectClipCheckBlitter fRectClipCheckBlitter; |
Mike Reed | 28930b4 | 2016-11-09 15:23:26 -0500 | [diff] [blame] | 29 | #endif |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 30 | SkBlitter* fBlitter; |
| 31 | const SkIRect* fClipRect; |
| 32 | }; |
| 33 | |
Yuqian Li | e4b8b52 | 2016-11-16 10:12:58 -0500 | [diff] [blame] | 34 | void sk_fill_path(const SkPath& path, const SkIRect& clipRect, |
reed@android.com | dca6a56 | 2010-02-22 16:05:48 +0000 | [diff] [blame] | 35 | SkBlitter* blitter, int start_y, int stop_y, int shiftEdgesUp, |
Yuqian Li | e4b8b52 | 2016-11-16 10:12:58 -0500 | [diff] [blame] | 36 | bool pathContainedInClip); |
| 37 | |
reed@google.com | 55b6b58 | 2011-03-02 15:58:18 +0000 | [diff] [blame] | 38 | // blit the rects above and below avoid, clipped to clip |
| 39 | void sk_blit_above(SkBlitter*, const SkIRect& avoid, const SkRegion& clip); |
| 40 | void sk_blit_below(SkBlitter*, const SkIRect& avoid, const SkRegion& clip); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 41 | |
Yuqian Li | a33b43d | 2017-03-17 11:26:29 -0400 | [diff] [blame] | 42 | template<class EdgeType> |
| 43 | static inline void remove_edge(EdgeType* edge) { |
| 44 | edge->fPrev->fNext = edge->fNext; |
| 45 | edge->fNext->fPrev = edge->fPrev; |
| 46 | } |
| 47 | |
| 48 | template<class EdgeType> |
| 49 | static inline void insert_edge_after(EdgeType* edge, EdgeType* afterMe) { |
| 50 | edge->fPrev = afterMe; |
| 51 | edge->fNext = afterMe->fNext; |
| 52 | afterMe->fNext->fPrev = edge; |
| 53 | afterMe->fNext = edge; |
| 54 | } |
| 55 | |
| 56 | template<class EdgeType> |
| 57 | static void backward_insert_edge_based_on_x(EdgeType* edge) { |
| 58 | SkFixed x = edge->fX; |
| 59 | EdgeType* prev = edge->fPrev; |
| 60 | while (prev->fPrev && prev->fX > x) { |
| 61 | prev = prev->fPrev; |
| 62 | } |
| 63 | if (prev->fNext != edge) { |
| 64 | remove_edge(edge); |
| 65 | insert_edge_after(edge, prev); |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | // Start from the right side, searching backwards for the point to begin the new edge list |
| 70 | // insertion, marching forwards from here. The implementation could have started from the left |
| 71 | // of the prior insertion, and search to the right, or with some additional caching, binary |
| 72 | // search the starting point. More work could be done to determine optimal new edge insertion. |
| 73 | template<class EdgeType> |
| 74 | static EdgeType* backward_insert_start(EdgeType* prev, SkFixed x) { |
| 75 | while (prev->fPrev && prev->fX > x) { |
| 76 | prev = prev->fPrev; |
| 77 | } |
| 78 | return prev; |
| 79 | } |
| 80 | |
Yuqian Li | ca50b87 | 2017-06-12 10:40:50 -0400 | [diff] [blame] | 81 | static bool fitsInsideLimit(const SkRect& r, SkScalar max) { |
| 82 | const SkScalar min = -max; |
| 83 | return r.fLeft > min && r.fTop > min && |
| 84 | r.fRight < max && r.fBottom < max; |
| 85 | } |
| 86 | |
| 87 | static int overflows_short_shift(int value, int shift) { |
| 88 | const int s = 16 + shift; |
| 89 | return (SkLeftShift(value, s) >> s) - value; |
| 90 | } |
| 91 | |
| 92 | /** |
| 93 | Would any of the coordinates of this rectangle not fit in a short, |
| 94 | when left-shifted by shift? |
| 95 | */ |
| 96 | static int rect_overflows_short_shift(SkIRect rect, int shift) { |
| 97 | SkASSERT(!overflows_short_shift(8191, shift)); |
| 98 | SkASSERT(overflows_short_shift(8192, shift)); |
| 99 | SkASSERT(!overflows_short_shift(32767, 0)); |
| 100 | SkASSERT(overflows_short_shift(32768, 0)); |
| 101 | |
| 102 | // Since we expect these to succeed, we bit-or together |
| 103 | // for a tiny extra bit of speed. |
| 104 | return overflows_short_shift(rect.fLeft, shift) | |
| 105 | overflows_short_shift(rect.fRight, shift) | |
| 106 | overflows_short_shift(rect.fTop, shift) | |
| 107 | overflows_short_shift(rect.fBottom, shift); |
| 108 | } |
| 109 | |
| 110 | static bool safeRoundOut(const SkRect& src, SkIRect* dst, int32_t maxInt) { |
| 111 | const SkScalar maxScalar = SkIntToScalar(maxInt); |
| 112 | |
| 113 | if (fitsInsideLimit(src, maxScalar)) { |
| 114 | src.roundOut(dst); |
| 115 | return true; |
| 116 | } |
| 117 | return false; |
| 118 | } |
| 119 | |
Yuqian Li | f60c1a3 | 2017-09-25 11:18:08 -0400 | [diff] [blame^] | 120 | // Check if the path is a rect and fat enough after clipping; if so, blit it. |
| 121 | static inline bool TryBlitFatAntiRect(SkBlitter* blitter, const SkPath& path, const SkIRect& clip) { |
| 122 | SkRect rect; |
| 123 | if (!path.isRect(&rect)) { |
| 124 | return false; // not rect |
| 125 | } |
| 126 | if (!rect.intersect(SkRect::Make(clip))) { |
| 127 | return true; // The intersection is empty. Hence consider it done. |
| 128 | } |
| 129 | SkIRect bounds = rect.roundOut(); |
| 130 | if (bounds.width() < 3 || bounds.height() < 3) { |
| 131 | return false; // not fat |
| 132 | } |
| 133 | blitter->blitFatAntiRect(rect); |
| 134 | return true; |
| 135 | } |
| 136 | |
Yuqian Li | ca50b87 | 2017-06-12 10:40:50 -0400 | [diff] [blame] | 137 | using FillPathFunc = std::function<void(const SkPath& path, SkBlitter* blitter, bool isInverse, |
| 138 | const SkIRect& ir, const SkRegion* clipRgn, const SkIRect* clipRect, bool forceRLE)>; |
| 139 | |
| 140 | static inline void do_fill_path(const SkPath& path, const SkRegion& origClip, SkBlitter* blitter, |
| 141 | bool forceRLE, const int SHIFT, FillPathFunc fillPathFunc) { |
| 142 | if (origClip.isEmpty()) { |
| 143 | return; |
| 144 | } |
| 145 | |
| 146 | const bool isInverse = path.isInverseFillType(); |
| 147 | SkIRect ir; |
| 148 | |
| 149 | if (!safeRoundOut(path.getBounds(), &ir, SK_MaxS32 >> SHIFT)) { |
| 150 | // Bounds can't fit in SkIRect; we'll return without drawing |
| 151 | return; |
| 152 | } |
| 153 | if (ir.isEmpty()) { |
| 154 | if (isInverse) { |
| 155 | blitter->blitRegion(origClip); |
| 156 | } |
| 157 | return; |
| 158 | } |
| 159 | |
| 160 | // If the intersection of the path bounds and the clip bounds |
| 161 | // will overflow 32767 when << by SHIFT, we can't supersample, |
| 162 | // so draw without antialiasing. |
| 163 | SkIRect clippedIR; |
| 164 | if (isInverse) { |
| 165 | // If the path is an inverse fill, it's going to fill the entire |
| 166 | // clip, and we care whether the entire clip exceeds our limits. |
| 167 | clippedIR = origClip.getBounds(); |
| 168 | } else { |
| 169 | if (!clippedIR.intersect(ir, origClip.getBounds())) { |
| 170 | return; |
| 171 | } |
| 172 | } |
| 173 | if (rect_overflows_short_shift(clippedIR, SHIFT)) { |
| 174 | SkScan::FillPath(path, origClip, blitter); |
| 175 | return; |
| 176 | } |
| 177 | |
| 178 | // Our antialiasing can't handle a clip larger than 32767, so we restrict |
| 179 | // the clip to that limit here. (the runs[] uses int16_t for its index). |
| 180 | // |
| 181 | // A more general solution (one that could also eliminate the need to |
| 182 | // disable aa based on ir bounds (see overflows_short_shift) would be |
| 183 | // to tile the clip/target... |
| 184 | SkRegion tmpClipStorage; |
| 185 | const SkRegion* clipRgn = &origClip; |
| 186 | { |
| 187 | static const int32_t kMaxClipCoord = 32767; |
| 188 | const SkIRect& bounds = origClip.getBounds(); |
| 189 | if (bounds.fRight > kMaxClipCoord || bounds.fBottom > kMaxClipCoord) { |
| 190 | SkIRect limit = { 0, 0, kMaxClipCoord, kMaxClipCoord }; |
| 191 | tmpClipStorage.op(origClip, limit, SkRegion::kIntersect_Op); |
| 192 | clipRgn = &tmpClipStorage; |
| 193 | } |
| 194 | } |
| 195 | // for here down, use clipRgn, not origClip |
| 196 | |
| 197 | SkScanClipper clipper(blitter, clipRgn, ir); |
| 198 | const SkIRect* clipRect = clipper.getClipRect(); |
| 199 | |
| 200 | if (clipper.getBlitter() == nullptr) { // clipped out |
| 201 | if (isInverse) { |
| 202 | blitter->blitRegion(*clipRgn); |
| 203 | } |
| 204 | return; |
| 205 | } |
| 206 | |
| 207 | SkASSERT(clipper.getClipRect() == nullptr || |
| 208 | *clipper.getClipRect() == clipRgn->getBounds()); |
| 209 | |
| 210 | // now use the (possibly wrapped) blitter |
| 211 | blitter = clipper.getBlitter(); |
| 212 | |
| 213 | if (isInverse) { |
| 214 | sk_blit_above(blitter, ir, *clipRgn); |
| 215 | } |
| 216 | |
| 217 | SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); |
| 218 | |
| 219 | fillPathFunc(path, blitter, isInverse, ir, clipRgn, clipRect, forceRLE); |
| 220 | |
| 221 | if (isInverse) { |
| 222 | sk_blit_below(blitter, ir, *clipRgn); |
| 223 | } |
| 224 | } |
| 225 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 226 | #endif |