region.c 84.5 KB
Newer Older
Alexandre Julliard's avatar
Alexandre Julliard committed
1
/*
Alexandre Julliard's avatar
Alexandre Julliard committed
2 3
 * GDI region objects. Shamelessly ripped out from the X11 distribution
 * Thanks for the nice licence.
Alexandre Julliard's avatar
Alexandre Julliard committed
4
 *
Alexandre Julliard's avatar
Alexandre Julliard committed
5
 * Copyright 1993, 1994, 1995 Alexandre Julliard
Alexandre Julliard's avatar
Alexandre Julliard committed
6
 * Modifications and additions: Copyright 1998 Huw Davies
7
 *					  1999 Alex Korobka
Alexandre Julliard's avatar
Alexandre Julliard committed
8
 *
9 10 11 12 13 14 15 16 17 18 19 20
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * 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
Alexandre Julliard's avatar
Alexandre Julliard committed
22 23
 */

Alexandre Julliard's avatar
Alexandre Julliard committed
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
/************************************************************************

Copyright (c) 1987, 1988  X Consortium

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Except as contained in this notice, the name of the X Consortium shall not be
used in advertising or otherwise to promote the sale, use or other dealings
in this Software without prior written authorization from the X Consortium.


Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.

			All Rights Reserved

54 55
Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
Alexandre Julliard's avatar
Alexandre Julliard committed
56
provided that the above copyright notice appear in all copies and that
57
both that copyright notice and this permission notice appear in
Alexandre Julliard's avatar
Alexandre Julliard committed
58 59
supporting documentation, and that the name of Digital not be
used in advertising or publicity pertaining to distribution of the
60
software without specific, written prior permission.
Alexandre Julliard's avatar
Alexandre Julliard committed
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
SOFTWARE.

************************************************************************/
/*
 * The functions in this file implement the Region abstraction, similar to one
 * used in the X11 sample server. A Region is simply an area, as the name
 * implies, and is implemented as a "y-x-banded" array of rectangles. To
 * explain: Each Region is made up of a certain number of rectangles sorted
 * by y coordinate first, and then by x coordinate.
 *
 * Furthermore, the rectangles are banded such that every rectangle with a
 * given upper-left y coordinate (y1) will have the same lower-right y
 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
 * will span the entire vertical distance of the band. This means that some
 * areas that could be merged into a taller rectangle will be represented as
 * several shorter rectangles to account for shorter rectangles to its left
 * or right but within its "vertical scope".
 *
 * An added constraint on the rectangles is that they must cover as much
 * horizontal area as possible. E.g. no two rectangles in a band are allowed
 * to touch.
 *
 * Whenever possible, bands will be merged together to cover a greater vertical
 * distance (and thus reduce the number of rectangles). Two bands can be merged
 * only if the bottom of one touches the top of the other and they have
 * rectangles in the same places (of the same width, of course). This maintains
 * the y-x-banding that's so nice to have...
 */

97
#include <stdarg.h>
98 99
#include <stdlib.h>
#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"
Alexandre Julliard's avatar
Alexandre Julliard committed
105

106
WINE_DEFAULT_DEBUG_CHANNEL(region);
107

108 109 110 111 112 113 114 115
typedef struct {
    INT size;
    INT numRects;
    RECT *rects;
    RECT extents;
} WINEREGION;

  /* GDI logical region object */
116
typedef struct
117 118 119 120 121 122
{
    GDIOBJHDR   header;
    WINEREGION  *rgn;
} RGNOBJ;


123
static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc );
124 125 126 127 128 129 130 131 132 133 134
static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj );

static const struct gdi_obj_funcs region_funcs =
{
    REGION_SelectObject,  /* pSelectObject */
    NULL,                 /* pGetObjectA */
    NULL,                 /* pGetObjectW */
    NULL,                 /* pUnrealizeObject */
    REGION_DeleteObject   /* pDeleteObject */
};

135 136 137 138 139 140 141 142 143 144 145 146
/*  1 if two RECTs overlap.
 *  0 if two RECTs do not overlap.
 */
#define EXTENTCHECK(r1, r2) \
	((r1)->right > (r2)->left && \
	 (r1)->left < (r2)->right && \
	 (r1)->bottom > (r2)->top && \
	 (r1)->top < (r2)->bottom)

/*
 *   Check to see if there is enough memory in the present region.
 */
147 148 149 150 151 152 153 154 155 156 157 158 159

static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
    if (reg->numRects >= (reg->size - 1)) {
	*firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
	if (*firstrect == 0)
	    return 0;
	reg->size *= 2;
	*rect = (*firstrect)+reg->numRects;
    }
    return 1;
}

#define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323

#define EMPTY_REGION(pReg) { \
    (pReg)->numRects = 0; \
    (pReg)->extents.left = (pReg)->extents.top = 0; \
    (pReg)->extents.right = (pReg)->extents.bottom = 0; \
 }

#define REGION_NOT_EMPTY(pReg) pReg->numRects

#define INRECT(r, x, y) \
      ( ( ((r).right >  x)) && \
        ( ((r).left <= x)) && \
        ( ((r).bottom >  y)) && \
        ( ((r).top <= y)) )


/*
 * number of points to buffer before sending them off
 * to scanlines() :  Must be an even number
 */
#define NUMPTSTOBUFFER 200

/*
 * used to allocate buffers for points and link
 * the buffers together
 */

typedef struct _POINTBLOCK {
    POINT pts[NUMPTSTOBUFFER];
    struct _POINTBLOCK *next;
} POINTBLOCK;



/*
 *     This file contains a few macros to help track
 *     the edge of a filled object.  The object is assumed
 *     to be filled in scanline order, and thus the
 *     algorithm used is an extension of Bresenham's line
 *     drawing algorithm which assumes that y is always the
 *     major axis.
 *     Since these pieces of code are the same for any filled shape,
 *     it is more convenient to gather the library in one
 *     place, but since these pieces of code are also in
 *     the inner loops of output primitives, procedure call
 *     overhead is out of the question.
 *     See the author for a derivation if needed.
 */


/*
 *  In scan converting polygons, we want to choose those pixels
 *  which are inside the polygon.  Thus, we add .5 to the starting
 *  x coordinate for both left and right edges.  Now we choose the
 *  first pixel which is inside the pgon for the left edge and the
 *  first pixel which is outside the pgon for the right edge.
 *  Draw the left pixel, but not the right.
 *
 *  How to add .5 to the starting x coordinate:
 *      If the edge is moving to the right, then subtract dy from the
 *  error term from the general form of the algorithm.
 *      If the edge is moving to the left, then add dy to the error term.
 *
 *  The reason for the difference between edges moving to the left
 *  and edges moving to the right is simple:  If an edge is moving
 *  to the right, then we want the algorithm to flip immediately.
 *  If it is moving to the left, then we don't want it to flip until
 *  we traverse an entire pixel.
 */
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
    int dx;      /* local storage */ \
\
    /* \
     *  if the edge is horizontal, then it is ignored \
     *  and assumed not to be processed.  Otherwise, do this stuff. \
     */ \
    if ((dy) != 0) { \
        xStart = (x1); \
        dx = (x2) - xStart; \
        if (dx < 0) { \
            m = dx / (dy); \
            m1 = m - 1; \
            incr1 = -2 * dx + 2 * (dy) * m1; \
            incr2 = -2 * dx + 2 * (dy) * m; \
            d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
        } else { \
            m = dx / (dy); \
            m1 = m + 1; \
            incr1 = 2 * dx - 2 * (dy) * m1; \
            incr2 = 2 * dx - 2 * (dy) * m; \
            d = -2 * m * (dy) + 2 * dx; \
        } \
    } \
}

#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
    if (m1 > 0) { \
        if (d > 0) { \
            minval += m1; \
            d += incr1; \
        } \
        else { \
            minval += m; \
            d += incr2; \
        } \
    } else {\
        if (d >= 0) { \
            minval += m1; \
            d += incr1; \
        } \
        else { \
            minval += m; \
            d += incr2; \
        } \
    } \
}

/*
 *     This structure contains all of the information needed
 *     to run the bresenham algorithm.
 *     The variables may be hardcoded into the declarations
 *     instead of using this structure to make use of
 *     register declarations.
 */
typedef struct {
    INT minor_axis;	/* minor axis        */
    INT d;		/* decision variable */
    INT m, m1;       	/* slope and slope+1 */
    INT incr1, incr2;	/* error increments */
} BRESINFO;


#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
	BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
                     bres.m, bres.m1, bres.incr1, bres.incr2)

#define BRESINCRPGONSTRUCT(bres) \
        BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)



/*
 *     These are the data structures needed to scan
 *     convert regions.  Two different scan conversion
 *     methods are available -- the even-odd method, and
 *     the winding number method.
 *     The even-odd rule states that a point is inside
 *     the polygon if a ray drawn from that point in any
 *     direction will pass through an odd number of
 *     path segments.
 *     By the winding number rule, a point is decided
 *     to be inside the polygon if a ray drawn from that
 *     point in any direction passes through a different
 *     number of clockwise and counter-clockwise path
 *     segments.
 *
 *     These data structures are adapted somewhat from
 *     the algorithm in (Foley/Van Dam) for scan converting
 *     polygons.
 *     The basic algorithm is to start at the top (smallest y)
 *     of the polygon, stepping down to the bottom of
 *     the polygon by incrementing the y coordinate.  We
 *     keep a list of edges which the current scanline crosses,
 *     sorted by x.  This list is called the Active Edge Table (AET)
324
 *     As we change the y-coordinate, we update each entry in
325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
 *     in the active edge table to reflect the edges new xcoord.
 *     This list must be sorted at each scanline in case
 *     two edges intersect.
 *     We also keep a data structure known as the Edge Table (ET),
 *     which keeps track of all the edges which the current
 *     scanline has not yet reached.  The ET is basically a
 *     list of ScanLineList structures containing a list of
 *     edges which are entered at a given scanline.  There is one
 *     ScanLineList per scanline at which an edge is entered.
 *     When we enter a new edge, we move it from the ET to the AET.
 *
 *     From the AET, we can implement the even-odd rule as in
 *     (Foley/Van Dam).
 *     The winding number rule is a little trickier.  We also
 *     keep the EdgeTableEntries in the AET linked by the
 *     nextWETE (winding EdgeTableEntry) link.  This allows
 *     the edges to be linked just as before for updating
 *     purposes, but only uses the edges linked by the nextWETE
 *     link as edges representing spans of the polygon to
 *     drawn (as with the even-odd rule).
 */

/*
 * for the winding number rule
 */
#define CLOCKWISE          1
351
#define COUNTERCLOCKWISE  -1
352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439

typedef struct _EdgeTableEntry {
     INT ymax;           /* ycoord at which we exit this edge. */
     BRESINFO bres;        /* Bresenham info to run the edge     */
     struct _EdgeTableEntry *next;       /* next in the list     */
     struct _EdgeTableEntry *back;       /* for insertion sort   */
     struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
     int ClockWise;        /* flag for winding number rule       */
} EdgeTableEntry;


typedef struct _ScanLineList{
     INT scanline;            /* the scanline represented */
     EdgeTableEntry *edgelist;  /* header node              */
     struct _ScanLineList *next;  /* next in the list       */
} ScanLineList;


typedef struct {
     INT ymax;               /* ymax for the polygon     */
     INT ymin;               /* ymin for the polygon     */
     ScanLineList scanlines;   /* header node              */
} EdgeTable;


/*
 * Here is a struct to help with storage allocation
 * so we can allocate a big chunk at a time, and then take
 * pieces from this heap when we need to.
 */
#define SLLSPERBLOCK 25

typedef struct _ScanLineListBlock {
     ScanLineList SLLs[SLLSPERBLOCK];
     struct _ScanLineListBlock *next;
} ScanLineListBlock;


/*
 *
 *     a few macros for the inner loops of the fill code where
 *     performance considerations don't allow a procedure call.
 *
 *     Evaluate the given edge at the given scanline.
 *     If the edge has expired, then we leave it and fix up
 *     the active edge table; otherwise, we increment the
 *     x value to be ready for the next scanline.
 *     The winding number rule is in effect, so we must notify
 *     the caller when the edge has been removed so he
 *     can reorder the Winding Active Edge Table.
 */
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
   if (pAET->ymax == y) {          /* leaving this edge */ \
      pPrevAET->next = pAET->next; \
      pAET = pPrevAET->next; \
      fixWAET = 1; \
      if (pAET) \
         pAET->back = pPrevAET; \
   } \
   else { \
      BRESINCRPGONSTRUCT(pAET->bres); \
      pPrevAET = pAET; \
      pAET = pAET->next; \
   } \
}


/*
 *     Evaluate the given edge at the given scanline.
 *     If the edge has expired, then we leave it and fix up
 *     the active edge table; otherwise, we increment the
 *     x value to be ready for the next scanline.
 *     The even-odd rule is in effect.
 */
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
   if (pAET->ymax == y) {          /* leaving this edge */ \
      pPrevAET->next = pAET->next; \
      pAET = pPrevAET->next; \
      if (pAET) \
         pAET->back = pPrevAET; \
   } \
   else { \
      BRESINCRPGONSTRUCT(pAET->bres); \
      pPrevAET = pAET; \
      pAET = pAET->next; \
   } \
}

Alexandre Julliard's avatar
Alexandre Julliard committed
440 441 442
/* Note the parameter order is different from the X11 equivalents */

static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
443
static void REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
Alexandre Julliard's avatar
Alexandre Julliard committed
444 445 446 447
static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448
static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
Alexandre Julliard's avatar
Alexandre Julliard committed
449

450
#define RGN_DEFAULT_RECTS	2
Alexandre Julliard's avatar
Alexandre Julliard committed
451

452 453 454 455

