epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 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 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 9 | |
| 10 | #include "SkRegionPriv.h" |
| 11 | #include "SkTemplates.h" |
| 12 | #include "SkThread.h" |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 13 | #include "SkUtils.h" |
| 14 | |
| 15 | /* Region Layout |
| 16 | * |
| 17 | * TOP |
| 18 | * |
| 19 | * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ] |
| 20 | * ... |
| 21 | * |
| 22 | * Y-Sentinel |
| 23 | */ |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 24 | |
| 25 | SkDEBUGCODE(int32_t gRgnAllocCounter;) |
| 26 | |
| 27 | ///////////////////////////////////////////////////////////////////////////////////////////////// |
| 28 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 29 | /* Pass in the beginning with the intervals. |
| 30 | * We back up 1 to read the interval-count. |
| 31 | * Return the beginning of the next scanline (i.e. the next Y-value) |
| 32 | */ |
| 33 | static SkRegion::RunType* skip_intervals(const SkRegion::RunType runs[]) { |
| 34 | int intervals = runs[-1]; |
| 35 | #ifdef SK_DEBUG |
| 36 | if (intervals > 0) { |
| 37 | SkASSERT(runs[0] < runs[1]); |
| 38 | SkASSERT(runs[1] < SkRegion::kRunTypeSentinel); |
| 39 | } else { |
| 40 | SkASSERT(0 == intervals); |
| 41 | SkASSERT(SkRegion::kRunTypeSentinel == runs[0]); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 42 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 43 | #endif |
| 44 | runs += intervals * 2 + 1; |
| 45 | return const_cast<SkRegion::RunType*>(runs); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 46 | } |
| 47 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 48 | bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count, |
| 49 | SkIRect* bounds) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 50 | assert_sentinel(runs[0], false); // top |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 51 | SkASSERT(count >= kRectRegionRuns); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 52 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 53 | if (count == kRectRegionRuns) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 54 | assert_sentinel(runs[1], false); // bottom |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 55 | SkASSERT(1 == runs[2]); |
| 56 | assert_sentinel(runs[3], false); // left |
| 57 | assert_sentinel(runs[4], false); // right |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 58 | assert_sentinel(runs[5], true); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 59 | assert_sentinel(runs[6], true); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 60 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 61 | SkASSERT(runs[0] < runs[1]); // valid height |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 62 | SkASSERT(runs[3] < runs[4]); // valid width |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 63 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 64 | bounds->set(runs[3], runs[0], runs[4], runs[1]); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 65 | return true; |
| 66 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 67 | return false; |
| 68 | } |
| 69 | |
| 70 | ////////////////////////////////////////////////////////////////////////// |
| 71 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 72 | SkRegion::SkRegion() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 73 | fBounds.set(0, 0, 0, 0); |
| 74 | fRunHead = SkRegion_gEmptyRunHeadPtr; |
| 75 | } |
| 76 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 77 | SkRegion::SkRegion(const SkRegion& src) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 78 | fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead) |
| 79 | this->setRegion(src); |
| 80 | } |
| 81 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 82 | SkRegion::SkRegion(const SkIRect& rect) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 83 | fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead) |
| 84 | this->setRect(rect); |
| 85 | } |
| 86 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 87 | SkRegion::~SkRegion() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 88 | this->freeRuns(); |
| 89 | } |
| 90 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 91 | void SkRegion::freeRuns() { |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 92 | if (this->isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 93 | SkASSERT(fRunHead->fRefCnt >= 1); |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 94 | if (sk_atomic_dec(&fRunHead->fRefCnt) == 1) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 95 | //SkASSERT(gRgnAllocCounter > 0); |
| 96 | //SkDEBUGCODE(sk_atomic_dec(&gRgnAllocCounter)); |
| 97 | //SkDEBUGF(("************** gRgnAllocCounter::free %d\n", gRgnAllocCounter)); |
| 98 | sk_free(fRunHead); |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 103 | void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) { |
| 104 | fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount); |
| 105 | } |
| 106 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 107 | void SkRegion::allocateRuns(int count) { |
| 108 | fRunHead = RunHead::Alloc(count); |
| 109 | } |
| 110 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 111 | void SkRegion::allocateRuns(const RunHead& head) { |
| 112 | fRunHead = RunHead::Alloc(head.fRunCount, |
| 113 | head.getYSpanCount(), |
| 114 | head.getIntervalCount()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 115 | } |
| 116 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 117 | SkRegion& SkRegion::operator=(const SkRegion& src) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 118 | (void)this->setRegion(src); |
| 119 | return *this; |
| 120 | } |
| 121 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 122 | void SkRegion::swap(SkRegion& other) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 123 | SkTSwap<SkIRect>(fBounds, other.fBounds); |
| 124 | SkTSwap<RunHead*>(fRunHead, other.fRunHead); |
| 125 | } |
| 126 | |
commit-bot@chromium.org | 5dd567c | 2013-07-17 21:39:28 +0000 | [diff] [blame] | 127 | int SkRegion::computeRegionComplexity() const { |
| 128 | if (this->isEmpty()) { |
| 129 | return 0; |
| 130 | } else if (this->isRect()) { |
| 131 | return 1; |
| 132 | } |
| 133 | return fRunHead->getIntervalCount(); |
| 134 | } |
skia.committer@gmail.com | f7d01ce | 2013-07-18 07:00:56 +0000 | [diff] [blame^] | 135 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 136 | bool SkRegion::setEmpty() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 137 | this->freeRuns(); |
| 138 | fBounds.set(0, 0, 0, 0); |
| 139 | fRunHead = SkRegion_gEmptyRunHeadPtr; |
| 140 | return false; |
| 141 | } |
| 142 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 143 | bool SkRegion::setRect(int32_t left, int32_t top, |
| 144 | int32_t right, int32_t bottom) { |
| 145 | if (left >= right || top >= bottom) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 146 | return this->setEmpty(); |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 147 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 148 | this->freeRuns(); |
| 149 | fBounds.set(left, top, right, bottom); |
| 150 | fRunHead = SkRegion_gRectRunHeadPtr; |
| 151 | return true; |
| 152 | } |
| 153 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 154 | bool SkRegion::setRect(const SkIRect& r) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 155 | return this->setRect(r.fLeft, r.fTop, r.fRight, r.fBottom); |
| 156 | } |
| 157 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 158 | bool SkRegion::setRegion(const SkRegion& src) { |
| 159 | if (this != &src) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 160 | this->freeRuns(); |
| 161 | |
| 162 | fBounds = src.fBounds; |
| 163 | fRunHead = src.fRunHead; |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 164 | if (this->isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 165 | sk_atomic_inc(&fRunHead->fRefCnt); |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 166 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 167 | } |
| 168 | return fRunHead != SkRegion_gEmptyRunHeadPtr; |
| 169 | } |
| 170 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 171 | bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 172 | SkRegion tmp(rect); |
| 173 | |
| 174 | return this->op(tmp, rgn, op); |
| 175 | } |
| 176 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 177 | bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 178 | SkRegion tmp(rect); |
| 179 | |
| 180 | return this->op(rgn, tmp, op); |
| 181 | } |
| 182 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 183 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 184 | |
djsollen@google.com | 56c6977 | 2011-11-08 19:00:26 +0000 | [diff] [blame] | 185 | #ifdef SK_BUILD_FOR_ANDROID |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 186 | char* SkRegion::toString() { |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 187 | Iterator iter(*this); |
| 188 | int count = 0; |
| 189 | while (!iter.done()) { |
| 190 | count++; |
| 191 | iter.next(); |
| 192 | } |
| 193 | // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0' |
| 194 | const int max = (count*((11*4)+5))+11+1; |
| 195 | char* result = (char*)malloc(max); |
| 196 | if (result == NULL) { |
| 197 | return NULL; |
| 198 | } |
| 199 | count = sprintf(result, "SkRegion("); |
| 200 | iter.reset(*this); |
| 201 | while (!iter.done()) { |
| 202 | const SkIRect& r = iter.rect(); |
| 203 | count += sprintf(result+count, "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom); |
| 204 | iter.next(); |
| 205 | } |
| 206 | count += sprintf(result+count, ")"); |
| 207 | return result; |
| 208 | } |
| 209 | #endif |
| 210 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 211 | /////////////////////////////////////////////////////////////////////////////// |
djsollen@google.com | cd9d69b | 2011-03-14 20:30:14 +0000 | [diff] [blame] | 212 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 213 | int SkRegion::count_runtype_values(int* itop, int* ibot) const { |
| 214 | if (this == NULL) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 215 | *itop = SK_MinS32; |
| 216 | *ibot = SK_MaxS32; |
| 217 | return 0; |
| 218 | } |
| 219 | |
| 220 | int maxT; |
| 221 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 222 | if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 223 | maxT = 2; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 224 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 225 | SkASSERT(this->isComplex()); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 226 | maxT = fRunHead->getIntervalCount() * 2; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 227 | } |
| 228 | *itop = fBounds.fTop; |
| 229 | *ibot = fBounds.fBottom; |
| 230 | return maxT; |
| 231 | } |
| 232 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 233 | static bool isRunCountEmpty(int count) { |
| 234 | return count <= 2; |
| 235 | } |
| 236 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 237 | bool SkRegion::setRuns(RunType runs[], int count) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 238 | SkDEBUGCODE(this->validate();) |
| 239 | SkASSERT(count > 0); |
| 240 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 241 | if (isRunCountEmpty(count)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 242 | // SkDEBUGF(("setRuns: empty\n")); |
| 243 | assert_sentinel(runs[count-1], true); |
| 244 | return this->setEmpty(); |
| 245 | } |
| 246 | |
| 247 | // trim off any empty spans from the top and bottom |
| 248 | // weird I should need this, perhaps op() could be smarter... |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 249 | if (count > kRectRegionRuns) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 250 | RunType* stop = runs + count; |
| 251 | assert_sentinel(runs[0], false); // top |
| 252 | assert_sentinel(runs[1], false); // bottom |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 253 | // runs[2] is uncomputed intervalCount |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 254 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 255 | if (runs[3] == SkRegion::kRunTypeSentinel) { // should be first left... |
| 256 | runs += 3; // skip empty initial span |
| 257 | runs[0] = runs[-2]; // set new top to prev bottom |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 258 | assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 259 | assert_sentinel(runs[2], false); // intervalcount |
| 260 | assert_sentinel(runs[3], false); // left |
| 261 | assert_sentinel(runs[4], false); // right |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 262 | } |
| 263 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 264 | assert_sentinel(stop[-1], true); |
| 265 | assert_sentinel(stop[-2], true); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 266 | |
| 267 | // now check for a trailing empty span |
| 268 | if (stop[-5] == SkRegion::kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs |
| 269 | stop[-4] = SkRegion::kRunTypeSentinel; // kill empty last span |
| 270 | stop -= 3; |
| 271 | assert_sentinel(stop[-1], true); // last y-sentinel |
| 272 | assert_sentinel(stop[-2], true); // last x-sentinel |
| 273 | assert_sentinel(stop[-3], false); // last right |
| 274 | assert_sentinel(stop[-4], false); // last left |
| 275 | assert_sentinel(stop[-5], false); // last interval-count |
| 276 | assert_sentinel(stop[-6], false); // last bottom |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 277 | } |
| 278 | count = (int)(stop - runs); |
| 279 | } |
| 280 | |
| 281 | SkASSERT(count >= kRectRegionRuns); |
| 282 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 283 | if (SkRegion::RunsAreARect(runs, count, &fBounds)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 284 | return this->setRect(fBounds); |
| 285 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 286 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 287 | // if we get here, we need to become a complex region |
| 288 | |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 289 | if (!this->isComplex() || fRunHead->fRunCount != count) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 290 | this->freeRuns(); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 291 | this->allocateRuns(count); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 292 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 293 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 294 | // must call this before we can write directly into runs() |
| 295 | // in case we are sharing the buffer with another region (copy on write) |
| 296 | fRunHead = fRunHead->ensureWritable(); |
| 297 | memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType)); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 298 | fRunHead->computeRunBounds(&fBounds); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 299 | |
| 300 | SkDEBUGCODE(this->validate();) |
| 301 | |
| 302 | return true; |
| 303 | } |
| 304 | |
| 305 | void SkRegion::BuildRectRuns(const SkIRect& bounds, |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 306 | RunType runs[kRectRegionRuns]) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 307 | runs[0] = bounds.fTop; |
| 308 | runs[1] = bounds.fBottom; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 309 | runs[2] = 1; // 1 interval for this scanline |
| 310 | runs[3] = bounds.fLeft; |
| 311 | runs[4] = bounds.fRight; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 312 | runs[5] = kRunTypeSentinel; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 313 | runs[6] = kRunTypeSentinel; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 314 | } |
| 315 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 316 | bool SkRegion::contains(int32_t x, int32_t y) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 317 | SkDEBUGCODE(this->validate();) |
| 318 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 319 | if (!fBounds.contains(x, y)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 320 | return false; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 321 | } |
| 322 | if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 323 | return true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 324 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 325 | SkASSERT(this->isComplex()); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 326 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 327 | const RunType* runs = fRunHead->findScanline(y); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 328 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 329 | // Skip the Bottom and IntervalCount |
| 330 | runs += 2; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 331 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 332 | // Just walk this scanline, checking each interval. The X-sentinel will |
| 333 | // appear as a left-inteval (runs[0]) and should abort the search. |
| 334 | // |
| 335 | // We could do a bsearch, using interval-count (runs[1]), but need to time |
| 336 | // when that would be worthwhile. |
| 337 | // |
| 338 | for (;;) { |
| 339 | if (x < runs[0]) { |
| 340 | break; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 341 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 342 | if (x < runs[1]) { |
| 343 | return true; |
| 344 | } |
| 345 | runs += 2; |
| 346 | } |
| 347 | return false; |
| 348 | } |
| 349 | |
mike@reedtribe.org | 796a175 | 2012-11-07 03:39:46 +0000 | [diff] [blame] | 350 | static SkRegion::RunType scanline_bottom(const SkRegion::RunType runs[]) { |
| 351 | return runs[0]; |
| 352 | } |
| 353 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 354 | static const SkRegion::RunType* scanline_next(const SkRegion::RunType runs[]) { |
| 355 | // skip [B N [L R]... S] |
| 356 | return runs + 2 + runs[1] * 2 + 1; |
| 357 | } |
| 358 | |
| 359 | static bool scanline_contains(const SkRegion::RunType runs[], |
| 360 | SkRegion::RunType L, SkRegion::RunType R) { |
| 361 | runs += 2; // skip Bottom and IntervalCount |
| 362 | for (;;) { |
| 363 | if (L < runs[0]) { |
| 364 | break; |
| 365 | } |
| 366 | if (R <= runs[1]) { |
| 367 | return true; |
| 368 | } |
| 369 | runs += 2; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 370 | } |
| 371 | return false; |
| 372 | } |
| 373 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 374 | bool SkRegion::contains(const SkIRect& r) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 375 | SkDEBUGCODE(this->validate();) |
| 376 | |
| 377 | if (!fBounds.contains(r)) { |
| 378 | return false; |
| 379 | } |
| 380 | if (this->isRect()) { |
| 381 | return true; |
| 382 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 383 | SkASSERT(this->isComplex()); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 384 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 385 | const RunType* scanline = fRunHead->findScanline(r.fTop); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 386 | for (;;) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 387 | if (!scanline_contains(scanline, r.fLeft, r.fRight)) { |
| 388 | return false; |
| 389 | } |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 390 | if (r.fBottom <= scanline_bottom(scanline)) { |
| 391 | break; |
| 392 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 393 | scanline = scanline_next(scanline); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 394 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 395 | return true; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 396 | } |
| 397 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 398 | bool SkRegion::contains(const SkRegion& rgn) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 399 | SkDEBUGCODE(this->validate();) |
| 400 | SkDEBUGCODE(rgn.validate();) |
| 401 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 402 | if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 403 | return false; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 404 | } |
| 405 | if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 406 | return true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 407 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 408 | if (rgn.isRect()) { |
| 409 | return this->contains(rgn.getBounds()); |
| 410 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 411 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 412 | /* |
| 413 | * A contains B is equivalent to |
| 414 | * B - A == 0 |
| 415 | */ |
| 416 | return !Oper(rgn, *this, kDifference_Op, NULL); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 417 | } |
| 418 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 419 | const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[], |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 420 | int* intervals) const { |
| 421 | SkASSERT(tmpStorage && intervals); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 422 | const RunType* runs = tmpStorage; |
| 423 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 424 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 425 | tmpStorage[0] = kRunTypeSentinel; |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 426 | *intervals = 0; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 427 | } else if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 428 | BuildRectRuns(fBounds, tmpStorage); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 429 | *intervals = 1; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 430 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 431 | runs = fRunHead->readonly_runs(); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 432 | *intervals = fRunHead->getIntervalCount(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 433 | } |
| 434 | return runs; |
| 435 | } |
| 436 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 437 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 438 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 439 | static bool scanline_intersects(const SkRegion::RunType runs[], |
| 440 | SkRegion::RunType L, SkRegion::RunType R) { |
| 441 | runs += 2; // skip Bottom and IntervalCount |
| 442 | for (;;) { |
| 443 | if (R <= runs[0]) { |
| 444 | break; |
| 445 | } |
| 446 | if (L < runs[1]) { |
| 447 | return true; |
| 448 | } |
| 449 | runs += 2; |
| 450 | } |
| 451 | return false; |
| 452 | } |
| 453 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 454 | bool SkRegion::intersects(const SkIRect& r) const { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 455 | SkDEBUGCODE(this->validate();) |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 456 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 457 | if (this->isEmpty() || r.isEmpty()) { |
| 458 | return false; |
| 459 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 460 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 461 | SkIRect sect; |
| 462 | if (!sect.intersect(fBounds, r)) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 463 | return false; |
| 464 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 465 | if (this->isRect()) { |
| 466 | return true; |
| 467 | } |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 468 | SkASSERT(this->isComplex()); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 469 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 470 | const RunType* scanline = fRunHead->findScanline(sect.fTop); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 471 | for (;;) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 472 | if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) { |
| 473 | return true; |
| 474 | } |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 475 | if (sect.fBottom <= scanline_bottom(scanline)) { |
| 476 | break; |
| 477 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 478 | scanline = scanline_next(scanline); |
reed@google.com | bb094b9 | 2012-11-07 14:23:42 +0000 | [diff] [blame] | 479 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 480 | return false; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 481 | } |
| 482 | |
| 483 | bool SkRegion::intersects(const SkRegion& rgn) const { |
| 484 | if (this->isEmpty() || rgn.isEmpty()) { |
| 485 | return false; |
| 486 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 487 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 488 | if (!SkIRect::Intersects(fBounds, rgn.fBounds)) { |
| 489 | return false; |
| 490 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 491 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 492 | bool weAreARect = this->isRect(); |
| 493 | bool theyAreARect = rgn.isRect(); |
| 494 | |
| 495 | if (weAreARect && theyAreARect) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 496 | return true; |
| 497 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 498 | if (weAreARect) { |
| 499 | return rgn.intersects(this->getBounds()); |
| 500 | } |
| 501 | if (theyAreARect) { |
| 502 | return this->intersects(rgn.getBounds()); |
| 503 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 504 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 505 | // both of us are complex |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 506 | return Oper(*this, rgn, kIntersect_Op, NULL); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 507 | } |
| 508 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 509 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 510 | |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 511 | bool SkRegion::operator==(const SkRegion& b) const { |
| 512 | SkDEBUGCODE(validate();) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 513 | SkDEBUGCODE(b.validate();) |
| 514 | |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 515 | if (this == &b) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 516 | return true; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 517 | } |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 518 | if (fBounds != b.fBounds) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 519 | return false; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 520 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 521 | |
reed@google.com | 6d428d3 | 2012-01-25 21:53:53 +0000 | [diff] [blame] | 522 | const SkRegion::RunHead* ah = fRunHead; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 523 | const SkRegion::RunHead* bh = b.fRunHead; |
| 524 | |
| 525 | // this catches empties and rects being equal |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 526 | if (ah == bh) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 527 | return true; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 528 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 529 | // now we insist that both are complex (but different ptrs) |
bungeman@google.com | b77b69f | 2013-01-24 16:38:23 +0000 | [diff] [blame] | 530 | if (!this->isComplex() || !b.isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 531 | return false; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 532 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 533 | return ah->fRunCount == bh->fRunCount && |
| 534 | !memcmp(ah->readonly_runs(), bh->readonly_runs(), |
| 535 | ah->fRunCount * sizeof(SkRegion::RunType)); |
| 536 | } |
| 537 | |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 538 | void SkRegion::translate(int dx, int dy, SkRegion* dst) const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 539 | SkDEBUGCODE(this->validate();) |
| 540 | |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 541 | if (NULL == dst) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 542 | return; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 543 | } |
| 544 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 545 | dst->setEmpty(); |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 546 | } else if (this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 547 | dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy, |
| 548 | fBounds.fRight + dx, fBounds.fBottom + dy); |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 549 | } else { |
| 550 | if (this == dst) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 551 | dst->fRunHead = dst->fRunHead->ensureWritable(); |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 552 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 553 | SkRegion tmp; |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 554 | tmp.allocateRuns(*fRunHead); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 555 | tmp.fBounds = fBounds; |
| 556 | dst->swap(tmp); |
| 557 | } |
| 558 | |
| 559 | dst->fBounds.offset(dx, dy); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 560 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 561 | const RunType* sruns = fRunHead->readonly_runs(); |
| 562 | RunType* druns = dst->fRunHead->writable_runs(); |
| 563 | |
| 564 | *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 565 | for (;;) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 566 | int bottom = *sruns++; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 567 | if (bottom == kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 568 | break; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 569 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 570 | *druns++ = (SkRegion::RunType)(bottom + dy); // bottom; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 571 | *druns++ = *sruns++; // copy intervalCount; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 572 | for (;;) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 573 | int x = *sruns++; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 574 | if (x == kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 575 | break; |
reed@google.com | 97fa34c | 2011-03-18 14:44:42 +0000 | [diff] [blame] | 576 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 577 | *druns++ = (SkRegion::RunType)(x + dx); |
| 578 | *druns++ = (SkRegion::RunType)(*sruns++ + dx); |
| 579 | } |
| 580 | *druns++ = kRunTypeSentinel; // x sentinel |
| 581 | } |
| 582 | *druns++ = kRunTypeSentinel; // y sentinel |
| 583 | |
| 584 | SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount); |
| 585 | SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount); |
| 586 | } |
| 587 | |
| 588 | SkDEBUGCODE(this->validate();) |
| 589 | } |
| 590 | |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 591 | /////////////////////////////////////////////////////////////////////////////// |
| 592 | |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 593 | bool SkRegion::setRects(const SkIRect rects[], int count) { |
| 594 | if (0 == count) { |
reed@android.com | cb34235 | 2010-07-22 18:27:53 +0000 | [diff] [blame] | 595 | this->setEmpty(); |
| 596 | } else { |
| 597 | this->setRect(rects[0]); |
| 598 | for (int i = 1; i < count; i++) { |
| 599 | this->op(rects[i], kUnion_Op); |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 600 | } |
| 601 | } |
reed@android.com | cb34235 | 2010-07-22 18:27:53 +0000 | [diff] [blame] | 602 | return !this->isEmpty(); |
reed@android.com | 097a351 | 2010-07-13 18:35:14 +0000 | [diff] [blame] | 603 | } |
| 604 | |
| 605 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 606 | |
| 607 | #if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized |
| 608 | #pragma warning ( push ) |
| 609 | #pragma warning ( disable : 4701 ) |
| 610 | #endif |
| 611 | |
| 612 | #ifdef SK_DEBUG |
| 613 | static void assert_valid_pair(int left, int rite) |
| 614 | { |
| 615 | SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite); |
| 616 | } |
| 617 | #else |
| 618 | #define assert_valid_pair(left, rite) |
| 619 | #endif |
| 620 | |
| 621 | struct spanRec { |
| 622 | const SkRegion::RunType* fA_runs; |
| 623 | const SkRegion::RunType* fB_runs; |
| 624 | int fA_left, fA_rite, fB_left, fB_rite; |
| 625 | int fLeft, fRite, fInside; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 626 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 627 | void init(const SkRegion::RunType a_runs[], |
| 628 | const SkRegion::RunType b_runs[]) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 629 | fA_left = *a_runs++; |
| 630 | fA_rite = *a_runs++; |
| 631 | fB_left = *b_runs++; |
| 632 | fB_rite = *b_runs++; |
| 633 | |
| 634 | fA_runs = a_runs; |
| 635 | fB_runs = b_runs; |
| 636 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 637 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 638 | bool done() const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 639 | SkASSERT(fA_left <= SkRegion::kRunTypeSentinel); |
| 640 | SkASSERT(fB_left <= SkRegion::kRunTypeSentinel); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 641 | return fA_left == SkRegion::kRunTypeSentinel && |
| 642 | fB_left == SkRegion::kRunTypeSentinel; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 643 | } |
| 644 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 645 | void next() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 646 | assert_valid_pair(fA_left, fA_rite); |
| 647 | assert_valid_pair(fB_left, fB_rite); |
| 648 | |
| 649 | int inside, left, rite SK_INIT_TO_AVOID_WARNING; |
| 650 | bool a_flush = false; |
| 651 | bool b_flush = false; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 652 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 653 | int a_left = fA_left; |
| 654 | int a_rite = fA_rite; |
| 655 | int b_left = fB_left; |
| 656 | int b_rite = fB_rite; |
| 657 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 658 | if (a_left < b_left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 659 | inside = 1; |
| 660 | left = a_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 661 | if (a_rite <= b_left) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 662 | rite = a_rite; |
| 663 | a_flush = true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 664 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 665 | rite = a_left = b_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 666 | } |
| 667 | } else if (b_left < a_left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 668 | inside = 2; |
| 669 | left = b_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 670 | if (b_rite <= a_left) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 671 | rite = b_rite; |
| 672 | b_flush = true; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 673 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 674 | rite = b_left = a_left; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 675 | } |
| 676 | } else { // a_left == b_left |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 677 | inside = 3; |
| 678 | left = a_left; // or b_left |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 679 | if (a_rite <= b_rite) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 680 | rite = b_left = a_rite; |
| 681 | a_flush = true; |
| 682 | } |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 683 | if (b_rite <= a_rite) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 684 | rite = a_left = b_rite; |
| 685 | b_flush = true; |
| 686 | } |
| 687 | } |
| 688 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 689 | if (a_flush) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 690 | a_left = *fA_runs++; |
| 691 | a_rite = *fA_runs++; |
| 692 | } |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 693 | if (b_flush) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 694 | b_left = *fB_runs++; |
| 695 | b_rite = *fB_runs++; |
| 696 | } |
| 697 | |
| 698 | SkASSERT(left <= rite); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 699 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 700 | // now update our state |
| 701 | fA_left = a_left; |
| 702 | fA_rite = a_rite; |
| 703 | fB_left = b_left; |
| 704 | fB_rite = b_rite; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 705 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 706 | fLeft = left; |
| 707 | fRite = rite; |
| 708 | fInside = inside; |
| 709 | } |
| 710 | }; |
| 711 | |
| 712 | static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[], |
| 713 | const SkRegion::RunType b_runs[], |
| 714 | SkRegion::RunType dst[], |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 715 | int min, int max) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 716 | spanRec rec; |
| 717 | bool firstInterval = true; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 718 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 719 | rec.init(a_runs, b_runs); |
| 720 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 721 | while (!rec.done()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 722 | rec.next(); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 723 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 724 | int left = rec.fLeft; |
| 725 | int rite = rec.fRite; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 726 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 727 | // add left,rite to our dst buffer (checking for coincidence |
| 728 | if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) && |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 729 | left < rite) { // skip if equal |
| 730 | if (firstInterval || dst[-1] < left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 731 | *dst++ = (SkRegion::RunType)(left); |
| 732 | *dst++ = (SkRegion::RunType)(rite); |
| 733 | firstInterval = false; |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 734 | } else { |
| 735 | // update the right edge |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 736 | dst[-1] = (SkRegion::RunType)(rite); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 737 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 738 | } |
| 739 | } |
| 740 | |
| 741 | *dst++ = SkRegion::kRunTypeSentinel; |
| 742 | return dst; |
| 743 | } |
| 744 | |
| 745 | #if defined _WIN32 && _MSC_VER >= 1300 |
| 746 | #pragma warning ( pop ) |
| 747 | #endif |
| 748 | |
| 749 | static const struct { |
| 750 | uint8_t fMin; |
| 751 | uint8_t fMax; |
| 752 | } gOpMinMax[] = { |
| 753 | { 1, 1 }, // Difference |
| 754 | { 3, 3 }, // Intersection |
| 755 | { 1, 3 }, // Union |
| 756 | { 1, 2 } // XOR |
| 757 | }; |
| 758 | |
| 759 | class RgnOper { |
| 760 | public: |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 761 | RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 762 | // need to ensure that the op enum lines up with our minmax array |
| 763 | SkASSERT(SkRegion::kDifference_Op == 0); |
| 764 | SkASSERT(SkRegion::kIntersect_Op == 1); |
| 765 | SkASSERT(SkRegion::kUnion_Op == 2); |
| 766 | SkASSERT(SkRegion::kXOR_Op == 3); |
| 767 | SkASSERT((unsigned)op <= 3); |
| 768 | |
| 769 | fStartDst = dst; |
| 770 | fPrevDst = dst + 1; |
| 771 | fPrevLen = 0; // will never match a length from operate_on_span |
| 772 | fTop = (SkRegion::RunType)(top); // just a first guess, we might update this |
| 773 | |
| 774 | fMin = gOpMinMax[op].fMin; |
| 775 | fMax = gOpMinMax[op].fMax; |
| 776 | } |
| 777 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 778 | void addSpan(int bottom, const SkRegion::RunType a_runs[], |
| 779 | const SkRegion::RunType b_runs[]) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 780 | // skip X values and slots for the next Y+intervalCount |
| 781 | SkRegion::RunType* start = fPrevDst + fPrevLen + 2; |
| 782 | // start points to beginning of dst interval |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 783 | SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax); |
| 784 | size_t len = stop - start; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 785 | SkASSERT(len >= 1 && (len & 1) == 1); |
| 786 | SkASSERT(SkRegion::kRunTypeSentinel == stop[-1]); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 787 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 788 | if (fPrevLen == len && |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 789 | (1 == len || !memcmp(fPrevDst, start, |
| 790 | (len - 1) * sizeof(SkRegion::RunType)))) { |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 791 | // update Y value |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 792 | fPrevDst[-2] = (SkRegion::RunType)(bottom); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 793 | } else { // accept the new span |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 794 | if (len == 1 && fPrevLen == 0) { |
| 795 | fTop = (SkRegion::RunType)(bottom); // just update our bottom |
| 796 | } else { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 797 | start[-2] = (SkRegion::RunType)(bottom); |
| 798 | start[-1] = len >> 1; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 799 | fPrevDst = start; |
| 800 | fPrevLen = len; |
| 801 | } |
| 802 | } |
| 803 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 804 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 805 | int flush() { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 806 | fStartDst[0] = fTop; |
| 807 | fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel; |
| 808 | return (int)(fPrevDst - fStartDst + fPrevLen + 1); |
| 809 | } |
| 810 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 811 | bool isEmpty() const { return 0 == fPrevLen; } |
| 812 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 813 | uint8_t fMin, fMax; |
| 814 | |
| 815 | private: |
| 816 | SkRegion::RunType* fStartDst; |
| 817 | SkRegion::RunType* fPrevDst; |
| 818 | size_t fPrevLen; |
| 819 | SkRegion::RunType fTop; |
| 820 | }; |
| 821 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 822 | // want a unique value to signal that we exited due to quickExit |
| 823 | #define QUICK_EXIT_TRUE_COUNT (-1) |
| 824 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 825 | static int operate(const SkRegion::RunType a_runs[], |
| 826 | const SkRegion::RunType b_runs[], |
| 827 | SkRegion::RunType dst[], |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 828 | SkRegion::Op op, |
| 829 | bool quickExit) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 830 | const SkRegion::RunType gEmptyScanline[] = { |
| 831 | 0, // dummy bottom value |
| 832 | 0, // zero intervals |
reed@google.com | 5f7c8a5 | 2012-05-03 16:17:38 +0000 | [diff] [blame] | 833 | SkRegion::kRunTypeSentinel, |
| 834 | // just need a 2nd value, since spanRec.init() reads 2 values, even |
| 835 | // though if the first value is the sentinel, it ignores the 2nd value. |
| 836 | // w/o the 2nd value here, we might read uninitialized memory. |
| 837 | // This happens when we are using gSentinel, which is pointing at |
| 838 | // our sentinel value. |
| 839 | 0 |
reed@android.com | fbb02e7 | 2010-04-13 14:52:52 +0000 | [diff] [blame] | 840 | }; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 841 | const SkRegion::RunType* const gSentinel = &gEmptyScanline[2]; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 842 | |
| 843 | int a_top = *a_runs++; |
| 844 | int a_bot = *a_runs++; |
| 845 | int b_top = *b_runs++; |
| 846 | int b_bot = *b_runs++; |
| 847 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 848 | a_runs += 1; // skip the intervalCount; |
| 849 | b_runs += 1; // skip the intervalCount; |
| 850 | |
| 851 | // Now a_runs and b_runs to their intervals (or sentinel) |
| 852 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 853 | assert_sentinel(a_top, false); |
| 854 | assert_sentinel(a_bot, false); |
| 855 | assert_sentinel(b_top, false); |
| 856 | assert_sentinel(b_bot, false); |
| 857 | |
| 858 | RgnOper oper(SkMin32(a_top, b_top), dst, op); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 859 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 860 | int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 861 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 862 | while (a_bot < SkRegion::kRunTypeSentinel || |
| 863 | b_bot < SkRegion::kRunTypeSentinel) { |
| 864 | int top, bot SK_INIT_TO_AVOID_WARNING; |
reed@android.com | fbb02e7 | 2010-04-13 14:52:52 +0000 | [diff] [blame] | 865 | const SkRegion::RunType* run0 = gSentinel; |
| 866 | const SkRegion::RunType* run1 = gSentinel; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 867 | bool a_flush = false; |
| 868 | bool b_flush = false; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 869 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 870 | if (a_top < b_top) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 871 | top = a_top; |
| 872 | run0 = a_runs; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 873 | if (a_bot <= b_top) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 874 | bot = a_bot; |
| 875 | a_flush = true; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 876 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 877 | bot = a_top = b_top; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 878 | } |
| 879 | } else if (b_top < a_top) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 880 | top = b_top; |
| 881 | run1 = b_runs; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 882 | if (b_bot <= a_top) { // [...] <...> |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 883 | bot = b_bot; |
| 884 | b_flush = true; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 885 | } else { // [...<..]...> or [...<...>...] |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 886 | bot = b_top = a_top; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 887 | } |
| 888 | } else { // a_top == b_top |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 889 | top = a_top; // or b_top |
| 890 | run0 = a_runs; |
| 891 | run1 = b_runs; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 892 | if (a_bot <= b_bot) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 893 | bot = b_top = a_bot; |
| 894 | a_flush = true; |
| 895 | } |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 896 | if (b_bot <= a_bot) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 897 | bot = a_top = b_bot; |
| 898 | b_flush = true; |
| 899 | } |
| 900 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 901 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 902 | if (top > prevBot) { |
reed@android.com | fbb02e7 | 2010-04-13 14:52:52 +0000 | [diff] [blame] | 903 | oper.addSpan(top, gSentinel, gSentinel); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 904 | } |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 905 | oper.addSpan(bot, run0, run1); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 906 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 907 | if (quickExit && !oper.isEmpty()) { |
| 908 | return QUICK_EXIT_TRUE_COUNT; |
| 909 | } |
| 910 | |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 911 | if (a_flush) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 912 | a_runs = skip_intervals(a_runs); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 913 | a_top = a_bot; |
| 914 | a_bot = *a_runs++; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 915 | a_runs += 1; // skip uninitialized intervalCount |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 916 | if (a_bot == SkRegion::kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 917 | a_top = a_bot; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 918 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 919 | } |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 920 | if (b_flush) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 921 | b_runs = skip_intervals(b_runs); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 922 | b_top = b_bot; |
| 923 | b_bot = *b_runs++; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 924 | b_runs += 1; // skip uninitialized intervalCount |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 925 | if (b_bot == SkRegion::kRunTypeSentinel) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 926 | b_top = b_bot; |
reed@google.com | 1deaab5 | 2011-10-06 13:11:46 +0000 | [diff] [blame] | 927 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 928 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 929 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 930 | prevBot = bot; |
| 931 | } |
| 932 | return oper.flush(); |
| 933 | } |
| 934 | |
| 935 | /////////////////////////////////////////////////////////////////////////////// |
| 936 | |
| 937 | /* Given count RunTypes in a complex region, return the worst case number of |
| 938 | logical intervals that represents (i.e. number of rects that would be |
| 939 | returned from the iterator). |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 940 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 941 | We could just return count/2, since there must be at least 2 values per |
| 942 | interval, but we can first trim off the const overhead of the initial TOP |
| 943 | value, plus the final BOTTOM + 2 sentinels. |
| 944 | */ |
caryclark@google.com | 803eceb | 2012-06-06 12:09:34 +0000 | [diff] [blame] | 945 | #if 0 // UNUSED |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 946 | static int count_to_intervals(int count) { |
| 947 | SkASSERT(count >= 6); // a single rect is 6 values |
| 948 | return (count - 4) >> 1; |
| 949 | } |
caryclark@google.com | 803eceb | 2012-06-06 12:09:34 +0000 | [diff] [blame] | 950 | #endif |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 951 | |
| 952 | /* Given a number of intervals, what is the worst case representation of that |
| 953 | many intervals? |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 954 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 955 | Worst case (from a storage perspective), is a vertical stack of single |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 956 | intervals: TOP + N * (BOTTOM INTERVALCOUNT LEFT RIGHT SENTINEL) + SENTINEL |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 957 | */ |
| 958 | static int intervals_to_count(int intervals) { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 959 | return 1 + intervals * 5 + 1; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 960 | } |
| 961 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 962 | /* Given the intervalCounts of RunTypes in two regions, return the worst-case number |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 963 | of RunTypes need to store the result after a region-op. |
| 964 | */ |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 965 | static int compute_worst_case_count(int a_intervals, int b_intervals) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 966 | // Our heuristic worst case is ai * (bi + 1) + bi * (ai + 1) |
| 967 | int intervals = 2 * a_intervals * b_intervals + a_intervals + b_intervals; |
| 968 | // convert back to number of RunType values |
| 969 | return intervals_to_count(intervals); |
| 970 | } |
| 971 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 972 | static bool setEmptyCheck(SkRegion* result) { |
| 973 | return result ? result->setEmpty() : false; |
| 974 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 975 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 976 | static bool setRectCheck(SkRegion* result, const SkIRect& rect) { |
| 977 | return result ? result->setRect(rect) : !rect.isEmpty(); |
| 978 | } |
| 979 | |
| 980 | static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) { |
| 981 | return result ? result->setRegion(rgn) : !rgn.isEmpty(); |
| 982 | } |
| 983 | |
| 984 | bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op, |
| 985 | SkRegion* result) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 986 | SkASSERT((unsigned)op < kOpCount); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 987 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 988 | if (kReplace_Op == op) { |
| 989 | return setRegionCheck(result, rgnbOrig); |
| 990 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 991 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 992 | // swith to using pointers, so we can swap them as needed |
| 993 | const SkRegion* rgna = &rgnaOrig; |
| 994 | const SkRegion* rgnb = &rgnbOrig; |
| 995 | // after this point, do not refer to rgnaOrig or rgnbOrig!!! |
| 996 | |
| 997 | // collaps difference and reverse-difference into just difference |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 998 | if (kReverseDifference_Op == op) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 999 | SkTSwap<const SkRegion*>(rgna, rgnb); |
| 1000 | op = kDifference_Op; |
| 1001 | } |
| 1002 | |
| 1003 | SkIRect bounds; |
| 1004 | bool a_empty = rgna->isEmpty(); |
| 1005 | bool b_empty = rgnb->isEmpty(); |
| 1006 | bool a_rect = rgna->isRect(); |
| 1007 | bool b_rect = rgnb->isRect(); |
| 1008 | |
| 1009 | switch (op) { |
| 1010 | case kDifference_Op: |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1011 | if (a_empty) { |
| 1012 | return setEmptyCheck(result); |
| 1013 | } |
reed@google.com | 0d10280 | 2012-05-31 18:28:59 +0000 | [diff] [blame] | 1014 | if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds, |
| 1015 | rgnb->fBounds)) { |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1016 | return setRegionCheck(result, *rgna); |
| 1017 | } |
reed@google.com | 0d10280 | 2012-05-31 18:28:59 +0000 | [diff] [blame] | 1018 | if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) { |
| 1019 | return setEmptyCheck(result); |
| 1020 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1021 | break; |
| 1022 | |
| 1023 | case kIntersect_Op: |
| 1024 | if ((a_empty | b_empty) |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1025 | || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) { |
| 1026 | return setEmptyCheck(result); |
| 1027 | } |
| 1028 | if (a_rect & b_rect) { |
| 1029 | return setRectCheck(result, bounds); |
| 1030 | } |
reed@google.com | 633c32b | 2013-01-31 15:24:24 +0000 | [diff] [blame] | 1031 | if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { |
| 1032 | return setRegionCheck(result, *rgnb); |
| 1033 | } |
| 1034 | if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { |
| 1035 | return setRegionCheck(result, *rgna); |
| 1036 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1037 | break; |
| 1038 | |
| 1039 | case kUnion_Op: |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1040 | if (a_empty) { |
| 1041 | return setRegionCheck(result, *rgnb); |
| 1042 | } |
| 1043 | if (b_empty) { |
| 1044 | return setRegionCheck(result, *rgna); |
| 1045 | } |
| 1046 | if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) { |
| 1047 | return setRegionCheck(result, *rgna); |
| 1048 | } |
| 1049 | if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) { |
| 1050 | return setRegionCheck(result, *rgnb); |
| 1051 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1052 | break; |
| 1053 | |
| 1054 | case kXOR_Op: |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1055 | if (a_empty) { |
| 1056 | return setRegionCheck(result, *rgnb); |
| 1057 | } |
| 1058 | if (b_empty) { |
| 1059 | return setRegionCheck(result, *rgna); |
| 1060 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1061 | break; |
| 1062 | default: |
tomhudson@google.com | 0c00f21 | 2011-12-28 14:59:50 +0000 | [diff] [blame] | 1063 | SkDEBUGFAIL("unknown region op"); |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1064 | return false; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1065 | } |
| 1066 | |
| 1067 | RunType tmpA[kRectRegionRuns]; |
| 1068 | RunType tmpB[kRectRegionRuns]; |
| 1069 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1070 | int a_intervals, b_intervals; |
| 1071 | const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals); |
| 1072 | const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1073 | |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1074 | int dstCount = compute_worst_case_count(a_intervals, b_intervals); |
| 1075 | SkAutoSTMalloc<256, RunType> array(dstCount); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1076 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1077 | #ifdef SK_DEBUG |
| 1078 | // Sometimes helpful to seed everything with a known value when debugging |
| 1079 | // sk_memset32((uint32_t*)array.get(), 0x7FFFFFFF, dstCount); |
| 1080 | #endif |
| 1081 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1082 | int count = operate(a_runs, b_runs, array.get(), op, NULL == result); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1083 | SkASSERT(count <= dstCount); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1084 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1085 | if (result) { |
| 1086 | SkASSERT(count >= 0); |
| 1087 | return result->setRuns(array.get(), count); |
| 1088 | } else { |
| 1089 | return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count); |
| 1090 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1091 | } |
| 1092 | |
reed@google.com | 7d4aee3 | 2012-04-30 13:29:02 +0000 | [diff] [blame] | 1093 | bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) { |
| 1094 | SkDEBUGCODE(this->validate();) |
| 1095 | return SkRegion::Oper(rgna, rgnb, op, this); |
| 1096 | } |
| 1097 | |
| 1098 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1099 | |
| 1100 | #include "SkBuffer.h" |
| 1101 | |
djsollen@google.com | 94e75ee | 2012-06-08 18:30:46 +0000 | [diff] [blame] | 1102 | uint32_t SkRegion::writeToMemory(void* storage) const { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1103 | if (NULL == storage) { |
| 1104 | uint32_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount |
| 1105 | if (!this->isEmpty()) { |
| 1106 | size += sizeof(fBounds); |
| 1107 | if (this->isComplex()) { |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1108 | size += 2 * sizeof(int32_t); // ySpanCount + intervalCount |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1109 | size += fRunHead->fRunCount * sizeof(RunType); |
| 1110 | } |
| 1111 | } |
| 1112 | return size; |
| 1113 | } |
| 1114 | |
| 1115 | SkWBuffer buffer(storage); |
| 1116 | |
| 1117 | if (this->isEmpty()) { |
| 1118 | buffer.write32(-1); |
| 1119 | } else { |
| 1120 | bool isRect = this->isRect(); |
| 1121 | |
| 1122 | buffer.write32(isRect ? 0 : fRunHead->fRunCount); |
| 1123 | buffer.write(&fBounds, sizeof(fBounds)); |
| 1124 | |
| 1125 | if (!isRect) { |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1126 | buffer.write32(fRunHead->getYSpanCount()); |
| 1127 | buffer.write32(fRunHead->getIntervalCount()); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1128 | buffer.write(fRunHead->readonly_runs(), |
| 1129 | fRunHead->fRunCount * sizeof(RunType)); |
| 1130 | } |
| 1131 | } |
| 1132 | return buffer.pos(); |
| 1133 | } |
| 1134 | |
djsollen@google.com | 94e75ee | 2012-06-08 18:30:46 +0000 | [diff] [blame] | 1135 | uint32_t SkRegion::readFromMemory(const void* storage) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1136 | SkRBuffer buffer(storage); |
| 1137 | SkRegion tmp; |
| 1138 | int32_t count; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1139 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1140 | count = buffer.readS32(); |
| 1141 | if (count >= 0) { |
| 1142 | buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)); |
| 1143 | if (count == 0) { |
| 1144 | tmp.fRunHead = SkRegion_gRectRunHeadPtr; |
| 1145 | } else { |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1146 | int32_t ySpanCount = buffer.readS32(); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1147 | int32_t intervalCount = buffer.readS32(); |
| 1148 | tmp.allocateRuns(count, ySpanCount, intervalCount); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1149 | buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType)); |
| 1150 | } |
| 1151 | } |
| 1152 | this->swap(tmp); |
| 1153 | return buffer.pos(); |
| 1154 | } |
| 1155 | |
reed@google.com | 0a0a236 | 2011-03-23 13:51:55 +0000 | [diff] [blame] | 1156 | /////////////////////////////////////////////////////////////////////////////// |
| 1157 | |
| 1158 | const SkRegion& SkRegion::GetEmptyRegion() { |
| 1159 | static SkRegion gEmpty; |
| 1160 | return gEmpty; |
| 1161 | } |
| 1162 | |
| 1163 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1164 | |
| 1165 | #ifdef SK_DEBUG |
| 1166 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1167 | // Starts with first X-interval, and returns a ptr to the X-sentinel |
| 1168 | static const SkRegion::RunType* skip_intervals_slow(const SkRegion::RunType runs[]) { |
| 1169 | // want to track that our intevals are all disjoint, such that |
| 1170 | // prev-right < next-left. We rely on this optimization in places such as |
| 1171 | // contains(). |
| 1172 | // |
| 1173 | SkRegion::RunType prevR = -SkRegion::kRunTypeSentinel; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1174 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1175 | while (runs[0] < SkRegion::kRunTypeSentinel) { |
| 1176 | SkASSERT(prevR < runs[0]); |
| 1177 | SkASSERT(runs[0] < runs[1]); |
| 1178 | SkASSERT(runs[1] < SkRegion::kRunTypeSentinel); |
| 1179 | prevR = runs[1]; |
| 1180 | runs += 2; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1181 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1182 | return runs; |
| 1183 | } |
| 1184 | |
sugoi@google.com | e0e385c | 2013-03-11 18:50:03 +0000 | [diff] [blame] | 1185 | static void compute_bounds(const SkRegion::RunType runs[], |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1186 | SkIRect* bounds, int* ySpanCountPtr, |
| 1187 | int* intervalCountPtr) { |
| 1188 | assert_sentinel(runs[0], false); // top |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1189 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1190 | int left = SK_MaxS32; |
| 1191 | int rite = SK_MinS32; |
| 1192 | int bot; |
| 1193 | int ySpanCount = 0; |
| 1194 | int intervalCount = 0; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1195 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1196 | bounds->fTop = *runs++; |
| 1197 | do { |
| 1198 | bot = *runs++; |
| 1199 | SkASSERT(SkRegion::kRunTypeSentinel > bot); |
| 1200 | |
| 1201 | ySpanCount += 1; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1202 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1203 | runs += 1; // skip intervalCount for now |
| 1204 | if (*runs < SkRegion::kRunTypeSentinel) { |
| 1205 | if (left > *runs) { |
| 1206 | left = *runs; |
| 1207 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1208 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1209 | const SkRegion::RunType* prev = runs; |
| 1210 | runs = skip_intervals_slow(runs); |
| 1211 | int intervals = (runs - prev) >> 1; |
| 1212 | SkASSERT(prev[-1] == intervals); |
| 1213 | intervalCount += intervals; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1214 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1215 | if (rite < runs[-1]) { |
| 1216 | rite = runs[-1]; |
| 1217 | } |
| 1218 | } else { |
| 1219 | SkASSERT(0 == runs[-1]); // no intervals |
| 1220 | } |
| 1221 | SkASSERT(SkRegion::kRunTypeSentinel == *runs); |
| 1222 | runs += 1; |
| 1223 | } while (SkRegion::kRunTypeSentinel != *runs); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1224 | |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1225 | bounds->fLeft = left; |
| 1226 | bounds->fRight = rite; |
| 1227 | bounds->fBottom = bot; |
| 1228 | *ySpanCountPtr = ySpanCount; |
| 1229 | *intervalCountPtr = intervalCount; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1230 | } |
| 1231 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1232 | void SkRegion::validate() const { |
| 1233 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1234 | // check for explicit empty (the zero rect), so we can compare rects to know when |
| 1235 | // two regions are equal (i.e. emptyRectA == emptyRectB) |
| 1236 | // this is stricter than just asserting fBounds.isEmpty() |
| 1237 | SkASSERT(fBounds.fLeft == 0 && fBounds.fTop == 0 && fBounds.fRight == 0 && fBounds.fBottom == 0); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1238 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1239 | SkASSERT(!fBounds.isEmpty()); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1240 | if (!this->isRect()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1241 | SkASSERT(fRunHead->fRefCnt >= 1); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1242 | SkASSERT(fRunHead->fRunCount > kRectRegionRuns); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1243 | |
| 1244 | const RunType* run = fRunHead->readonly_runs(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1245 | |
| 1246 | // check that our bounds match our runs |
| 1247 | { |
| 1248 | SkIRect bounds; |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1249 | int ySpanCount, intervalCount; |
sugoi@google.com | e0e385c | 2013-03-11 18:50:03 +0000 | [diff] [blame] | 1250 | compute_bounds(run, &bounds, &ySpanCount, &intervalCount); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1251 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1252 | SkASSERT(bounds == fBounds); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1253 | SkASSERT(ySpanCount > 0); |
| 1254 | SkASSERT(fRunHead->getYSpanCount() == ySpanCount); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1255 | // SkASSERT(intervalCount > 1); |
reed@google.com | af7e694 | 2012-05-01 14:43:22 +0000 | [diff] [blame] | 1256 | SkASSERT(fRunHead->getIntervalCount() == intervalCount); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1257 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1258 | } |
| 1259 | } |
| 1260 | } |
| 1261 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1262 | void SkRegion::dump() const { |
| 1263 | if (this->isEmpty()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1264 | SkDebugf(" rgn: empty\n"); |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1265 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1266 | SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1267 | if (this->isComplex()) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1268 | const RunType* runs = fRunHead->readonly_runs(); |
| 1269 | for (int i = 0; i < fRunHead->fRunCount; i++) |
| 1270 | SkDebugf(" %d", runs[i]); |
| 1271 | } |
| 1272 | SkDebugf("\n"); |
| 1273 | } |
| 1274 | } |
| 1275 | |
| 1276 | #endif |
| 1277 | |
reed@google.com | c34f53d | 2012-04-30 15:10:13 +0000 | [diff] [blame] | 1278 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1279 | |
| 1280 | SkRegion::Iterator::Iterator(const SkRegion& rgn) { |
| 1281 | this->reset(rgn); |
| 1282 | } |
| 1283 | |
| 1284 | bool SkRegion::Iterator::rewind() { |
| 1285 | if (fRgn) { |
| 1286 | this->reset(*fRgn); |
| 1287 | return true; |
| 1288 | } |
| 1289 | return false; |
| 1290 | } |
| 1291 | |
| 1292 | void SkRegion::Iterator::reset(const SkRegion& rgn) { |
| 1293 | fRgn = &rgn; |
| 1294 | if (rgn.isEmpty()) { |
| 1295 | fDone = true; |
| 1296 | } else { |
| 1297 | fDone = false; |
| 1298 | if (rgn.isRect()) { |
| 1299 | fRect = rgn.fBounds; |
| 1300 | fRuns = NULL; |
| 1301 | } else { |
| 1302 | fRuns = rgn.fRunHead->readonly_runs(); |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1303 | fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]); |
| 1304 | fRuns += 5; |
| 1305 | // Now fRuns points to the 2nd interval (or x-sentinel) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1306 | } |
| 1307 | } |
| 1308 | } |
| 1309 | |
| 1310 | void SkRegion::Iterator::next() { |
| 1311 | if (fDone) { |
| 1312 | return; |
| 1313 | } |
| 1314 | |
| 1315 | if (fRuns == NULL) { // rect case |
| 1316 | fDone = true; |
| 1317 | return; |
| 1318 | } |
| 1319 | |
| 1320 | const RunType* runs = fRuns; |
| 1321 | |
| 1322 | if (runs[0] < kRunTypeSentinel) { // valid X value |
| 1323 | fRect.fLeft = runs[0]; |
| 1324 | fRect.fRight = runs[1]; |
| 1325 | runs += 2; |
| 1326 | } else { // we're at the end of a line |
| 1327 | runs += 1; |
| 1328 | if (runs[0] < kRunTypeSentinel) { // valid Y value |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1329 | int intervals = runs[1]; |
| 1330 | if (0 == intervals) { // empty line |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1331 | fRect.fTop = runs[0]; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1332 | runs += 3; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1333 | } else { |
| 1334 | fRect.fTop = fRect.fBottom; |
| 1335 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1336 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1337 | fRect.fBottom = runs[0]; |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1338 | assert_sentinel(runs[2], false); |
| 1339 | assert_sentinel(runs[3], false); |
| 1340 | fRect.fLeft = runs[2]; |
| 1341 | fRect.fRight = runs[3]; |
| 1342 | runs += 4; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1343 | } else { // end of rgn |
| 1344 | fDone = true; |
| 1345 | } |
| 1346 | } |
| 1347 | fRuns = runs; |
| 1348 | } |
| 1349 | |
| 1350 | SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip) |
| 1351 | : fIter(rgn), fClip(clip), fDone(true) { |
| 1352 | const SkIRect& r = fIter.rect(); |
| 1353 | |
| 1354 | while (!fIter.done()) { |
| 1355 | if (r.fTop >= clip.fBottom) { |
| 1356 | break; |
| 1357 | } |
| 1358 | if (fRect.intersect(clip, r)) { |
| 1359 | fDone = false; |
| 1360 | break; |
| 1361 | } |
| 1362 | fIter.next(); |
| 1363 | } |
| 1364 | } |
| 1365 | |
| 1366 | void SkRegion::Cliperator::next() { |
| 1367 | if (fDone) { |
| 1368 | return; |
| 1369 | } |
| 1370 | |
| 1371 | const SkIRect& r = fIter.rect(); |
| 1372 | |
| 1373 | fDone = true; |
| 1374 | fIter.next(); |
| 1375 | while (!fIter.done()) { |
| 1376 | if (r.fTop >= fClip.fBottom) { |
| 1377 | break; |
| 1378 | } |
| 1379 | if (fRect.intersect(fClip, r)) { |
| 1380 | fDone = false; |
| 1381 | break; |
| 1382 | } |
| 1383 | fIter.next(); |
| 1384 | } |
| 1385 | } |
| 1386 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1387 | /////////////////////////////////////////////////////////////////////////////// |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1388 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1389 | SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left, |
| 1390 | int right) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1391 | SkDEBUGCODE(rgn.validate();) |
| 1392 | |
| 1393 | const SkIRect& r = rgn.getBounds(); |
| 1394 | |
| 1395 | fDone = true; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1396 | if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom && |
| 1397 | right > r.fLeft && left < r.fRight) { |
| 1398 | if (rgn.isRect()) { |
| 1399 | if (left < r.fLeft) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1400 | left = r.fLeft; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1401 | } |
| 1402 | if (right > r.fRight) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1403 | right = r.fRight; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1404 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1405 | fLeft = left; |
| 1406 | fRight = right; |
| 1407 | fRuns = NULL; // means we're a rect, not a rgn |
| 1408 | fDone = false; |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1409 | } else { |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1410 | const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y); |
| 1411 | runs += 2; // skip Bottom and IntervalCount |
| 1412 | for (;;) { |
| 1413 | // runs[0..1] is to the right of the span, so we're done |
| 1414 | if (runs[0] >= right) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1415 | break; |
| 1416 | } |
reed@google.com | 9c36a76 | 2012-05-02 18:07:33 +0000 | [diff] [blame] | 1417 | // runs[0..1] is to the left of the span, so continue |
| 1418 | if (runs[1] <= left) { |
| 1419 | runs += 2; |
| 1420 | continue; |
| 1421 | } |
| 1422 | // runs[0..1] intersects the span |
| 1423 | fRuns = runs; |
| 1424 | fLeft = left; |
| 1425 | fRight = right; |
| 1426 | fDone = false; |
| 1427 | break; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1428 | } |
| 1429 | } |
| 1430 | } |
| 1431 | } |
| 1432 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1433 | bool SkRegion::Spanerator::next(int* left, int* right) { |
| 1434 | if (fDone) { |
| 1435 | return false; |
| 1436 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1437 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1438 | if (fRuns == NULL) { // we're a rect |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1439 | fDone = true; // ok, now we're done |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1440 | if (left) { |
| 1441 | *left = fLeft; |
| 1442 | } |
| 1443 | if (right) { |
| 1444 | *right = fRight; |
| 1445 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1446 | return true; // this interval is legal |
| 1447 | } |
| 1448 | |
| 1449 | const SkRegion::RunType* runs = fRuns; |
| 1450 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1451 | if (runs[0] >= fRight) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1452 | fDone = true; |
| 1453 | return false; |
| 1454 | } |
| 1455 | |
| 1456 | SkASSERT(runs[1] > fLeft); |
| 1457 | |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1458 | if (left) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1459 | *left = SkMax32(fLeft, runs[0]); |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1460 | } |
| 1461 | if (right) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1462 | *right = SkMin32(fRight, runs[1]); |
reed@google.com | e72766f | 2011-01-07 15:00:44 +0000 | [diff] [blame] | 1463 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1464 | fRuns = runs + 2; |
| 1465 | return true; |
| 1466 | } |
| 1467 | |
| 1468 | /////////////////////////////////////////////////////////////////////////////// |
| 1469 | |
| 1470 | #ifdef SK_DEBUG |
| 1471 | |
| 1472 | bool SkRegion::debugSetRuns(const RunType runs[], int count) { |
| 1473 | // we need to make a copy, since the real method may modify the array, and |
| 1474 | // so it cannot be const. |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 1475 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1476 | SkAutoTArray<RunType> storage(count); |
| 1477 | memcpy(storage.get(), runs, count * sizeof(RunType)); |
| 1478 | return this->setRuns(storage.get(), count); |
| 1479 | } |
| 1480 | |
| 1481 | #endif |