Removed W->A from DEFWND_ImmIsUIMessageW.
[wine] / dlls / gdi / region.c
1 /*
2  * GDI region objects. Shamelessly ripped out from the X11 distribution
3  * Thanks for the nice licence.
4  *
5  * Copyright 1993, 1994, 1995 Alexandre Julliard
6  * Modifications and additions: Copyright 1998 Huw Davies
7  *                                        1999 Alex Korobka
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with this library; if not, write to the Free Software
21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
22  */
23
24 /************************************************************************
25
26 Copyright (c) 1987, 1988  X Consortium
27
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
34
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
37
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
48
49
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
51
52                         All Rights Reserved
53
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
61
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
68 SOFTWARE.
69
70 ************************************************************************/
71 /*
72  * The functions in this file implement the Region abstraction, similar to one
73  * used in the X11 sample server. A Region is simply an area, as the name
74  * implies, and is implemented as a "y-x-banded" array of rectangles. To
75  * explain: Each Region is made up of a certain number of rectangles sorted
76  * by y coordinate first, and then by x coordinate.
77  *
78  * Furthermore, the rectangles are banded such that every rectangle with a
79  * given upper-left y coordinate (y1) will have the same lower-right y
80  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81  * will span the entire vertical distance of the band. This means that some
82  * areas that could be merged into a taller rectangle will be represented as
83  * several shorter rectangles to account for shorter rectangles to its left
84  * or right but within its "vertical scope".
85  *
86  * An added constraint on the rectangles is that they must cover as much
87  * horizontal area as possible. E.g. no two rectangles in a band are allowed
88  * to touch.
89  *
90  * Whenever possible, bands will be merged together to cover a greater vertical
91  * distance (and thus reduce the number of rectangles). Two bands can be merged
92  * only if the bottom of one touches the top of the other and they have
93  * rectangles in the same places (of the same width, of course). This maintains
94  * the y-x-banding that's so nice to have...
95  */
96
97 #include <stdarg.h>
98 #include <stdlib.h>
99 #include <string.h>
100 #include "windef.h"
101 #include "winbase.h"
102 #include "wingdi.h"
103 #include "gdi.h"
104 #include "gdi_private.h"
105 #include "wine/debug.h"
106
107 WINE_DEFAULT_DEBUG_CHANNEL(region);
108
109 typedef struct {
110     INT size;
111     INT numRects;
112     RECT *rects;
113     RECT extents;
114 } WINEREGION;
115
116   /* GDI logical region object */
117 typedef struct
118 {
119     GDIOBJHDR   header;
120     WINEREGION  *rgn;
121 } RGNOBJ;
122
123
124 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, void *obj, HDC hdc );
125 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj );
126
127 static const struct gdi_obj_funcs region_funcs =
128 {
129     REGION_SelectObject,  /* pSelectObject */
130     NULL,                 /* pGetObject16 */
131     NULL,                 /* pGetObjectA */
132     NULL,                 /* pGetObjectW */
133     NULL,                 /* pUnrealizeObject */
134     REGION_DeleteObject   /* pDeleteObject */
135 };
136
137 /*  1 if two RECTs overlap.
138  *  0 if two RECTs do not overlap.
139  */
140 #define EXTENTCHECK(r1, r2) \
141         ((r1)->right > (r2)->left && \
142          (r1)->left < (r2)->right && \
143          (r1)->bottom > (r2)->top && \
144          (r1)->top < (r2)->bottom)
145
146 /*
147  *   Check to see if there is enough memory in the present region.
148  */
149
150 static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
151     if (reg->numRects >= (reg->size - 1)) {
152         *firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
153         if (*firstrect == 0)
154             return 0;
155         reg->size *= 2;
156         *rect = (*firstrect)+reg->numRects;
157     }
158     return 1;
159 }
160
161 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
162
163 #define EMPTY_REGION(pReg) { \
164     (pReg)->numRects = 0; \
165     (pReg)->extents.left = (pReg)->extents.top = 0; \
166     (pReg)->extents.right = (pReg)->extents.bottom = 0; \
167  }
168
169 #define REGION_NOT_EMPTY(pReg) pReg->numRects
170
171 #define INRECT(r, x, y) \
172       ( ( ((r).right >  x)) && \
173         ( ((r).left <= x)) && \
174         ( ((r).bottom >  y)) && \
175         ( ((r).top <= y)) )
176
177
178 /*
179  * number of points to buffer before sending them off
180  * to scanlines() :  Must be an even number
181  */
182 #define NUMPTSTOBUFFER 200
183
184 /*
185  * used to allocate buffers for points and link
186  * the buffers together
187  */
188
189 typedef struct _POINTBLOCK {
190     POINT pts[NUMPTSTOBUFFER];
191     struct _POINTBLOCK *next;
192 } POINTBLOCK;
193
194
195
196 /*
197  *     This file contains a few macros to help track
198  *     the edge of a filled object.  The object is assumed
199  *     to be filled in scanline order, and thus the
200  *     algorithm used is an extension of Bresenham's line
201  *     drawing algorithm which assumes that y is always the
202  *     major axis.
203  *     Since these pieces of code are the same for any filled shape,
204  *     it is more convenient to gather the library in one
205  *     place, but since these pieces of code are also in
206  *     the inner loops of output primitives, procedure call
207  *     overhead is out of the question.
208  *     See the author for a derivation if needed.
209  */
210
211
212 /*
213  *  In scan converting polygons, we want to choose those pixels
214  *  which are inside the polygon.  Thus, we add .5 to the starting
215  *  x coordinate for both left and right edges.  Now we choose the
216  *  first pixel which is inside the pgon for the left edge and the
217  *  first pixel which is outside the pgon for the right edge.
218  *  Draw the left pixel, but not the right.
219  *
220  *  How to add .5 to the starting x coordinate:
221  *      If the edge is moving to the right, then subtract dy from the
222  *  error term from the general form of the algorithm.
223  *      If the edge is moving to the left, then add dy to the error term.
224  *
225  *  The reason for the difference between edges moving to the left
226  *  and edges moving to the right is simple:  If an edge is moving
227  *  to the right, then we want the algorithm to flip immediately.
228  *  If it is moving to the left, then we don't want it to flip until
229  *  we traverse an entire pixel.
230  */
231 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
232     int dx;      /* local storage */ \
233 \
234     /* \
235      *  if the edge is horizontal, then it is ignored \
236      *  and assumed not to be processed.  Otherwise, do this stuff. \
237      */ \
238     if ((dy) != 0) { \
239         xStart = (x1); \
240         dx = (x2) - xStart; \
241         if (dx < 0) { \
242             m = dx / (dy); \
243             m1 = m - 1; \
244             incr1 = -2 * dx + 2 * (dy) * m1; \
245             incr2 = -2 * dx + 2 * (dy) * m; \
246             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
247         } else { \
248             m = dx / (dy); \
249             m1 = m + 1; \
250             incr1 = 2 * dx - 2 * (dy) * m1; \
251             incr2 = 2 * dx - 2 * (dy) * m; \
252             d = -2 * m * (dy) + 2 * dx; \
253         } \
254     } \
255 }
256
257 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
258     if (m1 > 0) { \
259         if (d > 0) { \
260             minval += m1; \
261             d += incr1; \
262         } \
263         else { \
264             minval += m; \
265             d += incr2; \
266         } \
267     } else {\
268         if (d >= 0) { \
269             minval += m1; \
270             d += incr1; \
271         } \
272         else { \
273             minval += m; \
274             d += incr2; \
275         } \
276     } \
277 }
278
279 /*
280  *     This structure contains all of the information needed
281  *     to run the bresenham algorithm.
282  *     The variables may be hardcoded into the declarations
283  *     instead of using this structure to make use of
284  *     register declarations.
285  */
286 typedef struct {
287     INT minor_axis;     /* minor axis        */
288     INT d;              /* decision variable */
289     INT m, m1;          /* slope and slope+1 */
290     INT incr1, incr2;   /* error increments */
291 } BRESINFO;
292
293
294 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
295         BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
296                      bres.m, bres.m1, bres.incr1, bres.incr2)
297
298 #define BRESINCRPGONSTRUCT(bres) \
299         BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
300
301
302
303 /*
304  *     These are the data structures needed to scan
305  *     convert regions.  Two different scan conversion
306  *     methods are available -- the even-odd method, and
307  *     the winding number method.
308  *     The even-odd rule states that a point is inside
309  *     the polygon if a ray drawn from that point in any
310  *     direction will pass through an odd number of
311  *     path segments.
312  *     By the winding number rule, a point is decided
313  *     to be inside the polygon if a ray drawn from that
314  *     point in any direction passes through a different
315  *     number of clockwise and counter-clockwise path
316  *     segments.
317  *
318  *     These data structures are adapted somewhat from
319  *     the algorithm in (Foley/Van Dam) for scan converting
320  *     polygons.
321  *     The basic algorithm is to start at the top (smallest y)
322  *     of the polygon, stepping down to the bottom of
323  *     the polygon by incrementing the y coordinate.  We
324  *     keep a list of edges which the current scanline crosses,
325  *     sorted by x.  This list is called the Active Edge Table (AET)
326  *     As we change the y-coordinate, we update each entry in
327  *     in the active edge table to reflect the edges new xcoord.
328  *     This list must be sorted at each scanline in case
329  *     two edges intersect.
330  *     We also keep a data structure known as the Edge Table (ET),
331  *     which keeps track of all the edges which the current
332  *     scanline has not yet reached.  The ET is basically a
333  *     list of ScanLineList structures containing a list of
334  *     edges which are entered at a given scanline.  There is one
335  *     ScanLineList per scanline at which an edge is entered.
336  *     When we enter a new edge, we move it from the ET to the AET.
337  *
338  *     From the AET, we can implement the even-odd rule as in
339  *     (Foley/Van Dam).
340  *     The winding number rule is a little trickier.  We also
341  *     keep the EdgeTableEntries in the AET linked by the
342  *     nextWETE (winding EdgeTableEntry) link.  This allows
343  *     the edges to be linked just as before for updating
344  *     purposes, but only uses the edges linked by the nextWETE
345  *     link as edges representing spans of the polygon to
346  *     drawn (as with the even-odd rule).
347  */
348
349 /*
350  * for the winding number rule
351  */
352 #define CLOCKWISE          1
353 #define COUNTERCLOCKWISE  -1
354
355 typedef struct _EdgeTableEntry {
356      INT ymax;           /* ycoord at which we exit this edge. */
357      BRESINFO bres;        /* Bresenham info to run the edge     */
358      struct _EdgeTableEntry *next;       /* next in the list     */
359      struct _EdgeTableEntry *back;       /* for insertion sort   */
360      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
361      int ClockWise;        /* flag for winding number rule       */
362 } EdgeTableEntry;
363
364
365 typedef struct _ScanLineList{
366      INT scanline;            /* the scanline represented */
367      EdgeTableEntry *edgelist;  /* header node              */
368      struct _ScanLineList *next;  /* next in the list       */
369 } ScanLineList;
370
371
372 typedef struct {
373      INT ymax;               /* ymax for the polygon     */
374      INT ymin;               /* ymin for the polygon     */
375      ScanLineList scanlines;   /* header node              */
376 } EdgeTable;
377
378
379 /*
380  * Here is a struct to help with storage allocation
381  * so we can allocate a big chunk at a time, and then take
382  * pieces from this heap when we need to.
383  */
384 #define SLLSPERBLOCK 25
385
386 typedef struct _ScanLineListBlock {
387      ScanLineList SLLs[SLLSPERBLOCK];
388      struct _ScanLineListBlock *next;
389 } ScanLineListBlock;
390
391
392 /*
393  *
394  *     a few macros for the inner loops of the fill code where
395  *     performance considerations don't allow a procedure call.
396  *
397  *     Evaluate the given edge at the given scanline.
398  *     If the edge has expired, then we leave it and fix up
399  *     the active edge table; otherwise, we increment the
400  *     x value to be ready for the next scanline.
401  *     The winding number rule is in effect, so we must notify
402  *     the caller when the edge has been removed so he
403  *     can reorder the Winding Active Edge Table.
404  */
405 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
406    if (pAET->ymax == y) {          /* leaving this edge */ \
407       pPrevAET->next = pAET->next; \
408       pAET = pPrevAET->next; \
409       fixWAET = 1; \
410       if (pAET) \
411          pAET->back = pPrevAET; \
412    } \
413    else { \
414       BRESINCRPGONSTRUCT(pAET->bres); \
415       pPrevAET = pAET; \
416       pAET = pAET->next; \
417    } \
418 }
419
420
421 /*
422  *     Evaluate the given edge at the given scanline.
423  *     If the edge has expired, then we leave it and fix up
424  *     the active edge table; otherwise, we increment the
425  *     x value to be ready for the next scanline.
426  *     The even-odd rule is in effect.
427  */
428 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
429    if (pAET->ymax == y) {          /* leaving this edge */ \
430       pPrevAET->next = pAET->next; \
431       pAET = pPrevAET->next; \
432       if (pAET) \
433          pAET->back = pPrevAET; \
434    } \
435    else { \
436       BRESINCRPGONSTRUCT(pAET->bres); \
437       pPrevAET = pAET; \
438       pAET = pAET->next; \
439    } \
440 }
441
442 typedef void (*voidProcp)();
443
444 /* Note the parameter order is different from the X11 equivalents */
445
446 static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
447 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
449 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
450 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
451 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
452
453 #define RGN_DEFAULT_RECTS       2
454
455
456 /***********************************************************************
457  *            get_region_type
458  */
459 inline static INT get_region_type( const RGNOBJ *obj )
460 {
461     switch(obj->rgn->numRects)
462     {
463     case 0:  return NULLREGION;
464     case 1:  return SIMPLEREGION;
465     default: return COMPLEXREGION;
466     }
467 }
468
469
470 /***********************************************************************
471  *            REGION_DumpRegion
472  *            Outputs the contents of a WINEREGION
473  */
474 static void REGION_DumpRegion(WINEREGION *pReg)
475 {
476     RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
477
478     TRACE("Region %p: %ld,%ld - %ld,%ld %d rects\n", pReg,
479             pReg->extents.left, pReg->extents.top,
480             pReg->extents.right, pReg->extents.bottom, pReg->numRects);
481     for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
482         TRACE("\t%ld,%ld - %ld,%ld\n", pRect->left, pRect->top,
483                        pRect->right, pRect->bottom);
484     return;
485 }
486
487
488 /***********************************************************************
489  *            REGION_AllocWineRegion
490  *            Create a new empty WINEREGION.
491  */
492 static WINEREGION *REGION_AllocWineRegion( INT n )
493 {
494     WINEREGION *pReg;
495
496     if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
497     {
498         if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
499         {
500             pReg->size = n;
501             EMPTY_REGION(pReg);
502             return pReg;
503         }
504         HeapFree(GetProcessHeap(), 0, pReg);
505     }
506     return NULL;
507 }
508
509
510 /***********************************************************************
511  *          REGION_CreateRegion
512  *          Create a new empty region.
513  */
514 static HRGN REGION_CreateRegion( INT n )
515 {
516     HRGN hrgn;
517     RGNOBJ *obj;
518
519     if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, (HGDIOBJ *)&hrgn,
520                                 &region_funcs ))) return 0;
521     if(!(obj->rgn = REGION_AllocWineRegion(n))) {
522         GDI_FreeObject( hrgn, obj );
523         return 0;
524     }
525     GDI_ReleaseObj( hrgn );
526     return hrgn;
527 }
528
529 /***********************************************************************
530  *           REGION_DestroyWineRegion
531  */
532 static void REGION_DestroyWineRegion( WINEREGION* pReg )
533 {
534     HeapFree( GetProcessHeap(), 0, pReg->rects );
535     HeapFree( GetProcessHeap(), 0, pReg );
536 }
537
538 /***********************************************************************
539  *           REGION_DeleteObject
540  */
541 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj )
542 {
543     RGNOBJ *rgn = obj;
544
545     TRACE(" %p\n", handle );
546
547     REGION_DestroyWineRegion( rgn->rgn );
548     return GDI_FreeObject( handle, obj );
549 }
550
551 /***********************************************************************
552  *           REGION_SelectObject
553  */
554 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, void *obj, HDC hdc )
555 {
556     return (HGDIOBJ)SelectClipRgn( hdc, handle );
557 }
558
559
560 /***********************************************************************
561  *           OffsetRgn   (GDI32.@)
562  *
563  * Moves a region by the specified X- and Y-axis offsets.
564  *
565  * PARAMS
566  *   hrgn [I] Region to offset.
567  *   x    [I] Offset right if positive or left if negative.
568  *   y    [I] Offset down if positive or up if negative.
569  *
570  * RETURNS
571  *   Success:
572  *     NULLREGION - The new region is empty.
573  *     SIMPLEREGION - The new region can be represented by one rectangle.
574  *     COMPLEXREGION - The new region can only be represented by more than
575  *                     one rectangle.
576  *   Failure: ERROR
577  */
578 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
579 {
580     RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
581     INT ret;
582
583     TRACE("%p %d,%d\n", hrgn, x, y);
584
585     if (!obj)
586         return ERROR;
587
588     if(x || y) {
589         int nbox = obj->rgn->numRects;
590         RECT *pbox = obj->rgn->rects;
591
592         if(nbox) {
593             while(nbox--) {
594                 pbox->left += x;
595                 pbox->right += x;
596                 pbox->top += y;
597                 pbox->bottom += y;
598                 pbox++;
599             }
600             obj->rgn->extents.left += x;
601             obj->rgn->extents.right += x;
602             obj->rgn->extents.top += y;
603             obj->rgn->extents.bottom += y;
604         }
605     }
606     ret = get_region_type( obj );
607     GDI_ReleaseObj( hrgn );
608     return ret;
609 }
610
611
612 /***********************************************************************
613  *           GetRgnBox    (GDI32.@)
614  *
615  * Retrieves the bounding rectangle of the region. The bounding rectangle
616  * is the smallest rectangle that contains the entire region.
617  *
618  * PARAMS
619  *   hrgn [I] Region to retrieve bounding rectangle from.
620  *   rect [O] Rectangle that will receive the coordinates of the bounding
621  *            rectangle.
622  *
623  * RETURNS
624  *     NULLREGION - The new region is empty.
625  *     SIMPLEREGION - The new region can be represented by one rectangle.
626  *     COMPLEXREGION - The new region can only be represented by more than
627  *                     one rectangle.
628  */
629 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
630 {
631     RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
632     if (obj)
633     {
634         INT ret;
635         rect->left = obj->rgn->extents.left;
636         rect->top = obj->rgn->extents.top;
637         rect->right = obj->rgn->extents.right;
638         rect->bottom = obj->rgn->extents.bottom;
639         TRACE("%p (%ld,%ld-%ld,%ld)\n", hrgn,
640                rect->left, rect->top, rect->right, rect->bottom);
641         ret = get_region_type( obj );
642         GDI_ReleaseObj(hrgn);
643         return ret;
644     }
645     return ERROR;
646 }
647
648
649 /***********************************************************************
650  *           CreateRectRgn   (GDI32.@)
651  *
652  * Creates a simple rectangular region.
653  *
654  * PARAMS
655  *   left   [I] Left coordinate of rectangle.
656  *   top    [I] Top coordinate of rectangle.
657  *   right  [I] Right coordinate of rectangle.
658  *   bottom [I] Bottom coordinate of rectangle.
659  *
660  * RETURNS
661  *   Success: Handle to region.
662  *   Failure: NULL.
663  */
664 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
665 {
666     HRGN hrgn;
667
668     /* Allocate 2 rects by default to reduce the number of reallocs */
669
670     if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
671         return 0;
672     TRACE("%d,%d-%d,%d\n", left, top, right, bottom);
673     SetRectRgn(hrgn, left, top, right, bottom);
674     return hrgn;
675 }
676
677
678 /***********************************************************************
679  *           CreateRectRgnIndirect    (GDI32.@)
680  *
681  * Creates a simple rectangular region.
682  *
683  * PARAMS
684  *   rect [I] Coordinates of rectangular region.
685  *
686  * RETURNS
687  *   Success: Handle to region.
688  *   Failure: NULL.
689  */
690 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
691 {
692     return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
693 }
694
695
696 /***********************************************************************
697  *           SetRectRgn    (GDI32.@)
698  *
699  * Sets a region to a simple rectangular region.
700  *
701  * PARAMS
702  *   hrgn   [I] Region to convert.
703  *   left   [I] Left coordinate of rectangle.
704  *   top    [I] Top coordinate of rectangle.
705  *   right  [I] Right coordinate of rectangle.
706  *   bottom [I] Bottom coordinate of rectangle.
707  *
708  * RETURNS
709  *   Success: Non-zero.
710  *   Failure: Zero.
711  *
712  * NOTES
713  *   Allows either or both left and top to be greater than right or bottom.
714  */
715 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
716                           INT right, INT bottom )
717 {
718     RGNOBJ * obj;
719
720     TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
721
722     if (!(obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
723
724     if (left > right) { INT tmp = left; left = right; right = tmp; }
725     if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
726
727     if((left != right) && (top != bottom))
728     {
729         obj->rgn->rects->left = obj->rgn->extents.left = left;
730         obj->rgn->rects->top = obj->rgn->extents.top = top;
731         obj->rgn->rects->right = obj->rgn->extents.right = right;
732         obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
733         obj->rgn->numRects = 1;
734     }
735     else
736         EMPTY_REGION(obj->rgn);
737
738     GDI_ReleaseObj( hrgn );
739     return TRUE;
740 }
741
742
743 /***********************************************************************
744  *           CreateRoundRectRgn    (GDI32.@)
745  *
746  * Creates a rectangular region with rounded corners.
747  *
748  * PARAMS
749  *   left           [I] Left coordinate of rectangle.
750  *   top            [I] Top coordinate of rectangle.
751  *   right          [I] Right coordinate of rectangle.
752  *   bottom         [I] Bottom coordinate of rectangle.
753  *   ellipse_width  [I] Width of the ellipse at each corner.
754  *   ellipse_height [I] Height of the ellipse at each corner.
755  *
756  * RETURNS
757  *   Success: Handle to region.
758  *   Failure: NULL.
759  *
760  * NOTES
761  *   If ellipse_width or ellipse_height is less than 2 logical units then
762  *   it is treated as though CreateRectRgn() was called instead.
763  */
764 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
765                                     INT right, INT bottom,
766                                     INT ellipse_width, INT ellipse_height )
767 {
768     RGNOBJ * obj;
769     HRGN hrgn;
770     int asq, bsq, d, xd, yd;
771     RECT rect;
772
773       /* Make the dimensions sensible */
774
775     if (left > right) { INT tmp = left; left = right; right = tmp; }
776     if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
777
778     ellipse_width = abs(ellipse_width);
779     ellipse_height = abs(ellipse_height);
780
781       /* Check parameters */
782
783     if (ellipse_width > right-left) ellipse_width = right-left;
784     if (ellipse_height > bottom-top) ellipse_height = bottom-top;
785
786       /* Check if we can do a normal rectangle instead */
787
788     if ((ellipse_width < 2) || (ellipse_height < 2))
789         return CreateRectRgn( left, top, right, bottom );
790
791       /* Create region */
792
793     d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
794     if (!(hrgn = REGION_CreateRegion(d))) return 0;
795     if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
796     TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
797           left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
798
799       /* Ellipse algorithm, based on an article by K. Porter */
800       /* in DDJ Graphics Programming Column, 8/89 */
801
802     asq = ellipse_width * ellipse_width / 4;        /* a^2 */
803     bsq = ellipse_height * ellipse_height / 4;      /* b^2 */
804     d = bsq - asq * ellipse_height / 2 + asq / 4;   /* b^2 - a^2b + a^2/4 */
805     xd = 0;
806     yd = asq * ellipse_height;                      /* 2a^2b */
807
808     rect.left   = left + ellipse_width / 2;
809     rect.right  = right - ellipse_width / 2;
810
811       /* Loop to draw first half of quadrant */
812
813     while (xd < yd)
814     {
815         if (d > 0)  /* if nearest pixel is toward the center */
816         {
817               /* move toward center */
818             rect.top = top++;
819             rect.bottom = rect.top + 1;
820             REGION_UnionRectWithRegion( &rect, obj->rgn );
821             rect.top = --bottom;
822             rect.bottom = rect.top + 1;
823             REGION_UnionRectWithRegion( &rect, obj->rgn );
824             yd -= 2*asq;
825             d  -= yd;
826         }
827         rect.left--;        /* next horiz point */
828         rect.right++;
829         xd += 2*bsq;
830         d  += bsq + xd;
831     }
832
833       /* Loop to draw second half of quadrant */
834
835     d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
836     while (yd >= 0)
837     {
838           /* next vertical point */
839         rect.top = top++;
840         rect.bottom = rect.top + 1;
841         REGION_UnionRectWithRegion( &rect, obj->rgn );
842         rect.top = --bottom;
843         rect.bottom = rect.top + 1;
844         REGION_UnionRectWithRegion( &rect, obj->rgn );
845         if (d < 0)   /* if nearest pixel is outside ellipse */
846         {
847             rect.left--;     /* move away from center */
848             rect.right++;
849             xd += 2*bsq;
850             d  += xd;
851         }
852         yd -= 2*asq;
853         d  += asq - yd;
854     }
855
856       /* Add the inside rectangle */
857
858     if (top <= bottom)
859     {
860         rect.top = top;
861         rect.bottom = bottom;
862         REGION_UnionRectWithRegion( &rect, obj->rgn );
863     }
864     GDI_ReleaseObj( hrgn );
865     return hrgn;
866 }
867
868
869 /***********************************************************************
870  *           CreateEllipticRgn    (GDI32.@)
871  *
872  * Creates an elliptical region.
873  *
874  * PARAMS
875  *   left   [I] Left coordinate of bounding rectangle.
876  *   top    [I] Top coordinate of bounding rectangle.
877  *   right  [I] Right coordinate of bounding rectangle.
878  *   bottom [I] Bottom coordinate of bounding rectangle.
879  *
880  * RETURNS
881  *   Success: Handle to region.
882  *   Failure: NULL.
883  *
884  * NOTES
885  *   This is a special case of CreateRoundRectRgn() where the width of the
886  *   ellipse at each corner is equal to the width the the rectangle and
887  *   the same for the height.
888  */
889 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
890                                    INT right, INT bottom )
891 {
892     return CreateRoundRectRgn( left, top, right, bottom,
893                                  right-left, bottom-top );
894 }
895
896
897 /***********************************************************************
898  *           CreateEllipticRgnIndirect    (GDI32.@)
899  *
900  * Creates an elliptical region.
901  *
902  * PARAMS
903  *   rect [I] Pointer to bounding rectangle of the ellipse.
904  *
905  * RETURNS
906  *   Success: Handle to region.
907  *   Failure: NULL.
908  *
909  * NOTES
910  *   This is a special case of CreateRoundRectRgn() where the width of the
911  *   ellipse at each corner is equal to the width the the rectangle and
912  *   the same for the height.
913  */
914 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
915 {
916     return CreateRoundRectRgn( rect->left, rect->top, rect->right,
917                                  rect->bottom, rect->right - rect->left,
918                                  rect->bottom - rect->top );
919 }
920
921 /***********************************************************************
922  *           GetRegionData   (GDI32.@)
923  *
924  * Retrieves the data that specifies the region.
925  *
926  * PARAMS
927  *   hrgn    [I] Region to retrieve the region data from.
928  *   count   [I] The size of the buffer pointed to by rgndata in bytes.
929  *   rgndata [I] The buffer to receive data about the region.
930  *
931  * RETURNS
932  *   Success: If rgndata is NULL then the required number of bytes. Otherwise,
933  *            the number of bytes copied to the output buffer.
934  *   Failure: 0.
935  *
936  * NOTES
937  *   The format of the Buffer member of RGNDATA is determined by the iType
938  *   member of the region data header.
939  *   Currently this is always RDH_RECTANGLES, which specifies that the format
940  *   is the array of RECT's that specify the region. The length of the array
941  *   is specified by the nCount member of the region data header.
942  */
943 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
944 {
945     DWORD size;
946     RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
947
948     TRACE(" %p count = %ld, rgndata = %p\n", hrgn, count, rgndata);
949
950     if(!obj) return 0;
951
952     size = obj->rgn->numRects * sizeof(RECT);
953     if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
954     {
955         GDI_ReleaseObj( hrgn );
956         if (rgndata) /* buffer is too small, signal it by return 0 */
957             return 0;
958         else            /* user requested buffer size with rgndata NULL */
959             return size + sizeof(RGNDATAHEADER);
960     }
961
962     rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
963     rgndata->rdh.iType = RDH_RECTANGLES;
964     rgndata->rdh.nCount = obj->rgn->numRects;
965     rgndata->rdh.nRgnSize = size;
966     rgndata->rdh.rcBound.left = obj->rgn->extents.left;
967     rgndata->rdh.rcBound.top = obj->rgn->extents.top;
968     rgndata->rdh.rcBound.right = obj->rgn->extents.right;
969     rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
970
971     memcpy( rgndata->Buffer, obj->rgn->rects, size );
972
973     GDI_ReleaseObj( hrgn );
974     return size + sizeof(RGNDATAHEADER);
975 }
976
977
978 /***********************************************************************
979  *           ExtCreateRegion   (GDI32.@)
980  *
981  * Creates a region as specified by the transformation data and region data.
982  *
983  * PARAMS
984  *   lpXform [I] World-space to logical-space transformation data.
985  *   dwCount [I] Size of the data pointed to by rgndata, in bytes.
986  *   rgndata [I] Data that specifes the region.
987  *
988  * RETURNS
989  *   Success: Handle to region.
990  *   Failure: NULL.
991  *
992  * NOTES
993  *   See GetRegionData().
994  */
995 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
996 {
997     HRGN hrgn;
998
999     TRACE(" %p %ld %p\n", lpXform, dwCount, rgndata );
1000
1001     if( lpXform )
1002         WARN("(Xform not implemented - ignored)\n");
1003
1004     if( rgndata->rdh.iType != RDH_RECTANGLES )
1005     {
1006         /* FIXME: We can use CreatePolyPolygonRgn() here
1007          *        for trapezoidal data */
1008
1009         WARN("(Unsupported region data type: %lu)\n", rgndata->rdh.iType);
1010         goto fail;
1011     }
1012
1013     if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
1014     {
1015         RECT *pCurRect, *pEndRect;
1016         RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
1017
1018         if (obj) {
1019             pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1020             for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1021             {
1022                 if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
1023                     REGION_UnionRectWithRegion( pCurRect, obj->rgn );
1024             }
1025             GDI_ReleaseObj( hrgn );
1026
1027             TRACE("-- %p\n", hrgn );
1028             return hrgn;
1029         }
1030         else ERR("Could not get pointer to newborn Region!\n");
1031     }
1032 fail:
1033     WARN("Failed\n");
1034     return 0;
1035 }
1036
1037
1038 /***********************************************************************
1039  *           PtInRegion    (GDI32.@)
1040  *
1041  * Tests whether the specified point is inside a region.
1042  *
1043  * PARAMS
1044  *   hrgn [I] Region to test.
1045  *   x    [I] X-coordinate of point to test.
1046  *   y    [I] Y-coordinate of point to test.
1047  *
1048  * RETURNS
1049  *   Non-zero if the point is inside the region or zero otherwise.
1050  */
1051 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
1052 {
1053     RGNOBJ * obj;
1054     BOOL ret = FALSE;
1055
1056     if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
1057     {
1058         int i;
1059
1060         if (obj->rgn->numRects > 0 && INRECT(obj->rgn->extents, x, y))
1061             for (i = 0; i < obj->rgn->numRects; i++)
1062                 if (INRECT (obj->rgn->rects[i], x, y))
1063                 {
1064                     ret = TRUE;
1065                     break;
1066                 }
1067         GDI_ReleaseObj( hrgn );
1068     }
1069     return ret;
1070 }
1071
1072
1073 /***********************************************************************
1074  *           RectInRegion    (GDI32.@)
1075  *
1076  * Tests if a rectangle is at least partly inside the specified region.
1077  *
1078  * PARAMS
1079  *   hrgn [I] Region to test.
1080  *   rect [I] Rectangle to test.
1081  *
1082  * RETURNS
1083  *   Non-zero if the rectangle is partially inside the region or
1084  *   zero otherwise.
1085  */
1086 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
1087 {
1088     RGNOBJ * obj;
1089     BOOL ret = FALSE;
1090
1091     if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
1092     {
1093         RECT *pCurRect, *pRectEnd;
1094
1095     /* this is (just) a useful optimization */
1096         if ((obj->rgn->numRects > 0) && EXTENTCHECK(&obj->rgn->extents,
1097                                                       rect))
1098         {
1099             for (pCurRect = obj->rgn->rects, pRectEnd = pCurRect +
1100              obj->rgn->numRects; pCurRect < pRectEnd; pCurRect++)
1101             {
1102                 if (pCurRect->bottom <= rect->top)
1103                     continue;             /* not far enough down yet */
1104
1105                 if (pCurRect->top >= rect->bottom)
1106                     break;                /* too far down */
1107
1108                 if (pCurRect->right <= rect->left)
1109                     continue;              /* not far enough over yet */
1110
1111                 if (pCurRect->left >= rect->right) {
1112                     continue;
1113                 }
1114
1115                 ret = TRUE;
1116                 break;
1117             }
1118         }
1119         GDI_ReleaseObj(hrgn);
1120     }
1121     return ret;
1122 }
1123
1124 /***********************************************************************
1125  *           EqualRgn    (GDI32.@)
1126  *
1127  * Tests whether one region is identical to another.
1128  *
1129  * PARAMS
1130  *   hrgn1 [I] The first region to compare.
1131  *   hrgn2 [I] The second region to compare.
1132  *
1133  * RETURNS
1134  *   Non-zero if both regions are identical or zero otherwise.
1135  */
1136 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1137 {
1138     RGNOBJ *obj1, *obj2;
1139     BOOL ret = FALSE;
1140
1141     if ((obj1 = (RGNOBJ *) GDI_GetObjPtr( hrgn1, REGION_MAGIC )))
1142     {
1143         if ((obj2 = (RGNOBJ *) GDI_GetObjPtr( hrgn2, REGION_MAGIC )))
1144         {
1145             int i;
1146
1147             if ( obj1->rgn->numRects != obj2->rgn->numRects ) goto done;
1148             if ( obj1->rgn->numRects == 0 )
1149             {
1150                 ret = TRUE;
1151                 goto done;
1152
1153             }
1154             if (obj1->rgn->extents.left   != obj2->rgn->extents.left) goto done;
1155             if (obj1->rgn->extents.right  != obj2->rgn->extents.right) goto done;
1156             if (obj1->rgn->extents.top    != obj2->rgn->extents.top) goto done;
1157             if (obj1->rgn->extents.bottom != obj2->rgn->extents.bottom) goto done;
1158             for( i = 0; i < obj1->rgn->numRects; i++ )
1159             {
1160                 if (obj1->rgn->rects[i].left   != obj2->rgn->rects[i].left) goto done;
1161                 if (obj1->rgn->rects[i].right  != obj2->rgn->rects[i].right) goto done;
1162                 if (obj1->rgn->rects[i].top    != obj2->rgn->rects[i].top) goto done;
1163                 if (obj1->rgn->rects[i].bottom != obj2->rgn->rects[i].bottom) goto done;
1164             }
1165             ret = TRUE;
1166         done:
1167             GDI_ReleaseObj(hrgn2);
1168         }
1169         GDI_ReleaseObj(hrgn1);
1170     }
1171     return ret;
1172 }
1173
1174 /***********************************************************************
1175  *           REGION_UnionRectWithRegion
1176  *           Adds a rectangle to a WINEREGION
1177  */
1178 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1179 {
1180     WINEREGION region;
1181
1182     region.rects = &region.extents;
1183     region.numRects = 1;
1184     region.size = 1;
1185     region.extents = *rect;
1186     REGION_UnionRegion(rgn, rgn, &region);
1187 }
1188
1189
1190 /***********************************************************************
1191  *           REGION_CreateFrameRgn
1192  *
1193  * Create a region that is a frame around another region.
1194  * Expand all rectangles by +/- x and y, then subtract original region.
1195  */
1196 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1197 {
1198     BOOL bRet;
1199     RGNOBJ *srcObj = (RGNOBJ*) GDI_GetObjPtr( hSrc, REGION_MAGIC );
1200
1201     if (!srcObj) return FALSE;
1202     if (srcObj->rgn->numRects != 0)
1203     {
1204         RGNOBJ* destObj = (RGNOBJ*) GDI_GetObjPtr( hDest, REGION_MAGIC );
1205         RECT *pRect, *pEndRect;
1206         RECT tempRect;
1207
1208         EMPTY_REGION( destObj->rgn );
1209
1210         pEndRect = srcObj->rgn->rects + srcObj->rgn->numRects;
1211         for(pRect = srcObj->rgn->rects; pRect < pEndRect; pRect++)
1212         {
1213             tempRect.left = pRect->left - x;
1214             tempRect.top = pRect->top - y;
1215             tempRect.right = pRect->right + x;
1216             tempRect.bottom = pRect->bottom + y;
1217             REGION_UnionRectWithRegion( &tempRect, destObj->rgn );
1218         }
1219         REGION_SubtractRegion( destObj->rgn, destObj->rgn, srcObj->rgn );
1220         GDI_ReleaseObj ( hDest );
1221         bRet = TRUE;
1222     }
1223     else
1224         bRet = FALSE;
1225     GDI_ReleaseObj( hSrc );
1226     return bRet;
1227 }
1228
1229
1230 /***********************************************************************
1231  *           CombineRgn   (GDI32.@)
1232  *
1233  * Combines two regions with the specifed operation and stores the result
1234  * in the specified destination region.
1235  *
1236  * PARAMS
1237  *   hDest [I] The region that receives the combined result.
1238  *   hSrc1 [I] The first source region.
1239  *   hSrc2 [I] The second source region.
1240  *   mode  [I] The way in which the source regions will be combined. See notes.
1241  *
1242  * RETURNS
1243  *   Success:
1244  *     NULLREGION - The new region is empty.
1245  *     SIMPLEREGION - The new region can be represented by one rectangle.
1246  *     COMPLEXREGION - The new region can only be represented by more than
1247  *                     one rectangle.
1248  *   Failure: ERROR
1249  *
1250  * NOTES
1251  *   The two source regions can be the same region.
1252  *   The mode can be one of the following:
1253  *|  RGN_AND - Intersection of the regions
1254  *|  RGN_OR - Union of the regions
1255  *|  RGN_XOR - Unions of the regions minus any intersection.
1256  *|  RGN_DIFF - Difference (subtraction) of the regions.
1257  */
1258 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1259 {
1260     RGNOBJ *destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC);
1261     INT result = ERROR;
1262
1263     TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1264     if (destObj)
1265     {
1266         RGNOBJ *src1Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc1, REGION_MAGIC);
1267
1268         if (src1Obj)
1269         {
1270             TRACE("dump src1Obj:\n");
1271             if(TRACE_ON(region))
1272               REGION_DumpRegion(src1Obj->rgn);
1273             if (mode == RGN_COPY)
1274             {
1275                 REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
1276                 result = get_region_type( destObj );
1277             }
1278             else
1279             {
1280                 RGNOBJ *src2Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc2, REGION_MAGIC);
1281
1282                 if (src2Obj)
1283                 {
1284                     TRACE("dump src2Obj:\n");
1285                     if(TRACE_ON(region))
1286                         REGION_DumpRegion(src2Obj->rgn);
1287                     switch (mode)
1288                     {
1289                     case RGN_AND:
1290                         REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
1291                         break;
1292                     case RGN_OR:
1293                         REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1294                         break;
1295                     case RGN_XOR:
1296                         REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1297                         break;
1298                     case RGN_DIFF:
1299                         REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1300                         break;
1301                     }
1302                     result = get_region_type( destObj );
1303                     GDI_ReleaseObj( hSrc2 );
1304                 }
1305             }
1306             GDI_ReleaseObj( hSrc1 );
1307         }
1308         TRACE("dump destObj:\n");
1309         if(TRACE_ON(region))
1310           REGION_DumpRegion(destObj->rgn);
1311
1312         GDI_ReleaseObj( hDest );
1313     } else {
1314        ERR("Invalid rgn=%p\n", hDest);
1315     }
1316     return result;
1317 }
1318
1319 /***********************************************************************
1320  *           REGION_SetExtents
1321  *           Re-calculate the extents of a region
1322  */
1323 static void REGION_SetExtents (WINEREGION *pReg)
1324 {
1325     RECT *pRect, *pRectEnd, *pExtents;
1326
1327     if (pReg->numRects == 0)
1328     {
1329         pReg->extents.left = 0;
1330         pReg->extents.top = 0;
1331         pReg->extents.right = 0;
1332         pReg->extents.bottom = 0;
1333         return;
1334     }
1335
1336     pExtents = &pReg->extents;
1337     pRect = pReg->rects;
1338     pRectEnd = &pRect[pReg->numRects - 1];
1339
1340     /*
1341      * Since pRect is the first rectangle in the region, it must have the
1342      * smallest top and since pRectEnd is the last rectangle in the region,
1343      * it must have the largest bottom, because of banding. Initialize left and
1344      * right from pRect and pRectEnd, resp., as good things to initialize them
1345      * to...
1346      */
1347     pExtents->left = pRect->left;
1348     pExtents->top = pRect->top;
1349     pExtents->right = pRectEnd->right;
1350     pExtents->bottom = pRectEnd->bottom;
1351
1352     while (pRect <= pRectEnd)
1353     {
1354         if (pRect->left < pExtents->left)
1355             pExtents->left = pRect->left;
1356         if (pRect->right > pExtents->right)
1357             pExtents->right = pRect->right;
1358         pRect++;
1359     }
1360 }
1361
1362 /***********************************************************************
1363  *           REGION_CopyRegion
1364  */
1365 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1366 {
1367     if (dst != src) /*  don't want to copy to itself */
1368     {
1369         if (dst->size < src->numRects)
1370         {
1371             if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1372                                 src->numRects * sizeof(RECT) )))
1373                 return;
1374             dst->size = src->numRects;
1375         }
1376         dst->numRects = src->numRects;
1377         dst->extents.left = src->extents.left;
1378         dst->extents.top = src->extents.top;
1379         dst->extents.right = src->extents.right;
1380         dst->extents.bottom = src->extents.bottom;
1381         memcpy((char *) dst->rects, (char *) src->rects,
1382                (int) (src->numRects * sizeof(RECT)));
1383     }
1384     return;
1385 }
1386
1387 /***********************************************************************
1388  *           REGION_Coalesce
1389  *
1390  *      Attempt to merge the rects in the current band with those in the
1391  *      previous one. Used only by REGION_RegionOp.
1392  *
1393  * Results:
1394  *      The new index for the previous band.
1395  *
1396  * Side Effects:
1397  *      If coalescing takes place:
1398  *          - rectangles in the previous band will have their bottom fields
1399  *            altered.
1400  *          - pReg->numRects will be decreased.
1401  *
1402  */
1403 static INT REGION_Coalesce (
1404              WINEREGION *pReg, /* Region to coalesce */
1405              INT prevStart,  /* Index of start of previous band */
1406              INT curStart    /* Index of start of current band */
1407 ) {
1408     RECT *pPrevRect;          /* Current rect in previous band */
1409     RECT *pCurRect;           /* Current rect in current band */
1410     RECT *pRegEnd;            /* End of region */
1411     INT curNumRects;          /* Number of rectangles in current band */
1412     INT prevNumRects;         /* Number of rectangles in previous band */
1413     INT bandtop;               /* top coordinate for current band */
1414
1415     pRegEnd = &pReg->rects[pReg->numRects];
1416
1417     pPrevRect = &pReg->rects[prevStart];
1418     prevNumRects = curStart - prevStart;
1419
1420     /*
1421      * Figure out how many rectangles are in the current band. Have to do
1422      * this because multiple bands could have been added in REGION_RegionOp
1423      * at the end when one region has been exhausted.
1424      */
1425     pCurRect = &pReg->rects[curStart];
1426     bandtop = pCurRect->top;
1427     for (curNumRects = 0;
1428          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1429          curNumRects++)
1430     {
1431         pCurRect++;
1432     }
1433
1434     if (pCurRect != pRegEnd)
1435     {
1436         /*
1437          * If more than one band was added, we have to find the start
1438          * of the last band added so the next coalescing job can start
1439          * at the right place... (given when multiple bands are added,
1440          * this may be pointless -- see above).
1441          */
1442         pRegEnd--;
1443         while (pRegEnd[-1].top == pRegEnd->top)
1444         {
1445             pRegEnd--;
1446         }
1447         curStart = pRegEnd - pReg->rects;
1448         pRegEnd = pReg->rects + pReg->numRects;
1449     }
1450
1451     if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1452         pCurRect -= curNumRects;
1453         /*
1454          * The bands may only be coalesced if the bottom of the previous
1455          * matches the top scanline of the current.
1456          */
1457         if (pPrevRect->bottom == pCurRect->top)
1458         {
1459             /*
1460              * Make sure the bands have rects in the same places. This
1461              * assumes that rects have been added in such a way that they
1462              * cover the most area possible. I.e. two rects in a band must
1463              * have some horizontal space between them.
1464              */
1465             do
1466             {
1467                 if ((pPrevRect->left != pCurRect->left) ||
1468                     (pPrevRect->right != pCurRect->right))
1469                 {
1470                     /*
1471                      * The bands don't line up so they can't be coalesced.
1472                      */
1473                     return (curStart);
1474                 }
1475                 pPrevRect++;
1476                 pCurRect++;
1477                 prevNumRects -= 1;
1478             } while (prevNumRects != 0);
1479
1480             pReg->numRects -= curNumRects;
1481             pCurRect -= curNumRects;
1482             pPrevRect -= curNumRects;
1483
1484             /*
1485              * The bands may be merged, so set the bottom of each rect
1486              * in the previous band to that of the corresponding rect in
1487              * the current band.
1488              */
1489             do
1490             {
1491                 pPrevRect->bottom = pCurRect->bottom;
1492                 pPrevRect++;
1493                 pCurRect++;
1494                 curNumRects -= 1;
1495             } while (curNumRects != 0);
1496
1497             /*
1498              * If only one band was added to the region, we have to backup
1499              * curStart to the start of the previous band.
1500              *
1501              * If more than one band was added to the region, copy the
1502              * other bands down. The assumption here is that the other bands
1503              * came from the same region as the current one and no further
1504              * coalescing can be done on them since it's all been done
1505              * already... curStart is already in the right place.
1506              */
1507             if (pCurRect == pRegEnd)
1508             {
1509                 curStart = prevStart;
1510             }
1511             else
1512             {
1513                 do
1514                 {
1515                     *pPrevRect++ = *pCurRect++;
1516                 } while (pCurRect != pRegEnd);
1517             }
1518
1519         }
1520     }
1521     return (curStart);
1522 }
1523
1524 /***********************************************************************
1525  *           REGION_RegionOp
1526  *
1527  *      Apply an operation to two regions. Called by REGION_Union,
1528  *      REGION_Inverse, REGION_Subtract, REGION_Intersect...
1529  *
1530  * Results:
1531  *      None.
1532  *
1533  * Side Effects:
1534  *      The new region is overwritten.
1535  *
1536  * Notes:
1537  *      The idea behind this function is to view the two regions as sets.
1538  *      Together they cover a rectangle of area that this function divides
1539  *      into horizontal bands where points are covered only by one region
1540  *      or by both. For the first case, the nonOverlapFunc is called with
1541  *      each the band and the band's upper and lower extents. For the
1542  *      second, the overlapFunc is called to process the entire band. It
1543  *      is responsible for clipping the rectangles in the band, though
1544  *      this function provides the boundaries.
1545  *      At the end of each band, the new region is coalesced, if possible,
1546  *      to reduce the number of rectangles in the region.
1547  *
1548  */
1549 static void REGION_RegionOp(
1550             WINEREGION *newReg, /* Place to store result */
1551             WINEREGION *reg1,   /* First region in operation */
1552             WINEREGION *reg2,   /* 2nd region in operation */
1553             void (*overlapFunc)(),     /* Function to call for over-lapping bands */
1554             void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
1555             void (*nonOverlap2Func)()  /* Function to call for non-overlapping bands in region 2 */
1556 ) {
1557     RECT *r1;                         /* Pointer into first region */
1558     RECT *r2;                         /* Pointer into 2d region */
1559     RECT *r1End;                      /* End of 1st region */
1560     RECT *r2End;                      /* End of 2d region */
1561     INT ybot;                         /* Bottom of intersection */
1562     INT ytop;                         /* Top of intersection */
1563     RECT *oldRects;                   /* Old rects for newReg */
1564     INT prevBand;                     /* Index of start of
1565                                                  * previous band in newReg */
1566     INT curBand;                      /* Index of start of current
1567                                                  * band in newReg */
1568     RECT *r1BandEnd;                  /* End of current band in r1 */
1569     RECT *r2BandEnd;                  /* End of current band in r2 */
1570     INT top;                          /* Top of non-overlapping band */
1571     INT bot;                          /* Bottom of non-overlapping band */
1572
1573     /*
1574      * Initialization:
1575      *  set r1, r2, r1End and r2End appropriately, preserve the important
1576      * parts of the destination region until the end in case it's one of
1577      * the two source regions, then mark the "new" region empty, allocating
1578      * another array of rectangles for it to use.
1579      */
1580     r1 = reg1->rects;
1581     r2 = reg2->rects;
1582     r1End = r1 + reg1->numRects;
1583     r2End = r2 + reg2->numRects;
1584
1585
1586     /*
1587      * newReg may be one of the src regions so we can't empty it. We keep a
1588      * note of its rects pointer (so that we can free them later), preserve its
1589      * extents and simply set numRects to zero.
1590      */
1591
1592     oldRects = newReg->rects;
1593     newReg->numRects = 0;
1594
1595     /*
1596      * Allocate a reasonable number of rectangles for the new region. The idea
1597      * is to allocate enough so the individual functions don't need to
1598      * reallocate and copy the array, which is time consuming, yet we don't
1599      * have to worry about using too much memory. I hope to be able to
1600      * nuke the Xrealloc() at the end of this function eventually.
1601      */
1602     newReg->size = max(reg1->numRects,reg2->numRects) * 2;
1603
1604     if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1605                                   sizeof(RECT) * newReg->size )))
1606     {
1607         newReg->size = 0;
1608         return;
1609     }
1610
1611     /*
1612      * Initialize ybot and ytop.
1613      * In the upcoming loop, ybot and ytop serve different functions depending
1614      * on whether the band being handled is an overlapping or non-overlapping
1615      * band.
1616      *  In the case of a non-overlapping band (only one of the regions
1617      * has points in the band), ybot is the bottom of the most recent
1618      * intersection and thus clips the top of the rectangles in that band.
1619      * ytop is the top of the next intersection between the two regions and
1620      * serves to clip the bottom of the rectangles in the current band.
1621      *  For an overlapping band (where the two regions intersect), ytop clips
1622      * the top of the rectangles of both regions and ybot clips the bottoms.
1623      */
1624     if (reg1->extents.top < reg2->extents.top)
1625         ybot = reg1->extents.top;
1626     else
1627         ybot = reg2->extents.top;
1628
1629     /*
1630      * prevBand serves to mark the start of the previous band so rectangles
1631      * can be coalesced into larger rectangles. qv. miCoalesce, above.
1632      * In the beginning, there is no previous band, so prevBand == curBand
1633      * (curBand is set later on, of course, but the first band will always
1634      * start at index 0). prevBand and curBand must be indices because of
1635      * the possible expansion, and resultant moving, of the new region's
1636      * array of rectangles.
1637      */
1638     prevBand = 0;
1639
1640     do
1641     {
1642         curBand = newReg->numRects;
1643
1644         /*
1645          * This algorithm proceeds one source-band (as opposed to a
1646          * destination band, which is determined by where the two regions
1647          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1648          * rectangle after the last one in the current band for their
1649          * respective regions.
1650          */
1651         r1BandEnd = r1;
1652         while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1653         {
1654             r1BandEnd++;
1655         }
1656
1657         r2BandEnd = r2;
1658         while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1659         {
1660             r2BandEnd++;
1661         }
1662
1663         /*
1664          * First handle the band that doesn't intersect, if any.
1665          *
1666          * Note that attention is restricted to one band in the
1667          * non-intersecting region at once, so if a region has n
1668          * bands between the current position and the next place it overlaps
1669          * the other, this entire loop will be passed through n times.
1670          */
1671         if (r1->top < r2->top)
1672         {
1673             top = max(r1->top,ybot);
1674             bot = min(r1->bottom,r2->top);
1675
1676             if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
1677             {
1678                 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1679             }
1680
1681             ytop = r2->top;
1682         }
1683         else if (r2->top < r1->top)
1684         {
1685             top = max(r2->top,ybot);
1686             bot = min(r2->bottom,r1->top);
1687
1688             if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
1689             {
1690                 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1691             }
1692
1693             ytop = r1->top;
1694         }
1695         else
1696         {
1697             ytop = r1->top;
1698         }
1699
1700         /*
1701          * If any rectangles got added to the region, try and coalesce them
1702          * with rectangles from the previous band. Note we could just do
1703          * this test in miCoalesce, but some machines incur a not
1704          * inconsiderable cost for function calls, so...
1705          */
1706         if (newReg->numRects != curBand)
1707         {
1708             prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1709         }
1710
1711         /*
1712          * Now see if we've hit an intersecting band. The two bands only
1713          * intersect if ybot > ytop
1714          */
1715         ybot = min(r1->bottom, r2->bottom);
1716         curBand = newReg->numRects;
1717         if (ybot > ytop)
1718         {
1719             (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1720
1721         }
1722
1723         if (newReg->numRects != curBand)
1724         {
1725             prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1726         }
1727
1728         /*
1729          * If we've finished with a band (bottom == ybot) we skip forward
1730          * in the region to the next band.
1731          */
1732         if (r1->bottom == ybot)
1733         {
1734             r1 = r1BandEnd;
1735         }
1736         if (r2->bottom == ybot)
1737         {
1738             r2 = r2BandEnd;
1739         }
1740     } while ((r1 != r1End) && (r2 != r2End));
1741
1742     /*
1743      * Deal with whichever region still has rectangles left.
1744      */
1745     curBand = newReg->numRects;
1746     if (r1 != r1End)
1747     {
1748         if (nonOverlap1Func != (void (*)())NULL)
1749         {
1750             do
1751             {
1752                 r1BandEnd = r1;
1753                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1754                 {
1755                     r1BandEnd++;
1756                 }
1757                 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1758                                      max(r1->top,ybot), r1->bottom);
1759                 r1 = r1BandEnd;
1760             } while (r1 != r1End);
1761         }
1762     }
1763     else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
1764     {
1765         do
1766         {
1767             r2BandEnd = r2;
1768             while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1769             {
1770                  r2BandEnd++;
1771             }
1772             (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1773                                 max(r2->top,ybot), r2->bottom);
1774             r2 = r2BandEnd;
1775         } while (r2 != r2End);
1776     }
1777
1778     if (newReg->numRects != curBand)
1779     {
1780         (void) REGION_Coalesce (newReg, prevBand, curBand);
1781     }
1782
1783     /*
1784      * A bit of cleanup. To keep regions from growing without bound,
1785      * we shrink the array of rectangles to match the new number of
1786      * rectangles in the region. This never goes to 0, however...
1787      *
1788      * Only do this stuff if the number of rectangles allocated is more than
1789      * twice the number of rectangles in the region (a simple optimization...).
1790      */
1791     if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1792     {
1793         if (REGION_NOT_EMPTY(newReg))
1794         {
1795             RECT *prev_rects = newReg->rects;
1796             newReg->size = newReg->numRects;
1797             newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1798                                    sizeof(RECT) * newReg->size );
1799             if (! newReg->rects)
1800                 newReg->rects = prev_rects;
1801         }
1802         else
1803         {
1804             /*
1805              * No point in doing the extra work involved in an Xrealloc if
1806              * the region is empty
1807              */
1808             newReg->size = 1;
1809             HeapFree( GetProcessHeap(), 0, newReg->rects );
1810             newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
1811         }
1812     }
1813     HeapFree( GetProcessHeap(), 0, oldRects );
1814     return;
1815 }
1816
1817 /***********************************************************************
1818  *          Region Intersection
1819  ***********************************************************************/
1820
1821
1822 /***********************************************************************
1823  *           REGION_IntersectO
1824  *
1825  * Handle an overlapping band for REGION_Intersect.
1826  *
1827  * Results:
1828  *      None.
1829  *
1830  * Side Effects:
1831  *      Rectangles may be added to the region.
1832  *
1833  */
1834 static void REGION_IntersectO(WINEREGION *pReg,  RECT *r1, RECT *r1End,
1835                 RECT *r2, RECT *r2End, INT top, INT bottom)
1836
1837 {
1838     INT       left, right;
1839     RECT      *pNextRect;
1840
1841     pNextRect = &pReg->rects[pReg->numRects];
1842
1843     while ((r1 != r1End) && (r2 != r2End))
1844     {
1845         left = max(r1->left, r2->left);
1846         right = min(r1->right, r2->right);
1847
1848         /*
1849          * If there's any overlap between the two rectangles, add that
1850          * overlap to the new region.
1851          * There's no need to check for subsumption because the only way
1852          * such a need could arise is if some region has two rectangles
1853          * right next to each other. Since that should never happen...
1854          */
1855         if (left < right)
1856         {
1857             MEMCHECK(pReg, pNextRect, pReg->rects);
1858             pNextRect->left = left;
1859             pNextRect->top = top;
1860             pNextRect->right = right;
1861             pNextRect->bottom = bottom;
1862             pReg->numRects += 1;
1863             pNextRect++;
1864         }
1865
1866         /*
1867          * Need to advance the pointers. Shift the one that extends
1868          * to the right the least, since the other still has a chance to
1869          * overlap with that region's next rectangle, if you see what I mean.
1870          */
1871         if (r1->right < r2->right)
1872         {
1873             r1++;
1874         }
1875         else if (r2->right < r1->right)
1876         {
1877             r2++;
1878         }
1879         else
1880         {
1881             r1++;
1882             r2++;
1883         }
1884     }
1885     return;
1886 }
1887
1888 /***********************************************************************
1889  *           REGION_IntersectRegion
1890  */
1891 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1892                                    WINEREGION *reg2)
1893 {
1894    /* check for trivial reject */
1895     if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
1896         (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
1897         newReg->numRects = 0;
1898     else
1899         REGION_RegionOp (newReg, reg1, reg2,
1900          (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
1901
1902     /*
1903      * Can't alter newReg's extents before we call miRegionOp because
1904      * it might be one of the source regions and miRegionOp depends
1905      * on the extents of those regions being the same. Besides, this
1906      * way there's no checking against rectangles that will be nuked
1907      * due to coalescing, so we have to examine fewer rectangles.
1908      */
1909     REGION_SetExtents(newReg);
1910 }
1911
1912 /***********************************************************************
1913  *           Region Union
1914  ***********************************************************************/
1915
1916 /***********************************************************************
1917  *           REGION_UnionNonO
1918  *
1919  *      Handle a non-overlapping band for the union operation. Just
1920  *      Adds the rectangles into the region. Doesn't have to check for
1921  *      subsumption or anything.
1922  *
1923  * Results:
1924  *      None.
1925  *
1926  * Side Effects:
1927  *      pReg->numRects is incremented and the final rectangles overwritten
1928  *      with the rectangles we're passed.
1929  *
1930  */
1931 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1932                               INT top, INT bottom)
1933 {
1934     RECT *pNextRect;
1935
1936     pNextRect = &pReg->rects[pReg->numRects];
1937
1938     while (r != rEnd)
1939     {
1940         MEMCHECK(pReg, pNextRect, pReg->rects);
1941         pNextRect->left = r->left;
1942         pNextRect->top = top;
1943         pNextRect->right = r->right;
1944         pNextRect->bottom = bottom;
1945         pReg->numRects += 1;
1946         pNextRect++;
1947         r++;
1948     }
1949     return;
1950 }
1951
1952 /***********************************************************************
1953  *           REGION_UnionO
1954  *
1955  *      Handle an overlapping band for the union operation. Picks the
1956  *      left-most rectangle each time and merges it into the region.
1957  *
1958  * Results:
1959  *      None.
1960  *
1961  * Side Effects:
1962  *      Rectangles are overwritten in pReg->rects and pReg->numRects will
1963  *      be changed.
1964  *
1965  */
1966 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1967                            RECT *r2, RECT *r2End, INT top, INT bottom)
1968 {
1969     RECT *pNextRect;
1970
1971     pNextRect = &pReg->rects[pReg->numRects];
1972
1973 #define MERGERECT(r) \
1974     if ((pReg->numRects != 0) &&  \
1975         (pNextRect[-1].top == top) &&  \
1976         (pNextRect[-1].bottom == bottom) &&  \
1977         (pNextRect[-1].right >= r->left))  \
1978     {  \
1979         if (pNextRect[-1].right < r->right)  \
1980         {  \
1981             pNextRect[-1].right = r->right;  \
1982         }  \
1983     }  \
1984     else  \
1985     {  \
1986         MEMCHECK(pReg, pNextRect, pReg->rects);  \
1987         pNextRect->top = top;  \
1988         pNextRect->bottom = bottom;  \
1989         pNextRect->left = r->left;  \
1990         pNextRect->right = r->right;  \
1991         pReg->numRects += 1;  \
1992         pNextRect += 1;  \
1993     }  \
1994     r++;
1995
1996     while ((r1 != r1End) && (r2 != r2End))
1997     {
1998         if (r1->left < r2->left)
1999         {
2000             MERGERECT(r1);
2001         }
2002         else
2003         {
2004             MERGERECT(r2);
2005         }
2006     }
2007
2008     if (r1 != r1End)
2009     {
2010         do
2011         {
2012             MERGERECT(r1);
2013         } while (r1 != r1End);
2014     }
2015     else while (r2 != r2End)
2016     {
2017         MERGERECT(r2);
2018     }
2019     return;
2020 }
2021
2022 /***********************************************************************
2023  *           REGION_UnionRegion
2024  */
2025 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
2026                                WINEREGION *reg2)
2027 {
2028     /*  checks all the simple cases */
2029
2030     /*
2031      * Region 1 and 2 are the same or region 1 is empty
2032      */
2033     if ( (reg1 == reg2) || (!(reg1->numRects)) )
2034     {
2035         if (newReg != reg2)
2036             REGION_CopyRegion(newReg, reg2);
2037         return;
2038     }
2039
2040     /*
2041      * if nothing to union (region 2 empty)
2042      */
2043     if (!(reg2->numRects))
2044     {
2045         if (newReg != reg1)
2046             REGION_CopyRegion(newReg, reg1);
2047         return;
2048     }
2049
2050     /*
2051      * Region 1 completely subsumes region 2
2052      */
2053     if ((reg1->numRects == 1) &&
2054         (reg1->extents.left <= reg2->extents.left) &&
2055         (reg1->extents.top <= reg2->extents.top) &&
2056         (reg1->extents.right >= reg2->extents.right) &&
2057         (reg1->extents.bottom >= reg2->extents.bottom))
2058     {
2059         if (newReg != reg1)
2060             REGION_CopyRegion(newReg, reg1);
2061         return;
2062     }
2063
2064     /*
2065      * Region 2 completely subsumes region 1
2066      */
2067     if ((reg2->numRects == 1) &&
2068         (reg2->extents.left <= reg1->extents.left) &&
2069         (reg2->extents.top <= reg1->extents.top) &&
2070         (reg2->extents.right >= reg1->extents.right) &&
2071         (reg2->extents.bottom >= reg1->extents.bottom))
2072     {
2073         if (newReg != reg2)
2074             REGION_CopyRegion(newReg, reg2);
2075         return;
2076     }
2077
2078     REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
2079                 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
2080
2081     newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2082     newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2083     newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2084     newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2085 }
2086
2087 /***********************************************************************
2088  *           Region Subtraction
2089  ***********************************************************************/
2090
2091 /***********************************************************************
2092  *           REGION_SubtractNonO1
2093  *
2094  *      Deal with non-overlapping band for subtraction. Any parts from
2095  *      region 2 we discard. Anything from region 1 we add to the region.
2096  *
2097  * Results:
2098  *      None.
2099  *
2100  * Side Effects:
2101  *      pReg may be affected.
2102  *
2103  */
2104 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
2105                 INT top, INT bottom)
2106 {
2107     RECT *pNextRect;
2108
2109     pNextRect = &pReg->rects[pReg->numRects];
2110
2111     while (r != rEnd)
2112     {
2113         MEMCHECK(pReg, pNextRect, pReg->rects);
2114         pNextRect->left = r->left;
2115         pNextRect->top = top;
2116         pNextRect->right = r->right;
2117         pNextRect->bottom = bottom;
2118         pReg->numRects += 1;
2119         pNextRect++;
2120         r++;
2121     }
2122     return;
2123 }
2124
2125
2126 /***********************************************************************
2127  *           REGION_SubtractO
2128  *
2129  *      Overlapping band subtraction. x1 is the left-most point not yet
2130  *      checked.
2131  *
2132  * Results:
2133  *      None.
2134  *
2135  * Side Effects:
2136  *      pReg may have rectangles added to it.
2137  *
2138  */
2139 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2140                 RECT *r2, RECT *r2End, INT top, INT bottom)
2141 {
2142     RECT *pNextRect;
2143     INT left;
2144
2145     left = r1->left;
2146     pNextRect = &pReg->rects[pReg->numRects];
2147
2148     while ((r1 != r1End) && (r2 != r2End))
2149     {
2150         if (r2->right <= left)
2151         {
2152             /*
2153              * Subtrahend missed the boat: go to next subtrahend.
2154              */
2155             r2++;
2156         }
2157         else if (r2->left <= left)
2158         {
2159             /*
2160              * Subtrahend preceeds minuend: nuke left edge of minuend.
2161              */
2162             left = r2->right;
2163             if (left >= r1->right)
2164             {
2165                 /*
2166                  * Minuend completely covered: advance to next minuend and
2167                  * reset left fence to edge of new minuend.
2168                  */
2169                 r1++;
2170                 if (r1 != r1End)
2171                     left = r1->left;
2172             }
2173             else
2174             {
2175                 /*
2176                  * Subtrahend now used up since it doesn't extend beyond
2177                  * minuend
2178                  */
2179                 r2++;
2180             }
2181         }
2182         else if (r2->left < r1->right)
2183         {
2184             /*
2185              * Left part of subtrahend covers part of minuend: add uncovered
2186              * part of minuend to region and skip to next subtrahend.
2187              */
2188             MEMCHECK(pReg, pNextRect, pReg->rects);
2189             pNextRect->left = left;
2190             pNextRect->top = top;
2191             pNextRect->right = r2->left;
2192             pNextRect->bottom = bottom;
2193             pReg->numRects += 1;
2194             pNextRect++;
2195             left = r2->right;
2196             if (left >= r1->right)
2197             {
2198                 /*
2199                  * Minuend used up: advance to new...
2200                  */
2201                 r1++;
2202                 if (r1 != r1End)
2203                     left = r1->left;
2204             }
2205             else
2206             {
2207                 /*
2208                  * Subtrahend used up
2209                  */
2210                 r2++;
2211             }
2212         }
2213         else
2214         {
2215             /*
2216              * Minuend used up: add any remaining piece before advancing.
2217              */
2218             if (r1->right > left)
2219             {
2220                 MEMCHECK(pReg, pNextRect, pReg->rects);
2221                 pNextRect->left = left;
2222                 pNextRect->top = top;
2223                 pNextRect->right = r1->right;
2224                 pNextRect->bottom = bottom;
2225                 pReg->numRects += 1;
2226                 pNextRect++;
2227             }
2228             r1++;
2229             left = r1->left;
2230         }
2231     }
2232
2233     /*
2234      * Add remaining minuend rectangles to region.
2235      */
2236     while (r1 != r1End)
2237     {
2238         MEMCHECK(pReg, pNextRect, pReg->rects);
2239         pNextRect->left = left;
2240         pNextRect->top = top;
2241         pNextRect->right = r1->right;
2242         pNextRect->bottom = bottom;
2243         pReg->numRects += 1;
2244         pNextRect++;
2245         r1++;
2246         if (r1 != r1End)
2247         {
2248             left = r1->left;
2249         }
2250     }
2251     return;
2252 }
2253
2254 /***********************************************************************
2255  *           REGION_SubtractRegion
2256  *
2257  *      Subtract regS from regM and leave the result in regD.
2258  *      S stands for subtrahend, M for minuend and D for difference.
2259  *
2260  * Results:
2261  *      TRUE.
2262  *
2263  * Side Effects:
2264  *      regD is overwritten.
2265  *
2266  */
2267 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
2268                                                        WINEREGION *regS )
2269 {
2270    /* check for trivial reject */
2271     if ( (!(regM->numRects)) || (!(regS->numRects))  ||
2272         (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2273     {
2274         REGION_CopyRegion(regD, regM);
2275         return;
2276     }
2277
2278     REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
2279                 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
2280
2281     /*
2282      * Can't alter newReg's extents before we call miRegionOp because
2283      * it might be one of the source regions and miRegionOp depends
2284      * on the extents of those regions being the unaltered. Besides, this
2285      * way there's no checking against rectangles that will be nuked
2286      * due to coalescing, so we have to examine fewer rectangles.
2287      */
2288     REGION_SetExtents (regD);
2289 }
2290
2291 /***********************************************************************
2292  *           REGION_XorRegion
2293  */
2294 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
2295                                                         WINEREGION *srb)
2296 {
2297     WINEREGION *tra, *trb;
2298
2299     if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
2300         (! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
2301         return;
2302     REGION_SubtractRegion(tra,sra,srb);
2303     REGION_SubtractRegion(trb,srb,sra);
2304     REGION_UnionRegion(dr,tra,trb);
2305     REGION_DestroyWineRegion(tra);
2306     REGION_DestroyWineRegion(trb);
2307     return;
2308 }
2309
2310 /**************************************************************************
2311  *
2312  *    Poly Regions
2313  *
2314  *************************************************************************/
2315
2316 #define LARGE_COORDINATE  0x7fffffff /* FIXME */
2317 #define SMALL_COORDINATE  0x80000000
2318
2319 /***********************************************************************
2320  *     REGION_InsertEdgeInET
2321  *
2322  *     Insert the given edge into the edge table.
2323  *     First we must find the correct bucket in the
2324  *     Edge table, then find the right slot in the
2325  *     bucket.  Finally, we can insert it.
2326  *
2327  */
2328 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2329                 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2330
2331 {
2332     EdgeTableEntry *start, *prev;
2333     ScanLineList *pSLL, *pPrevSLL;
2334     ScanLineListBlock *tmpSLLBlock;
2335
2336     /*
2337      * find the right bucket to put the edge into
2338      */
2339     pPrevSLL = &ET->scanlines;
2340     pSLL = pPrevSLL->next;
2341     while (pSLL && (pSLL->scanline < scanline))
2342     {
2343         pPrevSLL = pSLL;
2344         pSLL = pSLL->next;
2345     }
2346
2347     /*
2348      * reassign pSLL (pointer to ScanLineList) if necessary
2349      */
2350     if ((!pSLL) || (pSLL->scanline > scanline))
2351     {
2352         if (*iSLLBlock > SLLSPERBLOCK-1)
2353         {
2354             tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2355             if(!tmpSLLBlock)
2356             {
2357                 WARN("Can't alloc SLLB\n");
2358                 return;
2359             }
2360             (*SLLBlock)->next = tmpSLLBlock;
2361             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
2362             *SLLBlock = tmpSLLBlock;
2363             *iSLLBlock = 0;
2364         }
2365         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2366
2367         pSLL->next = pPrevSLL->next;
2368         pSLL->edgelist = (EdgeTableEntry *)NULL;
2369         pPrevSLL->next = pSLL;
2370     }
2371     pSLL->scanline = scanline;
2372
2373     /*
2374      * now insert the edge in the right bucket
2375      */
2376     prev = (EdgeTableEntry *)NULL;
2377     start = pSLL->edgelist;
2378     while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2379     {
2380         prev = start;
2381         start = start->next;
2382     }
2383     ETE->next = start;
2384
2385     if (prev)
2386         prev->next = ETE;
2387     else
2388         pSLL->edgelist = ETE;
2389 }
2390
2391 /***********************************************************************
2392  *     REGION_CreateEdgeTable
2393  *
2394  *     This routine creates the edge table for
2395  *     scan converting polygons.
2396  *     The Edge Table (ET) looks like:
2397  *
2398  *    EdgeTable
2399  *     --------
2400  *    |  ymax  |        ScanLineLists
2401  *    |scanline|-->------------>-------------->...
2402  *     --------   |scanline|   |scanline|
2403  *                |edgelist|   |edgelist|
2404  *                ---------    ---------
2405  *                    |             |
2406  *                    |             |
2407  *                    V             V
2408  *              list of ETEs   list of ETEs
2409  *
2410  *     where ETE is an EdgeTableEntry data structure,
2411  *     and there is one ScanLineList per scanline at
2412  *     which an edge is initially entered.
2413  *
2414  */
2415 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2416             const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2417             EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2418 {
2419     const POINT *top, *bottom;
2420     const POINT *PrevPt, *CurrPt, *EndPt;
2421     INT poly, count;
2422     int iSLLBlock = 0;
2423     int dy;
2424
2425
2426     /*
2427      *  initialize the Active Edge Table
2428      */
2429     AET->next = (EdgeTableEntry *)NULL;
2430     AET->back = (EdgeTableEntry *)NULL;
2431     AET->nextWETE = (EdgeTableEntry *)NULL;
2432     AET->bres.minor_axis = SMALL_COORDINATE;
2433
2434     /*
2435      *  initialize the Edge Table.
2436      */
2437     ET->scanlines.next = (ScanLineList *)NULL;
2438     ET->ymax = SMALL_COORDINATE;
2439     ET->ymin = LARGE_COORDINATE;
2440     pSLLBlock->next = (ScanLineListBlock *)NULL;
2441
2442     EndPt = pts - 1;
2443     for(poly = 0; poly < nbpolygons; poly++)
2444     {
2445         count = Count[poly];
2446         EndPt += count;
2447         if(count < 2)
2448             continue;
2449
2450         PrevPt = EndPt;
2451
2452     /*
2453      *  for each vertex in the array of points.
2454      *  In this loop we are dealing with two vertices at
2455      *  a time -- these make up one edge of the polygon.
2456      */
2457         while (count--)
2458         {
2459             CurrPt = pts++;
2460
2461         /*
2462          *  find out which point is above and which is below.
2463          */
2464             if (PrevPt->y > CurrPt->y)
2465             {
2466                 bottom = PrevPt, top = CurrPt;
2467                 pETEs->ClockWise = 0;
2468             }
2469             else
2470             {
2471                 bottom = CurrPt, top = PrevPt;
2472                 pETEs->ClockWise = 1;
2473             }
2474
2475         /*
2476          * don't add horizontal edges to the Edge table.
2477          */
2478             if (bottom->y != top->y)
2479             {
2480                 pETEs->ymax = bottom->y-1;
2481                                 /* -1 so we don't get last scanline */
2482
2483             /*
2484              *  initialize integer edge algorithm
2485              */
2486                 dy = bottom->y - top->y;
2487                 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2488
2489                 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2490                                                                 &iSLLBlock);
2491
2492                 if (PrevPt->y > ET->ymax)
2493                   ET->ymax = PrevPt->y;
2494                 if (PrevPt->y < ET->ymin)
2495                   ET->ymin = PrevPt->y;
2496                 pETEs++;
2497             }
2498
2499             PrevPt = CurrPt;
2500         }
2501     }
2502 }
2503
2504 /***********************************************************************
2505  *     REGION_loadAET
2506  *
2507  *     This routine moves EdgeTableEntries from the
2508  *     EdgeTable into the Active Edge Table,
2509  *     leaving them sorted by smaller x coordinate.
2510  *
2511  */
2512 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2513 {
2514     EdgeTableEntry *pPrevAET;
2515     EdgeTableEntry *tmp;
2516
2517     pPrevAET = AET;
2518     AET = AET->next;
2519     while (ETEs)
2520     {
2521         while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2522         {
2523             pPrevAET = AET;
2524             AET = AET->next;
2525         }
2526         tmp = ETEs->next;
2527         ETEs->next = AET;
2528         if (AET)
2529             AET->back = ETEs;
2530         ETEs->back = pPrevAET;
2531         pPrevAET->next = ETEs;
2532         pPrevAET = ETEs;
2533
2534         ETEs = tmp;
2535     }
2536 }
2537
2538 /***********************************************************************
2539  *     REGION_computeWAET
2540  *
2541  *     This routine links the AET by the
2542  *     nextWETE (winding EdgeTableEntry) link for
2543  *     use by the winding number rule.  The final
2544  *     Active Edge Table (AET) might look something
2545  *     like:
2546  *
2547  *     AET
2548  *     ----------  ---------   ---------
2549  *     |ymax    |  |ymax    |  |ymax    |
2550  *     | ...    |  |...     |  |...     |
2551  *     |next    |->|next    |->|next    |->...
2552  *     |nextWETE|  |nextWETE|  |nextWETE|
2553  *     ---------   ---------   ^--------
2554  *         |                   |       |
2555  *         V------------------->       V---> ...
2556  *
2557  */
2558 static void REGION_computeWAET(EdgeTableEntry *AET)
2559 {
2560     register EdgeTableEntry *pWETE;
2561     register int inside = 1;
2562     register int isInside = 0;
2563
2564     AET->nextWETE = (EdgeTableEntry *)NULL;
2565     pWETE = AET;
2566     AET = AET->next;
2567     while (AET)
2568     {
2569         if (AET->ClockWise)
2570             isInside++;
2571         else
2572             isInside--;
2573
2574         if ((!inside && !isInside) ||
2575             ( inside &&  isInside))
2576         {
2577             pWETE->nextWETE = AET;
2578             pWETE = AET;
2579             inside = !inside;
2580         }
2581         AET = AET->next;
2582     }
2583     pWETE->nextWETE = (EdgeTableEntry *)NULL;
2584 }
2585
2586 /***********************************************************************
2587  *     REGION_InsertionSort
2588  *
2589  *     Just a simple insertion sort using
2590  *     pointers and back pointers to sort the Active
2591  *     Edge Table.
2592  *
2593  */
2594 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2595 {
2596     EdgeTableEntry *pETEchase;
2597     EdgeTableEntry *pETEinsert;
2598     EdgeTableEntry *pETEchaseBackTMP;
2599     BOOL changed = FALSE;
2600
2601     AET = AET->next;
2602     while (AET)
2603     {
2604         pETEinsert = AET;
2605         pETEchase = AET;
2606         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2607             pETEchase = pETEchase->back;
2608
2609         AET = AET->next;
2610         if (pETEchase != pETEinsert)
2611         {
2612             pETEchaseBackTMP = pETEchase->back;
2613             pETEinsert->back->next = AET;
2614             if (AET)
2615                 AET->back = pETEinsert->back;
2616             pETEinsert->next = pETEchase;
2617             pETEchase->back->next = pETEinsert;
2618             pETEchase->back = pETEinsert;
2619             pETEinsert->back = pETEchaseBackTMP;
2620             changed = TRUE;
2621         }
2622     }
2623     return changed;
2624 }
2625
2626 /***********************************************************************
2627  *     REGION_FreeStorage
2628  *
2629  *     Clean up our act.
2630  */
2631 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2632 {
2633     ScanLineListBlock   *tmpSLLBlock;
2634
2635     while (pSLLBlock)
2636     {
2637         tmpSLLBlock = pSLLBlock->next;
2638         HeapFree( GetProcessHeap(), 0, pSLLBlock );
2639         pSLLBlock = tmpSLLBlock;
2640     }
2641 }
2642
2643
2644 /***********************************************************************
2645  *     REGION_PtsToRegion
2646  *
2647  *     Create an array of rectangles from a list of points.
2648  */
2649 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2650                        POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2651 {
2652     RECT *rects;
2653     POINT *pts;
2654     POINTBLOCK *CurPtBlock;
2655     int i;
2656     RECT *extents;
2657     INT numRects;
2658
2659     extents = &reg->extents;
2660
2661     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2662
2663     if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2664                            sizeof(RECT) * numRects )))
2665         return(0);
2666
2667     reg->size = numRects;
2668     CurPtBlock = FirstPtBlock;
2669     rects = reg->rects - 1;
2670     numRects = 0;
2671     extents->left = LARGE_COORDINATE,  extents->right = SMALL_COORDINATE;
2672
2673     for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2674         /* the loop uses 2 points per iteration */
2675         i = NUMPTSTOBUFFER >> 1;
2676         if (!numFullPtBlocks)
2677             i = iCurPtBlock >> 1;
2678         for (pts = CurPtBlock->pts; i--; pts += 2) {
2679             if (pts->x == pts[1].x)
2680                 continue;
2681             if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2682                 pts[1].x == rects->right &&
2683                 (numRects == 1 || rects[-1].top != rects->top) &&
2684                 (i && pts[2].y > pts[1].y)) {
2685                 rects->bottom = pts[1].y + 1;
2686                 continue;
2687             }
2688             numRects++;
2689             rects++;
2690             rects->left = pts->x;  rects->top = pts->y;
2691             rects->right = pts[1].x;  rects->bottom = pts[1].y + 1;
2692             if (rects->left < extents->left)
2693                 extents->left = rects->left;
2694             if (rects->right > extents->right)
2695                 extents->right = rects->right;
2696         }
2697         CurPtBlock = CurPtBlock->next;
2698     }
2699
2700     if (numRects) {
2701         extents->top = reg->rects->top;
2702         extents->bottom = rects->bottom;
2703     } else {
2704         extents->left = 0;
2705         extents->top = 0;
2706         extents->right = 0;
2707         extents->bottom = 0;
2708     }
2709     reg->numRects = numRects;
2710
2711     return(TRUE);
2712 }
2713
2714 /***********************************************************************
2715  *           CreatePolyPolygonRgn    (GDI32.@)
2716  */
2717 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2718                       INT nbpolygons, INT mode)
2719 {
2720     HRGN hrgn;
2721     RGNOBJ *obj;
2722     WINEREGION *region;
2723     register EdgeTableEntry *pAET;   /* Active Edge Table       */
2724     register INT y;                /* current scanline        */
2725     register int iPts = 0;           /* number of pts in buffer */
2726     register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
2727     register ScanLineList *pSLL;     /* current scanLineList    */
2728     register POINT *pts;           /* output buffer           */
2729     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
2730     EdgeTable ET;                    /* header node for ET      */
2731     EdgeTableEntry AET;              /* header node for AET     */
2732     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
2733     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
2734     int fixWAET = FALSE;
2735     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
2736     POINTBLOCK *tmpPtBlock;
2737     int numFullPtBlocks = 0;
2738     INT poly, total;
2739
2740     if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2741         return 0;
2742     obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
2743     region = obj->rgn;
2744
2745     /* special case a rectangle */
2746
2747     if (((nbpolygons == 1) && ((*Count == 4) ||
2748        ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2749         (((Pts[0].y == Pts[1].y) &&
2750           (Pts[1].x == Pts[2].x) &&
2751           (Pts[2].y == Pts[3].y) &&
2752           (Pts[3].x == Pts[0].x)) ||
2753          ((Pts[0].x == Pts[1].x) &&
2754           (Pts[1].y == Pts[2].y) &&
2755           (Pts[2].x == Pts[3].x) &&
2756           (Pts[3].y == Pts[0].y))))
2757     {
2758         SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2759                             max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2760         GDI_ReleaseObj( hrgn );
2761         return hrgn;
2762     }
2763
2764     for(poly = total = 0; poly < nbpolygons; poly++)
2765         total += Count[poly];
2766     if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2767     {
2768         REGION_DeleteObject( hrgn, obj );
2769         return 0;
2770     }
2771     pts = FirstPtBlock.pts;
2772     REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2773     pSLL = ET.scanlines.next;
2774     curPtBlock = &FirstPtBlock;
2775
2776     if (mode != WINDING) {
2777         /*
2778          *  for each scanline
2779          */
2780         for (y = ET.ymin; y < ET.ymax; y++) {
2781             /*
2782              *  Add a new edge to the active edge table when we
2783              *  get to the next edge.
2784              */
2785             if (pSLL != NULL && y == pSLL->scanline) {
2786                 REGION_loadAET(&AET, pSLL->edgelist);
2787                 pSLL = pSLL->next;
2788             }
2789             pPrevAET = &AET;
2790             pAET = AET.next;
2791
2792             /*
2793              *  for each active edge
2794              */
2795             while (pAET) {
2796                 pts->x = pAET->bres.minor_axis,  pts->y = y;
2797                 pts++, iPts++;
2798
2799                 /*
2800                  *  send out the buffer
2801                  */
2802                 if (iPts == NUMPTSTOBUFFER) {
2803                     tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2804                     if(!tmpPtBlock) {
2805                         WARN("Can't alloc tPB\n");
2806                         return 0;
2807                     }
2808                     curPtBlock->next = tmpPtBlock;
2809                     curPtBlock = tmpPtBlock;
2810                     pts = curPtBlock->pts;
2811                     numFullPtBlocks++;
2812                     iPts = 0;
2813                 }
2814                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2815             }
2816             REGION_InsertionSort(&AET);
2817         }
2818     }
2819     else {
2820         /*
2821          *  for each scanline
2822          */
2823         for (y = ET.ymin; y < ET.ymax; y++) {
2824             /*
2825              *  Add a new edge to the active edge table when we
2826              *  get to the next edge.
2827              */
2828             if (pSLL != NULL && y == pSLL->scanline) {
2829                 REGION_loadAET(&AET, pSLL->edgelist);
2830                 REGION_computeWAET(&AET);
2831                 pSLL = pSLL->next;
2832             }
2833             pPrevAET = &AET;
2834             pAET = AET.next;
2835             pWETE = pAET;
2836
2837             /*
2838              *  for each active edge
2839              */
2840             while (pAET) {
2841                 /*
2842                  *  add to the buffer only those edges that
2843                  *  are in the Winding active edge table.
2844                  */
2845                 if (pWETE == pAET) {
2846                     pts->x = pAET->bres.minor_axis,  pts->y = y;
2847                     pts++, iPts++;
2848
2849                     /*
2850                      *  send out the buffer
2851                      */
2852                     if (iPts == NUMPTSTOBUFFER) {
2853                         tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2854                                                sizeof(POINTBLOCK) );
2855                         if(!tmpPtBlock) {
2856                             WARN("Can't alloc tPB\n");
2857                             REGION_DeleteObject( hrgn, obj );
2858                             return 0;
2859                         }
2860                         curPtBlock->next = tmpPtBlock;
2861                         curPtBlock = tmpPtBlock;
2862                         pts = curPtBlock->pts;
2863                         numFullPtBlocks++;    iPts = 0;
2864                     }
2865                     pWETE = pWETE->nextWETE;
2866                 }
2867                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2868             }
2869
2870             /*
2871              *  recompute the winding active edge table if
2872              *  we just resorted or have exited an edge.
2873              */
2874             if (REGION_InsertionSort(&AET) || fixWAET) {
2875                 REGION_computeWAET(&AET);
2876                 fixWAET = FALSE;
2877             }
2878         }
2879     }
2880     REGION_FreeStorage(SLLBlock.next);
2881     REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2882
2883     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2884         tmpPtBlock = curPtBlock->next;
2885         HeapFree( GetProcessHeap(), 0, curPtBlock );
2886         curPtBlock = tmpPtBlock;
2887     }
2888     HeapFree( GetProcessHeap(), 0, pETEs );
2889     GDI_ReleaseObj( hrgn );
2890     return hrgn;
2891 }
2892
2893
2894 /***********************************************************************
2895  *           CreatePolygonRgn    (GDI32.@)
2896  */
2897 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2898                                   INT mode )
2899 {
2900     return CreatePolyPolygonRgn( points, &count, 1, mode );
2901 }