/***********************************************************************
 *            get_region_type
 */
456
static inline INT get_region_type( const RGNOBJ *obj )
457 458 459 460 461 462 463 464 465 466
{
    switch(obj->rgn->numRects)
    {
    case 0:  return NULLREGION;
    case 1:  return SIMPLEREGION;
    default: return COMPLEXREGION;
    }
}


Alexandre Julliard's avatar
Alexandre Julliard committed
467 468 469 470 471 472
/***********************************************************************
 *            REGION_DumpRegion
 *            Outputs the contents of a WINEREGION
 */
static void REGION_DumpRegion(WINEREGION *pReg)
{
473
    RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
Alexandre Julliard's avatar
Alexandre Julliard committed
474

475
    TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg,
Alexandre Julliard's avatar
Alexandre Julliard committed
476 477 478
	    pReg->extents.left, pReg->extents.top,
	    pReg->extents.right, pReg->extents.bottom, pReg->numRects);
    for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
479
        TRACE("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
Alexandre Julliard's avatar
Alexandre Julliard committed
480 481 482 483
		       pRect->right, pRect->bottom);
    return;
}

484

Alexandre Julliard's avatar
Alexandre Julliard committed
485 486 487 488
/***********************************************************************
 *            REGION_AllocWineRegion
 *            Create a new empty WINEREGION.
 */
489
static WINEREGION *REGION_AllocWineRegion( INT n )
Alexandre Julliard's avatar
Alexandre Julliard committed
490 491 492
{
    WINEREGION *pReg;

493
    if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
Alexandre Julliard's avatar
Alexandre Julliard committed
494
    {
495
        if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
496 497 498 499 500
        {
            pReg->size = n;
            EMPTY_REGION(pReg);
            return pReg;
        }
501
        HeapFree(GetProcessHeap(), 0, pReg);
Alexandre Julliard's avatar
Alexandre Julliard committed
502
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
503
    return NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
504 505
}

506

Alexandre Julliard's avatar
Alexandre Julliard committed
507 508 509 510
/***********************************************************************
 *          REGION_CreateRegion
 *          Create a new empty region.
 */
511
static HRGN REGION_CreateRegion( INT n )
Alexandre Julliard's avatar
Alexandre Julliard committed
512
{
513
    HRGN hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
514
    RGNOBJ *obj;
515

Michael Stefaniuc's avatar
Michael Stefaniuc committed
516 517
    if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, (HGDIOBJ *)&hrgn,
				&region_funcs ))) return 0;
518
    if(!(obj->rgn = REGION_AllocWineRegion(n))) {
519
        GDI_FreeObject( hrgn, obj );
520
        return 0;
Alexandre Julliard's avatar
Alexandre Julliard committed
521
    }
522
    GDI_ReleaseObj( hrgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
523 524
    return hrgn;
}
Alexandre Julliard's avatar
Alexandre Julliard committed
525

Alexandre Julliard's avatar
Alexandre Julliard committed
526 527 528 529 530
/***********************************************************************
 *           REGION_DestroyWineRegion
 */
static void REGION_DestroyWineRegion( WINEREGION* pReg )
{
531 532
    HeapFree( GetProcessHeap(), 0, pReg->rects );
    HeapFree( GetProcessHeap(), 0, pReg );
Alexandre Julliard's avatar
Alexandre Julliard committed
533
}
Alexandre Julliard's avatar
Alexandre Julliard committed
534 535 536 537

/***********************************************************************
 *           REGION_DeleteObject
 */
538
static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj )
Alexandre Julliard's avatar
Alexandre Julliard committed
539
{
540
    RGNOBJ *rgn = obj;
Alexandre Julliard's avatar
Alexandre Julliard committed
541

542
    TRACE(" %p\n", handle );
543 544 545 546 547 548 549 550

    REGION_DestroyWineRegion( rgn->rgn );
    return GDI_FreeObject( handle, obj );
}

/***********************************************************************
 *           REGION_SelectObject
 */
551
static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
552
{
553
    return ULongToHandle(SelectClipRgn( hdc, handle ));
Alexandre Julliard's avatar
Alexandre Julliard committed
554 555
}

Alexandre Julliard's avatar
Alexandre Julliard committed
556

557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585
/***********************************************************************
 *           REGION_OffsetRegion
 *           Offset a WINEREGION by x,y
 */
static void REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn,
                                INT x, INT y )
{
    if( rgn != srcrgn)
        REGION_CopyRegion( rgn, srcrgn);
    if(x || y) {
	int nbox = rgn->numRects;
	RECT *pbox = rgn->rects;

	if(nbox) {
	    while(nbox--) {
	        pbox->left += x;
		pbox->right += x;
		pbox->top += y;
		pbox->bottom += y;
		pbox++;
	    }
	    rgn->extents.left += x;
	    rgn->extents.right += x;
	    rgn->extents.top += y;
	    rgn->extents.bottom += y;
	}
    }
}

Alexandre Julliard's avatar
Alexandre Julliard committed
586
/***********************************************************************
587
 *           OffsetRgn   (GDI32.@)
588 589 590 591 592 593 594 595 596 597 598 599 600 601 602
 *
 * Moves a region by the specified X- and Y-axis offsets.
 *
 * PARAMS
 *   hrgn [I] Region to offset.
 *   x    [I] Offset right if positive or left if negative.
 *   y    [I] Offset down if positive or up if negative.
 *
 * RETURNS
 *   Success:
 *     NULLREGION - The new region is empty.
 *     SIMPLEREGION - The new region can be represented by one rectangle.
 *     COMPLEXREGION - The new region can only be represented by more than
 *                     one rectangle.
 *   Failure: ERROR
Alexandre Julliard's avatar
Alexandre Julliard committed
603
 */
604
INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
Alexandre Julliard's avatar
Alexandre Julliard committed
605
{
606
    RGNOBJ * obj = GDI_GetObjPtr( hrgn, REGION_MAGIC );
607
    INT ret;
Alexandre Julliard's avatar
Alexandre Julliard committed
608

609
    TRACE("%p %d,%d\n", hrgn, x, y);
610 611 612 613

    if (!obj)
        return ERROR;

614
    REGION_OffsetRegion( obj->rgn, obj->rgn, x, y);
615

616
    ret = get_region_type( obj );
617
    GDI_ReleaseObj( hrgn );
618
    return ret;
Alexandre Julliard's avatar
Alexandre Julliard committed
619 620 621 622
}


/***********************************************************************
623
 *           GetRgnBox    (GDI32.@)
624 625 626 627 628 629 630 631 632 633 634 635 636 637
 *
 * Retrieves the bounding rectangle of the region. The bounding rectangle
 * is the smallest rectangle that contains the entire region.
 *
 * PARAMS
 *   hrgn [I] Region to retrieve bounding rectangle from.
 *   rect [O] Rectangle that will receive the coordinates of the bounding
 *            rectangle.
 *
 * RETURNS
 *     NULLREGION - The new region is empty.
 *     SIMPLEREGION - The new region can be represented by one rectangle.
 *     COMPLEXREGION - The new region can only be represented by more than
 *                     one rectangle.
Alexandre Julliard's avatar
Alexandre Julliard committed
638
 */
639
INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
Alexandre Julliard's avatar
Alexandre Julliard committed
640
{
641
    RGNOBJ * obj = GDI_GetObjPtr( hrgn, REGION_MAGIC );
Alexandre Julliard's avatar
Alexandre Julliard committed
642 643
    if (obj)
    {
644
	INT ret;
Alexandre Julliard's avatar
Alexandre Julliard committed
645 646 647 648
	rect->left = obj->rgn->extents.left;
	rect->top = obj->rgn->extents.top;
	rect->right = obj->rgn->extents.right;
	rect->bottom = obj->rgn->extents.bottom;
649
	TRACE("%p (%d,%d-%d,%d)\n", hrgn,
650
               rect->left, rect->top, rect->right, rect->bottom);
651
	ret = get_region_type( obj );
652
	GDI_ReleaseObj(hrgn);
Alexandre Julliard's avatar
Alexandre Julliard committed
653 654 655
	return ret;
    }
    return ERROR;
Alexandre Julliard's avatar
Alexandre Julliard committed
656 657 658
}


Alexandre Julliard's avatar
Alexandre Julliard committed
659
/***********************************************************************
660
 *           CreateRectRgn   (GDI32.@)
661 662 663 664 665 666 667 668 669 670 671 672
 *
 * Creates a simple rectangular region.
 *
 * PARAMS
 *   left   [I] Left coordinate of rectangle.
 *   top    [I] Top coordinate of rectangle.
 *   right  [I] Right coordinate of rectangle.
 *   bottom [I] Bottom coordinate of rectangle.
 *
 * RETURNS
 *   Success: Handle to region.
 *   Failure: NULL.
Alexandre Julliard's avatar
Alexandre Julliard committed
673
 */
674
HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
Alexandre Julliard's avatar
Alexandre Julliard committed
675
{
676
    HRGN hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
677

678 679 680
    /* Allocate 2 rects by default to reduce the number of reallocs */

    if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
Alexandre Julliard's avatar
Alexandre Julliard committed
681
	return 0;
682
    TRACE("%d,%d-%d,%d\n", left, top, right, bottom);
683
    SetRectRgn(hrgn, left, top, right, bottom);
Alexandre Julliard's avatar
Alexandre Julliard committed
684
    return hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
685 686
}

Alexandre Julliard's avatar
Alexandre Julliard committed
687 688

/***********************************************************************
689
 *           CreateRectRgnIndirect    (GDI32.@)
690 691 692 693 694 695 696 697 698
 *
 * Creates a simple rectangular region.
 *
 * PARAMS
 *   rect [I] Coordinates of rectangular region.
 *
 * RETURNS
 *   Success: Handle to region.
 *   Failure: NULL.
Alexandre Julliard's avatar
Alexandre Julliard committed
699
 */
700
HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
Alexandre Julliard's avatar
Alexandre Julliard committed
701
{
702
    return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
Alexandre Julliard's avatar
Alexandre Julliard committed
703
}
Alexandre Julliard's avatar
Alexandre Julliard committed
704 705


Alexandre Julliard's avatar
Alexandre Julliard committed
706
/***********************************************************************
707
 *           SetRectRgn    (GDI32.@)
708
 *
709 710 711 712 713 714 715 716 717 718 719 720 721 722 723
 * Sets a region to a simple rectangular region.
 *
 * PARAMS
 *   hrgn   [I] Region to convert.
 *   left   [I] Left coordinate of rectangle.
 *   top    [I] Top coordinate of rectangle.
 *   right  [I] Right coordinate of rectangle.
 *   bottom [I] Bottom coordinate of rectangle.
 *
 * RETURNS
 *   Success: Non-zero.
 *   Failure: Zero.
 *
 * NOTES
 *   Allows either or both left and top to be greater than right or bottom.
Alexandre Julliard's avatar
Alexandre Julliard committed
724
 */
725
BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
726
			  INT right, INT bottom )
Alexandre Julliard's avatar
Alexandre Julliard committed
727 728 729
{
    RGNOBJ * obj;

730
    TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
731

732
    if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
733

734 735
    if (left > right) { INT tmp = left; left = right; right = tmp; }
    if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
736 737

    if((left != right) && (top != bottom))
Alexandre Julliard's avatar
Alexandre Julliard committed
738
    {
Alexandre Julliard's avatar
Alexandre Julliard committed
739 740 741 742
        obj->rgn->rects->left = obj->rgn->extents.left = left;
        obj->rgn->rects->top = obj->rgn->extents.top = top;
        obj->rgn->rects->right = obj->rgn->extents.right = right;
        obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
743
        obj->rgn->numRects = 1;
Alexandre Julliard's avatar
Alexandre Julliard committed
744
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
745 746 747
    else
	EMPTY_REGION(obj->rgn);

748
    GDI_ReleaseObj( hrgn );
749
    return TRUE;
Alexandre Julliard's avatar
Alexandre Julliard committed
750 751 752
}


Alexandre Julliard's avatar
Alexandre Julliard committed
753
/***********************************************************************
754
 *           CreateRoundRectRgn    (GDI32.@)
755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772
 *
 * Creates a rectangular region with rounded corners.
 *
 * PARAMS
 *   left           [I] Left coordinate of rectangle.
 *   top            [I] Top coordinate of rectangle.
 *   right          [I] Right coordinate of rectangle.
 *   bottom         [I] Bottom coordinate of rectangle.
 *   ellipse_width  [I] Width of the ellipse at each corner.
 *   ellipse_height [I] Height of the ellipse at each corner.
 *
 * RETURNS
 *   Success: Handle to region.
 *   Failure: NULL.
 *
 * NOTES
 *   If ellipse_width or ellipse_height is less than 2 logical units then
 *   it is treated as though CreateRectRgn() was called instead.
Alexandre Julliard's avatar
Alexandre Julliard committed
773
 */
774 775 776
HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
				    INT right, INT bottom,
				    INT ellipse_width, INT ellipse_height )
