regedit: Update Norwegian Bokmål translation.
[wine.git] / dlls / gdi32 / region.c
blobe70f65b206da2b4d310b09672b358e754ed67a19
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, void *obj );
126 static const struct gdi_obj_funcs region_funcs =
128 REGION_SelectObject, /* pSelectObject */
129 NULL, /* pGetObjectA */
130 NULL, /* pGetObjectW */
131 NULL, /* pUnrealizeObject */
132 REGION_DeleteObject /* pDeleteObject */
135 /* 1 if two RECTs overlap.
136 * 0 if two RECTs do not overlap.
138 #define EXTENTCHECK(r1, r2) \
139 ((r1)->right > (r2)->left && \
140 (r1)->left < (r2)->right && \
141 (r1)->bottom > (r2)->top && \
142 (r1)->top < (r2)->bottom)
145 * Check to see if there is enough memory in the present region.
148 static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
149 if (reg->numRects >= (reg->size - 1)) {
150 *firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
151 if (*firstrect == 0)
152 return 0;
153 reg->size *= 2;
154 *rect = (*firstrect)+reg->numRects;
156 return 1;
159 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
161 #define EMPTY_REGION(pReg) { \
162 (pReg)->numRects = 0; \
163 (pReg)->extents.left = (pReg)->extents.top = 0; \
164 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
167 #define REGION_NOT_EMPTY(pReg) pReg->numRects
169 #define INRECT(r, x, y) \
170 ( ( ((r).right > x)) && \
171 ( ((r).left <= x)) && \
172 ( ((r).bottom > y)) && \
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 void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
443 static void REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
444 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
445 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
446 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
447 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
450 #define RGN_DEFAULT_RECTS 2
453 /***********************************************************************
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 * REGION_AllocWineRegion
487 * Create a new empty WINEREGION.
489 static WINEREGION *REGION_AllocWineRegion( INT n )
491 WINEREGION *pReg;
493 if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
495 if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
497 pReg->size = n;
498 EMPTY_REGION(pReg);
499 return pReg;
501 HeapFree(GetProcessHeap(), 0, pReg);
503 return NULL;
507 /***********************************************************************
508 * REGION_CreateRegion
509 * Create a new empty region.
511 static HRGN REGION_CreateRegion( INT n )
513 HRGN hrgn;
514 RGNOBJ *obj;
516 if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, (HGDIOBJ *)&hrgn,
517 &region_funcs ))) return 0;
518 if(!(obj->rgn = REGION_AllocWineRegion(n))) {
519 GDI_FreeObject( hrgn, obj );
520 return 0;
522 GDI_ReleaseObj( hrgn );
523 return hrgn;
526 /***********************************************************************
527 * REGION_DestroyWineRegion
529 static void REGION_DestroyWineRegion( WINEREGION* pReg )
531 HeapFree( GetProcessHeap(), 0, pReg->rects );
532 HeapFree( GetProcessHeap(), 0, pReg );
535 /***********************************************************************
536 * REGION_DeleteObject
538 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj )
540 RGNOBJ *rgn = obj;
542 TRACE(" %p\n", handle );
544 REGION_DestroyWineRegion( rgn->rgn );
545 return GDI_FreeObject( handle, obj );
548 /***********************************************************************
549 * REGION_SelectObject
551 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
553 return ULongToHandle(SelectClipRgn( hdc, handle ));
557 /***********************************************************************
558 * REGION_OffsetRegion
559 * Offset a WINEREGION by x,y
561 static void REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn,
562 INT x, INT y )
564 if( rgn != srcrgn)
565 REGION_CopyRegion( rgn, srcrgn);
566 if(x || y) {
567 int nbox = rgn->numRects;
568 RECT *pbox = rgn->rects;
570 if(nbox) {
571 while(nbox--) {
572 pbox->left += x;
573 pbox->right += x;
574 pbox->top += y;
575 pbox->bottom += y;
576 pbox++;
578 rgn->extents.left += x;
579 rgn->extents.right += x;
580 rgn->extents.top += y;
581 rgn->extents.bottom += y;
586 /***********************************************************************
587 * OffsetRgn (GDI32.@)
589 * Moves a region by the specified X- and Y-axis offsets.
591 * PARAMS
592 * hrgn [I] Region to offset.
593 * x [I] Offset right if positive or left if negative.
594 * y [I] Offset down if positive or up if negative.
596 * RETURNS
597 * Success:
598 * NULLREGION - The new region is empty.
599 * SIMPLEREGION - The new region can be represented by one rectangle.
600 * COMPLEXREGION - The new region can only be represented by more than
601 * one rectangle.
602 * Failure: ERROR
604 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
606 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
607 INT ret;
609 TRACE("%p %d,%d\n", hrgn, x, y);
611 if (!obj)
612 return ERROR;
614 REGION_OffsetRegion( obj->rgn, obj->rgn, x, y);
616 ret = get_region_type( obj );
617 GDI_ReleaseObj( hrgn );
618 return ret;
622 /***********************************************************************
623 * GetRgnBox (GDI32.@)
625 * Retrieves the bounding rectangle of the region. The bounding rectangle
626 * is the smallest rectangle that contains the entire region.
628 * PARAMS
629 * hrgn [I] Region to retrieve bounding rectangle from.
630 * rect [O] Rectangle that will receive the coordinates of the bounding
631 * rectangle.
633 * RETURNS
634 * NULLREGION - The new region is empty.
635 * SIMPLEREGION - The new region can be represented by one rectangle.
636 * COMPLEXREGION - The new region can only be represented by more than
637 * one rectangle.
639 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
641 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
642 if (obj)
644 INT ret;
645 rect->left = obj->rgn->extents.left;
646 rect->top = obj->rgn->extents.top;
647 rect->right = obj->rgn->extents.right;
648 rect->bottom = obj->rgn->extents.bottom;
649 TRACE("%p (%d,%d-%d,%d)\n", hrgn,
650 rect->left, rect->top, rect->right, rect->bottom);
651 ret = get_region_type( obj );
652 GDI_ReleaseObj(hrgn);
653 return ret;
655 return ERROR;
659 /***********************************************************************
660 * CreateRectRgn (GDI32.@)
662 * Creates a simple rectangular region.
664 * PARAMS
665 * left [I] Left coordinate of rectangle.
666 * top [I] Top coordinate of rectangle.
667 * right [I] Right coordinate of rectangle.
668 * bottom [I] Bottom coordinate of rectangle.
670 * RETURNS
671 * Success: Handle to region.
672 * Failure: NULL.
674 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
676 HRGN hrgn;
678 /* Allocate 2 rects by default to reduce the number of reallocs */
680 if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
681 return 0;
682 TRACE("%d,%d-%d,%d\n", left, top, right, bottom);
683 SetRectRgn(hrgn, left, top, right, bottom);
684 return hrgn;
688 /***********************************************************************
689 * CreateRectRgnIndirect (GDI32.@)
691 * Creates a simple rectangular region.
693 * PARAMS
694 * rect [I] Coordinates of rectangular region.
696 * RETURNS
697 * Success: Handle to region.
698 * Failure: NULL.
700 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
702 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
706 /***********************************************************************
707 * SetRectRgn (GDI32.@)
709 * Sets a region to a simple rectangular region.
711 * PARAMS
712 * hrgn [I] Region to convert.
713 * left [I] Left coordinate of rectangle.
714 * top [I] Top coordinate of rectangle.
715 * right [I] Right coordinate of rectangle.
716 * bottom [I] Bottom coordinate of rectangle.
718 * RETURNS
719 * Success: Non-zero.
720 * Failure: Zero.
722 * NOTES
723 * Allows either or both left and top to be greater than right or bottom.
725 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
726 INT right, INT bottom )
728 RGNOBJ * obj;
730 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
732 if (!(obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
734 if (left > right) { INT tmp = left; left = right; right = tmp; }
735 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
737 if((left != right) && (top != bottom))
739 obj->rgn->rects->left = obj->rgn->extents.left = left;
740 obj->rgn->rects->top = obj->rgn->extents.top = top;
741 obj->rgn->rects->right = obj->rgn->extents.right = right;
742 obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
743 obj->rgn->numRects = 1;
745 else
746 EMPTY_REGION(obj->rgn);
748 GDI_ReleaseObj( hrgn );
749 return TRUE;
753 /***********************************************************************
754 * CreateRoundRectRgn (GDI32.@)
756 * Creates a rectangular region with rounded corners.
758 * PARAMS
759 * left [I] Left coordinate of rectangle.
760 * top [I] Top coordinate of rectangle.
761 * right [I] Right coordinate of rectangle.
762 * bottom [I] Bottom coordinate of rectangle.
763 * ellipse_width [I] Width of the ellipse at each corner.
764 * ellipse_height [I] Height of the ellipse at each corner.
766 * RETURNS
767 * Success: Handle to region.
768 * Failure: NULL.
770 * NOTES
771 * If ellipse_width or ellipse_height is less than 2 logical units then
772 * it is treated as though CreateRectRgn() was called instead.
774 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
775 INT right, INT bottom,
776 INT ellipse_width, INT ellipse_height )
778 RGNOBJ * obj;
779 HRGN hrgn;
780 int asq, bsq, d, xd, yd;
781 RECT rect;
783 /* Make the dimensions sensible */
785 if (left > right) { INT tmp = left; left = right; right = tmp; }
786 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
788 ellipse_width = abs(ellipse_width);
789 ellipse_height = abs(ellipse_height);
791 /* Check parameters */
793 if (ellipse_width > right-left) ellipse_width = right-left;
794 if (ellipse_height > bottom-top) ellipse_height = bottom-top;
796 /* Check if we can do a normal rectangle instead */
798 if ((ellipse_width < 2) || (ellipse_height < 2))
799 return CreateRectRgn( left, top, right, bottom );
801 /* Create region */
803 d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
804 if (!(hrgn = REGION_CreateRegion(d))) return 0;
805 if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
806 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
807 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
809 /* Ellipse algorithm, based on an article by K. Porter */
810 /* in DDJ Graphics Programming Column, 8/89 */
812 asq = ellipse_width * ellipse_width / 4; /* a^2 */
813 bsq = ellipse_height * ellipse_height / 4; /* b^2 */
814 d = bsq - asq * ellipse_height / 2 + asq / 4; /* b^2 - a^2b + a^2/4 */
815 xd = 0;
816 yd = asq * ellipse_height; /* 2a^2b */
818 rect.left = left + ellipse_width / 2;
819 rect.right = right - ellipse_width / 2;
821 /* Loop to draw first half of quadrant */
823 while (xd < yd)
825 if (d > 0) /* if nearest pixel is toward the center */
827 /* move toward center */
828 rect.top = top++;
829 rect.bottom = rect.top + 1;
830 REGION_UnionRectWithRegion( &rect, obj->rgn );
831 rect.top = --bottom;
832 rect.bottom = rect.top + 1;
833 REGION_UnionRectWithRegion( &rect, obj->rgn );
834 yd -= 2*asq;
835 d -= yd;
837 rect.left--; /* next horiz point */
838 rect.right++;
839 xd += 2*bsq;
840 d += bsq + xd;
843 /* Loop to draw second half of quadrant */
845 d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
846 while (yd >= 0)
848 /* next vertical point */
849 rect.top = top++;
850 rect.bottom = rect.top + 1;
851 REGION_UnionRectWithRegion( &rect, obj->rgn );
852 rect.top = --bottom;
853 rect.bottom = rect.top + 1;
854 REGION_UnionRectWithRegion( &rect, obj->rgn );
855 if (d < 0) /* if nearest pixel is outside ellipse */
857 rect.left--; /* move away from center */
858 rect.right++;
859 xd += 2*bsq;
860 d += xd;
862 yd -= 2*asq;
863 d += asq - yd;
866 /* Add the inside rectangle */
868 if (top <= bottom)
870 rect.top = top;
871 rect.bottom = bottom;
872 REGION_UnionRectWithRegion( &rect, obj->rgn );
874 GDI_ReleaseObj( hrgn );
875 return hrgn;
879 /***********************************************************************
880 * CreateEllipticRgn (GDI32.@)
882 * Creates an elliptical region.
884 * PARAMS
885 * left [I] Left coordinate of bounding rectangle.
886 * top [I] Top coordinate of bounding rectangle.
887 * right [I] Right coordinate of bounding rectangle.
888 * bottom [I] Bottom coordinate of bounding rectangle.
890 * RETURNS
891 * Success: Handle to region.
892 * Failure: NULL.
894 * NOTES
895 * This is a special case of CreateRoundRectRgn() where the width of the
896 * ellipse at each corner is equal to the width the rectangle and
897 * the same for the height.
899 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
900 INT right, INT bottom )
902 return CreateRoundRectRgn( left, top, right, bottom,
903 right-left, bottom-top );
907 /***********************************************************************
908 * CreateEllipticRgnIndirect (GDI32.@)
910 * Creates an elliptical region.
912 * PARAMS
913 * rect [I] Pointer to bounding rectangle of the ellipse.
915 * RETURNS
916 * Success: Handle to region.
917 * Failure: NULL.
919 * NOTES
920 * This is a special case of CreateRoundRectRgn() where the width of the
921 * ellipse at each corner is equal to the width the rectangle and
922 * the same for the height.
924 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
926 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
927 rect->bottom, rect->right - rect->left,
928 rect->bottom - rect->top );
931 /***********************************************************************
932 * GetRegionData (GDI32.@)
934 * Retrieves the data that specifies the region.
936 * PARAMS
937 * hrgn [I] Region to retrieve the region data from.
938 * count [I] The size of the buffer pointed to by rgndata in bytes.
939 * rgndata [I] The buffer to receive data about the region.
941 * RETURNS
942 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
943 * the number of bytes copied to the output buffer.
944 * Failure: 0.
946 * NOTES
947 * The format of the Buffer member of RGNDATA is determined by the iType
948 * member of the region data header.
949 * Currently this is always RDH_RECTANGLES, which specifies that the format
950 * is the array of RECT's that specify the region. The length of the array
951 * is specified by the nCount member of the region data header.
953 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
955 DWORD size;
956 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
958 TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
960 if(!obj) return 0;
962 size = obj->rgn->numRects * sizeof(RECT);
963 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
965 GDI_ReleaseObj( hrgn );
966 if (rgndata) /* buffer is too small, signal it by return 0 */
967 return 0;
968 else /* user requested buffer size with rgndata NULL */
969 return size + sizeof(RGNDATAHEADER);
972 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
973 rgndata->rdh.iType = RDH_RECTANGLES;
974 rgndata->rdh.nCount = obj->rgn->numRects;
975 rgndata->rdh.nRgnSize = size;
976 rgndata->rdh.rcBound.left = obj->rgn->extents.left;
977 rgndata->rdh.rcBound.top = obj->rgn->extents.top;
978 rgndata->rdh.rcBound.right = obj->rgn->extents.right;
979 rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
981 memcpy( rgndata->Buffer, obj->rgn->rects, size );
983 GDI_ReleaseObj( hrgn );
984 return size + sizeof(RGNDATAHEADER);
988 static void translate( POINT *pt, UINT count, const XFORM *xform )
990 while (count--)
992 double x = pt->x;
993 double y = pt->y;
994 pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
995 pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
996 pt++;
1001 /***********************************************************************
1002 * ExtCreateRegion (GDI32.@)
1004 * Creates a region as specified by the transformation data and region data.
1006 * PARAMS
1007 * lpXform [I] World-space to logical-space transformation data.
1008 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
1009 * rgndata [I] Data that specifies the region.
1011 * RETURNS
1012 * Success: Handle to region.
1013 * Failure: NULL.
1015 * NOTES
1016 * See GetRegionData().
1018 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
1020 HRGN hrgn;
1022 TRACE(" %p %d %p\n", lpXform, dwCount, rgndata );
1024 if (!rgndata)
1026 SetLastError( ERROR_INVALID_PARAMETER );
1027 return 0;
1030 if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
1031 return 0;
1033 /* XP doesn't care about the type */
1034 if( rgndata->rdh.iType != RDH_RECTANGLES )
1035 WARN("(Unsupported region data type: %u)\n", rgndata->rdh.iType);
1037 if (lpXform)
1039 RECT *pCurRect, *pEndRect;
1041 hrgn = CreateRectRgn( 0, 0, 0, 0 );
1043 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1044 for (pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1046 static const INT count = 4;
1047 HRGN poly_hrgn;
1048 POINT pt[4];
1050 pt[0].x = pCurRect->left;
1051 pt[0].y = pCurRect->top;
1052 pt[1].x = pCurRect->right;
1053 pt[1].y = pCurRect->top;
1054 pt[2].x = pCurRect->right;
1055 pt[2].y = pCurRect->bottom;
1056 pt[3].x = pCurRect->left;
1057 pt[3].y = pCurRect->bottom;
1059 translate( pt, 4, lpXform );
1060 poly_hrgn = CreatePolyPolygonRgn( pt, &count, 1, WINDING );
1061 CombineRgn( hrgn, hrgn, poly_hrgn, RGN_OR );
1062 DeleteObject( poly_hrgn );
1064 return hrgn;
1067 if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
1069 RECT *pCurRect, *pEndRect;
1070 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
1072 if (obj) {
1073 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1074 for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
1076 if (pCurRect->left < pCurRect->right && pCurRect->top < pCurRect->bottom)
1077 REGION_UnionRectWithRegion( pCurRect, obj->rgn );
1079 GDI_ReleaseObj( hrgn );
1081 TRACE("-- %p\n", hrgn );
1082 return hrgn;
1084 else ERR("Could not get pointer to newborn Region!\n");
1087 return 0;
1091 /***********************************************************************
1092 * PtInRegion (GDI32.@)
1094 * Tests whether the specified point is inside a region.
1096 * PARAMS
1097 * hrgn [I] Region to test.
1098 * x [I] X-coordinate of point to test.
1099 * y [I] Y-coordinate of point to test.
1101 * RETURNS
1102 * Non-zero if the point is inside the region or zero otherwise.
1104 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
1106 RGNOBJ * obj;
1107 BOOL ret = FALSE;
1109 if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
1111 int i;
1113 if (obj->rgn->numRects > 0 && INRECT(obj->rgn->extents, x, y))
1114 for (i = 0; i < obj->rgn->numRects; i++)
1115 if (INRECT (obj->rgn->rects[i], x, y))
1117 ret = TRUE;
1118 break;
1120 GDI_ReleaseObj( hrgn );
1122 return ret;
1126 /***********************************************************************
1127 * RectInRegion (GDI32.@)
1129 * Tests if a rectangle is at least partly inside the specified region.
1131 * PARAMS
1132 * hrgn [I] Region to test.
1133 * rect [I] Rectangle to test.
1135 * RETURNS
1136 * Non-zero if the rectangle is partially inside the region or
1137 * zero otherwise.
1139 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
1141 RGNOBJ * obj;
1142 BOOL ret = FALSE;
1144 if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
1146 RECT *pCurRect, *pRectEnd;
1148 /* this is (just) a useful optimization */
1149 if ((obj->rgn->numRects > 0) && EXTENTCHECK(&obj->rgn->extents,
1150 rect))
1152 for (pCurRect = obj->rgn->rects, pRectEnd = pCurRect +
1153 obj->rgn->numRects; pCurRect < pRectEnd; pCurRect++)
1155 if (pCurRect->bottom <= rect->top)
1156 continue; /* not far enough down yet */
1158 if (pCurRect->top >= rect->bottom)
1159 break; /* too far down */
1161 if (pCurRect->right <= rect->left)
1162 continue; /* not far enough over yet */
1164 if (pCurRect->left >= rect->right) {
1165 continue;
1168 ret = TRUE;
1169 break;
1172 GDI_ReleaseObj(hrgn);
1174 return ret;
1177 /***********************************************************************
1178 * EqualRgn (GDI32.@)
1180 * Tests whether one region is identical to another.
1182 * PARAMS
1183 * hrgn1 [I] The first region to compare.
1184 * hrgn2 [I] The second region to compare.
1186 * RETURNS
1187 * Non-zero if both regions are identical or zero otherwise.
1189 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1191 RGNOBJ *obj1, *obj2;
1192 BOOL ret = FALSE;
1194 if ((obj1 = (RGNOBJ *) GDI_GetObjPtr( hrgn1, REGION_MAGIC )))
1196 if ((obj2 = (RGNOBJ *) GDI_GetObjPtr( hrgn2, REGION_MAGIC )))
1198 int i;
1200 if ( obj1->rgn->numRects != obj2->rgn->numRects ) goto done;
1201 if ( obj1->rgn->numRects == 0 )
1203 ret = TRUE;
1204 goto done;
1207 if (obj1->rgn->extents.left != obj2->rgn->extents.left) goto done;
1208 if (obj1->rgn->extents.right != obj2->rgn->extents.right) goto done;
1209 if (obj1->rgn->extents.top != obj2->rgn->extents.top) goto done;
1210 if (obj1->rgn->extents.bottom != obj2->rgn->extents.bottom) goto done;
1211 for( i = 0; i < obj1->rgn->numRects; i++ )
1213 if (obj1->rgn->rects[i].left != obj2->rgn->rects[i].left) goto done;
1214 if (obj1->rgn->rects[i].right != obj2->rgn->rects[i].right) goto done;
1215 if (obj1->rgn->rects[i].top != obj2->rgn->rects[i].top) goto done;
1216 if (obj1->rgn->rects[i].bottom != obj2->rgn->rects[i].bottom) goto done;
1218 ret = TRUE;
1219 done:
1220 GDI_ReleaseObj(hrgn2);
1222 GDI_ReleaseObj(hrgn1);
1224 return ret;
1227 /***********************************************************************
1228 * REGION_UnionRectWithRegion
1229 * Adds a rectangle to a WINEREGION
1231 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1233 WINEREGION region;
1235 region.rects = &region.extents;
1236 region.numRects = 1;
1237 region.size = 1;
1238 region.extents = *rect;
1239 REGION_UnionRegion(rgn, rgn, &region);
1243 /***********************************************************************
1244 * REGION_CreateFrameRgn
1246 * Create a region that is a frame around another region.
1247 * Compute the intersection of the region moved in all 4 directions
1248 * ( +x, -x, +y, -y) and subtract from the original.
1249 * The result looks slightly better than in Windows :)
1251 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1253 BOOL bRet;
1254 RGNOBJ *srcObj = (RGNOBJ*) GDI_GetObjPtr( hSrc, REGION_MAGIC );
1256 if (!srcObj) return FALSE;
1257 if (srcObj->rgn->numRects != 0)
1259 RGNOBJ* destObj = (RGNOBJ*) GDI_GetObjPtr( hDest, REGION_MAGIC );
1260 WINEREGION *tmprgn = REGION_AllocWineRegion( srcObj->rgn->numRects);
1262 REGION_OffsetRegion( destObj->rgn, srcObj->rgn, -x, 0);
1263 REGION_OffsetRegion( tmprgn, srcObj->rgn, x, 0);
1264 REGION_IntersectRegion( destObj->rgn, destObj->rgn, tmprgn);
1265 REGION_OffsetRegion( tmprgn, srcObj->rgn, 0, -y);
1266 REGION_IntersectRegion( destObj->rgn, destObj->rgn, tmprgn);
1267 REGION_OffsetRegion( tmprgn, srcObj->rgn, 0, y);
1268 REGION_IntersectRegion( destObj->rgn, destObj->rgn, tmprgn);
1269 REGION_SubtractRegion( destObj->rgn, srcObj->rgn, destObj->rgn);
1271 REGION_DestroyWineRegion(tmprgn);
1272 GDI_ReleaseObj ( hDest );
1273 bRet = TRUE;
1275 else
1276 bRet = FALSE;
1277 GDI_ReleaseObj( hSrc );
1278 return bRet;
1282 /***********************************************************************
1283 * CombineRgn (GDI32.@)
1285 * Combines two regions with the specified operation and stores the result
1286 * in the specified destination region.
1288 * PARAMS
1289 * hDest [I] The region that receives the combined result.
1290 * hSrc1 [I] The first source region.
1291 * hSrc2 [I] The second source region.
1292 * mode [I] The way in which the source regions will be combined. See notes.
1294 * RETURNS
1295 * Success:
1296 * NULLREGION - The new region is empty.
1297 * SIMPLEREGION - The new region can be represented by one rectangle.
1298 * COMPLEXREGION - The new region can only be represented by more than
1299 * one rectangle.
1300 * Failure: ERROR
1302 * NOTES
1303 * The two source regions can be the same region.
1304 * The mode can be one of the following:
1305 *| RGN_AND - Intersection of the regions
1306 *| RGN_OR - Union of the regions
1307 *| RGN_XOR - Unions of the regions minus any intersection.
1308 *| RGN_DIFF - Difference (subtraction) of the regions.
1310 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1312 RGNOBJ *destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC);
1313 INT result = ERROR;
1315 TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1316 if (destObj)
1318 RGNOBJ *src1Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc1, REGION_MAGIC);
1320 if (src1Obj)
1322 TRACE("dump src1Obj:\n");
1323 if(TRACE_ON(region))
1324 REGION_DumpRegion(src1Obj->rgn);
1325 if (mode == RGN_COPY)
1327 REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
1328 result = get_region_type( destObj );
1330 else
1332 RGNOBJ *src2Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc2, REGION_MAGIC);
1334 if (src2Obj)
1336 TRACE("dump src2Obj:\n");
1337 if(TRACE_ON(region))
1338 REGION_DumpRegion(src2Obj->rgn);
1339 switch (mode)
1341 case RGN_AND:
1342 REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
1343 break;
1344 case RGN_OR:
1345 REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1346 break;
1347 case RGN_XOR:
1348 REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1349 break;
1350 case RGN_DIFF:
1351 REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1352 break;
1354 result = get_region_type( destObj );
1355 GDI_ReleaseObj( hSrc2 );
1358 GDI_ReleaseObj( hSrc1 );
1360 TRACE("dump destObj:\n");
1361 if(TRACE_ON(region))
1362 REGION_DumpRegion(destObj->rgn);
1364 GDI_ReleaseObj( hDest );
1365 } else {
1366 ERR("Invalid rgn=%p\n", hDest);
1368 return result;
1371 /***********************************************************************
1372 * REGION_SetExtents
1373 * Re-calculate the extents of a region
1375 static void REGION_SetExtents (WINEREGION *pReg)
1377 RECT *pRect, *pRectEnd, *pExtents;
1379 if (pReg->numRects == 0)
1381 pReg->extents.left = 0;
1382 pReg->extents.top = 0;
1383 pReg->extents.right = 0;
1384 pReg->extents.bottom = 0;
1385 return;
1388 pExtents = &pReg->extents;
1389 pRect = pReg->rects;
1390 pRectEnd = &pRect[pReg->numRects - 1];
1393 * Since pRect is the first rectangle in the region, it must have the
1394 * smallest top and since pRectEnd is the last rectangle in the region,
1395 * it must have the largest bottom, because of banding. Initialize left and
1396 * right from pRect and pRectEnd, resp., as good things to initialize them
1397 * to...
1399 pExtents->left = pRect->left;
1400 pExtents->top = pRect->top;
1401 pExtents->right = pRectEnd->right;
1402 pExtents->bottom = pRectEnd->bottom;
1404 while (pRect <= pRectEnd)
1406 if (pRect->left < pExtents->left)
1407 pExtents->left = pRect->left;
1408 if (pRect->right > pExtents->right)
1409 pExtents->right = pRect->right;
1410 pRect++;
1414 /***********************************************************************
1415 * REGION_CopyRegion
1417 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1419 if (dst != src) /* don't want to copy to itself */
1421 if (dst->size < src->numRects)
1423 if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1424 src->numRects * sizeof(RECT) )))
1425 return;
1426 dst->size = src->numRects;
1428 dst->numRects = src->numRects;
1429 dst->extents.left = src->extents.left;
1430 dst->extents.top = src->extents.top;
1431 dst->extents.right = src->extents.right;
1432 dst->extents.bottom = src->extents.bottom;
1433 memcpy((char *) dst->rects, (char *) src->rects,
1434 (int) (src->numRects * sizeof(RECT)));
1436 return;
1439 /***********************************************************************
1440 * REGION_Coalesce
1442 * Attempt to merge the rects in the current band with those in the
1443 * previous one. Used only by REGION_RegionOp.
1445 * Results:
1446 * The new index for the previous band.
1448 * Side Effects:
1449 * If coalescing takes place:
1450 * - rectangles in the previous band will have their bottom fields
1451 * altered.
1452 * - pReg->numRects will be decreased.
1455 static INT REGION_Coalesce (
1456 WINEREGION *pReg, /* Region to coalesce */
1457 INT prevStart, /* Index of start of previous band */
1458 INT curStart /* Index of start of current band */
1460 RECT *pPrevRect; /* Current rect in previous band */
1461 RECT *pCurRect; /* Current rect in current band */
1462 RECT *pRegEnd; /* End of region */
1463 INT curNumRects; /* Number of rectangles in current band */
1464 INT prevNumRects; /* Number of rectangles in previous band */
1465 INT bandtop; /* top coordinate for current band */
1467 pRegEnd = &pReg->rects[pReg->numRects];
1469 pPrevRect = &pReg->rects[prevStart];
1470 prevNumRects = curStart - prevStart;
1473 * Figure out how many rectangles are in the current band. Have to do
1474 * this because multiple bands could have been added in REGION_RegionOp
1475 * at the end when one region has been exhausted.
1477 pCurRect = &pReg->rects[curStart];
1478 bandtop = pCurRect->top;
1479 for (curNumRects = 0;
1480 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1481 curNumRects++)
1483 pCurRect++;
1486 if (pCurRect != pRegEnd)
1489 * If more than one band was added, we have to find the start
1490 * of the last band added so the next coalescing job can start
1491 * at the right place... (given when multiple bands are added,
1492 * this may be pointless -- see above).
1494 pRegEnd--;
1495 while (pRegEnd[-1].top == pRegEnd->top)
1497 pRegEnd--;
1499 curStart = pRegEnd - pReg->rects;
1500 pRegEnd = pReg->rects + pReg->numRects;
1503 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1504 pCurRect -= curNumRects;
1506 * The bands may only be coalesced if the bottom of the previous
1507 * matches the top scanline of the current.
1509 if (pPrevRect->bottom == pCurRect->top)
1512 * Make sure the bands have rects in the same places. This
1513 * assumes that rects have been added in such a way that they
1514 * cover the most area possible. I.e. two rects in a band must
1515 * have some horizontal space between them.
1519 if ((pPrevRect->left != pCurRect->left) ||
1520 (pPrevRect->right != pCurRect->right))
1523 * The bands don't line up so they can't be coalesced.
1525 return (curStart);
1527 pPrevRect++;
1528 pCurRect++;
1529 prevNumRects -= 1;
1530 } while (prevNumRects != 0);
1532 pReg->numRects -= curNumRects;
1533 pCurRect -= curNumRects;
1534 pPrevRect -= curNumRects;
1537 * The bands may be merged, so set the bottom of each rect
1538 * in the previous band to that of the corresponding rect in
1539 * the current band.
1543 pPrevRect->bottom = pCurRect->bottom;
1544 pPrevRect++;
1545 pCurRect++;
1546 curNumRects -= 1;
1547 } while (curNumRects != 0);
1550 * If only one band was added to the region, we have to backup
1551 * curStart to the start of the previous band.
1553 * If more than one band was added to the region, copy the
1554 * other bands down. The assumption here is that the other bands
1555 * came from the same region as the current one and no further
1556 * coalescing can be done on them since it's all been done
1557 * already... curStart is already in the right place.
1559 if (pCurRect == pRegEnd)
1561 curStart = prevStart;
1563 else
1567 *pPrevRect++ = *pCurRect++;
1568 } while (pCurRect != pRegEnd);
1573 return (curStart);
1576 /***********************************************************************
1577 * REGION_RegionOp
1579 * Apply an operation to two regions. Called by REGION_Union,
1580 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1582 * Results:
1583 * None.
1585 * Side Effects:
1586 * The new region is overwritten.
1588 * Notes:
1589 * The idea behind this function is to view the two regions as sets.
1590 * Together they cover a rectangle of area that this function divides
1591 * into horizontal bands where points are covered only by one region
1592 * or by both. For the first case, the nonOverlapFunc is called with
1593 * each the band and the band's upper and lower extents. For the
1594 * second, the overlapFunc is called to process the entire band. It
1595 * is responsible for clipping the rectangles in the band, though
1596 * this function provides the boundaries.
1597 * At the end of each band, the new region is coalesced, if possible,
1598 * to reduce the number of rectangles in the region.
1601 static void REGION_RegionOp(
1602 WINEREGION *newReg, /* Place to store result */
1603 WINEREGION *reg1, /* First region in operation */
1604 WINEREGION *reg2, /* 2nd region in operation */
1605 void (*overlapFunc)(WINEREGION*, RECT*, RECT*, RECT*, RECT*, INT, INT), /* Function to call for over-lapping bands */
1606 void (*nonOverlap1Func)(WINEREGION*, RECT*, RECT*, INT, INT), /* Function to call for non-overlapping bands in region 1 */
1607 void (*nonOverlap2Func)(WINEREGION*, RECT*, RECT*, INT, INT) /* Function to call for non-overlapping bands in region 2 */
1609 RECT *r1; /* Pointer into first region */
1610 RECT *r2; /* Pointer into 2d region */
1611 RECT *r1End; /* End of 1st region */
1612 RECT *r2End; /* End of 2d region */
1613 INT ybot; /* Bottom of intersection */
1614 INT ytop; /* Top of intersection */
1615 RECT *oldRects; /* Old rects for newReg */
1616 INT prevBand; /* Index of start of
1617 * previous band in newReg */
1618 INT curBand; /* Index of start of current
1619 * band in newReg */
1620 RECT *r1BandEnd; /* End of current band in r1 */
1621 RECT *r2BandEnd; /* End of current band in r2 */
1622 INT top; /* Top of non-overlapping band */
1623 INT bot; /* Bottom of non-overlapping band */
1626 * Initialization:
1627 * set r1, r2, r1End and r2End appropriately, preserve the important
1628 * parts of the destination region until the end in case it's one of
1629 * the two source regions, then mark the "new" region empty, allocating
1630 * another array of rectangles for it to use.
1632 r1 = reg1->rects;
1633 r2 = reg2->rects;
1634 r1End = r1 + reg1->numRects;
1635 r2End = r2 + reg2->numRects;
1639 * newReg may be one of the src regions so we can't empty it. We keep a
1640 * note of its rects pointer (so that we can free them later), preserve its
1641 * extents and simply set numRects to zero.
1644 oldRects = newReg->rects;
1645 newReg->numRects = 0;
1648 * Allocate a reasonable number of rectangles for the new region. The idea
1649 * is to allocate enough so the individual functions don't need to
1650 * reallocate and copy the array, which is time consuming, yet we don't
1651 * have to worry about using too much memory. I hope to be able to
1652 * nuke the Xrealloc() at the end of this function eventually.
1654 newReg->size = max(reg1->numRects,reg2->numRects) * 2;
1656 if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1657 sizeof(RECT) * newReg->size )))
1659 newReg->size = 0;
1660 return;
1664 * Initialize ybot and ytop.
1665 * In the upcoming loop, ybot and ytop serve different functions depending
1666 * on whether the band being handled is an overlapping or non-overlapping
1667 * band.
1668 * In the case of a non-overlapping band (only one of the regions
1669 * has points in the band), ybot is the bottom of the most recent
1670 * intersection and thus clips the top of the rectangles in that band.
1671 * ytop is the top of the next intersection between the two regions and
1672 * serves to clip the bottom of the rectangles in the current band.
1673 * For an overlapping band (where the two regions intersect), ytop clips
1674 * the top of the rectangles of both regions and ybot clips the bottoms.
1676 if (reg1->extents.top < reg2->extents.top)
1677 ybot = reg1->extents.top;
1678 else
1679 ybot = reg2->extents.top;
1682 * prevBand serves to mark the start of the previous band so rectangles
1683 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1684 * In the beginning, there is no previous band, so prevBand == curBand
1685 * (curBand is set later on, of course, but the first band will always
1686 * start at index 0). prevBand and curBand must be indices because of
1687 * the possible expansion, and resultant moving, of the new region's
1688 * array of rectangles.
1690 prevBand = 0;
1694 curBand = newReg->numRects;
1697 * This algorithm proceeds one source-band (as opposed to a
1698 * destination band, which is determined by where the two regions
1699 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1700 * rectangle after the last one in the current band for their
1701 * respective regions.
1703 r1BandEnd = r1;
1704 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1706 r1BandEnd++;
1709 r2BandEnd = r2;
1710 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1712 r2BandEnd++;
1716 * First handle the band that doesn't intersect, if any.
1718 * Note that attention is restricted to one band in the
1719 * non-intersecting region at once, so if a region has n
1720 * bands between the current position and the next place it overlaps
1721 * the other, this entire loop will be passed through n times.
1723 if (r1->top < r2->top)
1725 top = max(r1->top,ybot);
1726 bot = min(r1->bottom,r2->top);
1728 if ((top != bot) && (nonOverlap1Func != NULL))
1730 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1733 ytop = r2->top;
1735 else if (r2->top < r1->top)
1737 top = max(r2->top,ybot);
1738 bot = min(r2->bottom,r1->top);
1740 if ((top != bot) && (nonOverlap2Func != NULL))
1742 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1745 ytop = r1->top;
1747 else
1749 ytop = r1->top;
1753 * If any rectangles got added to the region, try and coalesce them
1754 * with rectangles from the previous band. Note we could just do
1755 * this test in miCoalesce, but some machines incur a not
1756 * inconsiderable cost for function calls, so...
1758 if (newReg->numRects != curBand)
1760 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1764 * Now see if we've hit an intersecting band. The two bands only
1765 * intersect if ybot > ytop
1767 ybot = min(r1->bottom, r2->bottom);
1768 curBand = newReg->numRects;
1769 if (ybot > ytop)
1771 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1775 if (newReg->numRects != curBand)
1777 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1781 * If we've finished with a band (bottom == ybot) we skip forward
1782 * in the region to the next band.
1784 if (r1->bottom == ybot)
1786 r1 = r1BandEnd;
1788 if (r2->bottom == ybot)
1790 r2 = r2BandEnd;
1792 } while ((r1 != r1End) && (r2 != r2End));
1795 * Deal with whichever region still has rectangles left.
1797 curBand = newReg->numRects;
1798 if (r1 != r1End)
1800 if (nonOverlap1Func != NULL)
1804 r1BandEnd = r1;
1805 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1807 r1BandEnd++;
1809 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1810 max(r1->top,ybot), r1->bottom);
1811 r1 = r1BandEnd;
1812 } while (r1 != r1End);
1815 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1819 r2BandEnd = r2;
1820 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1822 r2BandEnd++;
1824 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1825 max(r2->top,ybot), r2->bottom);
1826 r2 = r2BandEnd;
1827 } while (r2 != r2End);
1830 if (newReg->numRects != curBand)
1832 (void) REGION_Coalesce (newReg, prevBand, curBand);
1836 * A bit of cleanup. To keep regions from growing without bound,
1837 * we shrink the array of rectangles to match the new number of
1838 * rectangles in the region. This never goes to 0, however...
1840 * Only do this stuff if the number of rectangles allocated is more than
1841 * twice the number of rectangles in the region (a simple optimization...).
1843 if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1845 if (REGION_NOT_EMPTY(newReg))
1847 RECT *prev_rects = newReg->rects;
1848 newReg->size = newReg->numRects;
1849 newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1850 sizeof(RECT) * newReg->size );
1851 if (! newReg->rects)
1852 newReg->rects = prev_rects;
1854 else
1857 * No point in doing the extra work involved in an Xrealloc if
1858 * the region is empty
1860 newReg->size = 1;
1861 HeapFree( GetProcessHeap(), 0, newReg->rects );
1862 newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
1865 HeapFree( GetProcessHeap(), 0, oldRects );
1866 return;
1869 /***********************************************************************
1870 * Region Intersection
1871 ***********************************************************************/
1874 /***********************************************************************
1875 * REGION_IntersectO
1877 * Handle an overlapping band for REGION_Intersect.
1879 * Results:
1880 * None.
1882 * Side Effects:
1883 * Rectangles may be added to the region.
1886 static void REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1887 RECT *r2, RECT *r2End, INT top, INT bottom)
1890 INT left, right;
1891 RECT *pNextRect;
1893 pNextRect = &pReg->rects[pReg->numRects];
1895 while ((r1 != r1End) && (r2 != r2End))
1897 left = max(r1->left, r2->left);
1898 right = min(r1->right, r2->right);
1901 * If there's any overlap between the two rectangles, add that
1902 * overlap to the new region.
1903 * There's no need to check for subsumption because the only way
1904 * such a need could arise is if some region has two rectangles
1905 * right next to each other. Since that should never happen...
1907 if (left < right)
1909 MEMCHECK(pReg, pNextRect, pReg->rects);
1910 pNextRect->left = left;
1911 pNextRect->top = top;
1912 pNextRect->right = right;
1913 pNextRect->bottom = bottom;
1914 pReg->numRects += 1;
1915 pNextRect++;
1919 * Need to advance the pointers. Shift the one that extends
1920 * to the right the least, since the other still has a chance to
1921 * overlap with that region's next rectangle, if you see what I mean.
1923 if (r1->right < r2->right)
1925 r1++;
1927 else if (r2->right < r1->right)
1929 r2++;
1931 else
1933 r1++;
1934 r2++;
1937 return;
1940 /***********************************************************************
1941 * REGION_IntersectRegion
1943 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1944 WINEREGION *reg2)
1946 /* check for trivial reject */
1947 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1948 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
1949 newReg->numRects = 0;
1950 else
1951 REGION_RegionOp (newReg, reg1, reg2, REGION_IntersectO, NULL, NULL);
1954 * Can't alter newReg's extents before we call miRegionOp because
1955 * it might be one of the source regions and miRegionOp depends
1956 * on the extents of those regions being the same. Besides, this
1957 * way there's no checking against rectangles that will be nuked
1958 * due to coalescing, so we have to examine fewer rectangles.
1960 REGION_SetExtents(newReg);
1963 /***********************************************************************
1964 * Region Union
1965 ***********************************************************************/
1967 /***********************************************************************
1968 * REGION_UnionNonO
1970 * Handle a non-overlapping band for the union operation. Just
1971 * Adds the rectangles into the region. Doesn't have to check for
1972 * subsumption or anything.
1974 * Results:
1975 * None.
1977 * Side Effects:
1978 * pReg->numRects is incremented and the final rectangles overwritten
1979 * with the rectangles we're passed.
1982 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1983 INT top, INT bottom)
1985 RECT *pNextRect;
1987 pNextRect = &pReg->rects[pReg->numRects];
1989 while (r != rEnd)
1991 MEMCHECK(pReg, pNextRect, pReg->rects);
1992 pNextRect->left = r->left;
1993 pNextRect->top = top;
1994 pNextRect->right = r->right;
1995 pNextRect->bottom = bottom;
1996 pReg->numRects += 1;
1997 pNextRect++;
1998 r++;
2000 return;
2003 /***********************************************************************
2004 * REGION_UnionO
2006 * Handle an overlapping band for the union operation. Picks the
2007 * left-most rectangle each time and merges it into the region.
2009 * Results:
2010 * None.
2012 * Side Effects:
2013 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2014 * be changed.
2017 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2018 RECT *r2, RECT *r2End, INT top, INT bottom)
2020 RECT *pNextRect;
2022 pNextRect = &pReg->rects[pReg->numRects];
2024 #define MERGERECT(r) \
2025 if ((pReg->numRects != 0) && \
2026 (pNextRect[-1].top == top) && \
2027 (pNextRect[-1].bottom == bottom) && \
2028 (pNextRect[-1].right >= r->left)) \
2030 if (pNextRect[-1].right < r->right) \
2032 pNextRect[-1].right = r->right; \
2035 else \
2037 MEMCHECK(pReg, pNextRect, pReg->rects); \
2038 pNextRect->top = top; \
2039 pNextRect->bottom = bottom; \
2040 pNextRect->left = r->left; \
2041 pNextRect->right = r->right; \
2042 pReg->numRects += 1; \
2043 pNextRect += 1; \
2045 r++;
2047 while ((r1 != r1End) && (r2 != r2End))
2049 if (r1->left < r2->left)
2051 MERGERECT(r1);
2053 else
2055 MERGERECT(r2);
2059 if (r1 != r1End)
2063 MERGERECT(r1);
2064 } while (r1 != r1End);
2066 else while (r2 != r2End)
2068 MERGERECT(r2);
2070 return;
2073 /***********************************************************************
2074 * REGION_UnionRegion
2076 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
2077 WINEREGION *reg2)
2079 /* checks all the simple cases */
2082 * Region 1 and 2 are the same or region 1 is empty
2084 if ( (reg1 == reg2) || (!(reg1->numRects)) )
2086 if (newReg != reg2)
2087 REGION_CopyRegion(newReg, reg2);
2088 return;
2092 * if nothing to union (region 2 empty)
2094 if (!(reg2->numRects))
2096 if (newReg != reg1)
2097 REGION_CopyRegion(newReg, reg1);
2098 return;
2102 * Region 1 completely subsumes region 2
2104 if ((reg1->numRects == 1) &&
2105 (reg1->extents.left <= reg2->extents.left) &&
2106 (reg1->extents.top <= reg2->extents.top) &&
2107 (reg1->extents.right >= reg2->extents.right) &&
2108 (reg1->extents.bottom >= reg2->extents.bottom))
2110 if (newReg != reg1)
2111 REGION_CopyRegion(newReg, reg1);
2112 return;
2116 * Region 2 completely subsumes region 1
2118 if ((reg2->numRects == 1) &&
2119 (reg2->extents.left <= reg1->extents.left) &&
2120 (reg2->extents.top <= reg1->extents.top) &&
2121 (reg2->extents.right >= reg1->extents.right) &&
2122 (reg2->extents.bottom >= reg1->extents.bottom))
2124 if (newReg != reg2)
2125 REGION_CopyRegion(newReg, reg2);
2126 return;
2129 REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO, REGION_UnionNonO, REGION_UnionNonO);
2131 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2132 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2133 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2134 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2137 /***********************************************************************
2138 * Region Subtraction
2139 ***********************************************************************/
2141 /***********************************************************************
2142 * REGION_SubtractNonO1
2144 * Deal with non-overlapping band for subtraction. Any parts from
2145 * region 2 we discard. Anything from region 1 we add to the region.
2147 * Results:
2148 * None.
2150 * Side Effects:
2151 * pReg may be affected.
2154 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
2155 INT top, INT bottom)
2157 RECT *pNextRect;
2159 pNextRect = &pReg->rects[pReg->numRects];
2161 while (r != rEnd)
2163 MEMCHECK(pReg, pNextRect, pReg->rects);
2164 pNextRect->left = r->left;
2165 pNextRect->top = top;
2166 pNextRect->right = r->right;
2167 pNextRect->bottom = bottom;
2168 pReg->numRects += 1;
2169 pNextRect++;
2170 r++;
2172 return;
2176 /***********************************************************************
2177 * REGION_SubtractO
2179 * Overlapping band subtraction. x1 is the left-most point not yet
2180 * checked.
2182 * Results:
2183 * None.
2185 * Side Effects:
2186 * pReg may have rectangles added to it.
2189 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2190 RECT *r2, RECT *r2End, INT top, INT bottom)
2192 RECT *pNextRect;
2193 INT left;
2195 left = r1->left;
2196 pNextRect = &pReg->rects[pReg->numRects];
2198 while ((r1 != r1End) && (r2 != r2End))
2200 if (r2->right <= left)
2203 * Subtrahend missed the boat: go to next subtrahend.
2205 r2++;
2207 else if (r2->left <= left)
2210 * Subtrahend precedes minuend: nuke left edge of minuend.
2212 left = r2->right;
2213 if (left >= r1->right)
2216 * Minuend completely covered: advance to next minuend and
2217 * reset left fence to edge of new minuend.
2219 r1++;
2220 if (r1 != r1End)
2221 left = r1->left;
2223 else
2226 * Subtrahend now used up since it doesn't extend beyond
2227 * minuend
2229 r2++;
2232 else if (r2->left < r1->right)
2235 * Left part of subtrahend covers part of minuend: add uncovered
2236 * part of minuend to region and skip to next subtrahend.
2238 MEMCHECK(pReg, pNextRect, pReg->rects);
2239 pNextRect->left = left;
2240 pNextRect->top = top;
2241 pNextRect->right = r2->left;
2242 pNextRect->bottom = bottom;
2243 pReg->numRects += 1;
2244 pNextRect++;
2245 left = r2->right;
2246 if (left >= r1->right)
2249 * Minuend used up: advance to new...
2251 r1++;
2252 if (r1 != r1End)
2253 left = r1->left;
2255 else
2258 * Subtrahend used up
2260 r2++;
2263 else
2266 * Minuend used up: add any remaining piece before advancing.
2268 if (r1->right > left)
2270 MEMCHECK(pReg, pNextRect, pReg->rects);
2271 pNextRect->left = left;
2272 pNextRect->top = top;
2273 pNextRect->right = r1->right;
2274 pNextRect->bottom = bottom;
2275 pReg->numRects += 1;
2276 pNextRect++;
2278 r1++;
2279 left = r1->left;
2284 * Add remaining minuend rectangles to region.
2286 while (r1 != r1End)
2288 MEMCHECK(pReg, pNextRect, pReg->rects);
2289 pNextRect->left = left;
2290 pNextRect->top = top;
2291 pNextRect->right = r1->right;
2292 pNextRect->bottom = bottom;
2293 pReg->numRects += 1;
2294 pNextRect++;
2295 r1++;
2296 if (r1 != r1End)
2298 left = r1->left;
2301 return;
2304 /***********************************************************************
2305 * REGION_SubtractRegion
2307 * Subtract regS from regM and leave the result in regD.
2308 * S stands for subtrahend, M for minuend and D for difference.
2310 * Results:
2311 * TRUE.
2313 * Side Effects:
2314 * regD is overwritten.
2317 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
2318 WINEREGION *regS )
2320 /* check for trivial reject */
2321 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2322 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2324 REGION_CopyRegion(regD, regM);
2325 return;
2328 REGION_RegionOp (regD, regM, regS, REGION_SubtractO, REGION_SubtractNonO1, NULL);
2331 * Can't alter newReg's extents before we call miRegionOp because
2332 * it might be one of the source regions and miRegionOp depends
2333 * on the extents of those regions being the unaltered. Besides, this
2334 * way there's no checking against rectangles that will be nuked
2335 * due to coalescing, so we have to examine fewer rectangles.
2337 REGION_SetExtents (regD);
2340 /***********************************************************************
2341 * REGION_XorRegion
2343 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
2344 WINEREGION *srb)
2346 WINEREGION *tra, *trb;
2348 if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
2349 (! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
2350 return;
2351 REGION_SubtractRegion(tra,sra,srb);
2352 REGION_SubtractRegion(trb,srb,sra);
2353 REGION_UnionRegion(dr,tra,trb);
2354 REGION_DestroyWineRegion(tra);
2355 REGION_DestroyWineRegion(trb);
2356 return;
2359 /**************************************************************************
2361 * Poly Regions
2363 *************************************************************************/
2365 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2366 #define SMALL_COORDINATE 0x80000000
2368 /***********************************************************************
2369 * REGION_InsertEdgeInET
2371 * Insert the given edge into the edge table.
2372 * First we must find the correct bucket in the
2373 * Edge table, then find the right slot in the
2374 * bucket. Finally, we can insert it.
2377 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2378 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2381 EdgeTableEntry *start, *prev;
2382 ScanLineList *pSLL, *pPrevSLL;
2383 ScanLineListBlock *tmpSLLBlock;
2386 * find the right bucket to put the edge into
2388 pPrevSLL = &ET->scanlines;
2389 pSLL = pPrevSLL->next;
2390 while (pSLL && (pSLL->scanline < scanline))
2392 pPrevSLL = pSLL;
2393 pSLL = pSLL->next;
2397 * reassign pSLL (pointer to ScanLineList) if necessary
2399 if ((!pSLL) || (pSLL->scanline > scanline))
2401 if (*iSLLBlock > SLLSPERBLOCK-1)
2403 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2404 if(!tmpSLLBlock)
2406 WARN("Can't alloc SLLB\n");
2407 return;
2409 (*SLLBlock)->next = tmpSLLBlock;
2410 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
2411 *SLLBlock = tmpSLLBlock;
2412 *iSLLBlock = 0;
2414 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2416 pSLL->next = pPrevSLL->next;
2417 pSLL->edgelist = (EdgeTableEntry *)NULL;
2418 pPrevSLL->next = pSLL;
2420 pSLL->scanline = scanline;
2423 * now insert the edge in the right bucket
2425 prev = (EdgeTableEntry *)NULL;
2426 start = pSLL->edgelist;
2427 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2429 prev = start;
2430 start = start->next;
2432 ETE->next = start;
2434 if (prev)
2435 prev->next = ETE;
2436 else
2437 pSLL->edgelist = ETE;
2440 /***********************************************************************
2441 * REGION_CreateEdgeTable
2443 * This routine creates the edge table for
2444 * scan converting polygons.
2445 * The Edge Table (ET) looks like:
2447 * EdgeTable
2448 * --------
2449 * | ymax | ScanLineLists
2450 * |scanline|-->------------>-------------->...
2451 * -------- |scanline| |scanline|
2452 * |edgelist| |edgelist|
2453 * --------- ---------
2454 * | |
2455 * | |
2456 * V V
2457 * list of ETEs list of ETEs
2459 * where ETE is an EdgeTableEntry data structure,
2460 * and there is one ScanLineList per scanline at
2461 * which an edge is initially entered.
2464 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2465 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2466 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2468 const POINT *top, *bottom;
2469 const POINT *PrevPt, *CurrPt, *EndPt;
2470 INT poly, count;
2471 int iSLLBlock = 0;
2472 int dy;
2476 * initialize the Active Edge Table
2478 AET->next = (EdgeTableEntry *)NULL;
2479 AET->back = (EdgeTableEntry *)NULL;
2480 AET->nextWETE = (EdgeTableEntry *)NULL;
2481 AET->bres.minor_axis = SMALL_COORDINATE;
2484 * initialize the Edge Table.
2486 ET->scanlines.next = (ScanLineList *)NULL;
2487 ET->ymax = SMALL_COORDINATE;
2488 ET->ymin = LARGE_COORDINATE;
2489 pSLLBlock->next = (ScanLineListBlock *)NULL;
2491 EndPt = pts - 1;
2492 for(poly = 0; poly < nbpolygons; poly++)
2494 count = Count[poly];
2495 EndPt += count;
2496 if(count < 2)
2497 continue;
2499 PrevPt = EndPt;
2502 * for each vertex in the array of points.
2503 * In this loop we are dealing with two vertices at
2504 * a time -- these make up one edge of the polygon.
2506 while (count--)
2508 CurrPt = pts++;
2511 * find out which point is above and which is below.
2513 if (PrevPt->y > CurrPt->y)
2515 bottom = PrevPt, top = CurrPt;
2516 pETEs->ClockWise = 0;
2518 else
2520 bottom = CurrPt, top = PrevPt;
2521 pETEs->ClockWise = 1;
2525 * don't add horizontal edges to the Edge table.
2527 if (bottom->y != top->y)
2529 pETEs->ymax = bottom->y-1;
2530 /* -1 so we don't get last scanline */
2533 * initialize integer edge algorithm
2535 dy = bottom->y - top->y;
2536 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2538 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2539 &iSLLBlock);
2541 if (PrevPt->y > ET->ymax)
2542 ET->ymax = PrevPt->y;
2543 if (PrevPt->y < ET->ymin)
2544 ET->ymin = PrevPt->y;
2545 pETEs++;
2548 PrevPt = CurrPt;
2553 /***********************************************************************
2554 * REGION_loadAET
2556 * This routine moves EdgeTableEntries from the
2557 * EdgeTable into the Active Edge Table,
2558 * leaving them sorted by smaller x coordinate.
2561 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2563 EdgeTableEntry *pPrevAET;
2564 EdgeTableEntry *tmp;
2566 pPrevAET = AET;
2567 AET = AET->next;
2568 while (ETEs)
2570 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2572 pPrevAET = AET;
2573 AET = AET->next;
2575 tmp = ETEs->next;
2576 ETEs->next = AET;
2577 if (AET)
2578 AET->back = ETEs;
2579 ETEs->back = pPrevAET;
2580 pPrevAET->next = ETEs;
2581 pPrevAET = ETEs;
2583 ETEs = tmp;
2587 /***********************************************************************
2588 * REGION_computeWAET
2590 * This routine links the AET by the
2591 * nextWETE (winding EdgeTableEntry) link for
2592 * use by the winding number rule. The final
2593 * Active Edge Table (AET) might look something
2594 * like:
2596 * AET
2597 * ---------- --------- ---------
2598 * |ymax | |ymax | |ymax |
2599 * | ... | |... | |... |
2600 * |next |->|next |->|next |->...
2601 * |nextWETE| |nextWETE| |nextWETE|
2602 * --------- --------- ^--------
2603 * | | |
2604 * V-------------------> V---> ...
2607 static void REGION_computeWAET(EdgeTableEntry *AET)
2609 register EdgeTableEntry *pWETE;
2610 register int inside = 1;
2611 register int isInside = 0;
2613 AET->nextWETE = (EdgeTableEntry *)NULL;
2614 pWETE = AET;
2615 AET = AET->next;
2616 while (AET)
2618 if (AET->ClockWise)
2619 isInside++;
2620 else
2621 isInside--;
2623 if ((!inside && !isInside) ||
2624 ( inside && isInside))
2626 pWETE->nextWETE = AET;
2627 pWETE = AET;
2628 inside = !inside;
2630 AET = AET->next;
2632 pWETE->nextWETE = (EdgeTableEntry *)NULL;
2635 /***********************************************************************
2636 * REGION_InsertionSort
2638 * Just a simple insertion sort using
2639 * pointers and back pointers to sort the Active
2640 * Edge Table.
2643 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2645 EdgeTableEntry *pETEchase;
2646 EdgeTableEntry *pETEinsert;
2647 EdgeTableEntry *pETEchaseBackTMP;
2648 BOOL changed = FALSE;
2650 AET = AET->next;
2651 while (AET)
2653 pETEinsert = AET;
2654 pETEchase = AET;
2655 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2656 pETEchase = pETEchase->back;
2658 AET = AET->next;
2659 if (pETEchase != pETEinsert)
2661 pETEchaseBackTMP = pETEchase->back;
2662 pETEinsert->back->next = AET;
2663 if (AET)
2664 AET->back = pETEinsert->back;
2665 pETEinsert->next = pETEchase;
2666 pETEchase->back->next = pETEinsert;
2667 pETEchase->back = pETEinsert;
2668 pETEinsert->back = pETEchaseBackTMP;
2669 changed = TRUE;
2672 return changed;
2675 /***********************************************************************
2676 * REGION_FreeStorage
2678 * Clean up our act.
2680 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2682 ScanLineListBlock *tmpSLLBlock;
2684 while (pSLLBlock)
2686 tmpSLLBlock = pSLLBlock->next;
2687 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2688 pSLLBlock = tmpSLLBlock;
2693 /***********************************************************************
2694 * REGION_PtsToRegion
2696 * Create an array of rectangles from a list of points.
2698 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2699 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2701 RECT *rects;
2702 POINT *pts;
2703 POINTBLOCK *CurPtBlock;
2704 int i;
2705 RECT *extents;
2706 INT numRects;
2708 extents = &reg->extents;
2710 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2712 if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2713 sizeof(RECT) * numRects )))
2714 return(0);
2716 reg->size = numRects;
2717 CurPtBlock = FirstPtBlock;
2718 rects = reg->rects - 1;
2719 numRects = 0;
2720 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2722 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2723 /* the loop uses 2 points per iteration */
2724 i = NUMPTSTOBUFFER >> 1;
2725 if (!numFullPtBlocks)
2726 i = iCurPtBlock >> 1;
2727 for (pts = CurPtBlock->pts; i--; pts += 2) {
2728 if (pts->x == pts[1].x)
2729 continue;
2730 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2731 pts[1].x == rects->right &&
2732 (numRects == 1 || rects[-1].top != rects->top) &&
2733 (i && pts[2].y > pts[1].y)) {
2734 rects->bottom = pts[1].y + 1;
2735 continue;
2737 numRects++;
2738 rects++;
2739 rects->left = pts->x; rects->top = pts->y;
2740 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2741 if (rects->left < extents->left)
2742 extents->left = rects->left;
2743 if (rects->right > extents->right)
2744 extents->right = rects->right;
2746 CurPtBlock = CurPtBlock->next;
2749 if (numRects) {
2750 extents->top = reg->rects->top;
2751 extents->bottom = rects->bottom;
2752 } else {
2753 extents->left = 0;
2754 extents->top = 0;
2755 extents->right = 0;
2756 extents->bottom = 0;
2758 reg->numRects = numRects;
2760 return(TRUE);
2763 /***********************************************************************
2764 * CreatePolyPolygonRgn (GDI32.@)
2766 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2767 INT nbpolygons, INT mode)
2769 HRGN hrgn;
2770 RGNOBJ *obj;
2771 WINEREGION *region;
2772 register EdgeTableEntry *pAET; /* Active Edge Table */
2773 register INT y; /* current scanline */
2774 register int iPts = 0; /* number of pts in buffer */
2775 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2776 register ScanLineList *pSLL; /* current scanLineList */
2777 register POINT *pts; /* output buffer */
2778 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2779 EdgeTable ET; /* header node for ET */
2780 EdgeTableEntry AET; /* header node for AET */
2781 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2782 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2783 int fixWAET = FALSE;
2784 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2785 POINTBLOCK *tmpPtBlock;
2786 int numFullPtBlocks = 0;
2787 INT poly, total;
2789 TRACE("%p, count %d, polygons %d, mode %d\n", Pts, *Count, nbpolygons, mode);
2791 if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2792 return 0;
2793 obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
2794 region = obj->rgn;
2796 /* special case a rectangle */
2798 if (((nbpolygons == 1) && ((*Count == 4) ||
2799 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2800 (((Pts[0].y == Pts[1].y) &&
2801 (Pts[1].x == Pts[2].x) &&
2802 (Pts[2].y == Pts[3].y) &&
2803 (Pts[3].x == Pts[0].x)) ||
2804 ((Pts[0].x == Pts[1].x) &&
2805 (Pts[1].y == Pts[2].y) &&
2806 (Pts[2].x == Pts[3].x) &&
2807 (Pts[3].y == Pts[0].y))))
2809 SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2810 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2811 GDI_ReleaseObj( hrgn );
2812 return hrgn;
2815 for(poly = total = 0; poly < nbpolygons; poly++)
2816 total += Count[poly];
2817 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2819 REGION_DeleteObject( hrgn, obj );
2820 return 0;
2822 pts = FirstPtBlock.pts;
2823 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2824 pSLL = ET.scanlines.next;
2825 curPtBlock = &FirstPtBlock;
2827 if (mode != WINDING) {
2829 * for each scanline
2831 for (y = ET.ymin; y < ET.ymax; y++) {
2833 * Add a new edge to the active edge table when we
2834 * get to the next edge.
2836 if (pSLL != NULL && y == pSLL->scanline) {
2837 REGION_loadAET(&AET, pSLL->edgelist);
2838 pSLL = pSLL->next;
2840 pPrevAET = &AET;
2841 pAET = AET.next;
2844 * for each active edge
2846 while (pAET) {
2847 pts->x = pAET->bres.minor_axis, pts->y = y;
2848 pts++, iPts++;
2851 * send out the buffer
2853 if (iPts == NUMPTSTOBUFFER) {
2854 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2855 if(!tmpPtBlock) {
2856 WARN("Can't alloc tPB\n");
2857 HeapFree( GetProcessHeap(), 0, pETEs );
2858 return 0;
2860 curPtBlock->next = tmpPtBlock;
2861 curPtBlock = tmpPtBlock;
2862 pts = curPtBlock->pts;
2863 numFullPtBlocks++;
2864 iPts = 0;
2866 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2868 REGION_InsertionSort(&AET);
2871 else {
2873 * for each scanline
2875 for (y = ET.ymin; y < ET.ymax; y++) {
2877 * Add a new edge to the active edge table when we
2878 * get to the next edge.
2880 if (pSLL != NULL && y == pSLL->scanline) {
2881 REGION_loadAET(&AET, pSLL->edgelist);
2882 REGION_computeWAET(&AET);
2883 pSLL = pSLL->next;
2885 pPrevAET = &AET;
2886 pAET = AET.next;
2887 pWETE = pAET;
2890 * for each active edge
2892 while (pAET) {
2894 * add to the buffer only those edges that
2895 * are in the Winding active edge table.
2897 if (pWETE == pAET) {
2898 pts->x = pAET->bres.minor_axis, pts->y = y;
2899 pts++, iPts++;
2902 * send out the buffer
2904 if (iPts == NUMPTSTOBUFFER) {
2905 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2906 sizeof(POINTBLOCK) );
2907 if(!tmpPtBlock) {
2908 WARN("Can't alloc tPB\n");
2909 REGION_DeleteObject( hrgn, obj );
2910 HeapFree( GetProcessHeap(), 0, pETEs );
2911 return 0;
2913 curPtBlock->next = tmpPtBlock;
2914 curPtBlock = tmpPtBlock;
2915 pts = curPtBlock->pts;
2916 numFullPtBlocks++; iPts = 0;
2918 pWETE = pWETE->nextWETE;
2920 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2924 * recompute the winding active edge table if
2925 * we just resorted or have exited an edge.
2927 if (REGION_InsertionSort(&AET) || fixWAET) {
2928 REGION_computeWAET(&AET);
2929 fixWAET = FALSE;
2933 REGION_FreeStorage(SLLBlock.next);
2934 REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
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 GDI_ReleaseObj( hrgn );
2943 return hrgn;
2947 /***********************************************************************
2948 * CreatePolygonRgn (GDI32.@)
2950 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2951 INT mode )
2953 return CreatePolyPolygonRgn( points, &count, 1, mode );