2 * GDI region objects. Shamelessly ripped out from the X11 distribution
3 * Thanks for the nice licence.
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);
115 /* GDI logical region object */
123 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc );
124 static BOOL REGION_DeleteObject( HGDIOBJ handle );
126 static const struct gdi_obj_funcs region_funcs =
128 REGION_SelectObject, /* pSelectObject */
129 NULL, /* pGetObjectA */
130 NULL, /* pGetObjectW */
131 NULL, /* pUnrealizeObject */
132 REGION_DeleteObject /* pDeleteObject */
135 /* 1 if two RECTs overlap.
136 * 0 if two RECTs do not overlap.
138 #define EXTENTCHECK(r1, r2) \
139 ((r1)->right > (r2)->left && \
140 (r1)->left < (r2)->right && \
141 (r1)->bottom > (r2)->top && \
142 (r1)->top < (r2)->bottom)
145 * Check to see if there is enough memory in the present region.
148 static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
149 if (reg->numRects >= (reg->size - 1)) {
150 *firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
154 *rect = (*firstrect)+reg->numRects;
159 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
161 #define EMPTY_REGION(pReg) { \
162 (pReg)->numRects = 0; \
163 (pReg)->extents.left = (pReg)->extents.top = 0; \
164 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
167 #define REGION_NOT_EMPTY(pReg) pReg->numRects
169 #define INRECT(r, x, y) \
170 ( ( ((r).right > x)) && \
171 ( ((r).left <= x)) && \
172 ( ((r).bottom > y)) && \
177 * number of points to buffer before sending them off
178 * to scanlines() : Must be an even number
180 #define NUMPTSTOBUFFER 200
183 * used to allocate buffers for points and link
184 * the buffers together
187 typedef struct _POINTBLOCK {
188 POINT pts[NUMPTSTOBUFFER];
189 struct _POINTBLOCK *next;
195 * This file contains a few macros to help track
196 * the edge of a filled object. The object is assumed
197 * to be filled in scanline order, and thus the
198 * algorithm used is an extension of Bresenham's line
199 * drawing algorithm which assumes that y is always the
201 * Since these pieces of code are the same for any filled shape,
202 * it is more convenient to gather the library in one
203 * place, but since these pieces of code are also in
204 * the inner loops of output primitives, procedure call
205 * overhead is out of the question.
206 * See the author for a derivation if needed.
211 * In scan converting polygons, we want to choose those pixels
212 * which are inside the polygon. Thus, we add .5 to the starting
213 * x coordinate for both left and right edges. Now we choose the
214 * first pixel which is inside the pgon for the left edge and the
215 * first pixel which is outside the pgon for the right edge.
216 * Draw the left pixel, but not the right.
218 * How to add .5 to the starting x coordinate:
219 * If the edge is moving to the right, then subtract dy from the
220 * error term from the general form of the algorithm.
221 * If the edge is moving to the left, then add dy to the error term.
223 * The reason for the difference between edges moving to the left
224 * and edges moving to the right is simple: If an edge is moving
225 * to the right, then we want the algorithm to flip immediately.
226 * If it is moving to the left, then we don't want it to flip until
227 * we traverse an entire pixel.
229 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
230 int dx; /* local storage */ \
233 * if the edge is horizontal, then it is ignored \
234 * and assumed not to be processed. Otherwise, do this stuff. \
238 dx = (x2) - xStart; \
242 incr1 = -2 * dx + 2 * (dy) * m1; \
243 incr2 = -2 * dx + 2 * (dy) * m; \
244 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
248 incr1 = 2 * dx - 2 * (dy) * m1; \
249 incr2 = 2 * dx - 2 * (dy) * m; \
250 d = -2 * m * (dy) + 2 * dx; \
255 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
278 * This structure contains all of the information needed
279 * to run the bresenham algorithm.
280 * The variables may be hardcoded into the declarations
281 * instead of using this structure to make use of
282 * register declarations.
285 INT minor_axis; /* minor axis */
286 INT d; /* decision variable */
287 INT m, m1; /* slope and slope+1 */
288 INT incr1, incr2; /* error increments */
292 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
293 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
294 bres.m, bres.m1, bres.incr1, bres.incr2)
296 #define BRESINCRPGONSTRUCT(bres) \
297 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
302 * These are the data structures needed to scan
303 * convert regions. Two different scan conversion
304 * methods are available -- the even-odd method, and
305 * the winding number method.
306 * The even-odd rule states that a point is inside
307 * the polygon if a ray drawn from that point in any
308 * direction will pass through an odd number of
310 * By the winding number rule, a point is decided
311 * to be inside the polygon if a ray drawn from that
312 * point in any direction passes through a different
313 * number of clockwise and counter-clockwise path
316 * These data structures are adapted somewhat from
317 * the algorithm in (Foley/Van Dam) for scan converting
319 * The basic algorithm is to start at the top (smallest y)
320 * of the polygon, stepping down to the bottom of
321 * the polygon by incrementing the y coordinate. We
322 * keep a list of edges which the current scanline crosses,
323 * sorted by x. This list is called the Active Edge Table (AET)
324 * As we change the y-coordinate, we update each entry in
325 * in the active edge table to reflect the edges new xcoord.
326 * This list must be sorted at each scanline in case
327 * two edges intersect.
328 * We also keep a data structure known as the Edge Table (ET),
329 * which keeps track of all the edges which the current
330 * scanline has not yet reached. The ET is basically a
331 * list of ScanLineList structures containing a list of
332 * edges which are entered at a given scanline. There is one
333 * ScanLineList per scanline at which an edge is entered.
334 * When we enter a new edge, we move it from the ET to the AET.
336 * From the AET, we can implement the even-odd rule as in
338 * The winding number rule is a little trickier. We also
339 * keep the EdgeTableEntries in the AET linked by the
340 * nextWETE (winding EdgeTableEntry) link. This allows
341 * the edges to be linked just as before for updating
342 * purposes, but only uses the edges linked by the nextWETE
343 * link as edges representing spans of the polygon to
344 * drawn (as with the even-odd rule).
348 * for the winding number rule
351 #define COUNTERCLOCKWISE -1
353 typedef struct _EdgeTableEntry {
354 INT ymax; /* ycoord at which we exit this edge. */
355 BRESINFO bres; /* Bresenham info to run the edge */
356 struct _EdgeTableEntry *next; /* next in the list */
357 struct _EdgeTableEntry *back; /* for insertion sort */
358 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
359 int ClockWise; /* flag for winding number rule */
363 typedef struct _ScanLineList{
364 INT scanline; /* the scanline represented */
365 EdgeTableEntry *edgelist; /* header node */
366 struct _ScanLineList *next; /* next in the list */
371 INT ymax; /* ymax for the polygon */
372 INT ymin; /* ymin for the polygon */
373 ScanLineList scanlines; /* header node */
378 * Here is a struct to help with storage allocation
379 * so we can allocate a big chunk at a time, and then take
380 * pieces from this heap when we need to.
382 #define SLLSPERBLOCK 25
384 typedef struct _ScanLineListBlock {
385 ScanLineList SLLs[SLLSPERBLOCK];
386 struct _ScanLineListBlock *next;
392 * a few macros for the inner loops of the fill code where
393 * performance considerations don't allow a procedure call.
395 * Evaluate the given edge at the given scanline.
396 * If the edge has expired, then we leave it and fix up
397 * the active edge table; otherwise, we increment the
398 * x value to be ready for the next scanline.
399 * The winding number rule is in effect, so we must notify
400 * the caller when the edge has been removed so he
401 * can reorder the Winding Active Edge Table.
403 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
404 if (pAET->ymax == y) { /* leaving this edge */ \
405 pPrevAET->next = pAET->next; \
406 pAET = pPrevAET->next; \
409 pAET->back = pPrevAET; \
412 BRESINCRPGONSTRUCT(pAET->bres); \
420 * Evaluate the given edge at the given scanline.
421 * If the edge has expired, then we leave it and fix up
422 * the active edge table; otherwise, we increment the
423 * x value to be ready for the next scanline.
424 * The even-odd rule is in effect.
426 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
427 if (pAET->ymax == y) { /* leaving this edge */ \
428 pPrevAET->next = pAET->next; \
429 pAET = pPrevAET->next; \
431 pAET->back = pPrevAET; \
434 BRESINCRPGONSTRUCT(pAET->bres); \
440 /* Note the parameter order is different from the X11 equivalents */
442 static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
443 static void REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
444 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
445 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
446 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
447 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
450 #define RGN_DEFAULT_RECTS 2
453 /***********************************************************************
456 static inline INT get_region_type( const RGNOBJ *obj )
458 switch(obj->rgn.numRects)
460 case 0: return NULLREGION;
461 case 1: return SIMPLEREGION;
462 default: return COMPLEXREGION;
467 /***********************************************************************
469 * Outputs the contents of a WINEREGION
471 static void REGION_DumpRegion(WINEREGION *pReg)
473 RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
475 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg,
476 pReg->extents.left, pReg->extents.top,
477 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
478 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
479 TRACE("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
480 pRect->right, pRect->bottom);
485 /***********************************************************************
488 * Initialize a new empty region.
490 static BOOL init_region( WINEREGION *pReg, INT n )
492 if (!(pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT )))) return FALSE;
499 /***********************************************************************
500 * REGION_CreateRegion
501 * Create a new empty region.
503 static HRGN REGION_CreateRegion( INT n )
508 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
509 if (!init_region( &obj->rgn, n ))
511 HeapFree( GetProcessHeap(), 0, obj );
514 if (!(hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, ®ion_funcs )))
516 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
517 HeapFree( GetProcessHeap(), 0, obj );
522 /***********************************************************************
525 static void destroy_region( WINEREGION *pReg )
527 HeapFree( GetProcessHeap(), 0, pReg->rects );
530 /***********************************************************************
531 * REGION_DeleteObject
533 static BOOL REGION_DeleteObject( HGDIOBJ handle )
535 RGNOBJ *rgn = free_gdi_handle( handle );
537 if (!rgn) return FALSE;
538 HeapFree( GetProcessHeap(), 0, rgn->rgn.rects );
539 HeapFree( GetProcessHeap(), 0, rgn );
543 /***********************************************************************
544 * REGION_SelectObject
546 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
548 return ULongToHandle(SelectClipRgn( hdc, handle ));
552 /***********************************************************************
553 * REGION_OffsetRegion
554 * Offset a WINEREGION by x,y
556 static void REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn,
560 REGION_CopyRegion( rgn, srcrgn);
562 int nbox = rgn->numRects;
563 RECT *pbox = rgn->rects;
573 rgn->extents.left += x;
574 rgn->extents.right += x;
575 rgn->extents.top += y;
576 rgn->extents.bottom += y;
581 /***********************************************************************
582 * OffsetRgn (GDI32.@)
584 * Moves a region by the specified X- and Y-axis offsets.
587 * hrgn [I] Region to offset.
588 * x [I] Offset right if positive or left if negative.
589 * y [I] Offset down if positive or up if negative.
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
599 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
601 RGNOBJ * obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
604 TRACE("%p %d,%d\n", hrgn, x, y);
609 REGION_OffsetRegion( &obj->rgn, &obj->rgn, x, y);
611 ret = get_region_type( obj );
612 GDI_ReleaseObj( hrgn );
617 /***********************************************************************
618 * GetRgnBox (GDI32.@)
620 * Retrieves the bounding rectangle of the region. The bounding rectangle
621 * is the smallest rectangle that contains the entire region.
624 * hrgn [I] Region to retrieve bounding rectangle from.
625 * rect [O] Rectangle that will receive the coordinates of the bounding
629 * NULLREGION - The new region is empty.
630 * SIMPLEREGION - The new region can be represented by one rectangle.
631 * COMPLEXREGION - The new region can only be represented by more than
634 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
636 RGNOBJ * obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
640 rect->left = obj->rgn.extents.left;
641 rect->top = obj->rgn.extents.top;
642 rect->right = obj->rgn.extents.right;
643 rect->bottom = obj->rgn.extents.bottom;
644 TRACE("%p (%d,%d-%d,%d)\n", hrgn,
645 rect->left, rect->top, rect->right, rect->bottom);
646 ret = get_region_type( obj );
647 GDI_ReleaseObj(hrgn);
654 /***********************************************************************
655 * CreateRectRgn (GDI32.@)
657 * Creates a simple rectangular region.
660 * left [I] Left coordinate of rectangle.
661 * top [I] Top coordinate of rectangle.
662 * right [I] Right coordinate of rectangle.
663 * bottom [I] Bottom coordinate of rectangle.
666 * Success: Handle to region.
669 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
673 /* Allocate 2 rects by default to reduce the number of reallocs */
675 if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
677 TRACE("%d,%d-%d,%d\n", left, top, right, bottom);
678 SetRectRgn(hrgn, left, top, right, bottom);
683 /***********************************************************************
684 * CreateRectRgnIndirect (GDI32.@)
686 * Creates a simple rectangular region.
689 * rect [I] Coordinates of rectangular region.
692 * Success: Handle to region.
695 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
697 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
701 /***********************************************************************
702 * SetRectRgn (GDI32.@)
704 * Sets a region to a simple rectangular region.
707 * hrgn [I] Region to convert.
708 * left [I] Left coordinate of rectangle.
709 * top [I] Top coordinate of rectangle.
710 * right [I] Right coordinate of rectangle.
711 * bottom [I] Bottom coordinate of rectangle.
718 * Allows either or both left and top to be greater than right or bottom.
720 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
721 INT right, INT bottom )
725 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
727 if (!(obj = GDI_GetObjPtr( hrgn, OBJ_REGION ))) return FALSE;
729 if (left > right) { INT tmp = left; left = right; right = tmp; }
730 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
732 if((left != right) && (top != bottom))
734 obj->rgn.rects->left = obj->rgn.extents.left = left;
735 obj->rgn.rects->top = obj->rgn.extents.top = top;
736 obj->rgn.rects->right = obj->rgn.extents.right = right;
737 obj->rgn.rects->bottom = obj->rgn.extents.bottom = bottom;
738 obj->rgn.numRects = 1;
741 EMPTY_REGION(&obj->rgn);
743 GDI_ReleaseObj( hrgn );
748 /***********************************************************************
749 * CreateRoundRectRgn (GDI32.@)
751 * Creates a rectangular region with rounded corners.
754 * left [I] Left coordinate of rectangle.
755 * top [I] Top coordinate of rectangle.
756 * right [I] Right coordinate of rectangle.
757 * bottom [I] Bottom coordinate of rectangle.
758 * ellipse_width [I] Width of the ellipse at each corner.
759 * ellipse_height [I] Height of the ellipse at each corner.
762 * Success: Handle to region.
766 * If ellipse_width or ellipse_height is less than 2 logical units then
767 * it is treated as though CreateRectRgn() was called instead.
769 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
770 INT right, INT bottom,
771 INT ellipse_width, INT ellipse_height )
775 int asq, bsq, d, xd, yd;
778 /* Make the dimensions sensible */
780 if (left > right) { INT tmp = left; left = right; right = tmp; }
781 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
783 ellipse_width = abs(ellipse_width);
784 ellipse_height = abs(ellipse_height);
786 /* Check parameters */
788 if (ellipse_width > right-left) ellipse_width = right-left;
789 if (ellipse_height > bottom-top) ellipse_height = bottom-top;
791 /* Check if we can do a normal rectangle instead */
793 if ((ellipse_width < 2) || (ellipse_height < 2))
794 return CreateRectRgn( left, top, right, bottom );
798 d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
799 if (!(hrgn = REGION_CreateRegion(d))) return 0;
800 if (!(obj = GDI_GetObjPtr( hrgn, OBJ_REGION ))) return 0;
801 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
802 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
804 /* Ellipse algorithm, based on an article by K. Porter */
805 /* in DDJ Graphics Programming Column, 8/89 */
807 asq = ellipse_width * ellipse_width / 4; /* a^2 */
808 bsq = ellipse_height * ellipse_height / 4; /* b^2 */
809 d = bsq - asq * ellipse_height / 2 + asq / 4; /* b^2 - a^2b + a^2/4 */
811 yd = asq * ellipse_height; /* 2a^2b */
813 rect.left = left + ellipse_width / 2;
814 rect.right = right - ellipse_width / 2;
816 /* Loop to draw first half of quadrant */
820 if (d > 0) /* if nearest pixel is toward the center */
822 /* move toward center */
824 rect.bottom = rect.top + 1;
825 REGION_UnionRectWithRegion( &rect, &obj->rgn );
827 rect.bottom = rect.top + 1;
828 REGION_UnionRectWithRegion( &rect, &obj->rgn );
832 rect.left--; /* next horiz point */
838 /* Loop to draw second half of quadrant */
840 d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
843 /* next vertical point */
845 rect.bottom = rect.top + 1;
846 REGION_UnionRectWithRegion( &rect, &obj->rgn );
848 rect.bottom = rect.top + 1;
849 REGION_UnionRectWithRegion( &rect, &obj->rgn );
850 if (d < 0) /* if nearest pixel is outside ellipse */
852 rect.left--; /* move away from center */
861 /* Add the inside rectangle */
866 rect.bottom = bottom;
867 REGION_UnionRectWithRegion( &rect, &obj->rgn );
869 GDI_ReleaseObj( hrgn );
874 /***********************************************************************
875 * CreateEllipticRgn (GDI32.@)
877 * Creates an elliptical region.
880 * left [I] Left coordinate of bounding rectangle.
881 * top [I] Top coordinate of bounding rectangle.
882 * right [I] Right coordinate of bounding rectangle.
883 * bottom [I] Bottom coordinate of bounding rectangle.
886 * Success: Handle to region.
890 * This is a special case of CreateRoundRectRgn() where the width of the
891 * ellipse at each corner is equal to the width the rectangle and
892 * the same for the height.
894 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
895 INT right, INT bottom )
897 return CreateRoundRectRgn( left, top, right, bottom,
898 right-left, bottom-top );
902 /***********************************************************************
903 * CreateEllipticRgnIndirect (GDI32.@)
905 * Creates an elliptical region.
908 * rect [I] Pointer to bounding rectangle of the ellipse.
911 * Success: Handle to region.
915 * This is a special case of CreateRoundRectRgn() where the width of the
916 * ellipse at each corner is equal to the width the rectangle and
917 * the same for the height.
919 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
921 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
922 rect->bottom, rect->right - rect->left,
923 rect->bottom - rect->top );
926 /***********************************************************************
927 * GetRegionData (GDI32.@)
929 * Retrieves the data that specifies the region.
932 * hrgn [I] Region to retrieve the region data from.
933 * count [I] The size of the buffer pointed to by rgndata in bytes.
934 * rgndata [I] The buffer to receive data about the region.
937 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
938 * the number of bytes copied to the output buffer.
942 * The format of the Buffer member of RGNDATA is determined by the iType
943 * member of the region data header.
944 * Currently this is always RDH_RECTANGLES, which specifies that the format
945 * is the array of RECT's that specify the region. The length of the array
946 * is specified by the nCount member of the region data header.
948 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
951 RGNOBJ *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
953 TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
957 size = obj->rgn.numRects * sizeof(RECT);
958 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
960 GDI_ReleaseObj( hrgn );
961 if (rgndata) /* buffer is too small, signal it by return 0 */
963 else /* user requested buffer size with rgndata NULL */
964 return size + sizeof(RGNDATAHEADER);
967 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
968 rgndata->rdh.iType = RDH_RECTANGLES;
969 rgndata->rdh.nCount = obj->rgn.numRects;
970 rgndata->rdh.nRgnSize = size;
971 rgndata->rdh.rcBound.left = obj->rgn.extents.left;
972 rgndata->rdh.rcBound.top = obj->rgn.extents.top;
973 rgndata->rdh.rcBound.right = obj->rgn.extents.right;
974 rgndata->rdh.rcBound.bottom = obj->rgn.extents.bottom;
976 memcpy( rgndata->Buffer, obj->rgn.rects, size );
978 GDI_ReleaseObj( hrgn );
979 return size + sizeof(RGNDATAHEADER);
983 static void translate( POINT *pt, UINT count, const XFORM *xform )
989 pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
990 pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
996 /***********************************************************************
997 * ExtCreateRegion (GDI32.@)
999 * Creates a region as specified by the transformation data and region data.
1002 * lpXform [I] World-space to logical-space transformation data.
1003 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
1004 * rgndata [I] Data that specifies the region.
1007 * Success: Handle to region.
1011 * See GetRegionData().
1013 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
1017 TRACE(" %p %d %p\n", lpXform, dwCount, rgndata );
1021 SetLastError( ERROR_INVALID_PARAMETER );
1025 if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
1028 /* XP doesn't care about the type */
1029 if( rgndata->rdh.iType != RDH_RECTANGLES )
1030 WARN("(Unsupported region data type: %u)\n", rgndata->rdh.iType);
1034 RECT *pCurRect, *pEndRect;
1036 hrgn = CreateRectRgn( 0, 0, 0, 0 );
1038 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1039 for (pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1041 static const INT count = 4;
1045 pt[0].x = pCurRect->left;
1046 pt[0].y = pCurRect->top;
1047 pt[1].x = pCurRect->right;
1048 pt[1].y = pCurRect->top;
1049 pt[2].x = pCurRect->right;
1050 pt[2].y = pCurRect->bottom;
1051 pt[3].x = pCurRect->left;
1052 pt[3].y = pCurRect->bottom;
1054 translate( pt, 4, lpXform );
1055 poly_hrgn = CreatePolyPolygonRgn( pt, &count, 1, WINDING );
1056 CombineRgn( hrgn, hrgn, poly_hrgn, RGN_OR );
1057 DeleteObject( poly_hrgn );
1062 if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
1064 RECT *pCurRect, *pEndRect;
1065 RGNOBJ *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
1068 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1069 for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1071 if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
1072 REGION_UnionRectWithRegion( pCurRect, &obj->rgn );
1074 GDI_ReleaseObj( hrgn );
1076 TRACE("-- %p\n", hrgn );
1079 else ERR("Could not get pointer to newborn Region!\n");
1086 /***********************************************************************
1087 * PtInRegion (GDI32.@)
1089 * Tests whether the specified point is inside a region.
1092 * hrgn [I] Region to test.
1093 * x [I] X-coordinate of point to test.
1094 * y [I] Y-coordinate of point to test.
1097 * Non-zero if the point is inside the region or zero otherwise.
1099 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
1104 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1108 if (obj->rgn.numRects > 0 && INRECT(obj->rgn.extents, x, y))
1109 for (i = 0; i < obj->rgn.numRects; i++)
1110 if (INRECT (obj->rgn.rects[i], x, y))
1115 GDI_ReleaseObj( hrgn );
1121 /***********************************************************************
1122 * RectInRegion (GDI32.@)
1124 * Tests if a rectangle is at least partly inside the specified region.
1127 * hrgn [I] Region to test.
1128 * rect [I] Rectangle to test.
1131 * Non-zero if the rectangle is partially inside the region or
1134 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
1139 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1141 RECT *pCurRect, *pRectEnd;
1143 /* this is (just) a useful optimization */
1144 if ((obj->rgn.numRects > 0) && EXTENTCHECK(&obj->rgn.extents, rect))
1146 for (pCurRect = obj->rgn.rects, pRectEnd = pCurRect +
1147 obj->rgn.numRects; pCurRect < pRectEnd; pCurRect++)
1149 if (pCurRect->bottom <= rect->top)
1150 continue; /* not far enough down yet */
1152 if (pCurRect->top >= rect->bottom)
1153 break; /* too far down */
1155 if (pCurRect->right <= rect->left)
1156 continue; /* not far enough over yet */
1158 if (pCurRect->left >= rect->right) {
1166 GDI_ReleaseObj(hrgn);
1171 /***********************************************************************
1172 * EqualRgn (GDI32.@)
1174 * Tests whether one region is identical to another.
1177 * hrgn1 [I] The first region to compare.
1178 * hrgn2 [I] The second region to compare.
1181 * Non-zero if both regions are identical or zero otherwise.
1183 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1185 RGNOBJ *obj1, *obj2;
1188 if ((obj1 = GDI_GetObjPtr( hrgn1, OBJ_REGION )))
1190 if ((obj2 = GDI_GetObjPtr( hrgn2, OBJ_REGION )))
1194 if ( obj1->rgn.numRects != obj2->rgn.numRects ) goto done;
1195 if ( obj1->rgn.numRects == 0 )
1201 if (obj1->rgn.extents.left != obj2->rgn.extents.left) goto done;
1202 if (obj1->rgn.extents.right != obj2->rgn.extents.right) goto done;
1203 if (obj1->rgn.extents.top != obj2->rgn.extents.top) goto done;
1204 if (obj1->rgn.extents.bottom != obj2->rgn.extents.bottom) goto done;
1205 for( i = 0; i < obj1->rgn.numRects; i++ )
1207 if (obj1->rgn.rects[i].left != obj2->rgn.rects[i].left) goto done;
1208 if (obj1->rgn.rects[i].right != obj2->rgn.rects[i].right) goto done;
1209 if (obj1->rgn.rects[i].top != obj2->rgn.rects[i].top) goto done;
1210 if (obj1->rgn.rects[i].bottom != obj2->rgn.rects[i].bottom) goto done;
1214 GDI_ReleaseObj(hrgn2);
1216 GDI_ReleaseObj(hrgn1);
1221 /***********************************************************************
1222 * REGION_UnionRectWithRegion
1223 * Adds a rectangle to a WINEREGION
1225 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1229 region.rects = ®ion.extents;
1230 region.numRects = 1;
1232 region.extents = *rect;
1233 REGION_UnionRegion(rgn, rgn, ®ion);
1237 /***********************************************************************
1238 * REGION_CreateFrameRgn
1240 * Create a region that is a frame around another region.
1241 * Compute the intersection of the region moved in all 4 directions
1242 * ( +x, -x, +y, -y) and subtract from the original.
1243 * The result looks slightly better than in Windows :)
1245 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1248 RGNOBJ* destObj = NULL;
1249 RGNOBJ *srcObj = GDI_GetObjPtr( hSrc, OBJ_REGION );
1251 if (!srcObj) return FALSE;
1252 if (srcObj->rgn.numRects != 0)
1256 if (!(destObj = GDI_GetObjPtr( hDest, OBJ_REGION ))) goto done;
1257 if (!init_region( &tmprgn, srcObj->rgn.numRects )) goto done;
1259 REGION_OffsetRegion( &destObj->rgn, &srcObj->rgn, -x, 0);
1260 REGION_OffsetRegion( &tmprgn, &srcObj->rgn, x, 0);
1261 REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn );
1262 REGION_OffsetRegion( &tmprgn, &srcObj->rgn, 0, -y);
1263 REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn );
1264 REGION_OffsetRegion( &tmprgn, &srcObj->rgn, 0, y);
1265 REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn );
1266 REGION_SubtractRegion( &destObj->rgn, &srcObj->rgn, &destObj->rgn );
1268 destroy_region( &tmprgn );
1272 if (destObj) GDI_ReleaseObj ( hDest );
1273 GDI_ReleaseObj( hSrc );
1278 /***********************************************************************
1279 * CombineRgn (GDI32.@)
1281 * Combines two regions with the specified operation and stores the result
1282 * in the specified destination region.
1285 * hDest [I] The region that receives the combined result.
1286 * hSrc1 [I] The first source region.
1287 * hSrc2 [I] The second source region.
1288 * mode [I] The way in which the source regions will be combined. See notes.
1292 * NULLREGION - The new region is empty.
1293 * SIMPLEREGION - The new region can be represented by one rectangle.
1294 * COMPLEXREGION - The new region can only be represented by more than
1299 * The two source regions can be the same region.
1300 * The mode can be one of the following:
1301 *| RGN_AND - Intersection of the regions
1302 *| RGN_OR - Union of the regions
1303 *| RGN_XOR - Unions of the regions minus any intersection.
1304 *| RGN_DIFF - Difference (subtraction) of the regions.
1306 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1308 RGNOBJ *destObj = GDI_GetObjPtr( hDest, OBJ_REGION );
1311 TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1314 RGNOBJ *src1Obj = GDI_GetObjPtr( hSrc1, OBJ_REGION );
1318 TRACE("dump src1Obj:\n");
1319 if(TRACE_ON(region))
1320 REGION_DumpRegion(&src1Obj->rgn);
1321 if (mode == RGN_COPY)
1323 REGION_CopyRegion( &destObj->rgn, &src1Obj->rgn );
1324 result = get_region_type( destObj );
1328 RGNOBJ *src2Obj = GDI_GetObjPtr( hSrc2, OBJ_REGION );
1332 TRACE("dump src2Obj:\n");
1333 if(TRACE_ON(region))
1334 REGION_DumpRegion(&src2Obj->rgn);
1338 REGION_IntersectRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn );
1341 REGION_UnionRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn );
1344 REGION_XorRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn );
1347 REGION_SubtractRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn );
1350 result = get_region_type( destObj );
1351 GDI_ReleaseObj( hSrc2 );
1354 GDI_ReleaseObj( hSrc1 );
1356 TRACE("dump destObj:\n");
1357 if(TRACE_ON(region))
1358 REGION_DumpRegion(&destObj->rgn);
1360 GDI_ReleaseObj( hDest );
1362 ERR("Invalid rgn=%p\n", hDest);
1367 /***********************************************************************
1369 * Re-calculate the extents of a region
1371 static void REGION_SetExtents (WINEREGION *pReg)
1373 RECT *pRect, *pRectEnd, *pExtents;
1375 if (pReg->numRects == 0)
1377 pReg->extents.left = 0;
1378 pReg->extents.top = 0;
1379 pReg->extents.right = 0;
1380 pReg->extents.bottom = 0;
1384 pExtents = &pReg->extents;
1385 pRect = pReg->rects;
1386 pRectEnd = &pRect[pReg->numRects - 1];
1389 * Since pRect is the first rectangle in the region, it must have the
1390 * smallest top and since pRectEnd is the last rectangle in the region,
1391 * it must have the largest bottom, because of banding. Initialize left and
1392 * right from pRect and pRectEnd, resp., as good things to initialize them
1395 pExtents->left = pRect->left;
1396 pExtents->top = pRect->top;
1397 pExtents->right = pRectEnd->right;
1398 pExtents->bottom = pRectEnd->bottom;
1400 while (pRect <= pRectEnd)
1402 if (pRect->left < pExtents->left)
1403 pExtents->left = pRect->left;
1404 if (pRect->right > pExtents->right)
1405 pExtents->right = pRect->right;
1410 /***********************************************************************
1413 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1415 if (dst != src) /* don't want to copy to itself */
1417 if (dst->size < src->numRects)
1419 if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1420 src->numRects * sizeof(RECT) )))
1422 dst->size = src->numRects;
1424 dst->numRects = src->numRects;
1425 dst->extents.left = src->extents.left;
1426 dst->extents.top = src->extents.top;
1427 dst->extents.right = src->extents.right;
1428 dst->extents.bottom = src->extents.bottom;
1429 memcpy(dst->rects, src->rects, src->numRects * sizeof(RECT));
1434 /***********************************************************************
1437 * Attempt to merge the rects in the current band with those in the
1438 * previous one. Used only by REGION_RegionOp.
1441 * The new index for the previous band.
1444 * If coalescing takes place:
1445 * - rectangles in the previous band will have their bottom fields
1447 * - pReg->numRects will be decreased.
1450 static INT REGION_Coalesce (
1451 WINEREGION *pReg, /* Region to coalesce */
1452 INT prevStart, /* Index of start of previous band */
1453 INT curStart /* Index of start of current band */
1455 RECT *pPrevRect; /* Current rect in previous band */
1456 RECT *pCurRect; /* Current rect in current band */
1457 RECT *pRegEnd; /* End of region */
1458 INT curNumRects; /* Number of rectangles in current band */
1459 INT prevNumRects; /* Number of rectangles in previous band */
1460 INT bandtop; /* top coordinate for current band */
1462 pRegEnd = &pReg->rects[pReg->numRects];
1464 pPrevRect = &pReg->rects[prevStart];
1465 prevNumRects = curStart - prevStart;
1468 * Figure out how many rectangles are in the current band. Have to do
1469 * this because multiple bands could have been added in REGION_RegionOp
1470 * at the end when one region has been exhausted.
1472 pCurRect = &pReg->rects[curStart];
1473 bandtop = pCurRect->top;
1474 for (curNumRects = 0;
1475 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1481 if (pCurRect != pRegEnd)
1484 * If more than one band was added, we have to find the start
1485 * of the last band added so the next coalescing job can start
1486 * at the right place... (given when multiple bands are added,
1487 * this may be pointless -- see above).
1490 while (pRegEnd[-1].top == pRegEnd->top)
1494 curStart = pRegEnd - pReg->rects;
1495 pRegEnd = pReg->rects + pReg->numRects;
1498 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1499 pCurRect -= curNumRects;
1501 * The bands may only be coalesced if the bottom of the previous
1502 * matches the top scanline of the current.
1504 if (pPrevRect->bottom == pCurRect->top)
1507 * Make sure the bands have rects in the same places. This
1508 * assumes that rects have been added in such a way that they
1509 * cover the most area possible. I.e. two rects in a band must
1510 * have some horizontal space between them.
1514 if ((pPrevRect->left != pCurRect->left) ||
1515 (pPrevRect->right != pCurRect->right))
1518 * The bands don't line up so they can't be coalesced.
1525 } while (prevNumRects != 0);
1527 pReg->numRects -= curNumRects;
1528 pCurRect -= curNumRects;
1529 pPrevRect -= curNumRects;
1532 * The bands may be merged, so set the bottom of each rect
1533 * in the previous band to that of the corresponding rect in
1538 pPrevRect->bottom = pCurRect->bottom;
1542 } while (curNumRects != 0);
1545 * If only one band was added to the region, we have to backup
1546 * curStart to the start of the previous band.
1548 * If more than one band was added to the region, copy the
1549 * other bands down. The assumption here is that the other bands
1550 * came from the same region as the current one and no further
1551 * coalescing can be done on them since it's all been done
1552 * already... curStart is already in the right place.
1554 if (pCurRect == pRegEnd)
1556 curStart = prevStart;
1562 *pPrevRect++ = *pCurRect++;
1563 } while (pCurRect != pRegEnd);
1571 /***********************************************************************
1574 * Apply an operation to two regions. Called by REGION_Union,
1575 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1581 * The new region is overwritten.
1584 * The idea behind this function is to view the two regions as sets.
1585 * Together they cover a rectangle of area that this function divides
1586 * into horizontal bands where points are covered only by one region
1587 * or by both. For the first case, the nonOverlapFunc is called with
1588 * each the band and the band's upper and lower extents. For the
1589 * second, the overlapFunc is called to process the entire band. It
1590 * is responsible for clipping the rectangles in the band, though
1591 * this function provides the boundaries.
1592 * At the end of each band, the new region is coalesced, if possible,
1593 * to reduce the number of rectangles in the region.
1596 static void REGION_RegionOp(
1597 WINEREGION *newReg, /* Place to store result */
1598 WINEREGION *reg1, /* First region in operation */
1599 WINEREGION *reg2, /* 2nd region in operation */
1600 void (*overlapFunc)(WINEREGION*, RECT*, RECT*, RECT*, RECT*, INT, INT), /* Function to call for over-lapping bands */
1601 void (*nonOverlap1Func)(WINEREGION*, RECT*, RECT*, INT, INT), /* Function to call for non-overlapping bands in region 1 */
1602 void (*nonOverlap2Func)(WINEREGION*, RECT*, RECT*, INT, INT) /* Function to call for non-overlapping bands in region 2 */
1604 RECT *r1; /* Pointer into first region */
1605 RECT *r2; /* Pointer into 2d region */
1606 RECT *r1End; /* End of 1st region */
1607 RECT *r2End; /* End of 2d region */
1608 INT ybot; /* Bottom of intersection */
1609 INT ytop; /* Top of intersection */
1610 RECT *oldRects; /* Old rects for newReg */
1611 INT prevBand; /* Index of start of
1612 * previous band in newReg */
1613 INT curBand; /* Index of start of current
1615 RECT *r1BandEnd; /* End of current band in r1 */
1616 RECT *r2BandEnd; /* End of current band in r2 */
1617 INT top; /* Top of non-overlapping band */
1618 INT bot; /* Bottom of non-overlapping band */
1622 * set r1, r2, r1End and r2End appropriately, preserve the important
1623 * parts of the destination region until the end in case it's one of
1624 * the two source regions, then mark the "new" region empty, allocating
1625 * another array of rectangles for it to use.
1629 r1End = r1 + reg1->numRects;
1630 r2End = r2 + reg2->numRects;
1634 * newReg may be one of the src regions so we can't empty it. We keep a
1635 * note of its rects pointer (so that we can free them later), preserve its
1636 * extents and simply set numRects to zero.
1639 oldRects = newReg->rects;
1640 newReg->numRects = 0;
1643 * Allocate a reasonable number of rectangles for the new region. The idea
1644 * is to allocate enough so the individual functions don't need to
1645 * reallocate and copy the array, which is time consuming, yet we don't
1646 * have to worry about using too much memory. I hope to be able to
1647 * nuke the Xrealloc() at the end of this function eventually.
1649 newReg->size = max(reg1->numRects,reg2->numRects) * 2;
1651 if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1652 sizeof(RECT) * newReg->size )))
1659 * Initialize ybot and ytop.
1660 * In the upcoming loop, ybot and ytop serve different functions depending
1661 * on whether the band being handled is an overlapping or non-overlapping
1663 * In the case of a non-overlapping band (only one of the regions
1664 * has points in the band), ybot is the bottom of the most recent
1665 * intersection and thus clips the top of the rectangles in that band.
1666 * ytop is the top of the next intersection between the two regions and
1667 * serves to clip the bottom of the rectangles in the current band.
1668 * For an overlapping band (where the two regions intersect), ytop clips
1669 * the top of the rectangles of both regions and ybot clips the bottoms.
1671 if (reg1->extents.top < reg2->extents.top)
1672 ybot = reg1->extents.top;
1674 ybot = reg2->extents.top;
1677 * prevBand serves to mark the start of the previous band so rectangles
1678 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1679 * In the beginning, there is no previous band, so prevBand == curBand
1680 * (curBand is set later on, of course, but the first band will always
1681 * start at index 0). prevBand and curBand must be indices because of
1682 * the possible expansion, and resultant moving, of the new region's
1683 * array of rectangles.
1689 curBand = newReg->numRects;
1692 * This algorithm proceeds one source-band (as opposed to a
1693 * destination band, which is determined by where the two regions
1694 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1695 * rectangle after the last one in the current band for their
1696 * respective regions.
1699 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1705 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1711 * First handle the band that doesn't intersect, if any.
1713 * Note that attention is restricted to one band in the
1714 * non-intersecting region at once, so if a region has n
1715 * bands between the current position and the next place it overlaps
1716 * the other, this entire loop will be passed through n times.
1718 if (r1->top < r2->top)
1720 top = max(r1->top,ybot);
1721 bot = min(r1->bottom,r2->top);
1723 if ((top != bot) && (nonOverlap1Func != NULL))
1725 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1730 else if (r2->top < r1->top)
1732 top = max(r2->top,ybot);
1733 bot = min(r2->bottom,r1->top);
1735 if ((top != bot) && (nonOverlap2Func != NULL))
1737 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1748 * If any rectangles got added to the region, try and coalesce them
1749 * with rectangles from the previous band. Note we could just do
1750 * this test in miCoalesce, but some machines incur a not
1751 * inconsiderable cost for function calls, so...
1753 if (newReg->numRects != curBand)
1755 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1759 * Now see if we've hit an intersecting band. The two bands only
1760 * intersect if ybot > ytop
1762 ybot = min(r1->bottom, r2->bottom);
1763 curBand = newReg->numRects;
1766 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1770 if (newReg->numRects != curBand)
1772 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1776 * If we've finished with a band (bottom == ybot) we skip forward
1777 * in the region to the next band.
1779 if (r1->bottom == ybot)
1783 if (r2->bottom == ybot)
1787 } while ((r1 != r1End) && (r2 != r2End));
1790 * Deal with whichever region still has rectangles left.
1792 curBand = newReg->numRects;
1795 if (nonOverlap1Func != NULL)
1800 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1804 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1805 max(r1->top,ybot), r1->bottom);
1807 } while (r1 != r1End);
1810 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1815 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1819 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1820 max(r2->top,ybot), r2->bottom);
1822 } while (r2 != r2End);
1825 if (newReg->numRects != curBand)
1827 (void) REGION_Coalesce (newReg, prevBand, curBand);
1831 * A bit of cleanup. To keep regions from growing without bound,
1832 * we shrink the array of rectangles to match the new number of
1833 * rectangles in the region. This never goes to 0, however...
1835 * Only do this stuff if the number of rectangles allocated is more than
1836 * twice the number of rectangles in the region (a simple optimization...).
1838 if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1840 if (REGION_NOT_EMPTY(newReg))
1842 RECT *prev_rects = newReg->rects;
1843 newReg->size = newReg->numRects;
1844 newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1845 sizeof(RECT) * newReg->size );
1846 if (! newReg->rects)
1847 newReg->rects = prev_rects;
1852 * No point in doing the extra work involved in an Xrealloc if
1853 * the region is empty
1856 HeapFree( GetProcessHeap(), 0, newReg->rects );
1857 newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
1860 HeapFree( GetProcessHeap(), 0, oldRects );
1864 /***********************************************************************
1865 * Region Intersection
1866 ***********************************************************************/
1869 /***********************************************************************
1872 * Handle an overlapping band for REGION_Intersect.
1878 * Rectangles may be added to the region.
1881 static void REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1882 RECT *r2, RECT *r2End, INT top, INT bottom)
1888 pNextRect = &pReg->rects[pReg->numRects];
1890 while ((r1 != r1End) && (r2 != r2End))
1892 left = max(r1->left, r2->left);
1893 right = min(r1->right, r2->right);
1896 * If there's any overlap between the two rectangles, add that
1897 * overlap to the new region.
1898 * There's no need to check for subsumption because the only way
1899 * such a need could arise is if some region has two rectangles
1900 * right next to each other. Since that should never happen...
1904 MEMCHECK(pReg, pNextRect, pReg->rects);
1905 pNextRect->left = left;
1906 pNextRect->top = top;
1907 pNextRect->right = right;
1908 pNextRect->bottom = bottom;
1909 pReg->numRects += 1;
1914 * Need to advance the pointers. Shift the one that extends
1915 * to the right the least, since the other still has a chance to
1916 * overlap with that region's next rectangle, if you see what I mean.
1918 if (r1->right < r2->right)
1922 else if (r2->right < r1->right)
1935 /***********************************************************************
1936 * REGION_IntersectRegion
1938 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1941 /* check for trivial reject */
1942 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1943 (!EXTENTCHECK(®1->extents, ®2->extents)))
1944 newReg->numRects = 0;
1946 REGION_RegionOp (newReg, reg1, reg2, REGION_IntersectO, NULL, NULL);
1949 * Can't alter newReg's extents before we call miRegionOp because
1950 * it might be one of the source regions and miRegionOp depends
1951 * on the extents of those regions being the same. Besides, this
1952 * way there's no checking against rectangles that will be nuked
1953 * due to coalescing, so we have to examine fewer rectangles.
1955 REGION_SetExtents(newReg);
1958 /***********************************************************************
1960 ***********************************************************************/
1962 /***********************************************************************
1965 * Handle a non-overlapping band for the union operation. Just
1966 * Adds the rectangles into the region. Doesn't have to check for
1967 * subsumption or anything.
1973 * pReg->numRects is incremented and the final rectangles overwritten
1974 * with the rectangles we're passed.
1977 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1978 INT top, INT bottom)
1982 pNextRect = &pReg->rects[pReg->numRects];
1986 MEMCHECK(pReg, pNextRect, pReg->rects);
1987 pNextRect->left = r->left;
1988 pNextRect->top = top;
1989 pNextRect->right = r->right;
1990 pNextRect->bottom = bottom;
1991 pReg->numRects += 1;
1998 /***********************************************************************
2001 * Handle an overlapping band for the union operation. Picks the
2002 * left-most rectangle each time and merges it into the region.
2008 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2012 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2013 RECT *r2, RECT *r2End, INT top, INT bottom)
2017 pNextRect = &pReg->rects[pReg->numRects];
2019 #define MERGERECT(r) \
2020 if ((pReg->numRects != 0) && \
2021 (pNextRect[-1].top == top) && \
2022 (pNextRect[-1].bottom == bottom) && \
2023 (pNextRect[-1].right >= r->left)) \
2025 if (pNextRect[-1].right < r->right) \
2027 pNextRect[-1].right = r->right; \
2032 MEMCHECK(pReg, pNextRect, pReg->rects); \
2033 pNextRect->top = top; \
2034 pNextRect->bottom = bottom; \
2035 pNextRect->left = r->left; \
2036 pNextRect->right = r->right; \
2037 pReg->numRects += 1; \
2042 while ((r1 != r1End) && (r2 != r2End))
2044 if (r1->left < r2->left)
2059 } while (r1 != r1End);
2061 else while (r2 != r2End)
2068 /***********************************************************************
2069 * REGION_UnionRegion
2071 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
2074 /* checks all the simple cases */
2077 * Region 1 and 2 are the same or region 1 is empty
2079 if ( (reg1 == reg2) || (!(reg1->numRects)) )
2082 REGION_CopyRegion(newReg, reg2);
2087 * if nothing to union (region 2 empty)
2089 if (!(reg2->numRects))
2092 REGION_CopyRegion(newReg, reg1);
2097 * Region 1 completely subsumes region 2
2099 if ((reg1->numRects == 1) &&
2100 (reg1->extents.left <= reg2->extents.left) &&
2101 (reg1->extents.top <= reg2->extents.top) &&
2102 (reg1->extents.right >= reg2->extents.right) &&
2103 (reg1->extents.bottom >= reg2->extents.bottom))
2106 REGION_CopyRegion(newReg, reg1);
2111 * Region 2 completely subsumes region 1
2113 if ((reg2->numRects == 1) &&
2114 (reg2->extents.left <= reg1->extents.left) &&
2115 (reg2->extents.top <= reg1->extents.top) &&
2116 (reg2->extents.right >= reg1->extents.right) &&
2117 (reg2->extents.bottom >= reg1->extents.bottom))
2120 REGION_CopyRegion(newReg, reg2);
2124 REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO, REGION_UnionNonO, REGION_UnionNonO);
2126 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2127 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2128 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2129 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2132 /***********************************************************************
2133 * Region Subtraction
2134 ***********************************************************************/
2136 /***********************************************************************
2137 * REGION_SubtractNonO1
2139 * Deal with non-overlapping band for subtraction. Any parts from
2140 * region 2 we discard. Anything from region 1 we add to the region.
2146 * pReg may be affected.
2149 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
2150 INT top, INT bottom)
2154 pNextRect = &pReg->rects[pReg->numRects];
2158 MEMCHECK(pReg, pNextRect, pReg->rects);
2159 pNextRect->left = r->left;
2160 pNextRect->top = top;
2161 pNextRect->right = r->right;
2162 pNextRect->bottom = bottom;
2163 pReg->numRects += 1;
2171 /***********************************************************************
2174 * Overlapping band subtraction. x1 is the left-most point not yet
2181 * pReg may have rectangles added to it.
2184 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2185 RECT *r2, RECT *r2End, INT top, INT bottom)
2191 pNextRect = &pReg->rects[pReg->numRects];
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 MEMCHECK(pReg, pNextRect, pReg->rects);
2234 pNextRect->left = left;
2235 pNextRect->top = top;
2236 pNextRect->right = r2->left;
2237 pNextRect->bottom = bottom;
2238 pReg->numRects += 1;
2241 if (left >= r1->right)
2244 * Minuend used up: advance to new...
2253 * Subtrahend used up
2261 * Minuend used up: add any remaining piece before advancing.
2263 if (r1->right > left)
2265 MEMCHECK(pReg, pNextRect, pReg->rects);
2266 pNextRect->left = left;
2267 pNextRect->top = top;
2268 pNextRect->right = r1->right;
2269 pNextRect->bottom = bottom;
2270 pReg->numRects += 1;
2279 * Add remaining minuend rectangles to region.
2283 MEMCHECK(pReg, pNextRect, pReg->rects);
2284 pNextRect->left = left;
2285 pNextRect->top = top;
2286 pNextRect->right = r1->right;
2287 pNextRect->bottom = bottom;
2288 pReg->numRects += 1;
2299 /***********************************************************************
2300 * REGION_SubtractRegion
2302 * Subtract regS from regM and leave the result in regD.
2303 * S stands for subtrahend, M for minuend and D for difference.
2309 * regD is overwritten.
2312 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
2315 /* check for trivial reject */
2316 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2317 (!EXTENTCHECK(®M->extents, ®S->extents)) )
2319 REGION_CopyRegion(regD, regM);
2323 REGION_RegionOp (regD, regM, regS, REGION_SubtractO, REGION_SubtractNonO1, NULL);
2326 * Can't alter newReg's extents before we call miRegionOp because
2327 * it might be one of the source regions and miRegionOp depends
2328 * on the extents of those regions being the unaltered. Besides, this
2329 * way there's no checking against rectangles that will be nuked
2330 * due to coalescing, so we have to examine fewer rectangles.
2332 REGION_SetExtents (regD);
2335 /***********************************************************************
2338 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra, WINEREGION *srb)
2340 WINEREGION tra, trb;
2342 if (!init_region( &tra, sra->numRects + 1 )) return;
2343 if (init_region( &trb, srb->numRects + 1 ))
2345 REGION_SubtractRegion(&tra,sra,srb);
2346 REGION_SubtractRegion(&trb,srb,sra);
2347 REGION_UnionRegion(dr,&tra,&trb);
2348 destroy_region(&trb);
2350 destroy_region(&tra);
2353 /**************************************************************************
2357 *************************************************************************/
2359 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2360 #define SMALL_COORDINATE 0x80000000
2362 /***********************************************************************
2363 * REGION_InsertEdgeInET
2365 * Insert the given edge into the edge table.
2366 * First we must find the correct bucket in the
2367 * Edge table, then find the right slot in the
2368 * bucket. Finally, we can insert it.
2371 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2372 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2375 EdgeTableEntry *start, *prev;
2376 ScanLineList *pSLL, *pPrevSLL;
2377 ScanLineListBlock *tmpSLLBlock;
2380 * find the right bucket to put the edge into
2382 pPrevSLL = &ET->scanlines;
2383 pSLL = pPrevSLL->next;
2384 while (pSLL && (pSLL->scanline < scanline))
2391 * reassign pSLL (pointer to ScanLineList) if necessary
2393 if ((!pSLL) || (pSLL->scanline > scanline))
2395 if (*iSLLBlock > SLLSPERBLOCK-1)
2397 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2400 WARN("Can't alloc SLLB\n");
2403 (*SLLBlock)->next = tmpSLLBlock;
2404 tmpSLLBlock->next = NULL;
2405 *SLLBlock = tmpSLLBlock;
2408 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2410 pSLL->next = pPrevSLL->next;
2411 pSLL->edgelist = NULL;
2412 pPrevSLL->next = pSLL;
2414 pSLL->scanline = scanline;
2417 * now insert the edge in the right bucket
2420 start = pSLL->edgelist;
2421 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2424 start = start->next;
2431 pSLL->edgelist = ETE;
2434 /***********************************************************************
2435 * REGION_CreateEdgeTable
2437 * This routine creates the edge table for
2438 * scan converting polygons.
2439 * The Edge Table (ET) looks like:
2443 * | ymax | ScanLineLists
2444 * |scanline|-->------------>-------------->...
2445 * -------- |scanline| |scanline|
2446 * |edgelist| |edgelist|
2447 * --------- ---------
2451 * list of ETEs list of ETEs
2453 * where ETE is an EdgeTableEntry data structure,
2454 * and there is one ScanLineList per scanline at
2455 * which an edge is initially entered.
2458 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2459 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2460 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2462 const POINT *top, *bottom;
2463 const POINT *PrevPt, *CurrPt, *EndPt;
2470 * initialize the Active Edge Table
2474 AET->nextWETE = NULL;
2475 AET->bres.minor_axis = SMALL_COORDINATE;
2478 * initialize the Edge Table.
2480 ET->scanlines.next = NULL;
2481 ET->ymax = SMALL_COORDINATE;
2482 ET->ymin = LARGE_COORDINATE;
2483 pSLLBlock->next = NULL;
2486 for(poly = 0; poly < nbpolygons; poly++)
2488 count = Count[poly];
2496 * for each vertex in the array of points.
2497 * In this loop we are dealing with two vertices at
2498 * a time -- these make up one edge of the polygon.
2505 * find out which point is above and which is below.
2507 if (PrevPt->y > CurrPt->y)
2509 bottom = PrevPt, top = CurrPt;
2510 pETEs->ClockWise = 0;
2514 bottom = CurrPt, top = PrevPt;
2515 pETEs->ClockWise = 1;
2519 * don't add horizontal edges to the Edge table.
2521 if (bottom->y != top->y)
2523 pETEs->ymax = bottom->y-1;
2524 /* -1 so we don't get last scanline */
2527 * initialize integer edge algorithm
2529 dy = bottom->y - top->y;
2530 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2532 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2535 if (PrevPt->y > ET->ymax)
2536 ET->ymax = PrevPt->y;
2537 if (PrevPt->y < ET->ymin)
2538 ET->ymin = PrevPt->y;
2547 /***********************************************************************
2550 * This routine moves EdgeTableEntries from the
2551 * EdgeTable into the Active Edge Table,
2552 * leaving them sorted by smaller x coordinate.
2555 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2557 EdgeTableEntry *pPrevAET;
2558 EdgeTableEntry *tmp;
2564 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2573 ETEs->back = pPrevAET;
2574 pPrevAET->next = ETEs;
2581 /***********************************************************************
2582 * REGION_computeWAET
2584 * This routine links the AET by the
2585 * nextWETE (winding EdgeTableEntry) link for
2586 * use by the winding number rule. The final
2587 * Active Edge Table (AET) might look something
2591 * ---------- --------- ---------
2592 * |ymax | |ymax | |ymax |
2593 * | ... | |... | |... |
2594 * |next |->|next |->|next |->...
2595 * |nextWETE| |nextWETE| |nextWETE|
2596 * --------- --------- ^--------
2598 * V-------------------> V---> ...
2601 static void REGION_computeWAET(EdgeTableEntry *AET)
2603 register EdgeTableEntry *pWETE;
2604 register int inside = 1;
2605 register int isInside = 0;
2607 AET->nextWETE = NULL;
2617 if ((!inside && !isInside) ||
2618 ( inside && isInside))
2620 pWETE->nextWETE = AET;
2626 pWETE->nextWETE = NULL;
2629 /***********************************************************************
2630 * REGION_InsertionSort
2632 * Just a simple insertion sort using
2633 * pointers and back pointers to sort the Active
2637 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2639 EdgeTableEntry *pETEchase;
2640 EdgeTableEntry *pETEinsert;
2641 EdgeTableEntry *pETEchaseBackTMP;
2642 BOOL changed = FALSE;
2649 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2650 pETEchase = pETEchase->back;
2653 if (pETEchase != pETEinsert)
2655 pETEchaseBackTMP = pETEchase->back;
2656 pETEinsert->back->next = AET;
2658 AET->back = pETEinsert->back;
2659 pETEinsert->next = pETEchase;
2660 pETEchase->back->next = pETEinsert;
2661 pETEchase->back = pETEinsert;
2662 pETEinsert->back = pETEchaseBackTMP;
2669 /***********************************************************************
2670 * REGION_FreeStorage
2674 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2676 ScanLineListBlock *tmpSLLBlock;
2680 tmpSLLBlock = pSLLBlock->next;
2681 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2682 pSLLBlock = tmpSLLBlock;
2687 /***********************************************************************
2688 * REGION_PtsToRegion
2690 * Create an array of rectangles from a list of points.
2692 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2693 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2697 POINTBLOCK *CurPtBlock;
2702 extents = ®->extents;
2704 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2706 if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2707 sizeof(RECT) * numRects )))
2710 reg->size = numRects;
2711 CurPtBlock = FirstPtBlock;
2712 rects = reg->rects - 1;
2714 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2716 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2717 /* the loop uses 2 points per iteration */
2718 i = NUMPTSTOBUFFER >> 1;
2719 if (!numFullPtBlocks)
2720 i = iCurPtBlock >> 1;
2721 for (pts = CurPtBlock->pts; i--; pts += 2) {
2722 if (pts->x == pts[1].x)
2724 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2725 pts[1].x == rects->right &&
2726 (numRects == 1 || rects[-1].top != rects->top) &&
2727 (i && pts[2].y > pts[1].y)) {
2728 rects->bottom = pts[1].y + 1;
2733 rects->left = pts->x; rects->top = pts->y;
2734 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2735 if (rects->left < extents->left)
2736 extents->left = rects->left;
2737 if (rects->right > extents->right)
2738 extents->right = rects->right;
2740 CurPtBlock = CurPtBlock->next;
2744 extents->top = reg->rects->top;
2745 extents->bottom = rects->bottom;
2750 extents->bottom = 0;
2752 reg->numRects = numRects;
2757 /***********************************************************************
2758 * CreatePolyPolygonRgn (GDI32.@)
2760 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2761 INT nbpolygons, INT mode)
2765 EdgeTableEntry *pAET; /* Active Edge Table */
2766 INT y; /* current scanline */
2767 int iPts = 0; /* number of pts in buffer */
2768 EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2769 ScanLineList *pSLL; /* current scanLineList */
2770 POINT *pts; /* output buffer */
2771 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2772 EdgeTable ET; /* header node for ET */
2773 EdgeTableEntry AET; /* header node for AET */
2774 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2775 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2776 int fixWAET = FALSE;
2777 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2778 POINTBLOCK *tmpPtBlock;
2779 int numFullPtBlocks = 0;
2782 TRACE("%p, count %d, polygons %d, mode %d\n", Pts, *Count, nbpolygons, mode);
2784 if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2786 obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
2788 /* special case a rectangle */
2790 if (((nbpolygons == 1) && ((*Count == 4) ||
2791 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2792 (((Pts[0].y == Pts[1].y) &&
2793 (Pts[1].x == Pts[2].x) &&
2794 (Pts[2].y == Pts[3].y) &&
2795 (Pts[3].x == Pts[0].x)) ||
2796 ((Pts[0].x == Pts[1].x) &&
2797 (Pts[1].y == Pts[2].y) &&
2798 (Pts[2].x == Pts[3].x) &&
2799 (Pts[3].y == Pts[0].y))))
2801 SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2802 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2803 GDI_ReleaseObj( hrgn );
2807 for(poly = total = 0; poly < nbpolygons; poly++)
2808 total += Count[poly];
2809 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2811 destroy_region( &obj->rgn );
2812 free_gdi_handle( hrgn );
2813 HeapFree( GetProcessHeap(), 0, obj );
2816 pts = FirstPtBlock.pts;
2817 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2818 pSLL = ET.scanlines.next;
2819 curPtBlock = &FirstPtBlock;
2821 if (mode != WINDING) {
2825 for (y = ET.ymin; y < ET.ymax; y++) {
2827 * Add a new edge to the active edge table when we
2828 * get to the next edge.
2830 if (pSLL != NULL && y == pSLL->scanline) {
2831 REGION_loadAET(&AET, pSLL->edgelist);
2838 * for each active edge
2841 pts->x = pAET->bres.minor_axis, pts->y = y;
2845 * send out the buffer
2847 if (iPts == NUMPTSTOBUFFER) {
2848 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2850 WARN("Can't alloc tPB\n");
2851 HeapFree( GetProcessHeap(), 0, pETEs );
2854 curPtBlock->next = tmpPtBlock;
2855 curPtBlock = tmpPtBlock;
2856 pts = curPtBlock->pts;
2860 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2862 REGION_InsertionSort(&AET);
2869 for (y = ET.ymin; y < ET.ymax; y++) {
2871 * Add a new edge to the active edge table when we
2872 * get to the next edge.
2874 if (pSLL != NULL && y == pSLL->scanline) {
2875 REGION_loadAET(&AET, pSLL->edgelist);
2876 REGION_computeWAET(&AET);
2884 * for each active edge
2888 * add to the buffer only those edges that
2889 * are in the Winding active edge table.
2891 if (pWETE == pAET) {
2892 pts->x = pAET->bres.minor_axis, pts->y = y;
2896 * send out the buffer
2898 if (iPts == NUMPTSTOBUFFER) {
2899 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2900 sizeof(POINTBLOCK) );
2902 WARN("Can't alloc tPB\n");
2903 destroy_region( &obj->rgn );
2904 free_gdi_handle( hrgn );
2905 HeapFree( GetProcessHeap(), 0, obj );
2908 curPtBlock->next = tmpPtBlock;
2909 curPtBlock = tmpPtBlock;
2910 pts = curPtBlock->pts;
2911 numFullPtBlocks++; iPts = 0;
2913 pWETE = pWETE->nextWETE;
2915 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2919 * recompute the winding active edge table if
2920 * we just resorted or have exited an edge.
2922 if (REGION_InsertionSort(&AET) || fixWAET) {
2923 REGION_computeWAET(&AET);
2928 REGION_FreeStorage(SLLBlock.next);
2929 REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, &obj->rgn);
2931 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2932 tmpPtBlock = curPtBlock->next;
2933 HeapFree( GetProcessHeap(), 0, curPtBlock );
2934 curPtBlock = tmpPtBlock;
2936 HeapFree( GetProcessHeap(), 0, pETEs );
2937 GDI_ReleaseObj( hrgn );
2942 /***********************************************************************
2943 * CreatePolygonRgn (GDI32.@)
2945 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2948 return CreatePolyPolygonRgn( points, &count, 1, mode );