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