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