Region.cpp revision 4c0a170585d5c8a1f3508ac55f799ebaf86e91db
1/* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#define LOG_TAG "Region" 18 19#include <limits.h> 20 21#include <utils/Log.h> 22#include <utils/String8.h> 23 24#include <ui/Rect.h> 25#include <ui/Region.h> 26#include <ui/Point.h> 27 28#include <private/ui/RegionHelper.h> 29 30// ---------------------------------------------------------------------------- 31#define VALIDATE_REGIONS (false) 32#define VALIDATE_WITH_CORECG (false) 33// ---------------------------------------------------------------------------- 34 35#if VALIDATE_WITH_CORECG 36#include <core/SkRegion.h> 37#endif 38 39namespace android { 40// ---------------------------------------------------------------------------- 41 42enum { 43 op_nand = region_operator<Rect>::op_nand, 44 op_and = region_operator<Rect>::op_and, 45 op_or = region_operator<Rect>::op_or, 46 op_xor = region_operator<Rect>::op_xor 47}; 48 49// ---------------------------------------------------------------------------- 50 51Region::Region() 52 : mBounds(0,0) 53{ 54} 55 56Region::Region(const Region& rhs) 57 : mBounds(rhs.mBounds), mStorage(rhs.mStorage) 58{ 59#if VALIDATE_REGIONS 60 validate(rhs, "rhs copy-ctor"); 61#endif 62} 63 64Region::Region(const Rect& rhs) 65 : mBounds(rhs) 66{ 67} 68 69Region::~Region() 70{ 71} 72 73Region& Region::operator = (const Region& rhs) 74{ 75#if VALIDATE_REGIONS 76 validate(*this, "this->operator="); 77 validate(rhs, "rhs.operator="); 78#endif 79 mBounds = rhs.mBounds; 80 mStorage = rhs.mStorage; 81 return *this; 82} 83 84Region& Region::makeBoundsSelf() 85{ 86 mStorage.clear(); 87 return *this; 88} 89 90void Region::clear() 91{ 92 mBounds.clear(); 93 mStorage.clear(); 94} 95 96void Region::set(const Rect& r) 97{ 98 mBounds = r; 99 mStorage.clear(); 100} 101 102void Region::set(uint32_t w, uint32_t h) 103{ 104 mBounds = Rect(int(w), int(h)); 105 mStorage.clear(); 106} 107 108// ---------------------------------------------------------------------------- 109 110void Region::addRectUnchecked(int l, int t, int r, int b) 111{ 112 mStorage.add(Rect(l,t,r,b)); 113#if VALIDATE_REGIONS 114 validate(*this, "addRectUnchecked"); 115#endif 116} 117 118// ---------------------------------------------------------------------------- 119 120Region& Region::orSelf(const Rect& r) { 121 return operationSelf(r, op_or); 122} 123Region& Region::xorSelf(const Rect& r) { 124 return operationSelf(r, op_xor); 125} 126Region& Region::andSelf(const Rect& r) { 127 return operationSelf(r, op_and); 128} 129Region& Region::subtractSelf(const Rect& r) { 130 return operationSelf(r, op_nand); 131} 132Region& Region::operationSelf(const Rect& r, int op) { 133 Region lhs(*this); 134 boolean_operation(op, *this, lhs, r); 135 return *this; 136} 137 138// ---------------------------------------------------------------------------- 139 140Region& Region::orSelf(const Region& rhs) { 141 return operationSelf(rhs, op_or); 142} 143Region& Region::xorSelf(const Region& rhs) { 144 return operationSelf(rhs, op_xor); 145} 146Region& Region::andSelf(const Region& rhs) { 147 return operationSelf(rhs, op_and); 148} 149Region& Region::subtractSelf(const Region& rhs) { 150 return operationSelf(rhs, op_nand); 151} 152Region& Region::operationSelf(const Region& rhs, int op) { 153 Region lhs(*this); 154 boolean_operation(op, *this, lhs, rhs); 155 return *this; 156} 157 158Region& Region::translateSelf(int x, int y) { 159 if (x|y) translate(*this, x, y); 160 return *this; 161} 162 163// ---------------------------------------------------------------------------- 164 165const Region Region::merge(const Rect& rhs) const { 166 return operation(rhs, op_or); 167} 168const Region Region::mergeExclusive(const Rect& rhs) const { 169 return operation(rhs, op_xor); 170} 171const Region Region::intersect(const Rect& rhs) const { 172 return operation(rhs, op_and); 173} 174const Region Region::subtract(const Rect& rhs) const { 175 return operation(rhs, op_nand); 176} 177const Region Region::operation(const Rect& rhs, int op) const { 178 Region result; 179 boolean_operation(op, result, *this, rhs); 180 return result; 181} 182 183// ---------------------------------------------------------------------------- 184 185const Region Region::merge(const Region& rhs) const { 186 return operation(rhs, op_or); 187} 188const Region Region::mergeExclusive(const Region& rhs) const { 189 return operation(rhs, op_xor); 190} 191const Region Region::intersect(const Region& rhs) const { 192 return operation(rhs, op_and); 193} 194const Region Region::subtract(const Region& rhs) const { 195 return operation(rhs, op_nand); 196} 197const Region Region::operation(const Region& rhs, int op) const { 198 Region result; 199 boolean_operation(op, result, *this, rhs); 200 return result; 201} 202 203const Region Region::translate(int x, int y) const { 204 Region result; 205 translate(result, *this, x, y); 206 return result; 207} 208 209// ---------------------------------------------------------------------------- 210 211Region& Region::orSelf(const Region& rhs, int dx, int dy) { 212 return operationSelf(rhs, dx, dy, op_or); 213} 214Region& Region::xorSelf(const Region& rhs, int dx, int dy) { 215 return operationSelf(rhs, dx, dy, op_xor); 216} 217Region& Region::andSelf(const Region& rhs, int dx, int dy) { 218 return operationSelf(rhs, dx, dy, op_and); 219} 220Region& Region::subtractSelf(const Region& rhs, int dx, int dy) { 221 return operationSelf(rhs, dx, dy, op_nand); 222} 223Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) { 224 Region lhs(*this); 225 boolean_operation(op, *this, lhs, rhs, dx, dy); 226 return *this; 227} 228 229// ---------------------------------------------------------------------------- 230 231const Region Region::merge(const Region& rhs, int dx, int dy) const { 232 return operation(rhs, dx, dy, op_or); 233} 234const Region Region::mergeExclusive(const Region& rhs, int dx, int dy) const { 235 return operation(rhs, dx, dy, op_xor); 236} 237const Region Region::intersect(const Region& rhs, int dx, int dy) const { 238 return operation(rhs, dx, dy, op_and); 239} 240const Region Region::subtract(const Region& rhs, int dx, int dy) const { 241 return operation(rhs, dx, dy, op_nand); 242} 243const Region Region::operation(const Region& rhs, int dx, int dy, int op) const { 244 Region result; 245 boolean_operation(op, result, *this, rhs, dx, dy); 246 return result; 247} 248 249// ---------------------------------------------------------------------------- 250 251// This is our region rasterizer, which merges rects and spans together 252// to obtain an optimal region. 253class Region::rasterizer : public region_operator<Rect>::region_rasterizer 254{ 255 Rect& bounds; 256 Vector<Rect>& storage; 257 Rect* head; 258 Rect* tail; 259 Vector<Rect> span; 260 Rect* cur; 261public: 262 rasterizer(Region& reg) 263 : bounds(reg.mBounds), storage(reg.mStorage), head(), tail(), cur() { 264 bounds.top = bounds.bottom = 0; 265 bounds.left = INT_MAX; 266 bounds.right = INT_MIN; 267 storage.clear(); 268 } 269 270 ~rasterizer() { 271 if (span.size()) { 272 flushSpan(); 273 } 274 if (storage.size()) { 275 bounds.top = storage.itemAt(0).top; 276 bounds.bottom = storage.top().bottom; 277 if (storage.size() == 1) { 278 storage.clear(); 279 } 280 } else { 281 bounds.left = 0; 282 bounds.right = 0; 283 } 284 } 285 286 virtual void operator()(const Rect& rect) { 287 //ALOGD(">>> %3d, %3d, %3d, %3d", 288 // rect.left, rect.top, rect.right, rect.bottom); 289 if (span.size()) { 290 if (cur->top != rect.top) { 291 flushSpan(); 292 } else if (cur->right == rect.left) { 293 cur->right = rect.right; 294 return; 295 } 296 } 297 span.add(rect); 298 cur = span.editArray() + (span.size() - 1); 299 } 300private: 301 template<typename T> 302 static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; } 303 template<typename T> 304 static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; } 305 void flushSpan() { 306 bool merge = false; 307 if (tail-head == ssize_t(span.size())) { 308 Rect const* p = span.editArray(); 309 Rect const* q = head; 310 if (p->top == q->bottom) { 311 merge = true; 312 while (q != tail) { 313 if ((p->left != q->left) || (p->right != q->right)) { 314 merge = false; 315 break; 316 } 317 p++, q++; 318 } 319 } 320 } 321 if (merge) { 322 const int bottom = span[0].bottom; 323 Rect* r = head; 324 while (r != tail) { 325 r->bottom = bottom; 326 r++; 327 } 328 } else { 329 bounds.left = min(span.itemAt(0).left, bounds.left); 330 bounds.right = max(span.top().right, bounds.right); 331 storage.appendVector(span); 332 tail = storage.editArray() + storage.size(); 333 head = tail - span.size(); 334 } 335 span.clear(); 336 } 337}; 338 339bool Region::validate(const Region& reg, const char* name) 340{ 341 bool result = true; 342 const_iterator cur = reg.begin(); 343 const_iterator const tail = reg.end(); 344 const_iterator prev = cur++; 345 Rect b(*prev); 346 while (cur != tail) { 347 b.left = b.left < cur->left ? b.left : cur->left; 348 b.top = b.top < cur->top ? b.top : cur->top; 349 b.right = b.right > cur->right ? b.right : cur->right; 350 b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom; 351 if (cur->top == prev->top) { 352 if (cur->bottom != prev->bottom) { 353 ALOGE("%s: invalid span %p", name, cur); 354 result = false; 355 } else if (cur->left < prev->right) { 356 ALOGE("%s: spans overlap horizontally prev=%p, cur=%p", 357 name, prev, cur); 358 result = false; 359 } 360 } else if (cur->top < prev->bottom) { 361 ALOGE("%s: spans overlap vertically prev=%p, cur=%p", 362 name, prev, cur); 363 result = false; 364 } 365 prev = cur; 366 cur++; 367 } 368 if (b != reg.getBounds()) { 369 result = false; 370 ALOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name, 371 b.left, b.top, b.right, b.bottom, 372 reg.getBounds().left, reg.getBounds().top, 373 reg.getBounds().right, reg.getBounds().bottom); 374 } 375 if (result == false) { 376 reg.dump(name); 377 } 378 return result; 379} 380 381void Region::boolean_operation(int op, Region& dst, 382 const Region& lhs, 383 const Region& rhs, int dx, int dy) 384{ 385#if VALIDATE_REGIONS 386 validate(lhs, "boolean_operation (before): lhs"); 387 validate(rhs, "boolean_operation (before): rhs"); 388 validate(dst, "boolean_operation (before): dst"); 389#endif 390 391 size_t lhs_count; 392 Rect const * const lhs_rects = lhs.getArray(&lhs_count); 393 394 size_t rhs_count; 395 Rect const * const rhs_rects = rhs.getArray(&rhs_count); 396 397 region_operator<Rect>::region lhs_region(lhs_rects, lhs_count); 398 region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy); 399 region_operator<Rect> operation(op, lhs_region, rhs_region); 400 { // scope for rasterizer (dtor has side effects) 401 rasterizer r(dst); 402 operation(r); 403 } 404 405#if VALIDATE_REGIONS 406 validate(lhs, "boolean_operation: lhs"); 407 validate(rhs, "boolean_operation: rhs"); 408 validate(dst, "boolean_operation: dst"); 409#endif 410 411#if VALIDATE_WITH_CORECG 412 SkRegion sk_lhs; 413 SkRegion sk_rhs; 414 SkRegion sk_dst; 415 416 for (size_t i=0 ; i<lhs_count ; i++) 417 sk_lhs.op( 418 lhs_rects[i].left + dx, 419 lhs_rects[i].top + dy, 420 lhs_rects[i].right + dx, 421 lhs_rects[i].bottom + dy, 422 SkRegion::kUnion_Op); 423 424 for (size_t i=0 ; i<rhs_count ; i++) 425 sk_rhs.op( 426 rhs_rects[i].left + dx, 427 rhs_rects[i].top + dy, 428 rhs_rects[i].right + dx, 429 rhs_rects[i].bottom + dy, 430 SkRegion::kUnion_Op); 431 432 const char* name = "---"; 433 SkRegion::Op sk_op; 434 switch (op) { 435 case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break; 436 case op_xor: sk_op = SkRegion::kUnion_XOR; name="XOR"; break; 437 case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break; 438 case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break; 439 } 440 sk_dst.op(sk_lhs, sk_rhs, sk_op); 441 442 if (sk_dst.isEmpty() && dst.isEmpty()) 443 return; 444 445 bool same = true; 446 Region::const_iterator head = dst.begin(); 447 Region::const_iterator const tail = dst.end(); 448 SkRegion::Iterator it(sk_dst); 449 while (!it.done()) { 450 if (head != tail) { 451 if ( 452 head->left != it.rect().fLeft || 453 head->top != it.rect().fTop || 454 head->right != it.rect().fRight || 455 head->bottom != it.rect().fBottom 456 ) { 457 same = false; 458 break; 459 } 460 } else { 461 same = false; 462 break; 463 } 464 head++; 465 it.next(); 466 } 467 468 if (head != tail) { 469 same = false; 470 } 471 472 if(!same) { 473 ALOGD("---\nregion boolean %s failed", name); 474 lhs.dump("lhs"); 475 rhs.dump("rhs"); 476 dst.dump("dst"); 477 ALOGD("should be"); 478 SkRegion::Iterator it(sk_dst); 479 while (!it.done()) { 480 ALOGD(" [%3d, %3d, %3d, %3d]", 481 it.rect().fLeft, 482 it.rect().fTop, 483 it.rect().fRight, 484 it.rect().fBottom); 485 it.next(); 486 } 487 } 488#endif 489} 490 491void Region::boolean_operation(int op, Region& dst, 492 const Region& lhs, 493 const Rect& rhs, int dx, int dy) 494{ 495 if (!rhs.isValid()) { 496 ALOGE("Region::boolean_operation(op=%d) invalid Rect={%d,%d,%d,%d}", 497 op, rhs.left, rhs.top, rhs.right, rhs.bottom); 498 return; 499 } 500 501#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS 502 boolean_operation(op, dst, lhs, Region(rhs), dx, dy); 503#else 504 size_t lhs_count; 505 Rect const * const lhs_rects = lhs.getArray(&lhs_count); 506 507 region_operator<Rect>::region lhs_region(lhs_rects, lhs_count); 508 region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy); 509 region_operator<Rect> operation(op, lhs_region, rhs_region); 510 { // scope for rasterizer (dtor has side effects) 511 rasterizer r(dst); 512 operation(r); 513 } 514 515#endif 516} 517 518void Region::boolean_operation(int op, Region& dst, 519 const Region& lhs, const Region& rhs) 520{ 521 boolean_operation(op, dst, lhs, rhs, 0, 0); 522} 523 524void Region::boolean_operation(int op, Region& dst, 525 const Region& lhs, const Rect& rhs) 526{ 527 boolean_operation(op, dst, lhs, rhs, 0, 0); 528} 529 530void Region::translate(Region& reg, int dx, int dy) 531{ 532 if ((dx || dy) && !reg.isEmpty()) { 533#if VALIDATE_REGIONS 534 validate(reg, "translate (before)"); 535#endif 536 reg.mBounds.translate(dx, dy); 537 size_t count = reg.mStorage.size(); 538 Rect* rects = reg.mStorage.editArray(); 539 while (count) { 540 rects->translate(dx, dy); 541 rects++; 542 count--; 543 } 544#if VALIDATE_REGIONS 545 validate(reg, "translate (after)"); 546#endif 547 } 548} 549 550void Region::translate(Region& dst, const Region& reg, int dx, int dy) 551{ 552 dst = reg; 553 translate(dst, dx, dy); 554} 555 556// ---------------------------------------------------------------------------- 557 558size_t Region::getSize() const { 559 return (mStorage.size() + 1) * sizeof(Rect); 560} 561 562status_t Region::flatten(void* buffer) const { 563 Rect* rects = reinterpret_cast<Rect*>(buffer); 564 *rects++ = mBounds; 565 memcpy(rects, mStorage.array(), mStorage.size() * sizeof(Rect)); 566 return NO_ERROR; 567} 568 569status_t Region::unflatten(void const* buffer, size_t size) { 570 mStorage.clear(); 571 if (size >= sizeof(Rect)) { 572 Rect const* rects = reinterpret_cast<Rect const*>(buffer); 573 mBounds = *rects++; 574 size -= sizeof(Rect); 575 size_t count = size / sizeof(Rect); 576 if (count > 0) { 577 ssize_t err = mStorage.insertAt(0, count); 578 if (err < 0) { 579 return status_t(err); 580 } 581 memcpy(mStorage.editArray(), rects, count*sizeof(Rect)); 582 } 583 } 584 return NO_ERROR; 585} 586 587// ---------------------------------------------------------------------------- 588 589Region::const_iterator Region::begin() const { 590 return isRect() ? &mBounds : mStorage.array(); 591} 592 593Region::const_iterator Region::end() const { 594 if (isRect()) { 595 if (isEmpty()) { 596 return &mBounds; 597 } else { 598 return &mBounds + 1; 599 } 600 } else { 601 return mStorage.array() + mStorage.size(); 602 } 603} 604 605Rect const* Region::getArray(size_t* count) const { 606 const_iterator const b(begin()); 607 const_iterator const e(end()); 608 if (count) *count = e-b; 609 return b; 610} 611 612size_t Region::getRects(Vector<Rect>& rectList) const 613{ 614 rectList = mStorage; 615 if (rectList.isEmpty()) { 616 rectList.clear(); 617 rectList.add(mBounds); 618 } 619 return rectList.size(); 620} 621 622// ---------------------------------------------------------------------------- 623 624void Region::dump(String8& out, const char* what, uint32_t flags) const 625{ 626 (void)flags; 627 const_iterator head = begin(); 628 const_iterator const tail = end(); 629 630 size_t SIZE = 256; 631 char buffer[SIZE]; 632 633 snprintf(buffer, SIZE, " Region %s (this=%p, count=%d)\n", 634 what, this, tail-head); 635 out.append(buffer); 636 while (head != tail) { 637 snprintf(buffer, SIZE, " [%3d, %3d, %3d, %3d]\n", 638 head->left, head->top, head->right, head->bottom); 639 out.append(buffer); 640 head++; 641 } 642} 643 644void Region::dump(const char* what, uint32_t flags) const 645{ 646 (void)flags; 647 const_iterator head = begin(); 648 const_iterator const tail = end(); 649 ALOGD(" Region %s (this=%p, count=%d)\n", what, this, tail-head); 650 while (head != tail) { 651 ALOGD(" [%3d, %3d, %3d, %3d]\n", 652 head->left, head->top, head->right, head->bottom); 653 head++; 654 } 655} 656 657// ---------------------------------------------------------------------------- 658 659}; // namespace android 660