/[pcsx2_0.9.7]/branch/r3113_0.9.7_beta/3rdparty/wxWidgets/src/generic/regiong.cpp
ViewVC logotype

Annotation of /branch/r3113_0.9.7_beta/3rdparty/wxWidgets/src/generic/regiong.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

  ViewVC Help
Powered by ViewVC 1.1.22