Alexandre Julliard's avatar
Alexandre Julliard committed
777
{
Alexandre Julliard's avatar
Alexandre Julliard committed
778
    RGNOBJ * obj;
779
    HRGN hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
780
    int asq, bsq, d, xd, yd;
781
    RECT rect;
Alexandre Julliard's avatar
Alexandre Julliard committed
782

783 784
      /* Make the dimensions sensible */

785 786
    if (left > right) { INT tmp = left; left = right; right = tmp; }
    if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
787 788 789 790

    ellipse_width = abs(ellipse_width);
    ellipse_height = abs(ellipse_height);

791 792 793 794 795 796 797 798 799 800
      /* Check parameters */

    if (ellipse_width > right-left) ellipse_width = right-left;
    if (ellipse_height > bottom-top) ellipse_height = bottom-top;

      /* Check if we can do a normal rectangle instead */

    if ((ellipse_width < 2) || (ellipse_height < 2))
        return CreateRectRgn( left, top, right, bottom );

Alexandre Julliard's avatar
Alexandre Julliard committed
801 802
      /* Create region */

803 804
    d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
    if (!(hrgn = REGION_CreateRegion(d))) return 0;
805
    if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
806
    TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
807
	  left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
808 809 810 811 812 813 814 815 816 817

      /* Ellipse algorithm, based on an article by K. Porter */
      /* in DDJ Graphics Programming Column, 8/89 */

    asq = ellipse_width * ellipse_width / 4;        /* a^2 */
    bsq = ellipse_height * ellipse_height / 4;      /* b^2 */
    d = bsq - asq * ellipse_height / 2 + asq / 4;   /* b^2 - a^2b + a^2/4 */
    xd = 0;
    yd = asq * ellipse_height;                      /* 2a^2b */

Alexandre Julliard's avatar
Alexandre Julliard committed
818
    rect.left   = left + ellipse_width / 2;
819
    rect.right  = right - ellipse_width / 2;
Alexandre Julliard's avatar
Alexandre Julliard committed
820 821 822 823

      /* Loop to draw first half of quadrant */

    while (xd < yd)
Alexandre Julliard's avatar
Alexandre Julliard committed
824
    {
Alexandre Julliard's avatar
Alexandre Julliard committed
825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840
	if (d > 0)  /* if nearest pixel is toward the center */
	{
	      /* move toward center */
	    rect.top = top++;
	    rect.bottom = rect.top + 1;
	    REGION_UnionRectWithRegion( &rect, obj->rgn );
	    rect.top = --bottom;
	    rect.bottom = rect.top + 1;
	    REGION_UnionRectWithRegion( &rect, obj->rgn );
	    yd -= 2*asq;
	    d  -= yd;
	}
	rect.left--;        /* next horiz point */
	rect.right++;
	xd += 2*bsq;
	d  += bsq + xd;
Alexandre Julliard's avatar
Alexandre Julliard committed
841 842
    }

Alexandre Julliard's avatar
Alexandre Julliard committed
843 844 845 846
      /* Loop to draw second half of quadrant */

    d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
    while (yd >= 0)
Alexandre Julliard's avatar
Alexandre Julliard committed
847
    {
Alexandre Julliard's avatar
Alexandre Julliard committed
848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863
	  /* next vertical point */
	rect.top = top++;
	rect.bottom = rect.top + 1;
	REGION_UnionRectWithRegion( &rect, obj->rgn );
	rect.top = --bottom;
	rect.bottom = rect.top + 1;
	REGION_UnionRectWithRegion( &rect, obj->rgn );
	if (d < 0)   /* if nearest pixel is outside ellipse */
	{
	    rect.left--;     /* move away from center */
	    rect.right++;
	    xd += 2*bsq;
	    d  += xd;
	}
	yd -= 2*asq;
	d  += asq - yd;
Alexandre Julliard's avatar
Alexandre Julliard committed
864 865
    }

Alexandre Julliard's avatar
Alexandre Julliard committed
866
      /* Add the inside rectangle */
Alexandre Julliard's avatar
Alexandre Julliard committed
867

Alexandre Julliard's avatar
Alexandre Julliard committed
868 869
    if (top <= bottom)
    {
Alexandre Julliard's avatar
Alexandre Julliard committed
870 871 872
	rect.top = top;
	rect.bottom = bottom;
	REGION_UnionRectWithRegion( &rect, obj->rgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
873
    }
874
    GDI_ReleaseObj( hrgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
875
    return hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
876 877 878
}


Alexandre Julliard's avatar
Alexandre Julliard committed
879
/***********************************************************************
880
 *           CreateEllipticRgn    (GDI32.@)
881 882 883 884 885 886 887 888 889 890 891 892 893 894 895
 *
 * Creates an elliptical region.
 *
 * PARAMS
 *   left   [I] Left coordinate of bounding rectangle.
 *   top    [I] Top coordinate of bounding rectangle.
 *   right  [I] Right coordinate of bounding rectangle.
 *   bottom [I] Bottom coordinate of bounding rectangle.
 *
 * RETURNS
 *   Success: Handle to region.
 *   Failure: NULL.
 *
 * NOTES
 *   This is a special case of CreateRoundRectRgn() where the width of the
896
 *   ellipse at each corner is equal to the width the rectangle and
897
 *   the same for the height.
Alexandre Julliard's avatar
Alexandre Julliard committed
898
 */
899 900
HRGN WINAPI CreateEllipticRgn( INT left, INT top,
				   INT right, INT bottom )
Alexandre Julliard's avatar
Alexandre Julliard committed
901
{
902
    return CreateRoundRectRgn( left, top, right, bottom,
Alexandre Julliard's avatar
Alexandre Julliard committed
903
				 right-left, bottom-top );
Alexandre Julliard's avatar
Alexandre Julliard committed
904 905 906 907
}


/***********************************************************************
908
 *           CreateEllipticRgnIndirect    (GDI32.@)
909 910 911 912 913 914 915 916 917 918 919 920
 *
 * Creates an elliptical region.
 *
 * PARAMS
 *   rect [I] Pointer to bounding rectangle of the ellipse.
 *
 * RETURNS
 *   Success: Handle to region.
 *   Failure: NULL.
 *
 * NOTES
 *   This is a special case of CreateRoundRectRgn() where the width of the
921
 *   ellipse at each corner is equal to the width the rectangle and
922
 *   the same for the height.
Alexandre Julliard's avatar
Alexandre Julliard committed
923
 */
924
HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
Alexandre Julliard's avatar
Alexandre Julliard committed
925
{
926
    return CreateRoundRectRgn( rect->left, rect->top, rect->right,
Alexandre Julliard's avatar
Alexandre Julliard committed
927 928
				 rect->bottom, rect->right - rect->left,
				 rect->bottom - rect->top );
Alexandre Julliard's avatar
Alexandre Julliard committed
929 930 931
}

/***********************************************************************
932
 *           GetRegionData   (GDI32.@)
933
 *
934
 * Retrieves the data that specifies the region.
935
 *
936 937 938 939
 * PARAMS
 *   hrgn    [I] Region to retrieve the region data from.
 *   count   [I] The size of the buffer pointed to by rgndata in bytes.
 *   rgndata [I] The buffer to receive data about the region.
940
 *
941 942 943 944 945 946 947 948 949 950 951
 * RETURNS
 *   Success: If rgndata is NULL then the required number of bytes. Otherwise,
 *            the number of bytes copied to the output buffer.
 *   Failure: 0.
 *
 * NOTES
 *   The format of the Buffer member of RGNDATA is determined by the iType
 *   member of the region data header.
 *   Currently this is always RDH_RECTANGLES, which specifies that the format
 *   is the array of RECT's that specify the region. The length of the array
 *   is specified by the nCount member of the region data header.
Alexandre Julliard's avatar
Alexandre Julliard committed
952
 */
953
DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
Alexandre Julliard's avatar
Alexandre Julliard committed
954
{
Alexandre Julliard's avatar
Alexandre Julliard committed
955
    DWORD size;
956
    RGNOBJ *obj = GDI_GetObjPtr( hrgn, REGION_MAGIC );
957

958
    TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
Alexandre Julliard's avatar
Alexandre Julliard committed
959

Alexandre Julliard's avatar
Alexandre Julliard committed
960
    if(!obj) return 0;
Alexandre Julliard's avatar
Alexandre Julliard committed
961

962
    size = obj->rgn->numRects * sizeof(RECT);
Alexandre Julliard's avatar
Alexandre Julliard committed
963 964
    if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
    {
965
        GDI_ReleaseObj( hrgn );
966
	if (rgndata) /* buffer is too small, signal it by return 0 */
967
	    return 0;
968 969
	else		/* user requested buffer size with rgndata NULL */
	    return size + sizeof(RGNDATAHEADER);
Alexandre Julliard's avatar
Alexandre Julliard committed
970
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
971

Alexandre Julliard's avatar
Alexandre Julliard committed
972 973 974 975 976 977 978 979
    rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
    rgndata->rdh.iType = RDH_RECTANGLES;
    rgndata->rdh.nCount = obj->rgn->numRects;
    rgndata->rdh.nRgnSize = size;
    rgndata->rdh.rcBound.left = obj->rgn->extents.left;
    rgndata->rdh.rcBound.top = obj->rgn->extents.top;
    rgndata->rdh.rcBound.right = obj->rgn->extents.right;
    rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
Alexandre Julliard's avatar
Alexandre Julliard committed
980

Alexandre Julliard's avatar
Alexandre Julliard committed
981
    memcpy( rgndata->Buffer, obj->rgn->rects, size );
Alexandre Julliard's avatar
Alexandre Julliard committed
982

983
    GDI_ReleaseObj( hrgn );
984
    return size + sizeof(RGNDATAHEADER);
Alexandre Julliard's avatar
Alexandre Julliard committed
985
}
Alexandre Julliard's avatar
Alexandre Julliard committed
986

987

988 989 990 991
static void translate( POINT *pt, UINT count, const XFORM *xform )
{
    while (count--)
    {
992 993
        double x = pt->x;
        double y = pt->y;
994 995 996 997 998 999 1000
        pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
        pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
        pt++;
    }
}


Alexandre Julliard's avatar
Alexandre Julliard committed
1001
/***********************************************************************
1002
 *           ExtCreateRegion   (GDI32.@)
1003
 *
1004 1005 1006 1007 1008
 * Creates a region as specified by the transformation data and region data.
 *
 * PARAMS
 *   lpXform [I] World-space to logical-space transformation data.
 *   dwCount [I] Size of the data pointed to by rgndata, in bytes.
Austin English's avatar
Austin English committed
1009
 *   rgndata [I] Data that specifies the region.
1010 1011 1012 1013 1014 1015 1016
 *
 * RETURNS
 *   Success: Handle to region.
 *   Failure: NULL.
 *
 * NOTES
 *   See GetRegionData().
Alexandre Julliard's avatar
Alexandre Julliard committed
1017
 */
1018
HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
Alexandre Julliard's avatar
Alexandre Julliard committed
1019
{
1020
    HRGN hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
1021

1022
    TRACE(" %p %d %p\n", lpXform, dwCount, rgndata );
1023

1024 1025 1026 1027 1028
    if (!rgndata)
    {
        SetLastError( ERROR_INVALID_PARAMETER );
        return 0;
    }
1029

1030 1031 1032 1033
    if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
        return 0;

    /* XP doesn't care about the type */
1034
    if( rgndata->rdh.iType != RDH_RECTANGLES )
1035 1036 1037
        WARN("(Unsupported region data type: %u)\n", rgndata->rdh.iType);

    if (lpXform)
Alexandre Julliard's avatar
Alexandre Julliard committed
1038
    {
1039
        RECT *pCurRect, *pEndRect;
1040

1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064
        hrgn = CreateRectRgn( 0, 0, 0, 0 );

        pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
        for (pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
        {
            static const INT count = 4;
            HRGN poly_hrgn;
            POINT pt[4];

            pt[0].x = pCurRect->left;
            pt[0].y = pCurRect->top;
            pt[1].x = pCurRect->right;
            pt[1].y = pCurRect->top;
            pt[2].x = pCurRect->right;
            pt[2].y = pCurRect->bottom;
            pt[3].x = pCurRect->left;
            pt[3].y = pCurRect->bottom;

            translate( pt, 4, lpXform );
            poly_hrgn = CreatePolyPolygonRgn( pt, &count, 1, WINDING );
            CombineRgn( hrgn, hrgn, poly_hrgn, RGN_OR );
            DeleteObject( poly_hrgn );
        }
        return hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
1065
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
1066

1067 1068 1069
    if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
    {
	RECT *pCurRect, *pEndRect;
1070
        RGNOBJ *obj = GDI_GetObjPtr( hrgn, REGION_MAGIC );
Alexandre Julliard's avatar
Alexandre Julliard committed
1071

1072 1073 1074
	if (obj) {
            pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
            for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1075 1076 1077 1078
            {
                if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
                    REGION_UnionRectWithRegion( pCurRect, obj->rgn );
            }
1079
	    GDI_ReleaseObj( hrgn );
1080

1081
            TRACE("-- %p\n", hrgn );
1082 1083
            return hrgn;
        }
1084
	else ERR("Could not get pointer to newborn Region!\n");
1085
    }
1086

1087
    return 0;
Alexandre Julliard's avatar
Alexandre Julliard committed
1088 1089
}

Alexandre Julliard's avatar
Alexandre Julliard committed
1090 1091

/***********************************************************************
1092
 *           PtInRegion    (GDI32.@)
1093 1094 1095 1096 1097 1098 1099 1100 1101 1102
 *
 * Tests whether the specified point is inside a region.
 *
 * PARAMS
 *   hrgn [I] Region to test.
 *   x    [I] X-coordinate of point to test.
 *   y    [I] Y-coordinate of point to test.
 *
 * RETURNS
 *   Non-zero if the point is inside the region or zero otherwise.
Alexandre Julliard's avatar
Alexandre Julliard committed
1103
 */
1104
BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
Alexandre Julliard's avatar
Alexandre Julliard committed
1105 1106
{
    RGNOBJ * obj;
1107
    BOOL ret = FALSE;
1108

1109
    if ((obj = GDI_GetObjPtr( hrgn, REGION_MAGIC )))
Alexandre Julliard's avatar
Alexandre Julliard committed
1110
    {
Alexandre Julliard's avatar
Alexandre Julliard committed
1111 1112 1113 1114 1115
	int i;

	if (obj->rgn->numRects > 0 && INRECT(obj->rgn->extents, x, y))
	    for (i = 0; i < obj->rgn->numRects; i++)
		if (INRECT (obj->rgn->rects[i], x, y))
1116
                {
Alexandre Julliard's avatar
Alexandre Julliard committed
1117
		    ret = TRUE;
1118 1119 1120
                    break;
                }
	GDI_ReleaseObj( hrgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
1121
    }
1122
    return ret;
Alexandre Julliard's avatar
Alexandre Julliard committed
1123 1124 1125
}


Alexandre Julliard's avatar
Alexandre Julliard committed
1126
/***********************************************************************
1127
 *           RectInRegion    (GDI32.@)
Alexandre Julliard's avatar
Alexandre Julliard committed
1128
 *
1129 1130 1131 1132 1133 1134 1135 1136 1137
 * Tests if a rectangle is at least partly inside the specified region.
 *
 * PARAMS
 *   hrgn [I] Region to test.
 *   rect [I] Rectangle to test.
 *
 * RETURNS
 *   Non-zero if the rectangle is partially inside the region or
 *   zero otherwise.
Alexandre Julliard's avatar
Alexandre Julliard committed
1138
 */
1139
BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
Alexandre Julliard's avatar
Alexandre Julliard committed
1140 1141
{
    RGNOBJ * obj;
1142
    BOOL ret = FALSE;
1143

1144
    if ((obj = GDI_GetObjPtr( hrgn, REGION_MAGIC )))
Alexandre Julliard's avatar
Alexandre Julliard committed
1145
    {
1146
	RECT *pCurRect, *pRectEnd;
1147

Alexandre Julliard's avatar
Alexandre Julliard committed
1148 1149 1150 1151 1152 1153 1154 1155 1156 1157
    /* this is (just) a useful optimization */
	if ((obj->rgn->numRects > 0) && EXTENTCHECK(&obj->rgn->extents,
						      rect))
	{
	    for (pCurRect = obj->rgn->rects, pRectEnd = pCurRect +
	     obj->rgn->numRects; pCurRect < pRectEnd; pCurRect++)
	    {
	        if (pCurRect->bottom <= rect->top)
		    continue;             /* not far enough down yet */

1158 1159
		if (pCurRect->top >= rect->bottom)
		    break;                /* too far down */
Alexandre Julliard's avatar
Alexandre Julliard committed
1160 1161 1162 1163 1164

		if (pCurRect->right <= rect->left)
		    continue;              /* not far enough over yet */

		if (pCurRect->left >= rect->right) {
1165
		    continue;
Alexandre Julliard's avatar
Alexandre Julliard committed
1166 1167 1168 1169 1170 1171
		}

		ret = TRUE;
		break;
	    }
	}
1172
	GDI_ReleaseObj(hrgn);
Alexandre Julliard's avatar
Alexandre Julliard committed
1173
    }
1174
    return ret;
Alexandre Julliard's avatar
Alexandre Julliard committed
1175 1176
}

Alexandre Julliard's avatar
Alexandre Julliard committed
1177
/***********************************************************************
1178
 *           EqualRgn    (GDI32.@)
1179 1180 1181 1182 1183 1184 1185 1186 1187
 *
 * Tests whether one region is identical to another.
 *
 * PARAMS
 *   hrgn1 [I] The first region to compare.
 *   hrgn2 [I] The second region to compare.
 *
 * RETURNS
 *   Non-zero if both regions are identical or zero otherwise.
Alexandre Julliard's avatar
Alexandre Julliard committed
1188
 */
1189
BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
Alexandre Julliard's avatar
Alexandre Julliard committed
1190 1191
{
    RGNOBJ *obj1, *obj2;
1192
    BOOL ret = FALSE;
Alexandre Julliard's avatar
Alexandre Julliard committed
1193

1194
    if ((obj1 = GDI_GetObjPtr( hrgn1, REGION_MAGIC )))
Alexandre Julliard's avatar
Alexandre Julliard committed
1195
    {
1196
        if ((obj2 = GDI_GetObjPtr( hrgn2, REGION_MAGIC )))
Alexandre Julliard's avatar
Alexandre Julliard committed
1197
	{
Alexandre Julliard's avatar
Alexandre Julliard committed
1198 1199
	    int i;

1200 1201 1202 1203 1204
	    if ( obj1->rgn->numRects != obj2->rgn->numRects ) goto done;
            if ( obj1->rgn->numRects == 0 )
            {
                ret = TRUE;
                goto done;
1205

1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216
            }
            if (obj1->rgn->extents.left   != obj2->rgn->extents.left) goto done;
            if (obj1->rgn->extents.right  != obj2->rgn->extents.right) goto done;
            if (obj1->rgn->extents.top    != obj2->rgn->extents.top) goto done;
            if (obj1->rgn->extents.bottom != obj2->rgn->extents.bottom) goto done;
            for( i = 0; i < obj1->rgn->numRects; i++ )
            {
                if (obj1->rgn->rects[i].left   != obj2->rgn->rects[i].left) goto done;
                if (obj1->rgn->rects[i].right  != obj2->rgn->rects[i].right) goto done;
                if (obj1->rgn->rects[i].top    != obj2->rgn->rects[i].top) goto done;
                if (obj1->rgn->rects[i].bottom != obj2->rgn->rects[i].bottom) goto done;
Alexandre Julliard's avatar
Alexandre Julliard committed
1217
	    }
1218 1219
            ret = TRUE;
        done:
1220
	    GDI_ReleaseObj(hrgn2);
Alexandre Julliard's avatar
Alexandre Julliard committed
1221
	}
1222
	GDI_ReleaseObj(hrgn1);
Alexandre Julliard's avatar
Alexandre Julliard committed
1223
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
1224
    return ret;
Alexandre Julliard's avatar
Alexandre Julliard committed
1225
}
1226

Alexandre Julliard's avatar
Alexandre Julliard committed
1227
/***********************************************************************
Alexandre Julliard's avatar
Alexandre Julliard committed
1228 1229
 *           REGION_UnionRectWithRegion
 *           Adds a rectangle to a WINEREGION
Alexandre Julliard's avatar
Alexandre Julliard committed
1230
 */
1231
static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
Alexandre Julliard's avatar
Alexandre Julliard committed
1232
{
Alexandre Julliard's avatar
Alexandre Julliard committed
1233 1234 1235 1236 1237
    WINEREGION region;

    region.rects = &region.extents;
    region.numRects = 1;
    region.size = 1;
1238
    region.extents = *rect;
Alexandre Julliard's avatar
Alexandre Julliard committed
1239
    REGION_UnionRegion(rgn, rgn, &region);
Alexandre Julliard's avatar
Alexandre Julliard committed
1240 1241
}

Alexandre Julliard's avatar
Alexandre Julliard committed
1242

Alexandre Julliard's avatar
Alexandre Julliard committed
1243 1244 1245
/***********************************************************************
 *           REGION_CreateFrameRgn
 *
Alexandre Julliard's avatar
Alexandre Julliard committed
1246
 * Create a region that is a frame around another region.
1247 1248
 * Compute the intersection of the region moved in all 4 directions
 * ( +x, -x, +y, -y) and subtract from the original.
1249
 * The result looks slightly better than in Windows :)
Alexandre Julliard's avatar
Alexandre Julliard committed
1250
 */
1251
BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
Alexandre Julliard's avatar
Alexandre Julliard committed
1252
{
1253
    BOOL bRet;
1254
    RGNOBJ *srcObj = GDI_GetObjPtr( hSrc, REGION_MAGIC );
Alexandre Julliard's avatar
Alexandre Julliard committed
1255

1256
    if (!srcObj) return FALSE;
1257
    if (srcObj->rgn->numRects != 0)
Alexandre Julliard's avatar
Alexandre Julliard committed
1258
    {
1259
        RGNOBJ* destObj = GDI_GetObjPtr( hDest, REGION_MAGIC );
1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
        WINEREGION *tmprgn = REGION_AllocWineRegion( srcObj->rgn->numRects);

        REGION_OffsetRegion( destObj->rgn, srcObj->rgn, -x, 0);
        REGION_OffsetRegion( tmprgn, srcObj->rgn, x, 0);
        REGION_IntersectRegion( destObj->rgn, destObj->rgn, tmprgn);
        REGION_OffsetRegion( tmprgn, srcObj->rgn, 0, -y);
        REGION_IntersectRegion( destObj->rgn, destObj->rgn, tmprgn);
        REGION_OffsetRegion( tmprgn, srcObj->rgn, 0, y);
        REGION_IntersectRegion( destObj->rgn, destObj->rgn, tmprgn);
        REGION_SubtractRegion( destObj->rgn, srcObj->rgn, destObj->rgn);

        REGION_DestroyWineRegion(tmprgn);
1272
	GDI_ReleaseObj ( hDest );
Alexandre Julliard's avatar
Alexandre Julliard committed
1273
	bRet = TRUE;
Alexandre Julliard's avatar
Alexandre Julliard committed
1274
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
1275 1276
    else
	bRet = FALSE;
1277
    GDI_ReleaseObj( hSrc );
Alexandre Julliard's avatar
Alexandre Julliard committed
1278
    return bRet;
Alexandre Julliard's avatar
Alexandre Julliard committed
1279
}
Alexandre Julliard's avatar
Alexandre Julliard committed
1280

Alexandre Julliard's avatar
Alexandre Julliard committed
1281

Alexandre Julliard's avatar
Alexandre Julliard committed
1282
/***********************************************************************
1283
 *           CombineRgn   (GDI32.@)
Alexandre Julliard's avatar
Alexandre Julliard committed
1284
 *
Austin English's avatar
Austin English committed
1285
 * Combines two regions with the specified operation and stores the result
1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308
 * in the specified destination region.
 *
 * PARAMS
 *   hDest [I] The region that receives the combined result.
 *   hSrc1 [I] The first source region.
 *   hSrc2 [I] The second source region.
 *   mode  [I] The way in which the source regions will be combined. See notes.
 *
 * RETURNS
 *   Success:
 *     NULLREGION - The new region is empty.
 *     SIMPLEREGION - The new region can be represented by one rectangle.
 *     COMPLEXREGION - The new region can only be represented by more than
 *                     one rectangle.
 *   Failure: ERROR
 *
 * NOTES
 *   The two source regions can be the same region.
 *   The mode can be one of the following:
 *|  RGN_AND - Intersection of the regions
 *|  RGN_OR - Union of the regions
 *|  RGN_XOR - Unions of the regions minus any intersection.
 *|  RGN_DIFF - Difference (subtraction) of the regions.
Alexandre Julliard's avatar
Alexandre Julliard committed
1309
 */
1310
INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
Alexandre Julliard's avatar
Alexandre Julliard committed
1311
{
1312
    RGNOBJ *destObj = GDI_GetObjPtr( hDest, REGION_MAGIC);
1313
    INT result = ERROR;
Alexandre Julliard's avatar
Alexandre Julliard committed
1314

1315
    TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
Alexandre Julliard's avatar
Alexandre Julliard committed
1316
    if (destObj)
Alexandre Julliard's avatar
Alexandre Julliard committed
1317
    {
1318
        RGNOBJ *src1Obj = GDI_GetObjPtr( hSrc1, REGION_MAGIC);
Alexandre Julliard's avatar
Alexandre Julliard committed
1319

Alexandre Julliard's avatar
Alexandre Julliard committed
1320 1321
	if (src1Obj)
	{
Andreas Mohr's avatar
Andreas Mohr committed
1322
	    TRACE("dump src1Obj:\n");
1323
	    if(TRACE_ON(region))
Alexandre Julliard's avatar
Alexandre Julliard committed
1324
	      REGION_DumpRegion(src1Obj->rgn);
Alexandre Julliard's avatar
Alexandre Julliard committed
1325
	    if (mode == RGN_COPY)
Alexandre Julliard's avatar
Alexandre Julliard committed
1326 1327
	    {
		REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
1328
		result = get_region_type( destObj );
Alexandre Julliard's avatar
Alexandre Julliard committed
1329
	    }
Alexandre Julliard's avatar
Alexandre Julliard committed
1330
	    else
Alexandre Julliard's avatar
Alexandre Julliard committed
1331
	    {
1332
                RGNOBJ *src2Obj = GDI_GetObjPtr( hSrc2, REGION_MAGIC);
Alexandre Julliard's avatar
Alexandre Julliard committed
1333 1334 1335

		if (src2Obj)
		{
Andreas Mohr's avatar
Andreas Mohr committed
1336
		    TRACE("dump src2Obj:\n");
1337
		    if(TRACE_ON(region))
1338
		        REGION_DumpRegion(src2Obj->rgn);
Alexandre Julliard's avatar
Alexandre Julliard committed
1339
		    switch (mode)
Alexandre Julliard's avatar
Alexandre Julliard committed
1340
		    {
Alexandre Julliard's avatar
Alexandre Julliard committed
1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352
		    case RGN_AND:
			REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
			break;
		    case RGN_OR:
			REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
			break;
		    case RGN_XOR:
			REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
			break;
		    case RGN_DIFF:
			REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
			break;
Alexandre Julliard's avatar
Alexandre Julliard committed
1353
		    }
1354
		    result = get_region_type( destObj );
1355
		    GDI_ReleaseObj( hSrc2 );
Alexandre Julliard's avatar
Alexandre Julliard committed
1356
		}
Alexandre Julliard's avatar
Alexandre Julliard committed
1357
	    }
1358
	    GDI_ReleaseObj( hSrc1 );
Alexandre Julliard's avatar
Alexandre Julliard committed
1359
	}
Andreas Mohr's avatar
Andreas Mohr committed
1360
	TRACE("dump destObj:\n");
1361
	if(TRACE_ON(region))
Alexandre Julliard's avatar
Alexandre Julliard committed
1362
	  REGION_DumpRegion(destObj->rgn);
Alexandre Julliard's avatar
Alexandre Julliard committed
1363

1364
	GDI_ReleaseObj( hDest );
1365
    } else {
1366
       ERR("Invalid rgn=%p\n", hDest);
Alexandre Julliard's avatar
Alexandre Julliard committed
1367
    }
Alexandre Julliard's avatar
Alexandre Julliard committed
1368
    return result;
Alexandre Julliard's avatar
Alexandre Julliard committed
1369
}
Alexandre Julliard's avatar
Alexandre Julliard committed
1370

Alexandre Julliard's avatar
Alexandre Julliard committed
1371
/***********************************************************************
Alexandre Julliard's avatar
Alexandre Julliard committed
1372 1373
 *           REGION_SetExtents
 *           Re-calculate the extents of a region
Alexandre Julliard's avatar
Alexandre Julliard committed
1374
 */
Alexandre Julliard's avatar
Alexandre Julliard committed
1375 1376
static void REGION_SetExtents (WINEREGION *pReg)
{
1377
    RECT *pRect, *pRectEnd, *pExtents;
Alexandre Julliard's avatar
Alexandre Julliard committed
1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419

    if (pReg->numRects == 0)
    {
	pReg->extents.left = 0;
	pReg->extents.top = 0;
	pReg->extents.right = 0;
	pReg->extents.bottom = 0;
	return;
    }

    pExtents = &pReg->extents;
    pRect = pReg->rects;
    pRectEnd = &pRect[pReg->numRects - 1];

    /*
     * Since pRect is the first rectangle in the region, it must have the
     * smallest top and since pRectEnd is the last rectangle in the region,
     * it must have the largest bottom, because of banding. Initialize left and
     * right from pRect and pRectEnd, resp., as good things to initialize them
     * to...
     */
    pExtents->left = pRect->left;
    pExtents->top = pRect->top;
    pExtents->right = pRectEnd->right;
    pExtents->bottom = pRectEnd->bottom;

    while (pRect <= pRectEnd)
    {
	if (pRect->left < pExtents->left)
	    pExtents->left = pRect->left;
	if (pRect->right > pExtents->right)
	    pExtents->right = pRect->right;
	pRect++;
    }
}

/***********************************************************************
 *           REGION_CopyRegion
 */
static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
{
    if (dst != src) /*  don't want to copy to itself */
1420
    {
Alexandre Julliard's avatar
Alexandre Julliard committed
1421 1422
	if (dst->size < src->numRects)
	{
1423
	    if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1424
				src->numRects * sizeof(RECT) )))
Alexandre Julliard's avatar
Alexandre Julliard committed
1425 1426 1427 1428 1429 1430 1431 1432 1433
		return;
	    dst->size = src->numRects;
	}
	dst->numRects = src->numRects;
	dst->extents.left = src->extents.left;
	dst->extents.top = src->extents.top;
	dst->extents.right = src->extents.right;
	dst->extents.bottom = src->extents.bottom;
	memcpy((char *) dst->rects, (char *) src->rects,
1434
	       (int) (src->numRects * sizeof(RECT)));
Alexandre Julliard's avatar
Alexandre Julliard committed
1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454
    }
    return;
}

/***********************************************************************
 *           REGION_Coalesce
 *
 *      Attempt to merge the rects in the current band with those in the
 *      previous one. Used only by REGION_RegionOp.
 *
 * Results:
 *      The new index for the previous band.
 *
 * Side Effects:
 *      If coalescing takes place:
 *          - rectangles in the previous band will have their bottom fields
 *            altered.
 *          - pReg->numRects will be decreased.
 *
 */
1455
static INT REGION_Coalesce (
Alexandre Julliard's avatar
Alexandre Julliard committed
1456
	     WINEREGION *pReg, /* Region to coalesce */
1457 1458
	     INT prevStart,  /* Index of start of previous band */
	     INT curStart    /* Index of start of current band */
Alexandre Julliard's avatar
Alexandre Julliard committed
1459
) {
1460 1461 1462 1463 1464 1465
    RECT *pPrevRect;          /* Current rect in previous band */
    RECT *pCurRect;           /* Current rect in current band */
    RECT *pRegEnd;            /* End of region */
    INT curNumRects;          /* Number of rectangles in current band */
    INT prevNumRects;         /* Number of rectangles in previous band */
    INT bandtop;               /* top coordinate for current band */
Alexandre Julliard's avatar
Alexandre Julliard committed
1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484

    pRegEnd = &pReg->rects[pReg->numRects];

    pPrevRect = &pReg->rects[prevStart];
    prevNumRects = curStart - prevStart;

    /*
     * Figure out how many rectangles are in the current band. Have to do
     * this because multiple bands could have been added in REGION_RegionOp
     * at the end when one region has been exhausted.
     */
    pCurRect = &pReg->rects[curStart];
    bandtop = pCurRect->top;
    for (curNumRects = 0;
	 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
	 curNumRects++)
    {
	pCurRect++;
    }
1485

Alexandre Julliard's avatar
Alexandre Julliard committed
1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501
    if (pCurRect != pRegEnd)
    {
	/*
	 * If more than one band was added, we have to find the start
	 * of the last band added so the next coalescing job can start
	 * at the right place... (given when multiple bands are added,
	 * this may be pointless -- see above).
	 */
	pRegEnd--;
	while (pRegEnd[-1].top == pRegEnd->top)
	{
	    pRegEnd--;
	}
	curStart = pRegEnd - pReg->rects;
	pRegEnd = pReg->rects + pReg->numRects;
    }
1502

Alexandre Julliard's avatar
Alexandre Julliard committed
1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569
    if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
	pCurRect -= curNumRects;
	/*
	 * The bands may only be coalesced if the bottom of the previous
	 * matches the top scanline of the current.
	 */
	if (pPrevRect->bottom == pCurRect->top)
	{
	    /*
	     * Make sure the bands have rects in the same places. This
	     * assumes that rects have been added in such a way that they
	     * cover the most area possible. I.e. two rects in a band must
	     * have some horizontal space between them.
	     */
	    do
	    {
		if ((pPrevRect->left != pCurRect->left) ||
		    (pPrevRect->right != pCurRect->right))
		{
		    /*
		     * The bands don't line up so they can't be coalesced.
		     */
		    return (curStart);
		}
		pPrevRect++;
		pCurRect++;
		prevNumRects -= 1;
	    } while (prevNumRects != 0);

	    pReg->numRects -= curNumRects;
	    pCurRect -= curNumRects;
	    pPrevRect -= curNumRects;

	    /*
	     * The bands may be merged, so set the bottom of each rect
	     * in the previous band to that of the corresponding rect in
	     * the current band.
	     */
	    do
	    {
		pPrevRect->bottom = pCurRect->bottom;
		pPrevRect++;
		pCurRect++;
		curNumRects -= 1;
	    } while (curNumRects != 0);

	    /*
	     * If only one band was added to the region, we have to backup
	     * curStart to the start of the previous band.
	     *
	     * If more than one band was added to the region, copy the
	     * other bands down. The assumption here is that the other bands
	     * came from the same region as the current one and no further
	     * coalescing can be done on them since it's all been done
	     * already... curStart is already in the right place.
	     */
	    if (pCurRect == pRegEnd)
	    {
		curStart = prevStart;
	    }
	    else
	    {
		do
		{
		    *pPrevRect++ = *pCurRect++;
		} while (pCurRect != pRegEnd);
	    }
1570

Alexandre Julliard's avatar
Alexandre Julliard committed
1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600
	}
    }
    return (curStart);
}

/***********************************************************************
 *           REGION_RegionOp
 *
 *      Apply an operation to two regions. Called by REGION_Union,
 *      REGION_Inverse, REGION_Subtract, REGION_Intersect...
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      The new region is overwritten.
 *
 * Notes:
 *      The idea behind this function is to view the two regions as sets.
 *      Together they cover a rectangle of area that this function divides
 *      into horizontal bands where points are covered only by one region
 *      or by both. For the first case, the nonOverlapFunc is called with
 *      each the band and the band's upper and lower extents. For the
 *      second, the overlapFunc is called to process the entire band. It
 *      is responsible for clipping the rectangles in the band, though
 *      this function provides the boundaries.
 *      At the end of each band, the new region is coalesced, if possible,
 *      to reduce the number of rectangles in the region.
 *
 */
Alexandre Julliard's avatar
Alexandre Julliard committed
1601 1602 1603 1604
static void REGION_RegionOp(
	    WINEREGION *newReg, /* Place to store result */
	    WINEREGION *reg1,   /* First region in operation */
            WINEREGION *reg2,   /* 2nd region in operation */
1605 1606 1607
	    void (*overlapFunc)(WINEREGION*, RECT*, RECT*, RECT*, RECT*, INT, INT),     /* Function to call for over-lapping bands */
	    void (*nonOverlap1Func)(WINEREGION*, RECT*, RECT*, INT, INT), /* Function to call for non-overlapping bands in region 1 */
	    void (*nonOverlap2Func)(WINEREGION*, RECT*, RECT*, INT, INT)  /* Function to call for non-overlapping bands in region 2 */
Alexandre Julliard's avatar
Alexandre Julliard committed
1608
) {
1609 1610 1611 1612 1613 1614 1615 1616
    RECT *r1;                         /* Pointer into first region */
    RECT *r2;                         /* Pointer into 2d region */
    RECT *r1End;                      /* End of 1st region */
    RECT *r2End;                      /* End of 2d region */
    INT ybot;                         /* Bottom of intersection */
    INT ytop;                         /* Top of intersection */
    RECT *oldRects;                   /* Old rects for newReg */
    INT prevBand;                     /* Index of start of
Alexandre Julliard's avatar
Alexandre Julliard committed
1617
						 * previous band in newReg */
1618
    INT curBand;                      /* Index of start of current
Alexandre Julliard's avatar
Alexandre Julliard committed
1619
						 * band in newReg */
1620 1621 1622 1623
    RECT *r1BandEnd;                  /* End of current band in r1 */
    RECT *r2BandEnd;                  /* End of current band in r2 */
    INT top;                          /* Top of non-overlapping band */
    INT bot;                          /* Bottom of non-overlapping band */
1624

Alexandre Julliard's avatar
Alexandre Julliard committed
1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635
    /*
     * Initialization:
     *  set r1, r2, r1End and r2End appropriately, preserve the important
     * parts of the destination region until the end in case it's one of
     * the two source regions, then mark the "new" region empty, allocating
     * another array of rectangles for it to use.
     */
    r1 = reg1->rects;
    r2 = reg2->rects;
    r1End = r1 + reg1->numRects;
    r2End = r2 + reg2->numRects;
1636

Alexandre Julliard's avatar
Alexandre Julliard committed
1637 1638

    /*
1639
     * newReg may be one of the src regions so we can't empty it. We keep a
Alexandre Julliard's avatar
Alexandre Julliard committed
1640
     * note of its rects pointer (so that we can free them later), preserve its
1641
     * extents and simply set numRects to zero.
Alexandre Julliard's avatar
Alexandre Julliard committed
1642 1643
     */

Alexandre Julliard's avatar
Alexandre Julliard committed
1644
    oldRects = newReg->rects;
Alexandre Julliard's avatar
Alexandre Julliard committed
1645
    newReg->numRects = 0;
Alexandre Julliard's avatar
Alexandre Julliard committed
1646 1647 1648 1649 1650 1651 1652 1653

    /*
     * Allocate a reasonable number of rectangles for the new region. The idea
     * is to allocate enough so the individual functions don't need to
     * reallocate and copy the array, which is time consuming, yet we don't
     * have to worry about using too much memory. I hope to be able to
     * nuke the Xrealloc() at the end of this function eventually.
     */
1654
    newReg->size = max(reg1->numRects,reg2->numRects) * 2;
Alexandre Julliard's avatar
Alexandre Julliard committed
1655

1656
    if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1657
			          sizeof(RECT) * newReg->size )))
Alexandre Julliard's avatar
Alexandre Julliard committed
1658 1659 1660 1661
    {
	newReg->size = 0;
	return;
    }
1662

Alexandre Julliard's avatar
Alexandre Julliard committed
1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679
    /*
     * Initialize ybot and ytop.
     * In the upcoming loop, ybot and ytop serve different functions depending
     * on whether the band being handled is an overlapping or non-overlapping
     * band.
     *  In the case of a non-overlapping band (only one of the regions
     * has points in the band), ybot is the bottom of the most recent
     * intersection and thus clips the top of the rectangles in that band.
     * ytop is the top of the next intersection between the two regions and
     * serves to clip the bottom of the rectangles in the current band.
     *  For an overlapping band (where the two regions intersect), ytop clips
     * the top of the rectangles of both regions and ybot clips the bottoms.
     */
    if (reg1->extents.top < reg2->extents.top)
	ybot = reg1->extents.top;
    else
	ybot = reg2->extents.top;
1680

Alexandre Julliard's avatar
Alexandre Julliard committed
1681 1682 1683 1684 1685 1686 1687 1688 1689 1690
    /*
     * prevBand serves to mark the start of the previous band so rectangles
     * can be coalesced into larger rectangles. qv. miCoalesce, above.
     * In the beginning, there is no previous band, so prevBand == curBand
     * (curBand is set later on, of course, but the first band will always
     * start at index 0). prevBand and curBand must be indices because of
     * the possible expansion, and resultant moving, of the new region's
     * array of rectangles.
     */
    prevBand = 0;
1691

Alexandre Julliard's avatar
Alexandre Julliard committed
1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707
    do
    {
	curBand = newReg->numRects;

	/*
	 * This algorithm proceeds one source-band (as opposed to a
	 * destination band, which is determined by where the two regions
	 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
	 * rectangle after the last one in the current band for their
	 * respective regions.
	 */
	r1BandEnd = r1;
	while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
	{
	    r1BandEnd++;
	}
1708

Alexandre Julliard's avatar
Alexandre Julliard committed
1709 1710 1711 1712 1713
	r2BandEnd = r2;
	while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
	{
	    r2BandEnd++;
	}
1714

Alexandre Julliard's avatar
Alexandre Julliard committed
1715 1716 1717 1718 1719 1720 1721 1722 1723 1724
	/*
	 * First handle the band that doesn't intersect, if any.
	 *
	 * Note that attention is restricted to one band in the
	 * non-intersecting region at once, so if a region has n
	 * bands between the current position and the next place it overlaps
	 * the other, this entire loop will be passed through n times.
	 */
	if (r1->top < r2->top)
	{
1725 1726
	    top = max(r1->top,ybot);
	    bot = min(r1->bottom,r2->top);
Alexandre Julliard's avatar
Alexandre Julliard committed
1727

1728
            if ((top != bot) && (nonOverlap1Func != NULL))
Alexandre Julliard's avatar
Alexandre Julliard committed
1729 1730 1731 1732 1733 1734 1735 1736
	    {
		(* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
	    }

	    ytop = r2->top;
	}
	else if (r2->top < r1->top)
	{
1737 1738
	    top = max(r2->top,ybot);
	    bot = min(r2->bottom,r1->top);
Alexandre Julliard's avatar
Alexandre Julliard committed
1739

1740
            if ((top != bot) && (nonOverlap2Func != NULL))
Alexandre Julliard's avatar
Alexandre Julliard committed
1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766
	    {
		(* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
	    }

	    ytop = r1->top;
	}
	else
	{
	    ytop = r1->top;
	}

	/*
	 * If any rectangles got added to the region, try and coalesce them
	 * with rectangles from the previous band. Note we could just do
	 * this test in miCoalesce, but some machines incur a not
	 * inconsiderable cost for function calls, so...
	 */
	if (newReg->numRects != curBand)
	{
	    prevBand = REGION_Coalesce (newReg, prevBand, curBand);
	}

	/*
	 * Now see if we've hit an intersecting band. The two bands only
	 * intersect if ybot > ytop
	 */
1767
	ybot = min(r1->bottom, r2->bottom);
Alexandre Julliard's avatar
Alexandre Julliard committed
1768 1769 1770 1771 1772 1773
	curBand = newReg->numRects;
	if (ybot > ytop)
	{
	    (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);

	}
1774

Alexandre Julliard's avatar
Alexandre Julliard committed
1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799
	if (newReg->numRects != curBand)
	{
	    prevBand = REGION_Coalesce (newReg, prevBand, curBand);
	}

	/*
	 * If we've finished with a band (bottom == ybot) we skip forward
	 * in the region to the next band.
	 */
	if (r1->bottom == ybot)
	{
	    r1 = r1BandEnd;
	}
	if (r2->bottom == ybot)
	{
	    r2 = r2BandEnd;
	}
    } while ((r1 != r1End) && (r2 != r2End));

    /*
     * Deal with whichever region still has rectangles left.
     */
    curBand = newReg->numRects;
    if (r1 != r1End)
    {
1800
        if (nonOverlap1Func != NULL)
Alexandre Julliard's avatar
Alexandre Julliard committed
1801 1802 1803 1804 1805 1806 1807 1808 1809
	{
	    do
	    {
		r1BandEnd = r1;
		while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
		{
		    r1BandEnd++;
		}
		(* nonOverlap1Func) (newReg, r1, r1BandEnd,
1810
				     max(r1->top,ybot), r1->bottom);
Alexandre Julliard's avatar
Alexandre Julliard committed
1811 1812 1813 1814
		r1 = r1BandEnd;
	    } while (r1 != r1End);
	}
    }
1815
    else if ((r2 != r2End) && (nonOverlap2Func != NULL))
Alexandre Julliard's avatar
Alexandre Julliard committed
1816 1817 1818 1819 1820 1821 1822 1823 1824
    {
	do
	{
	    r2BandEnd = r2;
	    while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
	    {
		 r2BandEnd++;
	    }
	    (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1825
				max(r2->top,ybot), r2->bottom);
Alexandre Julliard's avatar
Alexandre Julliard committed
1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842
	    r2 = r2BandEnd;
	} while (r2 != r2End);
    }

    if (newReg->numRects != curBand)
    {
	(void) REGION_Coalesce (newReg, prevBand, curBand);
    }

    /*
     * A bit of cleanup. To keep regions from growing without bound,
     * we shrink the array of rectangles to match the new number of
     * rectangles in the region. This never goes to 0, however...
     *
     * Only do this stuff if the number of rectangles allocated is more than
     * twice the number of rectangles in the region (a simple optimization...).
     */
1843
    if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
Alexandre Julliard's avatar
Alexandre Julliard committed
1844 1845 1846
    {
	if (REGION_NOT_EMPTY(newReg))
	{
1847
	    RECT *prev_rects = newReg->rects;
Alexandre Julliard's avatar
Alexandre Julliard committed
1848
	    newReg->size = newReg->numRects;
1849
	    newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1850
				   sizeof(RECT) * newReg->size );
Alexandre Julliard's avatar
Alexandre Julliard committed
1851 1852 1853 1854 1855 1856 1857 1858 1859 1860
	    if (! newReg->rects)
		newReg->rects = prev_rects;
	}
	else
	{
	    /*
	     * No point in doing the extra work involved in an Xrealloc if
	     * the region is empty
	     */
	    newReg->size = 1;
1861 1862
	    HeapFree( GetProcessHeap(), 0, newReg->rects );
	    newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
Alexandre Julliard's avatar
Alexandre Julliard committed
1863 1864
	}
    }
1865
    HeapFree( GetProcessHeap(), 0, oldRects );
Alexandre Julliard's avatar
Alexandre Julliard committed
1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885
    return;
}

/***********************************************************************
 *          Region Intersection
 ***********************************************************************/


/***********************************************************************
 *	     REGION_IntersectO
 *
 * Handle an overlapping band for REGION_Intersect.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      Rectangles may be added to the region.
 *
 */
1886 1887
static void REGION_IntersectO(WINEREGION *pReg,  RECT *r1, RECT *r1End,
		RECT *r2, RECT *r2End, INT top, INT bottom)
Alexandre Julliard's avatar
Alexandre Julliard committed
1888 1889

{
1890 1891
    INT       left, right;
    RECT      *pNextRect;
Alexandre Julliard's avatar
Alexandre Julliard committed
1892 1893 1894 1895 1896

    pNextRect = &pReg->rects[pReg->numRects];

    while ((r1 != r1End) && (r2 != r2End))
    {
1897 1898
	left = max(r1->left, r2->left);
	right =	min(r1->right, r2->right);
Alexandre Julliard's avatar
Alexandre Julliard committed
1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950

	/*
	 * If there's any overlap between the two rectangles, add that
	 * overlap to the new region.
	 * There's no need to check for subsumption because the only way
	 * such a need could arise is if some region has two rectangles
	 * right next to each other. Since that should never happen...
	 */
	if (left < right)
	{
	    MEMCHECK(pReg, pNextRect, pReg->rects);
	    pNextRect->left = left;
	    pNextRect->top = top;
	    pNextRect->right = right;
	    pNextRect->bottom = bottom;
	    pReg->numRects += 1;
	    pNextRect++;
	}

	/*
	 * Need to advance the pointers. Shift the one that extends
	 * to the right the least, since the other still has a chance to
	 * overlap with that region's next rectangle, if you see what I mean.
	 */
	if (r1->right < r2->right)
	{
	    r1++;
	}
	else if (r2->right < r1->right)
	{
	    r2++;
	}
	else
	{
	    r1++;
	    r2++;
	}
    }
    return;
}

/***********************************************************************
 *	     REGION_IntersectRegion
 */
static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
				   WINEREGION *reg2)
{
   /* check for trivial reject */
    if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
	(!EXTENTCHECK(&reg1->extents, &reg2->extents)))
	newReg->numRects = 0;
    else
1951
	REGION_RegionOp (newReg, reg1, reg2, REGION_IntersectO, NULL, NULL);
1952

Alexandre Julliard's avatar
Alexandre Julliard committed
1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981
    /*
     * Can't alter newReg's extents before we call miRegionOp because
     * it might be one of the source regions and miRegionOp depends
     * on the extents of those regions being the same. Besides, this
     * way there's no checking against rectangles that will be nuked
     * due to coalescing, so we have to examine fewer rectangles.
     */
    REGION_SetExtents(newReg);
}

