1 /////////////////////////////////////////////////////////////////////////////
2 // Name: src/generic/regiong.cpp
3 // Purpose: generic wxRegion class
4 // Author: David Elliott
5 // Modified by:
6 // Created: 2004/04/12
7 // Copyright: (c) 2004 David Elliott
8 // Licence: wxWindows licence
9 /////////////////////////////////////////////////////////////////////////////
10
11
12 // For compilers that support precompilation, includes "wx.h".
13 #include "wx/wxprec.h"
14
15
16 #include "wx/region.h"
17
18 #ifndef WX_PRECOMP
19 #include "wx/utils.h"
20 #endif
21
22 // ========================================================================
23 // Classes to interface with X.org code
24 // ========================================================================
25
26 typedef struct Box
27 {
28 wxCoord x1, x2, y1, y2;
29 } Box, BOX, BoxRec, *BoxPtr;
30
31 typedef struct REGION *Region;
32
33 struct REGION
34 {
35 public:
36 // Default constructor initializes nothing
REGIONREGION37 REGION() {}
38
REGIONREGION39 REGION(const wxRect& rect)
40 {
41 rects = &extents;
42 numRects = 1;
43 extents.x1 = rect.x;
44 extents.y1 = rect.y;
45 extents.x2 = rect.x + rect.width;
46 extents.y2 = rect.y + rect.height;
47 size = 1;
48 }
49
GetBoxREGION50 BoxPtr GetBox(int i)
51 {
52 return i < numRects ? rects + i : NULL;
53 }
54
55 // X.org methods
56 static bool XClipBox(
57 Region r,
58 wxRect *rect);
59 static bool XOffsetRegion(
60 Region pRegion,
61 int x,
62 int y);
63 static bool XIntersectRegion(
64 Region reg1,
65 Region reg2, /* source regions */
66 Region newReg); /* destination Region */
67 static bool XUnionRegion(
68 Region reg1,
69 Region reg2, /* source regions */
70 Region newReg); /* destination Region */
71 static bool XSubtractRegion(
72 Region regM,
73 Region regS,
74 Region regD);
75 static bool XXorRegion(Region sra, Region srb, Region dr);
76 static bool XEmptyRegion(
77 Region r);
78 static bool XEqualRegion(Region r1, Region r2);
79 static bool XPointInRegion(
80 Region pRegion,
81 int x, int y);
82 static wxRegionContain XRectInRegion(
83 Region region,
84 int rx, int ry,
85 unsigned int rwidth, unsigned int rheight);
86
87 protected:
88 static Region XCreateRegion(void);
89 static void miSetExtents (
90 Region pReg);
91 static bool XDestroyRegion(Region r);
92 static int miIntersectO (
93 Region pReg,
94 BoxPtr r1,
95 BoxPtr r1End,
96 BoxPtr r2,
97 BoxPtr r2End,
98 wxCoord y1,
99 wxCoord y2);
100 static void miRegionCopy(
101 Region dstrgn,
102 Region rgn);
103 static int miCoalesce(
104 Region pReg, /* Region to coalesce */
105 int prevStart, /* Index of start of previous band */
106 int curStart); /* Index of start of current band */
107 static void miRegionOp(
108 Region newReg, /* Place to store result */
109 Region reg1, /* First region in operation */
110 Region reg2, /* 2d region in operation */
111 int (*overlapFunc)(
112 Region pReg,
113 BoxPtr r1,
114 BoxPtr r1End,
115 BoxPtr r2,
116 BoxPtr r2End,
117 wxCoord y1,
118 wxCoord y2), /* Function to call for over-
119 * lapping bands */
120 int (*nonOverlap1Func)(
121 Region pReg,
122 BoxPtr r,
123 BoxPtr rEnd,
124 wxCoord y1,
125 wxCoord y2), /* Function to call for non-
126 * overlapping bands in region
127 * 1 */
128 int (*nonOverlap2Func)(
129 Region pReg,
130 BoxPtr r,
131 BoxPtr rEnd,
132 wxCoord y1,
133 wxCoord y2)); /* Function to call for non-
134 * overlapping bands in region
135 * 2 */
136 static int miUnionNonO (
137 Region pReg,
138 BoxPtr r,
139 BoxPtr rEnd,
140 wxCoord y1,
141 wxCoord y2);
142 static int miUnionO (
143 Region pReg,
144 BoxPtr r1,
145 BoxPtr r1End,
146 BoxPtr r2,
147 BoxPtr r2End,
148 wxCoord y1,
149 wxCoord y2);
150 static int miSubtractNonO1 (
151 Region pReg,
152 BoxPtr r,
153 BoxPtr rEnd,
154 wxCoord y1,
155 wxCoord y2);
156 static int miSubtractO (
157 Region pReg,
158 BoxPtr r1,
159 BoxPtr r1End,
160 BoxPtr r2,
161 BoxPtr r2End,
162 wxCoord y1,
163 wxCoord y2);
164 protected:
165 long size;
166 long numRects;
167 Box *rects;
168 Box extents;
169 };
170
171 // ========================================================================
172 // wxRegionRefData
173 // ========================================================================
174
175 class wxRegionRefData : public wxGDIRefData,
176 public REGION
177 {
178 public:
wxRegionRefData()179 wxRegionRefData()
180 : wxGDIRefData(),
181 REGION()
182 {
183 size = 1;
184 numRects = 0;
185 rects = ( BOX * )malloc( (unsigned) sizeof( BOX ));
186 extents.x1 = 0;
187 extents.x2 = 0;
188 extents.y1 = 0;
189 extents.y2 = 0;
190 }
191
wxRegionRefData(const wxPoint & topLeft,const wxPoint & bottomRight)192 wxRegionRefData(const wxPoint& topLeft, const wxPoint& bottomRight)
193 : wxGDIRefData(),
194 REGION()
195 {
196 rects = (BOX*)malloc(sizeof(BOX));
197 size = 1;
198 numRects = 1;
199 extents.x1 = topLeft.x;
200 extents.y1 = topLeft.y;
201 extents.x2 = bottomRight.x;
202 extents.y2 = bottomRight.y;
203 *rects = extents;
204 }
205
wxRegionRefData(const wxRect & rect)206 wxRegionRefData(const wxRect& rect)
207 : wxGDIRefData(),
208 REGION(rect)
209 {
210 rects = (BOX*)malloc(sizeof(BOX));
211 *rects = extents;
212 }
213
wxRegionRefData(const wxRegionRefData & refData)214 wxRegionRefData(const wxRegionRefData& refData)
215 : wxGDIRefData(),
216 REGION()
217 {
218 size = refData.size;
219 numRects = refData.numRects;
220 rects = (Box*)malloc(numRects*sizeof(Box));
221 memcpy(rects, refData.rects, numRects*sizeof(Box));
222 extents = refData.extents;
223 }
224
~wxRegionRefData()225 virtual ~wxRegionRefData()
226 {
227 free(rects);
228 }
229
230 private:
231 // Don't allow this
232 wxRegionRefData(const REGION&);
233 };
234
235 // ========================================================================
236 // wxRegionGeneric
237 // ========================================================================
238 //wxIMPLEMENT_DYNAMIC_CLASS(wxRegionGeneric, wxGDIObject);
239
240 #define M_REGIONDATA ((wxRegionRefData *)m_refData)
241 #define M_REGIONDATA_OF(rgn) ((wxRegionRefData *)(rgn.m_refData))
242
243 // ----------------------------------------------------------------------------
244 // wxRegionGeneric construction
245 // ----------------------------------------------------------------------------
246
wxRegionGeneric()247 wxRegionGeneric::wxRegionGeneric()
248 {
249 }
250
~wxRegionGeneric()251 wxRegionGeneric::~wxRegionGeneric()
252 {
253 }
254
wxRegionGeneric(wxCoord x,wxCoord y,wxCoord w,wxCoord h)255 wxRegionGeneric::wxRegionGeneric(wxCoord x, wxCoord y, wxCoord w, wxCoord h)
256 {
257 m_refData = new wxRegionRefData(wxRect(x,y,w,h));
258 }
259
wxRegionGeneric(const wxRect & rect)260 wxRegionGeneric::wxRegionGeneric(const wxRect& rect)
261 {
262 m_refData = new wxRegionRefData(rect);
263 }
264
wxRegionGeneric(const wxPoint & topLeft,const wxPoint & bottomRight)265 wxRegionGeneric::wxRegionGeneric(const wxPoint& topLeft, const wxPoint& bottomRight)
266 {
267 m_refData = new wxRegionRefData(topLeft, bottomRight);
268 }
269
wxRegionGeneric(const wxBitmap & bmp)270 wxRegionGeneric::wxRegionGeneric(const wxBitmap& bmp)
271 {
272 wxFAIL_MSG("NOT IMPLEMENTED: wxRegionGeneric::wxRegionGeneric(const wxBitmap& bmp)");
273 }
274
wxRegionGeneric(size_t n,const wxPoint * points,wxPolygonFillMode fillStyle)275 wxRegionGeneric::wxRegionGeneric(size_t n, const wxPoint *points, wxPolygonFillMode fillStyle)
276 {
277 wxFAIL_MSG("NOT IMPLEMENTED: wxRegionGeneric::wxRegionGeneric(size_t n, const wxPoint *points, wxPolygonFillMode fillStyle)");
278 }
279
wxRegionGeneric(const wxBitmap & bmp,const wxColour & transp,int tolerance)280 wxRegionGeneric::wxRegionGeneric(const wxBitmap& bmp, const wxColour& transp, int tolerance)
281 {
282 wxFAIL_MSG("NOT IMPLEMENTED: wxRegionGeneric::wxRegionGeneric(const wxBitmap& bmp, const wxColour& transp, int tolerance)");
283 }
284
Clear()285 void wxRegionGeneric::Clear()
286 {
287 UnRef();
288 if (!m_refData)
289 m_refData = new wxRegionRefData(wxRect(0,0,0,0));
290 }
291
CreateGDIRefData() const292 wxGDIRefData *wxRegionGeneric::CreateGDIRefData() const
293 {
294 return new wxRegionRefData;
295 }
296
CloneGDIRefData(const wxGDIRefData * data) const297 wxGDIRefData *wxRegionGeneric::CloneGDIRefData(const wxGDIRefData *data) const
298 {
299 return new wxRegionRefData(*(wxRegionRefData *)data);
300 }
301
DoIsEqual(const wxRegion & region) const302 bool wxRegionGeneric::DoIsEqual(const wxRegion& region) const
303 {
304 return REGION::XEqualRegion(M_REGIONDATA,M_REGIONDATA_OF(region));
305 }
306
DoGetBox(wxCoord & x,wxCoord & y,wxCoord & w,wxCoord & h) const307 bool wxRegionGeneric::DoGetBox(wxCoord& x, wxCoord& y, wxCoord&w, wxCoord &h) const
308 {
309 if ( !m_refData )
310 return false;
311
312 wxRect rect;
313 REGION::XClipBox(M_REGIONDATA,&rect);
314 x = rect.x;
315 y = rect.y;
316 w = rect.width;
317 h = rect.height;
318 return true;
319 }
320
321 // ----------------------------------------------------------------------------
322 // wxRegionGeneric operations
323 // ----------------------------------------------------------------------------
324
DoUnionWithRect(const wxRect & rect)325 bool wxRegionGeneric::DoUnionWithRect(const wxRect& rect)
326 {
327 if ( rect.IsEmpty() )
328 {
329 // nothing to do
330 return true;
331 }
332
333 AllocExclusive();
334 REGION region(rect);
335 return REGION::XUnionRegion(®ion,M_REGIONDATA,M_REGIONDATA);
336 }
337
DoUnionWithRegion(const wxRegion & region)338 bool wxRegionGeneric::DoUnionWithRegion(const wxRegion& region)
339 {
340 AllocExclusive();
341 return REGION::XUnionRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA);
342 }
343
DoIntersect(const wxRegion & region)344 bool wxRegionGeneric::DoIntersect(const wxRegion& region)
345 {
346 AllocExclusive();
347 return REGION::XIntersectRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA);
348 }
349
DoSubtract(const wxRegion & region)350 bool wxRegionGeneric::DoSubtract(const wxRegion& region)
351 {
352 if ( region.IsEmpty() )
353 {
354 // nothing to do
355 return true;
356 }
357
358 return REGION::XSubtractRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA);
359 }
360
DoXor(const wxRegion & region)361 bool wxRegionGeneric::DoXor(const wxRegion& region)
362 {
363 AllocExclusive();
364 return REGION::XXorRegion(M_REGIONDATA_OF(region),M_REGIONDATA,M_REGIONDATA);
365 }
366
DoOffset(wxCoord x,wxCoord y)367 bool wxRegionGeneric::DoOffset(wxCoord x, wxCoord y)
368 {
369 AllocExclusive();
370 return REGION::XOffsetRegion(M_REGIONDATA, x, y);
371 }
372
373 // ----------------------------------------------------------------------------
374 // wxRegionGeneric comparison
375 // ----------------------------------------------------------------------------
376
IsEmpty() const377 bool wxRegionGeneric::IsEmpty() const
378 {
379 wxASSERT(m_refData);
380 return REGION::XEmptyRegion(M_REGIONDATA);
381 }
382
383 // Does the region contain the point (x,y)?
DoContainsPoint(wxCoord x,wxCoord y) const384 wxRegionContain wxRegionGeneric::DoContainsPoint(wxCoord x, wxCoord y) const
385 {
386 wxASSERT(m_refData);
387 return REGION::XPointInRegion(M_REGIONDATA,x,y) ? wxInRegion : wxOutRegion;
388 }
389
390 // Does the region contain the rectangle rect?
DoContainsRect(const wxRect & rect) const391 wxRegionContain wxRegionGeneric::DoContainsRect(const wxRect& rect) const
392 {
393 wxASSERT(m_refData);
394 return REGION::XRectInRegion(M_REGIONDATA,rect.x,rect.y,rect.width,rect.height);
395 }
396
397 // ========================================================================
398 // wxRegionIteratorGeneric
399 // ========================================================================
400 //wxIMPLEMENT_DYNAMIC_CLASS(wxRegionIteratorGeneric, wxObject);
401
wxRegionIteratorGeneric()402 wxRegionIteratorGeneric::wxRegionIteratorGeneric()
403 {
404 m_current = 0;
405 }
406
wxRegionIteratorGeneric(const wxRegionGeneric & region)407 wxRegionIteratorGeneric::wxRegionIteratorGeneric(const wxRegionGeneric& region)
408 : m_region(region)
409 {
410 m_current = 0;
411 }
412
wxRegionIteratorGeneric(const wxRegionIteratorGeneric & iterator)413 wxRegionIteratorGeneric::wxRegionIteratorGeneric(const wxRegionIteratorGeneric& iterator)
414 : m_region(iterator.m_region)
415 {
416 m_current = iterator.m_current;
417 }
418
Reset(const wxRegionGeneric & region)419 void wxRegionIteratorGeneric::Reset(const wxRegionGeneric& region)
420 {
421 m_region = region;
422 m_current = 0;
423 }
424
HaveRects() const425 bool wxRegionIteratorGeneric::HaveRects() const
426 {
427 return M_REGIONDATA_OF(m_region)->GetBox(m_current);
428 }
429
operator ++()430 wxRegionIteratorGeneric& wxRegionIteratorGeneric::operator++()
431 {
432 ++m_current;
433 return *this;
434 }
435
operator ++(int)436 wxRegionIteratorGeneric wxRegionIteratorGeneric::operator++(int)
437 {
438 wxRegionIteratorGeneric copy(*this);
439 ++*this;
440 return copy;
441 }
442
GetRect() const443 wxRect wxRegionIteratorGeneric::GetRect() const
444 {
445 wxASSERT(m_region.m_refData);
446 const Box *box = M_REGIONDATA_OF(m_region)->GetBox(m_current);
447 wxASSERT(box);
448 return wxRect
449 ( box->x1
450 , box->y1
451 , box->x2 - box->x1
452 , box->y2 - box->y1
453 );
454 }
455
GetX() const456 long wxRegionIteratorGeneric::GetX() const
457 {
458 wxASSERT(m_region.m_refData);
459 const Box *box = M_REGIONDATA_OF(m_region)->GetBox(m_current);
460 wxASSERT(box);
461 return box->x1;
462 }
463
GetY() const464 long wxRegionIteratorGeneric::GetY() const
465 {
466 wxASSERT(m_region.m_refData);
467 const Box *box = M_REGIONDATA_OF(m_region)->GetBox(m_current);
468 wxASSERT(box);
469 return box->y1;
470 }
471
GetW() const472 long wxRegionIteratorGeneric::GetW() const
473 {
474 wxASSERT(m_region.m_refData);
475 const Box *box = M_REGIONDATA_OF(m_region)->GetBox(m_current);
476 wxASSERT(box);
477 return box->x2 - box->x1;
478 }
479
GetH() const480 long wxRegionIteratorGeneric::GetH() const
481 {
482 wxASSERT(m_region.m_refData);
483 const Box *box = M_REGIONDATA_OF(m_region)->GetBox(m_current);
484 wxASSERT(box);
485 return box->y2 - box->y1;
486 }
487
~wxRegionIteratorGeneric()488 wxRegionIteratorGeneric::~wxRegionIteratorGeneric()
489 {
490 }
491
492
493 // ========================================================================
494 // The guts (from X.org)
495 // ========================================================================
496
497 /************************************************************************
498
499 Copyright 1987, 1988, 1998 The Open Group
500
501 Permission to use, copy, modify, distribute, and sell this software and its
502 documentation for any purpose is hereby granted without fee, provided that
503 the above copyright notice appear in all copies and that both that
504 copyright notice and this permission notice appear in supporting
505 documentation.
506
507 The above copyright notice and this permission notice shall be included in
508 all copies or substantial portions of the Software.
509
510 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
511 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
512 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
513 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
514 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
515 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
516
517 Except as contained in this notice, the name of The Open Group shall not be
518 used in advertising or otherwise to promote the sale, use or other dealings
519 in this Software without prior written authorization from The Open Group.
520
521
522 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
523
524 All Rights Reserved
525
526 Permission to use, copy, modify, and distribute this software and its
527 documentation for any purpose and without fee is hereby granted,
528 provided that the above copyright notice appear in all copies and that
529 both that copyright notice and this permission notice appear in
530 supporting documentation, and that the name of Digital not be
531 used in advertising or publicity pertaining to distribution of the
532 software without specific, written prior permission.
533
534 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
535 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
536 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
537 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
538 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
539 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
540 SOFTWARE.
541
542 ************************************************************************/
543
544 /* 1 if two BOXs overlap.
545 * 0 if two BOXs do not overlap.
546 * Remember, x2 and y2 are not in the region
547 */
548 #define EXTENTCHECK(r1, r2) \
549 ((r1)->x2 > (r2)->x1 && \
550 (r1)->x1 < (r2)->x2 && \
551 (r1)->y2 > (r2)->y1 && \
552 (r1)->y1 < (r2)->y2)
553
554 /*
555 * Check to see if there is enough memory in the present region.
556 */
557 #define MEMCHECK(reg, rect, firstrect){\
558 if ((reg)->numRects >= ((reg)->size - 1)){\
559 (firstrect) = (BOX *) realloc \
560 ((char *)(firstrect), (unsigned) (2 * (sizeof(BOX)) * ((reg)->size)));\
561 if ((firstrect) == 0)\
562 return(0);\
563 (reg)->size *= 2;\
564 (rect) = &(firstrect)[(reg)->numRects];\
565 }\
566 }
567
568 #define EMPTY_REGION(pReg) pReg->numRects = 0
569
570 #define REGION_NOT_EMPTY(pReg) pReg->numRects
571
572 #define INBOX(r, x, y) \
573 ( ( ((r).x2 > x)) && \
574 ( ((r).x1 <= x)) && \
575 ( ((r).y2 > y)) && \
576 ( ((r).y1 <= y)) )
577
578 /*
579 * The functions in this file implement the Region abstraction, similar to one
580 * used in the X11 sample server. A Region is simply an area, as the name
581 * implies, and is implemented as a "y-x-banded" array of rectangles. To
582 * explain: Each Region is made up of a certain number of rectangles sorted
583 * by y coordinate first, and then by x coordinate.
584 *
585 * Furthermore, the rectangles are banded such that every rectangle with a
586 * given upper-left y coordinate (y1) will have the same lower-right y
587 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
588 * will span the entire vertical distance of the band. This means that some
589 * areas that could be merged into a taller rectangle will be represented as
590 * several shorter rectangles to account for shorter rectangles to its left
591 * or right but within its "vertical scope".
592 *
593 * An added constraint on the rectangles is that they must cover as much
594 * horizontal area as possible. E.g. no two rectangles in a band are allowed
595 * to touch.
596 *
597 * Whenever possible, bands will be merged together to cover a greater vertical
598 * distance (and thus reduce the number of rectangles). Two bands can be merged
599 * only if the bottom of one touches the top of the other and they have
600 * rectangles in the same places (of the same width, of course). This maintains
601 * the y-x-banding that's so nice to have...
602 */
603
604 /* Create a new empty region */
XCreateRegion(void)605 Region REGION::XCreateRegion(void)
606 {
607 Region temp = new REGION;
608
609 if (!temp)
610 return (Region) NULL;
611
612 temp->rects = ( BOX * )malloc( (unsigned) sizeof( BOX ));
613
614 if (!temp->rects)
615 {
616 delete temp;
617 return (Region) NULL;
618 }
619 temp->numRects = 0;
620 temp->extents.x1 = 0;
621 temp->extents.y1 = 0;
622 temp->extents.x2 = 0;
623 temp->extents.y2 = 0;
624 temp->size = 1;
625 return( temp );
626 }
627
XClipBox(Region r,wxRect * rect)628 bool REGION::XClipBox(Region r, wxRect *rect)
629 {
630 rect->x = r->extents.x1;
631 rect->y = r->extents.y1;
632 rect->width = r->extents.x2 - r->extents.x1;
633 rect->height = r->extents.y2 - r->extents.y1;
634 return true;
635 }
636
637 /*-
638 *-----------------------------------------------------------------------
639 * miSetExtents --
640 * Reset the extents of a region to what they should be. Called by
641 * miSubtract and miIntersect b/c they can't figure it out along the
642 * way or do so easily, as miUnion can.
643 *
644 * Results:
645 * None.
646 *
647 * Side Effects:
648 * The region's 'extents' structure is overwritten.
649 *
650 *-----------------------------------------------------------------------
651 */
652 void REGION::
miSetExtents(Region pReg)653 miSetExtents (Region pReg)
654 {
655 BoxPtr pBox, pBoxEnd, pExtents;
656
657 if (pReg->numRects == 0)
658 {
659 pReg->extents.x1 = 0;
660 pReg->extents.y1 = 0;
661 pReg->extents.x2 = 0;
662 pReg->extents.y2 = 0;
663 return;
664 }
665
666 pExtents = &pReg->extents;
667 pBox = pReg->rects;
668 pBoxEnd = &pBox[pReg->numRects - 1];
669
670 /*
671 * Since pBox is the first rectangle in the region, it must have the
672 * smallest y1 and since pBoxEnd is the last rectangle in the region,
673 * it must have the largest y2, because of banding. Initialize x1 and
674 * x2 from pBox and pBoxEnd, resp., as good things to initialize them
675 * to...
676 */
677 pExtents->x1 = pBox->x1;
678 pExtents->y1 = pBox->y1;
679 pExtents->x2 = pBoxEnd->x2;
680 pExtents->y2 = pBoxEnd->y2;
681
682 wxASSERT_LEVEL_2(pExtents->y1 < pExtents->y2);
683 while (pBox <= pBoxEnd)
684 {
685 if (pBox->x1 < pExtents->x1)
686 {
687 pExtents->x1 = pBox->x1;
688 }
689 if (pBox->x2 > pExtents->x2)
690 {
691 pExtents->x2 = pBox->x2;
692 }
693 pBox++;
694 }
695 wxASSERT_LEVEL_2(pExtents->x1 < pExtents->x2);
696 }
697
698 bool REGION::
XDestroyRegion(Region r)699 XDestroyRegion(
700 Region r)
701 {
702 free( (char *) r->rects );
703 delete r;
704 return true;
705 }
706
707 /* TranslateRegion(pRegion, x, y)
708 translates in place
709 added by raymond
710 */
711
712 bool REGION::
XOffsetRegion(Region pRegion,int x,int y)713 XOffsetRegion(
714 Region pRegion,
715 int x,
716 int y)
717 {
718 int nbox;
719 BOX *pbox;
720
721 pbox = pRegion->rects;
722 nbox = pRegion->numRects;
723
724 while(nbox--)
725 {
726 pbox->x1 += x;
727 pbox->x2 += x;
728 pbox->y1 += y;
729 pbox->y2 += y;
730 pbox++;
731 }
732 pRegion->extents.x1 += x;
733 pRegion->extents.x2 += x;
734 pRegion->extents.y1 += y;
735 pRegion->extents.y2 += y;
736 return 1;
737 }
738
739 /*======================================================================
740 * Region Intersection
741 *====================================================================*/
742 /*-
743 *-----------------------------------------------------------------------
744 * miIntersectO --
745 * Handle an overlapping band for miIntersect.
746 *
747 * Results:
748 * None.
749 *
750 * Side Effects:
751 * Rectangles may be added to the region.
752 *
753 *-----------------------------------------------------------------------
754 */
755 /* static void*/
756 int REGION::
miIntersectO(Region pReg,BoxPtr r1,BoxPtr r1End,BoxPtr r2,BoxPtr r2End,wxCoord y1,wxCoord y2)757 miIntersectO (
758 Region pReg,
759 BoxPtr r1,
760 BoxPtr r1End,
761 BoxPtr r2,
762 BoxPtr r2End,
763 wxCoord y1,
764 wxCoord y2)
765 {
766 wxCoord x1;
767 wxCoord x2;
768 BoxPtr pNextRect;
769
770 pNextRect = &pReg->rects[pReg->numRects];
771
772 while ((r1 != r1End) && (r2 != r2End))
773 {
774 x1 = wxMax(r1->x1,r2->x1);
775 x2 = wxMin(r1->x2,r2->x2);
776
777 /*
778 * If there's any overlap between the two rectangles, add that
779 * overlap to the new region.
780 * There's no need to check for subsumption because the only way
781 * such a need could arise is if some region has two rectangles
782 * right next to each other. Since that should never happen...
783 */
784 if (x1 < x2)
785 {
786 wxASSERT_LEVEL_2(y1<y2);
787
788 MEMCHECK(pReg, pNextRect, pReg->rects);
789 pNextRect->x1 = x1;
790 pNextRect->y1 = y1;
791 pNextRect->x2 = x2;
792 pNextRect->y2 = y2;
793 pReg->numRects += 1;
794 pNextRect++;
795 wxASSERT_LEVEL_2(pReg->numRects <= pReg->size);
796 }
797
798 /*
799 * Need to advance the pointers. Shift the one that extends
800 * to the right the least, since the other still has a chance to
801 * overlap with that region's next rectangle, if you see what I mean.
802 */
803 if (r1->x2 < r2->x2)
804 {
805 r1++;
806 }
807 else if (r2->x2 < r1->x2)
808 {
809 r2++;
810 }
811 else
812 {
813 r1++;
814 r2++;
815 }
816 }
817 return 0; /* lint */
818 }
819
820 bool REGION::
XIntersectRegion(Region reg1,Region reg2,Region newReg)821 XIntersectRegion(
822 Region reg1,
823 Region reg2, /* source regions */
824 Region newReg) /* destination Region */
825 {
826 /* check for trivial reject */
827 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
828 (!EXTENTCHECK(®1->extents, ®2->extents)))
829 newReg->numRects = 0;
830 else
831 miRegionOp (newReg, reg1, reg2,
832 miIntersectO, NULL, NULL);
833
834 /*
835 * Can't alter newReg's extents before we call miRegionOp because
836 * it might be one of the source regions and miRegionOp depends
837 * on the extents of those regions being the same. Besides, this
838 * way there's no checking against rectangles that will be nuked
839 * due to coalescing, so we have to examine fewer rectangles.
840 */
841 miSetExtents(newReg);
842 return 1;
843 }
844
845 void REGION::
miRegionCopy(Region dstrgn,Region rgn)846 miRegionCopy(
847 Region dstrgn,
848 Region rgn)
849
850 {
851 if (dstrgn != rgn) /* don't want to copy to itself */
852 {
853 if (dstrgn->size < rgn->numRects)
854 {
855 if (dstrgn->rects)
856 {
857 BOX *prevRects = dstrgn->rects;
858
859 dstrgn->rects = (BOX *)
860 realloc((char *) dstrgn->rects,
861 (unsigned) rgn->numRects * (sizeof(BOX)));
862 if (!dstrgn->rects)
863 {
864 free(prevRects);
865 return;
866 }
867 }
868 dstrgn->size = rgn->numRects;
869 }
870 dstrgn->numRects = rgn->numRects;
871 dstrgn->extents.x1 = rgn->extents.x1;
872 dstrgn->extents.y1 = rgn->extents.y1;
873 dstrgn->extents.x2 = rgn->extents.x2;
874 dstrgn->extents.y2 = rgn->extents.y2;
875
876 memcpy((char *) dstrgn->rects, (char *) rgn->rects,
877 (int) (rgn->numRects * sizeof(BOX)));
878 }
879 }
880
881 /*======================================================================
882 * Generic Region Operator
883 *====================================================================*/
884
885 /*-
886 *-----------------------------------------------------------------------
887 * miCoalesce --
888 * Attempt to merge the boxes in the current band with those in the
889 * previous one. Used only by miRegionOp.
890 *
891 * Results:
892 * The new index for the previous band.
893 *
894 * Side Effects:
895 * If coalescing takes place:
896 * - rectangles in the previous band will have their y2 fields
897 * altered.
898 * - pReg->numRects will be decreased.
899 *
900 *-----------------------------------------------------------------------
901 */
902 /* static int*/
903 int REGION::
miCoalesce(Region pReg,int prevStart,int curStart)904 miCoalesce(
905 Region pReg, /* Region to coalesce */
906 int prevStart, /* Index of start of previous band */
907 int curStart) /* Index of start of current band */
908 {
909 BoxPtr pPrevBox; /* Current box in previous band */
910 BoxPtr pCurBox; /* Current box in current band */
911 BoxPtr pRegEnd; /* End of region */
912 int curNumRects; /* Number of rectangles in current
913 * band */
914 int prevNumRects; /* Number of rectangles in previous
915 * band */
916 int bandY1; /* Y1 coordinate for current band */
917
918 pRegEnd = &pReg->rects[pReg->numRects];
919
920 pPrevBox = &pReg->rects[prevStart];
921 prevNumRects = curStart - prevStart;
922
923 /*
924 * Figure out how many rectangles are in the current band. Have to do
925 * this because multiple bands could have been added in miRegionOp
926 * at the end when one region has been exhausted.
927 */
928 pCurBox = &pReg->rects[curStart];
929 bandY1 = pCurBox->y1;
930 for (curNumRects = 0;
931 (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
932 curNumRects++)
933 {
934 pCurBox++;
935 }
936
937 if (pCurBox != pRegEnd)
938 {
939 /*
940 * If more than one band was added, we have to find the start
941 * of the last band added so the next coalescing job can start
942 * at the right place... (given when multiple bands are added,
943 * this may be pointless -- see above).
944 */
945 pRegEnd--;
946 while (pRegEnd[-1].y1 == pRegEnd->y1)
947 {
948 pRegEnd--;
949 }
950 curStart = pRegEnd - pReg->rects;
951 pRegEnd = pReg->rects + pReg->numRects;
952 }
953
954 if ((curNumRects == prevNumRects) && (curNumRects != 0))
955 {
956 pCurBox -= curNumRects;
957 /*
958 * The bands may only be coalesced if the bottom of the previous
959 * matches the top scanline of the current.
960 */
961 if (pPrevBox->y2 == pCurBox->y1)
962 {
963 /*
964 * Make sure the bands have boxes in the same places. This
965 * assumes that boxes have been added in such a way that they
966 * cover the most area possible. I.e. two boxes in a band must
967 * have some horizontal space between them.
968 */
969 do
970 {
971 if ((pPrevBox->x1 != pCurBox->x1) ||
972 (pPrevBox->x2 != pCurBox->x2))
973 {
974 /*
975 * The bands don't line up so they can't be coalesced.
976 */
977 return (curStart);
978 }
979 pPrevBox++;
980 pCurBox++;
981 prevNumRects -= 1;
982 } while (prevNumRects != 0);
983
984 pReg->numRects -= curNumRects;
985 pCurBox -= curNumRects;
986 pPrevBox -= curNumRects;
987
988 /*
989 * The bands may be merged, so set the bottom y of each box
990 * in the previous band to that of the corresponding box in
991 * the current band.
992 */
993 do
994 {
995 pPrevBox->y2 = pCurBox->y2;
996 pPrevBox++;
997 pCurBox++;
998 curNumRects -= 1;
999 } while (curNumRects != 0);
1000
1001 /*
1002 * If only one band was added to the region, we have to backup
1003 * curStart to the start of the previous band.
1004 *
1005 * If more than one band was added to the region, copy the
1006 * other bands down. The assumption here is that the other bands
1007 * came from the same region as the current one and no further
1008 * coalescing can be done on them since it's all been done
1009 * already... curStart is already in the right place.
1010 */
1011 if (pCurBox == pRegEnd)
1012 {
1013 curStart = prevStart;
1014 }
1015 else
1016 {
1017 do
1018 {
1019 *pPrevBox++ = *pCurBox++;
1020 } while (pCurBox != pRegEnd);
1021 }
1022
1023 }
1024 }
1025 return (curStart);
1026 }
1027
1028 /*-
1029 *-----------------------------------------------------------------------
1030 * miRegionOp --
1031 * Apply an operation to two regions. Called by miUnion, miInverse,
1032 * miSubtract, miIntersect...
1033 *
1034 * Results:
1035 * None.
1036 *
1037 * Side Effects:
1038 * The new region is overwritten.
1039 *
1040 * Notes:
1041 * The idea behind this function is to view the two regions as sets.
1042 * Together they cover a rectangle of area that this function divides
1043 * into horizontal bands where points are covered only by one region
1044 * or by both. For the first case, the nonOverlapFunc is called with
1045 * each the band and the band's upper and lower extents. For the
1046 * second, the overlapFunc is called to process the entire band. It
1047 * is responsible for clipping the rectangles in the band, though
1048 * this function provides the boundaries.
1049 * At the end of each band, the new region is coalesced, if possible,
1050 * to reduce the number of rectangles in the region.
1051 *
1052 *-----------------------------------------------------------------------
1053 */
1054 /* static void*/
1055 void REGION::
miRegionOp(Region newReg,Region reg1,Region reg2,int (* overlapFunc)(Region pReg,BoxPtr r1,BoxPtr r1End,BoxPtr r2,BoxPtr r2End,wxCoord y1,wxCoord y2),int (* nonOverlap1Func)(Region pReg,BoxPtr r,BoxPtr rEnd,wxCoord y1,wxCoord y2),int (* nonOverlap2Func)(Region pReg,BoxPtr r,BoxPtr rEnd,wxCoord y1,wxCoord y2))1056 miRegionOp(
1057 Region newReg, /* Place to store result */
1058 Region reg1, /* First region in operation */
1059 Region reg2, /* 2d region in operation */
1060 int (*overlapFunc)(
1061 Region pReg,
1062 BoxPtr r1,
1063 BoxPtr r1End,
1064 BoxPtr r2,
1065 BoxPtr r2End,
1066 wxCoord y1,
1067 wxCoord y2), /* Function to call for over-
1068 * lapping bands */
1069 int (*nonOverlap1Func)(
1070 Region pReg,
1071 BoxPtr r,
1072 BoxPtr rEnd,
1073 wxCoord y1,
1074 wxCoord y2), /* Function to call for non-
1075 * overlapping bands in region
1076 * 1 */
1077 int (*nonOverlap2Func)(
1078 Region pReg,
1079 BoxPtr r,
1080 BoxPtr rEnd,
1081 wxCoord y1,
1082 wxCoord y2)) /* Function to call for non-
1083 * overlapping bands in region
1084 * 2 */
1085 {
1086 BoxPtr r1; /* Pointer into first region */
1087 BoxPtr r2; /* Pointer into 2d region */
1088 BoxPtr r1End; /* End of 1st region */
1089 BoxPtr r2End; /* End of 2d region */
1090 wxCoord ybot; /* Bottom of intersection */
1091 wxCoord ytop; /* Top of intersection */
1092 BoxPtr oldRects; /* Old rects for newReg */
1093 int prevBand; /* Index of start of
1094 * previous band in newReg */
1095 int curBand; /* Index of start of current
1096 * band in newReg */
1097 BoxPtr r1BandEnd; /* End of current band in r1 */
1098 BoxPtr r2BandEnd; /* End of current band in r2 */
1099 wxCoord top; /* Top of non-overlapping
1100 * band */
1101 wxCoord bot; /* Bottom of non-overlapping
1102 * band */
1103
1104 /*
1105 * Initialization:
1106 * set r1, r2, r1End and r2End appropriately, preserve the important
1107 * parts of the destination region until the end in case it's one of
1108 * the two source regions, then mark the "new" region empty, allocating
1109 * another array of rectangles for it to use.
1110 */
1111 r1 = reg1->rects;
1112 r2 = reg2->rects;
1113 r1End = r1 + reg1->numRects;
1114 r2End = r2 + reg2->numRects;
1115
1116 oldRects = newReg->rects;
1117
1118 EMPTY_REGION(newReg);
1119
1120 /*
1121 * Allocate a reasonable number of rectangles for the new region. The idea
1122 * is to allocate enough so the individual functions don't need to
1123 * reallocate and copy the array, which is time consuming, yet we don't
1124 * have to worry about using too much memory. I hope to be able to
1125 * nuke the realloc() at the end of this function eventually.
1126 */
1127 newReg->size = wxMax(reg1->numRects,reg2->numRects) * 2;
1128
1129 newReg->rects = (BoxPtr)malloc((unsigned) (sizeof(BoxRec) * newReg->size));
1130
1131 if (!newReg->rects)
1132 {
1133 newReg->size = 0;
1134 return;
1135 }
1136
1137 /*
1138 * Initialize ybot and ytop.
1139 * In the upcoming loop, ybot and ytop serve different functions depending
1140 * on whether the band being handled is an overlapping or non-overlapping
1141 * band.
1142 * In the case of a non-overlapping band (only one of the regions
1143 * has points in the band), ybot is the bottom of the most recent
1144 * intersection and thus clips the top of the rectangles in that band.
1145 * ytop is the top of the next intersection between the two regions and
1146 * serves to clip the bottom of the rectangles in the current band.
1147 * For an overlapping band (where the two regions intersect), ytop clips
1148 * the top of the rectangles of both regions and ybot clips the bottoms.
1149 */
1150 if (reg1->extents.y1 < reg2->extents.y1)
1151 ybot = reg1->extents.y1;
1152 else
1153 ybot = reg2->extents.y1;
1154
1155 /*
1156 * prevBand serves to mark the start of the previous band so rectangles
1157 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1158 * In the beginning, there is no previous band, so prevBand == curBand
1159 * (curBand is set later on, of course, but the first band will always
1160 * start at index 0). prevBand and curBand must be indices because of
1161 * the possible expansion, and resultant moving, of the new region's
1162 * array of rectangles.
1163 */
1164 prevBand = 0;
1165
1166 do
1167 {
1168 curBand = newReg->numRects;
1169
1170 /*
1171 * This algorithm proceeds one source-band (as opposed to a
1172 * destination band, which is determined by where the two regions
1173 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1174 * rectangle after the last one in the current band for their
1175 * respective regions.
1176 */
1177 r1BandEnd = r1;
1178 while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
1179 {
1180 r1BandEnd++;
1181 }
1182
1183 r2BandEnd = r2;
1184 while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
1185 {
1186 r2BandEnd++;
1187 }
1188
1189 /*
1190 * First handle the band that doesn't intersect, if any.
1191 *
1192 * Note that attention is restricted to one band in the
1193 * non-intersecting region at once, so if a region has n
1194 * bands between the current position and the next place it overlaps
1195 * the other, this entire loop will be passed through n times.
1196 */
1197 if (r1->y1 < r2->y1)
1198 {
1199 top = wxMax(r1->y1,ybot);
1200 bot = wxMin(r1->y2,r2->y1);
1201
1202 if ((top != bot) && (nonOverlap1Func != NULL))
1203 {
1204 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1205 }
1206
1207 ytop = r2->y1;
1208 }
1209 else if (r2->y1 < r1->y1)
1210 {
1211 top = wxMax(r2->y1,ybot);
1212 bot = wxMin(r2->y2,r1->y1);
1213
1214 if ((top != bot) && (nonOverlap2Func != NULL))
1215 {
1216 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1217 }
1218
1219 ytop = r1->y1;
1220 }
1221 else
1222 {
1223 ytop = r1->y1;
1224 }
1225
1226 /*
1227 * If any rectangles got added to the region, try and coalesce them
1228 * with rectangles from the previous band. Note we could just do
1229 * this test in miCoalesce, but some machines incur a not
1230 * inconsiderable cost for function calls, so...
1231 */
1232 if (newReg->numRects != curBand)
1233 {
1234 prevBand = miCoalesce (newReg, prevBand, curBand);
1235 }
1236
1237 /*
1238 * Now see if we've hit an intersecting band. The two bands only
1239 * intersect if ybot > ytop
1240 */
1241 ybot = wxMin(r1->y2, r2->y2);
1242 curBand = newReg->numRects;
1243 if (ybot > ytop)
1244 {
1245 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1246
1247 }
1248
1249 if (newReg->numRects != curBand)
1250 {
1251 prevBand = miCoalesce (newReg, prevBand, curBand);
1252 }
1253
1254 /*
1255 * If we've finished with a band (y2 == ybot) we skip forward
1256 * in the region to the next band.
1257 */
1258 if (r1->y2 == ybot)
1259 {
1260 r1 = r1BandEnd;
1261 }
1262 if (r2->y2 == ybot)
1263 {
1264 r2 = r2BandEnd;
1265 }
1266 } while ((r1 != r1End) && (r2 != r2End));
1267
1268 /*
1269 * Deal with whichever region still has rectangles left.
1270 */
1271 curBand = newReg->numRects;
1272 if (r1 != r1End)
1273 {
1274 if (nonOverlap1Func != NULL)
1275 {
1276 do
1277 {
1278 r1BandEnd = r1;
1279 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
1280 {
1281 r1BandEnd++;
1282 }
1283 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1284 wxMax(r1->y1,ybot), r1->y2);
1285 r1 = r1BandEnd;
1286 } while (r1 != r1End);
1287 }
1288 }
1289 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1290 {
1291 do
1292 {
1293 r2BandEnd = r2;
1294 while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
1295 {
1296 r2BandEnd++;
1297 }
1298 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1299 wxMax(r2->y1,ybot), r2->y2);
1300 r2 = r2BandEnd;
1301 } while (r2 != r2End);
1302 }
1303
1304 if (newReg->numRects != curBand)
1305 {
1306 (void) miCoalesce (newReg, prevBand, curBand);
1307 }
1308
1309 /*
1310 * A bit of cleanup. To keep regions from growing without bound,
1311 * we shrink the array of rectangles to match the new number of
1312 * rectangles in the region. This never goes to 0, however...
1313 *
1314 * Only do this stuff if the number of rectangles allocated is more than
1315 * twice the number of rectangles in the region (a simple optimization...).
1316 */
1317 if (newReg->numRects < (newReg->size >> 1))
1318 {
1319 if (REGION_NOT_EMPTY(newReg))
1320 {
1321 BoxPtr prev_rects = newReg->rects;
1322 newReg->size = newReg->numRects;
1323 newReg->rects = (BoxPtr) realloc ((char *) newReg->rects,
1324 (unsigned) (sizeof(BoxRec) * newReg->size));
1325 if (! newReg->rects)
1326 newReg->rects = prev_rects;
1327 }
1328 else
1329 {
1330 /*
1331 * No point in doing the extra work involved in an realloc if
1332 * the region is empty
1333 */
1334 newReg->size = 1;
1335 free((char *) newReg->rects);
1336 newReg->rects = (BoxPtr) malloc(sizeof(BoxRec));
1337 }
1338 }
1339 free ((char *) oldRects);
1340 return;
1341 }
1342
1343 /*======================================================================
1344 * Region Union
1345 *====================================================================*/
1346
1347 /*-
1348 *-----------------------------------------------------------------------
1349 * miUnionNonO --
1350 * Handle a non-overlapping band for the union operation. Just
1351 * Adds the rectangles into the region. Doesn't have to check for
1352 * subsumption or anything.
1353 *
1354 * Results:
1355 * None.
1356 *
1357 * Side Effects:
1358 * pReg->numRects is incremented and the final rectangles overwritten
1359 * with the rectangles we're passed.
1360 *
1361 *-----------------------------------------------------------------------
1362 */
1363 /* static void*/
1364 int REGION::
miUnionNonO(Region pReg,BoxPtr r,BoxPtr rEnd,wxCoord y1,wxCoord y2)1365 miUnionNonO (
1366 Region pReg,
1367 BoxPtr r,
1368 BoxPtr rEnd,
1369 wxCoord y1,
1370 wxCoord y2)
1371 {
1372 BoxPtr pNextRect;
1373
1374 pNextRect = &pReg->rects[pReg->numRects];
1375
1376 wxASSERT_LEVEL_2(y1 < y2);
1377
1378 while (r != rEnd)
1379 {
1380 wxASSERT_LEVEL_2(r->x1 < r->x2);
1381 MEMCHECK(pReg, pNextRect, pReg->rects);
1382 pNextRect->x1 = r->x1;
1383 pNextRect->y1 = y1;
1384 pNextRect->x2 = r->x2;
1385 pNextRect->y2 = y2;
1386 pReg->numRects += 1;
1387 pNextRect++;
1388
1389 wxASSERT_LEVEL_2(pReg->numRects<=pReg->size);
1390 r++;
1391 }
1392 return 0; /* lint */
1393 }
1394
1395
1396 /*-
1397 *-----------------------------------------------------------------------
1398 * miUnionO --
1399 * Handle an overlapping band for the union operation. Picks the
1400 * left-most rectangle each time and merges it into the region.
1401 *
1402 * Results:
1403 * None.
1404 *
1405 * Side Effects:
1406 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1407 * be changed.
1408 *
1409 *-----------------------------------------------------------------------
1410 */
1411
1412 /* static void*/
1413 int REGION::
miUnionO(Region pReg,BoxPtr r1,BoxPtr r1End,BoxPtr r2,BoxPtr r2End,wxCoord y1,wxCoord y2)1414 miUnionO (
1415 Region pReg,
1416 BoxPtr r1,
1417 BoxPtr r1End,
1418 BoxPtr r2,
1419 BoxPtr r2End,
1420 wxCoord y1,
1421 wxCoord y2)
1422 {
1423 BoxPtr pNextRect;
1424
1425 pNextRect = &pReg->rects[pReg->numRects];
1426
1427 #define MERGERECT(r) \
1428 if ((pReg->numRects != 0) && \
1429 (pNextRect[-1].y1 == y1) && \
1430 (pNextRect[-1].y2 == y2) && \
1431 (pNextRect[-1].x2 >= r->x1)) \
1432 { \
1433 if (pNextRect[-1].x2 < r->x2) \
1434 { \
1435 pNextRect[-1].x2 = r->x2; \
1436 wxASSERT_LEVEL_2(pNextRect[-1].x1<pNextRect[-1].x2); \
1437 } \
1438 } \
1439 else \
1440 { \
1441 MEMCHECK(pReg, pNextRect, pReg->rects); \
1442 pNextRect->y1 = y1; \
1443 pNextRect->y2 = y2; \
1444 pNextRect->x1 = r->x1; \
1445 pNextRect->x2 = r->x2; \
1446 pReg->numRects += 1; \
1447 pNextRect += 1; \
1448 } \
1449 wxASSERT_LEVEL_2(pReg->numRects<=pReg->size);\
1450 r++;
1451
1452 wxASSERT_LEVEL_2 (y1<y2);
1453 while ((r1 != r1End) && (r2 != r2End))
1454 {
1455 if (r1->x1 < r2->x1)
1456 {
1457 MERGERECT(r1);
1458 }
1459 else
1460 {
1461 MERGERECT(r2);
1462 }
1463 }
1464
1465 if (r1 != r1End)
1466 {
1467 do
1468 {
1469 MERGERECT(r1);
1470 } while (r1 != r1End);
1471 }
1472 else while (r2 != r2End)
1473 {
1474 MERGERECT(r2);
1475 }
1476 return 0; /* lint */
1477 }
1478
1479 bool REGION::
XUnionRegion(Region reg1,Region reg2,Region newReg)1480 XUnionRegion(
1481 Region reg1,
1482 Region reg2, /* source regions */
1483 Region newReg) /* destination Region */
1484 {
1485 /* checks all the simple cases */
1486
1487 /*
1488 * Region 1 and 2 are the same or region 1 is empty
1489 */
1490 if ( (reg1 == reg2) || (!(reg1->numRects)) )
1491 {
1492 if (newReg != reg2)
1493 miRegionCopy(newReg, reg2);
1494 return 1;
1495 }
1496
1497 /*
1498 * if nothing to union (region 2 empty)
1499 */
1500 if (!(reg2->numRects))
1501 {
1502 if (newReg != reg1)
1503 miRegionCopy(newReg, reg1);
1504 return 1;
1505 }
1506
1507 /*
1508 * Region 1 completely subsumes region 2
1509 */
1510 if ((reg1->numRects == 1) &&
1511 (reg1->extents.x1 <= reg2->extents.x1) &&
1512 (reg1->extents.y1 <= reg2->extents.y1) &&
1513 (reg1->extents.x2 >= reg2->extents.x2) &&
1514 (reg1->extents.y2 >= reg2->extents.y2))
1515 {
1516 if (newReg != reg1)
1517 miRegionCopy(newReg, reg1);
1518 return 1;
1519 }
1520
1521 /*
1522 * Region 2 completely subsumes region 1
1523 */
1524 if ((reg2->numRects == 1) &&
1525 (reg2->extents.x1 <= reg1->extents.x1) &&
1526 (reg2->extents.y1 <= reg1->extents.y1) &&
1527 (reg2->extents.x2 >= reg1->extents.x2) &&
1528 (reg2->extents.y2 >= reg1->extents.y2))
1529 {
1530 if (newReg != reg2)
1531 miRegionCopy(newReg, reg2);
1532 return 1;
1533 }
1534
1535 miRegionOp (newReg, reg1, reg2, miUnionO,
1536 miUnionNonO, miUnionNonO);
1537
1538 newReg->extents.x1 = wxMin(reg1->extents.x1, reg2->extents.x1);
1539 newReg->extents.y1 = wxMin(reg1->extents.y1, reg2->extents.y1);
1540 newReg->extents.x2 = wxMax(reg1->extents.x2, reg2->extents.x2);
1541 newReg->extents.y2 = wxMax(reg1->extents.y2, reg2->extents.y2);
1542
1543 return 1;
1544 }
1545
1546 /*======================================================================
1547 * Region Subtraction
1548 *====================================================================*/
1549
1550 /*-
1551 *-----------------------------------------------------------------------
1552 * miSubtractNonO --
1553 * Deal with non-overlapping band for subtraction. Any parts from
1554 * region 2 we discard. Anything from region 1 we add to the region.
1555 *
1556 * Results:
1557 * None.
1558 *
1559 * Side Effects:
1560 * pReg may be affected.
1561 *
1562 *-----------------------------------------------------------------------
1563 */
1564 /* static void*/
1565 int REGION::
miSubtractNonO1(Region pReg,BoxPtr r,BoxPtr rEnd,wxCoord y1,wxCoord y2)1566 miSubtractNonO1 (
1567 Region pReg,
1568 BoxPtr r,
1569 BoxPtr rEnd,
1570 wxCoord y1,
1571 wxCoord y2)
1572 {
1573 BoxPtr pNextRect;
1574
1575 pNextRect = &pReg->rects[pReg->numRects];
1576
1577 wxASSERT_LEVEL_2(y1<y2);
1578
1579 while (r != rEnd)
1580 {
1581 wxASSERT_LEVEL_2(r->x1<r->x2);
1582 MEMCHECK(pReg, pNextRect, pReg->rects);
1583 pNextRect->x1 = r->x1;
1584 pNextRect->y1 = y1;
1585 pNextRect->x2 = r->x2;
1586 pNextRect->y2 = y2;
1587 pReg->numRects += 1;
1588 pNextRect++;
1589
1590 wxASSERT_LEVEL_2(pReg->numRects <= pReg->size);
1591
1592 r++;
1593 }
1594 return 0; /* lint */
1595 }
1596
1597 /*-
1598 *-----------------------------------------------------------------------
1599 * miSubtractO --
1600 * Overlapping band subtraction. x1 is the left-most point not yet
1601 * checked.
1602 *
1603 * Results:
1604 * None.
1605 *
1606 * Side Effects:
1607 * pReg may have rectangles added to it.
1608 *
1609 *-----------------------------------------------------------------------
1610 */
1611 /* static void*/
1612 int REGION::
miSubtractO(Region pReg,BoxPtr r1,BoxPtr r1End,BoxPtr r2,BoxPtr r2End,wxCoord y1,wxCoord y2)1613 miSubtractO (
1614 Region pReg,
1615 BoxPtr r1,
1616 BoxPtr r1End,
1617 BoxPtr r2,
1618 BoxPtr r2End,
1619 wxCoord y1,
1620 wxCoord y2)
1621 {
1622 BoxPtr pNextRect;
1623 int x1;
1624
1625 x1 = r1->x1;
1626
1627 wxASSERT_LEVEL_2(y1<y2);
1628 pNextRect = &pReg->rects[pReg->numRects];
1629
1630 while ((r1 != r1End) && (r2 != r2End))
1631 {
1632 if (r2->x2 <= x1)
1633 {
1634 /*
1635 * Subtrahend missed the boat: go to next subtrahend.
1636 */
1637 r2++;
1638 }
1639 else if (r2->x1 <= x1)
1640 {
1641 /*
1642 * Subtrahend precedes minuend: nuke left edge of minuend.
1643 */
1644 x1 = r2->x2;
1645 if (x1 >= r1->x2)
1646 {
1647 /*
1648 * Minuend completely covered: advance to next minuend and
1649 * reset left fence to edge of new minuend.
1650 */
1651 r1++;
1652 if (r1 != r1End)
1653 x1 = r1->x1;
1654 }
1655 else
1656 {
1657 /*
1658 * Subtrahend now used up since it doesn't extend beyond
1659 * minuend
1660 */
1661 r2++;
1662 }
1663 }
1664 else if (r2->x1 < r1->x2)
1665 {
1666 /*
1667 * Left part of subtrahend covers part of minuend: add uncovered
1668 * part of minuend to region and skip to next subtrahend.
1669 */
1670 wxASSERT_LEVEL_2(x1<r2->x1);
1671 MEMCHECK(pReg, pNextRect, pReg->rects);
1672 pNextRect->x1 = x1;
1673 pNextRect->y1 = y1;
1674 pNextRect->x2 = r2->x1;
1675 pNextRect->y2 = y2;
1676 pReg->numRects += 1;
1677 pNextRect++;
1678
1679 wxASSERT_LEVEL_2(pReg->numRects<=pReg->size);
1680
1681 x1 = r2->x2;
1682 if (x1 >= r1->x2)
1683 {
1684 /*
1685 * Minuend used up: advance to new...
1686 */
1687 r1++;
1688 if (r1 != r1End)
1689 x1 = r1->x1;
1690 }
1691 else
1692 {
1693 /*
1694 * Subtrahend used up
1695 */
1696 r2++;
1697 }
1698 }
1699 else
1700 {
1701 /*
1702 * Minuend used up: add any remaining piece before advancing.
1703 */
1704 if (r1->x2 > x1)
1705 {
1706 MEMCHECK(pReg, pNextRect, pReg->rects);
1707 pNextRect->x1 = x1;
1708 pNextRect->y1 = y1;
1709 pNextRect->x2 = r1->x2;
1710 pNextRect->y2 = y2;
1711 pReg->numRects += 1;
1712 pNextRect++;
1713 wxASSERT_LEVEL_2(pReg->numRects<=pReg->size);
1714 }
1715 r1++;
1716 if (r1 != r1End)
1717 x1 = r1->x1;
1718 }
1719 }
1720
1721 /*
1722 * Add remaining minuend rectangles to region.
1723 */
1724 while (r1 != r1End)
1725 {
1726 wxASSERT_LEVEL_2(x1<r1->x2);
1727 MEMCHECK(pReg, pNextRect, pReg->rects);
1728 pNextRect->x1 = x1;
1729 pNextRect->y1 = y1;
1730 pNextRect->x2 = r1->x2;
1731 pNextRect->y2 = y2;
1732 pReg->numRects += 1;
1733 pNextRect++;
1734
1735 wxASSERT_LEVEL_2(pReg->numRects<=pReg->size);
1736
1737 r1++;
1738 if (r1 != r1End)
1739 {
1740 x1 = r1->x1;
1741 }
1742 }
1743 return 0; /* lint */
1744 }
1745
1746 /*-
1747 *-----------------------------------------------------------------------
1748 * miSubtract --
1749 * Subtract regS from regM and leave the result in regD.
1750 * S stands for subtrahend, M for minuend and D for difference.
1751 *
1752 * Results:
1753 * true.
1754 *
1755 * Side Effects:
1756 * regD is overwritten.
1757 *
1758 *-----------------------------------------------------------------------
1759 */
1760
XSubtractRegion(Region regM,Region regS,Region regD)1761 bool REGION::XSubtractRegion(Region regM, Region regS, Region regD)
1762 {
1763 /* check for trivial reject */
1764 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
1765 (!EXTENTCHECK(®M->extents, ®S->extents)) )
1766 {
1767 miRegionCopy(regD, regM);
1768 return true;
1769 }
1770
1771 miRegionOp (regD, regM, regS, miSubtractO,
1772 miSubtractNonO1, NULL);
1773
1774 /*
1775 * Can't alter newReg's extents before we call miRegionOp because
1776 * it might be one of the source regions and miRegionOp depends
1777 * on the extents of those regions being the unaltered. Besides, this
1778 * way there's no checking against rectangles that will be nuked
1779 * due to coalescing, so we have to examine fewer rectangles.
1780 */
1781 miSetExtents (regD);
1782 return true;
1783 }
1784
XXorRegion(Region sra,Region srb,Region dr)1785 bool REGION::XXorRegion(Region sra, Region srb, Region dr)
1786 {
1787 Region tra = XCreateRegion();
1788
1789 wxCHECK_MSG( tra, false, wxT("region not created") );
1790
1791 Region trb = XCreateRegion();
1792
1793 wxCHECK_MSG( trb, false, wxT("region not created") );
1794
1795 (void) XSubtractRegion(sra,srb,tra);
1796 (void) XSubtractRegion(srb,sra,trb);
1797 (void) XUnionRegion(tra,trb,dr);
1798 XDestroyRegion(tra);
1799 XDestroyRegion(trb);
1800 return 0;
1801 }
1802
1803 /*
1804 * Check to see if the region is empty. Assumes a region is passed
1805 * as a parameter
1806 */
XEmptyRegion(Region r)1807 bool REGION::XEmptyRegion(Region r)
1808 {
1809 if( r->numRects == 0 ) return true;
1810 else return false;
1811 }
1812
1813 /*
1814 * Check to see if two regions are equal
1815 */
XEqualRegion(Region r1,Region r2)1816 bool REGION::XEqualRegion(Region r1, Region r2)
1817 {
1818 int i;
1819
1820 if( r1->numRects != r2->numRects ) return false;
1821 else if( r1->numRects == 0 ) return true;
1822 else if ( r1->extents.x1 != r2->extents.x1 ) return false;
1823 else if ( r1->extents.x2 != r2->extents.x2 ) return false;
1824 else if ( r1->extents.y1 != r2->extents.y1 ) return false;
1825 else if ( r1->extents.y2 != r2->extents.y2 ) return false;
1826 else for( i=0; i < r1->numRects; i++ ) {
1827 if ( r1->rects[i].x1 != r2->rects[i].x1 ) return false;
1828 else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return false;
1829 else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return false;
1830 else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return false;
1831 }
1832 return true;
1833 }
1834
XPointInRegion(Region pRegion,int x,int y)1835 bool REGION::XPointInRegion(Region pRegion, int x, int y)
1836 {
1837 int i;
1838
1839 if (pRegion->numRects == 0)
1840 return false;
1841 if (!INBOX(pRegion->extents, x, y))
1842 return false;
1843 for (i=0; i<pRegion->numRects; i++)
1844 {
1845 if (INBOX (pRegion->rects[i], x, y))
1846 return true;
1847 }
1848 return false;
1849 }
1850
XRectInRegion(Region region,int rx,int ry,unsigned int rwidth,unsigned int rheight)1851 wxRegionContain REGION::XRectInRegion(Region region,
1852 int rx, int ry,
1853 unsigned int rwidth,
1854 unsigned int rheight)
1855 {
1856 BoxPtr pbox;
1857 BoxPtr pboxEnd;
1858 Box rect;
1859 BoxPtr prect = ▭
1860 int partIn, partOut;
1861
1862 prect->x1 = rx;
1863 prect->y1 = ry;
1864 prect->x2 = rwidth + rx;
1865 prect->y2 = rheight + ry;
1866
1867 /* this is (just) a useful optimization */
1868 if ((region->numRects == 0) || !EXTENTCHECK(®ion->extents, prect))
1869 return(wxOutRegion);
1870
1871 partOut = false;
1872 partIn = false;
1873
1874 /* can stop when both partOut and partIn are true, or we reach prect->y2 */
1875 for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1876 pbox < pboxEnd;
1877 pbox++)
1878 {
1879
1880 if (pbox->y2 <= ry)
1881 continue; /* getting up to speed or skipping remainder of band */
1882
1883 if (pbox->y1 > ry)
1884 {
1885 partOut = true; /* missed part of rectangle above */
1886 if (partIn || (pbox->y1 >= prect->y2))
1887 break;
1888 ry = pbox->y1; /* x guaranteed to be == prect->x1 */
1889 }
1890
1891 if (pbox->x2 <= rx)
1892 continue; /* not far enough over yet */
1893
1894 if (pbox->x1 > rx)
1895 {
1896 partOut = true; /* missed part of rectangle to left */
1897 if (partIn)
1898 break;
1899 }
1900
1901 if (pbox->x1 < prect->x2)
1902 {
1903 partIn = true; /* definitely overlap */
1904 if (partOut)
1905 break;
1906 }
1907
1908 if (pbox->x2 >= prect->x2)
1909 {
1910 ry = pbox->y2; /* finished with this band */
1911 if (ry >= prect->y2)
1912 break;
1913 rx = prect->x1; /* reset x out to left again */
1914 } else
1915 {
1916 /*
1917 * Because boxes in a band are maximal width, if the first box
1918 * to overlap the rectangle doesn't completely cover it in that
1919 * band, the rectangle must be partially out, since some of it
1920 * will be uncovered in that band. partIn will have been set true
1921 * by now...
1922 */
1923 break;
1924 }
1925
1926 }
1927
1928 return(partIn ? ((ry < prect->y2) ? wxPartRegion : wxInRegion) :
1929 wxOutRegion);
1930 }
1931