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