/***********************************************************************
 *	     Region Union
 ***********************************************************************/

/***********************************************************************
 *	     REGION_UnionNonO
 *
 *      Handle a non-overlapping band for the union operation. Just
 *      Adds the rectangles into the region. Doesn't have to check for
 *      subsumption or anything.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      pReg->numRects is incremented and the final rectangles overwritten
 *      with the rectangles we're passed.
 *
 */
1982 1983
static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
			      INT top, INT bottom)
Alexandre Julliard's avatar
Alexandre Julliard committed
1984
{
1985
    RECT *pNextRect;
Alexandre Julliard's avatar
Alexandre Julliard committed
1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016

    pNextRect = &pReg->rects[pReg->numRects];

    while (r != rEnd)
    {
	MEMCHECK(pReg, pNextRect, pReg->rects);
	pNextRect->left = r->left;
	pNextRect->top = top;
	pNextRect->right = r->right;
	pNextRect->bottom = bottom;
	pReg->numRects += 1;
	pNextRect++;
	r++;
    }
    return;
}

/***********************************************************************
 *	     REGION_UnionO
 *
 *      Handle an overlapping band for the union operation. Picks the
 *      left-most rectangle each time and merges it into the region.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      Rectangles are overwritten in pReg->rects and pReg->numRects will
 *      be changed.
 *
 */
