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