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