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