2017 2018
static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
			   RECT *r2, RECT *r2End, INT top, INT bottom)
Alexandre Julliard's avatar
Alexandre Julliard committed
2019
{
2020
    RECT *pNextRect;
2021

Alexandre Julliard's avatar
Alexandre Julliard committed
2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045
    pNextRect = &pReg->rects[pReg->numRects];

#define MERGERECT(r) \
    if ((pReg->numRects != 0) &&  \
	(pNextRect[-1].top == top) &&  \
	(pNextRect[-1].bottom == bottom) &&  \
	(pNextRect[-1].right >= r->left))  \
    {  \
	if (pNextRect[-1].right < r->right)  \
	{  \
	    pNextRect[-1].right = r->right;  \
	}  \
    }  \
    else  \
    {  \
	MEMCHECK(pReg, pNextRect, pReg->rects);  \
	pNextRect->top = top;  \
	pNextRect->bottom = bottom;  \
	pNextRect->left = r->left;  \
	pNextRect->right = r->right;  \
	pReg->numRects += 1;  \
	pNextRect += 1;  \
    }  \
    r++;
2046

Alexandre Julliard's avatar
Alexandre Julliard committed
2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057
    while ((r1 != r1End) && (r2 != r2End))
    {
	if (r1->left < r2->left)
	{
	    MERGERECT(r1);
	}
	else
	{
	    MERGERECT(r2);
	}
    }
2058

Alexandre Julliard's avatar
Alexandre Julliard committed
2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103
    if (r1 != r1End)
    {
	do
	{
	    MERGERECT(r1);
	} while (r1 != r1End);
    }
    else while (r2 != r2End)
    {
	MERGERECT(r2);
    }
    return;
}

