shell32: Added a stub for IShellDispatch2.
[wine/multimedia.git] / dlls / gdi32 / region.c
blobdd2827d941221b4213346dc4feb9d3f1fd90c84f
1 /*
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
7 * 1999 Alex Korobka
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.
52 All Rights Reserved
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
68 SOFTWARE.
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
88 * to touch.
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...
97 #include <stdarg.h>
98 #include <stdlib.h>
99 #include <string.h>
100 #include "windef.h"
101 #include "winbase.h"
102 #include "wingdi.h"
103 #include "gdi_private.h"
104 #include "wine/debug.h"
106 WINE_DEFAULT_DEBUG_CHANNEL(region);
108 /* GDI logical region object */
109 typedef struct
111 GDIOBJHDR header;
112 WINEREGION rgn;
113 } RGNOBJ;
116 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc );
117 static BOOL REGION_DeleteObject( HGDIOBJ handle );
119 static const struct gdi_obj_funcs region_funcs =
121 REGION_SelectObject, /* pSelectObject */
122 NULL, /* pGetObjectA */
123 NULL, /* pGetObjectW */
124 NULL, /* pUnrealizeObject */
125 REGION_DeleteObject /* pDeleteObject */
128 /* 1 if two RECTs overlap.
129 * 0 if two RECTs do not overlap.
131 #define EXTENTCHECK(r1, r2) \
132 ((r1)->right > (r2)->left && \
133 (r1)->left < (r2)->right && \
134 (r1)->bottom > (r2)->top && \
135 (r1)->top < (r2)->bottom)
138 static BOOL add_rect( WINEREGION *reg, INT left, INT top, INT right, INT bottom )
140 RECT *rect;
141 if (reg->numRects >= reg->size)
143 RECT *newrects = HeapReAlloc( GetProcessHeap(), 0, reg->rects, 2 * sizeof(RECT) * reg->size );
144 if (!newrects) return FALSE;
145 reg->rects = newrects;
146 reg->size *= 2;
148 rect = reg->rects + reg->numRects++;
149 rect->left = left;
150 rect->top = top;
151 rect->right = right;
152 rect->bottom = bottom;
153 return TRUE;
156 #define EMPTY_REGION(pReg) do { \
157 (pReg)->numRects = 0; \
158 (pReg)->extents.left = (pReg)->extents.top = 0; \
159 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
160 } while(0)
162 #define INRECT(r, x, y) \
163 ( ( ((r).right > x)) && \
164 ( ((r).left <= x)) && \
165 ( ((r).bottom > y)) && \
166 ( ((r).top <= y)) )
170 * number of points to buffer before sending them off
171 * to scanlines() : Must be an even number
173 #define NUMPTSTOBUFFER 200
176 * used to allocate buffers for points and link
177 * the buffers together
180 typedef struct _POINTBLOCK {
181 POINT pts[NUMPTSTOBUFFER];
182 struct _POINTBLOCK *next;
183 } POINTBLOCK;
188 * This file contains a few macros to help track
189 * the edge of a filled object. The object is assumed
190 * to be filled in scanline order, and thus the
191 * algorithm used is an extension of Bresenham's line
192 * drawing algorithm which assumes that y is always the
193 * major axis.
194 * Since these pieces of code are the same for any filled shape,
195 * it is more convenient to gather the library in one
196 * place, but since these pieces of code are also in
197 * the inner loops of output primitives, procedure call
198 * overhead is out of the question.
199 * See the author for a derivation if needed.
204 * In scan converting polygons, we want to choose those pixels
205 * which are inside the polygon. Thus, we add .5 to the starting
206 * x coordinate for both left and right edges. Now we choose the
207 * first pixel which is inside the pgon for the left edge and the
208 * first pixel which is outside the pgon for the right edge.
209 * Draw the left pixel, but not the right.
211 * How to add .5 to the starting x coordinate:
212 * If the edge is moving to the right, then subtract dy from the
213 * error term from the general form of the algorithm.
214 * If the edge is moving to the left, then add dy to the error term.
216 * The reason for the difference between edges moving to the left
217 * and edges moving to the right is simple: If an edge is moving
218 * to the right, then we want the algorithm to flip immediately.
219 * If it is moving to the left, then we don't want it to flip until
220 * we traverse an entire pixel.
222 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
223 int dx; /* local storage */ \
225 /* \
226 * if the edge is horizontal, then it is ignored \
227 * and assumed not to be processed. Otherwise, do this stuff. \
228 */ \
229 if ((dy) != 0) { \
230 xStart = (x1); \
231 dx = (x2) - xStart; \
232 if (dx < 0) { \
233 m = dx / (dy); \
234 m1 = m - 1; \
235 incr1 = -2 * dx + 2 * (dy) * m1; \
236 incr2 = -2 * dx + 2 * (dy) * m; \
237 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
238 } else { \
239 m = dx / (dy); \
240 m1 = m + 1; \
241 incr1 = 2 * dx - 2 * (dy) * m1; \
242 incr2 = 2 * dx - 2 * (dy) * m; \
243 d = -2 * m * (dy) + 2 * dx; \
248 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
249 if (m1 > 0) { \
250 if (d > 0) { \
251 minval += m1; \
252 d += incr1; \
254 else { \
255 minval += m; \
256 d += incr2; \
258 } else {\
259 if (d >= 0) { \
260 minval += m1; \
261 d += incr1; \
263 else { \
264 minval += m; \
265 d += incr2; \
271 * This structure contains all of the information needed
272 * to run the bresenham algorithm.
273 * The variables may be hardcoded into the declarations
274 * instead of using this structure to make use of
275 * register declarations.
277 typedef struct {
278 INT minor_axis; /* minor axis */
279 INT d; /* decision variable */
280 INT m, m1; /* slope and slope+1 */
281 INT incr1, incr2; /* error increments */
282 } BRESINFO;
285 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
286 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
287 bres.m, bres.m1, bres.incr1, bres.incr2)
289 #define BRESINCRPGONSTRUCT(bres) \
290 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
295 * These are the data structures needed to scan
296 * convert regions. Two different scan conversion
297 * methods are available -- the even-odd method, and
298 * the winding number method.
299 * The even-odd rule states that a point is inside
300 * the polygon if a ray drawn from that point in any
301 * direction will pass through an odd number of
302 * path segments.
303 * By the winding number rule, a point is decided
304 * to be inside the polygon if a ray drawn from that
305 * point in any direction passes through a different
306 * number of clockwise and counter-clockwise path
307 * segments.
309 * These data structures are adapted somewhat from
310 * the algorithm in (Foley/Van Dam) for scan converting
311 * polygons.
312 * The basic algorithm is to start at the top (smallest y)
313 * of the polygon, stepping down to the bottom of
314 * the polygon by incrementing the y coordinate. We
315 * keep a list of edges which the current scanline crosses,
316 * sorted by x. This list is called the Active Edge Table (AET)
317 * As we change the y-coordinate, we update each entry in
318 * in the active edge table to reflect the edges new xcoord.
319 * This list must be sorted at each scanline in case
320 * two edges intersect.
321 * We also keep a data structure known as the Edge Table (ET),
322 * which keeps track of all the edges which the current
323 * scanline has not yet reached. The ET is basically a
324 * list of ScanLineList structures containing a list of
325 * edges which are entered at a given scanline. There is one
326 * ScanLineList per scanline at which an edge is entered.
327 * When we enter a new edge, we move it from the ET to the AET.
329 * From the AET, we can implement the even-odd rule as in
330 * (Foley/Van Dam).
331 * The winding number rule is a little trickier. We also
332 * keep the EdgeTableEntries in the AET linked by the
333 * nextWETE (winding EdgeTableEntry) link. This allows
334 * the edges to be linked just as before for updating
335 * purposes, but only uses the edges linked by the nextWETE
336 * link as edges representing spans of the polygon to
337 * drawn (as with the even-odd rule).
341 * for the winding number rule
343 #define CLOCKWISE 1
344 #define COUNTERCLOCKWISE -1
346 typedef struct _EdgeTableEntry {
347 INT ymax; /* ycoord at which we exit this edge. */
348 BRESINFO bres; /* Bresenham info to run the edge */
349 struct _EdgeTableEntry *next; /* next in the list */
350 struct _EdgeTableEntry *back; /* for insertion sort */
351 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
352 int ClockWise; /* flag for winding number rule */
353 } EdgeTableEntry;
356 typedef struct _ScanLineList{
357 INT scanline; /* the scanline represented */
358 EdgeTableEntry *edgelist; /* header node */
359 struct _ScanLineList *next; /* next in the list */
360 } ScanLineList;
363 typedef struct {
364 INT ymax; /* ymax for the polygon */
365 INT ymin; /* ymin for the polygon */
366 ScanLineList scanlines; /* header node */
367 } EdgeTable;
371 * Here is a struct to help with storage allocation
372 * so we can allocate a big chunk at a time, and then take
373 * pieces from this heap when we need to.
375 #define SLLSPERBLOCK 25
377 typedef struct _ScanLineListBlock {
378 ScanLineList SLLs[SLLSPERBLOCK];
379 struct _ScanLineListBlock *next;
380 } ScanLineListBlock;
385 * a few macros for the inner loops of the fill code where
386 * performance considerations don't allow a procedure call.
388 * Evaluate the given edge at the given scanline.
389 * If the edge has expired, then we leave it and fix up
390 * the active edge table; otherwise, we increment the
391 * x value to be ready for the next scanline.
392 * The winding number rule is in effect, so we must notify
393 * the caller when the edge has been removed so he
394 * can reorder the Winding Active Edge Table.
396 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
397 if (pAET->ymax == y) { /* leaving this edge */ \
398 pPrevAET->next = pAET->next; \
399 pAET = pPrevAET->next; \
400 fixWAET = 1; \
401 if (pAET) \
402 pAET->back = pPrevAET; \
404 else { \
405 BRESINCRPGONSTRUCT(pAET->bres); \
406 pPrevAET = pAET; \
407 pAET = pAET->next; \
413 * Evaluate the given edge at the given scanline.
414 * If the edge has expired, then we leave it and fix up
415 * the active edge table; otherwise, we increment the
416 * x value to be ready for the next scanline.
417 * The even-odd rule is in effect.
419 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
420 if (pAET->ymax == y) { /* leaving this edge */ \
421 pPrevAET->next = pAET->next; \
422 pAET = pPrevAET->next; \
423 if (pAET) \
424 pAET->back = pPrevAET; \
426 else { \
427 BRESINCRPGONSTRUCT(pAET->bres); \
428 pPrevAET = pAET; \
429 pAET = pAET->next; \
433 /* Note the parameter order is different from the X11 equivalents */
435 static BOOL REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
436 static BOOL REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
437 static BOOL REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
438 static BOOL REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
439 static BOOL REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
440 static BOOL REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
441 static BOOL REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
443 #define RGN_DEFAULT_RECTS 2
446 /***********************************************************************
447 * get_region_type
449 static inline INT get_region_type( const RGNOBJ *obj )
451 switch(obj->rgn.numRects)
453 case 0: return NULLREGION;
454 case 1: return SIMPLEREGION;
455 default: return COMPLEXREGION;
460 /***********************************************************************
461 * REGION_DumpRegion
462 * Outputs the contents of a WINEREGION
464 static void REGION_DumpRegion(WINEREGION *pReg)
466 RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
468 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg,
469 pReg->extents.left, pReg->extents.top,
470 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
471 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
472 TRACE("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
473 pRect->right, pRect->bottom);
474 return;
478 /***********************************************************************
479 * init_region
481 * Initialize a new empty region.
483 static BOOL init_region( WINEREGION *pReg, INT n )
485 if (!(pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT )))) return FALSE;
486 pReg->size = n;
487 EMPTY_REGION(pReg);
488 return TRUE;
491 /***********************************************************************
492 * destroy_region
494 static void destroy_region( WINEREGION *pReg )
496 HeapFree( GetProcessHeap(), 0, pReg->rects );
499 /***********************************************************************
500 * REGION_DeleteObject
502 static BOOL REGION_DeleteObject( HGDIOBJ handle )
504 RGNOBJ *rgn = free_gdi_handle( handle );
506 if (!rgn) return FALSE;
507 HeapFree( GetProcessHeap(), 0, rgn->rgn.rects );
508 HeapFree( GetProcessHeap(), 0, rgn );
509 return TRUE;
512 /***********************************************************************
513 * REGION_SelectObject
515 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
517 return ULongToHandle(SelectClipRgn( hdc, handle ));
521 /***********************************************************************
522 * REGION_OffsetRegion
523 * Offset a WINEREGION by x,y
525 static BOOL REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn, INT x, INT y )
527 if( rgn != srcrgn)
529 if (!REGION_CopyRegion( rgn, srcrgn)) return FALSE;
531 if(x || y) {
532 int nbox = rgn->numRects;
533 RECT *pbox = rgn->rects;
535 if(nbox) {
536 while(nbox--) {
537 pbox->left += x;
538 pbox->right += x;
539 pbox->top += y;
540 pbox->bottom += y;
541 pbox++;
543 rgn->extents.left += x;
544 rgn->extents.right += x;
545 rgn->extents.top += y;
546 rgn->extents.bottom += y;
549 return TRUE;
552 /***********************************************************************
553 * OffsetRgn (GDI32.@)
555 * Moves a region by the specified X- and Y-axis offsets.
557 * PARAMS
558 * hrgn [I] Region to offset.
559 * x [I] Offset right if positive or left if negative.
560 * y [I] Offset down if positive or up if negative.
562 * RETURNS
563 * Success:
564 * NULLREGION - The new region is empty.
565 * SIMPLEREGION - The new region can be represented by one rectangle.
566 * COMPLEXREGION - The new region can only be represented by more than
567 * one rectangle.
568 * Failure: ERROR
570 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
572 RGNOBJ * obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
573 INT ret;
575 TRACE("%p %d,%d\n", hrgn, x, y);
577 if (!obj)
578 return ERROR;
580 REGION_OffsetRegion( &obj->rgn, &obj->rgn, x, y);
582 ret = get_region_type( obj );
583 GDI_ReleaseObj( hrgn );
584 return ret;
588 /***********************************************************************
589 * GetRgnBox (GDI32.@)
591 * Retrieves the bounding rectangle of the region. The bounding rectangle
592 * is the smallest rectangle that contains the entire region.
594 * PARAMS
595 * hrgn [I] Region to retrieve bounding rectangle from.
596 * rect [O] Rectangle that will receive the coordinates of the bounding
597 * rectangle.
599 * RETURNS
600 * NULLREGION - The new region is empty.
601 * SIMPLEREGION - The new region can be represented by one rectangle.
602 * COMPLEXREGION - The new region can only be represented by more than
603 * one rectangle.
605 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
607 RGNOBJ * obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
608 if (obj)
610 INT ret;
611 rect->left = obj->rgn.extents.left;
612 rect->top = obj->rgn.extents.top;
613 rect->right = obj->rgn.extents.right;
614 rect->bottom = obj->rgn.extents.bottom;
615 TRACE("%p (%d,%d-%d,%d)\n", hrgn,
616 rect->left, rect->top, rect->right, rect->bottom);
617 ret = get_region_type( obj );
618 GDI_ReleaseObj(hrgn);
619 return ret;
621 return ERROR;
625 /***********************************************************************
626 * CreateRectRgn (GDI32.@)
628 * Creates a simple rectangular region.
630 * PARAMS
631 * left [I] Left coordinate of rectangle.
632 * top [I] Top coordinate of rectangle.
633 * right [I] Right coordinate of rectangle.
634 * bottom [I] Bottom coordinate of rectangle.
636 * RETURNS
637 * Success: Handle to region.
638 * Failure: NULL.
640 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
642 HRGN hrgn;
643 RGNOBJ *obj;
645 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
647 /* Allocate 2 rects by default to reduce the number of reallocs */
648 if (!init_region( &obj->rgn, RGN_DEFAULT_RECTS ))
650 HeapFree( GetProcessHeap(), 0, obj );
651 return 0;
653 if (!(hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs )))
655 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
656 HeapFree( GetProcessHeap(), 0, obj );
657 return 0;
659 TRACE( "%d,%d-%d,%d returning %p\n", left, top, right, bottom, hrgn );
660 SetRectRgn(hrgn, left, top, right, bottom);
661 return hrgn;
665 /***********************************************************************
666 * CreateRectRgnIndirect (GDI32.@)
668 * Creates a simple rectangular region.
670 * PARAMS
671 * rect [I] Coordinates of rectangular region.
673 * RETURNS
674 * Success: Handle to region.
675 * Failure: NULL.
677 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
679 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
683 /***********************************************************************
684 * SetRectRgn (GDI32.@)
686 * Sets a region to a simple rectangular region.
688 * PARAMS
689 * hrgn [I] Region to convert.
690 * left [I] Left coordinate of rectangle.
691 * top [I] Top coordinate of rectangle.
692 * right [I] Right coordinate of rectangle.
693 * bottom [I] Bottom coordinate of rectangle.
695 * RETURNS
696 * Success: Non-zero.
697 * Failure: Zero.
699 * NOTES
700 * Allows either or both left and top to be greater than right or bottom.
702 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
703 INT right, INT bottom )
705 RGNOBJ * obj;
707 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
709 if (!(obj = GDI_GetObjPtr( hrgn, OBJ_REGION ))) return FALSE;
711 if (left > right) { INT tmp = left; left = right; right = tmp; }
712 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
714 if((left != right) && (top != bottom))
716 obj->rgn.rects->left = obj->rgn.extents.left = left;
717 obj->rgn.rects->top = obj->rgn.extents.top = top;
718 obj->rgn.rects->right = obj->rgn.extents.right = right;
719 obj->rgn.rects->bottom = obj->rgn.extents.bottom = bottom;
720 obj->rgn.numRects = 1;
722 else
723 EMPTY_REGION(&obj->rgn);
725 GDI_ReleaseObj( hrgn );
726 return TRUE;
730 /***********************************************************************
731 * CreateRoundRectRgn (GDI32.@)
733 * Creates a rectangular region with rounded corners.
735 * PARAMS
736 * left [I] Left coordinate of rectangle.
737 * top [I] Top coordinate of rectangle.
738 * right [I] Right coordinate of rectangle.
739 * bottom [I] Bottom coordinate of rectangle.
740 * ellipse_width [I] Width of the ellipse at each corner.
741 * ellipse_height [I] Height of the ellipse at each corner.
743 * RETURNS
744 * Success: Handle to region.
745 * Failure: NULL.
747 * NOTES
748 * If ellipse_width or ellipse_height is less than 2 logical units then
749 * it is treated as though CreateRectRgn() was called instead.
751 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
752 INT right, INT bottom,
753 INT ellipse_width, INT ellipse_height )
755 RGNOBJ * obj;
756 HRGN hrgn = 0;
757 int a, b, i, x, y;
758 INT64 asq, bsq, dx, dy, err;
759 RECT *rects;
761 /* Make the dimensions sensible */
763 if (left > right) { INT tmp = left; left = right; right = tmp; }
764 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
765 /* the region is for the rectangle interior, but only at right and bottom for some reason */
766 right--;
767 bottom--;
769 ellipse_width = min( right - left, abs( ellipse_width ));
770 ellipse_height = min( bottom - top, abs( ellipse_height ));
772 /* Check if we can do a normal rectangle instead */
774 if ((ellipse_width < 2) || (ellipse_height < 2))
775 return CreateRectRgn( left, top, right, bottom );
777 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
778 obj->rgn.size = ellipse_height;
779 obj->rgn.numRects = ellipse_height;
780 obj->rgn.extents.left = left;
781 obj->rgn.extents.top = top;
782 obj->rgn.extents.right = right;
783 obj->rgn.extents.bottom = bottom;
785 obj->rgn.rects = rects = HeapAlloc( GetProcessHeap(), 0, obj->rgn.size * sizeof(RECT) );
786 if (!rects) goto done;
788 /* based on an algorithm by Alois Zingl */
790 a = ellipse_width - 1;
791 b = ellipse_height - 1;
792 asq = (INT64)8 * a * a;
793 bsq = (INT64)8 * b * b;
794 dx = (INT64)4 * b * b * (1 - a);
795 dy = (INT64)4 * a * a * (1 + (b % 2));
796 err = dx + dy + a * a * (b % 2);
798 x = 0;
799 y = ellipse_height / 2;
801 rects[y].left = left;
802 rects[y].right = right;
804 while (x <= ellipse_width / 2)
806 INT64 e2 = 2 * err;
807 if (e2 >= dx)
809 x++;
810 err += dx += bsq;
812 if (e2 <= dy)
814 y++;
815 err += dy += asq;
816 rects[y].left = left + x;
817 rects[y].right = right - x;
820 for (i = 0; i < ellipse_height / 2; i++)
822 rects[i].left = rects[b - i].left;
823 rects[i].right = rects[b - i].right;
824 rects[i].top = top + i;
825 rects[i].bottom = rects[i].top + 1;
827 for (; i < ellipse_height; i++)
829 rects[i].top = bottom - ellipse_height + i;
830 rects[i].bottom = rects[i].top + 1;
832 rects[ellipse_height / 2].top = top + ellipse_height / 2; /* extend to top of rectangle */
834 hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs );
836 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
837 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
838 done:
839 if (!hrgn)
841 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
842 HeapFree( GetProcessHeap(), 0, obj );
844 return hrgn;
848 /***********************************************************************
849 * CreateEllipticRgn (GDI32.@)
851 * Creates an elliptical region.
853 * PARAMS
854 * left [I] Left coordinate of bounding rectangle.
855 * top [I] Top coordinate of bounding rectangle.
856 * right [I] Right coordinate of bounding rectangle.
857 * bottom [I] Bottom coordinate of bounding rectangle.
859 * RETURNS
860 * Success: Handle to region.
861 * Failure: NULL.
863 * NOTES
864 * This is a special case of CreateRoundRectRgn() where the width of the
865 * ellipse at each corner is equal to the width the rectangle and
866 * the same for the height.
868 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
869 INT right, INT bottom )
871 return CreateRoundRectRgn( left, top, right, bottom,
872 right-left, bottom-top );
876 /***********************************************************************
877 * CreateEllipticRgnIndirect (GDI32.@)
879 * Creates an elliptical region.
881 * PARAMS
882 * rect [I] Pointer to bounding rectangle of the ellipse.
884 * RETURNS
885 * Success: Handle to region.
886 * Failure: NULL.
888 * NOTES
889 * This is a special case of CreateRoundRectRgn() where the width of the
890 * ellipse at each corner is equal to the width the rectangle and
891 * the same for the height.
893 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
895 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
896 rect->bottom, rect->right - rect->left,
897 rect->bottom - rect->top );
900 /*********************************************************************
901 * get_wine_region
903 * Return the region data without making a copy. The caller
904 * must not alter anything and must call GDI_ReleaseObj() when
905 * they have finished with the data.
907 const WINEREGION *get_wine_region(HRGN rgn)
909 RGNOBJ *obj = GDI_GetObjPtr( rgn, OBJ_REGION );
910 if(!obj) return NULL;
911 return &obj->rgn;
914 /***********************************************************************
915 * GetRegionData (GDI32.@)
917 * Retrieves the data that specifies the region.
919 * PARAMS
920 * hrgn [I] Region to retrieve the region data from.
921 * count [I] The size of the buffer pointed to by rgndata in bytes.
922 * rgndata [I] The buffer to receive data about the region.
924 * RETURNS
925 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
926 * the number of bytes copied to the output buffer.
927 * Failure: 0.
929 * NOTES
930 * The format of the Buffer member of RGNDATA is determined by the iType
931 * member of the region data header.
932 * Currently this is always RDH_RECTANGLES, which specifies that the format
933 * is the array of RECT's that specify the region. The length of the array
934 * is specified by the nCount member of the region data header.
936 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
938 DWORD size;
939 RGNOBJ *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
941 TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
943 if(!obj) return 0;
945 size = obj->rgn.numRects * sizeof(RECT);
946 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
948 GDI_ReleaseObj( hrgn );
949 if (rgndata) /* buffer is too small, signal it by return 0 */
950 return 0;
951 else /* user requested buffer size with rgndata NULL */
952 return size + sizeof(RGNDATAHEADER);
955 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
956 rgndata->rdh.iType = RDH_RECTANGLES;
957 rgndata->rdh.nCount = obj->rgn.numRects;
958 rgndata->rdh.nRgnSize = size;
959 rgndata->rdh.rcBound.left = obj->rgn.extents.left;
960 rgndata->rdh.rcBound.top = obj->rgn.extents.top;
961 rgndata->rdh.rcBound.right = obj->rgn.extents.right;
962 rgndata->rdh.rcBound.bottom = obj->rgn.extents.bottom;
964 memcpy( rgndata->Buffer, obj->rgn.rects, size );
966 GDI_ReleaseObj( hrgn );
967 return size + sizeof(RGNDATAHEADER);
971 static void translate( POINT *pt, UINT count, const XFORM *xform )
973 while (count--)
975 double x = pt->x;
976 double y = pt->y;
977 pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
978 pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
979 pt++;
984 /***********************************************************************
985 * ExtCreateRegion (GDI32.@)
987 * Creates a region as specified by the transformation data and region data.
989 * PARAMS
990 * lpXform [I] World-space to logical-space transformation data.
991 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
992 * rgndata [I] Data that specifies the region.
994 * RETURNS
995 * Success: Handle to region.
996 * Failure: NULL.
998 * NOTES
999 * See GetRegionData().
1001 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
1003 HRGN hrgn = 0;
1004 RGNOBJ *obj;
1006 if (!rgndata)
1008 SetLastError( ERROR_INVALID_PARAMETER );
1009 return 0;
1012 if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
1013 return 0;
1015 /* XP doesn't care about the type */
1016 if( rgndata->rdh.iType != RDH_RECTANGLES )
1017 WARN("(Unsupported region data type: %u)\n", rgndata->rdh.iType);
1019 if (lpXform)
1021 const RECT *pCurRect, *pEndRect;
1023 hrgn = CreateRectRgn( 0, 0, 0, 0 );
1025 pEndRect = (const RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1026 for (pCurRect = (const RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1028 static const INT count = 4;
1029 HRGN poly_hrgn;
1030 POINT pt[4];
1032 pt[0].x = pCurRect->left;
1033 pt[0].y = pCurRect->top;
1034 pt[1].x = pCurRect->right;
1035 pt[1].y = pCurRect->top;
1036 pt[2].x = pCurRect->right;
1037 pt[2].y = pCurRect->bottom;
1038 pt[3].x = pCurRect->left;
1039 pt[3].y = pCurRect->bottom;
1041 translate( pt, 4, lpXform );
1042 poly_hrgn = CreatePolyPolygonRgn( pt, &count, 1, WINDING );
1043 CombineRgn( hrgn, hrgn, poly_hrgn, RGN_OR );
1044 DeleteObject( poly_hrgn );
1046 return hrgn;
1049 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
1051 if (init_region( &obj->rgn, rgndata->rdh.nCount ))
1053 const RECT *pCurRect, *pEndRect;
1055 pEndRect = (const RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1056 for(pCurRect = (const RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1058 if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
1060 if (!REGION_UnionRectWithRegion( pCurRect, &obj->rgn )) goto done;
1063 hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs );
1065 else
1067 HeapFree( GetProcessHeap(), 0, obj );
1068 return 0;
1071 done:
1072 if (!hrgn)
1074 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
1075 HeapFree( GetProcessHeap(), 0, obj );
1077 TRACE("%p %d %p returning %p\n", lpXform, dwCount, rgndata, hrgn );
1078 return hrgn;
1082 /***********************************************************************
1083 * PtInRegion (GDI32.@)
1085 * Tests whether the specified point is inside a region.
1087 * PARAMS
1088 * hrgn [I] Region to test.
1089 * x [I] X-coordinate of point to test.
1090 * y [I] Y-coordinate of point to test.
1092 * RETURNS
1093 * Non-zero if the point is inside the region or zero otherwise.
1095 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
1097 RGNOBJ * obj;
1098 BOOL ret = FALSE;
1100 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1102 int i;
1104 if (obj->rgn.numRects > 0 && INRECT(obj->rgn.extents, x, y))
1105 for (i = 0; i < obj->rgn.numRects; i++)
1106 if (INRECT (obj->rgn.rects[i], x, y))
1108 ret = TRUE;
1109 break;
1111 GDI_ReleaseObj( hrgn );
1113 return ret;
1117 /***********************************************************************
1118 * RectInRegion (GDI32.@)
1120 * Tests if a rectangle is at least partly inside the specified region.
1122 * PARAMS
1123 * hrgn [I] Region to test.
1124 * rect [I] Rectangle to test.
1126 * RETURNS
1127 * Non-zero if the rectangle is partially inside the region or
1128 * zero otherwise.
1130 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
1132 RGNOBJ * obj;
1133 BOOL ret = FALSE;
1134 RECT rc;
1136 /* swap the coordinates to make right >= left and bottom >= top */
1137 /* (region building rectangles are normalized the same way) */
1138 if( rect->top > rect->bottom) {
1139 rc.top = rect->bottom;
1140 rc.bottom = rect->top;
1141 } else {
1142 rc.top = rect->top;
1143 rc.bottom = rect->bottom;
1145 if( rect->right < rect->left) {
1146 rc.right = rect->left;
1147 rc.left = rect->right;
1148 } else {
1149 rc.right = rect->right;
1150 rc.left = rect->left;
1153 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1155 RECT *pCurRect, *pRectEnd;
1157 /* this is (just) a useful optimization */
1158 if ((obj->rgn.numRects > 0) && EXTENTCHECK(&obj->rgn.extents, &rc))
1160 for (pCurRect = obj->rgn.rects, pRectEnd = pCurRect +
1161 obj->rgn.numRects; pCurRect < pRectEnd; pCurRect++)
1163 if (pCurRect->bottom <= rc.top)
1164 continue; /* not far enough down yet */
1166 if (pCurRect->top >= rc.bottom)
1167 break; /* too far down */
1169 if (pCurRect->right <= rc.left)
1170 continue; /* not far enough over yet */
1172 if (pCurRect->left >= rc.right) {
1173 continue;
1176 ret = TRUE;
1177 break;
1180 GDI_ReleaseObj(hrgn);
1182 return ret;
1185 /***********************************************************************
1186 * EqualRgn (GDI32.@)
1188 * Tests whether one region is identical to another.
1190 * PARAMS
1191 * hrgn1 [I] The first region to compare.
1192 * hrgn2 [I] The second region to compare.
1194 * RETURNS
1195 * Non-zero if both regions are identical or zero otherwise.
1197 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1199 RGNOBJ *obj1, *obj2;
1200 BOOL ret = FALSE;
1202 if ((obj1 = GDI_GetObjPtr( hrgn1, OBJ_REGION )))
1204 if ((obj2 = GDI_GetObjPtr( hrgn2, OBJ_REGION )))
1206 int i;
1208 if ( obj1->rgn.numRects != obj2->rgn.numRects ) goto done;
1209 if ( obj1->rgn.numRects == 0 )
1211 ret = TRUE;
1212 goto done;
1215 if (obj1->rgn.extents.left != obj2->rgn.extents.left) goto done;
1216 if (obj1->rgn.extents.right != obj2->rgn.extents.right) goto done;
1217 if (obj1->rgn.extents.top != obj2->rgn.extents.top) goto done;
1218 if (obj1->rgn.extents.bottom != obj2->rgn.extents.bottom) goto done;
1219 for( i = 0; i < obj1->rgn.numRects; i++ )
1221 if (obj1->rgn.rects[i].left != obj2->rgn.rects[i].left) goto done;
1222 if (obj1->rgn.rects[i].right != obj2->rgn.rects[i].right) goto done;
1223 if (obj1->rgn.rects[i].top != obj2->rgn.rects[i].top) goto done;
1224 if (obj1->rgn.rects[i].bottom != obj2->rgn.rects[i].bottom) goto done;
1226 ret = TRUE;
1227 done:
1228 GDI_ReleaseObj(hrgn2);
1230 GDI_ReleaseObj(hrgn1);
1232 return ret;
1235 /***********************************************************************
1236 * REGION_UnionRectWithRegion
1237 * Adds a rectangle to a WINEREGION
1239 static BOOL REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1241 WINEREGION region;
1243 region.rects = &region.extents;
1244 region.numRects = 1;
1245 region.size = 1;
1246 region.extents = *rect;
1247 return REGION_UnionRegion(rgn, rgn, &region);
1251 BOOL add_rect_to_region( HRGN rgn, const RECT *rect )
1253 RGNOBJ *obj = GDI_GetObjPtr( rgn, OBJ_REGION );
1254 BOOL ret;
1256 if (!obj) return FALSE;
1257 ret = REGION_UnionRectWithRegion( rect, &obj->rgn );
1258 GDI_ReleaseObj( rgn );
1259 return ret;
1262 /***********************************************************************
1263 * REGION_CreateFrameRgn
1265 * Create a region that is a frame around another region.
1266 * Compute the intersection of the region moved in all 4 directions
1267 * ( +x, -x, +y, -y) and subtract from the original.
1268 * The result looks slightly better than in Windows :)
1270 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1272 WINEREGION tmprgn;
1273 BOOL bRet = FALSE;
1274 RGNOBJ* destObj = NULL;
1275 RGNOBJ *srcObj = GDI_GetObjPtr( hSrc, OBJ_REGION );
1277 tmprgn.rects = NULL;
1278 if (!srcObj) return FALSE;
1279 if (srcObj->rgn.numRects != 0)
1281 if (!(destObj = GDI_GetObjPtr( hDest, OBJ_REGION ))) goto done;
1282 if (!init_region( &tmprgn, srcObj->rgn.numRects )) goto done;
1284 if (!REGION_OffsetRegion( &destObj->rgn, &srcObj->rgn, -x, 0)) goto done;
1285 if (!REGION_OffsetRegion( &tmprgn, &srcObj->rgn, x, 0)) goto done;
1286 if (!REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn )) goto done;
1287 if (!REGION_OffsetRegion( &tmprgn, &srcObj->rgn, 0, -y)) goto done;
1288 if (!REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn )) goto done;
1289 if (!REGION_OffsetRegion( &tmprgn, &srcObj->rgn, 0, y)) goto done;
1290 if (!REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn )) goto done;
1291 if (!REGION_SubtractRegion( &destObj->rgn, &srcObj->rgn, &destObj->rgn )) goto done;
1292 bRet = TRUE;
1294 done:
1295 HeapFree( GetProcessHeap(), 0, tmprgn.rects );
1296 if (destObj) GDI_ReleaseObj ( hDest );
1297 GDI_ReleaseObj( hSrc );
1298 return bRet;
1302 /***********************************************************************
1303 * CombineRgn (GDI32.@)
1305 * Combines two regions with the specified operation and stores the result
1306 * in the specified destination region.
1308 * PARAMS
1309 * hDest [I] The region that receives the combined result.
1310 * hSrc1 [I] The first source region.
1311 * hSrc2 [I] The second source region.
1312 * mode [I] The way in which the source regions will be combined. See notes.
1314 * RETURNS
1315 * Success:
1316 * NULLREGION - The new region is empty.
1317 * SIMPLEREGION - The new region can be represented by one rectangle.
1318 * COMPLEXREGION - The new region can only be represented by more than
1319 * one rectangle.
1320 * Failure: ERROR
1322 * NOTES
1323 * The two source regions can be the same region.
1324 * The mode can be one of the following:
1325 *| RGN_AND - Intersection of the regions
1326 *| RGN_OR - Union of the regions
1327 *| RGN_XOR - Unions of the regions minus any intersection.
1328 *| RGN_DIFF - Difference (subtraction) of the regions.
1330 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1332 RGNOBJ *destObj = GDI_GetObjPtr( hDest, OBJ_REGION );
1333 INT result = ERROR;
1335 TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1336 if (destObj)
1338 RGNOBJ *src1Obj = GDI_GetObjPtr( hSrc1, OBJ_REGION );
1340 if (src1Obj)
1342 TRACE("dump src1Obj:\n");
1343 if(TRACE_ON(region))
1344 REGION_DumpRegion(&src1Obj->rgn);
1345 if (mode == RGN_COPY)
1347 if (REGION_CopyRegion( &destObj->rgn, &src1Obj->rgn ))
1348 result = get_region_type( destObj );
1350 else
1352 RGNOBJ *src2Obj = GDI_GetObjPtr( hSrc2, OBJ_REGION );
1354 if (src2Obj)
1356 TRACE("dump src2Obj:\n");
1357 if(TRACE_ON(region))
1358 REGION_DumpRegion(&src2Obj->rgn);
1359 switch (mode)
1361 case RGN_AND:
1362 if (REGION_IntersectRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1363 result = get_region_type( destObj );
1364 break;
1365 case RGN_OR:
1366 if (REGION_UnionRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1367 result = get_region_type( destObj );
1368 break;
1369 case RGN_XOR:
1370 if (REGION_XorRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1371 result = get_region_type( destObj );
1372 break;
1373 case RGN_DIFF:
1374 if (REGION_SubtractRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1375 result = get_region_type( destObj );
1376 break;
1378 GDI_ReleaseObj( hSrc2 );
1381 GDI_ReleaseObj( hSrc1 );
1383 TRACE("dump destObj:\n");
1384 if(TRACE_ON(region))
1385 REGION_DumpRegion(&destObj->rgn);
1387 GDI_ReleaseObj( hDest );
1389 return result;
1392 /***********************************************************************
1393 * REGION_SetExtents
1394 * Re-calculate the extents of a region
1396 static void REGION_SetExtents (WINEREGION *pReg)
1398 RECT *pRect, *pRectEnd, *pExtents;
1400 if (pReg->numRects == 0)
1402 pReg->extents.left = 0;
1403 pReg->extents.top = 0;
1404 pReg->extents.right = 0;
1405 pReg->extents.bottom = 0;
1406 return;
1409 pExtents = &pReg->extents;
1410 pRect = pReg->rects;
1411 pRectEnd = &pRect[pReg->numRects - 1];
1414 * Since pRect is the first rectangle in the region, it must have the
1415 * smallest top and since pRectEnd is the last rectangle in the region,
1416 * it must have the largest bottom, because of banding. Initialize left and
1417 * right from pRect and pRectEnd, resp., as good things to initialize them
1418 * to...
1420 pExtents->left = pRect->left;
1421 pExtents->top = pRect->top;
1422 pExtents->right = pRectEnd->right;
1423 pExtents->bottom = pRectEnd->bottom;
1425 while (pRect <= pRectEnd)
1427 if (pRect->left < pExtents->left)
1428 pExtents->left = pRect->left;
1429 if (pRect->right > pExtents->right)
1430 pExtents->right = pRect->right;
1431 pRect++;
1435 /***********************************************************************
1436 * REGION_CopyRegion
1438 static BOOL REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1440 if (dst != src) /* don't want to copy to itself */
1442 if (dst->size < src->numRects)
1444 RECT *rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects, src->numRects * sizeof(RECT) );
1445 if (!rects) return FALSE;
1446 dst->rects = rects;
1447 dst->size = src->numRects;
1449 dst->numRects = src->numRects;
1450 dst->extents.left = src->extents.left;
1451 dst->extents.top = src->extents.top;
1452 dst->extents.right = src->extents.right;
1453 dst->extents.bottom = src->extents.bottom;
1454 memcpy(dst->rects, src->rects, src->numRects * sizeof(RECT));
1456 return TRUE;
1459 /***********************************************************************
1460 * REGION_MirrorRegion
1462 static BOOL REGION_MirrorRegion( WINEREGION *dst, WINEREGION *src, int width )
1464 int i, start, end;
1465 RECT extents;
1466 RECT *rects = HeapAlloc( GetProcessHeap(), 0, src->numRects * sizeof(RECT) );
1468 if (!rects) return FALSE;
1470 extents.left = width - src->extents.right;
1471 extents.right = width - src->extents.left;
1472 extents.top = src->extents.top;
1473 extents.bottom = src->extents.bottom;
1475 for (start = 0; start < src->numRects; start = end)
1477 /* find the end of the current band */
1478 for (end = start + 1; end < src->numRects; end++)
1479 if (src->rects[end].top != src->rects[end - 1].top) break;
1481 for (i = 0; i < end - start; i++)
1483 rects[start + i].left = width - src->rects[end - i - 1].right;
1484 rects[start + i].right = width - src->rects[end - i - 1].left;
1485 rects[start + i].top = src->rects[end - i - 1].top;
1486 rects[start + i].bottom = src->rects[end - i - 1].bottom;
1490 HeapFree( GetProcessHeap(), 0, dst->rects );
1491 dst->rects = rects;
1492 dst->size = src->numRects;
1493 dst->numRects = src->numRects;
1494 dst->extents = extents;
1495 return TRUE;
1498 /***********************************************************************
1499 * mirror_region
1501 INT mirror_region( HRGN dst, HRGN src, INT width )
1503 RGNOBJ *src_rgn, *dst_rgn;
1504 INT ret = ERROR;
1506 if (!(src_rgn = GDI_GetObjPtr( src, OBJ_REGION ))) return ERROR;
1507 if ((dst_rgn = GDI_GetObjPtr( dst, OBJ_REGION )))
1509 if (REGION_MirrorRegion( &dst_rgn->rgn, &src_rgn->rgn, width )) ret = get_region_type( dst_rgn );
1510 GDI_ReleaseObj( dst_rgn );
1512 GDI_ReleaseObj( src_rgn );
1513 return ret;
1516 /***********************************************************************
1517 * MirrorRgn (GDI32.@)
1519 BOOL WINAPI MirrorRgn( HWND hwnd, HRGN hrgn )
1521 static const WCHAR user32W[] = {'u','s','e','r','3','2','.','d','l','l',0};
1522 static BOOL (WINAPI *pGetWindowRect)( HWND hwnd, LPRECT rect );
1523 RECT rect;
1525 /* yes, a HWND in gdi32, don't ask */
1526 if (!pGetWindowRect)
1528 HMODULE user32 = GetModuleHandleW(user32W);
1529 if (!user32) return FALSE;
1530 if (!(pGetWindowRect = (void *)GetProcAddress( user32, "GetWindowRect" ))) return FALSE;
1532 pGetWindowRect( hwnd, &rect );
1533 return mirror_region( hrgn, hrgn, rect.right - rect.left ) != ERROR;
1537 /***********************************************************************
1538 * REGION_Coalesce
1540 * Attempt to merge the rects in the current band with those in the
1541 * previous one. Used only by REGION_RegionOp.
1543 * Results:
1544 * The new index for the previous band.
1546 * Side Effects:
1547 * If coalescing takes place:
1548 * - rectangles in the previous band will have their bottom fields
1549 * altered.
1550 * - pReg->numRects will be decreased.
1553 static INT REGION_Coalesce (
1554 WINEREGION *pReg, /* Region to coalesce */
1555 INT prevStart, /* Index of start of previous band */
1556 INT curStart /* Index of start of current band */
1558 RECT *pPrevRect; /* Current rect in previous band */
1559 RECT *pCurRect; /* Current rect in current band */
1560 RECT *pRegEnd; /* End of region */
1561 INT curNumRects; /* Number of rectangles in current band */
1562 INT prevNumRects; /* Number of rectangles in previous band */
1563 INT bandtop; /* top coordinate for current band */
1565 pRegEnd = &pReg->rects[pReg->numRects];
1567 pPrevRect = &pReg->rects[prevStart];
1568 prevNumRects = curStart - prevStart;
1571 * Figure out how many rectangles are in the current band. Have to do
1572 * this because multiple bands could have been added in REGION_RegionOp
1573 * at the end when one region has been exhausted.
1575 pCurRect = &pReg->rects[curStart];
1576 bandtop = pCurRect->top;
1577 for (curNumRects = 0;
1578 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1579 curNumRects++)
1581 pCurRect++;
1584 if (pCurRect != pRegEnd)
1587 * If more than one band was added, we have to find the start
1588 * of the last band added so the next coalescing job can start
1589 * at the right place... (given when multiple bands are added,
1590 * this may be pointless -- see above).
1592 pRegEnd--;
1593 while (pRegEnd[-1].top == pRegEnd->top)
1595 pRegEnd--;
1597 curStart = pRegEnd - pReg->rects;
1598 pRegEnd = pReg->rects + pReg->numRects;
1601 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1602 pCurRect -= curNumRects;
1604 * The bands may only be coalesced if the bottom of the previous
1605 * matches the top scanline of the current.
1607 if (pPrevRect->bottom == pCurRect->top)
1610 * Make sure the bands have rects in the same places. This
1611 * assumes that rects have been added in such a way that they
1612 * cover the most area possible. I.e. two rects in a band must
1613 * have some horizontal space between them.
1617 if ((pPrevRect->left != pCurRect->left) ||
1618 (pPrevRect->right != pCurRect->right))
1621 * The bands don't line up so they can't be coalesced.
1623 return (curStart);
1625 pPrevRect++;
1626 pCurRect++;
1627 prevNumRects -= 1;
1628 } while (prevNumRects != 0);
1630 pReg->numRects -= curNumRects;
1631 pCurRect -= curNumRects;
1632 pPrevRect -= curNumRects;
1635 * The bands may be merged, so set the bottom of each rect
1636 * in the previous band to that of the corresponding rect in
1637 * the current band.
1641 pPrevRect->bottom = pCurRect->bottom;
1642 pPrevRect++;
1643 pCurRect++;
1644 curNumRects -= 1;
1645 } while (curNumRects != 0);
1648 * If only one band was added to the region, we have to backup
1649 * curStart to the start of the previous band.
1651 * If more than one band was added to the region, copy the
1652 * other bands down. The assumption here is that the other bands
1653 * came from the same region as the current one and no further
1654 * coalescing can be done on them since it's all been done
1655 * already... curStart is already in the right place.
1657 if (pCurRect == pRegEnd)
1659 curStart = prevStart;
1661 else
1665 *pPrevRect++ = *pCurRect++;
1666 } while (pCurRect != pRegEnd);
1671 return (curStart);
1674 /***********************************************************************
1675 * REGION_RegionOp
1677 * Apply an operation to two regions. Called by REGION_Union,
1678 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1680 * Results:
1681 * None.
1683 * Side Effects:
1684 * The new region is overwritten.
1686 * Notes:
1687 * The idea behind this function is to view the two regions as sets.
1688 * Together they cover a rectangle of area that this function divides
1689 * into horizontal bands where points are covered only by one region
1690 * or by both. For the first case, the nonOverlapFunc is called with
1691 * each the band and the band's upper and lower extents. For the
1692 * second, the overlapFunc is called to process the entire band. It
1693 * is responsible for clipping the rectangles in the band, though
1694 * this function provides the boundaries.
1695 * At the end of each band, the new region is coalesced, if possible,
1696 * to reduce the number of rectangles in the region.
1699 static BOOL REGION_RegionOp(
1700 WINEREGION *destReg, /* Place to store result */
1701 WINEREGION *reg1, /* First region in operation */
1702 WINEREGION *reg2, /* 2nd region in operation */
1703 BOOL (*overlapFunc)(WINEREGION*, RECT*, RECT*, RECT*, RECT*, INT, INT), /* Function to call for over-lapping bands */
1704 BOOL (*nonOverlap1Func)(WINEREGION*, RECT*, RECT*, INT, INT), /* Function to call for non-overlapping bands in region 1 */
1705 BOOL (*nonOverlap2Func)(WINEREGION*, RECT*, RECT*, INT, INT) /* Function to call for non-overlapping bands in region 2 */
1707 WINEREGION newReg;
1708 RECT *r1; /* Pointer into first region */
1709 RECT *r2; /* Pointer into 2d region */
1710 RECT *r1End; /* End of 1st region */
1711 RECT *r2End; /* End of 2d region */
1712 INT ybot; /* Bottom of intersection */
1713 INT ytop; /* Top of intersection */
1714 INT prevBand; /* Index of start of
1715 * previous band in newReg */
1716 INT curBand; /* Index of start of current
1717 * band in newReg */
1718 RECT *r1BandEnd; /* End of current band in r1 */
1719 RECT *r2BandEnd; /* End of current band in r2 */
1720 INT top; /* Top of non-overlapping band */
1721 INT bot; /* Bottom of non-overlapping band */
1724 * Initialization:
1725 * set r1, r2, r1End and r2End appropriately, preserve the important
1726 * parts of the destination region until the end in case it's one of
1727 * the two source regions, then mark the "new" region empty, allocating
1728 * another array of rectangles for it to use.
1730 r1 = reg1->rects;
1731 r2 = reg2->rects;
1732 r1End = r1 + reg1->numRects;
1733 r2End = r2 + reg2->numRects;
1736 * Allocate a reasonable number of rectangles for the new region. The idea
1737 * is to allocate enough so the individual functions don't need to
1738 * reallocate and copy the array, which is time consuming, yet we don't
1739 * have to worry about using too much memory. I hope to be able to
1740 * nuke the Xrealloc() at the end of this function eventually.
1742 if (!init_region( &newReg, max(reg1->numRects,reg2->numRects) * 2 )) return FALSE;
1745 * Initialize ybot and ytop.
1746 * In the upcoming loop, ybot and ytop serve different functions depending
1747 * on whether the band being handled is an overlapping or non-overlapping
1748 * band.
1749 * In the case of a non-overlapping band (only one of the regions
1750 * has points in the band), ybot is the bottom of the most recent
1751 * intersection and thus clips the top of the rectangles in that band.
1752 * ytop is the top of the next intersection between the two regions and
1753 * serves to clip the bottom of the rectangles in the current band.
1754 * For an overlapping band (where the two regions intersect), ytop clips
1755 * the top of the rectangles of both regions and ybot clips the bottoms.
1757 if (reg1->extents.top < reg2->extents.top)
1758 ybot = reg1->extents.top;
1759 else
1760 ybot = reg2->extents.top;
1763 * prevBand serves to mark the start of the previous band so rectangles
1764 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1765 * In the beginning, there is no previous band, so prevBand == curBand
1766 * (curBand is set later on, of course, but the first band will always
1767 * start at index 0). prevBand and curBand must be indices because of
1768 * the possible expansion, and resultant moving, of the new region's
1769 * array of rectangles.
1771 prevBand = 0;
1775 curBand = newReg.numRects;
1778 * This algorithm proceeds one source-band (as opposed to a
1779 * destination band, which is determined by where the two regions
1780 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1781 * rectangle after the last one in the current band for their
1782 * respective regions.
1784 r1BandEnd = r1;
1785 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1787 r1BandEnd++;
1790 r2BandEnd = r2;
1791 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1793 r2BandEnd++;
1797 * First handle the band that doesn't intersect, if any.
1799 * Note that attention is restricted to one band in the
1800 * non-intersecting region at once, so if a region has n
1801 * bands between the current position and the next place it overlaps
1802 * the other, this entire loop will be passed through n times.
1804 if (r1->top < r2->top)
1806 top = max(r1->top,ybot);
1807 bot = min(r1->bottom,r2->top);
1809 if ((top != bot) && (nonOverlap1Func != NULL))
1811 if (!nonOverlap1Func(&newReg, r1, r1BandEnd, top, bot)) return FALSE;
1814 ytop = r2->top;
1816 else if (r2->top < r1->top)
1818 top = max(r2->top,ybot);
1819 bot = min(r2->bottom,r1->top);
1821 if ((top != bot) && (nonOverlap2Func != NULL))
1823 if (!nonOverlap2Func(&newReg, r2, r2BandEnd, top, bot)) return FALSE;
1826 ytop = r1->top;
1828 else
1830 ytop = r1->top;
1834 * If any rectangles got added to the region, try and coalesce them
1835 * with rectangles from the previous band. Note we could just do
1836 * this test in miCoalesce, but some machines incur a not
1837 * inconsiderable cost for function calls, so...
1839 if (newReg.numRects != curBand)
1841 prevBand = REGION_Coalesce (&newReg, prevBand, curBand);
1845 * Now see if we've hit an intersecting band. The two bands only
1846 * intersect if ybot > ytop
1848 ybot = min(r1->bottom, r2->bottom);
1849 curBand = newReg.numRects;
1850 if (ybot > ytop)
1852 if (!overlapFunc(&newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot)) return FALSE;
1855 if (newReg.numRects != curBand)
1857 prevBand = REGION_Coalesce (&newReg, prevBand, curBand);
1861 * If we've finished with a band (bottom == ybot) we skip forward
1862 * in the region to the next band.
1864 if (r1->bottom == ybot)
1866 r1 = r1BandEnd;
1868 if (r2->bottom == ybot)
1870 r2 = r2BandEnd;
1872 } while ((r1 != r1End) && (r2 != r2End));
1875 * Deal with whichever region still has rectangles left.
1877 curBand = newReg.numRects;
1878 if (r1 != r1End)
1880 if (nonOverlap1Func != NULL)
1884 r1BandEnd = r1;
1885 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1887 r1BandEnd++;
1889 if (!nonOverlap1Func(&newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom))
1890 return FALSE;
1891 r1 = r1BandEnd;
1892 } while (r1 != r1End);
1895 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1899 r2BandEnd = r2;
1900 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1902 r2BandEnd++;
1904 if (!nonOverlap2Func(&newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom))
1905 return FALSE;
1906 r2 = r2BandEnd;
1907 } while (r2 != r2End);
1910 if (newReg.numRects != curBand)
1912 REGION_Coalesce (&newReg, prevBand, curBand);
1916 * A bit of cleanup. To keep regions from growing without bound,
1917 * we shrink the array of rectangles to match the new number of
1918 * rectangles in the region. This never goes to 0, however...
1920 * Only do this stuff if the number of rectangles allocated is more than
1921 * twice the number of rectangles in the region (a simple optimization...).
1923 if ((newReg.numRects < (newReg.size >> 1)) && (newReg.numRects > 2))
1925 RECT *new_rects = HeapReAlloc( GetProcessHeap(), 0, newReg.rects, newReg.numRects * sizeof(RECT) );
1926 if (new_rects)
1928 newReg.rects = new_rects;
1929 newReg.size = newReg.numRects;
1932 HeapFree( GetProcessHeap(), 0, destReg->rects );
1933 destReg->rects = newReg.rects;
1934 destReg->size = newReg.size;
1935 destReg->numRects = newReg.numRects;
1936 return TRUE;
1939 /***********************************************************************
1940 * Region Intersection
1941 ***********************************************************************/
1944 /***********************************************************************
1945 * REGION_IntersectO
1947 * Handle an overlapping band for REGION_Intersect.
1949 * Results:
1950 * None.
1952 * Side Effects:
1953 * Rectangles may be added to the region.
1956 static BOOL REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1957 RECT *r2, RECT *r2End, INT top, INT bottom)
1960 INT left, right;
1962 while ((r1 != r1End) && (r2 != r2End))
1964 left = max(r1->left, r2->left);
1965 right = min(r1->right, r2->right);
1968 * If there's any overlap between the two rectangles, add that
1969 * overlap to the new region.
1970 * There's no need to check for subsumption because the only way
1971 * such a need could arise is if some region has two rectangles
1972 * right next to each other. Since that should never happen...
1974 if (left < right)
1976 if (!add_rect( pReg, left, top, right, bottom )) return FALSE;
1980 * Need to advance the pointers. Shift the one that extends
1981 * to the right the least, since the other still has a chance to
1982 * overlap with that region's next rectangle, if you see what I mean.
1984 if (r1->right < r2->right)
1986 r1++;
1988 else if (r2->right < r1->right)
1990 r2++;
1992 else
1994 r1++;
1995 r2++;
1998 return TRUE;
2001 /***********************************************************************
2002 * REGION_IntersectRegion
2004 static BOOL REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
2005 WINEREGION *reg2)
2007 /* check for trivial reject */
2008 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
2009 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
2010 newReg->numRects = 0;
2011 else
2012 if (!REGION_RegionOp (newReg, reg1, reg2, REGION_IntersectO, NULL, NULL)) return FALSE;
2015 * Can't alter newReg's extents before we call miRegionOp because
2016 * it might be one of the source regions and miRegionOp depends
2017 * on the extents of those regions being the same. Besides, this
2018 * way there's no checking against rectangles that will be nuked
2019 * due to coalescing, so we have to examine fewer rectangles.
2021 REGION_SetExtents(newReg);
2022 return TRUE;
2025 /***********************************************************************
2026 * Region Union
2027 ***********************************************************************/
2029 /***********************************************************************
2030 * REGION_UnionNonO
2032 * Handle a non-overlapping band for the union operation. Just
2033 * Adds the rectangles into the region. Doesn't have to check for
2034 * subsumption or anything.
2036 * Results:
2037 * None.
2039 * Side Effects:
2040 * pReg->numRects is incremented and the final rectangles overwritten
2041 * with the rectangles we're passed.
2044 static BOOL REGION_UnionNonO(WINEREGION *pReg, RECT *r, RECT *rEnd, INT top, INT bottom)
2046 while (r != rEnd)
2048 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE;
2049 r++;
2051 return TRUE;
2054 /***********************************************************************
2055 * REGION_UnionO
2057 * Handle an overlapping band for the union operation. Picks the
2058 * left-most rectangle each time and merges it into the region.
2060 * Results:
2061 * None.
2063 * Side Effects:
2064 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2065 * be changed.
2068 static BOOL REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2069 RECT *r2, RECT *r2End, INT top, INT bottom)
2071 #define MERGERECT(r) \
2072 if ((pReg->numRects != 0) && \
2073 (pReg->rects[pReg->numRects-1].top == top) && \
2074 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
2075 (pReg->rects[pReg->numRects-1].right >= r->left)) \
2077 if (pReg->rects[pReg->numRects-1].right < r->right) \
2078 pReg->rects[pReg->numRects-1].right = r->right; \
2080 else \
2082 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
2084 r++;
2086 while ((r1 != r1End) && (r2 != r2End))
2088 if (r1->left < r2->left)
2090 MERGERECT(r1);
2092 else
2094 MERGERECT(r2);
2098 if (r1 != r1End)
2102 MERGERECT(r1);
2103 } while (r1 != r1End);
2105 else while (r2 != r2End)
2107 MERGERECT(r2);
2109 return TRUE;
2110 #undef MERGERECT
2113 /***********************************************************************
2114 * REGION_UnionRegion
2116 static BOOL REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1, WINEREGION *reg2)
2118 BOOL ret = TRUE;
2120 /* checks all the simple cases */
2123 * Region 1 and 2 are the same or region 1 is empty
2125 if ( (reg1 == reg2) || (!(reg1->numRects)) )
2127 if (newReg != reg2)
2128 ret = REGION_CopyRegion(newReg, reg2);
2129 return ret;
2133 * if nothing to union (region 2 empty)
2135 if (!(reg2->numRects))
2137 if (newReg != reg1)
2138 ret = REGION_CopyRegion(newReg, reg1);
2139 return ret;
2143 * Region 1 completely subsumes region 2
2145 if ((reg1->numRects == 1) &&
2146 (reg1->extents.left <= reg2->extents.left) &&
2147 (reg1->extents.top <= reg2->extents.top) &&
2148 (reg1->extents.right >= reg2->extents.right) &&
2149 (reg1->extents.bottom >= reg2->extents.bottom))
2151 if (newReg != reg1)
2152 ret = REGION_CopyRegion(newReg, reg1);
2153 return ret;
2157 * Region 2 completely subsumes region 1
2159 if ((reg2->numRects == 1) &&
2160 (reg2->extents.left <= reg1->extents.left) &&
2161 (reg2->extents.top <= reg1->extents.top) &&
2162 (reg2->extents.right >= reg1->extents.right) &&
2163 (reg2->extents.bottom >= reg1->extents.bottom))
2165 if (newReg != reg2)
2166 ret = REGION_CopyRegion(newReg, reg2);
2167 return ret;
2170 if ((ret = REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO, REGION_UnionNonO, REGION_UnionNonO)))
2172 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2173 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2174 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2175 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2177 return ret;
2180 /***********************************************************************
2181 * Region Subtraction
2182 ***********************************************************************/
2184 /***********************************************************************
2185 * REGION_SubtractNonO1
2187 * Deal with non-overlapping band for subtraction. Any parts from
2188 * region 2 we discard. Anything from region 1 we add to the region.
2190 * Results:
2191 * None.
2193 * Side Effects:
2194 * pReg may be affected.
2197 static BOOL REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd, INT top, INT bottom)
2199 while (r != rEnd)
2201 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE;
2202 r++;
2204 return TRUE;
2208 /***********************************************************************
2209 * REGION_SubtractO
2211 * Overlapping band subtraction. x1 is the left-most point not yet
2212 * checked.
2214 * Results:
2215 * None.
2217 * Side Effects:
2218 * pReg may have rectangles added to it.
2221 static BOOL REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2222 RECT *r2, RECT *r2End, INT top, INT bottom)
2224 INT left = r1->left;
2226 while ((r1 != r1End) && (r2 != r2End))
2228 if (r2->right <= left)
2231 * Subtrahend missed the boat: go to next subtrahend.
2233 r2++;
2235 else if (r2->left <= left)
2238 * Subtrahend precedes minuend: nuke left edge of minuend.
2240 left = r2->right;
2241 if (left >= r1->right)
2244 * Minuend completely covered: advance to next minuend and
2245 * reset left fence to edge of new minuend.
2247 r1++;
2248 if (r1 != r1End)
2249 left = r1->left;
2251 else
2254 * Subtrahend now used up since it doesn't extend beyond
2255 * minuend
2257 r2++;
2260 else if (r2->left < r1->right)
2263 * Left part of subtrahend covers part of minuend: add uncovered
2264 * part of minuend to region and skip to next subtrahend.
2266 if (!add_rect( pReg, left, top, r2->left, bottom )) return FALSE;
2267 left = r2->right;
2268 if (left >= r1->right)
2271 * Minuend used up: advance to new...
2273 r1++;
2274 if (r1 != r1End)
2275 left = r1->left;
2277 else
2280 * Subtrahend used up
2282 r2++;
2285 else
2288 * Minuend used up: add any remaining piece before advancing.
2290 if (r1->right > left)
2292 if (!add_rect( pReg, left, top, r1->right, bottom )) return FALSE;
2294 r1++;
2295 if (r1 != r1End)
2296 left = r1->left;
2301 * Add remaining minuend rectangles to region.
2303 while (r1 != r1End)
2305 if (!add_rect( pReg, left, top, r1->right, bottom )) return FALSE;
2306 r1++;
2307 if (r1 != r1End)
2309 left = r1->left;
2312 return TRUE;
2315 /***********************************************************************
2316 * REGION_SubtractRegion
2318 * Subtract regS from regM and leave the result in regD.
2319 * S stands for subtrahend, M for minuend and D for difference.
2321 * Results:
2322 * TRUE.
2324 * Side Effects:
2325 * regD is overwritten.
2328 static BOOL REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM, WINEREGION *regS )
2330 /* check for trivial reject */
2331 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2332 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2333 return REGION_CopyRegion(regD, regM);
2335 if (!REGION_RegionOp (regD, regM, regS, REGION_SubtractO, REGION_SubtractNonO1, NULL))
2336 return FALSE;
2339 * Can't alter newReg's extents before we call miRegionOp because
2340 * it might be one of the source regions and miRegionOp depends
2341 * on the extents of those regions being the unaltered. Besides, this
2342 * way there's no checking against rectangles that will be nuked
2343 * due to coalescing, so we have to examine fewer rectangles.
2345 REGION_SetExtents (regD);
2346 return TRUE;
2349 /***********************************************************************
2350 * REGION_XorRegion
2352 static BOOL REGION_XorRegion(WINEREGION *dr, WINEREGION *sra, WINEREGION *srb)
2354 WINEREGION tra, trb;
2355 BOOL ret;
2357 if (!init_region( &tra, sra->numRects + 1 )) return FALSE;
2358 if ((ret = init_region( &trb, srb->numRects + 1 )))
2360 ret = REGION_SubtractRegion(&tra,sra,srb) &&
2361 REGION_SubtractRegion(&trb,srb,sra) &&
2362 REGION_UnionRegion(dr,&tra,&trb);
2363 destroy_region(&trb);
2365 destroy_region(&tra);
2366 return ret;
2369 /**************************************************************************
2371 * Poly Regions
2373 *************************************************************************/
2375 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2376 #define SMALL_COORDINATE 0x80000000
2378 /***********************************************************************
2379 * REGION_InsertEdgeInET
2381 * Insert the given edge into the edge table.
2382 * First we must find the correct bucket in the
2383 * Edge table, then find the right slot in the
2384 * bucket. Finally, we can insert it.
2387 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2388 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2391 EdgeTableEntry *start, *prev;
2392 ScanLineList *pSLL, *pPrevSLL;
2393 ScanLineListBlock *tmpSLLBlock;
2396 * find the right bucket to put the edge into
2398 pPrevSLL = &ET->scanlines;
2399 pSLL = pPrevSLL->next;
2400 while (pSLL && (pSLL->scanline < scanline))
2402 pPrevSLL = pSLL;
2403 pSLL = pSLL->next;
2407 * reassign pSLL (pointer to ScanLineList) if necessary
2409 if ((!pSLL) || (pSLL->scanline > scanline))
2411 if (*iSLLBlock > SLLSPERBLOCK-1)
2413 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2414 if(!tmpSLLBlock)
2416 WARN("Can't alloc SLLB\n");
2417 return;
2419 (*SLLBlock)->next = tmpSLLBlock;
2420 tmpSLLBlock->next = NULL;
2421 *SLLBlock = tmpSLLBlock;
2422 *iSLLBlock = 0;
2424 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2426 pSLL->next = pPrevSLL->next;
2427 pSLL->edgelist = NULL;
2428 pPrevSLL->next = pSLL;
2430 pSLL->scanline = scanline;
2433 * now insert the edge in the right bucket
2435 prev = NULL;
2436 start = pSLL->edgelist;
2437 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2439 prev = start;
2440 start = start->next;
2442 ETE->next = start;
2444 if (prev)
2445 prev->next = ETE;
2446 else
2447 pSLL->edgelist = ETE;
2450 /***********************************************************************
2451 * REGION_CreateEdgeTable
2453 * This routine creates the edge table for
2454 * scan converting polygons.
2455 * The Edge Table (ET) looks like:
2457 * EdgeTable
2458 * --------
2459 * | ymax | ScanLineLists
2460 * |scanline|-->------------>-------------->...
2461 * -------- |scanline| |scanline|
2462 * |edgelist| |edgelist|
2463 * --------- ---------
2464 * | |
2465 * | |
2466 * V V
2467 * list of ETEs list of ETEs
2469 * where ETE is an EdgeTableEntry data structure,
2470 * and there is one ScanLineList per scanline at
2471 * which an edge is initially entered.
2474 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2475 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2476 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2478 const POINT *top, *bottom;
2479 const POINT *PrevPt, *CurrPt, *EndPt;
2480 INT poly, count;
2481 int iSLLBlock = 0;
2482 int dy;
2486 * initialize the Active Edge Table
2488 AET->next = NULL;
2489 AET->back = NULL;
2490 AET->nextWETE = NULL;
2491 AET->bres.minor_axis = SMALL_COORDINATE;
2494 * initialize the Edge Table.
2496 ET->scanlines.next = NULL;
2497 ET->ymax = SMALL_COORDINATE;
2498 ET->ymin = LARGE_COORDINATE;
2499 pSLLBlock->next = NULL;
2501 EndPt = pts - 1;
2502 for(poly = 0; poly < nbpolygons; poly++)
2504 count = Count[poly];
2505 EndPt += count;
2506 if(count < 2)
2507 continue;
2509 PrevPt = EndPt;
2512 * for each vertex in the array of points.
2513 * In this loop we are dealing with two vertices at
2514 * a time -- these make up one edge of the polygon.
2516 while (count--)
2518 CurrPt = pts++;
2521 * find out which point is above and which is below.
2523 if (PrevPt->y > CurrPt->y)
2525 bottom = PrevPt, top = CurrPt;
2526 pETEs->ClockWise = 0;
2528 else
2530 bottom = CurrPt, top = PrevPt;
2531 pETEs->ClockWise = 1;
2535 * don't add horizontal edges to the Edge table.
2537 if (bottom->y != top->y)
2539 pETEs->ymax = bottom->y-1;
2540 /* -1 so we don't get last scanline */
2543 * initialize integer edge algorithm
2545 dy = bottom->y - top->y;
2546 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2548 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2549 &iSLLBlock);
2551 if (PrevPt->y > ET->ymax)
2552 ET->ymax = PrevPt->y;
2553 if (PrevPt->y < ET->ymin)
2554 ET->ymin = PrevPt->y;
2555 pETEs++;
2558 PrevPt = CurrPt;
2563 /***********************************************************************
2564 * REGION_loadAET
2566 * This routine moves EdgeTableEntries from the
2567 * EdgeTable into the Active Edge Table,
2568 * leaving them sorted by smaller x coordinate.
2571 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2573 EdgeTableEntry *pPrevAET;
2574 EdgeTableEntry *tmp;
2576 pPrevAET = AET;
2577 AET = AET->next;
2578 while (ETEs)
2580 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2582 pPrevAET = AET;
2583 AET = AET->next;
2585 tmp = ETEs->next;
2586 ETEs->next = AET;
2587 if (AET)
2588 AET->back = ETEs;
2589 ETEs->back = pPrevAET;
2590 pPrevAET->next = ETEs;
2591 pPrevAET = ETEs;
2593 ETEs = tmp;
2597 /***********************************************************************
2598 * REGION_computeWAET
2600 * This routine links the AET by the
2601 * nextWETE (winding EdgeTableEntry) link for
2602 * use by the winding number rule. The final
2603 * Active Edge Table (AET) might look something
2604 * like:
2606 * AET
2607 * ---------- --------- ---------
2608 * |ymax | |ymax | |ymax |
2609 * | ... | |... | |... |
2610 * |next |->|next |->|next |->...
2611 * |nextWETE| |nextWETE| |nextWETE|
2612 * --------- --------- ^--------
2613 * | | |
2614 * V-------------------> V---> ...
2617 static void REGION_computeWAET(EdgeTableEntry *AET)
2619 register EdgeTableEntry *pWETE;
2620 register int inside = 1;
2621 register int isInside = 0;
2623 AET->nextWETE = NULL;
2624 pWETE = AET;
2625 AET = AET->next;
2626 while (AET)
2628 if (AET->ClockWise)
2629 isInside++;
2630 else
2631 isInside--;
2633 if ((!inside && !isInside) ||
2634 ( inside && isInside))
2636 pWETE->nextWETE = AET;
2637 pWETE = AET;
2638 inside = !inside;
2640 AET = AET->next;
2642 pWETE->nextWETE = NULL;
2645 /***********************************************************************
2646 * REGION_InsertionSort
2648 * Just a simple insertion sort using
2649 * pointers and back pointers to sort the Active
2650 * Edge Table.
2653 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2655 EdgeTableEntry *pETEchase;
2656 EdgeTableEntry *pETEinsert;
2657 EdgeTableEntry *pETEchaseBackTMP;
2658 BOOL changed = FALSE;
2660 AET = AET->next;
2661 while (AET)
2663 pETEinsert = AET;
2664 pETEchase = AET;
2665 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2666 pETEchase = pETEchase->back;
2668 AET = AET->next;
2669 if (pETEchase != pETEinsert)
2671 pETEchaseBackTMP = pETEchase->back;
2672 pETEinsert->back->next = AET;
2673 if (AET)
2674 AET->back = pETEinsert->back;
2675 pETEinsert->next = pETEchase;
2676 pETEchase->back->next = pETEinsert;
2677 pETEchase->back = pETEinsert;
2678 pETEinsert->back = pETEchaseBackTMP;
2679 changed = TRUE;
2682 return changed;
2685 /***********************************************************************
2686 * REGION_FreeStorage
2688 * Clean up our act.
2690 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2692 ScanLineListBlock *tmpSLLBlock;
2694 while (pSLLBlock)
2696 tmpSLLBlock = pSLLBlock->next;
2697 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2698 pSLLBlock = tmpSLLBlock;
2703 /***********************************************************************
2704 * REGION_PtsToRegion
2706 * Create an array of rectangles from a list of points.
2708 static BOOL REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2709 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2711 RECT *rects;
2712 POINT *pts;
2713 POINTBLOCK *CurPtBlock;
2714 int i;
2715 RECT *extents;
2716 INT numRects;
2718 extents = &reg->extents;
2720 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2721 if (!init_region( reg, numRects )) return FALSE;
2723 reg->size = numRects;
2724 CurPtBlock = FirstPtBlock;
2725 rects = reg->rects - 1;
2726 numRects = 0;
2727 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2729 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2730 /* the loop uses 2 points per iteration */
2731 i = NUMPTSTOBUFFER >> 1;
2732 if (!numFullPtBlocks)
2733 i = iCurPtBlock >> 1;
2734 for (pts = CurPtBlock->pts; i--; pts += 2) {
2735 if (pts->x == pts[1].x)
2736 continue;
2737 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2738 pts[1].x == rects->right &&
2739 (numRects == 1 || rects[-1].top != rects->top) &&
2740 (i && pts[2].y > pts[1].y)) {
2741 rects->bottom = pts[1].y + 1;
2742 continue;
2744 numRects++;
2745 rects++;
2746 rects->left = pts->x; rects->top = pts->y;
2747 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2748 if (rects->left < extents->left)
2749 extents->left = rects->left;
2750 if (rects->right > extents->right)
2751 extents->right = rects->right;
2753 CurPtBlock = CurPtBlock->next;
2756 if (numRects) {
2757 extents->top = reg->rects->top;
2758 extents->bottom = rects->bottom;
2759 } else {
2760 extents->left = 0;
2761 extents->top = 0;
2762 extents->right = 0;
2763 extents->bottom = 0;
2765 reg->numRects = numRects;
2767 return(TRUE);
2770 /***********************************************************************
2771 * CreatePolyPolygonRgn (GDI32.@)
2773 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2774 INT nbpolygons, INT mode)
2776 HRGN hrgn = 0;
2777 RGNOBJ *obj;
2778 EdgeTableEntry *pAET; /* Active Edge Table */
2779 INT y; /* current scanline */
2780 int iPts = 0; /* number of pts in buffer */
2781 EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2782 ScanLineList *pSLL; /* current scanLineList */
2783 POINT *pts; /* output buffer */
2784 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2785 EdgeTable ET; /* header node for ET */
2786 EdgeTableEntry AET; /* header node for AET */
2787 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2788 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2789 int fixWAET = FALSE;
2790 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2791 POINTBLOCK *tmpPtBlock;
2792 int numFullPtBlocks = 0;
2793 INT poly, total;
2795 TRACE("%p, count %d, polygons %d, mode %d\n", Pts, *Count, nbpolygons, mode);
2797 /* special case a rectangle */
2799 if (((nbpolygons == 1) && ((*Count == 4) ||
2800 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2801 (((Pts[0].y == Pts[1].y) &&
2802 (Pts[1].x == Pts[2].x) &&
2803 (Pts[2].y == Pts[3].y) &&
2804 (Pts[3].x == Pts[0].x)) ||
2805 ((Pts[0].x == Pts[1].x) &&
2806 (Pts[1].y == Pts[2].y) &&
2807 (Pts[2].x == Pts[3].x) &&
2808 (Pts[3].y == Pts[0].y))))
2809 return CreateRectRgn( min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2810 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2812 for(poly = total = 0; poly < nbpolygons; poly++)
2813 total += Count[poly];
2814 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2815 return 0;
2817 pts = FirstPtBlock.pts;
2818 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2819 pSLL = ET.scanlines.next;
2820 curPtBlock = &FirstPtBlock;
2822 if (mode != WINDING) {
2824 * for each scanline
2826 for (y = ET.ymin; y < ET.ymax; y++) {
2828 * Add a new edge to the active edge table when we
2829 * get to the next edge.
2831 if (pSLL != NULL && y == pSLL->scanline) {
2832 REGION_loadAET(&AET, pSLL->edgelist);
2833 pSLL = pSLL->next;
2835 pPrevAET = &AET;
2836 pAET = AET.next;
2839 * for each active edge
2841 while (pAET) {
2842 pts->x = pAET->bres.minor_axis, pts->y = y;
2843 pts++, iPts++;
2846 * send out the buffer
2848 if (iPts == NUMPTSTOBUFFER) {
2849 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2850 if(!tmpPtBlock) goto done;
2851 curPtBlock->next = tmpPtBlock;
2852 curPtBlock = tmpPtBlock;
2853 pts = curPtBlock->pts;
2854 numFullPtBlocks++;
2855 iPts = 0;
2857 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2859 REGION_InsertionSort(&AET);
2862 else {
2864 * for each scanline
2866 for (y = ET.ymin; y < ET.ymax; y++) {
2868 * Add a new edge to the active edge table when we
2869 * get to the next edge.
2871 if (pSLL != NULL && y == pSLL->scanline) {
2872 REGION_loadAET(&AET, pSLL->edgelist);
2873 REGION_computeWAET(&AET);
2874 pSLL = pSLL->next;
2876 pPrevAET = &AET;
2877 pAET = AET.next;
2878 pWETE = pAET;
2881 * for each active edge
2883 while (pAET) {
2885 * add to the buffer only those edges that
2886 * are in the Winding active edge table.
2888 if (pWETE == pAET) {
2889 pts->x = pAET->bres.minor_axis, pts->y = y;
2890 pts++, iPts++;
2893 * send out the buffer
2895 if (iPts == NUMPTSTOBUFFER) {
2896 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2897 sizeof(POINTBLOCK) );
2898 if(!tmpPtBlock) goto done;
2899 curPtBlock->next = tmpPtBlock;
2900 curPtBlock = tmpPtBlock;
2901 pts = curPtBlock->pts;
2902 numFullPtBlocks++;
2903 iPts = 0;
2905 pWETE = pWETE->nextWETE;
2907 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2911 * recompute the winding active edge table if
2912 * we just resorted or have exited an edge.
2914 if (REGION_InsertionSort(&AET) || fixWAET) {
2915 REGION_computeWAET(&AET);
2916 fixWAET = FALSE;
2921 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) goto done;
2923 if (!REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, &obj->rgn))
2925 HeapFree( GetProcessHeap(), 0, obj );
2926 goto done;
2928 if (!(hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs )))
2930 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
2931 HeapFree( GetProcessHeap(), 0, obj );
2934 done:
2935 REGION_FreeStorage(SLLBlock.next);
2936 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2937 tmpPtBlock = curPtBlock->next;
2938 HeapFree( GetProcessHeap(), 0, curPtBlock );
2939 curPtBlock = tmpPtBlock;
2941 HeapFree( GetProcessHeap(), 0, pETEs );
2942 return hrgn;
2946 /***********************************************************************
2947 * CreatePolygonRgn (GDI32.@)
2949 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2950 INT mode )
2952 return CreatePolyPolygonRgn( points, &count, 1, mode );