wined3d: read_from_framebuffer_texture() isn't suitable for readback of onscreen...
[wine/testsucceed.git] / dlls / gdi32 / region.c
blobd6dec1f7687fa90c6a7503136811ceaab6b337b4
1 /*
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
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 typedef struct {
109 INT size;
110 INT numRects;
111 RECT *rects;
112 RECT extents;
113 } WINEREGION;
115 /* GDI logical region object */
116 typedef struct
118 GDIOBJHDR header;
119 WINEREGION rgn;
120 } RGNOBJ;
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 static BOOL add_rect( WINEREGION *reg, INT left, INT top, INT right, INT bottom )
147 RECT *rect;
148 if (reg->numRects >= reg->size)
150 RECT *newrects = HeapReAlloc( GetProcessHeap(), 0, reg->rects, 2 * sizeof(RECT) * reg->size );
151 if (!newrects) return FALSE;
152 reg->rects = newrects;
153 reg->size *= 2;
155 rect = reg->rects + reg->numRects++;
156 rect->left = left;
157 rect->top = top;
158 rect->right = right;
159 rect->bottom = bottom;
160 return TRUE;
163 #define EMPTY_REGION(pReg) do { \
164 (pReg)->numRects = 0; \
165 (pReg)->extents.left = (pReg)->extents.top = 0; \
166 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
167 } while(0)
169 #define INRECT(r, x, y) \
170 ( ( ((r).right > x)) && \
171 ( ((r).left <= x)) && \
172 ( ((r).bottom > y)) && \
173 ( ((r).top <= 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;
190 } POINTBLOCK;
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
200 * major axis.
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 */ \
232 /* \
233 * if the edge is horizontal, then it is ignored \
234 * and assumed not to be processed. Otherwise, do this stuff. \
235 */ \
236 if ((dy) != 0) { \
237 xStart = (x1); \
238 dx = (x2) - xStart; \
239 if (dx < 0) { \
240 m = dx / (dy); \
241 m1 = m - 1; \
242 incr1 = -2 * dx + 2 * (dy) * m1; \
243 incr2 = -2 * dx + 2 * (dy) * m; \
244 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
245 } else { \
246 m = dx / (dy); \
247 m1 = m + 1; \
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) { \
256 if (m1 > 0) { \
257 if (d > 0) { \
258 minval += m1; \
259 d += incr1; \
261 else { \
262 minval += m; \
263 d += incr2; \
265 } else {\
266 if (d >= 0) { \
267 minval += m1; \
268 d += incr1; \
270 else { \
271 minval += m; \
272 d += 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.
284 typedef struct {
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 */
289 } BRESINFO;
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
309 * path segments.
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
314 * segments.
316 * These data structures are adapted somewhat from
317 * the algorithm in (Foley/Van Dam) for scan converting
318 * polygons.
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
337 * (Foley/Van Dam).
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
350 #define CLOCKWISE 1
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 */
360 } EdgeTableEntry;
363 typedef struct _ScanLineList{
364 INT scanline; /* the scanline represented */
365 EdgeTableEntry *edgelist; /* header node */
366 struct _ScanLineList *next; /* next in the list */
367 } ScanLineList;
370 typedef struct {
371 INT ymax; /* ymax for the polygon */
372 INT ymin; /* ymin for the polygon */
373 ScanLineList scanlines; /* header node */
374 } EdgeTable;
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;
387 } ScanLineListBlock;
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; \
407 fixWAET = 1; \
408 if (pAET) \
409 pAET->back = pPrevAET; \
411 else { \
412 BRESINCRPGONSTRUCT(pAET->bres); \
413 pPrevAET = pAET; \
414 pAET = pAET->next; \
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; \
430 if (pAET) \
431 pAET->back = pPrevAET; \
433 else { \
434 BRESINCRPGONSTRUCT(pAET->bres); \
435 pPrevAET = pAET; \
436 pAET = pAET->next; \
440 /* Note the parameter order is different from the X11 equivalents */
442 static BOOL REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
443 static BOOL REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
444 static BOOL REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
445 static BOOL REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
446 static BOOL REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
447 static BOOL REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static BOOL REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
450 #define RGN_DEFAULT_RECTS 2
453 /***********************************************************************
454 * get_region_type
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 /***********************************************************************
468 * REGION_DumpRegion
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);
481 return;
485 /***********************************************************************
486 * init_region
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;
493 pReg->size = n;
494 EMPTY_REGION(pReg);
495 return TRUE;
498 /***********************************************************************
499 * destroy_region
501 static void destroy_region( WINEREGION *pReg )
503 HeapFree( GetProcessHeap(), 0, pReg->rects );
506 /***********************************************************************
507 * REGION_DeleteObject
509 static BOOL REGION_DeleteObject( HGDIOBJ handle )
511 RGNOBJ *rgn = free_gdi_handle( handle );
513 if (!rgn) return FALSE;
514 HeapFree( GetProcessHeap(), 0, rgn->rgn.rects );
515 HeapFree( GetProcessHeap(), 0, rgn );
516 return TRUE;
519 /***********************************************************************
520 * REGION_SelectObject
522 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
524 return ULongToHandle(SelectClipRgn( hdc, handle ));
528 /***********************************************************************
529 * REGION_OffsetRegion
530 * Offset a WINEREGION by x,y
532 static BOOL REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn, INT x, INT y )
534 if( rgn != srcrgn)
536 if (!REGION_CopyRegion( rgn, srcrgn)) return FALSE;
538 if(x || y) {
539 int nbox = rgn->numRects;
540 RECT *pbox = rgn->rects;
542 if(nbox) {
543 while(nbox--) {
544 pbox->left += x;
545 pbox->right += x;
546 pbox->top += y;
547 pbox->bottom += y;
548 pbox++;
550 rgn->extents.left += x;
551 rgn->extents.right += x;
552 rgn->extents.top += y;
553 rgn->extents.bottom += y;
556 return TRUE;
559 /***********************************************************************
560 * OffsetRgn (GDI32.@)
562 * Moves a region by the specified X- and Y-axis offsets.
564 * PARAMS
565 * hrgn [I] Region to offset.
566 * x [I] Offset right if positive or left if negative.
567 * y [I] Offset down if positive or up if negative.
569 * RETURNS
570 * Success:
571 * NULLREGION - The new region is empty.
572 * SIMPLEREGION - The new region can be represented by one rectangle.
573 * COMPLEXREGION - The new region can only be represented by more than
574 * one rectangle.
575 * Failure: ERROR
577 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
579 RGNOBJ * obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
580 INT ret;
582 TRACE("%p %d,%d\n", hrgn, x, y);
584 if (!obj)
585 return ERROR;
587 REGION_OffsetRegion( &obj->rgn, &obj->rgn, x, y);
589 ret = get_region_type( obj );
590 GDI_ReleaseObj( hrgn );
591 return ret;
595 /***********************************************************************
596 * GetRgnBox (GDI32.@)
598 * Retrieves the bounding rectangle of the region. The bounding rectangle
599 * is the smallest rectangle that contains the entire region.
601 * PARAMS
602 * hrgn [I] Region to retrieve bounding rectangle from.
603 * rect [O] Rectangle that will receive the coordinates of the bounding
604 * rectangle.
606 * RETURNS
607 * NULLREGION - The new region is empty.
608 * SIMPLEREGION - The new region can be represented by one rectangle.
609 * COMPLEXREGION - The new region can only be represented by more than
610 * one rectangle.
612 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
614 RGNOBJ * obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
615 if (obj)
617 INT ret;
618 rect->left = obj->rgn.extents.left;
619 rect->top = obj->rgn.extents.top;
620 rect->right = obj->rgn.extents.right;
621 rect->bottom = obj->rgn.extents.bottom;
622 TRACE("%p (%d,%d-%d,%d)\n", hrgn,
623 rect->left, rect->top, rect->right, rect->bottom);
624 ret = get_region_type( obj );
625 GDI_ReleaseObj(hrgn);
626 return ret;
628 return ERROR;
632 /***********************************************************************
633 * CreateRectRgn (GDI32.@)
635 * Creates a simple rectangular region.
637 * PARAMS
638 * left [I] Left coordinate of rectangle.
639 * top [I] Top coordinate of rectangle.
640 * right [I] Right coordinate of rectangle.
641 * bottom [I] Bottom coordinate of rectangle.
643 * RETURNS
644 * Success: Handle to region.
645 * Failure: NULL.
647 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
649 HRGN hrgn;
650 RGNOBJ *obj;
652 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
654 /* Allocate 2 rects by default to reduce the number of reallocs */
655 if (!init_region( &obj->rgn, RGN_DEFAULT_RECTS ))
657 HeapFree( GetProcessHeap(), 0, obj );
658 return 0;
660 if (!(hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs )))
662 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
663 HeapFree( GetProcessHeap(), 0, obj );
664 return 0;
666 TRACE( "%d,%d-%d,%d returning %p\n", left, top, right, bottom, hrgn );
667 SetRectRgn(hrgn, left, top, right, bottom);
668 return hrgn;
672 /***********************************************************************
673 * CreateRectRgnIndirect (GDI32.@)
675 * Creates a simple rectangular region.
677 * PARAMS
678 * rect [I] Coordinates of rectangular region.
680 * RETURNS
681 * Success: Handle to region.
682 * Failure: NULL.
684 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
686 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
690 /***********************************************************************
691 * SetRectRgn (GDI32.@)
693 * Sets a region to a simple rectangular region.
695 * PARAMS
696 * hrgn [I] Region to convert.
697 * left [I] Left coordinate of rectangle.
698 * top [I] Top coordinate of rectangle.
699 * right [I] Right coordinate of rectangle.
700 * bottom [I] Bottom coordinate of rectangle.
702 * RETURNS
703 * Success: Non-zero.
704 * Failure: Zero.
706 * NOTES
707 * Allows either or both left and top to be greater than right or bottom.
709 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
710 INT right, INT bottom )
712 RGNOBJ * obj;
714 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
716 if (!(obj = GDI_GetObjPtr( hrgn, OBJ_REGION ))) return FALSE;
718 if (left > right) { INT tmp = left; left = right; right = tmp; }
719 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
721 if((left != right) && (top != bottom))
723 obj->rgn.rects->left = obj->rgn.extents.left = left;
724 obj->rgn.rects->top = obj->rgn.extents.top = top;
725 obj->rgn.rects->right = obj->rgn.extents.right = right;
726 obj->rgn.rects->bottom = obj->rgn.extents.bottom = bottom;
727 obj->rgn.numRects = 1;
729 else
730 EMPTY_REGION(&obj->rgn);
732 GDI_ReleaseObj( hrgn );
733 return TRUE;
737 /***********************************************************************
738 * CreateRoundRectRgn (GDI32.@)
740 * Creates a rectangular region with rounded corners.
742 * PARAMS
743 * left [I] Left coordinate of rectangle.
744 * top [I] Top coordinate of rectangle.
745 * right [I] Right coordinate of rectangle.
746 * bottom [I] Bottom coordinate of rectangle.
747 * ellipse_width [I] Width of the ellipse at each corner.
748 * ellipse_height [I] Height of the ellipse at each corner.
750 * RETURNS
751 * Success: Handle to region.
752 * Failure: NULL.
754 * NOTES
755 * If ellipse_width or ellipse_height is less than 2 logical units then
756 * it is treated as though CreateRectRgn() was called instead.
758 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
759 INT right, INT bottom,
760 INT ellipse_width, INT ellipse_height )
762 RGNOBJ * obj;
763 HRGN hrgn = 0;
764 int asq, bsq, d, xd, yd;
765 RECT rect;
767 /* Make the dimensions sensible */
769 if (left > right) { INT tmp = left; left = right; right = tmp; }
770 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
772 ellipse_width = abs(ellipse_width);
773 ellipse_height = abs(ellipse_height);
775 /* Check parameters */
777 if (ellipse_width > right-left) ellipse_width = right-left;
778 if (ellipse_height > bottom-top) ellipse_height = bottom-top;
780 /* Check if we can do a normal rectangle instead */
782 if ((ellipse_width < 2) || (ellipse_height < 2))
783 return CreateRectRgn( left, top, right, bottom );
785 /* Create region */
787 d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
788 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
789 if (!init_region( &obj->rgn, d ))
791 HeapFree( GetProcessHeap(), 0, obj );
792 return 0;
795 /* Ellipse algorithm, based on an article by K. Porter */
796 /* in DDJ Graphics Programming Column, 8/89 */
798 asq = ellipse_width * ellipse_width / 4; /* a^2 */
799 bsq = ellipse_height * ellipse_height / 4; /* b^2 */
800 d = bsq - asq * ellipse_height / 2 + asq / 4; /* b^2 - a^2b + a^2/4 */
801 xd = 0;
802 yd = asq * ellipse_height; /* 2a^2b */
804 rect.left = left + ellipse_width / 2;
805 rect.right = right - ellipse_width / 2;
807 /* Loop to draw first half of quadrant */
809 while (xd < yd)
811 if (d > 0) /* if nearest pixel is toward the center */
813 /* move toward center */
814 rect.top = top++;
815 rect.bottom = rect.top + 1;
816 if (!REGION_UnionRectWithRegion( &rect, &obj->rgn )) goto done;
817 rect.top = --bottom;
818 rect.bottom = rect.top + 1;
819 if (!REGION_UnionRectWithRegion( &rect, &obj->rgn )) goto done;
820 yd -= 2*asq;
821 d -= yd;
823 rect.left--; /* next horiz point */
824 rect.right++;
825 xd += 2*bsq;
826 d += bsq + xd;
829 /* Loop to draw second half of quadrant */
831 d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
832 while (yd >= 0)
834 /* next vertical point */
835 rect.top = top++;
836 rect.bottom = rect.top + 1;
837 if (!REGION_UnionRectWithRegion( &rect, &obj->rgn )) goto done;
838 rect.top = --bottom;
839 rect.bottom = rect.top + 1;
840 if (!REGION_UnionRectWithRegion( &rect, &obj->rgn )) goto done;
841 if (d < 0) /* if nearest pixel is outside ellipse */
843 rect.left--; /* move away from center */
844 rect.right++;
845 xd += 2*bsq;
846 d += xd;
848 yd -= 2*asq;
849 d += asq - yd;
852 /* Add the inside rectangle */
854 if (top <= bottom)
856 rect.top = top;
857 rect.bottom = bottom;
858 if (!REGION_UnionRectWithRegion( &rect, &obj->rgn )) goto done;
861 hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs );
863 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
864 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
865 done:
866 if (!hrgn)
868 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
869 HeapFree( GetProcessHeap(), 0, obj );
871 return hrgn;
875 /***********************************************************************
876 * CreateEllipticRgn (GDI32.@)
878 * Creates an elliptical region.
880 * PARAMS
881 * left [I] Left coordinate of bounding rectangle.
882 * top [I] Top coordinate of bounding rectangle.
883 * right [I] Right coordinate of bounding rectangle.
884 * bottom [I] Bottom coordinate of bounding rectangle.
886 * RETURNS
887 * Success: Handle to region.
888 * Failure: NULL.
890 * NOTES
891 * This is a special case of CreateRoundRectRgn() where the width of the
892 * ellipse at each corner is equal to the width the rectangle and
893 * the same for the height.
895 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
896 INT right, INT bottom )
898 return CreateRoundRectRgn( left, top, right, bottom,
899 right-left, bottom-top );
903 /***********************************************************************
904 * CreateEllipticRgnIndirect (GDI32.@)
906 * Creates an elliptical region.
908 * PARAMS
909 * rect [I] Pointer to bounding rectangle of the ellipse.
911 * RETURNS
912 * Success: Handle to region.
913 * Failure: NULL.
915 * NOTES
916 * This is a special case of CreateRoundRectRgn() where the width of the
917 * ellipse at each corner is equal to the width the rectangle and
918 * the same for the height.
920 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
922 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
923 rect->bottom, rect->right - rect->left,
924 rect->bottom - rect->top );
927 /***********************************************************************
928 * GetRegionData (GDI32.@)
930 * Retrieves the data that specifies the region.
932 * PARAMS
933 * hrgn [I] Region to retrieve the region data from.
934 * count [I] The size of the buffer pointed to by rgndata in bytes.
935 * rgndata [I] The buffer to receive data about the region.
937 * RETURNS
938 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
939 * the number of bytes copied to the output buffer.
940 * Failure: 0.
942 * NOTES
943 * The format of the Buffer member of RGNDATA is determined by the iType
944 * member of the region data header.
945 * Currently this is always RDH_RECTANGLES, which specifies that the format
946 * is the array of RECT's that specify the region. The length of the array
947 * is specified by the nCount member of the region data header.
949 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
951 DWORD size;
952 RGNOBJ *obj = GDI_GetObjPtr( hrgn, OBJ_REGION );
954 TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
956 if(!obj) return 0;
958 size = obj->rgn.numRects * sizeof(RECT);
959 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
961 GDI_ReleaseObj( hrgn );
962 if (rgndata) /* buffer is too small, signal it by return 0 */
963 return 0;
964 else /* user requested buffer size with rgndata NULL */
965 return size + sizeof(RGNDATAHEADER);
968 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
969 rgndata->rdh.iType = RDH_RECTANGLES;
970 rgndata->rdh.nCount = obj->rgn.numRects;
971 rgndata->rdh.nRgnSize = size;
972 rgndata->rdh.rcBound.left = obj->rgn.extents.left;
973 rgndata->rdh.rcBound.top = obj->rgn.extents.top;
974 rgndata->rdh.rcBound.right = obj->rgn.extents.right;
975 rgndata->rdh.rcBound.bottom = obj->rgn.extents.bottom;
977 memcpy( rgndata->Buffer, obj->rgn.rects, size );
979 GDI_ReleaseObj( hrgn );
980 return size + sizeof(RGNDATAHEADER);
984 static void translate( POINT *pt, UINT count, const XFORM *xform )
986 while (count--)
988 double x = pt->x;
989 double y = pt->y;
990 pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
991 pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
992 pt++;
997 /***********************************************************************
998 * ExtCreateRegion (GDI32.@)
1000 * Creates a region as specified by the transformation data and region data.
1002 * PARAMS
1003 * lpXform [I] World-space to logical-space transformation data.
1004 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
1005 * rgndata [I] Data that specifies the region.
1007 * RETURNS
1008 * Success: Handle to region.
1009 * Failure: NULL.
1011 * NOTES
1012 * See GetRegionData().
1014 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
1016 HRGN hrgn = 0;
1017 RGNOBJ *obj;
1019 if (!rgndata)
1021 SetLastError( ERROR_INVALID_PARAMETER );
1022 return 0;
1025 if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
1026 return 0;
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);
1032 if (lpXform)
1034 const RECT *pCurRect, *pEndRect;
1036 hrgn = CreateRectRgn( 0, 0, 0, 0 );
1038 pEndRect = (const RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1039 for (pCurRect = (const RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1041 static const INT count = 4;
1042 HRGN poly_hrgn;
1043 POINT pt[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 );
1059 return hrgn;
1062 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) return 0;
1064 if (init_region( &obj->rgn, rgndata->rdh.nCount ))
1066 const RECT *pCurRect, *pEndRect;
1068 pEndRect = (const RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1069 for(pCurRect = (const RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1071 if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
1073 if (!REGION_UnionRectWithRegion( pCurRect, &obj->rgn )) goto done;
1076 hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs );
1078 else
1080 HeapFree( GetProcessHeap(), 0, obj );
1081 return 0;
1084 done:
1085 if (!hrgn)
1087 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
1088 HeapFree( GetProcessHeap(), 0, obj );
1090 TRACE("%p %d %p returning %p\n", lpXform, dwCount, rgndata, hrgn );
1091 return hrgn;
1095 /***********************************************************************
1096 * PtInRegion (GDI32.@)
1098 * Tests whether the specified point is inside a region.
1100 * PARAMS
1101 * hrgn [I] Region to test.
1102 * x [I] X-coordinate of point to test.
1103 * y [I] Y-coordinate of point to test.
1105 * RETURNS
1106 * Non-zero if the point is inside the region or zero otherwise.
1108 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
1110 RGNOBJ * obj;
1111 BOOL ret = FALSE;
1113 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1115 int i;
1117 if (obj->rgn.numRects > 0 && INRECT(obj->rgn.extents, x, y))
1118 for (i = 0; i < obj->rgn.numRects; i++)
1119 if (INRECT (obj->rgn.rects[i], x, y))
1121 ret = TRUE;
1122 break;
1124 GDI_ReleaseObj( hrgn );
1126 return ret;
1130 /***********************************************************************
1131 * RectInRegion (GDI32.@)
1133 * Tests if a rectangle is at least partly inside the specified region.
1135 * PARAMS
1136 * hrgn [I] Region to test.
1137 * rect [I] Rectangle to test.
1139 * RETURNS
1140 * Non-zero if the rectangle is partially inside the region or
1141 * zero otherwise.
1143 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
1145 RGNOBJ * obj;
1146 BOOL ret = FALSE;
1147 RECT rc;
1149 /* swap the coordinates to make right >= left and bottom >= top */
1150 /* (region building rectangles are normalized the same way) */
1151 if( rect->top > rect->bottom) {
1152 rc.top = rect->bottom;
1153 rc.bottom = rect->top;
1154 } else {
1155 rc.top = rect->top;
1156 rc.bottom = rect->bottom;
1158 if( rect->right < rect->left) {
1159 rc.right = rect->left;
1160 rc.left = rect->right;
1161 } else {
1162 rc.right = rect->right;
1163 rc.left = rect->left;
1166 if ((obj = GDI_GetObjPtr( hrgn, OBJ_REGION )))
1168 RECT *pCurRect, *pRectEnd;
1170 /* this is (just) a useful optimization */
1171 if ((obj->rgn.numRects > 0) && EXTENTCHECK(&obj->rgn.extents, &rc))
1173 for (pCurRect = obj->rgn.rects, pRectEnd = pCurRect +
1174 obj->rgn.numRects; pCurRect < pRectEnd; pCurRect++)
1176 if (pCurRect->bottom <= rc.top)
1177 continue; /* not far enough down yet */
1179 if (pCurRect->top >= rc.bottom)
1180 break; /* too far down */
1182 if (pCurRect->right <= rc.left)
1183 continue; /* not far enough over yet */
1185 if (pCurRect->left >= rc.right) {
1186 continue;
1189 ret = TRUE;
1190 break;
1193 GDI_ReleaseObj(hrgn);
1195 return ret;
1198 /***********************************************************************
1199 * EqualRgn (GDI32.@)
1201 * Tests whether one region is identical to another.
1203 * PARAMS
1204 * hrgn1 [I] The first region to compare.
1205 * hrgn2 [I] The second region to compare.
1207 * RETURNS
1208 * Non-zero if both regions are identical or zero otherwise.
1210 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1212 RGNOBJ *obj1, *obj2;
1213 BOOL ret = FALSE;
1215 if ((obj1 = GDI_GetObjPtr( hrgn1, OBJ_REGION )))
1217 if ((obj2 = GDI_GetObjPtr( hrgn2, OBJ_REGION )))
1219 int i;
1221 if ( obj1->rgn.numRects != obj2->rgn.numRects ) goto done;
1222 if ( obj1->rgn.numRects == 0 )
1224 ret = TRUE;
1225 goto done;
1228 if (obj1->rgn.extents.left != obj2->rgn.extents.left) goto done;
1229 if (obj1->rgn.extents.right != obj2->rgn.extents.right) goto done;
1230 if (obj1->rgn.extents.top != obj2->rgn.extents.top) goto done;
1231 if (obj1->rgn.extents.bottom != obj2->rgn.extents.bottom) goto done;
1232 for( i = 0; i < obj1->rgn.numRects; i++ )
1234 if (obj1->rgn.rects[i].left != obj2->rgn.rects[i].left) goto done;
1235 if (obj1->rgn.rects[i].right != obj2->rgn.rects[i].right) goto done;
1236 if (obj1->rgn.rects[i].top != obj2->rgn.rects[i].top) goto done;
1237 if (obj1->rgn.rects[i].bottom != obj2->rgn.rects[i].bottom) goto done;
1239 ret = TRUE;
1240 done:
1241 GDI_ReleaseObj(hrgn2);
1243 GDI_ReleaseObj(hrgn1);
1245 return ret;
1248 /***********************************************************************
1249 * REGION_UnionRectWithRegion
1250 * Adds a rectangle to a WINEREGION
1252 static BOOL REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1254 WINEREGION region;
1256 region.rects = &region.extents;
1257 region.numRects = 1;
1258 region.size = 1;
1259 region.extents = *rect;
1260 return REGION_UnionRegion(rgn, rgn, &region);
1264 /***********************************************************************
1265 * REGION_CreateFrameRgn
1267 * Create a region that is a frame around another region.
1268 * Compute the intersection of the region moved in all 4 directions
1269 * ( +x, -x, +y, -y) and subtract from the original.
1270 * The result looks slightly better than in Windows :)
1272 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1274 WINEREGION tmprgn;
1275 BOOL bRet = FALSE;
1276 RGNOBJ* destObj = NULL;
1277 RGNOBJ *srcObj = GDI_GetObjPtr( hSrc, OBJ_REGION );
1279 tmprgn.rects = NULL;
1280 if (!srcObj) return FALSE;
1281 if (srcObj->rgn.numRects != 0)
1283 if (!(destObj = GDI_GetObjPtr( hDest, OBJ_REGION ))) goto done;
1284 if (!init_region( &tmprgn, srcObj->rgn.numRects )) goto done;
1286 if (!REGION_OffsetRegion( &destObj->rgn, &srcObj->rgn, -x, 0)) goto done;
1287 if (!REGION_OffsetRegion( &tmprgn, &srcObj->rgn, x, 0)) 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_OffsetRegion( &tmprgn, &srcObj->rgn, 0, y)) goto done;
1292 if (!REGION_IntersectRegion( &destObj->rgn, &destObj->rgn, &tmprgn )) goto done;
1293 if (!REGION_SubtractRegion( &destObj->rgn, &srcObj->rgn, &destObj->rgn )) goto done;
1294 bRet = TRUE;
1296 done:
1297 HeapFree( GetProcessHeap(), 0, tmprgn.rects );
1298 if (destObj) GDI_ReleaseObj ( hDest );
1299 GDI_ReleaseObj( hSrc );
1300 return bRet;
1304 /***********************************************************************
1305 * CombineRgn (GDI32.@)
1307 * Combines two regions with the specified operation and stores the result
1308 * in the specified destination region.
1310 * PARAMS
1311 * hDest [I] The region that receives the combined result.
1312 * hSrc1 [I] The first source region.
1313 * hSrc2 [I] The second source region.
1314 * mode [I] The way in which the source regions will be combined. See notes.
1316 * RETURNS
1317 * Success:
1318 * NULLREGION - The new region is empty.
1319 * SIMPLEREGION - The new region can be represented by one rectangle.
1320 * COMPLEXREGION - The new region can only be represented by more than
1321 * one rectangle.
1322 * Failure: ERROR
1324 * NOTES
1325 * The two source regions can be the same region.
1326 * The mode can be one of the following:
1327 *| RGN_AND - Intersection of the regions
1328 *| RGN_OR - Union of the regions
1329 *| RGN_XOR - Unions of the regions minus any intersection.
1330 *| RGN_DIFF - Difference (subtraction) of the regions.
1332 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1334 RGNOBJ *destObj = GDI_GetObjPtr( hDest, OBJ_REGION );
1335 INT result = ERROR;
1337 TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1338 if (destObj)
1340 RGNOBJ *src1Obj = GDI_GetObjPtr( hSrc1, OBJ_REGION );
1342 if (src1Obj)
1344 TRACE("dump src1Obj:\n");
1345 if(TRACE_ON(region))
1346 REGION_DumpRegion(&src1Obj->rgn);
1347 if (mode == RGN_COPY)
1349 if (REGION_CopyRegion( &destObj->rgn, &src1Obj->rgn ))
1350 result = get_region_type( destObj );
1352 else
1354 RGNOBJ *src2Obj = GDI_GetObjPtr( hSrc2, OBJ_REGION );
1356 if (src2Obj)
1358 TRACE("dump src2Obj:\n");
1359 if(TRACE_ON(region))
1360 REGION_DumpRegion(&src2Obj->rgn);
1361 switch (mode)
1363 case RGN_AND:
1364 if (REGION_IntersectRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1365 result = get_region_type( destObj );
1366 break;
1367 case RGN_OR:
1368 if (REGION_UnionRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1369 result = get_region_type( destObj );
1370 break;
1371 case RGN_XOR:
1372 if (REGION_XorRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1373 result = get_region_type( destObj );
1374 break;
1375 case RGN_DIFF:
1376 if (REGION_SubtractRegion( &destObj->rgn, &src1Obj->rgn, &src2Obj->rgn ))
1377 result = get_region_type( destObj );
1378 break;
1380 GDI_ReleaseObj( hSrc2 );
1383 GDI_ReleaseObj( hSrc1 );
1385 TRACE("dump destObj:\n");
1386 if(TRACE_ON(region))
1387 REGION_DumpRegion(&destObj->rgn);
1389 GDI_ReleaseObj( hDest );
1391 return result;
1394 /***********************************************************************
1395 * REGION_SetExtents
1396 * Re-calculate the extents of a region
1398 static void REGION_SetExtents (WINEREGION *pReg)
1400 RECT *pRect, *pRectEnd, *pExtents;
1402 if (pReg->numRects == 0)
1404 pReg->extents.left = 0;
1405 pReg->extents.top = 0;
1406 pReg->extents.right = 0;
1407 pReg->extents.bottom = 0;
1408 return;
1411 pExtents = &pReg->extents;
1412 pRect = pReg->rects;
1413 pRectEnd = &pRect[pReg->numRects - 1];
1416 * Since pRect is the first rectangle in the region, it must have the
1417 * smallest top and since pRectEnd is the last rectangle in the region,
1418 * it must have the largest bottom, because of banding. Initialize left and
1419 * right from pRect and pRectEnd, resp., as good things to initialize them
1420 * to...
1422 pExtents->left = pRect->left;
1423 pExtents->top = pRect->top;
1424 pExtents->right = pRectEnd->right;
1425 pExtents->bottom = pRectEnd->bottom;
1427 while (pRect <= pRectEnd)
1429 if (pRect->left < pExtents->left)
1430 pExtents->left = pRect->left;
1431 if (pRect->right > pExtents->right)
1432 pExtents->right = pRect->right;
1433 pRect++;
1437 /***********************************************************************
1438 * REGION_CopyRegion
1440 static BOOL REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1442 if (dst != src) /* don't want to copy to itself */
1444 if (dst->size < src->numRects)
1446 RECT *rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects, src->numRects * sizeof(RECT) );
1447 if (!rects) return FALSE;
1448 dst->rects = rects;
1449 dst->size = src->numRects;
1451 dst->numRects = src->numRects;
1452 dst->extents.left = src->extents.left;
1453 dst->extents.top = src->extents.top;
1454 dst->extents.right = src->extents.right;
1455 dst->extents.bottom = src->extents.bottom;
1456 memcpy(dst->rects, src->rects, src->numRects * sizeof(RECT));
1458 return TRUE;
1461 /***********************************************************************
1462 * REGION_Coalesce
1464 * Attempt to merge the rects in the current band with those in the
1465 * previous one. Used only by REGION_RegionOp.
1467 * Results:
1468 * The new index for the previous band.
1470 * Side Effects:
1471 * If coalescing takes place:
1472 * - rectangles in the previous band will have their bottom fields
1473 * altered.
1474 * - pReg->numRects will be decreased.
1477 static INT REGION_Coalesce (
1478 WINEREGION *pReg, /* Region to coalesce */
1479 INT prevStart, /* Index of start of previous band */
1480 INT curStart /* Index of start of current band */
1482 RECT *pPrevRect; /* Current rect in previous band */
1483 RECT *pCurRect; /* Current rect in current band */
1484 RECT *pRegEnd; /* End of region */
1485 INT curNumRects; /* Number of rectangles in current band */
1486 INT prevNumRects; /* Number of rectangles in previous band */
1487 INT bandtop; /* top coordinate for current band */
1489 pRegEnd = &pReg->rects[pReg->numRects];
1491 pPrevRect = &pReg->rects[prevStart];
1492 prevNumRects = curStart - prevStart;
1495 * Figure out how many rectangles are in the current band. Have to do
1496 * this because multiple bands could have been added in REGION_RegionOp
1497 * at the end when one region has been exhausted.
1499 pCurRect = &pReg->rects[curStart];
1500 bandtop = pCurRect->top;
1501 for (curNumRects = 0;
1502 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1503 curNumRects++)
1505 pCurRect++;
1508 if (pCurRect != pRegEnd)
1511 * If more than one band was added, we have to find the start
1512 * of the last band added so the next coalescing job can start
1513 * at the right place... (given when multiple bands are added,
1514 * this may be pointless -- see above).
1516 pRegEnd--;
1517 while (pRegEnd[-1].top == pRegEnd->top)
1519 pRegEnd--;
1521 curStart = pRegEnd - pReg->rects;
1522 pRegEnd = pReg->rects + pReg->numRects;
1525 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1526 pCurRect -= curNumRects;
1528 * The bands may only be coalesced if the bottom of the previous
1529 * matches the top scanline of the current.
1531 if (pPrevRect->bottom == pCurRect->top)
1534 * Make sure the bands have rects in the same places. This
1535 * assumes that rects have been added in such a way that they
1536 * cover the most area possible. I.e. two rects in a band must
1537 * have some horizontal space between them.
1541 if ((pPrevRect->left != pCurRect->left) ||
1542 (pPrevRect->right != pCurRect->right))
1545 * The bands don't line up so they can't be coalesced.
1547 return (curStart);
1549 pPrevRect++;
1550 pCurRect++;
1551 prevNumRects -= 1;
1552 } while (prevNumRects != 0);
1554 pReg->numRects -= curNumRects;
1555 pCurRect -= curNumRects;
1556 pPrevRect -= curNumRects;
1559 * The bands may be merged, so set the bottom of each rect
1560 * in the previous band to that of the corresponding rect in
1561 * the current band.
1565 pPrevRect->bottom = pCurRect->bottom;
1566 pPrevRect++;
1567 pCurRect++;
1568 curNumRects -= 1;
1569 } while (curNumRects != 0);
1572 * If only one band was added to the region, we have to backup
1573 * curStart to the start of the previous band.
1575 * If more than one band was added to the region, copy the
1576 * other bands down. The assumption here is that the other bands
1577 * came from the same region as the current one and no further
1578 * coalescing can be done on them since it's all been done
1579 * already... curStart is already in the right place.
1581 if (pCurRect == pRegEnd)
1583 curStart = prevStart;
1585 else
1589 *pPrevRect++ = *pCurRect++;
1590 } while (pCurRect != pRegEnd);
1595 return (curStart);
1598 /***********************************************************************
1599 * REGION_RegionOp
1601 * Apply an operation to two regions. Called by REGION_Union,
1602 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1604 * Results:
1605 * None.
1607 * Side Effects:
1608 * The new region is overwritten.
1610 * Notes:
1611 * The idea behind this function is to view the two regions as sets.
1612 * Together they cover a rectangle of area that this function divides
1613 * into horizontal bands where points are covered only by one region
1614 * or by both. For the first case, the nonOverlapFunc is called with
1615 * each the band and the band's upper and lower extents. For the
1616 * second, the overlapFunc is called to process the entire band. It
1617 * is responsible for clipping the rectangles in the band, though
1618 * this function provides the boundaries.
1619 * At the end of each band, the new region is coalesced, if possible,
1620 * to reduce the number of rectangles in the region.
1623 static BOOL REGION_RegionOp(
1624 WINEREGION *destReg, /* Place to store result */
1625 WINEREGION *reg1, /* First region in operation */
1626 WINEREGION *reg2, /* 2nd region in operation */
1627 BOOL (*overlapFunc)(WINEREGION*, RECT*, RECT*, RECT*, RECT*, INT, INT), /* Function to call for over-lapping bands */
1628 BOOL (*nonOverlap1Func)(WINEREGION*, RECT*, RECT*, INT, INT), /* Function to call for non-overlapping bands in region 1 */
1629 BOOL (*nonOverlap2Func)(WINEREGION*, RECT*, RECT*, INT, INT) /* Function to call for non-overlapping bands in region 2 */
1631 WINEREGION newReg;
1632 RECT *r1; /* Pointer into first region */
1633 RECT *r2; /* Pointer into 2d region */
1634 RECT *r1End; /* End of 1st region */
1635 RECT *r2End; /* End of 2d region */
1636 INT ybot; /* Bottom of intersection */
1637 INT ytop; /* Top of intersection */
1638 INT prevBand; /* Index of start of
1639 * previous band in newReg */
1640 INT curBand; /* Index of start of current
1641 * band in newReg */
1642 RECT *r1BandEnd; /* End of current band in r1 */
1643 RECT *r2BandEnd; /* End of current band in r2 */
1644 INT top; /* Top of non-overlapping band */
1645 INT bot; /* Bottom of non-overlapping band */
1648 * Initialization:
1649 * set r1, r2, r1End and r2End appropriately, preserve the important
1650 * parts of the destination region until the end in case it's one of
1651 * the two source regions, then mark the "new" region empty, allocating
1652 * another array of rectangles for it to use.
1654 r1 = reg1->rects;
1655 r2 = reg2->rects;
1656 r1End = r1 + reg1->numRects;
1657 r2End = r2 + reg2->numRects;
1660 * Allocate a reasonable number of rectangles for the new region. The idea
1661 * is to allocate enough so the individual functions don't need to
1662 * reallocate and copy the array, which is time consuming, yet we don't
1663 * have to worry about using too much memory. I hope to be able to
1664 * nuke the Xrealloc() at the end of this function eventually.
1666 if (!init_region( &newReg, max(reg1->numRects,reg2->numRects) * 2 )) return FALSE;
1669 * Initialize ybot and ytop.
1670 * In the upcoming loop, ybot and ytop serve different functions depending
1671 * on whether the band being handled is an overlapping or non-overlapping
1672 * band.
1673 * In the case of a non-overlapping band (only one of the regions
1674 * has points in the band), ybot is the bottom of the most recent
1675 * intersection and thus clips the top of the rectangles in that band.
1676 * ytop is the top of the next intersection between the two regions and
1677 * serves to clip the bottom of the rectangles in the current band.
1678 * For an overlapping band (where the two regions intersect), ytop clips
1679 * the top of the rectangles of both regions and ybot clips the bottoms.
1681 if (reg1->extents.top < reg2->extents.top)
1682 ybot = reg1->extents.top;
1683 else
1684 ybot = reg2->extents.top;
1687 * prevBand serves to mark the start of the previous band so rectangles
1688 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1689 * In the beginning, there is no previous band, so prevBand == curBand
1690 * (curBand is set later on, of course, but the first band will always
1691 * start at index 0). prevBand and curBand must be indices because of
1692 * the possible expansion, and resultant moving, of the new region's
1693 * array of rectangles.
1695 prevBand = 0;
1699 curBand = newReg.numRects;
1702 * This algorithm proceeds one source-band (as opposed to a
1703 * destination band, which is determined by where the two regions
1704 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1705 * rectangle after the last one in the current band for their
1706 * respective regions.
1708 r1BandEnd = r1;
1709 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1711 r1BandEnd++;
1714 r2BandEnd = r2;
1715 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1717 r2BandEnd++;
1721 * First handle the band that doesn't intersect, if any.
1723 * Note that attention is restricted to one band in the
1724 * non-intersecting region at once, so if a region has n
1725 * bands between the current position and the next place it overlaps
1726 * the other, this entire loop will be passed through n times.
1728 if (r1->top < r2->top)
1730 top = max(r1->top,ybot);
1731 bot = min(r1->bottom,r2->top);
1733 if ((top != bot) && (nonOverlap1Func != NULL))
1735 if (!nonOverlap1Func(&newReg, r1, r1BandEnd, top, bot)) return FALSE;
1738 ytop = r2->top;
1740 else if (r2->top < r1->top)
1742 top = max(r2->top,ybot);
1743 bot = min(r2->bottom,r1->top);
1745 if ((top != bot) && (nonOverlap2Func != NULL))
1747 if (!nonOverlap2Func(&newReg, r2, r2BandEnd, top, bot)) return FALSE;
1750 ytop = r1->top;
1752 else
1754 ytop = r1->top;
1758 * If any rectangles got added to the region, try and coalesce them
1759 * with rectangles from the previous band. Note we could just do
1760 * this test in miCoalesce, but some machines incur a not
1761 * inconsiderable cost for function calls, so...
1763 if (newReg.numRects != curBand)
1765 prevBand = REGION_Coalesce (&newReg, prevBand, curBand);
1769 * Now see if we've hit an intersecting band. The two bands only
1770 * intersect if ybot > ytop
1772 ybot = min(r1->bottom, r2->bottom);
1773 curBand = newReg.numRects;
1774 if (ybot > ytop)
1776 if (!overlapFunc(&newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot)) return FALSE;
1779 if (newReg.numRects != curBand)
1781 prevBand = REGION_Coalesce (&newReg, prevBand, curBand);
1785 * If we've finished with a band (bottom == ybot) we skip forward
1786 * in the region to the next band.
1788 if (r1->bottom == ybot)
1790 r1 = r1BandEnd;
1792 if (r2->bottom == ybot)
1794 r2 = r2BandEnd;
1796 } while ((r1 != r1End) && (r2 != r2End));
1799 * Deal with whichever region still has rectangles left.
1801 curBand = newReg.numRects;
1802 if (r1 != r1End)
1804 if (nonOverlap1Func != NULL)
1808 r1BandEnd = r1;
1809 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1811 r1BandEnd++;
1813 if (!nonOverlap1Func(&newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom))
1814 return FALSE;
1815 r1 = r1BandEnd;
1816 } while (r1 != r1End);
1819 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1823 r2BandEnd = r2;
1824 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1826 r2BandEnd++;
1828 if (!nonOverlap2Func(&newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom))
1829 return FALSE;
1830 r2 = r2BandEnd;
1831 } while (r2 != r2End);
1834 if (newReg.numRects != curBand)
1836 REGION_Coalesce (&newReg, prevBand, curBand);
1840 * A bit of cleanup. To keep regions from growing without bound,
1841 * we shrink the array of rectangles to match the new number of
1842 * rectangles in the region. This never goes to 0, however...
1844 * Only do this stuff if the number of rectangles allocated is more than
1845 * twice the number of rectangles in the region (a simple optimization...).
1847 if ((newReg.numRects < (newReg.size >> 1)) && (newReg.numRects > 2))
1849 RECT *new_rects = HeapReAlloc( GetProcessHeap(), 0, newReg.rects, newReg.numRects * sizeof(RECT) );
1850 if (new_rects)
1852 newReg.rects = new_rects;
1853 newReg.size = newReg.numRects;
1856 HeapFree( GetProcessHeap(), 0, destReg->rects );
1857 destReg->rects = newReg.rects;
1858 destReg->size = newReg.size;
1859 destReg->numRects = newReg.numRects;
1860 return TRUE;
1863 /***********************************************************************
1864 * Region Intersection
1865 ***********************************************************************/
1868 /***********************************************************************
1869 * REGION_IntersectO
1871 * Handle an overlapping band for REGION_Intersect.
1873 * Results:
1874 * None.
1876 * Side Effects:
1877 * Rectangles may be added to the region.
1880 static BOOL REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1881 RECT *r2, RECT *r2End, INT top, INT bottom)
1884 INT left, right;
1886 while ((r1 != r1End) && (r2 != r2End))
1888 left = max(r1->left, r2->left);
1889 right = min(r1->right, r2->right);
1892 * If there's any overlap between the two rectangles, add that
1893 * overlap to the new region.
1894 * There's no need to check for subsumption because the only way
1895 * such a need could arise is if some region has two rectangles
1896 * right next to each other. Since that should never happen...
1898 if (left < right)
1900 if (!add_rect( pReg, left, top, right, bottom )) return FALSE;
1904 * Need to advance the pointers. Shift the one that extends
1905 * to the right the least, since the other still has a chance to
1906 * overlap with that region's next rectangle, if you see what I mean.
1908 if (r1->right < r2->right)
1910 r1++;
1912 else if (r2->right < r1->right)
1914 r2++;
1916 else
1918 r1++;
1919 r2++;
1922 return TRUE;
1925 /***********************************************************************
1926 * REGION_IntersectRegion
1928 static BOOL REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1929 WINEREGION *reg2)
1931 /* check for trivial reject */
1932 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1933 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
1934 newReg->numRects = 0;
1935 else
1936 if (!REGION_RegionOp (newReg, reg1, reg2, REGION_IntersectO, NULL, NULL)) return FALSE;
1939 * Can't alter newReg's extents before we call miRegionOp because
1940 * it might be one of the source regions and miRegionOp depends
1941 * on the extents of those regions being the same. Besides, this
1942 * way there's no checking against rectangles that will be nuked
1943 * due to coalescing, so we have to examine fewer rectangles.
1945 REGION_SetExtents(newReg);
1946 return TRUE;
1949 /***********************************************************************
1950 * Region Union
1951 ***********************************************************************/
1953 /***********************************************************************
1954 * REGION_UnionNonO
1956 * Handle a non-overlapping band for the union operation. Just
1957 * Adds the rectangles into the region. Doesn't have to check for
1958 * subsumption or anything.
1960 * Results:
1961 * None.
1963 * Side Effects:
1964 * pReg->numRects is incremented and the final rectangles overwritten
1965 * with the rectangles we're passed.
1968 static BOOL REGION_UnionNonO(WINEREGION *pReg, RECT *r, RECT *rEnd, INT top, INT bottom)
1970 while (r != rEnd)
1972 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE;
1973 r++;
1975 return TRUE;
1978 /***********************************************************************
1979 * REGION_UnionO
1981 * Handle an overlapping band for the union operation. Picks the
1982 * left-most rectangle each time and merges it into the region.
1984 * Results:
1985 * None.
1987 * Side Effects:
1988 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1989 * be changed.
1992 static BOOL REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1993 RECT *r2, RECT *r2End, INT top, INT bottom)
1995 #define MERGERECT(r) \
1996 if ((pReg->numRects != 0) && \
1997 (pReg->rects[pReg->numRects-1].top == top) && \
1998 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
1999 (pReg->rects[pReg->numRects-1].right >= r->left)) \
2001 if (pReg->rects[pReg->numRects-1].right < r->right) \
2002 pReg->rects[pReg->numRects-1].right = r->right; \
2004 else \
2006 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
2008 r++;
2010 while ((r1 != r1End) && (r2 != r2End))
2012 if (r1->left < r2->left)
2014 MERGERECT(r1);
2016 else
2018 MERGERECT(r2);
2022 if (r1 != r1End)
2026 MERGERECT(r1);
2027 } while (r1 != r1End);
2029 else while (r2 != r2End)
2031 MERGERECT(r2);
2033 return TRUE;
2034 #undef MERGERECT
2037 /***********************************************************************
2038 * REGION_UnionRegion
2040 static BOOL REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1, WINEREGION *reg2)
2042 BOOL ret = TRUE;
2044 /* checks all the simple cases */
2047 * Region 1 and 2 are the same or region 1 is empty
2049 if ( (reg1 == reg2) || (!(reg1->numRects)) )
2051 if (newReg != reg2)
2052 ret = REGION_CopyRegion(newReg, reg2);
2053 return ret;
2057 * if nothing to union (region 2 empty)
2059 if (!(reg2->numRects))
2061 if (newReg != reg1)
2062 ret = REGION_CopyRegion(newReg, reg1);
2063 return ret;
2067 * Region 1 completely subsumes region 2
2069 if ((reg1->numRects == 1) &&
2070 (reg1->extents.left <= reg2->extents.left) &&
2071 (reg1->extents.top <= reg2->extents.top) &&
2072 (reg1->extents.right >= reg2->extents.right) &&
2073 (reg1->extents.bottom >= reg2->extents.bottom))
2075 if (newReg != reg1)
2076 ret = REGION_CopyRegion(newReg, reg1);
2077 return ret;
2081 * Region 2 completely subsumes region 1
2083 if ((reg2->numRects == 1) &&
2084 (reg2->extents.left <= reg1->extents.left) &&
2085 (reg2->extents.top <= reg1->extents.top) &&
2086 (reg2->extents.right >= reg1->extents.right) &&
2087 (reg2->extents.bottom >= reg1->extents.bottom))
2089 if (newReg != reg2)
2090 ret = REGION_CopyRegion(newReg, reg2);
2091 return ret;
2094 if ((ret = REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO, REGION_UnionNonO, REGION_UnionNonO)))
2096 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2097 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2098 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2099 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2101 return ret;
2104 /***********************************************************************
2105 * Region Subtraction
2106 ***********************************************************************/
2108 /***********************************************************************
2109 * REGION_SubtractNonO1
2111 * Deal with non-overlapping band for subtraction. Any parts from
2112 * region 2 we discard. Anything from region 1 we add to the region.
2114 * Results:
2115 * None.
2117 * Side Effects:
2118 * pReg may be affected.
2121 static BOOL REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd, INT top, INT bottom)
2123 while (r != rEnd)
2125 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE;
2126 r++;
2128 return TRUE;
2132 /***********************************************************************
2133 * REGION_SubtractO
2135 * Overlapping band subtraction. x1 is the left-most point not yet
2136 * checked.
2138 * Results:
2139 * None.
2141 * Side Effects:
2142 * pReg may have rectangles added to it.
2145 static BOOL REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2146 RECT *r2, RECT *r2End, INT top, INT bottom)
2148 INT left = r1->left;
2150 while ((r1 != r1End) && (r2 != r2End))
2152 if (r2->right <= left)
2155 * Subtrahend missed the boat: go to next subtrahend.
2157 r2++;
2159 else if (r2->left <= left)
2162 * Subtrahend precedes minuend: nuke left edge of minuend.
2164 left = r2->right;
2165 if (left >= r1->right)
2168 * Minuend completely covered: advance to next minuend and
2169 * reset left fence to edge of new minuend.
2171 r1++;
2172 if (r1 != r1End)
2173 left = r1->left;
2175 else
2178 * Subtrahend now used up since it doesn't extend beyond
2179 * minuend
2181 r2++;
2184 else if (r2->left < r1->right)
2187 * Left part of subtrahend covers part of minuend: add uncovered
2188 * part of minuend to region and skip to next subtrahend.
2190 if (!add_rect( pReg, left, top, r2->left, bottom )) return FALSE;
2191 left = r2->right;
2192 if (left >= r1->right)
2195 * Minuend used up: advance to new...
2197 r1++;
2198 if (r1 != r1End)
2199 left = r1->left;
2201 else
2204 * Subtrahend used up
2206 r2++;
2209 else
2212 * Minuend used up: add any remaining piece before advancing.
2214 if (r1->right > left)
2216 if (!add_rect( pReg, left, top, r1->right, bottom )) return FALSE;
2218 r1++;
2219 if (r1 != r1End)
2220 left = r1->left;
2225 * Add remaining minuend rectangles to region.
2227 while (r1 != r1End)
2229 if (!add_rect( pReg, left, top, r1->right, bottom )) return FALSE;
2230 r1++;
2231 if (r1 != r1End)
2233 left = r1->left;
2236 return TRUE;
2239 /***********************************************************************
2240 * REGION_SubtractRegion
2242 * Subtract regS from regM and leave the result in regD.
2243 * S stands for subtrahend, M for minuend and D for difference.
2245 * Results:
2246 * TRUE.
2248 * Side Effects:
2249 * regD is overwritten.
2252 static BOOL REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM, WINEREGION *regS )
2254 /* check for trivial reject */
2255 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2256 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2257 return REGION_CopyRegion(regD, regM);
2259 if (!REGION_RegionOp (regD, regM, regS, REGION_SubtractO, REGION_SubtractNonO1, NULL))
2260 return FALSE;
2263 * Can't alter newReg's extents before we call miRegionOp because
2264 * it might be one of the source regions and miRegionOp depends
2265 * on the extents of those regions being the unaltered. Besides, this
2266 * way there's no checking against rectangles that will be nuked
2267 * due to coalescing, so we have to examine fewer rectangles.
2269 REGION_SetExtents (regD);
2270 return TRUE;
2273 /***********************************************************************
2274 * REGION_XorRegion
2276 static BOOL REGION_XorRegion(WINEREGION *dr, WINEREGION *sra, WINEREGION *srb)
2278 WINEREGION tra, trb;
2279 BOOL ret;
2281 if (!init_region( &tra, sra->numRects + 1 )) return FALSE;
2282 if ((ret = init_region( &trb, srb->numRects + 1 )))
2284 ret = REGION_SubtractRegion(&tra,sra,srb) &&
2285 REGION_SubtractRegion(&trb,srb,sra) &&
2286 REGION_UnionRegion(dr,&tra,&trb);
2287 destroy_region(&trb);
2289 destroy_region(&tra);
2290 return ret;
2293 /**************************************************************************
2295 * Poly Regions
2297 *************************************************************************/
2299 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2300 #define SMALL_COORDINATE 0x80000000
2302 /***********************************************************************
2303 * REGION_InsertEdgeInET
2305 * Insert the given edge into the edge table.
2306 * First we must find the correct bucket in the
2307 * Edge table, then find the right slot in the
2308 * bucket. Finally, we can insert it.
2311 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2312 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2315 EdgeTableEntry *start, *prev;
2316 ScanLineList *pSLL, *pPrevSLL;
2317 ScanLineListBlock *tmpSLLBlock;
2320 * find the right bucket to put the edge into
2322 pPrevSLL = &ET->scanlines;
2323 pSLL = pPrevSLL->next;
2324 while (pSLL && (pSLL->scanline < scanline))
2326 pPrevSLL = pSLL;
2327 pSLL = pSLL->next;
2331 * reassign pSLL (pointer to ScanLineList) if necessary
2333 if ((!pSLL) || (pSLL->scanline > scanline))
2335 if (*iSLLBlock > SLLSPERBLOCK-1)
2337 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2338 if(!tmpSLLBlock)
2340 WARN("Can't alloc SLLB\n");
2341 return;
2343 (*SLLBlock)->next = tmpSLLBlock;
2344 tmpSLLBlock->next = NULL;
2345 *SLLBlock = tmpSLLBlock;
2346 *iSLLBlock = 0;
2348 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2350 pSLL->next = pPrevSLL->next;
2351 pSLL->edgelist = NULL;
2352 pPrevSLL->next = pSLL;
2354 pSLL->scanline = scanline;
2357 * now insert the edge in the right bucket
2359 prev = NULL;
2360 start = pSLL->edgelist;
2361 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2363 prev = start;
2364 start = start->next;
2366 ETE->next = start;
2368 if (prev)
2369 prev->next = ETE;
2370 else
2371 pSLL->edgelist = ETE;
2374 /***********************************************************************
2375 * REGION_CreateEdgeTable
2377 * This routine creates the edge table for
2378 * scan converting polygons.
2379 * The Edge Table (ET) looks like:
2381 * EdgeTable
2382 * --------
2383 * | ymax | ScanLineLists
2384 * |scanline|-->------------>-------------->...
2385 * -------- |scanline| |scanline|
2386 * |edgelist| |edgelist|
2387 * --------- ---------
2388 * | |
2389 * | |
2390 * V V
2391 * list of ETEs list of ETEs
2393 * where ETE is an EdgeTableEntry data structure,
2394 * and there is one ScanLineList per scanline at
2395 * which an edge is initially entered.
2398 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2399 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2400 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2402 const POINT *top, *bottom;
2403 const POINT *PrevPt, *CurrPt, *EndPt;
2404 INT poly, count;
2405 int iSLLBlock = 0;
2406 int dy;
2410 * initialize the Active Edge Table
2412 AET->next = NULL;
2413 AET->back = NULL;
2414 AET->nextWETE = NULL;
2415 AET->bres.minor_axis = SMALL_COORDINATE;
2418 * initialize the Edge Table.
2420 ET->scanlines.next = NULL;
2421 ET->ymax = SMALL_COORDINATE;
2422 ET->ymin = LARGE_COORDINATE;
2423 pSLLBlock->next = NULL;
2425 EndPt = pts - 1;
2426 for(poly = 0; poly < nbpolygons; poly++)
2428 count = Count[poly];
2429 EndPt += count;
2430 if(count < 2)
2431 continue;
2433 PrevPt = EndPt;
2436 * for each vertex in the array of points.
2437 * In this loop we are dealing with two vertices at
2438 * a time -- these make up one edge of the polygon.
2440 while (count--)
2442 CurrPt = pts++;
2445 * find out which point is above and which is below.
2447 if (PrevPt->y > CurrPt->y)
2449 bottom = PrevPt, top = CurrPt;
2450 pETEs->ClockWise = 0;
2452 else
2454 bottom = CurrPt, top = PrevPt;
2455 pETEs->ClockWise = 1;
2459 * don't add horizontal edges to the Edge table.
2461 if (bottom->y != top->y)
2463 pETEs->ymax = bottom->y-1;
2464 /* -1 so we don't get last scanline */
2467 * initialize integer edge algorithm
2469 dy = bottom->y - top->y;
2470 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2472 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2473 &iSLLBlock);
2475 if (PrevPt->y > ET->ymax)
2476 ET->ymax = PrevPt->y;
2477 if (PrevPt->y < ET->ymin)
2478 ET->ymin = PrevPt->y;
2479 pETEs++;
2482 PrevPt = CurrPt;
2487 /***********************************************************************
2488 * REGION_loadAET
2490 * This routine moves EdgeTableEntries from the
2491 * EdgeTable into the Active Edge Table,
2492 * leaving them sorted by smaller x coordinate.
2495 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2497 EdgeTableEntry *pPrevAET;
2498 EdgeTableEntry *tmp;
2500 pPrevAET = AET;
2501 AET = AET->next;
2502 while (ETEs)
2504 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2506 pPrevAET = AET;
2507 AET = AET->next;
2509 tmp = ETEs->next;
2510 ETEs->next = AET;
2511 if (AET)
2512 AET->back = ETEs;
2513 ETEs->back = pPrevAET;
2514 pPrevAET->next = ETEs;
2515 pPrevAET = ETEs;
2517 ETEs = tmp;
2521 /***********************************************************************
2522 * REGION_computeWAET
2524 * This routine links the AET by the
2525 * nextWETE (winding EdgeTableEntry) link for
2526 * use by the winding number rule. The final
2527 * Active Edge Table (AET) might look something
2528 * like:
2530 * AET
2531 * ---------- --------- ---------
2532 * |ymax | |ymax | |ymax |
2533 * | ... | |... | |... |
2534 * |next |->|next |->|next |->...
2535 * |nextWETE| |nextWETE| |nextWETE|
2536 * --------- --------- ^--------
2537 * | | |
2538 * V-------------------> V---> ...
2541 static void REGION_computeWAET(EdgeTableEntry *AET)
2543 register EdgeTableEntry *pWETE;
2544 register int inside = 1;
2545 register int isInside = 0;
2547 AET->nextWETE = NULL;
2548 pWETE = AET;
2549 AET = AET->next;
2550 while (AET)
2552 if (AET->ClockWise)
2553 isInside++;
2554 else
2555 isInside--;
2557 if ((!inside && !isInside) ||
2558 ( inside && isInside))
2560 pWETE->nextWETE = AET;
2561 pWETE = AET;
2562 inside = !inside;
2564 AET = AET->next;
2566 pWETE->nextWETE = NULL;
2569 /***********************************************************************
2570 * REGION_InsertionSort
2572 * Just a simple insertion sort using
2573 * pointers and back pointers to sort the Active
2574 * Edge Table.
2577 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2579 EdgeTableEntry *pETEchase;
2580 EdgeTableEntry *pETEinsert;
2581 EdgeTableEntry *pETEchaseBackTMP;
2582 BOOL changed = FALSE;
2584 AET = AET->next;
2585 while (AET)
2587 pETEinsert = AET;
2588 pETEchase = AET;
2589 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2590 pETEchase = pETEchase->back;
2592 AET = AET->next;
2593 if (pETEchase != pETEinsert)
2595 pETEchaseBackTMP = pETEchase->back;
2596 pETEinsert->back->next = AET;
2597 if (AET)
2598 AET->back = pETEinsert->back;
2599 pETEinsert->next = pETEchase;
2600 pETEchase->back->next = pETEinsert;
2601 pETEchase->back = pETEinsert;
2602 pETEinsert->back = pETEchaseBackTMP;
2603 changed = TRUE;
2606 return changed;
2609 /***********************************************************************
2610 * REGION_FreeStorage
2612 * Clean up our act.
2614 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2616 ScanLineListBlock *tmpSLLBlock;
2618 while (pSLLBlock)
2620 tmpSLLBlock = pSLLBlock->next;
2621 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2622 pSLLBlock = tmpSLLBlock;
2627 /***********************************************************************
2628 * REGION_PtsToRegion
2630 * Create an array of rectangles from a list of points.
2632 static BOOL REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2633 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2635 RECT *rects;
2636 POINT *pts;
2637 POINTBLOCK *CurPtBlock;
2638 int i;
2639 RECT *extents;
2640 INT numRects;
2642 extents = &reg->extents;
2644 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2645 if (!init_region( reg, numRects )) return FALSE;
2647 reg->size = numRects;
2648 CurPtBlock = FirstPtBlock;
2649 rects = reg->rects - 1;
2650 numRects = 0;
2651 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2653 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2654 /* the loop uses 2 points per iteration */
2655 i = NUMPTSTOBUFFER >> 1;
2656 if (!numFullPtBlocks)
2657 i = iCurPtBlock >> 1;
2658 for (pts = CurPtBlock->pts; i--; pts += 2) {
2659 if (pts->x == pts[1].x)
2660 continue;
2661 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2662 pts[1].x == rects->right &&
2663 (numRects == 1 || rects[-1].top != rects->top) &&
2664 (i && pts[2].y > pts[1].y)) {
2665 rects->bottom = pts[1].y + 1;
2666 continue;
2668 numRects++;
2669 rects++;
2670 rects->left = pts->x; rects->top = pts->y;
2671 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2672 if (rects->left < extents->left)
2673 extents->left = rects->left;
2674 if (rects->right > extents->right)
2675 extents->right = rects->right;
2677 CurPtBlock = CurPtBlock->next;
2680 if (numRects) {
2681 extents->top = reg->rects->top;
2682 extents->bottom = rects->bottom;
2683 } else {
2684 extents->left = 0;
2685 extents->top = 0;
2686 extents->right = 0;
2687 extents->bottom = 0;
2689 reg->numRects = numRects;
2691 return(TRUE);
2694 /***********************************************************************
2695 * CreatePolyPolygonRgn (GDI32.@)
2697 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2698 INT nbpolygons, INT mode)
2700 HRGN hrgn = 0;
2701 RGNOBJ *obj;
2702 EdgeTableEntry *pAET; /* Active Edge Table */
2703 INT y; /* current scanline */
2704 int iPts = 0; /* number of pts in buffer */
2705 EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2706 ScanLineList *pSLL; /* current scanLineList */
2707 POINT *pts; /* output buffer */
2708 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2709 EdgeTable ET; /* header node for ET */
2710 EdgeTableEntry AET; /* header node for AET */
2711 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2712 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2713 int fixWAET = FALSE;
2714 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2715 POINTBLOCK *tmpPtBlock;
2716 int numFullPtBlocks = 0;
2717 INT poly, total;
2719 TRACE("%p, count %d, polygons %d, mode %d\n", Pts, *Count, nbpolygons, mode);
2721 /* special case a rectangle */
2723 if (((nbpolygons == 1) && ((*Count == 4) ||
2724 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2725 (((Pts[0].y == Pts[1].y) &&
2726 (Pts[1].x == Pts[2].x) &&
2727 (Pts[2].y == Pts[3].y) &&
2728 (Pts[3].x == Pts[0].x)) ||
2729 ((Pts[0].x == Pts[1].x) &&
2730 (Pts[1].y == Pts[2].y) &&
2731 (Pts[2].x == Pts[3].x) &&
2732 (Pts[3].y == Pts[0].y))))
2733 return CreateRectRgn( min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2734 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2736 for(poly = total = 0; poly < nbpolygons; poly++)
2737 total += Count[poly];
2738 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2739 return 0;
2741 pts = FirstPtBlock.pts;
2742 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2743 pSLL = ET.scanlines.next;
2744 curPtBlock = &FirstPtBlock;
2746 if (mode != WINDING) {
2748 * for each scanline
2750 for (y = ET.ymin; y < ET.ymax; y++) {
2752 * Add a new edge to the active edge table when we
2753 * get to the next edge.
2755 if (pSLL != NULL && y == pSLL->scanline) {
2756 REGION_loadAET(&AET, pSLL->edgelist);
2757 pSLL = pSLL->next;
2759 pPrevAET = &AET;
2760 pAET = AET.next;
2763 * for each active edge
2765 while (pAET) {
2766 pts->x = pAET->bres.minor_axis, pts->y = y;
2767 pts++, iPts++;
2770 * send out the buffer
2772 if (iPts == NUMPTSTOBUFFER) {
2773 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2774 if(!tmpPtBlock) goto done;
2775 curPtBlock->next = tmpPtBlock;
2776 curPtBlock = tmpPtBlock;
2777 pts = curPtBlock->pts;
2778 numFullPtBlocks++;
2779 iPts = 0;
2781 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2783 REGION_InsertionSort(&AET);
2786 else {
2788 * for each scanline
2790 for (y = ET.ymin; y < ET.ymax; y++) {
2792 * Add a new edge to the active edge table when we
2793 * get to the next edge.
2795 if (pSLL != NULL && y == pSLL->scanline) {
2796 REGION_loadAET(&AET, pSLL->edgelist);
2797 REGION_computeWAET(&AET);
2798 pSLL = pSLL->next;
2800 pPrevAET = &AET;
2801 pAET = AET.next;
2802 pWETE = pAET;
2805 * for each active edge
2807 while (pAET) {
2809 * add to the buffer only those edges that
2810 * are in the Winding active edge table.
2812 if (pWETE == pAET) {
2813 pts->x = pAET->bres.minor_axis, pts->y = y;
2814 pts++, iPts++;
2817 * send out the buffer
2819 if (iPts == NUMPTSTOBUFFER) {
2820 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2821 sizeof(POINTBLOCK) );
2822 if(!tmpPtBlock) goto done;
2823 curPtBlock->next = tmpPtBlock;
2824 curPtBlock = tmpPtBlock;
2825 pts = curPtBlock->pts;
2826 numFullPtBlocks++;
2827 iPts = 0;
2829 pWETE = pWETE->nextWETE;
2831 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2835 * recompute the winding active edge table if
2836 * we just resorted or have exited an edge.
2838 if (REGION_InsertionSort(&AET) || fixWAET) {
2839 REGION_computeWAET(&AET);
2840 fixWAET = FALSE;
2845 if (!(obj = HeapAlloc( GetProcessHeap(), 0, sizeof(*obj) ))) goto done;
2847 if (!REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, &obj->rgn))
2849 HeapFree( GetProcessHeap(), 0, obj );
2850 goto done;
2852 if (!(hrgn = alloc_gdi_handle( &obj->header, OBJ_REGION, &region_funcs )))
2854 HeapFree( GetProcessHeap(), 0, obj->rgn.rects );
2855 HeapFree( GetProcessHeap(), 0, obj );
2858 done:
2859 REGION_FreeStorage(SLLBlock.next);
2860 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2861 tmpPtBlock = curPtBlock->next;
2862 HeapFree( GetProcessHeap(), 0, curPtBlock );
2863 curPtBlock = tmpPtBlock;
2865 HeapFree( GetProcessHeap(), 0, pETEs );
2866 return hrgn;
2870 /***********************************************************************
2871 * CreatePolygonRgn (GDI32.@)
2873 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2874 INT mode )
2876 return CreatePolyPolygonRgn( points, &count, 1, mode );