/***********************************************************************
 *	     REGION_UnionRegion
 */
static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
			       WINEREGION *reg2)
{
    /*  checks all the simple cases */

    /*
     * Region 1 and 2 are the same or region 1 is empty
     */
    if ( (reg1 == reg2) || (!(reg1->numRects)) )
    {
	if (newReg != reg2)
	    REGION_CopyRegion(newReg, reg2);
	return;
    }

    /*
     * if nothing to union (region 2 empty)
     */
    if (!(reg2->numRects))
    {
	if (newReg != reg1)
	    REGION_CopyRegion(newReg, reg1);
	return;
    }

    /*
     * Region 1 completely subsumes region 2
     */
2104
    if ((reg1->numRects == 1) &&
Alexandre Julliard's avatar
Alexandre Julliard committed
2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117
	(reg1->extents.left <= reg2->extents.left) &&
	(reg1->extents.top <= reg2->extents.top) &&
	(reg1->extents.right >= reg2->extents.right) &&
	(reg1->extents.bottom >= reg2->extents.bottom))
    {
	if (newReg != reg1)
	    REGION_CopyRegion(newReg, reg1);
	return;
    }

    /*
     * Region 2 completely subsumes region 1
     */
2118
    if ((reg2->numRects == 1) &&
Alexandre Julliard's avatar
Alexandre Julliard committed
2119 2120 2121 2122 2123 2124 2125 2126 2127 2128
	(reg2->extents.left <= reg1->extents.left) &&
	(reg2->extents.top <= reg1->extents.top) &&
	(reg2->extents.right >= reg1->extents.right) &&
	(reg2->extents.bottom >= reg1->extents.bottom))
    {
	if (newReg != reg2)
	    REGION_CopyRegion(newReg, reg2);
	return;
    }

2129
    REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO, REGION_UnionNonO, REGION_UnionNonO);
Alexandre Julliard's avatar
Alexandre Julliard committed
2130

2131 2132 2133 2134
    newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
    newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
    newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
    newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
Alexandre Julliard's avatar
Alexandre Julliard committed
2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153
}

/***********************************************************************
 *	     Region Subtraction
 ***********************************************************************/

/***********************************************************************
 *	     REGION_SubtractNonO1
 *
 *      Deal with non-overlapping band for subtraction. Any parts from
 *      region 2 we discard. Anything from region 1 we add to the region.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      pReg may be affected.
 *
 */
