1/* Copyright (C) 2007-2008 The Android Open Source Project 2** 3** This software is licensed under the terms of the GNU General Public 4** License version 2, as published by the Free Software Foundation, and 5** may be copied, distributed, and modified under those terms. 6** 7** This program is distributed in the hope that it will be useful, 8** but WITHOUT ANY WARRANTY; without even the implied warranty of 9** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10** GNU General Public License for more details. 11*/ 12#include "android/skin/region.h" 13#include <limits.h> 14#include <string.h> 15#include <stdlib.h> /* malloc/free */ 16 17/************************************************************************* 18 ************************************************************************* 19 **** 20 **** ASSERTION SUPPORT 21 **** 22 **** 23 ****/ 24 25#ifdef UNIT_TEST 26#include <stdlib.h> 27#include <stdio.h> 28static void 29_rpanic(void) 30{ 31 *((char*)(void*)0) = 1; /* should SEGFAULT */ 32 /* put a breakpoint here */ 33 exit(1); 34} 35 36#define RASSERT(cond) \ 37 ({ if (!(cond)) { fprintf(stderr, "%s:%d:%s: assertion failed: %s", \ 38 __FILE__, __LINE__, __FUNCTION__, #cond ); _rpanic(); } }) 39 40#else 41#define RASSERT(cond) ((void)0) 42#endif 43 44 45/************************************************************************* 46 ************************************************************************* 47 **** 48 **** IMPLEMENTATION DETAILS 49 **** 50 **** 51 ****/ 52 53/* this implementation of regions encodes the the region's spans with the 54 following format: 55 56 region ::= yband+ YSENTINEL 57 yband ::= YTOP YBOTTOM scanline 58 scanline ::= span+ XSENTINEL 59 span ::= XLEFT XRIGHT 60 61 XSENTINEL ::= 0x7fff 62 YSENTINEL := 0x7fff 63 64 all values are sorted in increasing order, which means that: 65 66 - YTOP1 < YBOTTOM1 <= YTOP2 < YBOTTOM2 <= .... < YSENTINEL 67 - XLEFT1 < XRIGHT1 < XLEFT2 < XRIGHT2 < .... < XSENTINEL 68 (in a given scanline) 69*/ 70 71/* convenience shortbuts */ 72typedef SkinRegionRun Run; 73typedef SkinRegion Region; 74 75#define RUNS_RECT_COUNT 6 /* YTOP YBOT XLEFT XRIGHT XSENTINEL YSENTINEL */ 76 77#define XSENTINEL SKIN_REGION_SENTINEL 78#define YSENTINEL SKIN_REGION_SENTINEL 79 80#define RUNS_EMPTY ((Run*)(void*)(-1)) 81#define RUNS_RECT ((Run*)(void*)(0)) 82 83static __inline__ int 84region_isEmpty( Region* r ) 85{ 86 return r->runs == RUNS_EMPTY; 87} 88 89static __inline__ int 90region_isRect( Region* r ) 91{ 92 return r->runs == RUNS_RECT; 93} 94 95static __inline__ int 96region_isComplex( Region* r ) 97{ 98 return r->runs != RUNS_EMPTY && r->runs != RUNS_RECT; 99} 100 101/** RunStore: ref-counted storage for runs 102 **/ 103 104typedef struct { 105 int refcount; 106 int count; 107} RunStore; 108 109static void 110runstore_free( RunStore* s ) 111{ 112 free(s); 113} 114 115static RunStore* 116runstore_alloc( int count ) 117{ 118 RunStore* s = malloc( sizeof(*s) + sizeof(Run)*count ); 119 RASSERT(s != NULL); 120 s->count = count; 121 s->refcount = 1; 122 return s; 123} 124 125static RunStore* 126runstore_edit( RunStore* s ) 127{ 128 RunStore* s2; 129 130 if (s->refcount == 1) 131 return s; 132 133 s2 = runstore_alloc( s->count ); 134 if (s2) { 135 memcpy( s2, s, sizeof(*s) + s->count*sizeof(Run) ); 136 s->refcount -= 1; 137 s2->refcount = 1; 138 } 139 return s2; 140} 141 142static void 143runstore_unrefp( RunStore* *ps ) 144{ 145 RunStore* s = *ps; 146 if (s != NULL) { 147 if (s->refcount <= 0) 148 runstore_free(s); 149 *ps = NULL; 150 } 151} 152 153static RunStore* 154runstore_ref( RunStore* s ) 155{ 156 if (s) s->refcount += 1; 157 return s; 158} 159 160static __inline__ RunStore* 161runstore_from_runs( Run* runs ) 162{ 163 RASSERT(runs != RUNS_EMPTY); 164 RASSERT(runs != RUNS_RECT); 165 return (RunStore*)runs - 1; 166} 167 168static __inline__ Run* 169runstore_to_runs( RunStore* s ) 170{ 171 RASSERT(s != NULL); 172 return (Run*)(s + 1); 173} 174 175static Run* 176region_edit( Region* r ) 177{ 178 RunStore* s; 179 180 RASSERT(region_isComplex(r)); 181 182 s = runstore_from_runs(r->runs); 183 s = runstore_edit(s); 184 r->runs = runstore_to_runs(s); 185 return r->runs; 186} 187 188/** Run parsing 189 **/ 190 191static Run* 192runs_next_scanline( Run* runs ) 193{ 194 RASSERT(runs[0] != YSENTINEL && runs[1] != YSENTINEL ); 195 runs += 2; 196 do { runs += 1; } while (runs[-1] != XSENTINEL); 197 return runs; 198} 199 200static Run* 201runs_find_y( Run* runs, int y ) 202{ 203 do { 204 int ybot, ytop = runs[0]; 205 206 if (y < ytop) 207 return NULL; 208 209 ybot = runs[1]; 210 if (y < ybot) 211 return runs; 212 213 runs = runs_next_scanline( runs ); 214 } while (runs[0] != YSENTINEL); 215 216 return NULL; 217} 218 219static void 220runs_set_rect( Run* runs, SkinRect* rect ) 221{ 222 runs[0] = rect->pos.y; 223 runs[1] = rect->pos.y + rect->size.h; 224 runs[2] = rect->pos.x; 225 runs[3] = rect->pos.x + rect->size.w; 226 runs[4] = XSENTINEL; 227 runs[5] = YSENTINEL; 228} 229 230static Run* 231runs_copy_scanline( Run* dst, Run* src ) 232{ 233 RASSERT(src[0] != YSENTINEL); 234 RASSERT(src[1] != YSENTINEL); 235 dst[0] = src[0]; 236 dst[1] = src[1]; 237 src += 2; 238 dst += 2; 239 do { *dst++ = *src++; } while (src[-1] != XSENTINEL); 240 return dst; 241} 242 243static Run* 244runs_copy_scanline_adj( Run* dst, Run* src, int ytop, int ybot ) 245{ 246 Run* runs2 = runs_copy_scanline( dst, src ); 247 dst[0] = (Run) ytop; 248 dst[1] = (Run) ybot; 249 return runs2; 250} 251 252static __inline__ Run* 253runs_add_span( Run* dst, int left, int right ) 254{ 255 dst[0] = (Run) left; 256 dst[1] = (Run) right; 257 return dst + 2; 258} 259 260static __inline__ int 261runs_get_count( Run* runs ) 262{ 263 RunStore* s = runstore_from_runs(runs); 264 return s->count; 265} 266 267 268static void 269runs_coalesce_band( Run* *psrc_spans, Run* *pdst_spans, SkinBox* minmax ) 270{ 271 Run* sspan = *psrc_spans; 272 Run* dspan = *pdst_spans; 273 int pleft = sspan[0]; 274 int pright = sspan[1]; 275 int xleft, xright; 276 277 RASSERT(pleft != XSENTINEL); 278 RASSERT(pright != XSENTINEL); 279 RASSERT(pleft < pright); 280 281 if (pleft < minmax->x1) minmax->x1 = pleft; 282 283 sspan += 2; 284 xleft = sspan[0]; 285 286 while (xleft != XSENTINEL) 287 { 288 xright = sspan[1]; 289 RASSERT(xright != XSENTINEL); 290 RASSERT(xleft < xright); 291 292 if (xleft == pright) { 293 pright = xright; 294 } else { 295 dspan[0] = (Run) pleft; 296 dspan[1] = (Run) pright; 297 dspan += 2; 298 } 299 sspan += 2; 300 xleft = sspan[0]; 301 } 302 dspan[0] = (Run) pleft; 303 dspan[1] = (Run) pright; 304 dspan[2] = XSENTINEL; 305 dspan += 3; 306 sspan += 1; /* skip XSENTINEL */ 307 308 if (pright > minmax->x2) minmax->x2 = pright; 309 310 *psrc_spans = sspan; 311 *pdst_spans = dspan; 312} 313 314 315static int 316runs_coalesce( Run* dst, Run* src, SkinBox* minmax ) 317{ 318 Run* prev = NULL; 319 Run* dst0 = dst; 320 int ytop = src[0]; 321 int ybot; 322 323 while (ytop != YSENTINEL) 324 { 325 Run* sspan = src + 2; 326 Run* dspan = dst + 2; 327 328 ybot = src[1]; 329 RASSERT( ytop < ybot ); 330 RASSERT( ybot != YSENTINEL ); 331 RASSERT( src[2] != XSENTINEL ); 332 333 if (ytop < minmax->y1) minmax->y1 = ytop; 334 if (ybot > minmax->y2) minmax->y2 = ybot; 335 336 dst[0] = (Run) ytop; 337 dst[1] = (Run) ybot; 338 339 runs_coalesce_band( &sspan, &dspan, minmax ); 340 341 if (prev && prev[1] == dst[0] && (dst-prev) == (dspan-dst) && 342 !memcmp(prev+2, dst+2, (dspan-dst-2)*sizeof(Run))) 343 { 344 /* coalesce two identical bands */ 345 prev[1] = dst[1]; 346 } 347 else 348 { 349 prev = dst; 350 dst = dspan; 351 } 352 src = sspan; 353 ytop = src[0]; 354 } 355 dst[0] = YSENTINEL; 356 return (dst + 1 - dst0); 357} 358 359/************************************************************************* 360 ************************************************************************* 361 **** 362 **** PUBLIC API 363 **** 364 ****/ 365 366void 367skin_region_init_empty( SkinRegion* r ) 368{ 369 /* empty region */ 370 r->bounds.pos.x = r->bounds.pos.y = 0; 371 r->bounds.size.w = r->bounds.size.h = 0; 372 r->runs = RUNS_EMPTY; 373} 374 375void 376skin_region_init( SkinRegion* r, int x1, int y1, int x2, int y2 ) 377{ 378 if (x1 >= x2 || y1 >= y2) { 379 skin_region_init_empty(r); 380 return; 381 } 382 r->bounds.pos.x = x1; 383 r->bounds.pos.y = y1; 384 r->bounds.size.w = x2 - x1; 385 r->bounds.size.h = y2 - y1; 386 r->runs = RUNS_RECT; 387} 388 389void 390skin_region_init_rect( SkinRegion* r, SkinRect* rect ) 391{ 392 if (rect == NULL || rect->size.w <= 0 || rect->size.h <= 0) { 393 skin_region_init_empty(r); 394 return; 395 } 396 r->bounds = rect[0]; 397 r->runs = RUNS_RECT; 398} 399 400void 401skin_region_init_box( SkinRegion* r, SkinBox* box ) 402{ 403 if (box == NULL || box->x1 >= box->x2 || box->y1 >= box->y2) { 404 skin_region_init_empty(r); 405 return; 406 } 407 r->bounds.pos.x = box->x1; 408 r->bounds.pos.y = box->y1; 409 r->bounds.size.w = box->x2 - box->x1; 410 r->bounds.size.h = box->y2 - box->y1; 411 r->runs = RUNS_RECT; 412} 413 414void 415skin_region_init_copy( SkinRegion* r, SkinRegion* src ) 416{ 417 if (src == NULL || region_isEmpty(src)) 418 skin_region_init_empty(r); 419 else { 420 r[0] = src[0]; 421 if (region_isComplex(src)) { 422 RunStore* s = runstore_from_runs(r->runs); 423 runstore_ref(s); 424 } 425 } 426} 427 428 429void 430skin_region_reset( SkinRegion* r ) 431{ 432 if (r != NULL) { 433 if (region_isComplex(r)) { 434 RunStore* s = runstore_from_runs(r->runs); 435 runstore_unrefp( &s ); 436 } 437 skin_region_init_empty(r); 438 } 439} 440 441 442 443void 444skin_region_copy( SkinRegion* r, SkinRegion* src ) 445{ 446 skin_region_reset(r); 447 skin_region_init_copy(r, src); 448} 449 450 451int 452skin_region_equals( SkinRegion* r1, SkinRegion* r2 ) 453{ 454 Run *runs1, *runs2; 455 RunStore *store1, *store2; 456 457 if (r1 == r2) 458 return 1; 459 460 if (!skin_rect_equals( &r1->bounds, &r2->bounds )) 461 return 0; 462 463 runs1 = r1->runs; 464 runs2 = r2->runs; 465 466 if (runs1 == runs2) /* empties and rects */ 467 return 1; 468 469 if ( !region_isComplex(r1) || !region_isComplex(r2) ) 470 return 0; 471 472 store1 = runstore_from_runs(runs1); 473 store2 = runstore_from_runs(runs2); 474 475 if (store1->count == store2->count && 476 !memcmp( (char*)runs1, (char*)runs2, store1->count*sizeof(Run) ) ) 477 return 1; 478 479 return 0; 480} 481 482void 483skin_region_translate( SkinRegion* r, int dx, int dy ) 484{ 485 Run* runs; 486 487 if (region_isEmpty(r)) 488 return; 489 490 skin_rect_translate( &r->bounds, dx, dy ); 491 if (region_isRect(r)) 492 return; 493 494 runs = region_edit(r); 495 while (runs[0] != YSENTINEL) { 496 int ytop = runs[0]; 497 int ybot = runs[1]; 498 499 RASSERT(ybot != YSENTINEL); 500 runs[0] = (Run)(ytop + dy); 501 runs[1] = (Run)(ybot + dy); 502 runs += 2; 503 while (runs[0] != XSENTINEL) { 504 int xleft = runs[0]; 505 int xright = runs[1]; 506 RASSERT(xright != YSENTINEL); 507 runs[0] = (Run)(xleft + dx); 508 runs[1] = (Run)(xright + dx); 509 runs += 2; 510 } 511 runs += 1; 512 } 513} 514 515void 516skin_region_get_bounds( SkinRegion* r, SkinRect* bounds ) 517{ 518 if (r != NULL) { 519 bounds[0] = r->bounds; 520 } else { 521 bounds->pos.x = bounds->pos.y = 0; 522 bounds->size.w = bounds->size.h = 0; 523 } 524} 525 526int 527skin_region_is_empty( SkinRegion* r ) 528{ 529 return region_isEmpty(r); 530} 531 532int 533skin_region_is_rect( SkinRegion* r ) 534{ 535 return region_isRect(r); 536} 537 538int 539skin_region_is_complex( SkinRegion* r ) 540{ 541 return region_isComplex(r); 542} 543 544void 545skin_region_swap( SkinRegion* r, SkinRegion* r2 ) 546{ 547 SkinRegion tmp; 548 tmp = r[0]; 549 r[0] = r2[0]; 550 r2[0] = tmp; 551} 552 553 554SkinOverlap 555skin_region_contains( SkinRegion* r, int x, int y ) 556{ 557 if (region_isEmpty(r)) 558 return SKIN_OUTSIDE; 559 if (region_isRect(r)) { 560 return skin_rect_contains(&r->bounds,x,y); 561 } else { 562 Run* runs = runs_find_y( r->runs, y ); 563 if (runs != NULL) { 564 runs += 2; 565 do { 566 int xright, xleft = runs[0]; 567 568 if (x < xleft) // also x < xleft == XSENTINEL 569 break; 570 xright = runs[1]; 571 if (xright == XSENTINEL) 572 break; 573 if (x < xright) 574 return SKIN_INSIDE; 575 runs += 2; 576 } while (runs[0] != XSENTINEL); 577 } 578 return SKIN_OUTSIDE; 579 } 580} 581 582 583SkinOverlap 584skin_region_contains_rect( SkinRegion* r, SkinRect* rect ) 585{ 586 SkinRegion r2[1]; 587 skin_region_init_rect( r2, rect ); 588 return skin_region_test_intersect( r, r2 ); 589} 590 591 592SkinOverlap 593skin_region_contains_box( SkinRegion* r, SkinBox* b ) 594{ 595 SkinRegion r2[1]; 596 597 skin_region_init_box( r2, b ); 598 return skin_region_test_intersect( r, r2 ); 599} 600 601 602 603#define FLAG_REGION_1 (1 << 0) 604#define FLAG_REGION_2 (1 << 1) 605#define FLAG_REGION_BOTH (1 << 2) 606 607SkinOverlap 608skin_region_test_intersect( SkinRegion* r1, 609 SkinRegion* r2 ) 610{ 611 Run *runs1, *runs2; 612 Run run2_tmp[ RUNS_RECT_COUNT ]; 613 SkinRect r; 614 615 if (region_isEmpty(r1) || region_isEmpty(r2)) 616 return SKIN_OUTSIDE; 617 618 if ( !skin_rect_intersect( &r, &r1->bounds, &r2->bounds) ) 619 return SKIN_OUTSIDE; 620 621 if (region_isRect(r1)) { 622 if (region_isRect(r2)) { 623 return skin_rect_contains_rect(&r1->bounds, &r2->bounds); 624 } else { 625 SkinRegion* tmp = r1; 626 r1 = r2; 627 r2 = tmp; 628 } 629 } 630 /* here r1 is guaranteed to be complex, r2 is either rect of complex */ 631 runs1 = r1->runs; 632 if (region_isRect(r2)) { 633 runs2 = run2_tmp; 634 runs_set_rect(runs2, &r2->bounds); 635 } 636 else { 637 runs2 = r2->runs; 638 } 639 640 { 641 int flags = 0; 642 643 while (runs1[0] != YSENTINEL && runs2[0] != YSENTINEL) 644 { 645 int ytop1 = runs1[0]; 646 int ybot1 = runs1[1]; 647 int ytop2 = runs2[0]; 648 int ybot2 = runs2[1]; 649 650 if (ybot1 <= ytop2) 651 { 652 /* band1 over band2 */ 653 flags |= FLAG_REGION_1; 654 runs1 = runs_next_scanline( runs1 ); 655 } 656 else if (ybot2 <= ytop1) 657 { 658 /* band2 over band1 */ 659 flags |= FLAG_REGION_2; 660 runs2 = runs_next_scanline( runs2 ); 661 } 662 else /* band1 and band2 overlap */ 663 { 664 Run* span1; 665 Run* span2; 666 int ybot; 667 668 if (ytop1 < ytop2) { 669 flags |= FLAG_REGION_1; 670 ytop1 = ytop2; 671 } else if (ytop2 < ytop1) { 672 flags |= FLAG_REGION_2; 673 ytop2 = ytop1; 674 } 675 676 ybot = (ybot1 < ybot2) ? ybot1 : ybot2; 677 678 span1 = runs1 + 2; 679 span2 = runs2 + 2; 680 681 while (span1[0] != XSENTINEL && span2[0] != XSENTINEL) 682 { 683 int xleft1 = span1[0]; 684 int xright1 = span1[1]; 685 int xleft2 = span2[0]; 686 int xright2 = span2[1]; 687 688 RASSERT(xright1 != XSENTINEL); 689 RASSERT(xright2 != XSENTINEL); 690 691 if (xright1 <= xleft2) { 692 flags |= FLAG_REGION_1; 693 span1 += 2; 694 } 695 else if (xright2 <= xleft1) { 696 flags |= FLAG_REGION_2; 697 span2 += 2; 698 } 699 else { 700 int xright; 701 702 if (xleft1 < xleft2) { 703 flags |= FLAG_REGION_1; 704 xleft1 = xleft2; 705 } else if (xleft2 < xleft1) { 706 flags |= FLAG_REGION_2; 707 xleft2 = xleft1; 708 } 709 710 xright = (xright1 < xright2) ? xright1 : xright2; 711 712 flags |= FLAG_REGION_BOTH; 713 714 if (xright == xright1) 715 span1 += 2; 716 if (xright == xright2) 717 span2 += 2; 718 } 719 } 720 721 if (span1[0] != XSENTINEL) { 722 flags |= FLAG_REGION_1; 723 } 724 725 if (span2[0] != XSENTINEL) { 726 flags |= FLAG_REGION_2; 727 } 728 729 if (ybot == ybot1) 730 runs1 = runs_next_scanline( runs1 ); 731 732 if (ybot == ybot2) 733 runs2 = runs_next_scanline( runs2 ); 734 } 735 } 736 737 if (runs1[0] != YSENTINEL) { 738 flags |= FLAG_REGION_1; 739 } 740 741 if (runs2[0] != YSENTINEL) { 742 flags |= FLAG_REGION_2; 743 } 744 745 if ( !(flags & FLAG_REGION_BOTH) ) { 746 /* no intersection at all */ 747 return SKIN_OUTSIDE; 748 } 749 750 if ( (flags & FLAG_REGION_2) != 0 ) { 751 /* intersection + overlap */ 752 return SKIN_OVERLAP; 753 } 754 755 return SKIN_INSIDE; 756 } 757} 758 759typedef struct { 760 Run* runs1; 761 Run* runs2; 762 Run* runs_base; 763 Run* runs; 764 RunStore* store; 765 Region result[1]; 766 Run runs1_rect[ RUNS_RECT_COUNT ]; 767 Run runs2_rect[ RUNS_RECT_COUNT ]; 768} RegionOperator; 769 770 771static void 772region_operator_init( RegionOperator* o, 773 Region* r1, 774 Region* r2 ) 775{ 776 int run1_count, run2_count; 777 int maxruns; 778 779 RASSERT( !region_isEmpty(r1) ); 780 RASSERT( !region_isEmpty(r2) ); 781 782 if (region_isRect(r1)) { 783 run1_count = RUNS_RECT_COUNT; 784 o->runs1 = o->runs1_rect; 785 runs_set_rect( o->runs1, &r1->bounds ); 786 } else { 787 o->runs1 = r1->runs; 788 run1_count = runs_get_count(r1->runs); 789 } 790 791 if (region_isRect(r2)) { 792 run2_count = RUNS_RECT_COUNT; 793 o->runs2 = o->runs2_rect; 794 runs_set_rect( o->runs2, &r2->bounds ); 795 } else { 796 o->runs2 = r2->runs; 797 run2_count = runs_get_count(r2->runs); 798 } 799 800 maxruns = run1_count < run2_count ? run2_count : run1_count; 801 o->store = runstore_alloc( 3*maxruns ); 802 o->runs_base = runstore_to_runs(o->store); 803} 804 805 806static void 807region_operator_do( RegionOperator* o, int wanted ) 808{ 809 Run* runs1 = o->runs1; 810 Run* runs2 = o->runs2; 811 Run* runs = o->runs_base; 812 int ytop1 = runs1[0]; 813 int ytop2 = runs2[0]; 814 815 if (ytop1 != YSENTINEL && ytop2 != YSENTINEL) 816 { 817 int ybot1, ybot2; 818 819 while (ytop1 != YSENTINEL && ytop2 != YSENTINEL) 820 { 821 int ybot; 822 823 ybot1 = runs1[1]; 824 ybot2 = runs2[1]; 825 826 RASSERT(ybot1 != YSENTINEL); 827 RASSERT(ybot2 != YSENTINEL); 828 829 if (ybot1 <= ytop2) { 830 if (wanted & FLAG_REGION_1) 831 runs = runs_copy_scanline_adj( runs, runs1, ytop1, ybot1 ); 832 runs1 = runs_next_scanline( runs1 ); 833 ytop1 = runs1[0]; 834 continue; 835 } 836 837 if (ybot2 <= ytop1) { 838 if (wanted & FLAG_REGION_2) 839 runs = runs_copy_scanline_adj( runs, runs2, ytop2, ybot2 ); 840 runs2 = runs_next_scanline(runs2); 841 ytop2 = runs2[0]; 842 continue; 843 } 844 845 if (ytop1 < ytop2) { 846 if (wanted & FLAG_REGION_1) 847 runs = runs_copy_scanline_adj( runs, runs1, ytop1, ytop2 ); 848 ytop1 = ytop2; 849 } 850 else if (ytop2 < ytop1) { 851 if (wanted & FLAG_REGION_2) 852 runs = runs_copy_scanline_adj( runs, runs2, ytop2, ytop1 ); 853 ytop2 = ytop1; 854 } 855 856 ybot = (ybot1 <= ybot2) ? ybot1 : ybot2; 857 858 runs[0] = (Run) ytop1; 859 runs[1] = (Run) ybot; 860 861 /* do the common band */ 862 { 863 Run* span1 = runs1 + 2; 864 Run* span2 = runs2 + 2; 865 Run* span = runs + 2; 866 int xleft1 = span1[0]; 867 int xleft2 = span2[0]; 868 int xright1, xright2; 869 870 while (xleft1 != XSENTINEL && xleft2 != XSENTINEL) 871 { 872 int xright; 873 874 xright1 = span1[1]; 875 xright2 = span2[1]; 876 877 RASSERT(xright1 != XSENTINEL); 878 RASSERT(xright2 != XSENTINEL); 879 880 if (xright1 <= xleft2) { 881 if (wanted & FLAG_REGION_1) 882 span = runs_add_span( span, xleft1, xright1 ); 883 span1 += 2; 884 xleft1 = span1[0]; 885 continue; 886 } 887 888 if (xright2 <= xleft1) { 889 if (wanted & FLAG_REGION_2) 890 span = runs_add_span( span, xleft2, xright2 ); 891 span2 += 2; 892 xleft2 = span2[0]; 893 continue; 894 } 895 896 if (xleft1 < xleft2) { 897 if (wanted & FLAG_REGION_1) 898 span = runs_add_span( span, xleft1, xleft2 ); 899 xleft1 = xleft2; 900 } 901 902 else if (xleft2 < xleft1) { 903 if (wanted & FLAG_REGION_2) 904 span = runs_add_span( span, xleft2, xleft1 ); 905 xleft2 = xleft1; 906 } 907 908 xright = (xright1 <= xright2) ? xright1 : xright2; 909 910 if (wanted & FLAG_REGION_BOTH) 911 span = runs_add_span( span, xleft1, xright ); 912 913 xleft1 = xleft2 = xright; 914 915 if (xright == xright1) { 916 span1 += 2; 917 xleft1 = span1[0]; 918 } 919 if (xright == xright2) { 920 span2 += 2; 921 xleft2 = span2[0]; 922 } 923 } 924 925 if (wanted & FLAG_REGION_1) { 926 while (xleft1 != XSENTINEL) { 927 RASSERT(span1[1] != XSENTINEL); 928 span[0] = (Run) xleft1; 929 span[1] = span1[1]; 930 span += 2; 931 span1 += 2; 932 xleft1 = span1[0]; 933 } 934 } 935 936 if (wanted & FLAG_REGION_2) { 937 while (xleft2 != XSENTINEL) { 938 RASSERT(span2[1] != XSENTINEL); 939 span[0] = (Run) xleft2; 940 span[1] = span2[1]; 941 span += 2; 942 span2 += 2; 943 xleft2 = span2[0]; 944 } 945 } 946 947 if (span > runs + 2) { 948 span[0] = XSENTINEL; 949 runs = span + 1; 950 } 951 } 952 953 ytop1 = ytop2 = ybot; 954 955 if (ybot == ybot1) { 956 runs1 = runs_next_scanline( runs1 ); 957 ytop1 = runs1[0]; 958 } 959 if (ybot == ybot2) { 960 runs2 = runs_next_scanline( runs2 ); 961 ytop2 = runs2[0]; 962 } 963 } 964 } 965 966 if ((wanted & FLAG_REGION_1) != 0) { 967 while (ytop1 != YSENTINEL) { 968 runs = runs_copy_scanline_adj( runs, runs1, ytop1, runs1[1] ); 969 runs1 = runs_next_scanline(runs1); 970 ytop1 = runs1[0]; 971 } 972 } 973 974 if ((wanted & FLAG_REGION_2) != 0) { 975 while (ytop2 != YSENTINEL) { 976 runs = runs_copy_scanline_adj( runs, runs2, ytop2, runs2[1] ); 977 runs2 = runs_next_scanline(runs2); 978 ytop2 = runs2[0]; 979 } 980 } 981 982 runs[0] = YSENTINEL; 983 o->runs = runs + 1; 984} 985 986/* returns 1 if the result is not empty */ 987static int 988region_operator_done( RegionOperator* o ) 989{ 990 Run* src = o->runs; 991 int count; 992 SkinBox minmax; 993 RunStore* store; 994 995 if (src <= o->runs_base + 1) { 996 /* result is empty */ 997 skin_region_init_empty( o->result ); 998 return 0; 999 } 1000 1001 /* coalesce the temp runs in-place and compute the corresponding bounds */ 1002 minmax.x1 = minmax.y1 = INT_MAX; 1003 minmax.x2 = minmax.y2 = INT_MIN; 1004 1005 count = runs_coalesce( o->runs_base, o->runs_base, &minmax ); 1006 if (count == 1) { 1007 /* result is empty */ 1008 skin_region_init_empty( o->result ); 1009 } 1010 else 1011 { 1012 skin_box_to_rect( &minmax, &o->result->bounds ); 1013 if (count == RUNS_RECT_COUNT) { 1014 o->result->runs = RUNS_RECT; 1015 } 1016 else 1017 { 1018 /* result is complex */ 1019 store = runstore_alloc( count ); 1020 o->result->runs = runstore_to_runs(store); 1021 memcpy( o->result->runs, o->runs_base, count*sizeof(Run) ); 1022 } 1023 } 1024 1025 /* release temporary runstore */ 1026 runstore_unrefp( &o->store ); 1027 1028 return region_isEmpty(o->result); 1029} 1030 1031 1032 1033int 1034skin_region_intersect( SkinRegion* r, SkinRegion* r2 ) 1035{ 1036 RegionOperator oper[1]; 1037 1038 if (region_isEmpty(r)) 1039 return 0; 1040 1041 if (region_isEmpty(r2)) 1042 return 1; 1043 1044 if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { 1045 skin_region_init_empty(r); 1046 return 0; 1047 } 1048 1049 region_operator_init( oper, r, r2 ); 1050 region_operator_do( oper, FLAG_REGION_BOTH ); 1051 region_operator_done( oper ); 1052 1053 skin_region_swap( r, oper->result ); 1054 skin_region_reset( oper->result ); 1055 1056 return region_isEmpty( r ); 1057} 1058 1059 1060/* performs r = (intersect r (region+_from_rect rect)), returns true iff 1061 the resulting region is not empty */ 1062int 1063skin_region_intersect_rect( SkinRegion* r, SkinRect* rect ) 1064{ 1065 Region r2[1]; 1066 1067 skin_region_init_rect( r2, rect ); 1068 return skin_region_intersect( r, r2 ); 1069} 1070 1071/* performs r = (union r r2) */ 1072void 1073skin_region_union( SkinRegion* r, SkinRegion* r2 ) 1074{ 1075 RegionOperator oper[1]; 1076 1077 if (region_isEmpty(r)) { 1078 skin_region_copy(r, r2); 1079 return; 1080 } 1081 1082 if (region_isEmpty(r2)) 1083 return; 1084 1085 region_operator_init( oper, r, r2 ); 1086 region_operator_do( oper, FLAG_REGION_1|FLAG_REGION_2|FLAG_REGION_BOTH ); 1087 region_operator_done( oper ); 1088 1089 skin_region_swap( r, oper->result ); 1090 skin_region_reset( oper->result ); 1091} 1092 1093void 1094skin_region_union_rect( SkinRegion* r, SkinRect* rect ) 1095{ 1096 Region r2[1]; 1097 1098 skin_region_init_rect(r2, rect); 1099 return skin_region_union( r, r2 ); 1100} 1101 1102/* performs r = (difference r r2) */ 1103void 1104skin_region_substract( SkinRegion* r, SkinRegion* r2 ) 1105{ 1106 RegionOperator oper[1]; 1107 1108 if (region_isEmpty(r) || region_isEmpty(r2)) 1109 return; 1110 1111 if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { 1112 skin_region_init_empty(r); 1113 return; 1114 } 1115 1116 region_operator_init( oper, r, r2 ); 1117 region_operator_do( oper, FLAG_REGION_1 ); 1118 region_operator_done( oper ); 1119 1120 skin_region_swap( r, oper->result ); 1121 skin_region_reset( oper->result ); 1122} 1123 1124void 1125skin_region_substract_rect( SkinRegion* r, SkinRect* rect ) 1126{ 1127 Region r2[1]; 1128 1129 skin_region_init_rect(r2, rect); 1130 return skin_region_substract( r, r2 ); 1131} 1132 1133/* performs r = (xor r r2) */ 1134void 1135skin_region_xor( SkinRegion* r, SkinRegion* r2 ) 1136{ 1137 RegionOperator oper[1]; 1138 1139 if (region_isEmpty(r)) { 1140 skin_region_copy(r, r2); 1141 return; 1142 } 1143 1144 if (region_isEmpty(r2)) 1145 return; 1146 1147 if ( skin_rect_contains_rect( &r->bounds, &r2->bounds ) == SKIN_OUTSIDE ) { 1148 skin_region_init_empty(r); 1149 return; 1150 } 1151 1152 region_operator_init( oper, r, r2 ); 1153 region_operator_do( oper, FLAG_REGION_1 ); 1154 region_operator_done( oper ); 1155 1156 skin_region_swap( r, oper->result ); 1157 skin_region_reset( oper->result ); 1158} 1159 1160 1161void 1162skin_region_iterator_init( SkinRegionIterator* iter, 1163 SkinRegion* region ) 1164{ 1165 iter->region = region; 1166 iter->band = NULL; 1167 iter->span = NULL; 1168} 1169 1170int 1171skin_region_iterator_next( SkinRegionIterator* iter, SkinRect *rect ) 1172{ 1173 static const Run dummy[ 2 ] = { XSENTINEL, YSENTINEL }; 1174 1175 Run* span = iter->span; 1176 Run* band = iter->band; 1177 1178 if (span == NULL) { 1179 Region* r = iter->region; 1180 if (region_isEmpty(r)) 1181 return 0; 1182 if (region_isRect(r)) { 1183 rect[0] = r->bounds; 1184 iter->span = (Run*) dummy; 1185 return 1; 1186 } 1187 iter->band = band = r->runs; 1188 iter->span = span = r->runs + 2; 1189 } 1190 else if (band == NULL) 1191 return 0; 1192 1193 while (span[0] == XSENTINEL) { 1194 band = span + 1; 1195 if (band[0] == YSENTINEL || band[1] == YSENTINEL) 1196 return 0; 1197 1198 iter->band = band; 1199 iter->span = span = band + 2; 1200 } 1201 1202 if (span[1] == XSENTINEL) 1203 return 0; 1204 1205 rect->pos.y = band[0]; 1206 rect->pos.x = span[0]; 1207 rect->size.h = band[1] - band[0]; 1208 rect->size.w = span[1] - span[0]; 1209 1210 iter->span = span + 2; 1211 return 1; 1212} 1213 1214int 1215skin_region_iterator_next_box( SkinRegionIterator* iter, SkinBox *box ) 1216{ 1217 SkinRect rect; 1218 int result = skin_region_iterator_next( iter, &rect ); 1219 1220 if (result) 1221 skin_box_from_rect( box, &rect ); 1222 1223 return result; 1224} 1225 1226#ifdef UNIT_TEST 1227 1228#include <stdio.h> 1229#include <stdlib.h> 1230#include "skin_rect.c" 1231 1232static void 1233panic(void) 1234{ 1235 *((char*)0) = 1; 1236 exit(0); 1237} 1238 1239static void 1240_expectCompare( Region* r, const SkinBox* boxes, int count ) 1241{ 1242 if (count == 0) { 1243 if ( !skin_region_is_empty(r) ) { 1244 printf( " result is not empty\n" ); 1245 panic(); 1246 } 1247 } 1248 else if (count == 1) { 1249 SkinRect rect1, rect2; 1250 if ( !skin_region_is_rect(r) ) { 1251 printf( " result is not a rectangle\n" ); 1252 panic(); 1253 } 1254 skin_region_get_bounds( r, &rect1 ); 1255 skin_box_to_rect( (SkinBox*)boxes, &rect2 ); 1256 if ( !skin_rect_equals( &rect1, &rect2 ) ) { 1257 printf( " result is (%d,%d,%d,%d), expected (%d,%d,%d,%d)\n", 1258 rect1.pos.x, rect1.pos.y, 1259 rect1.pos.x + rect1.size.w, rect1.pos.y + rect1.size.h, 1260 rect2.pos.x, rect2.pos.y, 1261 rect2.pos.x + rect2.size.w, rect2.pos.y + rect2.size.h ); 1262 panic(); 1263 } 1264 } 1265 else { 1266 SkinRegionIterator iter; 1267 SkinBox b; 1268 int n; 1269 1270 skin_region_iterator_init( &iter, r ); 1271 n = 0; 1272 while (n < count) { 1273 if ( !skin_region_iterator_next_box( &iter, &b ) ) { 1274 printf( "missing region box (%d, %d, %d, %d)\n", 1275 boxes->x1, boxes->y1, boxes->x2, boxes->y2 ); 1276 panic(); 1277 } 1278 1279 if (b.x1 != boxes->x1 || b.x2 != boxes->x2|| 1280 b.y1 != boxes->y1 || b.y2 != boxes->y2) 1281 { 1282 printf( "invalid region box (%d,%d,%d,%d) expecting (%d,%d,%d,%d)\n", 1283 b.x1, b.y1, b.x2, b.y2, 1284 boxes->x1, boxes->y1, boxes->x2, boxes->y2 ); 1285 panic(); 1286 } 1287 boxes += 1; 1288 n += 1; 1289 } 1290 1291 if ( skin_region_iterator_next_box( &iter, &b ) ) { 1292 printf( "excess region box (%d,%d,%d,%d)\n", 1293 b.x1, b.y1, b.x2, b.y2 ); 1294 panic(); 1295 } 1296 } 1297} 1298 1299 1300static void 1301expectEmptyRegion( Region* r ) 1302{ 1303 printf( "expectEmptyRegion: " ); 1304 if (!skin_region_is_empty(r)) { 1305 printf( "region not empty !!\n" ); 1306 panic(); 1307 } 1308 printf( "ok\n" ); 1309} 1310 1311static void 1312expectTestIntersect( Region* r1, Region* r2, SkinOverlap overlap ) 1313{ 1314 SkinOverlap result; 1315 printf( "expectTestIntersect(%d): ", overlap ); 1316 result = skin_region_test_intersect(r1, r2); 1317 if (result != overlap) { 1318 printf( "bad result %d, expected %d\n", result, overlap ); 1319 panic(); 1320 } 1321 printf( "ok\n" ); 1322} 1323 1324static void 1325expectRectRegion( Region* r, int x1, int y1, int x2, int y2 ) 1326{ 1327 SkinRect rect; 1328 SkinBox b; 1329 1330 printf( "expectRectRegion(%d,%d,%d,%d): ",x1,y1,x2,y2 ); 1331 if (!skin_region_is_rect(r)) { 1332 printf( "region not rect !!\n" ); 1333 panic(); 1334 } 1335 1336 skin_region_get_bounds( r, &rect ); 1337 skin_box_from_rect( &b, &rect ); 1338 1339 if (b.x1 != x1 || b.x2 != x2 || b.y1 != y1 || b.y2 != y2) { 1340 printf( "rect region bounds are (%d,%d,%d,%d), expecting (%d,%d,%d,%d)\n", 1341 b.x1, b.y1, b.x2, b.y2, x1, y1, x2, y2 ); 1342 panic(); 1343 } 1344 printf( "ok\n" ); 1345} 1346 1347static void 1348expectComplexRegion( Region* r, const SkinBox* boxes, int count ) 1349{ 1350 SkinRegionIterator iter; 1351 SkinBox b; 1352 int n; 1353 1354 printf( "expectComplexRegion(): " ); 1355 if (!skin_region_is_complex(r)) { 1356 printf( "region is not complex !!\n" ); 1357 panic(); 1358 } 1359 _expectCompare( r, boxes, count ); 1360 printf( "ok\n" ); 1361} 1362 1363static void 1364expectIntersect( Region* r1, Region* r2, const SkinBox* boxes, int count ) 1365{ 1366 SkinRegion r[1]; 1367 1368 printf( "expectIntersect(%d): ", count ); 1369 skin_region_init_copy( r, r1 ); 1370 skin_region_intersect( r, r2 ); 1371 _expectCompare( r, boxes, count ); 1372 printf( "ok\n" ); 1373} 1374 1375static void 1376expectUnion( Region* r1, Region* r2, const SkinBox* boxes, int count ) 1377{ 1378 SkinRegion r[1]; 1379 1380 printf( "expectUnion(%d): ", count ); 1381 skin_region_init_copy( r, r1 ); 1382 skin_region_union( r, r2 ); 1383 _expectCompare( r, boxes, count ); 1384 printf( "ok\n" ); 1385} 1386 1387 1388static void 1389expectSubstract( Region* r1, Region* r2, const SkinBox* boxes, int count ) 1390{ 1391 SkinRegion r[1]; 1392 1393 printf( "expectSubstract(%d): ", count ); 1394 skin_region_init_copy( r, r1 ); 1395 skin_region_substract( r, r2 ); 1396 _expectCompare( r, boxes, count ); 1397 printf( "ok\n" ); 1398} 1399 1400 1401int main( void ) 1402{ 1403 SkinRegion r[1], r2[1]; 1404 1405 skin_region_init_empty( r ); 1406 expectEmptyRegion( r ); 1407 1408 skin_region_init( r, 10, 20, 110, 120 ); 1409 expectRectRegion( r, 10, 20, 110, 120 ); 1410 1411 skin_region_translate( r, 50, 80 ); 1412 expectRectRegion( r, 60, 100, 160, 200 ); 1413 1414 skin_region_init( r, 10, 10, 40, 40 ); 1415 skin_region_init( r2, 20, 20, 50, 50 ); 1416 expectTestIntersect( r, r2, SKIN_OVERLAP ); 1417 1418 skin_region_translate(r2, +20, + 20 ); 1419 expectTestIntersect( r, r2, SKIN_OUTSIDE ); 1420 1421 skin_region_translate(r2, -30, -30 ); 1422 expectTestIntersect( r, r2, SKIN_INSIDE ); 1423 1424 { 1425 static const SkinBox result1[1] = { 1426 { 20, 20, 40, 40 } 1427 }; 1428 static const SkinBox result2[3] = { 1429 { 10, 10, 40, 20 }, 1430 { 10, 20, 50, 40 }, 1431 { 20, 40, 50, 50 }, 1432 }; 1433 static const SkinBox result3[2] = { 1434 { 10, 10, 40, 20 }, 1435 { 10, 20, 20, 40 }, 1436 }; 1437 1438 skin_region_init( r, 10, 10, 40, 40 ); 1439 skin_region_init( r2, 20, 20, 50, 50 ); 1440 expectIntersect( r, r2, result1, 1 ); 1441 expectUnion( r, r2, result2, 3 ); 1442 expectSubstract( r, r2, result3, 2 ); 1443 } 1444 1445 return 0; 1446} 1447 1448#endif /* UNIT_TEST */ 1449