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