X-Git-Url: http://code.vuplus.com/gitweb/?p=vuplus_dvbapp;a=blobdiff_plain;f=lib%2Fgdi%2Fregion.cpp;fp=lib%2Fgdi%2Fregion.cpp;h=f341e79a61de30aeb17bc6918c91be336acee6a7;hp=0000000000000000000000000000000000000000;hb=d6f6602d7cea3a7899990fe79216af7d98d05917;hpb=ae9b6fba0b02b5990fd1635a2154336c5043df02 diff --git a/lib/gdi/region.cpp b/lib/gdi/region.cpp new file mode 100644 index 0000000..f341e79 --- /dev/null +++ b/lib/gdi/region.cpp @@ -0,0 +1,343 @@ +#include +#include +#include + +#undef max +#define max(a,b) ((a) > (b) ? (a) : (b)) +#undef min +#define min(a,b) ((a) < (b) ? (a) : (b)) + + +/* + + Region code. + + A region is basically a list of rectangles. In this implementation, + rectangles are ordered by their upper-left position, organized in bands. + + this code stolen from miregion.c out of the X-Window system. + for implementation details, look into their source. + This code does all the ugly stuff. + + Thanks go out to ryg, for explaining me this stuff. + +*/ + +gRegion::gRegion(const eRect &rect) : extends(rect) +{ + rects.push_back(rect); +} + +gRegion::gRegion() +{ +} + +gRegion::~gRegion() +{ +} + +int gRegion::do_coalesce(int prevStart, unsigned int curStart) +{ + // Figure out how many rectangles are in the band. + unsigned int numRects = curStart - prevStart; + assert(numRects == rects.size() - curStart); + if (!numRects) + return curStart; + std::vector::iterator prevBox = rects.begin() + prevStart; + std::vector::const_iterator curBox = rects.begin() + curStart; + + // The bands may only be coalesced if the bottom of the previous + // matches the top scanline of the current. + if (prevBox->y2 != curBox->y1) + return curStart; + + // Make sure the bands have boxes in the same places. This + // assumes that boxes have been added in such a way that they + // cover the most area possible. I.e. two boxes in a band must + // have some horizontal space between them. + + int y2 = curBox->y2; + + do { + if ((prevBox->x1 != curBox->x1) || (prevBox->x2 != curBox->x2)) + return curStart; + prevBox++; + curBox++; + numRects--; + } while ( numRects ); + + // The bands may be merged, so set the bottom y of each box + // in the previous band to the bottom y of the current band. + numRects = curStart - prevStart; + rects.resize(rects.size() - numRects); + do { + prevBox--; + prevBox->y2 = y2; + numRects--; + } while (numRects); + return prevStart; +} + +void gRegion::appendNonO(std::vector::const_iterator r, + std::vector::const_iterator rEnd, int y1, int y2) +{ + int newRects = rEnd - r; + assert(y1 < y2); + assert(newRects != 0); + rects.reserve(rects.size() + newRects); + do { + assert(r->x1 < r->x2); + rects.push_back(eRect(r->x1, y1, r->x2, y2)); + r++; + } while (r != rEnd); +} + +void gRegion::intersectO( + std::vector::const_iterator r1, + std::vector::const_iterator r1End, + std::vector::const_iterator r2, + std::vector::const_iterator r2End, + int y1, int y2, + int &overlap) +{ + int x1, x2; + + assert(y1 < y2); + assert(r1 != r1End && r2 != r2End); + + do { + x1 = max(r1->x1, r2->x1); + x2 = min(r1->x2, r2->x2); + + if (x1 < x2) + rects.push_back(eRect(x1, y1, x2, y2)); + if (r1->x2 == x2) + r1++; + if (r2->x2 == x2) + r2++; + } while ( (r1 != r1End) && (r2 != r2End)); +} + +void gRegion::subtractO( + std::vector::const_iterator r1, + std::vector::const_iterator r1End, + std::vector::const_iterator r2, + std::vector::const_iterator r2End, + int y1, int y2, + int &overlap) +{ + int x1; + x1 = r1->x1; + + assert(y1x2 <= x1) + ++r2; + else if (r2->x1 <= x1) { + x1 = r2->x2; + if (x1 >= r1->x2) { + ++r1; + if (r1 != r1End) + x1 = r1->x1; + } else + ++r2; + } else if (r2->x1 < r1->x2) { + assert(x1x1); + rects.push_back(eRect(x1, y1, r2->x1, y2)); + x1 = r2->x2; + if (x1 >= r1->x2) { + ++r1; + if (r1 != r1End) + x1 = r1->x1; + } else + ++r2; + } else + { + if (r1->x2 > x1) + rects.push_back(eRect(x1, y1, r1->x2, y2)); + ++r1; + if (r1 != r1End) + x1 = r1->x1; + } + } while ((r1 != r1End) && (r2 != r2End)); + while (r1 != r1End) + { + assert(x1x2); + rects.push_back(eRect(x1, y1, r1->x2, y2)); + ++r1; + if (r1 != r1End) + x1 = r1->x1; + } +} + +#define MERGERECT(r) \ +{ \ + if (r->x1 <= x2) { \ + /* Merge with current rectangle */ \ + if (r->x1 < x2) overlap = 1; \ + if (x2 < r->x2) x2 = r->x2; \ + } else { \ + /* Add current rectangle, start new one */ \ + rects.push_back(eRect(x1, y1, x2, y2)); \ + x1 = r->x1; \ + x2 = r->x2; \ + } \ + r++; \ +} + +void gRegion::mergeO( + std::vector::const_iterator r1, + std::vector::const_iterator r1End, + std::vector::const_iterator r2, + std::vector::const_iterator r2End, + int y1, int y2, + int &overlap) +{ + int x1, x2; + + assert(y1 < y2); + assert(r1 != r1End && r2 != r2End); + + if (r1->x1 < r2->x1) + { + x1 = r1->x1; + x2 = r1->x2; + ++r1; + } else { + x1 = r2->x1; + x2 = r2->x2; + ++r2; + } + + while (r1 != r1End && r2 != r2End) + if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2); + + if (r1 != r1End) + { + do { + MERGERECT(r1); + } while (r1 != r1End); + } else if (r2 != r2End) + { + do { + MERGERECT(r2); + } while (r2 != r2End); + } + rects.push_back(eRect(x1, y1, x2, y2)); +} + +void gRegion::regionOp(const gRegion ®1, const gRegion ®2, int opcode, int &overlap) +{ + std::vector::const_iterator r1, r1End, r2, r2End, r1BandEnd, r2BandEnd; + int prevBand; + int r1y1, r2y1; + int curBand, ytop, top, bot; + + r1 = reg1.rects.begin(); + r1End = reg1.rects.end(); + r2 = reg2.rects.begin(); + r2End = reg2.rects.end(); + + int newSize = reg1.rects.size(); + int numRects = reg2.rects.size(); + assert(r1 != r1End); + assert(r2 != r2End); + + if (numRects > newSize) + newSize = numRects; + newSize <<= 1; + + rects.reserve(newSize); + + int ybot = min(r1->y1, r2->y1); + prevBand = 0; + do { + assert(r1 != r1End); + assert(r2 != r2End); + FindBand(r1, r1BandEnd, r1End, r1y1); + FindBand(r2, r2BandEnd, r2End, r2y1); + if (r1y1 < r2y1) { + if (opcode & 1) { + top = max(r1y1, ybot); + bot = min(r1->y2, r2y1); + if (top != bot) { + curBand = rects.size(); + appendNonO(r1, r1BandEnd, top, bot); + coalesce(prevBand, curBand); + } + } + ytop = r2y1; + } else if (r2y1 < r1y1) { + if (opcode & 2) { + top = max(r2y1, ybot); + bot = min(r2->y2, r1y1); + if (top != bot) { + curBand = rects.size(); + appendNonO(r2, r2BandEnd, top, bot); + coalesce(prevBand, curBand); + } + } + ytop = r1y1; + } else + ytop = r1y1; + ybot = min(r1->y2, r2->y2); + if (ybot > ytop) { + curBand = rects.size(); + switch (opcode) + { + case OP_INTERSECT: + intersectO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap); + break; + case OP_SUBTRACT: + subtractO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap); + break; + case OP_UNION: + mergeO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap); + break; + default: + assert(0); + break; + } + coalesce(prevBand, curBand); + } + if (r1->y2 == ybot) r1 = r1BandEnd; + if (r2->y2 == ybot) r2 = r2BandEnd; + } while (r1 != r1End && r2 != r2End); + if ((r1 != r1End) && (opcode & 1)) { + FindBand(r1, r1BandEnd, r1End, r1y1); + curBand = rects.size(); + appendNonO(r1, r1BandEnd, max(r1y1, ybot), r1->y2); + coalesce(prevBand, curBand); + AppendRegions(r1BandEnd, r1End); + } else if ((r2 != r2End) && (opcode & 2)) { + FindBand(r2, r2BandEnd, r2End, r2y1); + curBand = rects.size(); + appendNonO(r2, r2BandEnd, max(r2y1, ybot), r2->y2); + coalesce(prevBand, curBand); + AppendRegions(r2BandEnd, r2End); + } +} + +void gRegion::intersect(const gRegion &r1, const gRegion &r2) +{ + int overlap; + // TODO: handle trivial reject + regionOp(r1, r2, OP_INTERSECT, overlap); +} + +void gRegion::subtract(const gRegion &r1, const gRegion &r2) +{ + int overlap; + // TODO: handle trivial reject + regionOp(r1, r2, OP_SUBTRACT, overlap); +} + +void gRegion::merge(const gRegion &r1, const gRegion &r2) +{ + int overlap; + // TODO: handle trivial reject + regionOp(r1, r2, OP_UNION, overlap); +} +