2154
static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
2155
		INT top, INT bottom)
Alexandre Julliard's avatar
Alexandre Julliard committed
2156
{
2157
    RECT *pNextRect;
2158

Alexandre Julliard's avatar
Alexandre Julliard committed
2159
    pNextRect = &pReg->rects[pReg->numRects];
2160

Alexandre Julliard's avatar
Alexandre Julliard committed
2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188
    while (r != rEnd)
    {
	MEMCHECK(pReg, pNextRect, pReg->rects);
	pNextRect->left = r->left;
	pNextRect->top = top;
	pNextRect->right = r->right;
	pNextRect->bottom = bottom;
	pReg->numRects += 1;
	pNextRect++;
	r++;
    }
    return;
}


/***********************************************************************
 *	     REGION_SubtractO
 *
 *      Overlapping band subtraction. x1 is the left-most point not yet
 *      checked.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      pReg may have rectangles added to it.
 *
 */
2189
static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2190
		RECT *r2, RECT *r2End, INT top, INT bottom)
Alexandre Julliard's avatar
Alexandre Julliard committed
2191
{
2192 2193
    RECT *pNextRect;
    INT left;
2194

Alexandre Julliard's avatar
Alexandre Julliard committed
2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209
    left = r1->left;
    pNextRect = &pReg->rects[pReg->numRects];

    while ((r1 != r1End) && (r2 != r2End))
    {
	if (r2->right <= left)
	{
	    /*
	     * Subtrahend missed the boat: go to next subtrahend.
	     */
	    r2++;
	}
	else if (r2->left <= left)
	{
	    /*
2210
	     * Subtrahend precedes minuend: nuke left edge of minuend.
Alexandre Julliard's avatar
Alexandre Julliard committed
2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302
	     */
	    left = r2->right;
	    if (left >= r1->right)
	    {
		/*
		 * Minuend completely covered: advance to next minuend and
		 * reset left fence to edge of new minuend.
		 */
		r1++;
		if (r1 != r1End)
		    left = r1->left;
	    }
	    else
	    {
		/*
		 * Subtrahend now used up since it doesn't extend beyond
		 * minuend
		 */
		r2++;
	    }
	}
	else if (r2->left < r1->right)
	{
	    /*
	     * Left part of subtrahend covers part of minuend: add uncovered
	     * part of minuend to region and skip to next subtrahend.
	     */
	    MEMCHECK(pReg, pNextRect, pReg->rects);
	    pNextRect->left = left;
	    pNextRect->top = top;
	    pNextRect->right = r2->left;
	    pNextRect->bottom = bottom;
	    pReg->numRects += 1;
	    pNextRect++;
	    left = r2->right;
	    if (left >= r1->right)
	    {
		/*
		 * Minuend used up: advance to new...
		 */
		r1++;
		if (r1 != r1End)
		    left = r1->left;
	    }
	    else
	    {
		/*
		 * Subtrahend used up
		 */
		r2++;
	    }
	}
	else
	{
	    /*
	     * Minuend used up: add any remaining piece before advancing.
	     */
	    if (r1->right > left)
	    {
		MEMCHECK(pReg, pNextRect, pReg->rects);
		pNextRect->left = left;
		pNextRect->top = top;
		pNextRect->right = r1->right;
		pNextRect->bottom = bottom;
		pReg->numRects += 1;
		pNextRect++;
	    }
	    r1++;
	    left = r1->left;
	}
    }

    /*
     * Add remaining minuend rectangles to region.
     */
    while (r1 != r1End)
    {
	MEMCHECK(pReg, pNextRect, pReg->rects);
	pNextRect->left = left;
	pNextRect->top = top;
	pNextRect->right = r1->right;
	pNextRect->bottom = bottom;
	pReg->numRects += 1;
	pNextRect++;
	r1++;
	if (r1 != r1End)
	{
	    left = r1->left;
	}
    }
    return;
}
2303

Alexandre Julliard's avatar
Alexandre Julliard committed
2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326
/***********************************************************************
 *	     REGION_SubtractRegion
 *
 *      Subtract regS from regM and leave the result in regD.
 *      S stands for subtrahend, M for minuend and D for difference.
 *
 * Results:
 *      TRUE.
 *
 * Side Effects:
 *      regD is overwritten.
 *
 */
static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
				                       WINEREGION *regS )
{
   /* check for trivial reject */
    if ( (!(regM->numRects)) || (!(regS->numRects))  ||
	(!EXTENTCHECK(&regM->extents, &regS->extents)) )
    {
	REGION_CopyRegion(regD, regM);
	return;
    }
2327

2328
    REGION_RegionOp (regD, regM, regS, REGION_SubtractO, REGION_SubtractNonO1, NULL);
Alexandre Julliard's avatar
Alexandre Julliard committed
2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347

    /*
     * Can't alter newReg's extents before we call miRegionOp because
     * it might be one of the source regions and miRegionOp depends
     * on the extents of those regions being the unaltered. Besides, this
     * way there's no checking against rectangles that will be nuked
     * due to coalescing, so we have to examine fewer rectangles.
     */
    REGION_SetExtents (regD);
}

/***********************************************************************
 *	     REGION_XorRegion
 */
static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
							WINEREGION *srb)
{
    WINEREGION *tra, *trb;

2348
    if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
2349
	(! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
Alexandre Julliard's avatar
Alexandre Julliard committed
2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361
	return;
    REGION_SubtractRegion(tra,sra,srb);
    REGION_SubtractRegion(trb,srb,sra);
    REGION_UnionRegion(dr,tra,trb);
    REGION_DestroyWineRegion(tra);
    REGION_DestroyWineRegion(trb);
    return;
}

/**************************************************************************
 *
 *    Poly Regions
2362
 *
Alexandre Julliard's avatar
Alexandre Julliard committed
2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377
 *************************************************************************/

#define LARGE_COORDINATE  0x7fffffff /* FIXME */
#define SMALL_COORDINATE  0x80000000

/***********************************************************************
 *     REGION_InsertEdgeInET
 *
 *     Insert the given edge into the edge table.
 *     First we must find the correct bucket in the
 *     Edge table, then find the right slot in the
 *     bucket.  Finally, we can insert it.
 *
 */
static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2378
                INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
Alexandre Julliard's avatar
Alexandre Julliard committed
2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389

{
    EdgeTableEntry *start, *prev;
    ScanLineList *pSLL, *pPrevSLL;
    ScanLineListBlock *tmpSLLBlock;

    /*
     * find the right bucket to put the edge into
     */
    pPrevSLL = &ET->scanlines;
    pSLL = pPrevSLL->next;
2390
    while (pSLL && (pSLL->scanline < scanline))
Alexandre Julliard's avatar
Alexandre Julliard committed
2391 2392 2393 2394 2395 2396 2397 2398
    {
        pPrevSLL = pSLL;
        pSLL = pSLL->next;
    }

    /*
     * reassign pSLL (pointer to ScanLineList) if necessary
     */
2399
    if ((!pSLL) || (pSLL->scanline > scanline))
Alexandre Julliard's avatar
Alexandre Julliard committed
2400
    {
2401
        if (*iSLLBlock > SLLSPERBLOCK-1)
Alexandre Julliard's avatar
Alexandre Julliard committed
2402
        {
2403
            tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
Alexandre Julliard's avatar
Alexandre Julliard committed
2404 2405
	    if(!tmpSLLBlock)
	    {
2406
	        WARN("Can't alloc SLLB\n");
Alexandre Julliard's avatar
Alexandre Julliard committed
2407 2408 2409
		return;
	    }
            (*SLLBlock)->next = tmpSLLBlock;
2410
            tmpSLLBlock->next = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2411 2412 2413 2414 2415 2416
            *SLLBlock = tmpSLLBlock;
            *iSLLBlock = 0;
        }
        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);

        pSLL->next = pPrevSLL->next;
2417
        pSLL->edgelist = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2418 2419 2420 2421 2422 2423 2424
        pPrevSLL->next = pSLL;
    }
    pSLL->scanline = scanline;

    /*
     * now insert the edge in the right bucket
     */
2425
    prev = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2426
    start = pSLL->edgelist;
2427
    while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
Alexandre Julliard's avatar
Alexandre Julliard committed
2428 2429 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443
    {
        prev = start;
        start = start->next;
    }
    ETE->next = start;

    if (prev)
        prev->next = ETE;
    else
        pSLL->edgelist = ETE;
}

/***********************************************************************
 *     REGION_CreateEdgeTable
 *
 *     This routine creates the edge table for
2444
 *     scan converting polygons.
Alexandre Julliard's avatar
Alexandre Julliard committed
2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463
 *     The Edge Table (ET) looks like:
 *
 *    EdgeTable
 *     --------
 *    |  ymax  |        ScanLineLists
 *    |scanline|-->------------>-------------->...
 *     --------   |scanline|   |scanline|
 *                |edgelist|   |edgelist|
 *                ---------    ---------
 *                    |             |
 *                    |             |
 *                    V             V
 *              list of ETEs   list of ETEs
 *
 *     where ETE is an EdgeTableEntry data structure,
 *     and there is one ScanLineList per scanline at
 *     which an edge is initially entered.
 *
 */
2464
static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2465
            const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
Alexandre Julliard's avatar
Alexandre Julliard committed
2466 2467
            EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
{
2468 2469 2470
    const POINT *top, *bottom;
    const POINT *PrevPt, *CurrPt, *EndPt;
    INT poly, count;
Alexandre Julliard's avatar
Alexandre Julliard committed
2471 2472 2473
    int iSLLBlock = 0;
    int dy;

2474

Alexandre Julliard's avatar
Alexandre Julliard committed
2475 2476 2477
    /*
     *  initialize the Active Edge Table
     */
2478 2479 2480
    AET->next = NULL;
    AET->back = NULL;
    AET->nextWETE = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2481 2482 2483 2484 2485
    AET->bres.minor_axis = SMALL_COORDINATE;

    /*
     *  initialize the Edge Table.
     */
2486
    ET->scanlines.next = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2487 2488
    ET->ymax = SMALL_COORDINATE;
    ET->ymin = LARGE_COORDINATE;
2489
    pSLLBlock->next = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2490 2491 2492 2493 2494 2495 2496 2497

    EndPt = pts - 1;
    for(poly = 0; poly < nbpolygons; poly++)
    {
        count = Count[poly];
        EndPt += count;
        if(count < 2)
	    continue;
2498

Alexandre Julliard's avatar
Alexandre Julliard committed
2499 2500 2501 2502 2503 2504 2505
	PrevPt = EndPt;

    /*
     *  for each vertex in the array of points.
     *  In this loop we are dealing with two vertices at
     *  a time -- these make up one edge of the polygon.
     */
2506
	while (count--)
Alexandre Julliard's avatar
Alexandre Julliard committed
2507 2508 2509 2510 2511 2512
	{
	    CurrPt = pts++;

        /*
         *  find out which point is above and which is below.
         */
2513
	    if (PrevPt->y > CurrPt->y)
Alexandre Julliard's avatar
Alexandre Julliard committed
2514 2515 2516 2517
	    {
	        bottom = PrevPt, top = CurrPt;
		pETEs->ClockWise = 0;
	    }
2518
	    else
Alexandre Julliard's avatar
Alexandre Julliard committed
2519 2520 2521 2522 2523 2524 2525 2526
	    {
	        bottom = CurrPt, top = PrevPt;
		pETEs->ClockWise = 1;
	    }

        /*
         * don't add horizontal edges to the Edge table.
         */
2527
	    if (bottom->y != top->y)
Alexandre Julliard's avatar
Alexandre Julliard committed
2528 2529 2530 2531 2532 2533 2534 2535 2536 2537
	    {
	        pETEs->ymax = bottom->y-1;
				/* -1 so we don't get last scanline */

            /*
             *  initialize integer edge algorithm
             */
		dy = bottom->y - top->y;
		BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);

2538
		REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
Alexandre Julliard's avatar
Alexandre Julliard committed
2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567
								&iSLLBlock);

		if (PrevPt->y > ET->ymax)
		  ET->ymax = PrevPt->y;
		if (PrevPt->y < ET->ymin)
		  ET->ymin = PrevPt->y;
		pETEs++;
	    }

	    PrevPt = CurrPt;
	}
    }
}

/***********************************************************************
 *     REGION_loadAET
 *
 *     This routine moves EdgeTableEntries from the
 *     EdgeTable into the Active Edge Table,
 *     leaving them sorted by smaller x coordinate.
 *
 */
static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
{
    EdgeTableEntry *pPrevAET;
    EdgeTableEntry *tmp;

    pPrevAET = AET;
    AET = AET->next;
2568
    while (ETEs)
Alexandre Julliard's avatar
Alexandre Julliard committed
2569
    {
2570
        while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
Alexandre Julliard's avatar
Alexandre Julliard committed
2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591
        {
            pPrevAET = AET;
            AET = AET->next;
        }
        tmp = ETEs->next;
        ETEs->next = AET;
        if (AET)
            AET->back = ETEs;
        ETEs->back = pPrevAET;
        pPrevAET->next = ETEs;
        pPrevAET = ETEs;

        ETEs = tmp;
    }
}

/***********************************************************************
 *     REGION_computeWAET
 *
 *     This routine links the AET by the
 *     nextWETE (winding EdgeTableEntry) link for
2592
 *     use by the winding number rule.  The final
Alexandre Julliard's avatar
Alexandre Julliard committed
2593 2594 2595 2596 2597
 *     Active Edge Table (AET) might look something
 *     like:
 *
 *     AET
 *     ----------  ---------   ---------
2598
 *     |ymax    |  |ymax    |  |ymax    |
Alexandre Julliard's avatar
Alexandre Julliard committed
2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612
 *     | ...    |  |...     |  |...     |
 *     |next    |->|next    |->|next    |->...
 *     |nextWETE|  |nextWETE|  |nextWETE|
 *     ---------   ---------   ^--------
 *         |                   |       |
 *         V------------------->       V---> ...
 *
 */
