lib/gdi/region.cpp

   1 #include <lib/gdi/erect.h>
   2 #include <lib/gdi/epoint.h>
   3 #include <lib/gdi/region.h>
   4 #include <lib/base/eerror.h>
   5
   6 #undef max
   7 #define max(a,b)  ((a) > (b) ? (a) : (b))
   8 #undef min
   9 #define min(a,b)  ((a) < (b) ? (a) : (b))
  10
  11
  12 /*
  13
  14         Region code.
  15
  16         A region is basically a list of rectangles. In this implementation,
  17         rectangles are ordered by their upper-left position, organized in bands.
  18
  19         this code stolen from miregion.c out of the X-Window system.
  20         for implementation details, look into their source.
  21         This code does all the ugly stuff.
  22
  23         Thanks go out to ryg, for explaining me this stuff.
  24
  25 */
  26
  27 gRegion::gRegion(const eRect &rect) : extends(rect)
  28 {
  29         if (rect.valid() && !rect.empty())
  30                 rects.push_back(rect);
  31 }
  32
  33 gRegion::gRegion() : extends(eRect::emptyRect())
  34 {
  35 }
  36
  37 gRegion::~gRegion()
  38 {
  39 }
  40
  41 int gRegion::do_coalesce(int prevStart, unsigned int curStart)
  42 {
  43                 // Figure out how many rectangles are in the band.
  44         unsigned int numRects = curStart - prevStart;
  45         ASSERT(numRects == rects.size() - curStart);
  46         if (!numRects)
  47                 return curStart;
  48         std::vector<eRect>::iterator prevBox = rects.begin() + prevStart;
  49         std::vector<eRect>::const_iterator  curBox = rects.begin() + curStart;
  50
  51                 // The bands may only be coalesced if the bottom of the previous
  52                 // matches the top scanline of the current.
  53         if (prevBox->y2 != curBox->y1)
  54                 return curStart;
  55
  56                 // Make sure the bands have boxes in the same places. This
  57                 // assumes that boxes have been added in such a way that they
  58                 // cover the most area possible. I.e. two boxes in a band must
  59                 // have some horizontal space between them.
  60
  61         int y2 = curBox->y2;
  62
  63         do {
  64                 if ((prevBox->x1 != curBox->x1) || (prevBox->x2 != curBox->x2))
  65                         return curStart;
  66                 prevBox++;
  67                 curBox++;
  68                 numRects--;
  69         } while ( numRects );
  70
  71                 // The bands may be merged, so set the bottom y of each box
  72                 // in the previous band to the bottom y of the current band.
  73         numRects = curStart - prevStart;
  74         rects.resize(rects.size() - numRects);
  75         do {
  76                 prevBox--;
  77                 prevBox->y2 = y2;
  78                 numRects--;
  79         } while (numRects);
  80         return prevStart;
  81 }
  82
  83 void gRegion::appendNonO(std::vector<eRect>::const_iterator r,
  84                         std::vector<eRect>::const_iterator rEnd, int y1, int y2)
  85 {
  86         int newRects = rEnd - r;
  87         ASSERT(y1 < y2);
  88         ASSERT(newRects != 0);
  89         rects.reserve(rects.size() + newRects);
  90         do {
  91                 ASSERT(r->x1 < r->x2);
  92                 rects.push_back(eRect(r->x1, y1, r->x2 - r->x1, y2 - y1));
  93                 r++;
  94         } while (r != rEnd);
  95 }
  96
  97 void gRegion::intersectO(
  98                 std::vector<eRect>::const_iterator r1,
  99                 std::vector<eRect>::const_iterator r1End,
 100                 std::vector<eRect>::const_iterator r2,
 101                 std::vector<eRect>::const_iterator r2End,
 102                 int y1, int y2,
 103                 int &overlap)
 104 {
 105         int x1, x2;
 106
 107         ASSERT(y1 < y2);
 108         ASSERT(r1 != r1End && r2 != r2End);
 109
 110         do {
 111                 x1 = max(r1->x1, r2->x1);
 112                 x2 = min(r1->x2, r2->x2);
 113
 114                 if (x1 < x2)
 115                         rects.push_back(eRect(x1, y1, x2 - x1, y2 - y1));
 116                 if (r1->x2 == x2)
 117                         r1++;
 118                 if (r2->x2 == x2)
 119                         r2++;
 120         } while ( (r1 != r1End) && (r2 != r2End));
 121 }
 122
 123 void gRegion::subtractO(
 124                 std::vector<eRect>::const_iterator r1,
 125                 std::vector<eRect>::const_iterator r1End,
 126                 std::vector<eRect>::const_iterator r2,
 127                 std::vector<eRect>::const_iterator r2End,
 128                 int y1, int y2,
 129                 int &overlap)
 130 {
 131         int x1;
 132         x1 = r1->x1;
 133
 134         ASSERT(y1<y2);
 135         ASSERT(r1 != r1End && r2 != r2End);
 136
 137         do {
 138                 if (r2->x2 <= x1)
 139                         ++r2;
 140                 else if (r2->x1 <= x1) {
 141                         x1 = r2->x2;
 142                         if (x1 >= r1->x2) {
 143                                 ++r1;
 144                                 if (r1 != r1End)
 145                                         x1 = r1->x1;
 146                         } else
 147                                 ++r2;
 148                 } else if (r2->x1 < r1->x2) {
 149                         ASSERT(x1<r2->x1);
 150                         rects.push_back(eRect(x1, y1, r2->x1 - x1, y2 - y1));
 151                         x1 = r2->x2;
 152                         if (x1 >= r1->x2) {
 153                                 ++r1;
 154                                 if (r1 != r1End)
 155                                         x1 = r1->x1;
 156                         } else
 157                                 ++r2;
 158                 } else
 159                 {
 160                         if (r1->x2 > x1)
 161                                 rects.push_back(eRect(x1, y1, r1->x2 - x1, y2 - y1));
 162                         ++r1;
 163                         if (r1 != r1End)
 164                                 x1 = r1->x1;
 165                 }
 166         } while ((r1 != r1End) && (r2 != r2End));
 167         while (r1 != r1End)
 168         {
 169                 ASSERT(x1<r1->x2);
 170                 rects.push_back(eRect(x1, y1, r1->x2 - x1, y2 - y1));
 171                 ++r1;
 172                 if (r1 != r1End)
 173                         x1 = r1->x1;
 174         }
 175 }
 176
 177 #define MERGERECT(r)                                        \
 178 {                                                           \
 179         if (r->x1 <= x2) {                                        \
 180                 /* Merge with current rectangle */                      \
 181                 if (r->x1 < x2) overlap = 1;                            \
 182                 if (x2 < r->x2) x2 = r->x2;                             \
 183         } else {                                                  \
 184                 /* Add current rectangle, start new one */              \
 185                 rects.push_back(eRect(x1, y1, x2 - x1, y2 - y1));       \
 186                 x1 = r->x1;                                             \
 187                 x2 = r->x2;                                             \
 188         }                                                         \
 189         r++;                                                      \
 190 }
 191
 192 void gRegion::mergeO(
 193                 std::vector<eRect>::const_iterator r1,
 194                 std::vector<eRect>::const_iterator r1End,
 195                 std::vector<eRect>::const_iterator r2,
 196                 std::vector<eRect>::const_iterator r2End,
 197                 int y1, int y2,
 198                 int &overlap)
 199 {
 200         int x1, x2;
 201
 202         ASSERT(y1 < y2);
 203         ASSERT(r1 != r1End && r2 != r2End);
 204
 205         if (r1->x1 < r2->x1)
 206         {
 207                 x1 = r1->x1;
 208                 x2 = r1->x2;
 209                 ++r1;
 210         } else {
 211                 x1 = r2->x1;
 212                 x2 = r2->x2;
 213                 ++r2;
 214         }
 215
 216         while (r1 != r1End && r2 != r2End)
 217                 if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
 218
 219         if (r1 != r1End)
 220         {
 221                 do {
 222                         MERGERECT(r1);
 223                 } while (r1 != r1End);
 224         } else if (r2 != r2End)
 225         {
 226                 do {
 227                         MERGERECT(r2);
 228                 } while (r2 != r2End);
 229         }
 230         rects.push_back(eRect(x1, y1, x2 - x1, y2 - y1));
 231 }
 232
 233 void gRegion::regionOp(const gRegion &reg1, const gRegion &reg2, int opcode, int &overlap)
 234 {
 235         std::vector<eRect>::const_iterator r1, r1End, r2, r2End, r1BandEnd, r2BandEnd;
 236         int prevBand;
 237         int r1y1, r2y1;
 238         int curBand, ytop, top, bot;
 239
 240         r1    = reg1.rects.begin();
 241         r1End = reg1.rects.end();
 242         r2    = reg2.rects.begin();
 243         r2End = reg2.rects.end();
 244
 245         int newSize  = reg1.rects.size();
 246         int numRects = reg2.rects.size();
 247         ASSERT(r1 != r1End);
 248         ASSERT(r2 != r2End);
 249
 250         if (numRects > newSize)
 251                 newSize = numRects;
 252         newSize <<= 1;
 253
 254         rects.reserve(newSize);
 255
 256         int ybot = min(r1->y1, r2->y1);
 257         prevBand = 0;
 258         do {
 259                 ASSERT(r1 != r1End);
 260                 ASSERT(r2 != r2End);
 261                 FindBand(r1, r1BandEnd, r1End, r1y1);
 262                 FindBand(r2, r2BandEnd, r2End, r2y1);
 263                 if (r1y1 < r2y1) {
 264                         if (opcode & 1) {
 265                                 top = max(r1y1, ybot);
 266                                 bot = min(r1->y2, r2y1);
 267                                 if (top != bot) {
 268                                         curBand = rects.size();
 269                                         appendNonO(r1, r1BandEnd, top, bot);
 270                                         coalesce(prevBand, curBand);
 271                                 }
 272                         }
 273                         ytop = r2y1;
 274                 } else if (r2y1 < r1y1) {
 275                         if (opcode & 2) {
 276                                 top = max(r2y1, ybot);
 277                                 bot = min(r2->y2, r1y1);
 278                                 if (top != bot) {
 279                                         curBand = rects.size();
 280                                         appendNonO(r2, r2BandEnd, top, bot);
 281                                         coalesce(prevBand, curBand);
 282                                 }
 283                         }
 284                         ytop = r1y1;
 285                 } else
 286                         ytop = r1y1;
 287                         ybot = min(r1->y2, r2->y2);
 288                 if (ybot > ytop) {
 289                         curBand = rects.size();
 290                         switch (opcode)
 291                         {
 292                         case OP_INTERSECT:
 293                                 intersectO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap);
 294                                 break;
 295                         case OP_SUBTRACT:
 296                                 subtractO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap);
 297                                 break;
 298                         case OP_UNION:
 299                                 mergeO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap);
 300                                 break;
 301                         default:
 302                                 ASSERT(0);
 303                                 break;
 304                         }
 305                         coalesce(prevBand, curBand);
 306                 }
 307                 if (r1->y2 == ybot) r1 = r1BandEnd;
 308                 if (r2->y2 == ybot) r2 = r2BandEnd;
 309         } while (r1 != r1End && r2 != r2End);
 310         if ((r1 != r1End) && (opcode & 1)) {
 311                 FindBand(r1, r1BandEnd, r1End, r1y1);
 312                 curBand = rects.size();
 313                 appendNonO(r1, r1BandEnd, max(r1y1, ybot), r1->y2);
 314                 coalesce(prevBand, curBand);
 315                 AppendRegions(r1BandEnd, r1End);
 316         } else if ((r2 != r2End) && (opcode & 2)) {
 317                 FindBand(r2, r2BandEnd, r2End, r2y1);
 318                 curBand = rects.size();
 319                 appendNonO(r2, r2BandEnd, max(r2y1, ybot), r2->y2);
 320                 coalesce(prevBand, curBand);
 321                 AppendRegions(r2BandEnd, r2End);
 322         }
 323
 324         extends = eRect();
 325
 326         for (unsigned int a = 0; a<rects.size(); ++a)
 327                 extends = extends | rects[a];
 328         if (!extends.valid())
 329                 extends = eRect::emptyRect();
 330 }
 331
 332 void gRegion::intersect(const gRegion &r1, const gRegion &r2)
 333 {
 334                 /* in case one region is empty, the resulting regions is empty, too. */
 335         if (r1.rects.empty())
 336         {
 337                 *this = r1;
 338                 return;
 339         }
 340         if (r2.rects.empty())
 341         {
 342                 *this = r2;
 343                 return;
 344         }
 345         int overlap;
 346         // TODO: handle trivial reject
 347         regionOp(r1, r2, OP_INTERSECT, overlap);
 348 }
 349
 350 void gRegion::subtract(const gRegion &r1, const gRegion &r2)
 351 {
 352         if (r1.rects.empty() || r2.rects.empty())
 353         {
 354                 *this = r1;
 355                 return;
 356         }
 357         int overlap;
 358         // TODO: handle trivial reject
 359         regionOp(r1, r2, OP_SUBTRACT, overlap);
 360 }
 361
 362 void gRegion::merge(const gRegion &r1, const gRegion &r2)
 363 {
 364         if (r1.rects.empty())
 365         {
 366                 *this = r2;
 367                 return;
 368         }
 369         if (r2.rects.empty())
 370         {
 371                 *this = r1;
 372                 return;
 373         }
 374         int overlap;
 375         // TODO: handle trivial reject
 376         regionOp(r1, r2, OP_UNION, overlap);
 377 }
 378
 379 gRegion gRegion::operator&(const gRegion &r2) const
 380 {
 381         gRegion res;
 382         res.intersect(*this, r2);
 383         return res;
 384 }
 385
 386 gRegion gRegion::operator-(const gRegion &r2) const
 387 {
 388         gRegion res;
 389         res.subtract(*this, r2);
 390         return res;
 391 }
 392
 393 gRegion gRegion::operator|(const gRegion &r2) const
 394 {
 395         gRegion res;
 396         res.merge(*this, r2);
 397         return res;
 398 }
 399
 400 gRegion &gRegion::operator&=(const gRegion &r2)
 401 {
 402         gRegion res;
 403         res.intersect(*this, r2);
 404         return *this = res;
 405 }
 406
 407 gRegion &gRegion::operator-=(const gRegion &r2)
 408 {
 409         gRegion res;
 410         res.subtract(*this, r2);
 411         return *this = res;
 412 }
 413
 414 gRegion &gRegion::operator|=(const gRegion &r2)
 415 {
 416         gRegion res;
 417         res.merge(*this, r2);
 418         return *this = res;
 419 }
 420
 421 void gRegion::moveBy(ePoint offset)
 422 {
 423         extends.moveBy(offset);
 424         unsigned int i;
 425         for (i=0; i<rects.size(); ++i)
 426                 rects[i].moveBy(offset);
 427 }
 428
 429 void gRegion::scale(int x_n, int x_d, int y_n, int y_d)
 430 {
 431         unsigned int i;
 432         for (i=0; i<rects.size(); ++i)
 433                 rects[i].scale(x_n, x_d, y_n, y_d);
 434 }
 435