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