--- /dev/null
+#include <lib/gdi/erect.h>
+#include <lib/gdi/epoint.h>
+#include <lib/gdi/region.h>
+
+#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<eRect>::iterator prevBox = rects.begin() + prevStart;
+ std::vector<eRect>::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<eRect>::const_iterator r,
+ std::vector<eRect>::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<eRect>::const_iterator r1,
+ std::vector<eRect>::const_iterator r1End,
+ std::vector<eRect>::const_iterator r2,
+ std::vector<eRect>::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<eRect>::const_iterator r1,
+ std::vector<eRect>::const_iterator r1End,
+ std::vector<eRect>::const_iterator r2,
+ std::vector<eRect>::const_iterator r2End,
+ int y1, int y2,
+ int &overlap)
+{
+ int x1;
+ x1 = r1->x1;
+
+ assert(y1<y2);
+ assert(r1 != r1End && r2 != r2End);
+
+ do {
+ if (r2->x2 <= 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(x1<r2->x1);
+ 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(x1<r1->x2);
+ 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<eRect>::const_iterator r1,
+ std::vector<eRect>::const_iterator r1End,
+ std::vector<eRect>::const_iterator r2,
+ std::vector<eRect>::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<eRect>::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);
+}
+
projects / vuplus_dvbapp / blobdiff