1 /* $Xorg: Region.c,v 1.6 2001/02/09 02:03:35 xorgcvs Exp $ */ 2 /************************************************************************ 3 4 Copyright 1987, 1988, 1998 The Open Group 5 6 Permission to use, copy, modify, distribute, and sell this software and its 7 documentation for any purpose is hereby granted without fee, provided that 8 the above copyright notice appear in all copies and that both that 9 copyright notice and this permission notice appear in supporting 10 documentation. 11 12 The above copyright notice and this permission notice shall be included in 13 all copies or substantial portions of the Software. 14 15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 21 22 Except as contained in this notice, the name of The Open Group shall not be 23 used in advertising or otherwise to promote the sale, use or other dealings 24 in this Software without prior written authorization from The Open Group. 25 26 27 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts. 28 29 All Rights Reserved 30 31 Permission to use, copy, modify, and distribute this software and its 32 documentation for any purpose and without fee is hereby granted, 33 provided that the above copyright notice appear in all copies and that 34 both that copyright notice and this permission notice appear in 35 supporting documentation, and that the name of Digital not be 36 used in advertising or publicity pertaining to distribution of the 37 software without specific, written prior permission. 38 39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 45 SOFTWARE. 46 47 ************************************************************************/ 48 /* $XFree86: xc/lib/X11/Region.c,v 1.9 2002/06/04 22:19:57 dawes Exp $ */ 49 /* 50 * The functions in this file implement the BRegion* abstraction, similar to one 51 * used in the X11 sample server. A BRegion* is simply an area, as the name 52 * implies, and is implemented as a "y-x-banded" array of rectangles. To 53 * explain: Each BRegion* is made up of a certain number of rectangles sorted 54 * by y coordinate first, and then by x coordinate. 55 * 56 * Furthermore, the rectangles are banded such that every rectangle with a 57 * given upper-left y coordinate (top) will have the same lower-right y 58 * coordinate (bottom) and vice versa. If a rectangle has scanlines in a band, it 59 * will span the entire vertical distance of the band. This means that some 60 * areas that could be merged into a taller rectangle will be represented as 61 * several shorter rectangles to account for shorter rectangles to its left 62 * or right but within its "vertical scope". 63 * 64 * An added constraint on the rectangles is that they must cover as much 65 * horizontal area as possible. E.g. no two rectangles in a band are allowed 66 * to touch. 67 * 68 * Whenever possible, bands will be merged together to cover a greater vertical 69 * distance (and thus reduce the number of rectangles). Two bands can be merged 70 * only if the bottom of one touches the top of the other and they have 71 * rectangles in the same places (of the same width, of course). This maintains 72 * the y-x-banding that's so nice to have... 73 */ 74 75 #include "RegionSupport.h" 76 77 #include <stdlib.h> 78 #include <new> 79 80 using std::nothrow; 81 82 #include <SupportDefs.h> 83 84 85 #ifdef DEBUG 86 #include <stdio.h> 87 #define assert(expr) {if (!(expr)) fprintf(stderr,\ 88 "Assertion failed file %s, line %d: " #expr "\n", __FILE__, __LINE__); } 89 #else 90 #define assert(expr) 91 #endif 92 93 94 /* 1 if two clipping_rects overlap. 95 * 0 if two clipping_rects do not overlap. 96 * Remember, right and bottom are not in the region 97 */ 98 #define EXTENTCHECK(r1, r2) \ 99 ((r1)->right > (r2)->left && \ 100 (r1)->left < (r2)->right && \ 101 (r1)->bottom > (r2)->top && \ 102 (r1)->top < (r2)->bottom) 103 104 /* 105 * update region fBounds 106 */ 107 #define EXTENTS(r,idRect){\ 108 if ((r)->left < (idRect)->fBounds.left)\ 109 (idRect)->fBounds.left = (r)->left;\ 110 if ((r)->top < (idRect)->fBounds.top)\ 111 (idRect)->fBounds.top = (r)->top;\ 112 if ((r)->right > (idRect)->fBounds.right)\ 113 (idRect)->fBounds.right = (r)->right;\ 114 if ((r)->bottom > (idRect)->fBounds.bottom)\ 115 (idRect)->fBounds.bottom = (r)->bottom;\ 116 } 117 118 /* 119 * Check to see if there is enough memory in the present region. 120 */ 121 #define MEMCHECK(reg, rect, firstrect){\ 122 if ((reg)->fCount >= ((reg)->fDataSize - 1)){\ 123 (firstrect) = (clipping_rect *) realloc \ 124 ((char *)(firstrect), (unsigned) (2 * (sizeof(clipping_rect)) * ((reg)->fDataSize)));\ 125 if ((firstrect) == 0)\ 126 return(0);\ 127 (reg)->fDataSize *= 2;\ 128 (rect) = &(firstrect)[(reg)->fCount];\ 129 }\ 130 } 131 132 /* this routine checks to see if the previous rectangle is the same 133 * or subsumes the new rectangle to add. 134 */ 135 136 #define CHECK_PREVIOUS(Reg, R, Rx1, Ry1, Rx2, Ry2)\ 137 (!(((Reg)->fCount > 0)&&\ 138 ((R-1)->top == (Ry1)) &&\ 139 ((R-1)->bottom == (Ry2)) &&\ 140 ((R-1)->left <= (Rx1)) &&\ 141 ((R-1)->right >= (Rx2)))) 142 143 /* add a rectangle to the given BRegion */ 144 #define ADDRECT(reg, r, rx1, ry1, rx2, ry2){\ 145 if (((rx1) < (rx2)) && ((ry1) < (ry2)) &&\ 146 CHECK_PREVIOUS((reg), (r), (rx1), (ry1), (rx2), (ry2))){\ 147 (r)->left = (rx1);\ 148 (r)->top = (ry1);\ 149 (r)->right = (rx2);\ 150 (r)->bottom = (ry2);\ 151 EXTENTS((r), (reg));\ 152 (reg)->fCount++;\ 153 (r)++;\ 154 }\ 155 } 156 157 158 159 /* add a rectangle to the given BRegion */ 160 #define ADDRECTNOX(reg, r, rx1, ry1, rx2, ry2){\ 161 if ((rx1 < rx2) && (ry1 < ry2) &&\ 162 CHECK_PREVIOUS((reg), (r), (rx1), (ry1), (rx2), (ry2))){\ 163 (r)->left = (rx1);\ 164 (r)->top = (ry1);\ 165 (r)->right = (rx2);\ 166 (r)->bottom = (ry2);\ 167 (reg)->fCount++;\ 168 (r)++;\ 169 }\ 170 } 171 172 #define EMPTY_REGION(pReg) pReg->MakeEmpty() 173 174 #define REGION_NOT_EMPTY(pReg) pReg->fCount 175 176 #define INBOX(r, x, y) \ 177 ( ( ((r).right > x)) && \ 178 ( ((r).left <= x)) && \ 179 ( ((r).bottom > y)) && \ 180 ( ((r).top <= y)) ) 181 182 183 184 /* Create a new empty region */ 185 BRegion* 186 BRegion::Support::CreateRegion(void) 187 { 188 return new (nothrow) BRegion(); 189 } 190 191 void 192 BRegion::Support::DestroyRegion(BRegion* r) 193 { 194 delete r; 195 } 196 197 198 /*- 199 *----------------------------------------------------------------------- 200 * miSetExtents -- 201 * Reset the fBounds of a region to what they should be. Called by 202 * miSubtract and miIntersect b/c they can't figure it out along the 203 * way or do so easily, as miUnion can. 204 * 205 * Results: 206 * None. 207 * 208 * Side Effects: 209 * The region's 'fBounds' structure is overwritten. 210 * 211 *----------------------------------------------------------------------- 212 */ 213 void 214 BRegion::Support::miSetExtents(BRegion* pReg) 215 { 216 clipping_rect* pBox; 217 clipping_rect* pBoxEnd; 218 clipping_rect* pExtents; 219 220 if (pReg->fCount == 0) 221 { 222 pReg->fBounds.left = 0; 223 pReg->fBounds.top = 0; 224 pReg->fBounds.right = 0; 225 pReg->fBounds.bottom = 0; 226 return; 227 } 228 229 pExtents = &pReg->fBounds; 230 pBox = pReg->fData; 231 pBoxEnd = &pBox[pReg->fCount - 1]; 232 233 /* 234 * Since pBox is the first rectangle in the region, it must have the 235 * smallest top and since pBoxEnd is the last rectangle in the region, 236 * it must have the largest bottom, because of banding. Initialize left and 237 * right from pBox and pBoxEnd, resp., as good things to initialize them 238 * to... 239 */ 240 pExtents->left = pBox->left; 241 pExtents->top = pBox->top; 242 pExtents->right = pBoxEnd->right; 243 pExtents->bottom = pBoxEnd->bottom; 244 245 assert(pExtents->top < pExtents->bottom); 246 while (pBox <= pBoxEnd) 247 { 248 if (pBox->left < pExtents->left) 249 { 250 pExtents->left = pBox->left; 251 } 252 if (pBox->right > pExtents->right) 253 { 254 pExtents->right = pBox->right; 255 } 256 pBox++; 257 } 258 assert(pExtents->left < pExtents->right); 259 } 260 261 262 /* TranslateRegion(pRegion, x, y) 263 translates in place 264 added by raymond 265 */ 266 void 267 BRegion::Support::XOffsetRegion( 268 BRegion* pRegion, 269 int x, 270 int y) 271 { 272 int nbox; 273 clipping_rect *pbox; 274 275 pbox = pRegion->fData; 276 nbox = pRegion->fCount; 277 278 while(nbox--) 279 { 280 pbox->left += x; 281 pbox->right += x; 282 pbox->top += y; 283 pbox->bottom += y; 284 pbox++; 285 } 286 pRegion->fBounds.left += x; 287 pRegion->fBounds.right += x; 288 pRegion->fBounds.top += y; 289 pRegion->fBounds.bottom += y; 290 } 291 292 /* 293 Utility procedure Compress: 294 Replace r by the region r', where 295 p in r' iff (Quantifer m <= dx) (p + m in r), and 296 Quantifier is Exists if grow is true, For all if grow is false, and 297 (x,y) + m = (x+m,y) if xdir is true; (x,y+m) if xdir is false. 298 299 Thus, if xdir is true and grow is false, r is replaced by the region 300 of all points p such that p and the next dx points on the same 301 horizontal scan line are all in r. We do this using by noting 302 that p is the head of a run of length 2^i + k iff p is the head 303 of a run of length 2^i and p+2^i is the head of a run of length 304 k. Thus, the loop invariant: s contains the region corresponding 305 to the runs of length shift. r contains the region corresponding 306 to the runs of length 1 + dxo & (shift-1), where dxo is the original 307 value of dx. dx = dxo & ~(shift-1). As parameters, s and t are 308 scratch regions, so that we don't have to allocate them on every 309 call. 310 */ 311 312 #if 0 313 #define ZOpRegion(a,b,c) if (grow) BRegion::Support::XUnionRegion(a,b,c); \ 314 else BRegion::Support::XIntersectRegion(a,b,c) 315 #define ZShiftRegion(a,b) if (xdir) BRegion::Support::XOffsetRegion(a,b,0); \ 316 else BRegion::Support::XOffsetRegion(a,0,b) 317 #define ZCopyRegion(a,b) BRegion::Support::XUnionRegion(a,a,b) 318 319 static void 320 Compress( 321 BRegion* r, BRegion* s, BRegion* t, 322 register unsigned dx, 323 register int xdir, register int grow) 324 { 325 register unsigned shift = 1; 326 327 ZCopyRegion(r, s); 328 while (dx) { 329 if (dx & shift) { 330 ZShiftRegion(r, -(int)shift); 331 ZOpRegion(r, s, r); 332 dx -= shift; 333 if (!dx) break; 334 } 335 ZCopyRegion(s, t); 336 ZShiftRegion(s, -(int)shift); 337 ZOpRegion(s, t, s); 338 shift <<= 1; 339 } 340 } 341 342 #undef ZOpRegion 343 #undef ZShiftRegion 344 #undef ZCopyRegion 345 346 int 347 XShrinkRegion( 348 BRegion* r, 349 int dx, int dy) 350 { 351 BRegion* s; 352 BRegion* t; 353 int grow; 354 355 if (!dx && !dy) return 0; 356 if ((! (s = CreateRegion())) || (! (t = CreateRegion()))) return 0; 357 if ((grow = (dx < 0))) dx = -dx; 358 if (dx) Compress(r, s, t, (unsigned) 2*dx, true, grow); 359 if ((grow = (dy < 0))) dy = -dy; 360 if (dy) Compress(r, s, t, (unsigned) 2*dy, false, grow); 361 XOffsetRegion(r, dx, dy); 362 DestroyRegion(s); 363 DestroyRegion(t); 364 return 0; 365 } 366 367 #ifdef notdef 368 /*********************************************************** 369 * Bop down the array of fData until we have passed 370 * scanline y. fCount is the fDataSize of the array. 371 ***********************************************************/ 372 373 static clipping_rect* 374 IndexRects( 375 register clipping_rect *rect, 376 register int rectCount, 377 register int y) 378 { 379 while ((rectCount--) && (rect->bottom <= y)) 380 rect++; 381 return(rect); 382 } 383 #endif 384 #endif // 0 385 386 /*====================================================================== 387 * BRegion* Intersection 388 *====================================================================*/ 389 /*- 390 *----------------------------------------------------------------------- 391 * miIntersectO -- 392 * Handle an overlapping band for miIntersect. 393 * 394 * Results: 395 * None. 396 * 397 * Side Effects: 398 * Rectangles may be added to the region. 399 * 400 *----------------------------------------------------------------------- 401 */ 402 int 403 BRegion::Support::miIntersectO ( 404 BRegion* pReg, 405 clipping_rect* r1, 406 clipping_rect* r1End, 407 clipping_rect* r2, 408 clipping_rect* r2End, 409 int top, 410 int bottom) 411 { 412 int left; 413 int right; 414 clipping_rect* pNextRect; 415 416 pNextRect = &pReg->fData[pReg->fCount]; 417 418 while ((r1 != r1End) && (r2 != r2End)) 419 { 420 left = max_c(r1->left,r2->left); 421 right = min_c(r1->right,r2->right); 422 423 /* 424 * If there's any overlap between the two rectangles, add that 425 * overlap to the new region. 426 * There's no need to check for subsumption because the only way 427 * such a need could arise is if some region has two rectangles 428 * right next to each other. Since that should never happen... 429 */ 430 if (left < right) 431 { 432 assert(top<bottom); 433 434 MEMCHECK(pReg, pNextRect, pReg->fData); 435 pNextRect->left = left; 436 pNextRect->top = top; 437 pNextRect->right = right; 438 pNextRect->bottom = bottom; 439 pReg->fCount += 1; 440 pNextRect++; 441 assert(pReg->fCount <= pReg->fDataSize); 442 } 443 444 /* 445 * Need to advance the pointers. Shift the one that extends 446 * to the right the least, since the other still has a chance to 447 * overlap with that region's next rectangle, if you see what I mean. 448 */ 449 if (r1->right < r2->right) 450 { 451 r1++; 452 } 453 else if (r2->right < r1->right) 454 { 455 r2++; 456 } 457 else 458 { 459 r1++; 460 r2++; 461 } 462 } 463 return 0; /* lint */ 464 } 465 466 int 467 BRegion::Support::XIntersectRegion( 468 const BRegion* reg1, 469 const BRegion* reg2, /* source regions */ 470 BRegion* newReg) /* destination BRegion* */ 471 { 472 /* check for trivial reject */ 473 if ( (!(reg1->fCount)) || (!(reg2->fCount)) || 474 (!EXTENTCHECK(®1->fBounds, ®2->fBounds))) 475 newReg->fCount = 0; 476 else 477 miRegionOp (newReg, reg1, reg2, 478 miIntersectO, NULL, NULL); 479 480 /* 481 * Can't alter newReg's fBounds before we call miRegionOp because 482 * it might be one of the source regions and miRegionOp depends 483 * on the fBounds of those regions being the same. Besides, this 484 * way there's no checking against rectangles that will be nuked 485 * due to coalescing, so we have to examine fewer rectangles. 486 */ 487 miSetExtents(newReg); 488 return 1; 489 } 490 491 void 492 BRegion::Support::miRegionCopy( 493 BRegion* dstrgn, 494 const BRegion* rgn) 495 496 { 497 *dstrgn = *rgn; 498 } 499 500 #if 0 501 #ifdef notdef 502 503 /* 504 * combinRegs(newReg, reg1, reg2) 505 * if one region is above or below the other. 506 */ 507 508 static void 509 combineRegs( 510 register BRegion* newReg, 511 BRegion* reg1, 512 BRegion* reg2) 513 { 514 register BRegion* tempReg; 515 register clipping_rect *rects_; 516 register clipping_rect *rects1; 517 register clipping_rect *rects2; 518 register int total; 519 520 rects1 = reg1->fData; 521 rects2 = reg2->fData; 522 523 total = reg1->fCount + reg2->fCount; 524 if (! (tempReg = CreateRegion())) 525 return; 526 tempReg->fDataSize = total; 527 /* region 1 is below region 2 */ 528 if (reg1->fBounds.top > reg2->fBounds.top) 529 { 530 miRegionCopy(tempReg, reg2); 531 rects_ = &tempReg->fData[tempReg->fCount]; 532 total -= tempReg->fCount; 533 while (total--) 534 *rects_++ = *rects1++; 535 } 536 else 537 { 538 miRegionCopy(tempReg, reg1); 539 rects_ = &tempReg->fData[tempReg->fCount]; 540 total -= tempReg->fCount; 541 while (total--) 542 *rects_++ = *rects2++; 543 } 544 tempReg->fBounds = reg1->fBounds; 545 tempReg->fCount = reg1->fCount + reg2->fCount; 546 EXTENTS(®2->fBounds, tempReg); 547 miRegionCopy(newReg, tempReg); 548 549 DestroyRegion(tempReg); 550 } 551 552 /* 553 * QuickCheck checks to see if it does not have to go through all the 554 * the ugly code for the region call. It returns 1 if it did all 555 * the work for Union, otherwise 0 - still work to be done. 556 */ 557 558 static int 559 QuickCheck(BRegion* newReg, BRegion* reg1, BRegion* reg2) 560 { 561 562 /* if unioning with itself or no fData to union with */ 563 if ( (reg1 == reg2) || (!(reg1->fCount)) ) 564 { 565 miRegionCopy(newReg, reg2); 566 return true; 567 } 568 569 /* if nothing to union */ 570 if (!(reg2->fCount)) 571 { 572 miRegionCopy(newReg, reg1); 573 return true; 574 } 575 576 /* could put an extent check to see if add above or below */ 577 578 if ((reg1->fBounds.top >= reg2->fBounds.bottom) || 579 (reg2->fBounds.top >= reg1->fBounds.bottom) ) 580 { 581 combineRegs(newReg, reg1, reg2); 582 return true; 583 } 584 return false; 585 } 586 587 /* TopRects(fData, reg1, reg2) 588 * N.B. We now assume that reg1 and reg2 intersect. Therefore we are 589 * NOT checking in the two while loops for stepping off the end of the 590 * region. 591 */ 592 593 static int 594 TopRects( 595 register BRegion* newReg, 596 register clipping_rect *rects_, 597 register BRegion* reg1, 598 register BRegion* reg2, 599 clipping_rect *FirstRect) 600 { 601 register clipping_rect *tempRects; 602 603 /* need to add some fData from region 1 */ 604 if (reg1->fBounds.top < reg2->fBounds.top) 605 { 606 tempRects = reg1->fData; 607 while(tempRects->top < reg2->fBounds.top) 608 { 609 MEMCHECK(newReg, rects_, FirstRect); 610 ADDRECTNOX(newReg,rects_, tempRects->left, tempRects->top, 611 tempRects->right, min_c(tempRects->bottom, reg2->fBounds.top)); 612 tempRects++; 613 } 614 } 615 /* need to add some fData from region 2 */ 616 if (reg2->fBounds.top < reg1->fBounds.top) 617 { 618 tempRects = reg2->fData; 619 while (tempRects->top < reg1->fBounds.top) 620 { 621 MEMCHECK(newReg, rects_, FirstRect); 622 ADDRECTNOX(newReg, rects_, tempRects->left,tempRects->top, 623 tempRects->right, min_c(tempRects->bottom, reg1->fBounds.top)); 624 tempRects++; 625 } 626 } 627 return 1; 628 } 629 #endif // notdef 630 #endif // 0 631 632 /*====================================================================== 633 * Generic BRegion* Operator 634 *====================================================================*/ 635 636 /*- 637 *----------------------------------------------------------------------- 638 * miCoalesce -- 639 * Attempt to merge the boxes in the current band with those in the 640 * previous one. Used only by miRegionOp. 641 * 642 * Results: 643 * The new index for the previous band. 644 * 645 * Side Effects: 646 * If coalescing takes place: 647 * - rectangles in the previous band will have their bottom fields 648 * altered. 649 * - pReg->fCount will be decreased. 650 * 651 *----------------------------------------------------------------------- 652 */ 653 int 654 BRegion::Support::miCoalesce( 655 BRegion* pReg, /* BRegion* to coalesce */ 656 int prevStart, /* Index of start of previous band */ 657 int curStart) /* Index of start of current band */ 658 { 659 clipping_rect* pPrevBox; /* Current box in previous band */ 660 clipping_rect* pCurBox; /* Current box in current band */ 661 clipping_rect* pRegEnd; /* End of region */ 662 int curNumRects; /* Number of rectangles in current 663 * band */ 664 int prevNumRects; /* Number of rectangles in previous 665 * band */ 666 int bandY1; /* Y1 coordinate for current band */ 667 668 pRegEnd = &pReg->fData[pReg->fCount]; 669 670 pPrevBox = &pReg->fData[prevStart]; 671 prevNumRects = curStart - prevStart; 672 673 /* 674 * Figure out how many rectangles are in the current band. Have to do 675 * this because multiple bands could have been added in miRegionOp 676 * at the end when one region has been exhausted. 677 */ 678 pCurBox = &pReg->fData[curStart]; 679 bandY1 = pCurBox->top; 680 for (curNumRects = 0; 681 (pCurBox != pRegEnd) && (pCurBox->top == bandY1); 682 curNumRects++) 683 { 684 pCurBox++; 685 } 686 687 if (pCurBox != pRegEnd) 688 { 689 /* 690 * If more than one band was added, we have to find the start 691 * of the last band added so the next coalescing job can start 692 * at the right place... (given when multiple bands are added, 693 * this may be pointless -- see above). 694 */ 695 pRegEnd--; 696 while (pRegEnd[-1].top == pRegEnd->top) 697 { 698 pRegEnd--; 699 } 700 curStart = pRegEnd - pReg->fData; 701 pRegEnd = pReg->fData + pReg->fCount; 702 } 703 704 if ((curNumRects == prevNumRects) && (curNumRects != 0)) { 705 pCurBox -= curNumRects; 706 /* 707 * The bands may only be coalesced if the bottom of the previous 708 * matches the top scanline of the current. 709 */ 710 if (pPrevBox->bottom == pCurBox->top) 711 { 712 /* 713 * Make sure the bands have boxes in the same places. This 714 * assumes that boxes have been added in such a way that they 715 * cover the most area possible. I.e. two boxes in a band must 716 * have some horizontal space between them. 717 */ 718 do 719 { 720 if ((pPrevBox->left != pCurBox->left) || 721 (pPrevBox->right != pCurBox->right)) 722 { 723 /* 724 * The bands don't line up so they can't be coalesced. 725 */ 726 return (curStart); 727 } 728 pPrevBox++; 729 pCurBox++; 730 prevNumRects -= 1; 731 } while (prevNumRects != 0); 732 733 pReg->fCount -= curNumRects; 734 pCurBox -= curNumRects; 735 pPrevBox -= curNumRects; 736 737 /* 738 * The bands may be merged, so set the bottom y of each box 739 * in the previous band to that of the corresponding box in 740 * the current band. 741 */ 742 do 743 { 744 pPrevBox->bottom = pCurBox->bottom; 745 pPrevBox++; 746 pCurBox++; 747 curNumRects -= 1; 748 } while (curNumRects != 0); 749 750 /* 751 * If only one band was added to the region, we have to backup 752 * curStart to the start of the previous band. 753 * 754 * If more than one band was added to the region, copy the 755 * other bands down. The assumption here is that the other bands 756 * came from the same region as the current one and no further 757 * coalescing can be done on them since it's all been done 758 * already... curStart is already in the right place. 759 */ 760 if (pCurBox == pRegEnd) 761 { 762 curStart = prevStart; 763 } 764 else 765 { 766 do 767 { 768 *pPrevBox++ = *pCurBox++; 769 } while (pCurBox != pRegEnd); 770 } 771 772 } 773 } 774 return (curStart); 775 } 776 777 /*- 778 *----------------------------------------------------------------------- 779 * miRegionOp -- 780 * Apply an operation to two regions. Called by miUnion, miInverse, 781 * miSubtract, miIntersect... 782 * 783 * Results: 784 * None. 785 * 786 * Side Effects: 787 * The new region is overwritten. 788 * 789 * Notes: 790 * The idea behind this function is to view the two regions as sets. 791 * Together they cover a rectangle of area that this function divides 792 * into horizontal bands where points are covered only by one region 793 * or by both. For the first case, the nonOverlapFunc is called with 794 * each the band and the band's upper and lower fBounds. For the 795 * second, the overlapFunc is called to process the entire band. It 796 * is responsible for clipping the rectangles in the band, though 797 * this function provides the boundaries. 798 * At the end of each band, the new region is coalesced, if possible, 799 * to reduce the number of rectangles in the region. 800 * 801 *----------------------------------------------------------------------- 802 */ 803 void 804 BRegion::Support::miRegionOp( 805 BRegion* newReg, /* Place to store result */ 806 const BRegion* reg1, /* First region in operation */ 807 const BRegion* reg2, /* 2d region in operation */ 808 int (*overlapFunc)( 809 BRegion* pReg, 810 clipping_rect* r1, 811 clipping_rect* r1End, 812 clipping_rect* r2, 813 clipping_rect* r2End, 814 int top, 815 int bottom), /* Function to call for over- 816 * lapping bands */ 817 int (*nonOverlap1Func)( 818 BRegion* pReg, 819 clipping_rect* r, 820 clipping_rect* rEnd, 821 int top, 822 int bottom), /* Function to call for non- 823 * overlapping bands in region 824 * 1 */ 825 int (*nonOverlap2Func)( 826 BRegion* pReg, 827 clipping_rect* r, 828 clipping_rect* rEnd, 829 int top, 830 int bottom)) /* Function to call for non- 831 * overlapping bands in region 832 * 2 */ 833 { 834 clipping_rect* r1; /* Pointer into first region */ 835 clipping_rect* r2; /* Pointer into 2d region */ 836 clipping_rect* r1End; /* End of 1st region */ 837 clipping_rect* r2End; /* End of 2d region */ 838 int ybot; /* Bottom of intersection */ 839 int ytop; /* Top of intersection */ 840 // clipping_rect* oldRects; /* Old fData for newReg */ 841 int prevBand; /* Index of start of 842 * previous band in newReg */ 843 int curBand; /* Index of start of current 844 * band in newReg */ 845 clipping_rect* r1BandEnd; /* End of current band in r1 */ 846 clipping_rect* r2BandEnd; /* End of current band in r2 */ 847 int top; /* Top of non-overlapping 848 * band */ 849 int bot; /* Bottom of non-overlapping 850 * band */ 851 852 /* 853 * Initialization: 854 * set r1, r2, r1End and r2End appropriately, preserve the important 855 * parts of the destination region until the end in case it's one of 856 * the two source regions, then mark the "new" region empty, allocating 857 * another array of rectangles for it to use. 858 */ 859 r1 = reg1->fData; 860 r2 = reg2->fData; 861 r1End = r1 + reg1->fCount; 862 r2End = r2 + reg2->fCount; 863 864 // oldRects = newReg->fData; 865 866 EMPTY_REGION(newReg); 867 868 /* 869 * Allocate a reasonable number of rectangles for the new region. The idea 870 * is to allocate enough so the individual functions don't need to 871 * reallocate and copy the array, which is time consuming, yet we don't 872 * have to worry about using too much memory. I hope to be able to 873 * nuke the realloc() at the end of this function eventually. 874 */ 875 if (!newReg->_SetSize(max_c(reg1->fCount,reg2->fCount) * 2)) { 876 return; 877 } 878 879 /* 880 * Initialize ybot and ytop. 881 * In the upcoming loop, ybot and ytop serve different functions depending 882 * on whether the band being handled is an overlapping or non-overlapping 883 * band. 884 * In the case of a non-overlapping band (only one of the regions 885 * has points in the band), ybot is the bottom of the most recent 886 * intersection and thus clips the top of the rectangles in that band. 887 * ytop is the top of the next intersection between the two regions and 888 * serves to clip the bottom of the rectangles in the current band. 889 * For an overlapping band (where the two regions intersect), ytop clips 890 * the top of the rectangles of both regions and ybot clips the bottoms. 891 */ 892 if (reg1->fBounds.top < reg2->fBounds.top) 893 ybot = reg1->fBounds.top; 894 else 895 ybot = reg2->fBounds.top; 896 897 /* 898 * prevBand serves to mark the start of the previous band so rectangles 899 * can be coalesced into larger rectangles. qv. miCoalesce, above. 900 * In the beginning, there is no previous band, so prevBand == curBand 901 * (curBand is set later on, of course, but the first band will always 902 * start at index 0). prevBand and curBand must be indices because of 903 * the possible expansion, and resultant moving, of the new region's 904 * array of rectangles. 905 */ 906 prevBand = 0; 907 908 do 909 { 910 curBand = newReg->fCount; 911 912 /* 913 * This algorithm proceeds one source-band (as opposed to a 914 * destination band, which is determined by where the two regions 915 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the 916 * rectangle after the last one in the current band for their 917 * respective regions. 918 */ 919 r1BandEnd = r1; 920 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) 921 { 922 r1BandEnd++; 923 } 924 925 r2BandEnd = r2; 926 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) 927 { 928 r2BandEnd++; 929 } 930 931 /* 932 * First handle the band that doesn't intersect, if any. 933 * 934 * Note that attention is restricted to one band in the 935 * non-intersecting region at once, so if a region has n 936 * bands between the current position and the next place it overlaps 937 * the other, this entire loop will be passed through n times. 938 */ 939 if (r1->top < r2->top) 940 { 941 top = max_c(r1->top,ybot); 942 bot = min_c(r1->bottom,r2->top); 943 944 if ((top != bot) && (nonOverlap1Func != NULL)) 945 { 946 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot); 947 } 948 949 ytop = r2->top; 950 } 951 else if (r2->top < r1->top) 952 { 953 top = max_c(r2->top,ybot); 954 bot = min_c(r2->bottom,r1->top); 955 956 if ((top != bot) && (nonOverlap2Func != NULL)) 957 { 958 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot); 959 } 960 961 ytop = r1->top; 962 } 963 else 964 { 965 ytop = r1->top; 966 } 967 968 /* 969 * If any rectangles got added to the region, try and coalesce them 970 * with rectangles from the previous band. Note we could just do 971 * this test in miCoalesce, but some machines incur a not 972 * inconsiderable cost for function calls, so... 973 */ 974 if (newReg->fCount != curBand) 975 { 976 prevBand = miCoalesce (newReg, prevBand, curBand); 977 } 978 979 /* 980 * Now see if we've hit an intersecting band. The two bands only 981 * intersect if ybot > ytop 982 */ 983 ybot = min_c(r1->bottom, r2->bottom); 984 curBand = newReg->fCount; 985 if (ybot > ytop) 986 { 987 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot); 988 989 } 990 991 if (newReg->fCount != curBand) 992 { 993 prevBand = miCoalesce (newReg, prevBand, curBand); 994 } 995 996 /* 997 * If we've finished with a band (bottom == ybot) we skip forward 998 * in the region to the next band. 999 */ 1000 if (r1->bottom == ybot) 1001 { 1002 r1 = r1BandEnd; 1003 } 1004 if (r2->bottom == ybot) 1005 { 1006 r2 = r2BandEnd; 1007 } 1008 } while ((r1 != r1End) && (r2 != r2End)); 1009 1010 /* 1011 * Deal with whichever region still has rectangles left. 1012 */ 1013 curBand = newReg->fCount; 1014 if (r1 != r1End) 1015 { 1016 if (nonOverlap1Func != NULL) 1017 { 1018 do 1019 { 1020 r1BandEnd = r1; 1021 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) 1022 { 1023 r1BandEnd++; 1024 } 1025 (* nonOverlap1Func) (newReg, r1, r1BandEnd, 1026 max_c(r1->top,ybot), r1->bottom); 1027 r1 = r1BandEnd; 1028 } while (r1 != r1End); 1029 } 1030 } 1031 else if ((r2 != r2End) && (nonOverlap2Func != NULL)) 1032 { 1033 do 1034 { 1035 r2BandEnd = r2; 1036 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) 1037 { 1038 r2BandEnd++; 1039 } 1040 (* nonOverlap2Func) (newReg, r2, r2BandEnd, 1041 max_c(r2->top,ybot), r2->bottom); 1042 r2 = r2BandEnd; 1043 } while (r2 != r2End); 1044 } 1045 1046 if (newReg->fCount != curBand) 1047 { 1048 (void) miCoalesce (newReg, prevBand, curBand); 1049 } 1050 1051 /* 1052 * A bit of cleanup. To keep regions from growing without bound, 1053 * we shrink the array of rectangles to match the new number of 1054 * rectangles in the region. This never goes to 0, however... 1055 * 1056 * Only do this stuff if the number of rectangles allocated is more than 1057 * twice the number of rectangles in the region (a simple optimization...). 1058 */ 1059 // if (newReg->fCount < (newReg->fDataSize >> 1)) 1060 // { 1061 // if (REGION_NOT_EMPTY(newReg)) 1062 // { 1063 // clipping_rect* prev_rects = newReg->fData; 1064 // newReg->fDataSize = newReg->fCount; 1065 // newReg->fData = (clipping_rect*) realloc ((char *) newReg->fData, 1066 // (unsigned) (sizeof(clipping_rect) * newReg->fDataSize)); 1067 // if (! newReg->fData) 1068 // newReg->fData = prev_rects; 1069 // } 1070 // else 1071 // { 1072 // /* 1073 // * No point in doing the extra work involved in an realloc if 1074 // * the region is empty 1075 // */ 1076 // newReg->fDataSize = 1; 1077 // free((char *) newReg->fData); 1078 // newReg->fData = (clipping_rect*) malloc(sizeof(clipping_rect)); 1079 // } 1080 // } 1081 // free ((char *) oldRects); 1082 return; 1083 } 1084 1085 1086 /*====================================================================== 1087 * BRegion* Union 1088 *====================================================================*/ 1089 1090 /*- 1091 *----------------------------------------------------------------------- 1092 * miUnionNonO -- 1093 * Handle a non-overlapping band for the union operation. Just 1094 * Adds the rectangles into the region. Doesn't have to check for 1095 * subsumption or anything. 1096 * 1097 * Results: 1098 * None. 1099 * 1100 * Side Effects: 1101 * pReg->fCount is incremented and the final rectangles overwritten 1102 * with the rectangles we're passed. 1103 * 1104 *----------------------------------------------------------------------- 1105 */ 1106 int 1107 BRegion::Support::miUnionNonO(BRegion* pReg, 1108 clipping_rect* r, clipping_rect* rEnd, 1109 int top, int bottom) 1110 { 1111 clipping_rect* pNextRect = &pReg->fData[pReg->fCount]; 1112 1113 assert(top < bottom); 1114 1115 while (r != rEnd) { 1116 assert(r->left < r->right); 1117 MEMCHECK(pReg, pNextRect, pReg->fData); 1118 pNextRect->left = r->left; 1119 pNextRect->top = top; 1120 pNextRect->right = r->right; 1121 pNextRect->bottom = bottom; 1122 pReg->fCount += 1; 1123 pNextRect++; 1124 1125 assert(pReg->fCount<=pReg->fDataSize); 1126 r++; 1127 } 1128 return 0; 1129 } 1130 1131 1132 /*- 1133 *----------------------------------------------------------------------- 1134 * miUnionO -- 1135 * Handle an overlapping band for the union operation. Picks the 1136 * left-most rectangle each time and merges it into the region. 1137 * 1138 * Results: 1139 * None. 1140 * 1141 * Side Effects: 1142 * Rectangles are overwritten in pReg->fData and pReg->fCount will 1143 * be changed. 1144 * 1145 *----------------------------------------------------------------------- 1146 */ 1147 1148 int 1149 BRegion::Support::miUnionO ( 1150 BRegion* pReg, 1151 clipping_rect* r1, 1152 clipping_rect* r1End, 1153 clipping_rect* r2, 1154 clipping_rect* r2End, 1155 int top, 1156 int bottom) 1157 { 1158 clipping_rect* pNextRect; 1159 1160 pNextRect = &pReg->fData[pReg->fCount]; 1161 1162 #define MERGERECT(r) \ 1163 if ((pReg->fCount != 0) && \ 1164 (pNextRect[-1].top == top) && \ 1165 (pNextRect[-1].bottom == bottom) && \ 1166 (pNextRect[-1].right >= r->left)) \ 1167 { \ 1168 if (pNextRect[-1].right < r->right) \ 1169 { \ 1170 pNextRect[-1].right = r->right; \ 1171 assert(pNextRect[-1].left<pNextRect[-1].right); \ 1172 } \ 1173 } \ 1174 else \ 1175 { \ 1176 MEMCHECK(pReg, pNextRect, pReg->fData); \ 1177 pNextRect->top = top; \ 1178 pNextRect->bottom = bottom; \ 1179 pNextRect->left = r->left; \ 1180 pNextRect->right = r->right; \ 1181 pReg->fCount += 1; \ 1182 pNextRect += 1; \ 1183 } \ 1184 assert(pReg->fCount<=pReg->fDataSize);\ 1185 r++; 1186 1187 assert (top<bottom); 1188 while ((r1 != r1End) && (r2 != r2End)) 1189 { 1190 if (r1->left < r2->left) 1191 { 1192 MERGERECT(r1); 1193 } 1194 else 1195 { 1196 MERGERECT(r2); 1197 } 1198 } 1199 1200 if (r1 != r1End) 1201 { 1202 do 1203 { 1204 MERGERECT(r1); 1205 } while (r1 != r1End); 1206 } 1207 else while (r2 != r2End) 1208 { 1209 MERGERECT(r2); 1210 } 1211 return 0; /* lint */ 1212 } 1213 1214 int 1215 BRegion::Support::XUnionRegion( 1216 const BRegion* reg1, 1217 const BRegion* reg2, /* source regions */ 1218 BRegion* newReg) /* destination BRegion* */ 1219 { 1220 /* checks all the simple cases */ 1221 1222 /* 1223 * BRegion* 1 and 2 are the same or region 1 is empty 1224 */ 1225 if ( (reg1 == reg2) || (!(reg1->fCount)) ) 1226 { 1227 if (newReg != reg2) 1228 miRegionCopy(newReg, reg2); 1229 return 1; 1230 } 1231 1232 /* 1233 * if nothing to union (region 2 empty) 1234 */ 1235 if (!(reg2->fCount)) 1236 { 1237 if (newReg != reg1) 1238 miRegionCopy(newReg, reg1); 1239 return 1; 1240 } 1241 1242 /* 1243 * BRegion* 1 completely subsumes region 2 1244 */ 1245 if ((reg1->fCount == 1) && 1246 (reg1->fBounds.left <= reg2->fBounds.left) && 1247 (reg1->fBounds.top <= reg2->fBounds.top) && 1248 (reg1->fBounds.right >= reg2->fBounds.right) && 1249 (reg1->fBounds.bottom >= reg2->fBounds.bottom)) 1250 { 1251 if (newReg != reg1) 1252 miRegionCopy(newReg, reg1); 1253 return 1; 1254 } 1255 1256 /* 1257 * BRegion* 2 completely subsumes region 1 1258 */ 1259 if ((reg2->fCount == 1) && 1260 (reg2->fBounds.left <= reg1->fBounds.left) && 1261 (reg2->fBounds.top <= reg1->fBounds.top) && 1262 (reg2->fBounds.right >= reg1->fBounds.right) && 1263 (reg2->fBounds.bottom >= reg1->fBounds.bottom)) 1264 { 1265 if (newReg != reg2) 1266 miRegionCopy(newReg, reg2); 1267 return 1; 1268 } 1269 1270 miRegionOp (newReg, reg1, reg2, miUnionO, 1271 miUnionNonO, miUnionNonO); 1272 1273 newReg->fBounds.left = min_c(reg1->fBounds.left, reg2->fBounds.left); 1274 newReg->fBounds.top = min_c(reg1->fBounds.top, reg2->fBounds.top); 1275 newReg->fBounds.right = max_c(reg1->fBounds.right, reg2->fBounds.right); 1276 newReg->fBounds.bottom = max_c(reg1->fBounds.bottom, reg2->fBounds.bottom); 1277 1278 return 1; 1279 } 1280 1281 1282 /*====================================================================== 1283 * BRegion* Subtraction 1284 *====================================================================*/ 1285 1286 /*- 1287 *----------------------------------------------------------------------- 1288 * miSubtractNonO -- 1289 * Deal with non-overlapping band for subtraction. Any parts from 1290 * region 2 we discard. Anything from region 1 we add to the region. 1291 * 1292 * Results: 1293 * None. 1294 * 1295 * Side Effects: 1296 * pReg may be affected. 1297 * 1298 *----------------------------------------------------------------------- 1299 */ 1300 int 1301 BRegion::Support::miSubtractNonO1 ( 1302 BRegion* pReg, 1303 clipping_rect* r, 1304 clipping_rect* rEnd, 1305 int top, 1306 int bottom) 1307 { 1308 clipping_rect* pNextRect; 1309 1310 pNextRect = &pReg->fData[pReg->fCount]; 1311 1312 assert(top<bottom); 1313 1314 while (r != rEnd) 1315 { 1316 assert(r->left<r->right); 1317 MEMCHECK(pReg, pNextRect, pReg->fData); 1318 pNextRect->left = r->left; 1319 pNextRect->top = top; 1320 pNextRect->right = r->right; 1321 pNextRect->bottom = bottom; 1322 pReg->fCount += 1; 1323 pNextRect++; 1324 1325 assert(pReg->fCount <= pReg->fDataSize); 1326 1327 r++; 1328 } 1329 return 0; /* lint */ 1330 } 1331 1332 /*- 1333 *----------------------------------------------------------------------- 1334 * miSubtractO -- 1335 * Overlapping band subtraction. left is the left-most point not yet 1336 * checked. 1337 * 1338 * Results: 1339 * None. 1340 * 1341 * Side Effects: 1342 * pReg may have rectangles added to it. 1343 * 1344 *----------------------------------------------------------------------- 1345 */ 1346 int 1347 BRegion::Support::miSubtractO( 1348 BRegion* pReg, 1349 clipping_rect* r1, 1350 clipping_rect* r1End, 1351 clipping_rect* r2, 1352 clipping_rect* r2End, 1353 int top, 1354 int bottom) 1355 { 1356 clipping_rect* pNextRect; 1357 int left; 1358 1359 left = r1->left; 1360 1361 assert(top<bottom); 1362 pNextRect = &pReg->fData[pReg->fCount]; 1363 1364 while ((r1 != r1End) && (r2 != r2End)) 1365 { 1366 if (r2->right <= left) 1367 { 1368 /* 1369 * Subtrahend missed the boat: go to next subtrahend. 1370 */ 1371 r2++; 1372 } 1373 else if (r2->left <= left) 1374 { 1375 /* 1376 * Subtrahend preceeds minuend: nuke left edge of minuend. 1377 */ 1378 left = r2->right; 1379 if (left >= r1->right) 1380 { 1381 /* 1382 * Minuend completely covered: advance to next minuend and 1383 * reset left fence to edge of new minuend. 1384 */ 1385 r1++; 1386 if (r1 != r1End) 1387 left = r1->left; 1388 } 1389 else 1390 { 1391 /* 1392 * Subtrahend now used up since it doesn't extend beyond 1393 * minuend 1394 */ 1395 r2++; 1396 } 1397 } 1398 else if (r2->left < r1->right) 1399 { 1400 /* 1401 * Left part of subtrahend covers part of minuend: add uncovered 1402 * part of minuend to region and skip to next subtrahend. 1403 */ 1404 assert(left<r2->left); 1405 MEMCHECK(pReg, pNextRect, pReg->fData); 1406 pNextRect->left = left; 1407 pNextRect->top = top; 1408 pNextRect->right = r2->left; 1409 pNextRect->bottom = bottom; 1410 pReg->fCount += 1; 1411 pNextRect++; 1412 1413 assert(pReg->fCount<=pReg->fDataSize); 1414 1415 left = r2->right; 1416 if (left >= r1->right) 1417 { 1418 /* 1419 * Minuend used up: advance to new... 1420 */ 1421 r1++; 1422 if (r1 != r1End) 1423 left = r1->left; 1424 } 1425 else 1426 { 1427 /* 1428 * Subtrahend used up 1429 */ 1430 r2++; 1431 } 1432 } 1433 else 1434 { 1435 /* 1436 * Minuend used up: add any remaining piece before advancing. 1437 */ 1438 if (r1->right > left) 1439 { 1440 MEMCHECK(pReg, pNextRect, pReg->fData); 1441 pNextRect->left = left; 1442 pNextRect->top = top; 1443 pNextRect->right = r1->right; 1444 pNextRect->bottom = bottom; 1445 pReg->fCount += 1; 1446 pNextRect++; 1447 assert(pReg->fCount<=pReg->fDataSize); 1448 } 1449 r1++; 1450 if (r1 != r1End) 1451 left = r1->left; 1452 } 1453 } 1454 1455 /* 1456 * Add remaining minuend rectangles to region. 1457 */ 1458 while (r1 != r1End) 1459 { 1460 assert(left<r1->right); 1461 MEMCHECK(pReg, pNextRect, pReg->fData); 1462 pNextRect->left = left; 1463 pNextRect->top = top; 1464 pNextRect->right = r1->right; 1465 pNextRect->bottom = bottom; 1466 pReg->fCount += 1; 1467 pNextRect++; 1468 1469 assert(pReg->fCount<=pReg->fDataSize); 1470 1471 r1++; 1472 if (r1 != r1End) 1473 { 1474 left = r1->left; 1475 } 1476 } 1477 return 0; /* lint */ 1478 } 1479 1480 /*- 1481 *----------------------------------------------------------------------- 1482 * miSubtract -- 1483 * Subtract regS from regM and leave the result in regD. 1484 * S stands for subtrahend, M for minuend and D for difference. 1485 * 1486 * Results: 1487 * true. 1488 * 1489 * Side Effects: 1490 * regD is overwritten. 1491 * 1492 *----------------------------------------------------------------------- 1493 */ 1494 1495 int 1496 BRegion::Support::XSubtractRegion( 1497 const BRegion* regM, 1498 const BRegion* regS, 1499 BRegion* regD) 1500 { 1501 /* check for trivial reject */ 1502 if ( (!(regM->fCount)) || (!(regS->fCount)) || 1503 (!EXTENTCHECK(®M->fBounds, ®S->fBounds)) ) 1504 { 1505 miRegionCopy(regD, regM); 1506 return 1; 1507 } 1508 1509 miRegionOp (regD, regM, regS, miSubtractO, 1510 miSubtractNonO1, NULL); 1511 1512 /* 1513 * Can't alter newReg's fBounds before we call miRegionOp because 1514 * it might be one of the source regions and miRegionOp depends 1515 * on the fBounds of those regions being the unaltered. Besides, this 1516 * way there's no checking against rectangles that will be nuked 1517 * due to coalescing, so we have to examine fewer rectangles. 1518 */ 1519 miSetExtents (regD); 1520 return 1; 1521 } 1522 1523 int 1524 BRegion::Support::XXorRegion(const BRegion* sra, const BRegion* srb, 1525 BRegion* dr) 1526 { 1527 BRegion* tra = NULL; 1528 BRegion* trb = NULL; 1529 1530 if ((! (tra = CreateRegion())) || (! (trb = CreateRegion()))) 1531 { 1532 DestroyRegion(tra); 1533 DestroyRegion(trb); 1534 return 0; 1535 } 1536 (void) XSubtractRegion(sra,srb,tra); 1537 (void) XSubtractRegion(srb,sra,trb); 1538 (void) XUnionRegion(tra,trb,dr); 1539 DestroyRegion(tra); 1540 DestroyRegion(trb); 1541 return 0; 1542 } 1543 1544 1545 bool 1546 BRegion::Support::XPointInRegion( 1547 const BRegion* pRegion, 1548 int x, int y) 1549 { 1550 // TODO: binary search by "y"! 1551 int i; 1552 1553 if (pRegion->fCount == 0) 1554 return false; 1555 if (!INBOX(pRegion->fBounds, x, y)) 1556 return false; 1557 for (i=0; i<pRegion->fCount; i++) 1558 { 1559 if (INBOX (pRegion->fData[i], x, y)) 1560 return true; 1561 } 1562 return false; 1563 } 1564 1565 int 1566 BRegion::Support::XRectInRegion( 1567 const BRegion* region, 1568 const clipping_rect& rect) 1569 { 1570 clipping_rect* pbox; 1571 clipping_rect* pboxEnd; 1572 const clipping_rect* prect = ▭ 1573 bool partIn, partOut; 1574 1575 int rx = prect->left; 1576 int ry = prect->top; 1577 1578 /* this is (just) a useful optimization */ 1579 if ((region->fCount == 0) || !EXTENTCHECK(®ion->fBounds, prect)) 1580 return(RectangleOut); 1581 1582 partOut = false; 1583 partIn = false; 1584 1585 /* can stop when both partOut and partIn are true, or we reach prect->bottom */ 1586 for (pbox = region->fData, pboxEnd = pbox + region->fCount; 1587 pbox < pboxEnd; 1588 pbox++) 1589 { 1590 1591 if (pbox->bottom <= ry) 1592 continue; /* getting up to speed or skipping remainder of band */ 1593 1594 if (pbox->top > ry) 1595 { 1596 partOut = true; /* missed part of rectangle above */ 1597 if (partIn || (pbox->top >= prect->bottom)) 1598 break; 1599 ry = pbox->top; /* x guaranteed to be == prect->left */ 1600 } 1601 1602 if (pbox->right <= rx) 1603 continue; /* not far enough over yet */ 1604 1605 if (pbox->left > rx) 1606 { 1607 partOut = true; /* missed part of rectangle to left */ 1608 if (partIn) 1609 break; 1610 } 1611 1612 if (pbox->left < prect->right) 1613 { 1614 partIn = true; /* definitely overlap */ 1615 if (partOut) 1616 break; 1617 } 1618 1619 if (pbox->right >= prect->right) 1620 { 1621 ry = pbox->bottom; /* finished with this band */ 1622 if (ry >= prect->bottom) 1623 break; 1624 rx = prect->left; /* reset x out to left again */ 1625 } else 1626 { 1627 /* 1628 * Because boxes in a band are maximal width, if the first box 1629 * to overlap the rectangle doesn't completely cover it in that 1630 * band, the rectangle must be partially out, since some of it 1631 * will be uncovered in that band. partIn will have been set true 1632 * by now... 1633 */ 1634 break; 1635 } 1636 1637 } 1638 1639 return(partIn ? ((ry < prect->bottom) ? RectanglePart : RectangleIn) : 1640 RectangleOut); 1641 } 1642