1 #include <lib/gdi/erect.h>
2 #include <lib/gdi/epoint.h>
3 #include <lib/gdi/region.h>
4 #include <lib/base/eerror.h>
7 #define max(a,b) ((a) > (b) ? (a) : (b))
9 #define min(a,b) ((a) < (b) ? (a) : (b))
16 A region is basically a list of rectangles. In this implementation,
17 rectangles are ordered by their upper-left position, organized in bands.
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.
23 Thanks go out to ryg, for explaining me this stuff.
27 gRegion::gRegion(const eRect &rect) : extends(rect)
29 if (rect.valid() && !rect.empty())
30 rects.push_back(rect);
33 gRegion::gRegion() : extends(eRect::emptyRect())
41 int gRegion::do_coalesce(int prevStart, unsigned int curStart)
43 // Figure out how many rectangles are in the band.
44 unsigned int numRects = curStart - prevStart;
45 assert(numRects == rects.size() - curStart);
48 std::vector<eRect>::iterator prevBox = rects.begin() + prevStart;
49 std::vector<eRect>::const_iterator curBox = rects.begin() + curStart;
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)
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.
64 if ((prevBox->x1 != curBox->x1) || (prevBox->x2 != curBox->x2))
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);
83 void gRegion::appendNonO(std::vector<eRect>::const_iterator r,
84 std::vector<eRect>::const_iterator rEnd, int y1, int y2)
86 int newRects = rEnd - r;
88 assert(newRects != 0);
89 rects.reserve(rects.size() + newRects);
91 assert(r->x1 < r->x2);
92 rects.push_back(eRect(r->x1, y1, r->x2 - r->x1, y2 - y1));
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,
108 assert(r1 != r1End && r2 != r2End);
111 x1 = max(r1->x1, r2->x1);
112 x2 = min(r1->x2, r2->x2);
115 rects.push_back(eRect(x1, y1, x2 - x1, y2 - y1));
120 } while ( (r1 != r1End) && (r2 != r2End));
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,
135 assert(r1 != r1End && r2 != r2End);
140 else if (r2->x1 <= x1) {
148 } else if (r2->x1 < r1->x2) {
150 rects.push_back(eRect(x1, y1, r2->x1 - x1, y2 - y1));
161 rects.push_back(eRect(x1, y1, r1->x2 - x1, y2 - y1));
166 } while ((r1 != r1End) && (r2 != r2End));
170 rects.push_back(eRect(x1, y1, r1->x2 - x1, y2 - y1));
177 #define MERGERECT(r) \
180 /* Merge with current rectangle */ \
181 if (r->x1 < x2) overlap = 1; \
182 if (x2 < r->x2) x2 = r->x2; \
184 /* Add current rectangle, start new one */ \
185 rects.push_back(eRect(x1, y1, x2 - x1, y2 - y1)); \
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,
203 assert(r1 != r1End && r2 != r2End);
216 while (r1 != r1End && r2 != r2End)
217 if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
223 } while (r1 != r1End);
224 } else if (r2 != r2End)
228 } while (r2 != r2End);
230 rects.push_back(eRect(x1, y1, x2 - x1, y2 - y1));
233 void gRegion::regionOp(const gRegion ®1, const gRegion ®2, int opcode, int &overlap)
235 std::vector<eRect>::const_iterator r1, r1End, r2, r2End, r1BandEnd, r2BandEnd;
238 int curBand, ytop, top, bot;
240 r1 = reg1.rects.begin();
241 r1End = reg1.rects.end();
242 r2 = reg2.rects.begin();
243 r2End = reg2.rects.end();
245 int newSize = reg1.rects.size();
246 int numRects = reg2.rects.size();
250 if (numRects > newSize)
254 rects.reserve(newSize);
256 int ybot = min(r1->y1, r2->y1);
261 FindBand(r1, r1BandEnd, r1End, r1y1);
262 FindBand(r2, r2BandEnd, r2End, r2y1);
265 top = max(r1y1, ybot);
266 bot = min(r1->y2, r2y1);
268 curBand = rects.size();
269 appendNonO(r1, r1BandEnd, top, bot);
270 coalesce(prevBand, curBand);
274 } else if (r2y1 < r1y1) {
276 top = max(r2y1, ybot);
277 bot = min(r2->y2, r1y1);
279 curBand = rects.size();
280 appendNonO(r2, r2BandEnd, top, bot);
281 coalesce(prevBand, curBand);
287 ybot = min(r1->y2, r2->y2);
289 curBand = rects.size();
293 intersectO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap);
296 subtractO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap);
299 mergeO(r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, overlap);
305 coalesce(prevBand, curBand);
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);
326 for (unsigned int a = 0; a<rects.size(); ++a)
327 extends = extends | rects[a];
330 void gRegion::intersect(const gRegion &r1, const gRegion &r2)
332 /* in case one region is empty, the resulting regions is empty, too. */
333 if (r1.rects.empty())
338 if (r2.rects.empty())
344 // TODO: handle trivial reject
345 regionOp(r1, r2, OP_INTERSECT, overlap);
348 void gRegion::subtract(const gRegion &r1, const gRegion &r2)
350 if (r1.rects.empty() || r2.rects.empty())
356 // TODO: handle trivial reject
357 regionOp(r1, r2, OP_SUBTRACT, overlap);
360 void gRegion::merge(const gRegion &r1, const gRegion &r2)
362 if (r1.rects.empty())
367 if (r2.rects.empty())
373 // TODO: handle trivial reject
374 regionOp(r1, r2, OP_UNION, overlap);
377 gRegion gRegion::operator&(const gRegion &r2) const
380 res.intersect(*this, r2);
384 gRegion gRegion::operator-(const gRegion &r2) const
387 res.subtract(*this, r2);
391 gRegion gRegion::operator|(const gRegion &r2) const
394 res.merge(*this, r2);
398 gRegion &gRegion::operator&=(const gRegion &r2)
401 res.intersect(*this, r2);
405 gRegion &gRegion::operator-=(const gRegion &r2)
408 res.subtract(*this, r2);
412 gRegion &gRegion::operator|=(const gRegion &r2)
415 res.merge(*this, r2);
419 void gRegion::moveBy(ePoint offset)
421 extends.moveBy(offset);
423 for (i=0; i<rects.size(); ++i)
424 rects[i].moveBy(offset);