static void REGION_computeWAET(EdgeTableEntry *AET)
{
    register EdgeTableEntry *pWETE;
    register int inside = 1;
    register int isInside = 0;

2613
    AET->nextWETE = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2614 2615
    pWETE = AET;
    AET = AET->next;
2616
    while (AET)
Alexandre Julliard's avatar
Alexandre Julliard committed
2617 2618 2619 2620 2621 2622 2623
    {
        if (AET->ClockWise)
            isInside++;
        else
            isInside--;

        if ((!inside && !isInside) ||
2624
            ( inside &&  isInside))
Alexandre Julliard's avatar
Alexandre Julliard committed
2625 2626 2627 2628 2629 2630 2631
        {
            pWETE->nextWETE = AET;
            pWETE = AET;
            inside = !inside;
        }
        AET = AET->next;
    }
2632
    pWETE->nextWETE = NULL;
Alexandre Julliard's avatar
Alexandre Julliard committed
2633 2634 2635 2636 2637 2638 2639 2640 2641 2642
}

/***********************************************************************
 *     REGION_InsertionSort
 *
 *     Just a simple insertion sort using
 *     pointers and back pointers to sort the Active
 *     Edge Table.
 *
 */
2643
static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
Alexandre Julliard's avatar
Alexandre Julliard committed
2644 2645 2646 2647
{
    EdgeTableEntry *pETEchase;
    EdgeTableEntry *pETEinsert;
    EdgeTableEntry *pETEchaseBackTMP;
2648
    BOOL changed = FALSE;
Alexandre Julliard's avatar
Alexandre Julliard committed
2649 2650

    AET = AET->next;
2651
    while (AET)
Alexandre Julliard's avatar
Alexandre Julliard committed
2652 2653 2654 2655 2656 2657 2658
    {
        pETEinsert = AET;
        pETEchase = AET;
        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
            pETEchase = pETEchase->back;

        AET = AET->next;
2659
        if (pETEchase != pETEinsert)
Alexandre Julliard's avatar
Alexandre Julliard committed
2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678 2679 2680 2681 2682 2683
        {
            pETEchaseBackTMP = pETEchase->back;
            pETEinsert->back->next = AET;
            if (AET)
                AET->back = pETEinsert->back;
            pETEinsert->next = pETEchase;
            pETEchase->back->next = pETEinsert;
            pETEchase->back = pETEinsert;
            pETEinsert->back = pETEchaseBackTMP;
            changed = TRUE;
        }
    }
    return changed;
}

/***********************************************************************
 *     REGION_FreeStorage
 *
 *     Clean up our act.
 */
static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
{
    ScanLineListBlock   *tmpSLLBlock;

2684
    while (pSLLBlock)
Alexandre Julliard's avatar
Alexandre Julliard committed
2685 2686
    {
        tmpSLLBlock = pSLLBlock->next;
2687
        HeapFree( GetProcessHeap(), 0, pSLLBlock );
Alexandre Julliard's avatar
Alexandre Julliard committed
2688 2689 2690 2691 2692 2693 2694 2695 2696 2697
        pSLLBlock = tmpSLLBlock;
    }
}


/***********************************************************************
 *     REGION_PtsToRegion
 *
 *     Create an array of rectangles from a list of points.
 */
2698
static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
Alexandre Julliard's avatar
Alexandre Julliard committed
2699 2700
		       POINTBLOCK *FirstPtBlock, WINEREGION *reg)
{
2701 2702
    RECT *rects;
    POINT *pts;
Alexandre Julliard's avatar
Alexandre Julliard committed
2703 2704
    POINTBLOCK *CurPtBlock;
    int i;
2705 2706
    RECT *extents;
    INT numRects;
2707

Alexandre Julliard's avatar
Alexandre Julliard committed
2708
    extents = &reg->extents;
2709

Alexandre Julliard's avatar
Alexandre Julliard committed
2710
    numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2711 2712

    if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2713
			   sizeof(RECT) * numRects )))
Alexandre Julliard's avatar
Alexandre Julliard committed
2714
        return(0);
2715

Alexandre Julliard's avatar
Alexandre Julliard committed
2716 2717 2718 2719 2720
    reg->size = numRects;
    CurPtBlock = FirstPtBlock;
    rects = reg->rects - 1;
    numRects = 0;
    extents->left = LARGE_COORDINATE,  extents->right = SMALL_COORDINATE;
2721

Alexandre Julliard's avatar
Alexandre Julliard committed
2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758
    for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
	/* the loop uses 2 points per iteration */
	i = NUMPTSTOBUFFER >> 1;
	if (!numFullPtBlocks)
	    i = iCurPtBlock >> 1;
	for (pts = CurPtBlock->pts; i--; pts += 2) {
	    if (pts->x == pts[1].x)
		continue;
	    if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
		pts[1].x == rects->right &&
		(numRects == 1 || rects[-1].top != rects->top) &&
		(i && pts[2].y > pts[1].y)) {
		rects->bottom = pts[1].y + 1;
		continue;
	    }
	    numRects++;
	    rects++;
	    rects->left = pts->x;  rects->top = pts->y;
	    rects->right = pts[1].x;  rects->bottom = pts[1].y + 1;
	    if (rects->left < extents->left)
		extents->left = rects->left;
	    if (rects->right > extents->right)
		extents->right = rects->right;
        }
	CurPtBlock = CurPtBlock->next;
    }

    if (numRects) {
	extents->top = reg->rects->top;
	extents->bottom = rects->bottom;
    } else {
	extents->left = 0;
	extents->top = 0;
	extents->right = 0;
	extents->bottom = 0;
    }
    reg->numRects = numRects;
2759

Alexandre Julliard's avatar
Alexandre Julliard committed
2760 2761 2762 2763
    return(TRUE);
}

/***********************************************************************
2764
 *           CreatePolyPolygonRgn    (GDI32.@)
Alexandre Julliard's avatar
Alexandre Julliard committed
2765
 */
2766
HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2767
		      INT nbpolygons, INT mode)
Alexandre Julliard's avatar
Alexandre Julliard committed
2768
{
2769
    HRGN hrgn;
Alexandre Julliard's avatar
Alexandre Julliard committed
2770 2771 2772
    RGNOBJ *obj;
    WINEREGION *region;
    register EdgeTableEntry *pAET;   /* Active Edge Table       */
2773
    register INT y;                /* current scanline        */
Alexandre Julliard's avatar
Alexandre Julliard committed
2774 2775 2776
    register int iPts = 0;           /* number of pts in buffer */
    register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
    register ScanLineList *pSLL;     /* current scanLineList    */
2777
    register POINT *pts;           /* output buffer           */
Alexandre Julliard's avatar
Alexandre Julliard committed
2778 2779 2780 2781 2782 2783 2784 2785 2786
    EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
    EdgeTable ET;                    /* header node for ET      */
    EdgeTableEntry AET;              /* header node for AET     */
    EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
    ScanLineListBlock SLLBlock;      /* header for scanlinelist */
    int fixWAET = FALSE;
    POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
    POINTBLOCK *tmpPtBlock;
    int numFullPtBlocks = 0;
2787
    INT poly, total;
Alexandre Julliard's avatar
Alexandre Julliard committed
2788

2789 2790
    TRACE("%p, count %d, polygons %d, mode %d\n", Pts, *Count, nbpolygons, mode);

2791
    if(!(hrgn = REGION_CreateRegion(nbpolygons)))
Alexandre Julliard's avatar
Alexandre Julliard committed
2792
        return 0;
2793
    obj = GDI_GetObjPtr( hrgn, REGION_MAGIC );
Alexandre Julliard's avatar
Alexandre Julliard committed
2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808
    region = obj->rgn;

    /* special case a rectangle */

    if (((nbpolygons == 1) && ((*Count == 4) ||
       ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
	(((Pts[0].y == Pts[1].y) &&
	  (Pts[1].x == Pts[2].x) &&
	  (Pts[2].y == Pts[3].y) &&
	  (Pts[3].x == Pts[0].x)) ||
	 ((Pts[0].x == Pts[1].x) &&
	  (Pts[1].y == Pts[2].y) &&
	  (Pts[2].x == Pts[3].x) &&
	  (Pts[3].y == Pts[0].y))))
    {
2809
        SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2810
		            max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2811
	GDI_ReleaseObj( hrgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
2812 2813
	return hrgn;
    }
2814

Alexandre Julliard's avatar
Alexandre Julliard committed
2815 2816
    for(poly = total = 0; poly < nbpolygons; poly++)
        total += Count[poly];
2817
    if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
Alexandre Julliard's avatar
Alexandre Julliard committed
2818 2819 2820 2821 2822 2823 2824 2825
    {
        REGION_DeleteObject( hrgn, obj );
	return 0;
    }
    pts = FirstPtBlock.pts;
    REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
    pSLL = ET.scanlines.next;
    curPtBlock = &FirstPtBlock;
2826

Alexandre Julliard's avatar
Alexandre Julliard committed
2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841
    if (mode != WINDING) {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; y++) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL != NULL && y == pSLL->scanline) {
                REGION_loadAET(&AET, pSLL->edgelist);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;
2842

Alexandre Julliard's avatar
Alexandre Julliard committed
2843 2844 2845 2846 2847 2848
            /*
             *  for each active edge
             */
            while (pAET) {
                pts->x = pAET->bres.minor_axis,  pts->y = y;
                pts++, iPts++;
2849

Alexandre Julliard's avatar
Alexandre Julliard committed
2850 2851 2852 2853
                /*
                 *  send out the buffer
                 */
                if (iPts == NUMPTSTOBUFFER) {
2854
                    tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
Alexandre Julliard's avatar
Alexandre Julliard committed
2855
		    if(!tmpPtBlock) {
2856
		        WARN("Can't alloc tPB\n");
2857
                        HeapFree( GetProcessHeap(), 0, pETEs );
Alexandre Julliard's avatar
Alexandre Julliard committed
2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887
			return 0;
		    }
                    curPtBlock->next = tmpPtBlock;
                    curPtBlock = tmpPtBlock;
                    pts = curPtBlock->pts;
                    numFullPtBlocks++;
                    iPts = 0;
                }
                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
            }
            REGION_InsertionSort(&AET);
        }
    }
    else {
        /*
         *  for each scanline
         */
        for (y = ET.ymin; y < ET.ymax; y++) {
            /*
             *  Add a new edge to the active edge table when we
             *  get to the next edge.
             */
            if (pSLL != NULL && y == pSLL->scanline) {
                REGION_loadAET(&AET, pSLL->edgelist);
                REGION_computeWAET(&AET);
                pSLL = pSLL->next;
            }
            pPrevAET = &AET;
            pAET = AET.next;
            pWETE = pAET;
2888

Alexandre Julliard's avatar
Alexandre Julliard committed
2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899
            /*
             *  for each active edge
             */
            while (pAET) {
                /*
                 *  add to the buffer only those edges that
                 *  are in the Winding active edge table.
                 */
                if (pWETE == pAET) {
                    pts->x = pAET->bres.minor_axis,  pts->y = y;
                    pts++, iPts++;
2900

Alexandre Julliard's avatar
Alexandre Julliard committed
2901 2902 2903 2904
                    /*
                     *  send out the buffer
                     */
                    if (iPts == NUMPTSTOBUFFER) {
2905
                        tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
Alexandre Julliard's avatar
Alexandre Julliard committed
2906 2907
					       sizeof(POINTBLOCK) );
			if(!tmpPtBlock) {
2908
			    WARN("Can't alloc tPB\n");
2909
			    REGION_DeleteObject( hrgn, obj );
2910
                            HeapFree( GetProcessHeap(), 0, pETEs );
Alexandre Julliard's avatar
Alexandre Julliard committed
2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921
			    return 0;
			}
                        curPtBlock->next = tmpPtBlock;
                        curPtBlock = tmpPtBlock;
                        pts = curPtBlock->pts;
                        numFullPtBlocks++;    iPts = 0;
                    }
                    pWETE = pWETE->nextWETE;
                }
                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
            }
2922

Alexandre Julliard's avatar
Alexandre Julliard committed
2923 2924 2925 2926 2927 2928 2929 2930 2931 2932
            /*
             *  recompute the winding active edge table if
             *  we just resorted or have exited an edge.
             */
            if (REGION_InsertionSort(&AET) || fixWAET) {
                REGION_computeWAET(&AET);
                fixWAET = FALSE;
            }
        }
    }
2933
    REGION_FreeStorage(SLLBlock.next);
Alexandre Julliard's avatar
Alexandre Julliard committed
2934
    REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2935

Alexandre Julliard's avatar
Alexandre Julliard committed
2936 2937
    for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
	tmpPtBlock = curPtBlock->next;
2938
	HeapFree( GetProcessHeap(), 0, curPtBlock );
Alexandre Julliard's avatar
Alexandre Julliard committed
2939 2940
	curPtBlock = tmpPtBlock;
    }
2941
    HeapFree( GetProcessHeap(), 0, pETEs );
2942
    GDI_ReleaseObj( hrgn );
Alexandre Julliard's avatar
Alexandre Julliard committed
2943 2944 2945 2946 2947
    return hrgn;
}


/***********************************************************************
2948
 *           CreatePolygonRgn    (GDI32.@)
Alexandre Julliard's avatar
Alexandre Julliard committed
2949
 */
2950 2951
HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
                                  INT mode )
Alexandre Julliard's avatar
Alexandre Julliard committed
2952
{
2953
    return CreatePolyPolygonRgn( points, &count, 1, mode );
Alexandre Julliard's avatar
Alexandre Julliard committed
2954
}