2 * GDI region objects. Shamelessly ripped out from the X11 distribution
3 * Thanks for the nice license.
5 * Copyright 1993, 1994, 1995 Alexandre Julliard
6 * Modifications and additions: Copyright 1998 Huw Davies
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
24 /************************************************************************
26 Copyright (c) 1987, 1988 X Consortium
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
70 ************************************************************************/
72 * The functions in this file implement the Region abstraction, similar to one
73 * used in the X11 sample server. A Region is simply an area, as the name
74 * implies, and is implemented as a "y-x-banded" array of rectangles. To
75 * explain: Each Region is made up of a certain number of rectangles sorted
76 * by y coordinate first, and then by x coordinate.
78 * Furthermore, the rectangles are banded such that every rectangle with a
79 * given upper-left y coordinate (y1) will have the same lower-right y
80 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81 * will span the entire vertical distance of the band. This means that some
82 * areas that could be merged into a taller rectangle will be represented as
83 * several shorter rectangles to account for shorter rectangles to its left
84 * or right but within its "vertical scope".
86 * An added constraint on the rectangles is that they must cover as much
87 * horizontal area as possible. E.g. no two rectangles in a band are allowed
90 * Whenever possible, bands will be merged together to cover a greater vertical
91 * distance (and thus reduce the number of rectangles). Two bands can be merged
92 * only if the bottom of one touches the top of the other and they have
93 * rectangles in the same places (of the same width, of course). This maintains
94 * the y-x-banding that's so nice to have...
103 #include "gdi_private.h"
104 #include "wine/debug.h"
106 WINE_DEFAULT_DEBUG_CHANNEL(region
);
109 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, HDC hdc
);
110 static BOOL
REGION_DeleteObject( HGDIOBJ handle
);
112 static const struct gdi_obj_funcs region_funcs
=
114 REGION_SelectObject
, /* pSelectObject */
115 NULL
, /* pGetObjectA */
116 NULL
, /* pGetObjectW */
117 NULL
, /* pUnrealizeObject */
118 REGION_DeleteObject
/* pDeleteObject */
121 /* Check if two RECTs overlap. */
122 static inline BOOL
overlapping( const RECT
*r1
, const RECT
*r2
)
124 return (r1
->right
> r2
->left
&& r1
->left
< r2
->right
&&
125 r1
->bottom
> r2
->top
&& r1
->top
< r2
->bottom
);
128 static BOOL
grow_region( WINEREGION
*rgn
, int size
)
132 if (size
<= rgn
->size
) return TRUE
;
134 if (rgn
->rects
== rgn
->rects_buf
)
136 new_rects
= HeapAlloc( GetProcessHeap(), 0, size
* sizeof(RECT
) );
137 if (!new_rects
) return FALSE
;
138 memcpy( new_rects
, rgn
->rects
, rgn
->numRects
* sizeof(RECT
) );
142 new_rects
= HeapReAlloc( GetProcessHeap(), 0, rgn
->rects
, size
* sizeof(RECT
) );
143 if (!new_rects
) return FALSE
;
145 rgn
->rects
= new_rects
;
150 static BOOL
add_rect( WINEREGION
*reg
, INT left
, INT top
, INT right
, INT bottom
)
153 if (reg
->numRects
>= reg
->size
&& !grow_region( reg
, 2 * reg
->size
))
156 rect
= reg
->rects
+ reg
->numRects
++;
160 rect
->bottom
= bottom
;
164 static inline void empty_region( WINEREGION
*reg
)
167 reg
->extents
.left
= reg
->extents
.top
= reg
->extents
.right
= reg
->extents
.bottom
= 0;
170 static inline BOOL
is_in_rect( const RECT
*rect
, int x
, int y
)
172 return (rect
->right
> x
&& rect
->left
<= x
&& rect
->bottom
> y
&& rect
->top
<= 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
188 POINT pts
[NUMPTSTOBUFFER
];
190 struct point_block
*next
;
193 static struct point_block
*add_point( struct point_block
*block
, int x
, int y
)
195 if (block
->count
== NUMPTSTOBUFFER
)
197 struct point_block
*new = HeapAlloc( GetProcessHeap(), 0, sizeof(*new) );
198 if (!new) return NULL
;
204 block
->pts
[block
->count
].x
= x
;
205 block
->pts
[block
->count
].y
= y
;
210 static void free_point_blocks( struct point_block
*block
)
214 struct point_block
*tmp
= block
->next
;
215 HeapFree( GetProcessHeap(), 0, block
);
222 * This file contains a few macros to help track
223 * the edge of a filled object. The object is assumed
224 * to be filled in scanline order, and thus the
225 * algorithm used is an extension of Bresenham's line
226 * drawing algorithm which assumes that y is always the
228 * Since these pieces of code are the same for any filled shape,
229 * it is more convenient to gather the library in one
230 * place, but since these pieces of code are also in
231 * the inner loops of output primitives, procedure call
232 * overhead is out of the question.
233 * See the author for a derivation if needed.
238 * This structure contains all of the information needed
239 * to run the bresenham algorithm.
240 * The variables may be hardcoded into the declarations
241 * instead of using this structure to make use of
242 * register declarations.
246 INT minor_axis
; /* minor axis */
247 INT d
; /* decision variable */
248 INT m
, m1
; /* slope and slope+1 */
249 INT incr1
, incr2
; /* error increments */
254 * In scan converting polygons, we want to choose those pixels
255 * which are inside the polygon. Thus, we add .5 to the starting
256 * x coordinate for both left and right edges. Now we choose the
257 * first pixel which is inside the pgon for the left edge and the
258 * first pixel which is outside the pgon for the right edge.
259 * Draw the left pixel, but not the right.
261 * How to add .5 to the starting x coordinate:
262 * If the edge is moving to the right, then subtract dy from the
263 * error term from the general form of the algorithm.
264 * If the edge is moving to the left, then add dy to the error term.
266 * The reason for the difference between edges moving to the left
267 * and edges moving to the right is simple: If an edge is moving
268 * to the right, then we want the algorithm to flip immediately.
269 * If it is moving to the left, then we don't want it to flip until
270 * we traverse an entire pixel.
272 static inline void bres_init_polygon( int dy
, int x1
, int x2
, struct bres_info
*bres
)
277 * if the edge is horizontal, then it is ignored
278 * and assumed not to be processed. Otherwise, do this stuff.
282 bres
->minor_axis
= x1
;
287 bres
->m1
= bres
->m
- 1;
288 bres
->incr1
= -2 * dx
+ 2 * dy
* bres
->m1
;
289 bres
->incr2
= -2 * dx
+ 2 * dy
* bres
->m
;
290 bres
->d
= 2 * bres
->m
* dy
- 2 * dx
- 2 * dy
;
295 bres
->m1
= bres
->m
+ 1;
296 bres
->incr1
= 2 * dx
- 2 * dy
* bres
->m1
;
297 bres
->incr2
= 2 * dx
- 2 * dy
* bres
->m
;
298 bres
->d
= -2 * bres
->m
* dy
+ 2 * dx
;
302 static inline void bres_incr_polygon( struct bres_info
*bres
)
306 bres
->minor_axis
+= bres
->m1
;
307 bres
->d
+= bres
->incr1
;
310 bres
->minor_axis
+= bres
->m
;
311 bres
->d
+= bres
->incr2
;
315 bres
->minor_axis
+= bres
->m1
;
316 bres
->d
+= bres
->incr1
;
319 bres
->minor_axis
+= bres
->m
;
320 bres
->d
+= bres
->incr2
;
327 * These are the data structures needed to scan
328 * convert regions. Two different scan conversion
329 * methods are available -- the even-odd method, and
330 * the winding number method.
331 * The even-odd rule states that a point is inside
332 * the polygon if a ray drawn from that point in any
333 * direction will pass through an odd number of
335 * By the winding number rule, a point is decided
336 * to be inside the polygon if a ray drawn from that
337 * point in any direction passes through a different
338 * number of clockwise and counter-clockwise path
341 * These data structures are adapted somewhat from
342 * the algorithm in (Foley/Van Dam) for scan converting
344 * The basic algorithm is to start at the top (smallest y)
345 * of the polygon, stepping down to the bottom of
346 * the polygon by incrementing the y coordinate. We
347 * keep a list of edges which the current scanline crosses,
348 * sorted by x. This list is called the Active Edge Table (AET)
349 * As we change the y-coordinate, we update each entry in
350 * in the active edge table to reflect the edges new xcoord.
351 * This list must be sorted at each scanline in case
352 * two edges intersect.
353 * We also keep a data structure known as the Edge Table (ET),
354 * which keeps track of all the edges which the current
355 * scanline has not yet reached. The ET is basically a
356 * list of ScanLineList structures containing a list of
357 * edges which are entered at a given scanline. There is one
358 * ScanLineList per scanline at which an edge is entered.
359 * When we enter a new edge, we move it from the ET to the AET.
361 * From the AET, we can implement the even-odd rule as in
363 * The winding number rule is a little trickier. We also
364 * keep the EdgeTableEntries in the AET linked by the
365 * nextWETE (winding EdgeTableEntry) link. This allows
366 * the edges to be linked just as before for updating
367 * purposes, but only uses the edges linked by the nextWETE
368 * link as edges representing spans of the polygon to
369 * drawn (as with the even-odd rule).
372 typedef struct edge_table_entry
{
374 struct list winding_entry
;
375 INT ymax
; /* ycoord at which we exit this edge. */
376 struct bres_info bres
; /* Bresenham info to run the edge */
377 int ClockWise
; /* flag for winding number rule */
381 typedef struct _ScanLineList
{
382 struct list edgelist
;
383 INT scanline
; /* the scanline represented */
384 struct _ScanLineList
*next
; /* next in the list */
389 INT ymax
; /* ymax for the polygon */
390 INT ymin
; /* ymin for the polygon */
391 ScanLineList scanlines
; /* header node */
396 * Here is a struct to help with storage allocation
397 * so we can allocate a big chunk at a time, and then take
398 * pieces from this heap when we need to.
400 #define SLLSPERBLOCK 25
402 typedef struct _ScanLineListBlock
{
403 ScanLineList SLLs
[SLLSPERBLOCK
];
404 struct _ScanLineListBlock
*next
;
408 /* Note the parameter order is different from the X11 equivalents */
410 static BOOL
REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
411 static BOOL
REGION_OffsetRegion(WINEREGION
*d
, WINEREGION
*s
, INT x
, INT y
);
412 static BOOL
REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
413 static BOOL
REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
414 static BOOL
REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
415 static BOOL
REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
416 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
418 /***********************************************************************
421 static inline INT
get_region_type( const WINEREGION
*obj
)
423 switch(obj
->numRects
)
425 case 0: return NULLREGION
;
426 case 1: return SIMPLEREGION
;
427 default: return COMPLEXREGION
;
432 /***********************************************************************
434 * Outputs the contents of a WINEREGION
436 static void REGION_DumpRegion(WINEREGION
*pReg
)
438 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
440 TRACE("Region %p: %s %d rects\n", pReg
, wine_dbgstr_rect(&pReg
->extents
), pReg
->numRects
);
441 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
442 TRACE("\t%s\n", wine_dbgstr_rect(pRect
));
447 /***********************************************************************
450 * Initialize a new empty region.
452 static BOOL
init_region( WINEREGION
*pReg
, INT n
)
454 n
= max( n
, RGN_DEFAULT_RECTS
);
456 if (n
> RGN_DEFAULT_RECTS
)
458 if (!(pReg
->rects
= HeapAlloc( GetProcessHeap(), 0, n
* sizeof( RECT
) )))
462 pReg
->rects
= pReg
->rects_buf
;
469 /***********************************************************************
472 static void destroy_region( WINEREGION
*pReg
)
474 if (pReg
->rects
!= pReg
->rects_buf
)
475 HeapFree( GetProcessHeap(), 0, pReg
->rects
);
478 /***********************************************************************
481 static void free_region( WINEREGION
*rgn
)
483 destroy_region( rgn
);
484 HeapFree( GetProcessHeap(), 0, rgn
);
487 /***********************************************************************
490 static WINEREGION
*alloc_region( INT n
)
492 WINEREGION
*rgn
= HeapAlloc( GetProcessHeap(), 0, sizeof(*rgn
) );
494 if (rgn
&& !init_region( rgn
, n
))
502 /************************************************************
505 * Move rectangles from src to dst leaving src with no rectangles.
507 static inline void move_rects( WINEREGION
*dst
, WINEREGION
*src
)
509 destroy_region( dst
);
510 if (src
->rects
== src
->rects_buf
)
512 dst
->rects
= dst
->rects_buf
;
513 memcpy( dst
->rects
, src
->rects
, src
->numRects
* sizeof(RECT
) );
516 dst
->rects
= src
->rects
;
517 dst
->size
= src
->size
;
518 dst
->numRects
= src
->numRects
;
519 init_region( src
, 0 );
522 /***********************************************************************
523 * REGION_DeleteObject
525 static BOOL
REGION_DeleteObject( HGDIOBJ handle
)
527 WINEREGION
*rgn
= free_gdi_handle( handle
);
529 if (!rgn
) return FALSE
;
534 /***********************************************************************
535 * REGION_SelectObject
537 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, HDC hdc
)
539 return ULongToHandle(SelectClipRgn( hdc
, handle
));
543 /***********************************************************************
544 * REGION_OffsetRegion
545 * Offset a WINEREGION by x,y
547 static BOOL
REGION_OffsetRegion( WINEREGION
*rgn
, WINEREGION
*srcrgn
, INT x
, INT y
)
551 if (!REGION_CopyRegion( rgn
, srcrgn
)) return FALSE
;
554 int nbox
= rgn
->numRects
;
555 RECT
*pbox
= rgn
->rects
;
565 rgn
->extents
.left
+= x
;
566 rgn
->extents
.right
+= x
;
567 rgn
->extents
.top
+= y
;
568 rgn
->extents
.bottom
+= y
;
574 /***********************************************************************
575 * OffsetRgn (GDI32.@)
577 * Moves a region by the specified X- and Y-axis offsets.
580 * hrgn [I] Region to offset.
581 * x [I] Offset right if positive or left if negative.
582 * y [I] Offset down if positive or up if negative.
586 * NULLREGION - The new region is empty.
587 * SIMPLEREGION - The new region can be represented by one rectangle.
588 * COMPLEXREGION - The new region can only be represented by more than
592 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
594 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
597 TRACE("%p %d,%d\n", hrgn
, x
, y
);
602 REGION_OffsetRegion( obj
, obj
, x
, y
);
604 ret
= get_region_type( obj
);
605 GDI_ReleaseObj( hrgn
);
610 /***********************************************************************
611 * GetRgnBox (GDI32.@)
613 * Retrieves the bounding rectangle of the region. The bounding rectangle
614 * is the smallest rectangle that contains the entire region.
617 * hrgn [I] Region to retrieve bounding rectangle from.
618 * rect [O] Rectangle that will receive the coordinates of the bounding
622 * NULLREGION - The new region is empty.
623 * SIMPLEREGION - The new region can be represented by one rectangle.
624 * COMPLEXREGION - The new region can only be represented by more than
627 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
629 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
633 rect
->left
= obj
->extents
.left
;
634 rect
->top
= obj
->extents
.top
;
635 rect
->right
= obj
->extents
.right
;
636 rect
->bottom
= obj
->extents
.bottom
;
637 TRACE("%p %s\n", hrgn
, wine_dbgstr_rect(rect
));
638 ret
= get_region_type( obj
);
639 GDI_ReleaseObj(hrgn
);
646 /***********************************************************************
647 * CreateRectRgn (GDI32.@)
649 * Creates a simple rectangular region.
652 * left [I] Left coordinate of rectangle.
653 * top [I] Top coordinate of rectangle.
654 * right [I] Right coordinate of rectangle.
655 * bottom [I] Bottom coordinate of rectangle.
658 * Success: Handle to region.
661 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
666 if (!(obj
= alloc_region( RGN_DEFAULT_RECTS
))) return 0;
668 if (!(hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
)))
673 TRACE( "%d,%d-%d,%d returning %p\n", left
, top
, right
, bottom
, hrgn
);
674 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
679 /***********************************************************************
680 * CreateRectRgnIndirect (GDI32.@)
682 * Creates a simple rectangular region.
685 * rect [I] Coordinates of rectangular region.
688 * Success: Handle to region.
691 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
693 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
697 /***********************************************************************
698 * SetRectRgn (GDI32.@)
700 * Sets a region to a simple rectangular region.
703 * hrgn [I] Region to convert.
704 * left [I] Left coordinate of rectangle.
705 * top [I] Top coordinate of rectangle.
706 * right [I] Right coordinate of rectangle.
707 * bottom [I] Bottom coordinate of rectangle.
714 * Allows either or both left and top to be greater than right or bottom.
716 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
717 INT right
, INT bottom
)
721 TRACE("%p %d,%d-%d,%d\n", hrgn
, left
, top
, right
, bottom
);
723 if (!(obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
))) return FALSE
;
725 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
726 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
728 if((left
!= right
) && (top
!= bottom
))
730 obj
->rects
->left
= obj
->extents
.left
= left
;
731 obj
->rects
->top
= obj
->extents
.top
= top
;
732 obj
->rects
->right
= obj
->extents
.right
= right
;
733 obj
->rects
->bottom
= obj
->extents
.bottom
= bottom
;
739 GDI_ReleaseObj( hrgn
);
744 /***********************************************************************
745 * CreateRoundRectRgn (GDI32.@)
747 * Creates a rectangular region with rounded corners.
750 * left [I] Left coordinate of rectangle.
751 * top [I] Top coordinate of rectangle.
752 * right [I] Right coordinate of rectangle.
753 * bottom [I] Bottom coordinate of rectangle.
754 * ellipse_width [I] Width of the ellipse at each corner.
755 * ellipse_height [I] Height of the ellipse at each corner.
758 * Success: Handle to region.
762 * If ellipse_width or ellipse_height is less than 2 logical units then
763 * it is treated as though CreateRectRgn() was called instead.
765 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
766 INT right
, INT bottom
,
767 INT ellipse_width
, INT ellipse_height
)
772 INT64 asq
, bsq
, dx
, dy
, err
;
775 /* Make the dimensions sensible */
777 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
778 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
779 /* the region is for the rectangle interior, but only at right and bottom for some reason */
783 ellipse_width
= min( right
- left
, abs( ellipse_width
));
784 ellipse_height
= min( bottom
- top
, abs( ellipse_height
));
786 /* Check if we can do a normal rectangle instead */
788 if ((ellipse_width
< 2) || (ellipse_height
< 2))
789 return CreateRectRgn( left
, top
, right
, bottom
);
791 if (!(obj
= alloc_region( ellipse_height
))) return 0;
792 obj
->numRects
= ellipse_height
;
793 obj
->extents
.left
= left
;
794 obj
->extents
.top
= top
;
795 obj
->extents
.right
= right
;
796 obj
->extents
.bottom
= bottom
;
799 /* based on an algorithm by Alois Zingl */
801 a
= ellipse_width
- 1;
802 b
= ellipse_height
- 1;
803 asq
= (INT64
)8 * a
* a
;
804 bsq
= (INT64
)8 * b
* b
;
805 dx
= (INT64
)4 * b
* b
* (1 - a
);
806 dy
= (INT64
)4 * a
* a
* (1 + (b
% 2));
807 err
= dx
+ dy
+ a
* a
* (b
% 2);
810 y
= ellipse_height
/ 2;
812 rects
[y
].left
= left
;
813 rects
[y
].right
= right
;
815 while (x
<= ellipse_width
/ 2)
827 rects
[y
].left
= left
+ x
;
828 rects
[y
].right
= right
- x
;
831 for (i
= 0; i
< ellipse_height
/ 2; i
++)
833 rects
[i
].left
= rects
[b
- i
].left
;
834 rects
[i
].right
= rects
[b
- i
].right
;
835 rects
[i
].top
= top
+ i
;
836 rects
[i
].bottom
= rects
[i
].top
+ 1;
838 for (; i
< ellipse_height
; i
++)
840 rects
[i
].top
= bottom
- ellipse_height
+ i
;
841 rects
[i
].bottom
= rects
[i
].top
+ 1;
843 rects
[ellipse_height
/ 2].top
= top
+ ellipse_height
/ 2; /* extend to top of rectangle */
845 hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
);
847 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
848 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
849 if (!hrgn
) free_region( obj
);
854 /***********************************************************************
855 * CreateEllipticRgn (GDI32.@)
857 * Creates an elliptical region.
860 * left [I] Left coordinate of bounding rectangle.
861 * top [I] Top coordinate of bounding rectangle.
862 * right [I] Right coordinate of bounding rectangle.
863 * bottom [I] Bottom coordinate of bounding rectangle.
866 * Success: Handle to region.
870 * This is a special case of CreateRoundRectRgn() where the width of the
871 * ellipse at each corner is equal to the width the rectangle and
872 * the same for the height.
874 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
875 INT right
, INT bottom
)
877 return CreateRoundRectRgn( left
, top
, right
, bottom
,
878 right
-left
, bottom
-top
);
882 /***********************************************************************
883 * CreateEllipticRgnIndirect (GDI32.@)
885 * Creates an elliptical region.
888 * rect [I] Pointer to bounding rectangle of the ellipse.
891 * Success: Handle to region.
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
CreateEllipticRgnIndirect( const RECT
*rect
)
901 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
902 rect
->bottom
, rect
->right
- rect
->left
,
903 rect
->bottom
- rect
->top
);
906 /***********************************************************************
907 * GetRegionData (GDI32.@)
909 * Retrieves the data that specifies the region.
912 * hrgn [I] Region to retrieve the region data from.
913 * count [I] The size of the buffer pointed to by rgndata in bytes.
914 * rgndata [I] The buffer to receive data about the region.
917 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
918 * the number of bytes copied to the output buffer.
922 * The format of the Buffer member of RGNDATA is determined by the iType
923 * member of the region data header.
924 * Currently this is always RDH_RECTANGLES, which specifies that the format
925 * is the array of RECT's that specify the region. The length of the array
926 * is specified by the nCount member of the region data header.
928 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
931 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
933 TRACE(" %p count = %d, rgndata = %p\n", hrgn
, count
, rgndata
);
937 size
= obj
->numRects
* sizeof(RECT
);
938 if (!rgndata
|| count
< FIELD_OFFSET(RGNDATA
, Buffer
[size
]))
940 GDI_ReleaseObj( hrgn
);
941 if (rgndata
) /* buffer is too small, signal it by return 0 */
943 /* user requested buffer size with NULL rgndata */
944 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
947 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
948 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
949 rgndata
->rdh
.nCount
= obj
->numRects
;
950 rgndata
->rdh
.nRgnSize
= size
;
951 rgndata
->rdh
.rcBound
.left
= obj
->extents
.left
;
952 rgndata
->rdh
.rcBound
.top
= obj
->extents
.top
;
953 rgndata
->rdh
.rcBound
.right
= obj
->extents
.right
;
954 rgndata
->rdh
.rcBound
.bottom
= obj
->extents
.bottom
;
956 memcpy( rgndata
->Buffer
, obj
->rects
, size
);
958 GDI_ReleaseObj( hrgn
);
959 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
963 static void translate( POINT
*pt
, UINT count
, const XFORM
*xform
)
969 pt
->x
= floor( x
* xform
->eM11
+ y
* xform
->eM21
+ xform
->eDx
+ 0.5 );
970 pt
->y
= floor( x
* xform
->eM12
+ y
* xform
->eM22
+ xform
->eDy
+ 0.5 );
976 /***********************************************************************
977 * ExtCreateRegion (GDI32.@)
979 * Creates a region as specified by the transformation data and region data.
982 * lpXform [I] World-space to logical-space transformation data.
983 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
984 * rgndata [I] Data that specifies the region.
987 * Success: Handle to region.
991 * See GetRegionData().
993 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
997 const RECT
*pCurRect
, *pEndRect
;
1001 SetLastError( ERROR_INVALID_PARAMETER
);
1005 if (rgndata
->rdh
.dwSize
< sizeof(RGNDATAHEADER
))
1008 /* XP doesn't care about the type */
1009 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
1010 WARN("(Unsupported region data type: %u)\n", rgndata
->rdh
.iType
);
1014 const RECT
*pCurRect
, *pEndRect
;
1016 hrgn
= CreateRectRgn( 0, 0, 0, 0 );
1018 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
1019 for (pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
1021 static const INT count
= 4;
1025 pt
[0].x
= pCurRect
->left
;
1026 pt
[0].y
= pCurRect
->top
;
1027 pt
[1].x
= pCurRect
->right
;
1028 pt
[1].y
= pCurRect
->top
;
1029 pt
[2].x
= pCurRect
->right
;
1030 pt
[2].y
= pCurRect
->bottom
;
1031 pt
[3].x
= pCurRect
->left
;
1032 pt
[3].y
= pCurRect
->bottom
;
1034 translate( pt
, 4, lpXform
);
1035 poly_hrgn
= CreatePolyPolygonRgn( pt
, &count
, 1, WINDING
);
1036 CombineRgn( hrgn
, hrgn
, poly_hrgn
, RGN_OR
);
1037 DeleteObject( poly_hrgn
);
1042 if (!(obj
= alloc_region( rgndata
->rdh
.nCount
))) return 0;
1044 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
1045 for(pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
1047 if (pCurRect
->left
< pCurRect
->right
&& pCurRect
->top
< pCurRect
->bottom
)
1049 if (!REGION_UnionRectWithRegion( pCurRect
, obj
)) goto done
;
1052 hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
);
1055 if (!hrgn
) free_region( obj
);
1057 TRACE("%p %d %p returning %p\n", lpXform
, dwCount
, rgndata
, hrgn
);
1062 /***********************************************************************
1063 * PtInRegion (GDI32.@)
1065 * Tests whether the specified point is inside a region.
1068 * hrgn [I] Region to test.
1069 * x [I] X-coordinate of point to test.
1070 * y [I] Y-coordinate of point to test.
1073 * Non-zero if the point is inside the region or zero otherwise.
1075 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
1080 if ((obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
)))
1082 if (obj
->numRects
> 0 && is_in_rect( &obj
->extents
, x
, y
))
1083 region_find_pt( obj
, x
, y
, &ret
);
1084 GDI_ReleaseObj( hrgn
);
1090 /***********************************************************************
1091 * RectInRegion (GDI32.@)
1093 * Tests if a rectangle is at least partly inside the specified region.
1096 * hrgn [I] Region to test.
1097 * rect [I] Rectangle to test.
1100 * Non-zero if the rectangle is partially inside the region or
1103 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
1110 /* swap the coordinates to make right >= left and bottom >= top */
1111 /* (region building rectangles are normalized the same way) */
1115 if ((obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
)))
1117 if ((obj
->numRects
> 0) && overlapping(&obj
->extents
, &rc
))
1119 for (i
= region_find_pt( obj
, rc
.left
, rc
.top
, &ret
); !ret
&& i
< obj
->numRects
; i
++ )
1121 if (obj
->rects
[i
].bottom
<= rc
.top
)
1122 continue; /* not far enough down yet */
1124 if (obj
->rects
[i
].top
>= rc
.bottom
)
1125 break; /* too far down */
1127 if (obj
->rects
[i
].right
<= rc
.left
)
1128 continue; /* not far enough over yet */
1130 if (obj
->rects
[i
].left
>= rc
.right
)
1136 GDI_ReleaseObj(hrgn
);
1141 /***********************************************************************
1142 * EqualRgn (GDI32.@)
1144 * Tests whether one region is identical to another.
1147 * hrgn1 [I] The first region to compare.
1148 * hrgn2 [I] The second region to compare.
1151 * Non-zero if both regions are identical or zero otherwise.
1153 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
1155 WINEREGION
*obj1
, *obj2
;
1158 if ((obj1
= GDI_GetObjPtr( hrgn1
, OBJ_REGION
)))
1160 if ((obj2
= GDI_GetObjPtr( hrgn2
, OBJ_REGION
)))
1164 if ( obj1
->numRects
!= obj2
->numRects
) goto done
;
1165 if ( obj1
->numRects
== 0 )
1171 if (obj1
->extents
.left
!= obj2
->extents
.left
) goto done
;
1172 if (obj1
->extents
.right
!= obj2
->extents
.right
) goto done
;
1173 if (obj1
->extents
.top
!= obj2
->extents
.top
) goto done
;
1174 if (obj1
->extents
.bottom
!= obj2
->extents
.bottom
) goto done
;
1175 for( i
= 0; i
< obj1
->numRects
; i
++ )
1177 if (obj1
->rects
[i
].left
!= obj2
->rects
[i
].left
) goto done
;
1178 if (obj1
->rects
[i
].right
!= obj2
->rects
[i
].right
) goto done
;
1179 if (obj1
->rects
[i
].top
!= obj2
->rects
[i
].top
) goto done
;
1180 if (obj1
->rects
[i
].bottom
!= obj2
->rects
[i
].bottom
) goto done
;
1184 GDI_ReleaseObj(hrgn2
);
1186 GDI_ReleaseObj(hrgn1
);
1191 /***********************************************************************
1192 * REGION_UnionRectWithRegion
1193 * Adds a rectangle to a WINEREGION
1195 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1199 init_region( ®ion
, 1 );
1200 region
.numRects
= 1;
1201 region
.extents
= *region
.rects
= *rect
;
1202 return REGION_UnionRegion(rgn
, rgn
, ®ion
);
1206 BOOL
add_rect_to_region( HRGN rgn
, const RECT
*rect
)
1208 WINEREGION
*obj
= GDI_GetObjPtr( rgn
, OBJ_REGION
);
1211 if (!obj
) return FALSE
;
1212 ret
= REGION_UnionRectWithRegion( rect
, obj
);
1213 GDI_ReleaseObj( rgn
);
1217 /***********************************************************************
1218 * REGION_CreateFrameRgn
1220 * Create a region that is a frame around another region.
1221 * Compute the intersection of the region moved in all 4 directions
1222 * ( +x, -x, +y, -y) and subtract from the original.
1223 * The result looks slightly better than in Windows :)
1225 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1229 WINEREGION
* destObj
= NULL
;
1230 WINEREGION
*srcObj
= GDI_GetObjPtr( hSrc
, OBJ_REGION
);
1232 tmprgn
.rects
= NULL
;
1233 if (!srcObj
) return FALSE
;
1234 if (srcObj
->numRects
!= 0)
1236 if (!(destObj
= GDI_GetObjPtr( hDest
, OBJ_REGION
))) goto done
;
1237 if (!init_region( &tmprgn
, srcObj
->numRects
)) goto done
;
1239 if (!REGION_OffsetRegion( destObj
, srcObj
, -x
, 0)) goto done
;
1240 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, x
, 0)) goto done
;
1241 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1242 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, -y
)) goto done
;
1243 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1244 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, y
)) goto done
;
1245 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1246 if (!REGION_SubtractRegion( destObj
, srcObj
, destObj
)) goto done
;
1250 destroy_region( &tmprgn
);
1251 if (destObj
) GDI_ReleaseObj ( hDest
);
1252 GDI_ReleaseObj( hSrc
);
1257 /***********************************************************************
1258 * CombineRgn (GDI32.@)
1260 * Combines two regions with the specified operation and stores the result
1261 * in the specified destination region.
1264 * hDest [I] The region that receives the combined result.
1265 * hSrc1 [I] The first source region.
1266 * hSrc2 [I] The second source region.
1267 * mode [I] The way in which the source regions will be combined. See notes.
1271 * NULLREGION - The new region is empty.
1272 * SIMPLEREGION - The new region can be represented by one rectangle.
1273 * COMPLEXREGION - The new region can only be represented by more than
1278 * The two source regions can be the same region.
1279 * The mode can be one of the following:
1280 *| RGN_AND - Intersection of the regions
1281 *| RGN_OR - Union of the regions
1282 *| RGN_XOR - Unions of the regions minus any intersection.
1283 *| RGN_DIFF - Difference (subtraction) of the regions.
1285 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1287 WINEREGION
*destObj
= GDI_GetObjPtr( hDest
, OBJ_REGION
);
1290 TRACE(" %p,%p -> %p mode=%x\n", hSrc1
, hSrc2
, hDest
, mode
);
1293 WINEREGION
*src1Obj
= GDI_GetObjPtr( hSrc1
, OBJ_REGION
);
1297 TRACE("dump src1Obj:\n");
1298 if(TRACE_ON(region
))
1299 REGION_DumpRegion(src1Obj
);
1300 if (mode
== RGN_COPY
)
1302 if (REGION_CopyRegion( destObj
, src1Obj
))
1303 result
= get_region_type( destObj
);
1307 WINEREGION
*src2Obj
= GDI_GetObjPtr( hSrc2
, OBJ_REGION
);
1311 TRACE("dump src2Obj:\n");
1312 if(TRACE_ON(region
))
1313 REGION_DumpRegion(src2Obj
);
1317 if (REGION_IntersectRegion( destObj
, src1Obj
, src2Obj
))
1318 result
= get_region_type( destObj
);
1321 if (REGION_UnionRegion( destObj
, src1Obj
, src2Obj
))
1322 result
= get_region_type( destObj
);
1325 if (REGION_XorRegion( destObj
, src1Obj
, src2Obj
))
1326 result
= get_region_type( destObj
);
1329 if (REGION_SubtractRegion( destObj
, src1Obj
, src2Obj
))
1330 result
= get_region_type( destObj
);
1333 GDI_ReleaseObj( hSrc2
);
1336 GDI_ReleaseObj( hSrc1
);
1338 TRACE("dump destObj:\n");
1339 if(TRACE_ON(region
))
1340 REGION_DumpRegion(destObj
);
1342 GDI_ReleaseObj( hDest
);
1347 /***********************************************************************
1349 * Re-calculate the extents of a region
1351 static void REGION_SetExtents (WINEREGION
*pReg
)
1353 RECT
*pRect
, *pRectEnd
, *pExtents
;
1355 if (pReg
->numRects
== 0)
1357 pReg
->extents
.left
= 0;
1358 pReg
->extents
.top
= 0;
1359 pReg
->extents
.right
= 0;
1360 pReg
->extents
.bottom
= 0;
1364 pExtents
= &pReg
->extents
;
1365 pRect
= pReg
->rects
;
1366 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1369 * Since pRect is the first rectangle in the region, it must have the
1370 * smallest top and since pRectEnd is the last rectangle in the region,
1371 * it must have the largest bottom, because of banding. Initialize left and
1372 * right from pRect and pRectEnd, resp., as good things to initialize them
1375 pExtents
->left
= pRect
->left
;
1376 pExtents
->top
= pRect
->top
;
1377 pExtents
->right
= pRectEnd
->right
;
1378 pExtents
->bottom
= pRectEnd
->bottom
;
1380 while (pRect
<= pRectEnd
)
1382 if (pRect
->left
< pExtents
->left
)
1383 pExtents
->left
= pRect
->left
;
1384 if (pRect
->right
> pExtents
->right
)
1385 pExtents
->right
= pRect
->right
;
1390 /***********************************************************************
1393 static BOOL
REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1395 if (dst
!= src
) /* don't want to copy to itself */
1397 if (dst
->size
< src
->numRects
&& !grow_region( dst
, src
->numRects
))
1400 dst
->numRects
= src
->numRects
;
1401 dst
->extents
.left
= src
->extents
.left
;
1402 dst
->extents
.top
= src
->extents
.top
;
1403 dst
->extents
.right
= src
->extents
.right
;
1404 dst
->extents
.bottom
= src
->extents
.bottom
;
1405 memcpy(dst
->rects
, src
->rects
, src
->numRects
* sizeof(RECT
));
1410 /***********************************************************************
1411 * REGION_MirrorRegion
1413 static BOOL
REGION_MirrorRegion( WINEREGION
*dst
, WINEREGION
*src
, int width
)
1422 if (!grow_region( dst
, src
->numRects
)) return FALSE
;
1424 dst
->numRects
= src
->numRects
;
1428 if (!init_region( &tmp
, src
->numRects
)) return FALSE
;
1430 tmp
.numRects
= src
->numRects
;
1433 extents
.left
= width
- src
->extents
.right
;
1434 extents
.right
= width
- src
->extents
.left
;
1435 extents
.top
= src
->extents
.top
;
1436 extents
.bottom
= src
->extents
.bottom
;
1438 for (start
= 0; start
< src
->numRects
; start
= end
)
1440 /* find the end of the current band */
1441 for (end
= start
+ 1; end
< src
->numRects
; end
++)
1442 if (src
->rects
[end
].top
!= src
->rects
[end
- 1].top
) break;
1444 for (i
= 0; i
< end
- start
; i
++)
1446 rects
[start
+ i
].left
= width
- src
->rects
[end
- i
- 1].right
;
1447 rects
[start
+ i
].right
= width
- src
->rects
[end
- i
- 1].left
;
1448 rects
[start
+ i
].top
= src
->rects
[end
- i
- 1].top
;
1449 rects
[start
+ i
].bottom
= src
->rects
[end
- i
- 1].bottom
;
1454 move_rects( dst
, &tmp
);
1456 dst
->extents
= extents
;
1460 /***********************************************************************
1463 INT
mirror_region( HRGN dst
, HRGN src
, INT width
)
1465 WINEREGION
*src_rgn
, *dst_rgn
;
1468 if (!(src_rgn
= GDI_GetObjPtr( src
, OBJ_REGION
))) return ERROR
;
1469 if ((dst_rgn
= GDI_GetObjPtr( dst
, OBJ_REGION
)))
1471 if (REGION_MirrorRegion( dst_rgn
, src_rgn
, width
)) ret
= get_region_type( dst_rgn
);
1472 GDI_ReleaseObj( dst_rgn
);
1474 GDI_ReleaseObj( src_rgn
);
1478 /***********************************************************************
1479 * MirrorRgn (GDI32.@)
1481 BOOL WINAPI
MirrorRgn( HWND hwnd
, HRGN hrgn
)
1483 static const WCHAR user32W
[] = {'u','s','e','r','3','2','.','d','l','l',0};
1484 static BOOL (WINAPI
*pGetWindowRect
)( HWND hwnd
, LPRECT rect
);
1487 /* yes, a HWND in gdi32, don't ask */
1488 if (!pGetWindowRect
)
1490 HMODULE user32
= GetModuleHandleW(user32W
);
1491 if (!user32
) return FALSE
;
1492 if (!(pGetWindowRect
= (void *)GetProcAddress( user32
, "GetWindowRect" ))) return FALSE
;
1494 pGetWindowRect( hwnd
, &rect
);
1495 return mirror_region( hrgn
, hrgn
, rect
.right
- rect
.left
) != ERROR
;
1499 /***********************************************************************
1502 * Attempt to merge the rects in the current band with those in the
1503 * previous one. Used only by REGION_RegionOp.
1506 * The new index for the previous band.
1509 * If coalescing takes place:
1510 * - rectangles in the previous band will have their bottom fields
1512 * - pReg->numRects will be decreased.
1515 static INT
REGION_Coalesce (
1516 WINEREGION
*pReg
, /* Region to coalesce */
1517 INT prevStart
, /* Index of start of previous band */
1518 INT curStart
/* Index of start of current band */
1520 RECT
*pPrevRect
; /* Current rect in previous band */
1521 RECT
*pCurRect
; /* Current rect in current band */
1522 RECT
*pRegEnd
; /* End of region */
1523 INT curNumRects
; /* Number of rectangles in current band */
1524 INT prevNumRects
; /* Number of rectangles in previous band */
1525 INT bandtop
; /* top coordinate for current band */
1527 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1529 pPrevRect
= &pReg
->rects
[prevStart
];
1530 prevNumRects
= curStart
- prevStart
;
1533 * Figure out how many rectangles are in the current band. Have to do
1534 * this because multiple bands could have been added in REGION_RegionOp
1535 * at the end when one region has been exhausted.
1537 pCurRect
= &pReg
->rects
[curStart
];
1538 bandtop
= pCurRect
->top
;
1539 for (curNumRects
= 0;
1540 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1546 if (pCurRect
!= pRegEnd
)
1549 * If more than one band was added, we have to find the start
1550 * of the last band added so the next coalescing job can start
1551 * at the right place... (given when multiple bands are added,
1552 * this may be pointless -- see above).
1555 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1559 curStart
= pRegEnd
- pReg
->rects
;
1560 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1563 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1564 pCurRect
-= curNumRects
;
1566 * The bands may only be coalesced if the bottom of the previous
1567 * matches the top scanline of the current.
1569 if (pPrevRect
->bottom
== pCurRect
->top
)
1572 * Make sure the bands have rects in the same places. This
1573 * assumes that rects have been added in such a way that they
1574 * cover the most area possible. I.e. two rects in a band must
1575 * have some horizontal space between them.
1579 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1580 (pPrevRect
->right
!= pCurRect
->right
))
1583 * The bands don't line up so they can't be coalesced.
1590 } while (prevNumRects
!= 0);
1592 pReg
->numRects
-= curNumRects
;
1593 pCurRect
-= curNumRects
;
1594 pPrevRect
-= curNumRects
;
1597 * The bands may be merged, so set the bottom of each rect
1598 * in the previous band to that of the corresponding rect in
1603 pPrevRect
->bottom
= pCurRect
->bottom
;
1607 } while (curNumRects
!= 0);
1610 * If only one band was added to the region, we have to backup
1611 * curStart to the start of the previous band.
1613 * If more than one band was added to the region, copy the
1614 * other bands down. The assumption here is that the other bands
1615 * came from the same region as the current one and no further
1616 * coalescing can be done on them since it's all been done
1617 * already... curStart is already in the right place.
1619 if (pCurRect
== pRegEnd
)
1621 curStart
= prevStart
;
1627 *pPrevRect
++ = *pCurRect
++;
1628 } while (pCurRect
!= pRegEnd
);
1636 /**********************************************************************
1639 * To keep regions from growing without bound, shrink the array of rectangles
1640 * to match the new number of rectangles in the region.
1642 * Only do this if the number of rectangles allocated is more than
1643 * twice the number of rectangles in the region.
1645 static void REGION_compact( WINEREGION
*reg
)
1647 if ((reg
->numRects
< reg
->size
/ 2) && (reg
->numRects
> RGN_DEFAULT_RECTS
))
1649 RECT
*new_rects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
, reg
->numRects
* sizeof(RECT
) );
1652 reg
->rects
= new_rects
;
1653 reg
->size
= reg
->numRects
;
1658 /***********************************************************************
1661 * Apply an operation to two regions. Called by REGION_Union,
1662 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1668 * The new region is overwritten.
1671 * The idea behind this function is to view the two regions as sets.
1672 * Together they cover a rectangle of area that this function divides
1673 * into horizontal bands where points are covered only by one region
1674 * or by both. For the first case, the nonOverlapFunc is called with
1675 * each the band and the band's upper and lower extents. For the
1676 * second, the overlapFunc is called to process the entire band. It
1677 * is responsible for clipping the rectangles in the band, though
1678 * this function provides the boundaries.
1679 * At the end of each band, the new region is coalesced, if possible,
1680 * to reduce the number of rectangles in the region.
1683 static BOOL
REGION_RegionOp(
1684 WINEREGION
*destReg
, /* Place to store result */
1685 WINEREGION
*reg1
, /* First region in operation */
1686 WINEREGION
*reg2
, /* 2nd region in operation */
1687 BOOL (*overlapFunc
)(WINEREGION
*, RECT
*, RECT
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for over-lapping bands */
1688 BOOL (*nonOverlap1Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for non-overlapping bands in region 1 */
1689 BOOL (*nonOverlap2Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
) /* Function to call for non-overlapping bands in region 2 */
1692 RECT
*r1
; /* Pointer into first region */
1693 RECT
*r2
; /* Pointer into 2d region */
1694 RECT
*r1End
; /* End of 1st region */
1695 RECT
*r2End
; /* End of 2d region */
1696 INT ybot
; /* Bottom of intersection */
1697 INT ytop
; /* Top of intersection */
1698 INT prevBand
; /* Index of start of
1699 * previous band in newReg */
1700 INT curBand
; /* Index of start of current
1702 RECT
*r1BandEnd
; /* End of current band in r1 */
1703 RECT
*r2BandEnd
; /* End of current band in r2 */
1704 INT top
; /* Top of non-overlapping band */
1705 INT bot
; /* Bottom of non-overlapping band */
1709 * set r1, r2, r1End and r2End appropriately, preserve the important
1710 * parts of the destination region until the end in case it's one of
1711 * the two source regions, then mark the "new" region empty, allocating
1712 * another array of rectangles for it to use.
1716 r1End
= r1
+ reg1
->numRects
;
1717 r2End
= r2
+ reg2
->numRects
;
1720 * Allocate a reasonable number of rectangles for the new region. The idea
1721 * is to allocate enough so the individual functions don't need to
1722 * reallocate and copy the array, which is time consuming, yet we don't
1723 * have to worry about using too much memory. I hope to be able to
1724 * nuke the Xrealloc() at the end of this function eventually.
1726 if (!init_region( &newReg
, max(reg1
->numRects
,reg2
->numRects
) * 2 )) return FALSE
;
1729 * Initialize ybot and ytop.
1730 * In the upcoming loop, ybot and ytop serve different functions depending
1731 * on whether the band being handled is an overlapping or non-overlapping
1733 * In the case of a non-overlapping band (only one of the regions
1734 * has points in the band), ybot is the bottom of the most recent
1735 * intersection and thus clips the top of the rectangles in that band.
1736 * ytop is the top of the next intersection between the two regions and
1737 * serves to clip the bottom of the rectangles in the current band.
1738 * For an overlapping band (where the two regions intersect), ytop clips
1739 * the top of the rectangles of both regions and ybot clips the bottoms.
1741 if (reg1
->extents
.top
< reg2
->extents
.top
)
1742 ybot
= reg1
->extents
.top
;
1744 ybot
= reg2
->extents
.top
;
1747 * prevBand serves to mark the start of the previous band so rectangles
1748 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1749 * In the beginning, there is no previous band, so prevBand == curBand
1750 * (curBand is set later on, of course, but the first band will always
1751 * start at index 0). prevBand and curBand must be indices because of
1752 * the possible expansion, and resultant moving, of the new region's
1753 * array of rectangles.
1759 curBand
= newReg
.numRects
;
1762 * This algorithm proceeds one source-band (as opposed to a
1763 * destination band, which is determined by where the two regions
1764 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1765 * rectangle after the last one in the current band for their
1766 * respective regions.
1769 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1775 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1781 * First handle the band that doesn't intersect, if any.
1783 * Note that attention is restricted to one band in the
1784 * non-intersecting region at once, so if a region has n
1785 * bands between the current position and the next place it overlaps
1786 * the other, this entire loop will be passed through n times.
1788 if (r1
->top
< r2
->top
)
1790 top
= max(r1
->top
,ybot
);
1791 bot
= min(r1
->bottom
,r2
->top
);
1793 if ((top
!= bot
) && (nonOverlap1Func
!= NULL
))
1795 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, top
, bot
)) return FALSE
;
1800 else if (r2
->top
< r1
->top
)
1802 top
= max(r2
->top
,ybot
);
1803 bot
= min(r2
->bottom
,r1
->top
);
1805 if ((top
!= bot
) && (nonOverlap2Func
!= NULL
))
1807 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, top
, bot
)) return FALSE
;
1818 * If any rectangles got added to the region, try and coalesce them
1819 * with rectangles from the previous band. Note we could just do
1820 * this test in miCoalesce, but some machines incur a not
1821 * inconsiderable cost for function calls, so...
1823 if (newReg
.numRects
!= curBand
)
1825 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1829 * Now see if we've hit an intersecting band. The two bands only
1830 * intersect if ybot > ytop
1832 ybot
= min(r1
->bottom
, r2
->bottom
);
1833 curBand
= newReg
.numRects
;
1836 if (!overlapFunc(&newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
)) return FALSE
;
1839 if (newReg
.numRects
!= curBand
)
1841 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1845 * If we've finished with a band (bottom == ybot) we skip forward
1846 * in the region to the next band.
1848 if (r1
->bottom
== ybot
)
1852 if (r2
->bottom
== ybot
)
1856 } while ((r1
!= r1End
) && (r2
!= r2End
));
1859 * Deal with whichever region still has rectangles left.
1861 curBand
= newReg
.numRects
;
1864 if (nonOverlap1Func
!= NULL
)
1869 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1873 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, max(r1
->top
,ybot
), r1
->bottom
))
1876 } while (r1
!= r1End
);
1879 else if ((r2
!= r2End
) && (nonOverlap2Func
!= NULL
))
1884 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1888 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, max(r2
->top
,ybot
), r2
->bottom
))
1891 } while (r2
!= r2End
);
1894 if (newReg
.numRects
!= curBand
)
1896 REGION_Coalesce (&newReg
, prevBand
, curBand
);
1899 REGION_compact( &newReg
);
1900 move_rects( destReg
, &newReg
);
1904 /***********************************************************************
1905 * Region Intersection
1906 ***********************************************************************/
1909 /***********************************************************************
1912 * Handle an overlapping band for REGION_Intersect.
1918 * Rectangles may be added to the region.
1921 static BOOL
REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1922 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1927 while ((r1
!= r1End
) && (r2
!= r2End
))
1929 left
= max(r1
->left
, r2
->left
);
1930 right
= min(r1
->right
, r2
->right
);
1933 * If there's any overlap between the two rectangles, add that
1934 * overlap to the new region.
1935 * There's no need to check for subsumption because the only way
1936 * such a need could arise is if some region has two rectangles
1937 * right next to each other. Since that should never happen...
1941 if (!add_rect( pReg
, left
, top
, right
, bottom
)) return FALSE
;
1945 * Need to advance the pointers. Shift the one that extends
1946 * to the right the least, since the other still has a chance to
1947 * overlap with that region's next rectangle, if you see what I mean.
1949 if (r1
->right
< r2
->right
)
1953 else if (r2
->right
< r1
->right
)
1966 /***********************************************************************
1967 * REGION_IntersectRegion
1969 static BOOL
REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1972 /* check for trivial reject */
1973 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1974 (!overlapping(®1
->extents
, ®2
->extents
)))
1975 newReg
->numRects
= 0;
1977 if (!REGION_RegionOp (newReg
, reg1
, reg2
, REGION_IntersectO
, NULL
, NULL
)) return FALSE
;
1980 * Can't alter newReg's extents before we call miRegionOp because
1981 * it might be one of the source regions and miRegionOp depends
1982 * on the extents of those regions being the same. Besides, this
1983 * way there's no checking against rectangles that will be nuked
1984 * due to coalescing, so we have to examine fewer rectangles.
1986 REGION_SetExtents(newReg
);
1990 /***********************************************************************
1992 ***********************************************************************/
1994 /***********************************************************************
1997 * Handle a non-overlapping band for the union operation. Just
1998 * Adds the rectangles into the region. Doesn't have to check for
1999 * subsumption or anything.
2005 * pReg->numRects is incremented and the final rectangles overwritten
2006 * with the rectangles we're passed.
2009 static BOOL
REGION_UnionNonO(WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
2013 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
2019 /***********************************************************************
2022 * Handle an overlapping band for the union operation. Picks the
2023 * left-most rectangle each time and merges it into the region.
2029 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2033 static BOOL
REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2034 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2036 #define MERGERECT(r) \
2037 if ((pReg->numRects != 0) && \
2038 (pReg->rects[pReg->numRects-1].top == top) && \
2039 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
2040 (pReg->rects[pReg->numRects-1].right >= r->left)) \
2042 if (pReg->rects[pReg->numRects-1].right < r->right) \
2043 pReg->rects[pReg->numRects-1].right = r->right; \
2047 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
2051 while ((r1
!= r1End
) && (r2
!= r2End
))
2053 if (r1
->left
< r2
->left
)
2068 } while (r1
!= r1End
);
2070 else while (r2
!= r2End
)
2078 /***********************************************************************
2079 * REGION_UnionRegion
2081 static BOOL
REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
, WINEREGION
*reg2
)
2085 /* checks all the simple cases */
2088 * Region 1 and 2 are the same or region 1 is empty
2090 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
2093 ret
= REGION_CopyRegion(newReg
, reg2
);
2098 * if nothing to union (region 2 empty)
2100 if (!(reg2
->numRects
))
2103 ret
= REGION_CopyRegion(newReg
, reg1
);
2108 * Region 1 completely subsumes region 2
2110 if ((reg1
->numRects
== 1) &&
2111 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
2112 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
2113 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
2114 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
2117 ret
= REGION_CopyRegion(newReg
, reg1
);
2122 * Region 2 completely subsumes region 1
2124 if ((reg2
->numRects
== 1) &&
2125 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
2126 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
2127 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
2128 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
2131 ret
= REGION_CopyRegion(newReg
, reg2
);
2135 if ((ret
= REGION_RegionOp (newReg
, reg1
, reg2
, REGION_UnionO
, REGION_UnionNonO
, REGION_UnionNonO
)))
2137 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
2138 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
2139 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
2140 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
2145 /***********************************************************************
2146 * Region Subtraction
2147 ***********************************************************************/
2149 /***********************************************************************
2150 * REGION_SubtractNonO1
2152 * Deal with non-overlapping band for subtraction. Any parts from
2153 * region 2 we discard. Anything from region 1 we add to the region.
2159 * pReg may be affected.
2162 static BOOL
REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
2166 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
2173 /***********************************************************************
2176 * Overlapping band subtraction. x1 is the left-most point not yet
2183 * pReg may have rectangles added to it.
2186 static BOOL
REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2187 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2189 INT left
= r1
->left
;
2191 while ((r1
!= r1End
) && (r2
!= r2End
))
2193 if (r2
->right
<= left
)
2196 * Subtrahend missed the boat: go to next subtrahend.
2200 else if (r2
->left
<= left
)
2203 * Subtrahend precedes minuend: nuke left edge of minuend.
2206 if (left
>= r1
->right
)
2209 * Minuend completely covered: advance to next minuend and
2210 * reset left fence to edge of new minuend.
2219 * Subtrahend now used up since it doesn't extend beyond
2225 else if (r2
->left
< r1
->right
)
2228 * Left part of subtrahend covers part of minuend: add uncovered
2229 * part of minuend to region and skip to next subtrahend.
2231 if (!add_rect( pReg
, left
, top
, r2
->left
, bottom
)) return FALSE
;
2233 if (left
>= r1
->right
)
2236 * Minuend used up: advance to new...
2245 * Subtrahend used up
2253 * Minuend used up: add any remaining piece before advancing.
2255 if (r1
->right
> left
)
2257 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2266 * Add remaining minuend rectangles to region.
2270 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2280 /***********************************************************************
2281 * REGION_SubtractRegion
2283 * Subtract regS from regM and leave the result in regD.
2284 * S stands for subtrahend, M for minuend and D for difference.
2290 * regD is overwritten.
2293 static BOOL
REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
, WINEREGION
*regS
)
2295 /* check for trivial reject */
2296 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2297 (!overlapping(®M
->extents
, ®S
->extents
)) )
2298 return REGION_CopyRegion(regD
, regM
);
2300 if (!REGION_RegionOp (regD
, regM
, regS
, REGION_SubtractO
, REGION_SubtractNonO1
, NULL
))
2304 * Can't alter newReg's extents before we call miRegionOp because
2305 * it might be one of the source regions and miRegionOp depends
2306 * on the extents of those regions being the unaltered. Besides, this
2307 * way there's no checking against rectangles that will be nuked
2308 * due to coalescing, so we have to examine fewer rectangles.
2310 REGION_SetExtents (regD
);
2314 /***********************************************************************
2317 static BOOL
REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
, WINEREGION
*srb
)
2319 WINEREGION tra
, trb
;
2322 if (!init_region( &tra
, sra
->numRects
+ 1 )) return FALSE
;
2323 if ((ret
= init_region( &trb
, srb
->numRects
+ 1 )))
2325 ret
= REGION_SubtractRegion(&tra
,sra
,srb
) &&
2326 REGION_SubtractRegion(&trb
,srb
,sra
) &&
2327 REGION_UnionRegion(dr
,&tra
,&trb
);
2328 destroy_region(&trb
);
2330 destroy_region(&tra
);
2334 /**************************************************************************
2338 *************************************************************************/
2340 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2341 #define SMALL_COORDINATE 0x80000000
2343 /***********************************************************************
2344 * REGION_InsertEdgeInET
2346 * Insert the given edge into the edge table.
2347 * First we must find the correct bucket in the
2348 * Edge table, then find the right slot in the
2349 * bucket. Finally, we can insert it.
2352 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2353 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2357 ScanLineList
*pSLL
, *pPrevSLL
;
2358 ScanLineListBlock
*tmpSLLBlock
;
2361 * find the right bucket to put the edge into
2363 pPrevSLL
= &ET
->scanlines
;
2364 pSLL
= pPrevSLL
->next
;
2365 while (pSLL
&& (pSLL
->scanline
< scanline
))
2372 * reassign pSLL (pointer to ScanLineList) if necessary
2374 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2376 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2378 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2381 WARN("Can't alloc SLLB\n");
2384 (*SLLBlock
)->next
= tmpSLLBlock
;
2385 tmpSLLBlock
->next
= NULL
;
2386 *SLLBlock
= tmpSLLBlock
;
2389 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2391 pSLL
->next
= pPrevSLL
->next
;
2392 list_init( &pSLL
->edgelist
);
2393 pPrevSLL
->next
= pSLL
;
2395 pSLL
->scanline
= scanline
;
2398 * now insert the edge in the right bucket
2400 LIST_FOR_EACH( ptr
, &pSLL
->edgelist
)
2402 struct edge_table_entry
*entry
= LIST_ENTRY( ptr
, struct edge_table_entry
, entry
);
2403 if (entry
->bres
.minor_axis
>= ETE
->bres
.minor_axis
) break;
2405 list_add_before( ptr
, &ETE
->entry
);
2408 /***********************************************************************
2409 * REGION_CreateEdgeTable
2411 * This routine creates the edge table for
2412 * scan converting polygons.
2413 * The Edge Table (ET) looks like:
2417 * | ymax | ScanLineLists
2418 * |scanline|-->------------>-------------->...
2419 * -------- |scanline| |scanline|
2420 * |edgelist| |edgelist|
2421 * --------- ---------
2425 * list of ETEs list of ETEs
2427 * where ETE is an EdgeTableEntry data structure,
2428 * and there is one ScanLineList per scanline at
2429 * which an edge is initially entered.
2432 static void REGION_CreateEdgeTable(const INT
*Count
, INT nbpolygons
,
2433 const POINT
*pts
, EdgeTable
*ET
,
2434 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2436 const POINT
*top
, *bottom
;
2437 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2443 * initialize the Edge Table.
2445 ET
->scanlines
.next
= NULL
;
2446 ET
->ymax
= SMALL_COORDINATE
;
2447 ET
->ymin
= LARGE_COORDINATE
;
2448 pSLLBlock
->next
= NULL
;
2451 for(poly
= 0; poly
< nbpolygons
; poly
++)
2453 count
= Count
[poly
];
2461 * for each vertex in the array of points.
2462 * In this loop we are dealing with two vertices at
2463 * a time -- these make up one edge of the polygon.
2470 * find out which point is above and which is below.
2472 if (PrevPt
->y
> CurrPt
->y
)
2474 bottom
= PrevPt
, top
= CurrPt
;
2475 pETEs
->ClockWise
= 0;
2479 bottom
= CurrPt
, top
= PrevPt
;
2480 pETEs
->ClockWise
= 1;
2484 * don't add horizontal edges to the Edge table.
2486 if (bottom
->y
!= top
->y
)
2488 pETEs
->ymax
= bottom
->y
-1;
2489 /* -1 so we don't get last scanline */
2492 * initialize integer edge algorithm
2494 dy
= bottom
->y
- top
->y
;
2495 bres_init_polygon(dy
, top
->x
, bottom
->x
, &pETEs
->bres
);
2497 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2500 if (PrevPt
->y
> ET
->ymax
)
2501 ET
->ymax
= PrevPt
->y
;
2502 if (PrevPt
->y
< ET
->ymin
)
2503 ET
->ymin
= PrevPt
->y
;
2512 /***********************************************************************
2515 * This routine moves EdgeTableEntries from the
2516 * EdgeTable into the Active Edge Table,
2517 * leaving them sorted by smaller x coordinate.
2520 static void REGION_loadAET( struct list
*AET
, struct list
*ETEs
)
2522 struct edge_table_entry
*ptr
, *next
, *entry
;
2523 struct list
*active
;
2525 LIST_FOR_EACH_ENTRY_SAFE( ptr
, next
, ETEs
, struct edge_table_entry
, entry
)
2527 LIST_FOR_EACH( active
, AET
)
2529 entry
= LIST_ENTRY( active
, struct edge_table_entry
, entry
);
2530 if (entry
->bres
.minor_axis
>= ptr
->bres
.minor_axis
) break;
2532 list_remove( &ptr
->entry
);
2533 list_add_before( active
, &ptr
->entry
);
2537 /***********************************************************************
2538 * REGION_computeWAET
2540 * This routine links the AET by the
2541 * nextWETE (winding EdgeTableEntry) link for
2542 * use by the winding number rule. The final
2543 * Active Edge Table (AET) might look something
2547 * ---------- --------- ---------
2548 * |ymax | |ymax | |ymax |
2549 * | ... | |... | |... |
2550 * |next |->|next |->|next |->...
2551 * |nextWETE| |nextWETE| |nextWETE|
2552 * --------- --------- ^--------
2554 * V-------------------> V---> ...
2557 static void REGION_computeWAET( struct list
*AET
, struct list
*WETE
)
2559 struct edge_table_entry
*active
;
2564 LIST_FOR_EACH_ENTRY( active
, AET
, struct edge_table_entry
, entry
)
2566 if (active
->ClockWise
)
2571 if ((!inside
&& !isInside
) || (inside
&& isInside
))
2573 list_add_tail( WETE
, &active
->winding_entry
);
2579 /***********************************************************************
2580 * REGION_InsertionSort
2582 * Just a simple insertion sort to sort the Active Edge Table.
2585 static BOOL
REGION_InsertionSort( struct list
*AET
)
2587 struct edge_table_entry
*active
, *next
, *insert
;
2588 BOOL changed
= FALSE
;
2590 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, AET
, struct edge_table_entry
, entry
)
2592 LIST_FOR_EACH_ENTRY( insert
, AET
, struct edge_table_entry
, entry
)
2594 if (insert
== active
) break;
2595 if (insert
->bres
.minor_axis
> active
->bres
.minor_axis
) break;
2597 if (insert
== active
) continue;
2598 list_remove( &active
->entry
);
2599 list_add_before( &insert
->entry
, &active
->entry
);
2605 /***********************************************************************
2606 * REGION_FreeStorage
2610 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2612 ScanLineListBlock
*tmpSLLBlock
;
2616 tmpSLLBlock
= pSLLBlock
->next
;
2617 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2618 pSLLBlock
= tmpSLLBlock
;
2623 /***********************************************************************
2624 * REGION_PtsToRegion
2626 * Create an array of rectangles from a list of points.
2628 static WINEREGION
*REGION_PtsToRegion( struct point_block
*FirstPtBlock
)
2631 struct point_block
*pb
;
2632 int i
, size
, cur_band
= 0, prev_band
= 0;
2636 for (pb
= FirstPtBlock
, size
= 0; pb
; pb
= pb
->next
) size
+= pb
->count
;
2637 if (!(reg
= alloc_region( size
))) return NULL
;
2639 extents
= ®
->extents
;
2640 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2642 for (pb
= FirstPtBlock
; pb
; pb
= pb
->next
)
2644 /* the loop uses 2 points per iteration */
2646 for (pts
= pb
->pts
; i
--; pts
+= 2) {
2647 if (pts
->x
== pts
[1].x
)
2650 if (reg
->numRects
&& pts
[0].y
!= reg
->rects
[cur_band
].top
)
2652 prev_band
= REGION_Coalesce( reg
, prev_band
, cur_band
);
2653 cur_band
= reg
->numRects
;
2656 add_rect( reg
, pts
[0].x
, pts
[0].y
, pts
[1].x
, pts
[1].y
+ 1 );
2657 if (pts
[0].x
< extents
->left
)
2658 extents
->left
= pts
[0].x
;
2659 if (pts
[1].x
> extents
->right
)
2660 extents
->right
= pts
[1].x
;
2664 if (reg
->numRects
) {
2665 REGION_Coalesce( reg
, prev_band
, cur_band
);
2666 extents
->top
= reg
->rects
[0].top
;
2667 extents
->bottom
= reg
->rects
[reg
->numRects
-1].bottom
;
2672 extents
->bottom
= 0;
2674 REGION_compact( reg
);
2679 /***********************************************************************
2680 * CreatePolyPolygonRgn (GDI32.@)
2682 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2683 INT nbpolygons
, INT mode
)
2687 INT y
; /* current scanline */
2688 struct list WETE
, *pWETE
; /* Winding Edge Table */
2689 ScanLineList
*pSLL
; /* current scanLineList */
2690 EdgeTable ET
; /* header node for ET */
2691 struct list AET
; /* header for AET */
2692 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2693 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2694 BOOL fixWAET
= FALSE
;
2695 struct point_block FirstPtBlock
, *block
; /* PtBlock buffers */
2696 struct edge_table_entry
*active
, *next
;
2699 TRACE("%p, count %d, polygons %d, mode %d\n", Pts
, *Count
, nbpolygons
, mode
);
2701 /* special case a rectangle */
2703 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2704 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2705 (((Pts
[0].y
== Pts
[1].y
) &&
2706 (Pts
[1].x
== Pts
[2].x
) &&
2707 (Pts
[2].y
== Pts
[3].y
) &&
2708 (Pts
[3].x
== Pts
[0].x
)) ||
2709 ((Pts
[0].x
== Pts
[1].x
) &&
2710 (Pts
[1].y
== Pts
[2].y
) &&
2711 (Pts
[2].x
== Pts
[3].x
) &&
2712 (Pts
[3].y
== Pts
[0].y
))))
2713 return CreateRectRgn( min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2714 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2716 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2717 total
+= Count
[poly
];
2718 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2721 REGION_CreateEdgeTable(Count
, nbpolygons
, Pts
, &ET
, pETEs
, &SLLBlock
);
2723 pSLL
= ET
.scanlines
.next
;
2724 block
= &FirstPtBlock
;
2725 FirstPtBlock
.count
= 0;
2726 FirstPtBlock
.next
= NULL
;
2728 if (mode
!= WINDING
) {
2732 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2734 * Add a new edge to the active edge table when we
2735 * get to the next edge.
2737 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2738 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2742 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, &AET
, struct edge_table_entry
, entry
)
2744 block
= add_point( block
, active
->bres
.minor_axis
, y
);
2745 if (!block
) goto done
;
2747 if (active
->ymax
== y
) /* leaving this edge */
2748 list_remove( &active
->entry
);
2750 bres_incr_polygon( &active
->bres
);
2752 REGION_InsertionSort(&AET
);
2759 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2761 * Add a new edge to the active edge table when we
2762 * get to the next edge.
2764 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2765 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2766 REGION_computeWAET( &AET
, &WETE
);
2769 pWETE
= list_head( &WETE
);
2772 * for each active edge
2774 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, &AET
, struct edge_table_entry
, entry
)
2777 * add to the buffer only those edges that
2778 * are in the Winding active edge table.
2780 if (pWETE
== &active
->winding_entry
) {
2781 block
= add_point( block
, active
->bres
.minor_axis
, y
);
2782 if (!block
) goto done
;
2783 pWETE
= list_next( &WETE
, pWETE
);
2785 if (active
->ymax
== y
) /* leaving this edge */
2787 list_remove( &active
->entry
);
2791 bres_incr_polygon( &active
->bres
);
2795 * recompute the winding active edge table if
2796 * we just resorted or have exited an edge.
2798 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2799 REGION_computeWAET( &AET
, &WETE
);
2805 if (!(obj
= REGION_PtsToRegion( &FirstPtBlock
))) goto done
;
2806 if (!(hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
)))
2810 REGION_FreeStorage(SLLBlock
.next
);
2811 free_point_blocks( FirstPtBlock
.next
);
2812 HeapFree( GetProcessHeap(), 0, pETEs
);
2817 /***********************************************************************
2818 * CreatePolygonRgn (GDI32.@)
2820 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2823 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);