2 * GDI region objects. Shamelessly ripped out from the X11 distribution
3 * Thanks for the nice license.
5 * Copyright 1993, 1994, 1995 Alexandre Julliard
6 * Modifications and additions: Copyright 1998 Huw Davies
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
24 /************************************************************************
26 Copyright (c) 1987, 1988 X Consortium
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
70 ************************************************************************/
72 * The functions in this file implement the Region abstraction, similar to one
73 * used in the X11 sample server. A Region is simply an area, as the name
74 * implies, and is implemented as a "y-x-banded" array of rectangles. To
75 * explain: Each Region is made up of a certain number of rectangles sorted
76 * by y coordinate first, and then by x coordinate.
78 * Furthermore, the rectangles are banded such that every rectangle with a
79 * given upper-left y coordinate (y1) will have the same lower-right y
80 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81 * will span the entire vertical distance of the band. This means that some
82 * areas that could be merged into a taller rectangle will be represented as
83 * several shorter rectangles to account for shorter rectangles to its left
84 * or right but within its "vertical scope".
86 * An added constraint on the rectangles is that they must cover as much
87 * horizontal area as possible. E.g. no two rectangles in a band are allowed
90 * Whenever possible, bands will be merged together to cover a greater vertical
91 * distance (and thus reduce the number of rectangles). Two bands can be merged
92 * only if the bottom of one touches the top of the other and they have
93 * rectangles in the same places (of the same width, of course). This maintains
94 * the y-x-banding that's so nice to have...
103 #include "gdi_private.h"
104 #include "wine/debug.h"
106 WINE_DEFAULT_DEBUG_CHANNEL(region);
109 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc );
110 static BOOL REGION_DeleteObject( HGDIOBJ handle );
112 static const struct gdi_obj_funcs region_funcs =
114 REGION_SelectObject, /* pSelectObject */
115 NULL, /* pGetObjectA */
116 NULL, /* pGetObjectW */
117 NULL, /* pUnrealizeObject */
118 REGION_DeleteObject /* pDeleteObject */
121 /* 1 if two RECTs overlap.
122 * 0 if two RECTs do not overlap.
124 #define EXTENTCHECK(r1, r2) \
125 ((r1)->right > (r2)->left && \
126 (r1)->left < (r2)->right && \
127 (r1)->bottom > (r2)->top && \
128 (r1)->top < (r2)->bottom)
131 static BOOL add_rect( WINEREGION *reg, INT left, INT top, INT right, INT bottom )
134 if (reg->numRects >= reg->size)
136 RECT *newrects = HeapReAlloc( GetProcessHeap(), 0, reg->rects, 2 * sizeof(RECT) * reg->size );
137 if (!newrects) return FALSE;
138 reg->rects = newrects;
141 rect = reg->rects + reg->numRects++;
145 rect->bottom = bottom;
149 #define EMPTY_REGION(pReg) do { \
150 (pReg)->numRects = 0; \
151 (pReg)->extents.left = (pReg)->extents.top = 0; \
152 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
155 #define INRECT(r, x, y) \
156 ( ( ((r).right > x)) && \
157 ( ((r).left <= x)) && \
158 ( ((r).bottom > y)) && \
163 * number of points to buffer before sending them off
164 * to scanlines() : Must be an even number
166 #define NUMPTSTOBUFFER 200
169 * used to allocate buffers for points and link
170 * the buffers together
173 typedef struct _POINTBLOCK {
174 POINT pts[NUMPTSTOBUFFER];
175 struct _POINTBLOCK *next;
181 * This file contains a few macros to help track
182 * the edge of a filled object. The object is assumed
183 * to be filled in scanline order, and thus the
184 * algorithm used is an extension of Bresenham's line
185 * drawing algorithm which assumes that y is always the
187 * Since these pieces of code are the same for any filled shape,
188 * it is more convenient to gather the library in one
189 * place, but since these pieces of code are also in
190 * the inner loops of output primitives, procedure call
191 * overhead is out of the question.
192 * See the author for a derivation if needed.
197 * In scan converting polygons, we want to choose those pixels
198 * which are inside the polygon. Thus, we add .5 to the starting
199 * x coordinate for both left and right edges. Now we choose the
200 * first pixel which is inside the pgon for the left edge and the
201 * first pixel which is outside the pgon for the right edge.
202 * Draw the left pixel, but not the right.
204 * How to add .5 to the starting x coordinate:
205 * If the edge is moving to the right, then subtract dy from the
206 * error term from the general form of the algorithm.
207 * If the edge is moving to the left, then add dy to the error term.
209 * The reason for the difference between edges moving to the left
210 * and edges moving to the right is simple: If an edge is moving
211 * to the right, then we want the algorithm to flip immediately.
212 * If it is moving to the left, then we don't want it to flip until
213 * we traverse an entire pixel.
215 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
216 int dx; /* local storage */ \
219 * if the edge is horizontal, then it is ignored \
220 * and assumed not to be processed. Otherwise, do this stuff. \
224 dx = (x2) - xStart; \
228 incr1 = -2 * dx + 2 * (dy) * m1; \
229 incr2 = -2 * dx + 2 * (dy) * m; \
230 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
234 incr1 = 2 * dx - 2 * (dy) * m1; \
235 incr2 = 2 * dx - 2 * (dy) * m; \
236 d = -2 * m * (dy) + 2 * dx; \
241 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
264 * This structure contains all of the information needed
265 * to run the bresenham algorithm.
266 * The variables may be hardcoded into the declarations
267 * instead of using this structure to make use of
268 * register declarations.
271 INT minor_axis; /* minor axis */
272 INT d; /* decision variable */
273 INT m, m1; /* slope and slope+1 */
274 INT incr1, incr2; /* error increments */
278 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
279 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
280 bres.m, bres.m1, bres.incr1, bres.incr2)
282 #define BRESINCRPGONSTRUCT(bres) \
283 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
288 * These are the data structures needed to scan
289 * convert regions. Two different scan conversion
290 * methods are available -- the even-odd method, and
291 * the winding number method.
292 * The even-odd rule states that a point is inside
293 * the polygon if a ray drawn from that point in any
294 * direction will pass through an odd number of
296 * By the winding number rule, a point is decided
297 * to be inside the polygon if a ray drawn from that
298 * point in any direction passes through a different
299 * number of clockwise and counter-clockwise path
302 * These data structures are adapted somewhat from
303 * the algorithm in (Foley/Van Dam) for scan converting
305 * The basic algorithm is to start at the top (smallest y)
306 * of the polygon, stepping down to the bottom of
307 * the polygon by incrementing the y coordinate. We
308 * keep a list of edges which the current scanline crosses,
309 * sorted by x. This list is called the Active Edge Table (AET)
310 * As we change the y-coordinate, we update each entry in
311 * in the active edge table to reflect the edges new xcoord.
312 * This list must be sorted at each scanline in case
313 * two edges intersect.
314 * We also keep a data structure known as the Edge Table (ET),
315 * which keeps track of all the edges which the current
316 * scanline has not yet reached. The ET is basically a
317 * list of ScanLineList structures containing a list of
318 * edges which are entered at a given scanline. There is one
319 * ScanLineList per scanline at which an edge is entered.
320 * When we enter a new edge, we move it from the ET to the AET.
322 * From the AET, we can implement the even-odd rule as in
324 * The winding number rule is a little trickier. We also
325 * keep the EdgeTableEntries in the AET linked by the
326 * nextWETE (winding EdgeTableEntry) link. This allows
327 * the edges to be linked just as before for updating
328 * purposes, but only uses the edges linked by the nextWETE
329 * link as edges representing spans of the polygon to
330 * drawn (as with the even-odd rule).
334 * for the winding number rule
337 #define COUNTERCLOCKWISE -1
339 typedef struct _EdgeTableEntry {
340 INT ymax; /* ycoord at which we exit this edge. */
341 BRESINFO bres; /* Bresenham info to run the edge */
342 struct _EdgeTableEntry *next; /* next in the list */
343 struct _EdgeTableEntry *back; /* for insertion sort */
344 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
345 int ClockWise; /* flag for winding number rule */
349 typedef struct _ScanLineList{
350 INT scanline; /* the scanline represented */
351 EdgeTableEntry *edgelist; /* header node */
352 struct _ScanLineList *next; /* next in the list */
357 INT ymax; /* ymax for the polygon */
358 INT ymin; /* ymin for the polygon */
359 ScanLineList scanlines; /* header node */
364 * Here is a struct to help with storage allocation
365 * so we can allocate a big chunk at a time, and then take
366 * pieces from this heap when we need to.
368 #define SLLSPERBLOCK 25
370 typedef struct _ScanLineListBlock {
371 ScanLineList SLLs[SLLSPERBLOCK];
372 struct _ScanLineListBlock *next;
378 * a few macros for the inner loops of the fill code where
379 * performance considerations don't allow a procedure call.
381 * Evaluate the given edge at the given scanline.
382 * If the edge has expired, then we leave it and fix up
383 * the active edge table; otherwise, we increment the
384 * x value to be ready for the next scanline.
385 * The winding number rule is in effect, so we must notify
386 * the caller when the edge has been removed so he
387 * can reorder the Winding Active Edge Table.
389 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
390 if (pAET->ymax == y) { /* leaving this edge */ \
391 pPrevAET->next = pAET->next; \
392 pAET = pPrevAET->next; \
395 pAET->back = pPrevAET; \
398 BRESINCRPGONSTRUCT(pAET->bres); \
406 * Evaluate the given edge at the given scanline.
407 * If the edge has expired, then we leave it and fix up
408 * the active edge table; otherwise, we increment the
409 * x value to be ready for the next scanline.
410 * The even-odd rule is in effect.
412 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
413 if (pAET->ymax == y) { /* leaving this edge */ \
414 pPrevAET->next = pAET->next; \
415 pAET = pPrevAET->next; \
417 pAET->back = pPrevAET; \
420 BRESINCRPGONSTRUCT(pAET->bres); \
426 /* Note the parameter order is different from the X11 equivalents */
428 static BOOL REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
429 static BOOL REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
430 static BOOL REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
431 static BOOL REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
432 static BOOL REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
433 static BOOL REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
434 static BOOL REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
436 #define RGN_DEFAULT_RECTS 2
439 /***********************************************************************
442 static inline INT get_region_type( const WINEREGION *obj )
444 switch(obj->numRects)
446 case 0: return NULLREGION;
447 case 1: return SIMPLEREGION;
448 default: return COMPLEXREGION;
453 /***********************************************************************
455 * Outputs the contents of a WINEREGION
457 static void REGION_DumpRegion(WINEREGION *pReg)
459 RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
461 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg,
462 pReg->extents.left, pReg->extents.top,
463 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
464 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
465 TRACE("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
466 pRect->right, pRect->bottom);
471 /***********************************************************************
474 * Initialize a new empty region.
476 static BOOL init_region( WINEREGION *pReg, INT n )
478 if (!(pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT )))) return FALSE;
484 /***********************************************************************
487 static void destroy_region( WINEREGION *pReg )
489 HeapFree( GetProcessHeap(), 0, pReg->rects );
492 /***********************************************************************
493 * REGION_DeleteObject
495 static BOOL REGION_DeleteObject( HGDIOBJ handle )
497 WINEREGION *rgn = free_gdi_handle( handle );
499 if (!rgn) return FALSE;
500 HeapFree( GetProcessHeap(), 0, rgn->rects );
501 HeapFree( GetProcessHeap(), 0, rgn );
505 /***********************************************************************
506 * REGION_SelectObject
508 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
510 return ULongToHandle(SelectClipRgn( hdc, handle ));
514 /***********************************************************************
515 * REGION_OffsetRegion
516 * Offset a WINEREGION by x,y
518 static BOOL REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn, INT x, INT y )
522 if (!REGION_CopyRegion( rgn, srcrgn)) return FALSE;
525 int nbox = rgn->numRects;
526 RECT *pbox = rgn->rects;
536 rgn->extents.left += x;
537 rgn->extents.right += x;
538 rgn->extents.top += y;
539 rgn->extents.bottom += y;
545 /***********************************************************************
546 * OffsetRgn (GDI32.@)
548 * Moves a region by the specified X- and Y-axis offsets.
551 * hrgn [I] Region to offset.
552 * x [I] Offset right if positive or left if negative.
553 * y [I] Offset down if positive or up if negative.
557 * NULLREGION - The new region is empty.
558 * SIMPLEREGION - The new region can be represented by one rectangle.
559 * COMPLEXREGION - The new region can only be represented by more than
563 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
565 WINEREGION *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
568 TRACE("%p %d,%d\n", hrgn, x, y);
573 REGION_OffsetRegion( obj, obj, x, y);
575 ret = get_region_type( obj );
576 GDI_ReleaseObj( hrgn );
581 /***********************************************************************
582 * GetRgnBox (GDI32.@)
584 * Retrieves the bounding rectangle of the region. The bounding rectangle
585 * is the smallest rectangle that contains the entire region.
588 * hrgn [I] Region to retrieve bounding rectangle from.
589 * rect [O] Rectangle that will receive the coordinates of the bounding
593 * NULLREGION - The new region is empty.
594 * SIMPLEREGION - The new region can be represented by one rectangle.
595 * COMPLEXREGION - The new region can only be represented by more than
598 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
600 WINEREGION *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
604 rect->left = obj->extents.left;
605 rect->top = obj->extents.top;
606 rect->right = obj->extents.right;
607 rect->bottom = obj->extents.bottom;
608 TRACE("%p (%d,%d-%d,%d)\n", hrgn,
609 rect->left, rect->top, rect->right, rect->bottom);
610 ret = get_region_type( obj );
611 GDI_ReleaseObj(hrgn);
618 /***********************************************************************
619 * CreateRectRgn (GDI32.@)
621 * Creates a simple rectangular region.
624 * left [I] Left coordinate of rectangle.
625 * top [I] Top coordinate of rectangle.
626 * right [I] Right coordinate of rectangle.
627 * bottom [I] Bottom coordinate of rectangle.
630 * Success: Handle to region.
633 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
638 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
640 /* Allocate 2 rects by default to reduce the number of reallocs */
641 if (!init_region( obj, RGN_DEFAULT_RECTS ))
643 HeapFree( GetProcessHeap(), 0, obj );
646 if (!(hrgn = alloc_gdi_handle( obj, OBJ_REGION, ®ion_funcs )))
648 HeapFree( GetProcessHeap(), 0, obj->rects );
649 HeapFree( GetProcessHeap(), 0, obj );
652 TRACE( "%d,%d-%d,%d returning %p\n", left, top, right, bottom, hrgn );
653 SetRectRgn(hrgn, left, top, right, bottom);
658 /***********************************************************************
659 * CreateRectRgnIndirect (GDI32.@)
661 * Creates a simple rectangular region.
664 * rect [I] Coordinates of rectangular region.
667 * Success: Handle to region.
670 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
672 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
676 /***********************************************************************
677 * SetRectRgn (GDI32.@)
679 * Sets a region to a simple rectangular region.
682 * hrgn [I] Region to convert.
683 * left [I] Left coordinate of rectangle.
684 * top [I] Top coordinate of rectangle.
685 * right [I] Right coordinate of rectangle.
686 * bottom [I] Bottom coordinate of rectangle.
693 * Allows either or both left and top to be greater than right or bottom.
695 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
696 INT right, INT bottom )
700 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
702 if (!(obj = GDI_GetObjPtr( hrgn, OBJ_REGION ))) return FALSE;
704 if (left > right) { INT tmp = left; left = right; right = tmp; }
705 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
707 if((left != right) && (top != bottom))
709 obj->rects->left = obj->extents.left = left;
710 obj->rects->top = obj->extents.top = top;
711 obj->rects->right = obj->extents.right = right;
712 obj->rects->bottom = obj->extents.bottom = bottom;
718 GDI_ReleaseObj( hrgn );
723 /***********************************************************************
724 * CreateRoundRectRgn (GDI32.@)
726 * Creates a rectangular region with rounded corners.
729 * left [I] Left coordinate of rectangle.
730 * top [I] Top coordinate of rectangle.
731 * right [I] Right coordinate of rectangle.
732 * bottom [I] Bottom coordinate of rectangle.
733 * ellipse_width [I] Width of the ellipse at each corner.
734 * ellipse_height [I] Height of the ellipse at each corner.
737 * Success: Handle to region.
741 * If ellipse_width or ellipse_height is less than 2 logical units then
742 * it is treated as though CreateRectRgn() was called instead.
744 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
745 INT right, INT bottom,
746 INT ellipse_width, INT ellipse_height )
751 INT64 asq, bsq, dx, dy, err;
754 /* Make the dimensions sensible */
756 if (left > right) { INT tmp = left; left = right; right = tmp; }
757 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
758 /* the region is for the rectangle interior, but only at right and bottom for some reason */
762 ellipse_width = min( right - left, abs( ellipse_width ));
763 ellipse_height = min( bottom - top, abs( ellipse_height ));
765 /* Check if we can do a normal rectangle instead */
767 if ((ellipse_width < 2) || (ellipse_height < 2))
768 return CreateRectRgn( left, top, right, bottom );
770 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
771 obj->size = ellipse_height;
772 obj->numRects = ellipse_height;
773 obj->extents.left = left;
774 obj->extents.top = top;
775 obj->extents.right = right;
776 obj->extents.bottom = bottom;
778 obj->rects = rects = HeapAlloc( GetProcessHeap(), 0, obj->size * sizeof(RECT) );
779 if (!rects) goto done;
781 /* based on an algorithm by Alois Zingl */
783 a = ellipse_width - 1;
784 b = ellipse_height - 1;
785 asq = (INT64)8 * a * a;
786 bsq = (INT64)8 * b * b;
787 dx = (INT64)4 * b * b * (1 - a);
788 dy = (INT64)4 * a * a * (1 + (b % 2));
789 err = dx + dy + a * a * (b % 2);
792 y = ellipse_height / 2;
794 rects[y].left = left;
795 rects[y].right = right;
797 while (x <= ellipse_width / 2)
809 rects[y].left = left + x;
810 rects[y].right = right - x;
813 for (i = 0; i < ellipse_height / 2; i++)
815 rects[i].left = rects[b - i].left;
816 rects[i].right = rects[b - i].right;
817 rects[i].top = top + i;
818 rects[i].bottom = rects[i].top + 1;
820 for (; i < ellipse_height; i++)
822 rects[i].top = bottom - ellipse_height + i;
823 rects[i].bottom = rects[i].top + 1;
825 rects[ellipse_height / 2].top = top + ellipse_height / 2; /* extend to top of rectangle */
827 hrgn = alloc_gdi_handle( obj, OBJ_REGION, ®ion_funcs );
829 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
830 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
834 HeapFree( GetProcessHeap(), 0, obj->rects );
835 HeapFree( GetProcessHeap(), 0, obj );
841 /***********************************************************************
842 * CreateEllipticRgn (GDI32.@)
844 * Creates an elliptical region.
847 * left [I] Left coordinate of bounding rectangle.
848 * top [I] Top coordinate of bounding rectangle.
849 * right [I] Right coordinate of bounding rectangle.
850 * bottom [I] Bottom coordinate of bounding rectangle.
853 * Success: Handle to region.
857 * This is a special case of CreateRoundRectRgn() where the width of the
858 * ellipse at each corner is equal to the width the rectangle and
859 * the same for the height.
861 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
862 INT right, INT bottom )
864 return CreateRoundRectRgn( left, top, right, bottom,
865 right-left, bottom-top );
869 /***********************************************************************
870 * CreateEllipticRgnIndirect (GDI32.@)
872 * Creates an elliptical region.
875 * rect [I] Pointer to bounding rectangle of the ellipse.
878 * Success: Handle to region.
882 * This is a special case of CreateRoundRectRgn() where the width of the
883 * ellipse at each corner is equal to the width the rectangle and
884 * the same for the height.
886 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
888 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
889 rect->bottom, rect->right - rect->left,
890 rect->bottom - rect->top );
893 /***********************************************************************
894 * GetRegionData (GDI32.@)
896 * Retrieves the data that specifies the region.
899 * hrgn [I] Region to retrieve the region data from.
900 * count [I] The size of the buffer pointed to by rgndata in bytes.
901 * rgndata [I] The buffer to receive data about the region.
904 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
905 * the number of bytes copied to the output buffer.
909 * The format of the Buffer member of RGNDATA is determined by the iType
910 * member of the region data header.
911 * Currently this is always RDH_RECTANGLES, which specifies that the format
912 * is the array of RECT's that specify the region. The length of the array
913 * is specified by the nCount member of the region data header.
915 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
918 WINEREGION *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
920 TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
924 size = obj->numRects * sizeof(RECT);
925 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
927 GDI_ReleaseObj( hrgn );
928 if (rgndata) /* buffer is too small, signal it by return 0 */
930 else /* user requested buffer size with rgndata NULL */
931 return size + sizeof(RGNDATAHEADER);
934 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
935 rgndata->rdh.iType = RDH_RECTANGLES;
936 rgndata->rdh.nCount = obj->numRects;
937 rgndata->rdh.nRgnSize = size;
938 rgndata->rdh.rcBound.left = obj->extents.left;
939 rgndata->rdh.rcBound.top = obj->extents.top;
940 rgndata->rdh.rcBound.right = obj->extents.right;
941 rgndata->rdh.rcBound.bottom = obj->extents.bottom;
943 memcpy( rgndata->Buffer, obj->rects, size );
945 GDI_ReleaseObj( hrgn );
946 return size + sizeof(RGNDATAHEADER);
950 static void translate( POINT *pt, UINT count, const XFORM *xform )
956 pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
957 pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
963 /***********************************************************************
964 * ExtCreateRegion (GDI32.@)
966 * Creates a region as specified by the transformation data and region data.
969 * lpXform [I] World-space to logical-space transformation data.
970 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
971 * rgndata [I] Data that specifies the region.
974 * Success: Handle to region.
978 * See GetRegionData().
980 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
987 SetLastError( ERROR_INVALID_PARAMETER );
991 if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
994 /* XP doesn't care about the type */
995 if( rgndata->rdh.iType != RDH_RECTANGLES )
996 WARN("(Unsupported region data type: %u)\n", rgndata->rdh.iType);
1000 const RECT *pCurRect, *pEndRect;
1002 hrgn = CreateRectRgn( 0, 0, 0, 0 );
1004 pEndRect = (const RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1005 for (pCurRect = (const RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1007 static const INT count = 4;
1011 pt[0].x = pCurRect->left;
1012 pt[0].y = pCurRect->top;
1013 pt[1].x = pCurRect->right;
1014 pt[1].y = pCurRect->top;
1015 pt[2].x = pCurRect->right;
1016 pt[2].y = pCurRect->bottom;
1017 pt[3].x = pCurRect->left;
1018 pt[3].y = pCurRect->bottom;
1020 translate( pt, 4, lpXform );
1021 poly_hrgn = CreatePolyPolygonRgn( pt, &count, 1, WINDING );
1022 CombineRgn( hrgn, hrgn, poly_hrgn, RGN_OR );
1023 DeleteObject( poly_hrgn );
1028 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
1030 if (init_region( obj, rgndata->rdh.nCount ))
1032 const RECT *pCurRect, *pEndRect;
1034 pEndRect = (const RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1035 for(pCurRect = (const RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1037 if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
1039 if (!REGION_UnionRectWithRegion( pCurRect, obj )) goto done;
1042 hrgn = alloc_gdi_handle( obj, OBJ_REGION, ®ion_funcs );
1046 HeapFree( GetProcessHeap(), 0, obj );
1053 HeapFree( GetProcessHeap(), 0, obj->rects );
1054 HeapFree( GetProcessHeap(), 0, obj );
1056 TRACE("%p %d %p returning %p\n", lpXform, dwCount, rgndata, hrgn );
1061 /***********************************************************************
1062 * PtInRegion (GDI32.@)
1064 * Tests whether the specified point is inside a region.
1067 * hrgn [I] Region to test.
1068 * x [I] X-coordinate of point to test.
1069 * y [I] Y-coordinate of point to test.
1072 * Non-zero if the point is inside the region or zero otherwise.
1074 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
1079 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1083 if (obj->numRects > 0 && INRECT(obj->extents, x, y))
1084 for (i = 0; i < obj->numRects; i++)
1085 if (INRECT (obj->rects[i], x, y))
1090 GDI_ReleaseObj( hrgn );
1096 /***********************************************************************
1097 * RectInRegion (GDI32.@)
1099 * Tests if a rectangle is at least partly inside the specified region.
1102 * hrgn [I] Region to test.
1103 * rect [I] Rectangle to test.
1106 * Non-zero if the rectangle is partially inside the region or
1109 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
1115 /* swap the coordinates to make right >= left and bottom >= top */
1116 /* (region building rectangles are normalized the same way) */
1120 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1122 RECT *pCurRect, *pRectEnd;
1124 /* this is (just) a useful optimization */
1125 if ((obj->numRects > 0) && EXTENTCHECK(&obj->extents, &rc))
1127 for (pCurRect = obj->rects, pRectEnd = pCurRect +
1128 obj->numRects; pCurRect < pRectEnd; pCurRect++)
1130 if (pCurRect->bottom <= rc.top)
1131 continue; /* not far enough down yet */
1133 if (pCurRect->top >= rc.bottom)
1134 break; /* too far down */
1136 if (pCurRect->right <= rc.left)
1137 continue; /* not far enough over yet */
1139 if (pCurRect->left >= rc.right) {
1147 GDI_ReleaseObj(hrgn);
1152 /***********************************************************************
1153 * EqualRgn (GDI32.@)
1155 * Tests whether one region is identical to another.
1158 * hrgn1 [I] The first region to compare.
1159 * hrgn2 [I] The second region to compare.
1162 * Non-zero if both regions are identical or zero otherwise.
1164 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1166 WINEREGION *obj1, *obj2;
1169 if ((obj1 = GDI_GetObjPtr( hrgn1, OBJ_REGION )))
1171 if ((obj2 = GDI_GetObjPtr( hrgn2, OBJ_REGION )))
1175 if ( obj1->numRects != obj2->numRects ) goto done;
1176 if ( obj1->numRects == 0 )
1182 if (obj1->extents.left != obj2->extents.left) goto done;
1183 if (obj1->extents.right != obj2->extents.right) goto done;
1184 if (obj1->extents.top != obj2->extents.top) goto done;
1185 if (obj1->extents.bottom != obj2->extents.bottom) goto done;
1186 for( i = 0; i < obj1->numRects; i++ )
1188 if (obj1->rects[i].left != obj2->rects[i].left) goto done;
1189 if (obj1->rects[i].right != obj2->rects[i].right) goto done;
1190 if (obj1->rects[i].top != obj2->rects[i].top) goto done;
1191 if (obj1->rects[i].bottom != obj2->rects[i].bottom) goto done;
1195 GDI_ReleaseObj(hrgn2);
1197 GDI_ReleaseObj(hrgn1);
1202 /***********************************************************************
1203 * REGION_UnionRectWithRegion
1204 * Adds a rectangle to a WINEREGION
1206 static BOOL REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1210 region.rects = ®ion.extents;
1211 region.numRects = 1;
1213 region.extents = *rect;
1214 return REGION_UnionRegion(rgn, rgn, ®ion);
1218 BOOL add_rect_to_region( HRGN rgn, const RECT *rect )
1220 WINEREGION *obj = GDI_GetObjPtr( rgn, OBJ_REGION );
1223 if (!obj) return FALSE;
1224 ret = REGION_UnionRectWithRegion( rect, obj );
1225 GDI_ReleaseObj( rgn );
1229 /***********************************************************************
1230 * REGION_CreateFrameRgn
1232 * Create a region that is a frame around another region.
1233 * Compute the intersection of the region moved in all 4 directions
1234 * ( +x, -x, +y, -y) and subtract from the original.
1235 * The result looks slightly better than in Windows :)
1237 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1241 WINEREGION* destObj = NULL;
1242 WINEREGION *srcObj = GDI_GetObjPtr( hSrc, OBJ_REGION );
1244 tmprgn.rects = NULL;
1245 if (!srcObj) return FALSE;
1246 if (srcObj->numRects != 0)
1248 if (!(destObj = GDI_GetObjPtr( hDest, OBJ_REGION ))) goto done;
1249 if (!init_region( &tmprgn, srcObj->numRects )) goto done;
1251 if (!REGION_OffsetRegion( destObj, srcObj, -x, 0)) goto done;
1252 if (!REGION_OffsetRegion( &tmprgn, srcObj, x, 0)) goto done;
1253 if (!REGION_IntersectRegion( destObj, destObj, &tmprgn )) goto done;
1254 if (!REGION_OffsetRegion( &tmprgn, srcObj, 0, -y)) goto done;
1255 if (!REGION_IntersectRegion( destObj, destObj, &tmprgn )) goto done;
1256 if (!REGION_OffsetRegion( &tmprgn, srcObj, 0, y)) goto done;
1257 if (!REGION_IntersectRegion( destObj, destObj, &tmprgn )) goto done;
1258 if (!REGION_SubtractRegion( destObj, srcObj, destObj )) goto done;
1262 HeapFree( GetProcessHeap(), 0, tmprgn.rects );
1263 if (destObj) GDI_ReleaseObj ( hDest );
1264 GDI_ReleaseObj( hSrc );
1269 /***********************************************************************
1270 * CombineRgn (GDI32.@)
1272 * Combines two regions with the specified operation and stores the result
1273 * in the specified destination region.
1276 * hDest [I] The region that receives the combined result.
1277 * hSrc1 [I] The first source region.
1278 * hSrc2 [I] The second source region.
1279 * mode [I] The way in which the source regions will be combined. See notes.
1283 * NULLREGION - The new region is empty.
1284 * SIMPLEREGION - The new region can be represented by one rectangle.
1285 * COMPLEXREGION - The new region can only be represented by more than
1290 * The two source regions can be the same region.
1291 * The mode can be one of the following:
1292 *| RGN_AND - Intersection of the regions
1293 *| RGN_OR - Union of the regions
1294 *| RGN_XOR - Unions of the regions minus any intersection.
1295 *| RGN_DIFF - Difference (subtraction) of the regions.
1297 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1299 WINEREGION *destObj = GDI_GetObjPtr( hDest, OBJ_REGION );
1302 TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1305 WINEREGION *src1Obj = GDI_GetObjPtr( hSrc1, OBJ_REGION );
1309 TRACE("dump src1Obj:\n");
1310 if(TRACE_ON(region))
1311 REGION_DumpRegion(src1Obj);
1312 if (mode == RGN_COPY)
1314 if (REGION_CopyRegion( destObj, src1Obj ))
1315 result = get_region_type( destObj );
1319 WINEREGION *src2Obj = GDI_GetObjPtr( hSrc2, OBJ_REGION );
1323 TRACE("dump src2Obj:\n");
1324 if(TRACE_ON(region))
1325 REGION_DumpRegion(src2Obj);
1329 if (REGION_IntersectRegion( destObj, src1Obj, src2Obj ))
1330 result = get_region_type( destObj );
1333 if (REGION_UnionRegion( destObj, src1Obj, src2Obj ))
1334 result = get_region_type( destObj );
1337 if (REGION_XorRegion( destObj, src1Obj, src2Obj ))
1338 result = get_region_type( destObj );
1341 if (REGION_SubtractRegion( destObj, src1Obj, src2Obj ))
1342 result = get_region_type( destObj );
1345 GDI_ReleaseObj( hSrc2 );
1348 GDI_ReleaseObj( hSrc1 );
1350 TRACE("dump destObj:\n");
1351 if(TRACE_ON(region))
1352 REGION_DumpRegion(destObj);
1354 GDI_ReleaseObj( hDest );
1359 /***********************************************************************
1361 * Re-calculate the extents of a region
1363 static void REGION_SetExtents (WINEREGION *pReg)
1365 RECT *pRect, *pRectEnd, *pExtents;
1367 if (pReg->numRects == 0)
1369 pReg->extents.left = 0;
1370 pReg->extents.top = 0;
1371 pReg->extents.right = 0;
1372 pReg->extents.bottom = 0;
1376 pExtents = &pReg->extents;
1377 pRect = pReg->rects;
1378 pRectEnd = &pRect[pReg->numRects - 1];
1381 * Since pRect is the first rectangle in the region, it must have the
1382 * smallest top and since pRectEnd is the last rectangle in the region,
1383 * it must have the largest bottom, because of banding. Initialize left and
1384 * right from pRect and pRectEnd, resp., as good things to initialize them
1387 pExtents->left = pRect->left;
1388 pExtents->top = pRect->top;
1389 pExtents->right = pRectEnd->right;
1390 pExtents->bottom = pRectEnd->bottom;
1392 while (pRect <= pRectEnd)
1394 if (pRect->left < pExtents->left)
1395 pExtents->left = pRect->left;
1396 if (pRect->right > pExtents->right)
1397 pExtents->right = pRect->right;
1402 /***********************************************************************
1405 static BOOL REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1407 if (dst != src) /* don't want to copy to itself */
1409 if (dst->size < src->numRects)
1411 RECT *rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects, src->numRects * sizeof(RECT) );
1412 if (!rects) return FALSE;
1414 dst->size = src->numRects;
1416 dst->numRects = src->numRects;
1417 dst->extents.left = src->extents.left;
1418 dst->extents.top = src->extents.top;
1419 dst->extents.right = src->extents.right;
1420 dst->extents.bottom = src->extents.bottom;
1421 memcpy(dst->rects, src->rects, src->numRects * sizeof(RECT));
1426 /***********************************************************************
1427 * REGION_MirrorRegion
1429 static BOOL REGION_MirrorRegion( WINEREGION *dst, WINEREGION *src, int width )
1433 RECT *rects = HeapAlloc( GetProcessHeap(), 0, src->numRects * sizeof(RECT) );
1435 if (!rects) return FALSE;
1437 extents.left = width - src->extents.right;
1438 extents.right = width - src->extents.left;
1439 extents.top = src->extents.top;
1440 extents.bottom = src->extents.bottom;
1442 for (start = 0; start < src->numRects; start = end)
1444 /* find the end of the current band */
1445 for (end = start + 1; end < src->numRects; end++)
1446 if (src->rects[end].top != src->rects[end - 1].top) break;
1448 for (i = 0; i < end - start; i++)
1450 rects[start + i].left = width - src->rects[end - i - 1].right;
1451 rects[start + i].right = width - src->rects[end - i - 1].left;
1452 rects[start + i].top = src->rects[end - i - 1].top;
1453 rects[start + i].bottom = src->rects[end - i - 1].bottom;
1457 HeapFree( GetProcessHeap(), 0, dst->rects );
1459 dst->size = src->numRects;
1460 dst->numRects = src->numRects;
1461 dst->extents = extents;
1465 /***********************************************************************
1468 INT mirror_region( HRGN dst, HRGN src, INT width )
1470 WINEREGION *src_rgn, *dst_rgn;
1473 if (!(src_rgn = GDI_GetObjPtr( src, OBJ_REGION ))) return ERROR;
1474 if ((dst_rgn = GDI_GetObjPtr( dst, OBJ_REGION )))
1476 if (REGION_MirrorRegion( dst_rgn, src_rgn, width )) ret = get_region_type( dst_rgn );
1477 GDI_ReleaseObj( dst_rgn );
1479 GDI_ReleaseObj( src_rgn );
1483 /***********************************************************************
1484 * MirrorRgn (GDI32.@)
1486 BOOL WINAPI MirrorRgn( HWND hwnd, HRGN hrgn )
1488 static const WCHAR user32W[] = {'u','s','e','r','3','2','.','d','l','l',0};
1489 static BOOL (WINAPI *pGetWindowRect)( HWND hwnd, LPRECT rect );
1492 /* yes, a HWND in gdi32, don't ask */
1493 if (!pGetWindowRect)
1495 HMODULE user32 = GetModuleHandleW(user32W);
1496 if (!user32) return FALSE;
1497 if (!(pGetWindowRect = (void *)GetProcAddress( user32, "GetWindowRect" ))) return FALSE;
1499 pGetWindowRect( hwnd, &rect );
1500 return mirror_region( hrgn, hrgn, rect.right - rect.left ) != ERROR;
1504 /***********************************************************************
1507 * Attempt to merge the rects in the current band with those in the
1508 * previous one. Used only by REGION_RegionOp.
1511 * The new index for the previous band.
1514 * If coalescing takes place:
1515 * - rectangles in the previous band will have their bottom fields
1517 * - pReg->numRects will be decreased.
1520 static INT REGION_Coalesce (
1521 WINEREGION *pReg, /* Region to coalesce */
1522 INT prevStart, /* Index of start of previous band */
1523 INT curStart /* Index of start of current band */
1525 RECT *pPrevRect; /* Current rect in previous band */
1526 RECT *pCurRect; /* Current rect in current band */
1527 RECT *pRegEnd; /* End of region */
1528 INT curNumRects; /* Number of rectangles in current band */
1529 INT prevNumRects; /* Number of rectangles in previous band */
1530 INT bandtop; /* top coordinate for current band */
1532 pRegEnd = &pReg->rects[pReg->numRects];
1534 pPrevRect = &pReg->rects[prevStart];
1535 prevNumRects = curStart - prevStart;
1538 * Figure out how many rectangles are in the current band. Have to do
1539 * this because multiple bands could have been added in REGION_RegionOp
1540 * at the end when one region has been exhausted.
1542 pCurRect = &pReg->rects[curStart];
1543 bandtop = pCurRect->top;
1544 for (curNumRects = 0;
1545 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1551 if (pCurRect != pRegEnd)
1554 * If more than one band was added, we have to find the start
1555 * of the last band added so the next coalescing job can start
1556 * at the right place... (given when multiple bands are added,
1557 * this may be pointless -- see above).
1560 while (pRegEnd[-1].top == pRegEnd->top)
1564 curStart = pRegEnd - pReg->rects;
1565 pRegEnd = pReg->rects + pReg->numRects;
1568 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1569 pCurRect -= curNumRects;
1571 * The bands may only be coalesced if the bottom of the previous
1572 * matches the top scanline of the current.
1574 if (pPrevRect->bottom == pCurRect->top)
1577 * Make sure the bands have rects in the same places. This
1578 * assumes that rects have been added in such a way that they
1579 * cover the most area possible. I.e. two rects in a band must
1580 * have some horizontal space between them.
1584 if ((pPrevRect->left != pCurRect->left) ||
1585 (pPrevRect->right != pCurRect->right))
1588 * The bands don't line up so they can't be coalesced.
1595 } while (prevNumRects != 0);
1597 pReg->numRects -= curNumRects;
1598 pCurRect -= curNumRects;
1599 pPrevRect -= curNumRects;
1602 * The bands may be merged, so set the bottom of each rect
1603 * in the previous band to that of the corresponding rect in
1608 pPrevRect->bottom = pCurRect->bottom;
1612 } while (curNumRects != 0);
1615 * If only one band was added to the region, we have to backup
1616 * curStart to the start of the previous band.
1618 * If more than one band was added to the region, copy the
1619 * other bands down. The assumption here is that the other bands
1620 * came from the same region as the current one and no further
1621 * coalescing can be done on them since it's all been done
1622 * already... curStart is already in the right place.
1624 if (pCurRect == pRegEnd)
1626 curStart = prevStart;
1632 *pPrevRect++ = *pCurRect++;
1633 } while (pCurRect != pRegEnd);
1641 /***********************************************************************
1644 * Apply an operation to two regions. Called by REGION_Union,
1645 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1651 * The new region is overwritten.
1654 * The idea behind this function is to view the two regions as sets.
1655 * Together they cover a rectangle of area that this function divides
1656 * into horizontal bands where points are covered only by one region
1657 * or by both. For the first case, the nonOverlapFunc is called with
1658 * each the band and the band's upper and lower extents. For the
1659 * second, the overlapFunc is called to process the entire band. It
1660 * is responsible for clipping the rectangles in the band, though
1661 * this function provides the boundaries.
1662 * At the end of each band, the new region is coalesced, if possible,
1663 * to reduce the number of rectangles in the region.
1666 static BOOL REGION_RegionOp(
1667 WINEREGION *destReg, /* Place to store result */
1668 WINEREGION *reg1, /* First region in operation */
1669 WINEREGION *reg2, /* 2nd region in operation */
1670 BOOL (*overlapFunc)(WINEREGION*, RECT*, RECT*, RECT*, RECT*, INT, INT), /* Function to call for over-lapping bands */
1671 BOOL (*nonOverlap1Func)(WINEREGION*, RECT*, RECT*, INT, INT), /* Function to call for non-overlapping bands in region 1 */
1672 BOOL (*nonOverlap2Func)(WINEREGION*, RECT*, RECT*, INT, INT) /* Function to call for non-overlapping bands in region 2 */
1675 RECT *r1; /* Pointer into first region */
1676 RECT *r2; /* Pointer into 2d region */
1677 RECT *r1End; /* End of 1st region */
1678 RECT *r2End; /* End of 2d region */
1679 INT ybot; /* Bottom of intersection */
1680 INT ytop; /* Top of intersection */
1681 INT prevBand; /* Index of start of
1682 * previous band in newReg */
1683 INT curBand; /* Index of start of current
1685 RECT *r1BandEnd; /* End of current band in r1 */
1686 RECT *r2BandEnd; /* End of current band in r2 */
1687 INT top; /* Top of non-overlapping band */
1688 INT bot; /* Bottom of non-overlapping band */
1692 * set r1, r2, r1End and r2End appropriately, preserve the important
1693 * parts of the destination region until the end in case it's one of
1694 * the two source regions, then mark the "new" region empty, allocating
1695 * another array of rectangles for it to use.
1699 r1End = r1 + reg1->numRects;
1700 r2End = r2 + reg2->numRects;
1703 * Allocate a reasonable number of rectangles for the new region. The idea
1704 * is to allocate enough so the individual functions don't need to
1705 * reallocate and copy the array, which is time consuming, yet we don't
1706 * have to worry about using too much memory. I hope to be able to
1707 * nuke the Xrealloc() at the end of this function eventually.
1709 if (!init_region( &newReg, max(reg1->numRects,reg2->numRects) * 2 )) return FALSE;
1712 * Initialize ybot and ytop.
1713 * In the upcoming loop, ybot and ytop serve different functions depending
1714 * on whether the band being handled is an overlapping or non-overlapping
1716 * In the case of a non-overlapping band (only one of the regions
1717 * has points in the band), ybot is the bottom of the most recent
1718 * intersection and thus clips the top of the rectangles in that band.
1719 * ytop is the top of the next intersection between the two regions and
1720 * serves to clip the bottom of the rectangles in the current band.
1721 * For an overlapping band (where the two regions intersect), ytop clips
1722 * the top of the rectangles of both regions and ybot clips the bottoms.
1724 if (reg1->extents.top < reg2->extents.top)
1725 ybot = reg1->extents.top;
1727 ybot = reg2->extents.top;
1730 * prevBand serves to mark the start of the previous band so rectangles
1731 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1732 * In the beginning, there is no previous band, so prevBand == curBand
1733 * (curBand is set later on, of course, but the first band will always
1734 * start at index 0). prevBand and curBand must be indices because of
1735 * the possible expansion, and resultant moving, of the new region's
1736 * array of rectangles.
1742 curBand = newReg.numRects;
1745 * This algorithm proceeds one source-band (as opposed to a
1746 * destination band, which is determined by where the two regions
1747 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1748 * rectangle after the last one in the current band for their
1749 * respective regions.
1752 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1758 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1764 * First handle the band that doesn't intersect, if any.
1766 * Note that attention is restricted to one band in the
1767 * non-intersecting region at once, so if a region has n
1768 * bands between the current position and the next place it overlaps
1769 * the other, this entire loop will be passed through n times.
1771 if (r1->top < r2->top)
1773 top = max(r1->top,ybot);
1774 bot = min(r1->bottom,r2->top);
1776 if ((top != bot) && (nonOverlap1Func != NULL))
1778 if (!nonOverlap1Func(&newReg, r1, r1BandEnd, top, bot)) return FALSE;
1783 else if (r2->top < r1->top)
1785 top = max(r2->top,ybot);
1786 bot = min(r2->bottom,r1->top);
1788 if ((top != bot) && (nonOverlap2Func != NULL))
1790 if (!nonOverlap2Func(&newReg, r2, r2BandEnd, top, bot)) return FALSE;
1801 * If any rectangles got added to the region, try and coalesce them
1802 * with rectangles from the previous band. Note we could just do
1803 * this test in miCoalesce, but some machines incur a not
1804 * inconsiderable cost for function calls, so...
1806 if (newReg.numRects != curBand)
1808 prevBand = REGION_Coalesce (&newReg, prevBand, curBand);
1812 * Now see if we've hit an intersecting band. The two bands only
1813 * intersect if ybot > ytop
1815 ybot = min(r1->bottom, r2->bottom);
1816 curBand = newReg.numRects;
1819 if (!overlapFunc(&newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot)) return FALSE;
1822 if (newReg.numRects != curBand)
1824 prevBand = REGION_Coalesce (&newReg, prevBand, curBand);
1828 * If we've finished with a band (bottom == ybot) we skip forward
1829 * in the region to the next band.
1831 if (r1->bottom == ybot)
1835 if (r2->bottom == ybot)
1839 } while ((r1 != r1End) && (r2 != r2End));
1842 * Deal with whichever region still has rectangles left.
1844 curBand = newReg.numRects;
1847 if (nonOverlap1Func != NULL)
1852 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1856 if (!nonOverlap1Func(&newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom))
1859 } while (r1 != r1End);
1862 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1867 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1871 if (!nonOverlap2Func(&newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom))
1874 } while (r2 != r2End);
1877 if (newReg.numRects != curBand)
1879 REGION_Coalesce (&newReg, prevBand, curBand);
1883 * A bit of cleanup. To keep regions from growing without bound,
1884 * we shrink the array of rectangles to match the new number of
1885 * rectangles in the region. This never goes to 0, however...
1887 * Only do this stuff if the number of rectangles allocated is more than
1888 * twice the number of rectangles in the region (a simple optimization...).
1890 if ((newReg.numRects < (newReg.size >> 1)) && (newReg.numRects > 2))
1892 RECT *new_rects = HeapReAlloc( GetProcessHeap(), 0, newReg.rects, newReg.numRects * sizeof(RECT) );
1895 newReg.rects = new_rects;
1896 newReg.size = newReg.numRects;
1899 HeapFree( GetProcessHeap(), 0, destReg->rects );
1900 destReg->rects = newReg.rects;
1901 destReg->size = newReg.size;
1902 destReg->numRects = newReg.numRects;
1906 /***********************************************************************
1907 * Region Intersection
1908 ***********************************************************************/
1911 /***********************************************************************
1914 * Handle an overlapping band for REGION_Intersect.
1920 * Rectangles may be added to the region.
1923 static BOOL REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1924 RECT *r2, RECT *r2End, INT top, INT bottom)
1929 while ((r1 != r1End) && (r2 != r2End))
1931 left = max(r1->left, r2->left);
1932 right = min(r1->right, r2->right);
1935 * If there's any overlap between the two rectangles, add that
1936 * overlap to the new region.
1937 * There's no need to check for subsumption because the only way
1938 * such a need could arise is if some region has two rectangles
1939 * right next to each other. Since that should never happen...
1943 if (!add_rect( pReg, left, top, right, bottom )) return FALSE;
1947 * Need to advance the pointers. Shift the one that extends
1948 * to the right the least, since the other still has a chance to
1949 * overlap with that region's next rectangle, if you see what I mean.
1951 if (r1->right < r2->right)
1955 else if (r2->right < r1->right)
1968 /***********************************************************************
1969 * REGION_IntersectRegion
1971 static BOOL REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1974 /* check for trivial reject */
1975 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1976 (!EXTENTCHECK(®1->extents, ®2->extents)))
1977 newReg->numRects = 0;
1979 if (!REGION_RegionOp (newReg, reg1, reg2, REGION_IntersectO, NULL, NULL)) return FALSE;
1982 * Can't alter newReg's extents before we call miRegionOp because
1983 * it might be one of the source regions and miRegionOp depends
1984 * on the extents of those regions being the same. Besides, this
1985 * way there's no checking against rectangles that will be nuked
1986 * due to coalescing, so we have to examine fewer rectangles.
1988 REGION_SetExtents(newReg);
1992 /***********************************************************************
1994 ***********************************************************************/
1996 /***********************************************************************
1999 * Handle a non-overlapping band for the union operation. Just
2000 * Adds the rectangles into the region. Doesn't have to check for
2001 * subsumption or anything.
2007 * pReg->numRects is incremented and the final rectangles overwritten
2008 * with the rectangles we're passed.
2011 static BOOL REGION_UnionNonO(WINEREGION *pReg, RECT *r, RECT *rEnd, INT top, INT bottom)
2015 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE;
2021 /***********************************************************************
2024 * Handle an overlapping band for the union operation. Picks the
2025 * left-most rectangle each time and merges it into the region.
2031 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2035 static BOOL REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2036 RECT *r2, RECT *r2End, INT top, INT bottom)
2038 #define MERGERECT(r) \
2039 if ((pReg->numRects != 0) && \
2040 (pReg->rects[pReg->numRects-1].top == top) && \
2041 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
2042 (pReg->rects[pReg->numRects-1].right >= r->left)) \
2044 if (pReg->rects[pReg->numRects-1].right < r->right) \
2045 pReg->rects[pReg->numRects-1].right = r->right; \
2049 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
2053 while ((r1 != r1End) && (r2 != r2End))
2055 if (r1->left < r2->left)
2070 } while (r1 != r1End);
2072 else while (r2 != r2End)
2080 /***********************************************************************
2081 * REGION_UnionRegion
2083 static BOOL REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1, WINEREGION *reg2)
2087 /* checks all the simple cases */
2090 * Region 1 and 2 are the same or region 1 is empty
2092 if ( (reg1 == reg2) || (!(reg1->numRects)) )
2095 ret = REGION_CopyRegion(newReg, reg2);
2100 * if nothing to union (region 2 empty)
2102 if (!(reg2->numRects))
2105 ret = REGION_CopyRegion(newReg, reg1);
2110 * Region 1 completely subsumes region 2
2112 if ((reg1->numRects == 1) &&
2113 (reg1->extents.left <= reg2->extents.left) &&
2114 (reg1->extents.top <= reg2->extents.top) &&
2115 (reg1->extents.right >= reg2->extents.right) &&
2116 (reg1->extents.bottom >= reg2->extents.bottom))
2119 ret = REGION_CopyRegion(newReg, reg1);
2124 * Region 2 completely subsumes region 1
2126 if ((reg2->numRects == 1) &&
2127 (reg2->extents.left <= reg1->extents.left) &&
2128 (reg2->extents.top <= reg1->extents.top) &&
2129 (reg2->extents.right >= reg1->extents.right) &&
2130 (reg2->extents.bottom >= reg1->extents.bottom))
2133 ret = REGION_CopyRegion(newReg, reg2);
2137 if ((ret = REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO, REGION_UnionNonO, REGION_UnionNonO)))
2139 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2140 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2141 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2142 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2147 /***********************************************************************
2148 * Region Subtraction
2149 ***********************************************************************/
2151 /***********************************************************************
2152 * REGION_SubtractNonO1
2154 * Deal with non-overlapping band for subtraction. Any parts from
2155 * region 2 we discard. Anything from region 1 we add to the region.
2161 * pReg may be affected.
2164 static BOOL REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd, INT top, INT bottom)
2168 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE;
2175 /***********************************************************************
2178 * Overlapping band subtraction. x1 is the left-most point not yet
2185 * pReg may have rectangles added to it.
2188 static BOOL REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2189 RECT *r2, RECT *r2End, INT top, INT bottom)
2191 INT left = r1->left;
2193 while ((r1 != r1End) && (r2 != r2End))
2195 if (r2->right <= left)
2198 * Subtrahend missed the boat: go to next subtrahend.
2202 else if (r2->left <= left)
2205 * Subtrahend precedes minuend: nuke left edge of minuend.
2208 if (left >= r1->right)
2211 * Minuend completely covered: advance to next minuend and
2212 * reset left fence to edge of new minuend.
2221 * Subtrahend now used up since it doesn't extend beyond
2227 else if (r2->left < r1->right)
2230 * Left part of subtrahend covers part of minuend: add uncovered
2231 * part of minuend to region and skip to next subtrahend.
2233 if (!add_rect( pReg, left, top, r2->left, bottom )) return FALSE;
2235 if (left >= r1->right)
2238 * Minuend used up: advance to new...
2247 * Subtrahend used up
2255 * Minuend used up: add any remaining piece before advancing.
2257 if (r1->right > left)
2259 if (!add_rect( pReg, left, top, r1->right, bottom )) return FALSE;
2268 * Add remaining minuend rectangles to region.
2272 if (!add_rect( pReg, left, top, r1->right, bottom )) return FALSE;
2282 /***********************************************************************
2283 * REGION_SubtractRegion
2285 * Subtract regS from regM and leave the result in regD.
2286 * S stands for subtrahend, M for minuend and D for difference.
2292 * regD is overwritten.
2295 static BOOL REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM, WINEREGION *regS )
2297 /* check for trivial reject */
2298 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2299 (!EXTENTCHECK(®M->extents, ®S->extents)) )
2300 return REGION_CopyRegion(regD, regM);
2302 if (!REGION_RegionOp (regD, regM, regS, REGION_SubtractO, REGION_SubtractNonO1, NULL))
2306 * Can't alter newReg's extents before we call miRegionOp because
2307 * it might be one of the source regions and miRegionOp depends
2308 * on the extents of those regions being the unaltered. Besides, this
2309 * way there's no checking against rectangles that will be nuked
2310 * due to coalescing, so we have to examine fewer rectangles.
2312 REGION_SetExtents (regD);
2316 /***********************************************************************
2319 static BOOL REGION_XorRegion(WINEREGION *dr, WINEREGION *sra, WINEREGION *srb)
2321 WINEREGION tra, trb;
2324 if (!init_region( &tra, sra->numRects + 1 )) return FALSE;
2325 if ((ret = init_region( &trb, srb->numRects + 1 )))
2327 ret = REGION_SubtractRegion(&tra,sra,srb) &&
2328 REGION_SubtractRegion(&trb,srb,sra) &&
2329 REGION_UnionRegion(dr,&tra,&trb);
2330 destroy_region(&trb);
2332 destroy_region(&tra);
2336 /**************************************************************************
2340 *************************************************************************/
2342 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2343 #define SMALL_COORDINATE 0x80000000
2345 /***********************************************************************
2346 * REGION_InsertEdgeInET
2348 * Insert the given edge into the edge table.
2349 * First we must find the correct bucket in the
2350 * Edge table, then find the right slot in the
2351 * bucket. Finally, we can insert it.
2354 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2355 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2358 EdgeTableEntry *start, *prev;
2359 ScanLineList *pSLL, *pPrevSLL;
2360 ScanLineListBlock *tmpSLLBlock;
2363 * find the right bucket to put the edge into
2365 pPrevSLL = &ET->scanlines;
2366 pSLL = pPrevSLL->next;
2367 while (pSLL && (pSLL->scanline < scanline))
2374 * reassign pSLL (pointer to ScanLineList) if necessary
2376 if ((!pSLL) || (pSLL->scanline > scanline))
2378 if (*iSLLBlock > SLLSPERBLOCK-1)
2380 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2383 WARN("Can't alloc SLLB\n");
2386 (*SLLBlock)->next = tmpSLLBlock;
2387 tmpSLLBlock->next = NULL;
2388 *SLLBlock = tmpSLLBlock;
2391 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2393 pSLL->next = pPrevSLL->next;
2394 pSLL->edgelist = NULL;
2395 pPrevSLL->next = pSLL;
2397 pSLL->scanline = scanline;
2400 * now insert the edge in the right bucket
2403 start = pSLL->edgelist;
2404 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2407 start = start->next;
2414 pSLL->edgelist = ETE;
2417 /***********************************************************************
2418 * REGION_CreateEdgeTable
2420 * This routine creates the edge table for
2421 * scan converting polygons.
2422 * The Edge Table (ET) looks like:
2426 * | ymax | ScanLineLists
2427 * |scanline|-->------------>-------------->...
2428 * -------- |scanline| |scanline|
2429 * |edgelist| |edgelist|
2430 * --------- ---------
2434 * list of ETEs list of ETEs
2436 * where ETE is an EdgeTableEntry data structure,
2437 * and there is one ScanLineList per scanline at
2438 * which an edge is initially entered.
2441 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2442 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2443 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2445 const POINT *top, *bottom;
2446 const POINT *PrevPt, *CurrPt, *EndPt;
2453 * initialize the Active Edge Table
2457 AET->nextWETE = NULL;
2458 AET->bres.minor_axis = SMALL_COORDINATE;
2461 * initialize the Edge Table.
2463 ET->scanlines.next = NULL;
2464 ET->ymax = SMALL_COORDINATE;
2465 ET->ymin = LARGE_COORDINATE;
2466 pSLLBlock->next = NULL;
2469 for(poly = 0; poly < nbpolygons; poly++)
2471 count = Count[poly];
2479 * for each vertex in the array of points.
2480 * In this loop we are dealing with two vertices at
2481 * a time -- these make up one edge of the polygon.
2488 * find out which point is above and which is below.
2490 if (PrevPt->y > CurrPt->y)
2492 bottom = PrevPt, top = CurrPt;
2493 pETEs->ClockWise = 0;
2497 bottom = CurrPt, top = PrevPt;
2498 pETEs->ClockWise = 1;
2502 * don't add horizontal edges to the Edge table.
2504 if (bottom->y != top->y)
2506 pETEs->ymax = bottom->y-1;
2507 /* -1 so we don't get last scanline */
2510 * initialize integer edge algorithm
2512 dy = bottom->y - top->y;
2513 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2515 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2518 if (PrevPt->y > ET->ymax)
2519 ET->ymax = PrevPt->y;
2520 if (PrevPt->y < ET->ymin)
2521 ET->ymin = PrevPt->y;
2530 /***********************************************************************
2533 * This routine moves EdgeTableEntries from the
2534 * EdgeTable into the Active Edge Table,
2535 * leaving them sorted by smaller x coordinate.
2538 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2540 EdgeTableEntry *pPrevAET;
2541 EdgeTableEntry *tmp;
2547 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2556 ETEs->back = pPrevAET;
2557 pPrevAET->next = ETEs;
2564 /***********************************************************************
2565 * REGION_computeWAET
2567 * This routine links the AET by the
2568 * nextWETE (winding EdgeTableEntry) link for
2569 * use by the winding number rule. The final
2570 * Active Edge Table (AET) might look something
2574 * ---------- --------- ---------
2575 * |ymax | |ymax | |ymax |
2576 * | ... | |... | |... |
2577 * |next |->|next |->|next |->...
2578 * |nextWETE| |nextWETE| |nextWETE|
2579 * --------- --------- ^--------
2581 * V-------------------> V---> ...
2584 static void REGION_computeWAET(EdgeTableEntry *AET)
2586 EdgeTableEntry *pWETE;
2590 AET->nextWETE = NULL;
2600 if ((!inside && !isInside) ||
2601 ( inside && isInside))
2603 pWETE->nextWETE = AET;
2609 pWETE->nextWETE = NULL;
2612 /***********************************************************************
2613 * REGION_InsertionSort
2615 * Just a simple insertion sort using
2616 * pointers and back pointers to sort the Active
2620 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2622 EdgeTableEntry *pETEchase;
2623 EdgeTableEntry *pETEinsert;
2624 EdgeTableEntry *pETEchaseBackTMP;
2625 BOOL changed = FALSE;
2632 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2633 pETEchase = pETEchase->back;
2636 if (pETEchase != pETEinsert)
2638 pETEchaseBackTMP = pETEchase->back;
2639 pETEinsert->back->next = AET;
2641 AET->back = pETEinsert->back;
2642 pETEinsert->next = pETEchase;
2643 pETEchase->back->next = pETEinsert;
2644 pETEchase->back = pETEinsert;
2645 pETEinsert->back = pETEchaseBackTMP;
2652 /***********************************************************************
2653 * REGION_FreeStorage
2657 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2659 ScanLineListBlock *tmpSLLBlock;
2663 tmpSLLBlock = pSLLBlock->next;
2664 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2665 pSLLBlock = tmpSLLBlock;
2670 /***********************************************************************
2671 * REGION_PtsToRegion
2673 * Create an array of rectangles from a list of points.
2675 static BOOL REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2676 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2680 POINTBLOCK *CurPtBlock;
2685 extents = ®->extents;
2687 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2688 if (!init_region( reg, numRects )) return FALSE;
2690 reg->size = numRects;
2691 CurPtBlock = FirstPtBlock;
2692 rects = reg->rects - 1;
2694 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2696 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2697 /* the loop uses 2 points per iteration */
2698 i = NUMPTSTOBUFFER >> 1;
2699 if (!numFullPtBlocks)
2700 i = iCurPtBlock >> 1;
2701 for (pts = CurPtBlock->pts; i--; pts += 2) {
2702 if (pts->x == pts[1].x)
2704 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2705 pts[1].x == rects->right &&
2706 (numRects == 1 || rects[-1].top != rects->top) &&
2707 (i && pts[2].y > pts[1].y)) {
2708 rects->bottom = pts[1].y + 1;
2713 rects->left = pts->x; rects->top = pts->y;
2714 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2715 if (rects->left < extents->left)
2716 extents->left = rects->left;
2717 if (rects->right > extents->right)
2718 extents->right = rects->right;
2720 CurPtBlock = CurPtBlock->next;
2724 extents->top = reg->rects->top;
2725 extents->bottom = rects->bottom;
2730 extents->bottom = 0;
2732 reg->numRects = numRects;
2737 /***********************************************************************
2738 * CreatePolyPolygonRgn (GDI32.@)
2740 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2741 INT nbpolygons, INT mode)
2745 EdgeTableEntry *pAET; /* Active Edge Table */
2746 INT y; /* current scanline */
2747 int iPts = 0; /* number of pts in buffer */
2748 EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2749 ScanLineList *pSLL; /* current scanLineList */
2750 POINT *pts; /* output buffer */
2751 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2752 EdgeTable ET; /* header node for ET */
2753 EdgeTableEntry AET; /* header node for AET */
2754 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2755 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2756 int fixWAET = FALSE;
2757 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2758 POINTBLOCK *tmpPtBlock;
2759 int numFullPtBlocks = 0;
2762 TRACE("%p, count %d, polygons %d, mode %d\n", Pts, *Count, nbpolygons, mode);
2764 /* special case a rectangle */
2766 if (((nbpolygons == 1) && ((*Count == 4) ||
2767 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2768 (((Pts[0].y == Pts[1].y) &&
2769 (Pts[1].x == Pts[2].x) &&
2770 (Pts[2].y == Pts[3].y) &&
2771 (Pts[3].x == Pts[0].x)) ||
2772 ((Pts[0].x == Pts[1].x) &&
2773 (Pts[1].y == Pts[2].y) &&
2774 (Pts[2].x == Pts[3].x) &&
2775 (Pts[3].y == Pts[0].y))))
2776 return CreateRectRgn( min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2777 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2779 for(poly = total = 0; poly < nbpolygons; poly++)
2780 total += Count[poly];
2781 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2784 pts = FirstPtBlock.pts;
2785 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2786 pSLL = ET.scanlines.next;
2787 curPtBlock = &FirstPtBlock;
2789 if (mode != WINDING) {
2793 for (y = ET.ymin; y < ET.ymax; y++) {
2795 * Add a new edge to the active edge table when we
2796 * get to the next edge.
2798 if (pSLL != NULL && y == pSLL->scanline) {
2799 REGION_loadAET(&AET, pSLL->edgelist);
2806 * for each active edge
2809 pts->x = pAET->bres.minor_axis, pts->y = y;
2813 * send out the buffer
2815 if (iPts == NUMPTSTOBUFFER) {
2816 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2817 if(!tmpPtBlock) goto done;
2818 curPtBlock->next = tmpPtBlock;
2819 curPtBlock = tmpPtBlock;
2820 pts = curPtBlock->pts;
2824 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2826 REGION_InsertionSort(&AET);
2833 for (y = ET.ymin; y < ET.ymax; y++) {
2835 * Add a new edge to the active edge table when we
2836 * get to the next edge.
2838 if (pSLL != NULL && y == pSLL->scanline) {
2839 REGION_loadAET(&AET, pSLL->edgelist);
2840 REGION_computeWAET(&AET);
2848 * for each active edge
2852 * add to the buffer only those edges that
2853 * are in the Winding active edge table.
2855 if (pWETE == pAET) {
2856 pts->x = pAET->bres.minor_axis, pts->y = y;
2860 * send out the buffer
2862 if (iPts == NUMPTSTOBUFFER) {
2863 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2864 sizeof(POINTBLOCK) );
2865 if(!tmpPtBlock) goto done;
2866 curPtBlock->next = tmpPtBlock;
2867 curPtBlock = tmpPtBlock;
2868 pts = curPtBlock->pts;
2872 pWETE = pWETE->nextWETE;
2874 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2878 * recompute the winding active edge table if
2879 * we just resorted or have exited an edge.
2881 if (REGION_InsertionSort(&AET) || fixWAET) {
2882 REGION_computeWAET(&AET);
2888 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) goto done;
2890 if (!REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, obj))
2892 HeapFree( GetProcessHeap(), 0, obj );
2895 if (!(hrgn = alloc_gdi_handle( obj, OBJ_REGION, ®ion_funcs )))
2897 HeapFree( GetProcessHeap(), 0, obj->rects );
2898 HeapFree( GetProcessHeap(), 0, obj );
2902 REGION_FreeStorage(SLLBlock.next);
2903 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2904 tmpPtBlock = curPtBlock->next;
2905 HeapFree( GetProcessHeap(), 0, curPtBlock );
2906 curPtBlock = tmpPtBlock;
2908 HeapFree( GetProcessHeap(), 0, pETEs );
2913 /***********************************************************************
2914 * CreatePolygonRgn (GDI32.@)
2916 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2919 return CreatePolyPolygonRgn( points, &count, 1, mode );