2 * GDI region objects. Shamelessly ripped out from the X11 distribution
3 * Thanks for the nice licence.
5 * Copyright 1993, 1994, 1995 Alexandre Julliard
6 * Modifications and additions: Copyright 1998 Huw Davies
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 /************************************************************************
26 Copyright (c) 1987, 1988 X Consortium
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
70 ************************************************************************/
72 * The functions in this file implement the Region abstraction, similar to one
73 * used in the X11 sample server. A Region is simply an area, as the name
74 * implies, and is implemented as a "y-x-banded" array of rectangles. To
75 * explain: Each Region is made up of a certain number of rectangles sorted
76 * by y coordinate first, and then by x coordinate.
78 * Furthermore, the rectangles are banded such that every rectangle with a
79 * given upper-left y coordinate (y1) will have the same lower-right y
80 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81 * will span the entire vertical distance of the band. This means that some
82 * areas that could be merged into a taller rectangle will be represented as
83 * several shorter rectangles to account for shorter rectangles to its left
84 * or right but within its "vertical scope".
86 * An added constraint on the rectangles is that they must cover as much
87 * horizontal area as possible. E.g. no two rectangles in a band are allowed
90 * Whenever possible, bands will be merged together to cover a greater vertical
91 * distance (and thus reduce the number of rectangles). Two bands can be merged
92 * only if the bottom of one touches the top of the other and they have
93 * rectangles in the same places (of the same width, of course). This maintains
94 * the y-x-banding that's so nice to have...
102 #include "wine/debug.h"
104 WINE_DEFAULT_DEBUG_CHANNEL(region
);
113 /* GDI logical region object */
121 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, void *obj
, HDC hdc
);
122 static BOOL
REGION_DeleteObject( HGDIOBJ handle
, void *obj
);
124 static const struct gdi_obj_funcs region_funcs
=
126 REGION_SelectObject
, /* pSelectObject */
127 NULL
, /* pGetObject16 */
128 NULL
, /* pGetObjectA */
129 NULL
, /* pGetObjectW */
130 NULL
, /* pUnrealizeObject */
131 REGION_DeleteObject
/* pDeleteObject */
134 /* 1 if two RECTs overlap.
135 * 0 if two RECTs do not overlap.
137 #define EXTENTCHECK(r1, r2) \
138 ((r1)->right > (r2)->left && \
139 (r1)->left < (r2)->right && \
140 (r1)->bottom > (r2)->top && \
141 (r1)->top < (r2)->bottom)
144 * Check to see if there is enough memory in the present region.
147 static inline int xmemcheck(WINEREGION
*reg
, LPRECT
*rect
, LPRECT
*firstrect
) {
148 if (reg
->numRects
>= (reg
->size
- 1)) {
149 *firstrect
= HeapReAlloc( GetProcessHeap(), 0, *firstrect
, (2 * (sizeof(RECT
)) * (reg
->size
)));
153 *rect
= (*firstrect
)+reg
->numRects
;
158 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
160 #define EMPTY_REGION(pReg) { \
161 (pReg)->numRects = 0; \
162 (pReg)->extents.left = (pReg)->extents.top = 0; \
163 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
166 #define REGION_NOT_EMPTY(pReg) pReg->numRects
168 #define INRECT(r, x, y) \
169 ( ( ((r).right > x)) && \
170 ( ((r).left <= x)) && \
171 ( ((r).bottom > y)) && \
176 * number of points to buffer before sending them off
177 * to scanlines() : Must be an even number
179 #define NUMPTSTOBUFFER 200
182 * used to allocate buffers for points and link
183 * the buffers together
186 typedef struct _POINTBLOCK
{
187 POINT pts
[NUMPTSTOBUFFER
];
188 struct _POINTBLOCK
*next
;
194 * This file contains a few macros to help track
195 * the edge of a filled object. The object is assumed
196 * to be filled in scanline order, and thus the
197 * algorithm used is an extension of Bresenham's line
198 * drawing algorithm which assumes that y is always the
200 * Since these pieces of code are the same for any filled shape,
201 * it is more convenient to gather the library in one
202 * place, but since these pieces of code are also in
203 * the inner loops of output primitives, procedure call
204 * overhead is out of the question.
205 * See the author for a derivation if needed.
210 * In scan converting polygons, we want to choose those pixels
211 * which are inside the polygon. Thus, we add .5 to the starting
212 * x coordinate for both left and right edges. Now we choose the
213 * first pixel which is inside the pgon for the left edge and the
214 * first pixel which is outside the pgon for the right edge.
215 * Draw the left pixel, but not the right.
217 * How to add .5 to the starting x coordinate:
218 * If the edge is moving to the right, then subtract dy from the
219 * error term from the general form of the algorithm.
220 * If the edge is moving to the left, then add dy to the error term.
222 * The reason for the difference between edges moving to the left
223 * and edges moving to the right is simple: If an edge is moving
224 * to the right, then we want the algorithm to flip immediately.
225 * If it is moving to the left, then we don't want it to flip until
226 * we traverse an entire pixel.
228 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
229 int dx; /* local storage */ \
232 * if the edge is horizontal, then it is ignored \
233 * and assumed not to be processed. Otherwise, do this stuff. \
237 dx = (x2) - xStart; \
241 incr1 = -2 * dx + 2 * (dy) * m1; \
242 incr2 = -2 * dx + 2 * (dy) * m; \
243 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
247 incr1 = 2 * dx - 2 * (dy) * m1; \
248 incr2 = 2 * dx - 2 * (dy) * m; \
249 d = -2 * m * (dy) + 2 * dx; \
254 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
277 * This structure contains all of the information needed
278 * to run the bresenham algorithm.
279 * The variables may be hardcoded into the declarations
280 * instead of using this structure to make use of
281 * register declarations.
284 INT minor_axis
; /* minor axis */
285 INT d
; /* decision variable */
286 INT m
, m1
; /* slope and slope+1 */
287 INT incr1
, incr2
; /* error increments */
291 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
292 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
293 bres.m, bres.m1, bres.incr1, bres.incr2)
295 #define BRESINCRPGONSTRUCT(bres) \
296 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
301 * These are the data structures needed to scan
302 * convert regions. Two different scan conversion
303 * methods are available -- the even-odd method, and
304 * the winding number method.
305 * The even-odd rule states that a point is inside
306 * the polygon if a ray drawn from that point in any
307 * direction will pass through an odd number of
309 * By the winding number rule, a point is decided
310 * to be inside the polygon if a ray drawn from that
311 * point in any direction passes through a different
312 * number of clockwise and counter-clockwise path
315 * These data structures are adapted somewhat from
316 * the algorithm in (Foley/Van Dam) for scan converting
318 * The basic algorithm is to start at the top (smallest y)
319 * of the polygon, stepping down to the bottom of
320 * the polygon by incrementing the y coordinate. We
321 * keep a list of edges which the current scanline crosses,
322 * sorted by x. This list is called the Active Edge Table (AET)
323 * As we change the y-coordinate, we update each entry in
324 * in the active edge table to reflect the edges new xcoord.
325 * This list must be sorted at each scanline in case
326 * two edges intersect.
327 * We also keep a data structure known as the Edge Table (ET),
328 * which keeps track of all the edges which the current
329 * scanline has not yet reached. The ET is basically a
330 * list of ScanLineList structures containing a list of
331 * edges which are entered at a given scanline. There is one
332 * ScanLineList per scanline at which an edge is entered.
333 * When we enter a new edge, we move it from the ET to the AET.
335 * From the AET, we can implement the even-odd rule as in
337 * The winding number rule is a little trickier. We also
338 * keep the EdgeTableEntries in the AET linked by the
339 * nextWETE (winding EdgeTableEntry) link. This allows
340 * the edges to be linked just as before for updating
341 * purposes, but only uses the edges linked by the nextWETE
342 * link as edges representing spans of the polygon to
343 * drawn (as with the even-odd rule).
347 * for the winding number rule
350 #define COUNTERCLOCKWISE -1
352 typedef struct _EdgeTableEntry
{
353 INT ymax
; /* ycoord at which we exit this edge. */
354 BRESINFO bres
; /* Bresenham info to run the edge */
355 struct _EdgeTableEntry
*next
; /* next in the list */
356 struct _EdgeTableEntry
*back
; /* for insertion sort */
357 struct _EdgeTableEntry
*nextWETE
; /* for winding num rule */
358 int ClockWise
; /* flag for winding number rule */
362 typedef struct _ScanLineList
{
363 INT scanline
; /* the scanline represented */
364 EdgeTableEntry
*edgelist
; /* header node */
365 struct _ScanLineList
*next
; /* next in the list */
370 INT ymax
; /* ymax for the polygon */
371 INT ymin
; /* ymin for the polygon */
372 ScanLineList scanlines
; /* header node */
377 * Here is a struct to help with storage allocation
378 * so we can allocate a big chunk at a time, and then take
379 * pieces from this heap when we need to.
381 #define SLLSPERBLOCK 25
383 typedef struct _ScanLineListBlock
{
384 ScanLineList SLLs
[SLLSPERBLOCK
];
385 struct _ScanLineListBlock
*next
;
391 * a few macros for the inner loops of the fill code where
392 * performance considerations don't allow a procedure call.
394 * Evaluate the given edge at the given scanline.
395 * If the edge has expired, then we leave it and fix up
396 * the active edge table; otherwise, we increment the
397 * x value to be ready for the next scanline.
398 * The winding number rule is in effect, so we must notify
399 * the caller when the edge has been removed so he
400 * can reorder the Winding Active Edge Table.
402 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
403 if (pAET->ymax == y) { /* leaving this edge */ \
404 pPrevAET->next = pAET->next; \
405 pAET = pPrevAET->next; \
408 pAET->back = pPrevAET; \
411 BRESINCRPGONSTRUCT(pAET->bres); \
419 * Evaluate the given edge at the given scanline.
420 * If the edge has expired, then we leave it and fix up
421 * the active edge table; otherwise, we increment the
422 * x value to be ready for the next scanline.
423 * The even-odd rule is in effect.
425 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
426 if (pAET->ymax == y) { /* leaving this edge */ \
427 pPrevAET->next = pAET->next; \
428 pAET = pPrevAET->next; \
430 pAET->back = pPrevAET; \
433 BRESINCRPGONSTRUCT(pAET->bres); \
439 typedef void (*voidProcp
)();
441 /* Note the parameter order is different from the X11 equivalents */
443 static void REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
444 static void REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
445 static void REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
446 static void REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
447 static void REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
448 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
450 #define RGN_DEFAULT_RECTS 2
453 /***********************************************************************
456 inline static INT
get_region_type( const RGNOBJ
*obj
)
458 switch(obj
->rgn
->numRects
)
460 case 0: return NULLREGION
;
461 case 1: return SIMPLEREGION
;
462 default: return COMPLEXREGION
;
467 /***********************************************************************
469 * Outputs the contents of a WINEREGION
471 static void REGION_DumpRegion(WINEREGION
*pReg
)
473 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
475 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg
,
476 pReg
->extents
.left
, pReg
->extents
.top
,
477 pReg
->extents
.right
, pReg
->extents
.bottom
, pReg
->numRects
);
478 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
479 TRACE("\t%d,%d - %d,%d\n", pRect
->left
, pRect
->top
,
480 pRect
->right
, pRect
->bottom
);
485 /***********************************************************************
486 * REGION_AllocWineRegion
487 * Create a new empty WINEREGION.
489 static WINEREGION
*REGION_AllocWineRegion( INT n
)
493 if ((pReg
= HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION
))))
495 if ((pReg
->rects
= HeapAlloc(GetProcessHeap(), 0, n
* sizeof( RECT
))))
501 HeapFree(GetProcessHeap(), 0, pReg
);
507 /***********************************************************************
508 * REGION_CreateRegion
509 * Create a new empty region.
511 static HRGN
REGION_CreateRegion( INT n
)
516 if(!(obj
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
, &hrgn
, ®ion_funcs
))) return 0;
517 if(!(obj
->rgn
= REGION_AllocWineRegion(n
))) {
518 GDI_FreeObject( hrgn
, obj
);
521 GDI_ReleaseObj( hrgn
);
525 /***********************************************************************
526 * REGION_DestroyWineRegion
528 static void REGION_DestroyWineRegion( WINEREGION
* pReg
)
530 HeapFree( GetProcessHeap(), 0, pReg
->rects
);
531 HeapFree( GetProcessHeap(), 0, pReg
);
534 /***********************************************************************
535 * REGION_DeleteObject
537 static BOOL
REGION_DeleteObject( HGDIOBJ handle
, void *obj
)
541 TRACE(" %04x\n", handle
);
543 REGION_DestroyWineRegion( rgn
->rgn
);
544 return GDI_FreeObject( handle
, obj
);
547 /***********************************************************************
548 * REGION_SelectObject
550 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, void *obj
, HDC hdc
)
552 return (HGDIOBJ
)SelectClipRgn( hdc
, handle
);
556 /***********************************************************************
557 * OffsetRgn (GDI32.@)
559 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
561 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
564 TRACE("%04x %d,%d\n", hrgn
, x
, y
);
570 int nbox
= obj
->rgn
->numRects
;
571 RECT
*pbox
= obj
->rgn
->rects
;
581 obj
->rgn
->extents
.left
+= x
;
582 obj
->rgn
->extents
.right
+= x
;
583 obj
->rgn
->extents
.top
+= y
;
584 obj
->rgn
->extents
.bottom
+= y
;
587 ret
= get_region_type( obj
);
588 GDI_ReleaseObj( hrgn
);
593 /***********************************************************************
594 * GetRgnBox (GDI32.@)
596 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
598 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
602 TRACE(" %04x\n", hrgn
);
603 rect
->left
= obj
->rgn
->extents
.left
;
604 rect
->top
= obj
->rgn
->extents
.top
;
605 rect
->right
= obj
->rgn
->extents
.right
;
606 rect
->bottom
= obj
->rgn
->extents
.bottom
;
607 ret
= get_region_type( obj
);
608 GDI_ReleaseObj(hrgn
);
615 /***********************************************************************
616 * CreateRectRgn (GDI32.@)
618 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
622 /* Allocate 2 rects by default to reduce the number of reallocs */
624 if (!(hrgn
= REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
627 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
632 /***********************************************************************
633 * CreateRectRgnIndirect (GDI32.@)
635 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
637 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
641 /***********************************************************************
642 * SetRectRgn (GDI32.@)
644 * Allows either or both left and top to be greater than right or bottom.
646 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
647 INT right
, INT bottom
)
651 TRACE(" %04x %d,%d-%d,%d\n",
652 hrgn
, left
, top
, right
, bottom
);
654 if (!(obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return FALSE
;
656 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
657 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
659 if((left
!= right
) && (top
!= bottom
))
661 obj
->rgn
->rects
->left
= obj
->rgn
->extents
.left
= left
;
662 obj
->rgn
->rects
->top
= obj
->rgn
->extents
.top
= top
;
663 obj
->rgn
->rects
->right
= obj
->rgn
->extents
.right
= right
;
664 obj
->rgn
->rects
->bottom
= obj
->rgn
->extents
.bottom
= bottom
;
665 obj
->rgn
->numRects
= 1;
668 EMPTY_REGION(obj
->rgn
);
670 GDI_ReleaseObj( hrgn
);
675 /***********************************************************************
676 * CreateRoundRectRgn (GDI32.@)
678 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
679 INT right
, INT bottom
,
680 INT ellipse_width
, INT ellipse_height
)
684 int asq
, bsq
, d
, xd
, yd
;
687 /* Make the dimensions sensible */
689 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
690 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
692 ellipse_width
= abs(ellipse_width
);
693 ellipse_height
= abs(ellipse_height
);
695 /* Check parameters */
697 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
698 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
700 /* Check if we can do a normal rectangle instead */
702 if ((ellipse_width
< 2) || (ellipse_height
< 2))
703 return CreateRectRgn( left
, top
, right
, bottom
);
707 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
708 if (!(hrgn
= REGION_CreateRegion(d
))) return 0;
709 if (!(obj
= GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return 0;
710 TRACE("(%d,%d-%d,%d %dx%d): ret=%04x\n",
711 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
713 /* Ellipse algorithm, based on an article by K. Porter */
714 /* in DDJ Graphics Programming Column, 8/89 */
716 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
717 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
718 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
720 yd
= asq
* ellipse_height
; /* 2a^2b */
722 rect
.left
= left
+ ellipse_width
/ 2;
723 rect
.right
= right
- ellipse_width
/ 2;
725 /* Loop to draw first half of quadrant */
729 if (d
> 0) /* if nearest pixel is toward the center */
731 /* move toward center */
733 rect
.bottom
= rect
.top
+ 1;
734 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
736 rect
.bottom
= rect
.top
+ 1;
737 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
741 rect
.left
--; /* next horiz point */
747 /* Loop to draw second half of quadrant */
749 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
752 /* next vertical point */
754 rect
.bottom
= rect
.top
+ 1;
755 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
757 rect
.bottom
= rect
.top
+ 1;
758 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
759 if (d
< 0) /* if nearest pixel is outside ellipse */
761 rect
.left
--; /* move away from center */
770 /* Add the inside rectangle */
775 rect
.bottom
= bottom
;
776 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
778 GDI_ReleaseObj( hrgn
);
783 /***********************************************************************
784 * CreateEllipticRgn (GDI32.@)
786 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
787 INT right
, INT bottom
)
789 return CreateRoundRectRgn( left
, top
, right
, bottom
,
790 right
-left
, bottom
-top
);
794 /***********************************************************************
795 * CreateEllipticRgnIndirect (GDI32.@)
797 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
799 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
800 rect
->bottom
, rect
->right
- rect
->left
,
801 rect
->bottom
- rect
->top
);
804 /***********************************************************************
805 * GetRegionData (GDI32.@)
807 * MSDN: GetRegionData, Return Values:
809 * "If the function succeeds and dwCount specifies an adequate number of bytes,
810 * the return value is always dwCount. If dwCount is too small or the function
811 * fails, the return value is 0. If lpRgnData is NULL, the return value is the
812 * required number of bytes.
814 * If the function fails, the return value is zero."
816 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
819 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
821 TRACE(" %04x count = %ld, rgndata = %p\n",
822 hrgn
, count
, rgndata
);
826 size
= obj
->rgn
->numRects
* sizeof(RECT
);
827 if(count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
829 GDI_ReleaseObj( hrgn
);
830 if (rgndata
) /* buffer is too small, signal it by return 0 */
832 else /* user requested buffer size with rgndata NULL */
833 return size
+ sizeof(RGNDATAHEADER
);
836 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
837 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
838 rgndata
->rdh
.nCount
= obj
->rgn
->numRects
;
839 rgndata
->rdh
.nRgnSize
= size
;
840 rgndata
->rdh
.rcBound
.left
= obj
->rgn
->extents
.left
;
841 rgndata
->rdh
.rcBound
.top
= obj
->rgn
->extents
.top
;
842 rgndata
->rdh
.rcBound
.right
= obj
->rgn
->extents
.right
;
843 rgndata
->rdh
.rcBound
.bottom
= obj
->rgn
->extents
.bottom
;
845 memcpy( rgndata
->Buffer
, obj
->rgn
->rects
, size
);
847 GDI_ReleaseObj( hrgn
);
848 return size
+ sizeof(RGNDATAHEADER
);
852 /***********************************************************************
853 * ExtCreateRegion (GDI32.@)
856 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
860 TRACE(" %p %ld %p = ", lpXform
, dwCount
, rgndata
);
863 WARN("(Xform not implemented - ignored)\n");
865 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
867 /* FIXME: We can use CreatePolyPolygonRgn() here
868 * for trapezoidal data */
870 WARN("(Unsupported region data)\n");
874 if( (hrgn
= REGION_CreateRegion( rgndata
->rdh
.nCount
)) )
876 RECT
*pCurRect
, *pEndRect
;
877 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
880 pEndRect
= (RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
881 for(pCurRect
= (RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
882 REGION_UnionRectWithRegion( pCurRect
, obj
->rgn
);
883 GDI_ReleaseObj( hrgn
);
885 TRACE("%04x\n", hrgn
);
888 else ERR("Could not get pointer to newborn Region!\n");
896 /***********************************************************************
897 * PtInRegion (GDI32.@)
899 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
904 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
908 if (obj
->rgn
->numRects
> 0 && INRECT(obj
->rgn
->extents
, x
, y
))
909 for (i
= 0; i
< obj
->rgn
->numRects
; i
++)
910 if (INRECT (obj
->rgn
->rects
[i
], x
, y
))
915 GDI_ReleaseObj( hrgn
);
921 /***********************************************************************
922 * RectInRegion (GDI32.@)
924 * Returns TRUE if rect is at least partly inside hrgn
926 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
931 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
933 RECT
*pCurRect
, *pRectEnd
;
935 /* this is (just) a useful optimization */
936 if ((obj
->rgn
->numRects
> 0) && EXTENTCHECK(&obj
->rgn
->extents
,
939 for (pCurRect
= obj
->rgn
->rects
, pRectEnd
= pCurRect
+
940 obj
->rgn
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
942 if (pCurRect
->bottom
<= rect
->top
)
943 continue; /* not far enough down yet */
945 if (pCurRect
->top
>= rect
->bottom
)
946 break; /* too far down */
948 if (pCurRect
->right
<= rect
->left
)
949 continue; /* not far enough over yet */
951 if (pCurRect
->left
>= rect
->right
) {
959 GDI_ReleaseObj(hrgn
);
964 /***********************************************************************
967 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
972 if ((obj1
= (RGNOBJ
*) GDI_GetObjPtr( hrgn1
, REGION_MAGIC
)))
974 if ((obj2
= (RGNOBJ
*) GDI_GetObjPtr( hrgn2
, REGION_MAGIC
)))
978 if ( obj1
->rgn
->numRects
!= obj2
->rgn
->numRects
) goto done
;
979 if ( obj1
->rgn
->numRects
== 0 )
985 if (obj1
->rgn
->extents
.left
!= obj2
->rgn
->extents
.left
) goto done
;
986 if (obj1
->rgn
->extents
.right
!= obj2
->rgn
->extents
.right
) goto done
;
987 if (obj1
->rgn
->extents
.top
!= obj2
->rgn
->extents
.top
) goto done
;
988 if (obj1
->rgn
->extents
.bottom
!= obj2
->rgn
->extents
.bottom
) goto done
;
989 for( i
= 0; i
< obj1
->rgn
->numRects
; i
++ )
991 if (obj1
->rgn
->rects
[i
].left
!= obj2
->rgn
->rects
[i
].left
) goto done
;
992 if (obj1
->rgn
->rects
[i
].right
!= obj2
->rgn
->rects
[i
].right
) goto done
;
993 if (obj1
->rgn
->rects
[i
].top
!= obj2
->rgn
->rects
[i
].top
) goto done
;
994 if (obj1
->rgn
->rects
[i
].bottom
!= obj2
->rgn
->rects
[i
].bottom
) goto done
;
998 GDI_ReleaseObj(hrgn2
);
1000 GDI_ReleaseObj(hrgn1
);
1005 /***********************************************************************
1006 * REGION_UnionRectWithRegion
1007 * Adds a rectangle to a WINEREGION
1009 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1013 region
.rects
= ®ion
.extents
;
1014 region
.numRects
= 1;
1016 region
.extents
= *rect
;
1017 REGION_UnionRegion(rgn
, rgn
, ®ion
);
1021 /***********************************************************************
1022 * REGION_CreateFrameRgn
1024 * Create a region that is a frame around another region.
1025 * Expand all rectangles by +/- x and y, then subtract original region.
1027 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1030 RGNOBJ
*srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
1032 if (!srcObj
) return FALSE
;
1033 if (srcObj
->rgn
->numRects
!= 0)
1035 RGNOBJ
* destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1036 RECT
*pRect
, *pEndRect
;
1039 EMPTY_REGION( destObj
->rgn
);
1041 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
1042 for(pRect
= srcObj
->rgn
->rects
; pRect
< pEndRect
; pRect
++)
1044 tempRect
.left
= pRect
->left
- x
;
1045 tempRect
.top
= pRect
->top
- y
;
1046 tempRect
.right
= pRect
->right
+ x
;
1047 tempRect
.bottom
= pRect
->bottom
+ y
;
1048 REGION_UnionRectWithRegion( &tempRect
, destObj
->rgn
);
1050 REGION_SubtractRegion( destObj
->rgn
, destObj
->rgn
, srcObj
->rgn
);
1051 GDI_ReleaseObj ( hDest
);
1056 GDI_ReleaseObj( hSrc
);
1061 /***********************************************************************
1062 * CombineRgn (GDI32.@)
1064 * Note: The behavior is correct even if src and dest regions are the same.
1066 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1068 RGNOBJ
*destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1071 TRACE(" %04x,%04x -> %04x mode=%x\n",
1072 hSrc1
, hSrc2
, hDest
, mode
);
1075 RGNOBJ
*src1Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc1
, REGION_MAGIC
);
1079 TRACE("dump src1Obj:\n");
1080 if(TRACE_ON(region
))
1081 REGION_DumpRegion(src1Obj
->rgn
);
1082 if (mode
== RGN_COPY
)
1084 REGION_CopyRegion( destObj
->rgn
, src1Obj
->rgn
);
1085 result
= get_region_type( destObj
);
1089 RGNOBJ
*src2Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc2
, REGION_MAGIC
);
1093 TRACE("dump src2Obj:\n");
1094 if(TRACE_ON(region
))
1095 REGION_DumpRegion(src2Obj
->rgn
);
1099 REGION_IntersectRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1102 REGION_UnionRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1105 REGION_XorRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1108 REGION_SubtractRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1111 result
= get_region_type( destObj
);
1112 GDI_ReleaseObj( hSrc2
);
1115 GDI_ReleaseObj( hSrc1
);
1117 TRACE("dump destObj:\n");
1118 if(TRACE_ON(region
))
1119 REGION_DumpRegion(destObj
->rgn
);
1121 GDI_ReleaseObj( hDest
);
1123 ERR("Invalid rgn=%04x\n", hDest
);
1128 /***********************************************************************
1130 * Re-calculate the extents of a region
1132 static void REGION_SetExtents (WINEREGION
*pReg
)
1134 RECT
*pRect
, *pRectEnd
, *pExtents
;
1136 if (pReg
->numRects
== 0)
1138 pReg
->extents
.left
= 0;
1139 pReg
->extents
.top
= 0;
1140 pReg
->extents
.right
= 0;
1141 pReg
->extents
.bottom
= 0;
1145 pExtents
= &pReg
->extents
;
1146 pRect
= pReg
->rects
;
1147 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1150 * Since pRect is the first rectangle in the region, it must have the
1151 * smallest top and since pRectEnd is the last rectangle in the region,
1152 * it must have the largest bottom, because of banding. Initialize left and
1153 * right from pRect and pRectEnd, resp., as good things to initialize them
1156 pExtents
->left
= pRect
->left
;
1157 pExtents
->top
= pRect
->top
;
1158 pExtents
->right
= pRectEnd
->right
;
1159 pExtents
->bottom
= pRectEnd
->bottom
;
1161 while (pRect
<= pRectEnd
)
1163 if (pRect
->left
< pExtents
->left
)
1164 pExtents
->left
= pRect
->left
;
1165 if (pRect
->right
> pExtents
->right
)
1166 pExtents
->right
= pRect
->right
;
1171 /***********************************************************************
1174 static void REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1176 if (dst
!= src
) /* don't want to copy to itself */
1178 if (dst
->size
< src
->numRects
)
1180 if (! (dst
->rects
= HeapReAlloc( GetProcessHeap(), 0, dst
->rects
,
1181 src
->numRects
* sizeof(RECT
) )))
1183 dst
->size
= src
->numRects
;
1185 dst
->numRects
= src
->numRects
;
1186 dst
->extents
.left
= src
->extents
.left
;
1187 dst
->extents
.top
= src
->extents
.top
;
1188 dst
->extents
.right
= src
->extents
.right
;
1189 dst
->extents
.bottom
= src
->extents
.bottom
;
1190 memcpy((char *) dst
->rects
, (char *) src
->rects
,
1191 (int) (src
->numRects
* sizeof(RECT
)));
1196 /***********************************************************************
1199 * Attempt to merge the rects in the current band with those in the
1200 * previous one. Used only by REGION_RegionOp.
1203 * The new index for the previous band.
1206 * If coalescing takes place:
1207 * - rectangles in the previous band will have their bottom fields
1209 * - pReg->numRects will be decreased.
1212 static INT
REGION_Coalesce (
1213 WINEREGION
*pReg
, /* Region to coalesce */
1214 INT prevStart
, /* Index of start of previous band */
1215 INT curStart
/* Index of start of current band */
1217 RECT
*pPrevRect
; /* Current rect in previous band */
1218 RECT
*pCurRect
; /* Current rect in current band */
1219 RECT
*pRegEnd
; /* End of region */
1220 INT curNumRects
; /* Number of rectangles in current band */
1221 INT prevNumRects
; /* Number of rectangles in previous band */
1222 INT bandtop
; /* top coordinate for current band */
1224 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1226 pPrevRect
= &pReg
->rects
[prevStart
];
1227 prevNumRects
= curStart
- prevStart
;
1230 * Figure out how many rectangles are in the current band. Have to do
1231 * this because multiple bands could have been added in REGION_RegionOp
1232 * at the end when one region has been exhausted.
1234 pCurRect
= &pReg
->rects
[curStart
];
1235 bandtop
= pCurRect
->top
;
1236 for (curNumRects
= 0;
1237 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1243 if (pCurRect
!= pRegEnd
)
1246 * If more than one band was added, we have to find the start
1247 * of the last band added so the next coalescing job can start
1248 * at the right place... (given when multiple bands are added,
1249 * this may be pointless -- see above).
1252 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1256 curStart
= pRegEnd
- pReg
->rects
;
1257 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1260 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1261 pCurRect
-= curNumRects
;
1263 * The bands may only be coalesced if the bottom of the previous
1264 * matches the top scanline of the current.
1266 if (pPrevRect
->bottom
== pCurRect
->top
)
1269 * Make sure the bands have rects in the same places. This
1270 * assumes that rects have been added in such a way that they
1271 * cover the most area possible. I.e. two rects in a band must
1272 * have some horizontal space between them.
1276 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1277 (pPrevRect
->right
!= pCurRect
->right
))
1280 * The bands don't line up so they can't be coalesced.
1287 } while (prevNumRects
!= 0);
1289 pReg
->numRects
-= curNumRects
;
1290 pCurRect
-= curNumRects
;
1291 pPrevRect
-= curNumRects
;
1294 * The bands may be merged, so set the bottom of each rect
1295 * in the previous band to that of the corresponding rect in
1300 pPrevRect
->bottom
= pCurRect
->bottom
;
1304 } while (curNumRects
!= 0);
1307 * If only one band was added to the region, we have to backup
1308 * curStart to the start of the previous band.
1310 * If more than one band was added to the region, copy the
1311 * other bands down. The assumption here is that the other bands
1312 * came from the same region as the current one and no further
1313 * coalescing can be done on them since it's all been done
1314 * already... curStart is already in the right place.
1316 if (pCurRect
== pRegEnd
)
1318 curStart
= prevStart
;
1324 *pPrevRect
++ = *pCurRect
++;
1325 } while (pCurRect
!= pRegEnd
);
1333 /***********************************************************************
1336 * Apply an operation to two regions. Called by REGION_Union,
1337 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1343 * The new region is overwritten.
1346 * The idea behind this function is to view the two regions as sets.
1347 * Together they cover a rectangle of area that this function divides
1348 * into horizontal bands where points are covered only by one region
1349 * or by both. For the first case, the nonOverlapFunc is called with
1350 * each the band and the band's upper and lower extents. For the
1351 * second, the overlapFunc is called to process the entire band. It
1352 * is responsible for clipping the rectangles in the band, though
1353 * this function provides the boundaries.
1354 * At the end of each band, the new region is coalesced, if possible,
1355 * to reduce the number of rectangles in the region.
1358 static void REGION_RegionOp(
1359 WINEREGION
*newReg
, /* Place to store result */
1360 WINEREGION
*reg1
, /* First region in operation */
1361 WINEREGION
*reg2
, /* 2nd region in operation */
1362 void (*overlapFunc
)(), /* Function to call for over-lapping bands */
1363 void (*nonOverlap1Func
)(), /* Function to call for non-overlapping bands in region 1 */
1364 void (*nonOverlap2Func
)() /* Function to call for non-overlapping bands in region 2 */
1366 RECT
*r1
; /* Pointer into first region */
1367 RECT
*r2
; /* Pointer into 2d region */
1368 RECT
*r1End
; /* End of 1st region */
1369 RECT
*r2End
; /* End of 2d region */
1370 INT ybot
; /* Bottom of intersection */
1371 INT ytop
; /* Top of intersection */
1372 RECT
*oldRects
; /* Old rects for newReg */
1373 INT prevBand
; /* Index of start of
1374 * previous band in newReg */
1375 INT curBand
; /* Index of start of current
1377 RECT
*r1BandEnd
; /* End of current band in r1 */
1378 RECT
*r2BandEnd
; /* End of current band in r2 */
1379 INT top
; /* Top of non-overlapping band */
1380 INT bot
; /* Bottom of non-overlapping band */
1384 * set r1, r2, r1End and r2End appropriately, preserve the important
1385 * parts of the destination region until the end in case it's one of
1386 * the two source regions, then mark the "new" region empty, allocating
1387 * another array of rectangles for it to use.
1391 r1End
= r1
+ reg1
->numRects
;
1392 r2End
= r2
+ reg2
->numRects
;
1396 * newReg may be one of the src regions so we can't empty it. We keep a
1397 * note of its rects pointer (so that we can free them later), preserve its
1398 * extents and simply set numRects to zero.
1401 oldRects
= newReg
->rects
;
1402 newReg
->numRects
= 0;
1405 * Allocate a reasonable number of rectangles for the new region. The idea
1406 * is to allocate enough so the individual functions don't need to
1407 * reallocate and copy the array, which is time consuming, yet we don't
1408 * have to worry about using too much memory. I hope to be able to
1409 * nuke the Xrealloc() at the end of this function eventually.
1411 newReg
->size
= max(reg1
->numRects
,reg2
->numRects
) * 2;
1413 if (! (newReg
->rects
= HeapAlloc( GetProcessHeap(), 0,
1414 sizeof(RECT
) * newReg
->size
)))
1421 * Initialize ybot and ytop.
1422 * In the upcoming loop, ybot and ytop serve different functions depending
1423 * on whether the band being handled is an overlapping or non-overlapping
1425 * In the case of a non-overlapping band (only one of the regions
1426 * has points in the band), ybot is the bottom of the most recent
1427 * intersection and thus clips the top of the rectangles in that band.
1428 * ytop is the top of the next intersection between the two regions and
1429 * serves to clip the bottom of the rectangles in the current band.
1430 * For an overlapping band (where the two regions intersect), ytop clips
1431 * the top of the rectangles of both regions and ybot clips the bottoms.
1433 if (reg1
->extents
.top
< reg2
->extents
.top
)
1434 ybot
= reg1
->extents
.top
;
1436 ybot
= reg2
->extents
.top
;
1439 * prevBand serves to mark the start of the previous band so rectangles
1440 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1441 * In the beginning, there is no previous band, so prevBand == curBand
1442 * (curBand is set later on, of course, but the first band will always
1443 * start at index 0). prevBand and curBand must be indices because of
1444 * the possible expansion, and resultant moving, of the new region's
1445 * array of rectangles.
1451 curBand
= newReg
->numRects
;
1454 * This algorithm proceeds one source-band (as opposed to a
1455 * destination band, which is determined by where the two regions
1456 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1457 * rectangle after the last one in the current band for their
1458 * respective regions.
1461 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1467 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1473 * First handle the band that doesn't intersect, if any.
1475 * Note that attention is restricted to one band in the
1476 * non-intersecting region at once, so if a region has n
1477 * bands between the current position and the next place it overlaps
1478 * the other, this entire loop will be passed through n times.
1480 if (r1
->top
< r2
->top
)
1482 top
= max(r1
->top
,ybot
);
1483 bot
= min(r1
->bottom
,r2
->top
);
1485 if ((top
!= bot
) && (nonOverlap1Func
!= (void (*)())NULL
))
1487 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1492 else if (r2
->top
< r1
->top
)
1494 top
= max(r2
->top
,ybot
);
1495 bot
= min(r2
->bottom
,r1
->top
);
1497 if ((top
!= bot
) && (nonOverlap2Func
!= (void (*)())NULL
))
1499 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1510 * If any rectangles got added to the region, try and coalesce them
1511 * with rectangles from the previous band. Note we could just do
1512 * this test in miCoalesce, but some machines incur a not
1513 * inconsiderable cost for function calls, so...
1515 if (newReg
->numRects
!= curBand
)
1517 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1521 * Now see if we've hit an intersecting band. The two bands only
1522 * intersect if ybot > ytop
1524 ybot
= min(r1
->bottom
, r2
->bottom
);
1525 curBand
= newReg
->numRects
;
1528 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1532 if (newReg
->numRects
!= curBand
)
1534 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1538 * If we've finished with a band (bottom == ybot) we skip forward
1539 * in the region to the next band.
1541 if (r1
->bottom
== ybot
)
1545 if (r2
->bottom
== ybot
)
1549 } while ((r1
!= r1End
) && (r2
!= r2End
));
1552 * Deal with whichever region still has rectangles left.
1554 curBand
= newReg
->numRects
;
1557 if (nonOverlap1Func
!= (void (*)())NULL
)
1562 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1566 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1567 max(r1
->top
,ybot
), r1
->bottom
);
1569 } while (r1
!= r1End
);
1572 else if ((r2
!= r2End
) && (nonOverlap2Func
!= (void (*)())NULL
))
1577 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1581 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1582 max(r2
->top
,ybot
), r2
->bottom
);
1584 } while (r2
!= r2End
);
1587 if (newReg
->numRects
!= curBand
)
1589 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1593 * A bit of cleanup. To keep regions from growing without bound,
1594 * we shrink the array of rectangles to match the new number of
1595 * rectangles in the region. This never goes to 0, however...
1597 * Only do this stuff if the number of rectangles allocated is more than
1598 * twice the number of rectangles in the region (a simple optimization...).
1600 if ((newReg
->numRects
< (newReg
->size
>> 1)) && (newReg
->numRects
> 2))
1602 if (REGION_NOT_EMPTY(newReg
))
1604 RECT
*prev_rects
= newReg
->rects
;
1605 newReg
->size
= newReg
->numRects
;
1606 newReg
->rects
= HeapReAlloc( GetProcessHeap(), 0, newReg
->rects
,
1607 sizeof(RECT
) * newReg
->size
);
1608 if (! newReg
->rects
)
1609 newReg
->rects
= prev_rects
;
1614 * No point in doing the extra work involved in an Xrealloc if
1615 * the region is empty
1618 HeapFree( GetProcessHeap(), 0, newReg
->rects
);
1619 newReg
->rects
= HeapAlloc( GetProcessHeap(), 0, sizeof(RECT
) );
1622 HeapFree( GetProcessHeap(), 0, oldRects
);
1626 /***********************************************************************
1627 * Region Intersection
1628 ***********************************************************************/
1631 /***********************************************************************
1634 * Handle an overlapping band for REGION_Intersect.
1640 * Rectangles may be added to the region.
1643 static void REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1644 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1650 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1652 while ((r1
!= r1End
) && (r2
!= r2End
))
1654 left
= max(r1
->left
, r2
->left
);
1655 right
= min(r1
->right
, r2
->right
);
1658 * If there's any overlap between the two rectangles, add that
1659 * overlap to the new region.
1660 * There's no need to check for subsumption because the only way
1661 * such a need could arise is if some region has two rectangles
1662 * right next to each other. Since that should never happen...
1666 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1667 pNextRect
->left
= left
;
1668 pNextRect
->top
= top
;
1669 pNextRect
->right
= right
;
1670 pNextRect
->bottom
= bottom
;
1671 pReg
->numRects
+= 1;
1676 * Need to advance the pointers. Shift the one that extends
1677 * to the right the least, since the other still has a chance to
1678 * overlap with that region's next rectangle, if you see what I mean.
1680 if (r1
->right
< r2
->right
)
1684 else if (r2
->right
< r1
->right
)
1697 /***********************************************************************
1698 * REGION_IntersectRegion
1700 static void REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1703 /* check for trivial reject */
1704 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1705 (!EXTENTCHECK(®1
->extents
, ®2
->extents
)))
1706 newReg
->numRects
= 0;
1708 REGION_RegionOp (newReg
, reg1
, reg2
,
1709 (voidProcp
) REGION_IntersectO
, (voidProcp
) NULL
, (voidProcp
) NULL
);
1712 * Can't alter newReg's extents before we call miRegionOp because
1713 * it might be one of the source regions and miRegionOp depends
1714 * on the extents of those regions being the same. Besides, this
1715 * way there's no checking against rectangles that will be nuked
1716 * due to coalescing, so we have to examine fewer rectangles.
1718 REGION_SetExtents(newReg
);
1721 /***********************************************************************
1723 ***********************************************************************/
1725 /***********************************************************************
1728 * Handle a non-overlapping band for the union operation. Just
1729 * Adds the rectangles into the region. Doesn't have to check for
1730 * subsumption or anything.
1736 * pReg->numRects is incremented and the final rectangles overwritten
1737 * with the rectangles we're passed.
1740 static void REGION_UnionNonO (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1741 INT top
, INT bottom
)
1745 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1749 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1750 pNextRect
->left
= r
->left
;
1751 pNextRect
->top
= top
;
1752 pNextRect
->right
= r
->right
;
1753 pNextRect
->bottom
= bottom
;
1754 pReg
->numRects
+= 1;
1761 /***********************************************************************
1764 * Handle an overlapping band for the union operation. Picks the
1765 * left-most rectangle each time and merges it into the region.
1771 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1775 static void REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1776 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1780 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1782 #define MERGERECT(r) \
1783 if ((pReg->numRects != 0) && \
1784 (pNextRect[-1].top == top) && \
1785 (pNextRect[-1].bottom == bottom) && \
1786 (pNextRect[-1].right >= r->left)) \
1788 if (pNextRect[-1].right < r->right) \
1790 pNextRect[-1].right = r->right; \
1795 MEMCHECK(pReg, pNextRect, pReg->rects); \
1796 pNextRect->top = top; \
1797 pNextRect->bottom = bottom; \
1798 pNextRect->left = r->left; \
1799 pNextRect->right = r->right; \
1800 pReg->numRects += 1; \
1805 while ((r1
!= r1End
) && (r2
!= r2End
))
1807 if (r1
->left
< r2
->left
)
1822 } while (r1
!= r1End
);
1824 else while (r2
!= r2End
)
1831 /***********************************************************************
1832 * REGION_UnionRegion
1834 static void REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1837 /* checks all the simple cases */
1840 * Region 1 and 2 are the same or region 1 is empty
1842 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
1845 REGION_CopyRegion(newReg
, reg2
);
1850 * if nothing to union (region 2 empty)
1852 if (!(reg2
->numRects
))
1855 REGION_CopyRegion(newReg
, reg1
);
1860 * Region 1 completely subsumes region 2
1862 if ((reg1
->numRects
== 1) &&
1863 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
1864 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
1865 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
1866 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
1869 REGION_CopyRegion(newReg
, reg1
);
1874 * Region 2 completely subsumes region 1
1876 if ((reg2
->numRects
== 1) &&
1877 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
1878 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
1879 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
1880 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
1883 REGION_CopyRegion(newReg
, reg2
);
1887 REGION_RegionOp (newReg
, reg1
, reg2
, (voidProcp
) REGION_UnionO
,
1888 (voidProcp
) REGION_UnionNonO
, (voidProcp
) REGION_UnionNonO
);
1890 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
1891 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
1892 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
1893 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
1896 /***********************************************************************
1897 * Region Subtraction
1898 ***********************************************************************/
1900 /***********************************************************************
1901 * REGION_SubtractNonO1
1903 * Deal with non-overlapping band for subtraction. Any parts from
1904 * region 2 we discard. Anything from region 1 we add to the region.
1910 * pReg may be affected.
1913 static void REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1914 INT top
, INT bottom
)
1918 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1922 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1923 pNextRect
->left
= r
->left
;
1924 pNextRect
->top
= top
;
1925 pNextRect
->right
= r
->right
;
1926 pNextRect
->bottom
= bottom
;
1927 pReg
->numRects
+= 1;
1935 /***********************************************************************
1938 * Overlapping band subtraction. x1 is the left-most point not yet
1945 * pReg may have rectangles added to it.
1948 static void REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1949 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1955 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1957 while ((r1
!= r1End
) && (r2
!= r2End
))
1959 if (r2
->right
<= left
)
1962 * Subtrahend missed the boat: go to next subtrahend.
1966 else if (r2
->left
<= left
)
1969 * Subtrahend preceeds minuend: nuke left edge of minuend.
1972 if (left
>= r1
->right
)
1975 * Minuend completely covered: advance to next minuend and
1976 * reset left fence to edge of new minuend.
1985 * Subtrahend now used up since it doesn't extend beyond
1991 else if (r2
->left
< r1
->right
)
1994 * Left part of subtrahend covers part of minuend: add uncovered
1995 * part of minuend to region and skip to next subtrahend.
1997 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1998 pNextRect
->left
= left
;
1999 pNextRect
->top
= top
;
2000 pNextRect
->right
= r2
->left
;
2001 pNextRect
->bottom
= bottom
;
2002 pReg
->numRects
+= 1;
2005 if (left
>= r1
->right
)
2008 * Minuend used up: advance to new...
2017 * Subtrahend used up
2025 * Minuend used up: add any remaining piece before advancing.
2027 if (r1
->right
> left
)
2029 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2030 pNextRect
->left
= left
;
2031 pNextRect
->top
= top
;
2032 pNextRect
->right
= r1
->right
;
2033 pNextRect
->bottom
= bottom
;
2034 pReg
->numRects
+= 1;
2043 * Add remaining minuend rectangles to region.
2047 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2048 pNextRect
->left
= left
;
2049 pNextRect
->top
= top
;
2050 pNextRect
->right
= r1
->right
;
2051 pNextRect
->bottom
= bottom
;
2052 pReg
->numRects
+= 1;
2063 /***********************************************************************
2064 * REGION_SubtractRegion
2066 * Subtract regS from regM and leave the result in regD.
2067 * S stands for subtrahend, M for minuend and D for difference.
2073 * regD is overwritten.
2076 static void REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
,
2079 /* check for trivial reject */
2080 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2081 (!EXTENTCHECK(®M
->extents
, ®S
->extents
)) )
2083 REGION_CopyRegion(regD
, regM
);
2087 REGION_RegionOp (regD
, regM
, regS
, (voidProcp
) REGION_SubtractO
,
2088 (voidProcp
) REGION_SubtractNonO1
, (voidProcp
) NULL
);
2091 * Can't alter newReg's extents before we call miRegionOp because
2092 * it might be one of the source regions and miRegionOp depends
2093 * on the extents of those regions being the unaltered. Besides, this
2094 * way there's no checking against rectangles that will be nuked
2095 * due to coalescing, so we have to examine fewer rectangles.
2097 REGION_SetExtents (regD
);
2100 /***********************************************************************
2103 static void REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
,
2106 WINEREGION
*tra
, *trb
;
2108 if ((! (tra
= REGION_AllocWineRegion(sra
->numRects
+ 1))) ||
2109 (! (trb
= REGION_AllocWineRegion(srb
->numRects
+ 1))))
2111 REGION_SubtractRegion(tra
,sra
,srb
);
2112 REGION_SubtractRegion(trb
,srb
,sra
);
2113 REGION_UnionRegion(dr
,tra
,trb
);
2114 REGION_DestroyWineRegion(tra
);
2115 REGION_DestroyWineRegion(trb
);
2119 /**************************************************************************
2123 *************************************************************************/
2125 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2126 #define SMALL_COORDINATE 0x80000000
2128 /***********************************************************************
2129 * REGION_InsertEdgeInET
2131 * Insert the given edge into the edge table.
2132 * First we must find the correct bucket in the
2133 * Edge table, then find the right slot in the
2134 * bucket. Finally, we can insert it.
2137 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2138 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2141 EdgeTableEntry
*start
, *prev
;
2142 ScanLineList
*pSLL
, *pPrevSLL
;
2143 ScanLineListBlock
*tmpSLLBlock
;
2146 * find the right bucket to put the edge into
2148 pPrevSLL
= &ET
->scanlines
;
2149 pSLL
= pPrevSLL
->next
;
2150 while (pSLL
&& (pSLL
->scanline
< scanline
))
2157 * reassign pSLL (pointer to ScanLineList) if necessary
2159 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2161 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2163 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2166 WARN("Can't alloc SLLB\n");
2169 (*SLLBlock
)->next
= tmpSLLBlock
;
2170 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2171 *SLLBlock
= tmpSLLBlock
;
2174 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2176 pSLL
->next
= pPrevSLL
->next
;
2177 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
2178 pPrevSLL
->next
= pSLL
;
2180 pSLL
->scanline
= scanline
;
2183 * now insert the edge in the right bucket
2185 prev
= (EdgeTableEntry
*)NULL
;
2186 start
= pSLL
->edgelist
;
2187 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
2190 start
= start
->next
;
2197 pSLL
->edgelist
= ETE
;
2200 /***********************************************************************
2201 * REGION_CreateEdgeTable
2203 * This routine creates the edge table for
2204 * scan converting polygons.
2205 * The Edge Table (ET) looks like:
2209 * | ymax | ScanLineLists
2210 * |scanline|-->------------>-------------->...
2211 * -------- |scanline| |scanline|
2212 * |edgelist| |edgelist|
2213 * --------- ---------
2217 * list of ETEs list of ETEs
2219 * where ETE is an EdgeTableEntry data structure,
2220 * and there is one ScanLineList per scanline at
2221 * which an edge is initially entered.
2224 static void REGION_CreateETandAET(const INT
*Count
, INT nbpolygons
,
2225 const POINT
*pts
, EdgeTable
*ET
, EdgeTableEntry
*AET
,
2226 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2228 const POINT
*top
, *bottom
;
2229 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2236 * initialize the Active Edge Table
2238 AET
->next
= (EdgeTableEntry
*)NULL
;
2239 AET
->back
= (EdgeTableEntry
*)NULL
;
2240 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2241 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
2244 * initialize the Edge Table.
2246 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
2247 ET
->ymax
= SMALL_COORDINATE
;
2248 ET
->ymin
= LARGE_COORDINATE
;
2249 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2252 for(poly
= 0; poly
< nbpolygons
; poly
++)
2254 count
= Count
[poly
];
2262 * for each vertex in the array of points.
2263 * In this loop we are dealing with two vertices at
2264 * a time -- these make up one edge of the polygon.
2271 * find out which point is above and which is below.
2273 if (PrevPt
->y
> CurrPt
->y
)
2275 bottom
= PrevPt
, top
= CurrPt
;
2276 pETEs
->ClockWise
= 0;
2280 bottom
= CurrPt
, top
= PrevPt
;
2281 pETEs
->ClockWise
= 1;
2285 * don't add horizontal edges to the Edge table.
2287 if (bottom
->y
!= top
->y
)
2289 pETEs
->ymax
= bottom
->y
-1;
2290 /* -1 so we don't get last scanline */
2293 * initialize integer edge algorithm
2295 dy
= bottom
->y
- top
->y
;
2296 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
2298 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2301 if (PrevPt
->y
> ET
->ymax
)
2302 ET
->ymax
= PrevPt
->y
;
2303 if (PrevPt
->y
< ET
->ymin
)
2304 ET
->ymin
= PrevPt
->y
;
2313 /***********************************************************************
2316 * This routine moves EdgeTableEntries from the
2317 * EdgeTable into the Active Edge Table,
2318 * leaving them sorted by smaller x coordinate.
2321 static void REGION_loadAET(EdgeTableEntry
*AET
, EdgeTableEntry
*ETEs
)
2323 EdgeTableEntry
*pPrevAET
;
2324 EdgeTableEntry
*tmp
;
2330 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
2339 ETEs
->back
= pPrevAET
;
2340 pPrevAET
->next
= ETEs
;
2347 /***********************************************************************
2348 * REGION_computeWAET
2350 * This routine links the AET by the
2351 * nextWETE (winding EdgeTableEntry) link for
2352 * use by the winding number rule. The final
2353 * Active Edge Table (AET) might look something
2357 * ---------- --------- ---------
2358 * |ymax | |ymax | |ymax |
2359 * | ... | |... | |... |
2360 * |next |->|next |->|next |->...
2361 * |nextWETE| |nextWETE| |nextWETE|
2362 * --------- --------- ^--------
2364 * V-------------------> V---> ...
2367 static void REGION_computeWAET(EdgeTableEntry
*AET
)
2369 register EdgeTableEntry
*pWETE
;
2370 register int inside
= 1;
2371 register int isInside
= 0;
2373 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2383 if ((!inside
&& !isInside
) ||
2384 ( inside
&& isInside
))
2386 pWETE
->nextWETE
= AET
;
2392 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
2395 /***********************************************************************
2396 * REGION_InsertionSort
2398 * Just a simple insertion sort using
2399 * pointers and back pointers to sort the Active
2403 static BOOL
REGION_InsertionSort(EdgeTableEntry
*AET
)
2405 EdgeTableEntry
*pETEchase
;
2406 EdgeTableEntry
*pETEinsert
;
2407 EdgeTableEntry
*pETEchaseBackTMP
;
2408 BOOL changed
= FALSE
;
2415 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
2416 pETEchase
= pETEchase
->back
;
2419 if (pETEchase
!= pETEinsert
)
2421 pETEchaseBackTMP
= pETEchase
->back
;
2422 pETEinsert
->back
->next
= AET
;
2424 AET
->back
= pETEinsert
->back
;
2425 pETEinsert
->next
= pETEchase
;
2426 pETEchase
->back
->next
= pETEinsert
;
2427 pETEchase
->back
= pETEinsert
;
2428 pETEinsert
->back
= pETEchaseBackTMP
;
2435 /***********************************************************************
2436 * REGION_FreeStorage
2440 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2442 ScanLineListBlock
*tmpSLLBlock
;
2446 tmpSLLBlock
= pSLLBlock
->next
;
2447 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2448 pSLLBlock
= tmpSLLBlock
;
2453 /***********************************************************************
2454 * REGION_PtsToRegion
2456 * Create an array of rectangles from a list of points.
2458 static int REGION_PtsToRegion(int numFullPtBlocks
, int iCurPtBlock
,
2459 POINTBLOCK
*FirstPtBlock
, WINEREGION
*reg
)
2463 POINTBLOCK
*CurPtBlock
;
2468 extents
= ®
->extents
;
2470 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
2472 if (!(reg
->rects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
,
2473 sizeof(RECT
) * numRects
)))
2476 reg
->size
= numRects
;
2477 CurPtBlock
= FirstPtBlock
;
2478 rects
= reg
->rects
- 1;
2480 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2482 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--) {
2483 /* the loop uses 2 points per iteration */
2484 i
= NUMPTSTOBUFFER
>> 1;
2485 if (!numFullPtBlocks
)
2486 i
= iCurPtBlock
>> 1;
2487 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2) {
2488 if (pts
->x
== pts
[1].x
)
2490 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2491 pts
[1].x
== rects
->right
&&
2492 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2493 (i
&& pts
[2].y
> pts
[1].y
)) {
2494 rects
->bottom
= pts
[1].y
+ 1;
2499 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2500 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2501 if (rects
->left
< extents
->left
)
2502 extents
->left
= rects
->left
;
2503 if (rects
->right
> extents
->right
)
2504 extents
->right
= rects
->right
;
2506 CurPtBlock
= CurPtBlock
->next
;
2510 extents
->top
= reg
->rects
->top
;
2511 extents
->bottom
= rects
->bottom
;
2516 extents
->bottom
= 0;
2518 reg
->numRects
= numRects
;
2523 /***********************************************************************
2524 * CreatePolyPolygonRgn (GDI32.@)
2526 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2527 INT nbpolygons
, INT mode
)
2532 register EdgeTableEntry
*pAET
; /* Active Edge Table */
2533 register INT y
; /* current scanline */
2534 register int iPts
= 0; /* number of pts in buffer */
2535 register EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
2536 register ScanLineList
*pSLL
; /* current scanLineList */
2537 register POINT
*pts
; /* output buffer */
2538 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
2539 EdgeTable ET
; /* header node for ET */
2540 EdgeTableEntry AET
; /* header node for AET */
2541 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2542 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2543 int fixWAET
= FALSE
;
2544 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
2545 POINTBLOCK
*tmpPtBlock
;
2546 int numFullPtBlocks
= 0;
2549 if(!(hrgn
= REGION_CreateRegion(nbpolygons
)))
2551 obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
2554 /* special case a rectangle */
2556 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2557 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2558 (((Pts
[0].y
== Pts
[1].y
) &&
2559 (Pts
[1].x
== Pts
[2].x
) &&
2560 (Pts
[2].y
== Pts
[3].y
) &&
2561 (Pts
[3].x
== Pts
[0].x
)) ||
2562 ((Pts
[0].x
== Pts
[1].x
) &&
2563 (Pts
[1].y
== Pts
[2].y
) &&
2564 (Pts
[2].x
== Pts
[3].x
) &&
2565 (Pts
[3].y
== Pts
[0].y
))))
2567 SetRectRgn( hrgn
, min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2568 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2569 GDI_ReleaseObj( hrgn
);
2573 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2574 total
+= Count
[poly
];
2575 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2577 REGION_DeleteObject( hrgn
, obj
);
2580 pts
= FirstPtBlock
.pts
;
2581 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
2582 pSLL
= ET
.scanlines
.next
;
2583 curPtBlock
= &FirstPtBlock
;
2585 if (mode
!= WINDING
) {
2589 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2591 * Add a new edge to the active edge table when we
2592 * get to the next edge.
2594 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2595 REGION_loadAET(&AET
, pSLL
->edgelist
);
2602 * for each active edge
2605 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2609 * send out the buffer
2611 if (iPts
== NUMPTSTOBUFFER
) {
2612 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK
));
2614 WARN("Can't alloc tPB\n");
2617 curPtBlock
->next
= tmpPtBlock
;
2618 curPtBlock
= tmpPtBlock
;
2619 pts
= curPtBlock
->pts
;
2623 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
2625 REGION_InsertionSort(&AET
);
2632 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2634 * Add a new edge to the active edge table when we
2635 * get to the next edge.
2637 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2638 REGION_loadAET(&AET
, pSLL
->edgelist
);
2639 REGION_computeWAET(&AET
);
2647 * for each active edge
2651 * add to the buffer only those edges that
2652 * are in the Winding active edge table.
2654 if (pWETE
== pAET
) {
2655 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2659 * send out the buffer
2661 if (iPts
== NUMPTSTOBUFFER
) {
2662 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0,
2663 sizeof(POINTBLOCK
) );
2665 WARN("Can't alloc tPB\n");
2666 REGION_DeleteObject( hrgn
, obj
);
2669 curPtBlock
->next
= tmpPtBlock
;
2670 curPtBlock
= tmpPtBlock
;
2671 pts
= curPtBlock
->pts
;
2672 numFullPtBlocks
++; iPts
= 0;
2674 pWETE
= pWETE
->nextWETE
;
2676 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
2680 * recompute the winding active edge table if
2681 * we just resorted or have exited an edge.
2683 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2684 REGION_computeWAET(&AET
);
2689 REGION_FreeStorage(SLLBlock
.next
);
2690 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
2692 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;) {
2693 tmpPtBlock
= curPtBlock
->next
;
2694 HeapFree( GetProcessHeap(), 0, curPtBlock
);
2695 curPtBlock
= tmpPtBlock
;
2697 HeapFree( GetProcessHeap(), 0, pETEs
);
2698 GDI_ReleaseObj( hrgn
);
2703 /***********************************************************************
2704 * CreatePolygonRgn (GDI32.@)
2706 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2709 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);
2713 /***********************************************************************
2714 * GetRandomRgn [GDI32.@]
2717 * This function is documented in MSDN online
2719 INT WINAPI
GetRandomRgn(HDC hDC
, HRGN hRgn
, DWORD dwCode
)
2723 case 4: /* == SYSRGN ? */
2725 DC
*dc
= DC_GetDCPtr (hDC
);
2730 CombineRgn (hRgn
, dc
->hVisRgn
, 0, RGN_COPY
);
2732 * On Windows NT/2000,
2733 * the region returned is in screen coordinates.
2735 * the region returned is in window coordinates
2737 vi
.dwOSVersionInfoSize
= sizeof(vi
);
2738 if (GetVersionExA( &vi
) && vi
.dwPlatformId
== VER_PLATFORM_WIN32_NT
)
2739 GetDCOrgEx(hDC
, &org
);
2742 OffsetRgn (hRgn
, org
.x
, org
.y
);
2743 GDI_ReleaseObj( hDC
);
2747 return GetClipRgn (hDC, hRgn);
2750 WARN("Unknown dwCode %ld\n", dwCode
);
2758 /***********************************************************************
2759 * GetMetaRgn (GDI32.@)
2761 INT WINAPI
GetMetaRgn( HDC hdc
, HRGN hRgn
)
2769 /***********************************************************************
2770 * SetMetaRgn (GDI32.@)
2772 INT WINAPI
SetMetaRgn( HDC hdc
)