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 new_rects
= HeapReAlloc( GetProcessHeap(), 0, rgn
->rects
, size
* sizeof(RECT
) );
135 if (!new_rects
) return FALSE
;
136 rgn
->rects
= new_rects
;
141 static BOOL
add_rect( WINEREGION
*reg
, INT left
, INT top
, INT right
, INT bottom
)
144 if (reg
->numRects
>= reg
->size
&& !grow_region( reg
, 2 * reg
->size
))
147 rect
= reg
->rects
+ reg
->numRects
++;
151 rect
->bottom
= bottom
;
155 static inline void empty_region( WINEREGION
*reg
)
158 reg
->extents
.left
= reg
->extents
.top
= reg
->extents
.right
= reg
->extents
.bottom
= 0;
161 static inline BOOL
is_in_rect( const RECT
*rect
, int x
, int y
)
163 return (rect
->right
> x
&& rect
->left
<= x
&& rect
->bottom
> y
&& rect
->top
<= y
);
167 * number of points to buffer before sending them off
168 * to scanlines() : Must be an even number
170 #define NUMPTSTOBUFFER 200
173 * used to allocate buffers for points and link
174 * the buffers together
179 POINT pts
[NUMPTSTOBUFFER
];
181 struct point_block
*next
;
184 static struct point_block
*add_point( struct point_block
*block
, int x
, int y
)
186 if (block
->count
== NUMPTSTOBUFFER
)
188 struct point_block
*new = HeapAlloc( GetProcessHeap(), 0, sizeof(*new) );
189 if (!new) return NULL
;
195 block
->pts
[block
->count
].x
= x
;
196 block
->pts
[block
->count
].y
= y
;
201 static void free_point_blocks( struct point_block
*block
)
205 struct point_block
*tmp
= block
->next
;
206 HeapFree( GetProcessHeap(), 0, block
);
213 * This file contains a few macros to help track
214 * the edge of a filled object. The object is assumed
215 * to be filled in scanline order, and thus the
216 * algorithm used is an extension of Bresenham's line
217 * drawing algorithm which assumes that y is always the
219 * Since these pieces of code are the same for any filled shape,
220 * it is more convenient to gather the library in one
221 * place, but since these pieces of code are also in
222 * the inner loops of output primitives, procedure call
223 * overhead is out of the question.
224 * See the author for a derivation if needed.
229 * This structure contains all of the information needed
230 * to run the bresenham algorithm.
231 * The variables may be hardcoded into the declarations
232 * instead of using this structure to make use of
233 * register declarations.
237 INT minor_axis
; /* minor axis */
238 INT d
; /* decision variable */
239 INT m
, m1
; /* slope and slope+1 */
240 INT incr1
, incr2
; /* error increments */
245 * In scan converting polygons, we want to choose those pixels
246 * which are inside the polygon. Thus, we add .5 to the starting
247 * x coordinate for both left and right edges. Now we choose the
248 * first pixel which is inside the pgon for the left edge and the
249 * first pixel which is outside the pgon for the right edge.
250 * Draw the left pixel, but not the right.
252 * How to add .5 to the starting x coordinate:
253 * If the edge is moving to the right, then subtract dy from the
254 * error term from the general form of the algorithm.
255 * If the edge is moving to the left, then add dy to the error term.
257 * The reason for the difference between edges moving to the left
258 * and edges moving to the right is simple: If an edge is moving
259 * to the right, then we want the algorithm to flip immediately.
260 * If it is moving to the left, then we don't want it to flip until
261 * we traverse an entire pixel.
263 static inline void bres_init_polygon( int dy
, int x1
, int x2
, struct bres_info
*bres
)
268 * if the edge is horizontal, then it is ignored
269 * and assumed not to be processed. Otherwise, do this stuff.
273 bres
->minor_axis
= x1
;
278 bres
->m1
= bres
->m
- 1;
279 bres
->incr1
= -2 * dx
+ 2 * dy
* bres
->m1
;
280 bres
->incr2
= -2 * dx
+ 2 * dy
* bres
->m
;
281 bres
->d
= 2 * bres
->m
* dy
- 2 * dx
- 2 * dy
;
286 bres
->m1
= bres
->m
+ 1;
287 bres
->incr1
= 2 * dx
- 2 * dy
* bres
->m1
;
288 bres
->incr2
= 2 * dx
- 2 * dy
* bres
->m
;
289 bres
->d
= -2 * bres
->m
* dy
+ 2 * dx
;
293 static inline void bres_incr_polygon( struct bres_info
*bres
)
297 bres
->minor_axis
+= bres
->m1
;
298 bres
->d
+= bres
->incr1
;
301 bres
->minor_axis
+= bres
->m
;
302 bres
->d
+= bres
->incr2
;
306 bres
->minor_axis
+= bres
->m1
;
307 bres
->d
+= bres
->incr1
;
310 bres
->minor_axis
+= bres
->m
;
311 bres
->d
+= bres
->incr2
;
318 * These are the data structures needed to scan
319 * convert regions. Two different scan conversion
320 * methods are available -- the even-odd method, and
321 * the winding number method.
322 * The even-odd rule states that a point is inside
323 * the polygon if a ray drawn from that point in any
324 * direction will pass through an odd number of
326 * By the winding number rule, a point is decided
327 * to be inside the polygon if a ray drawn from that
328 * point in any direction passes through a different
329 * number of clockwise and counter-clockwise path
332 * These data structures are adapted somewhat from
333 * the algorithm in (Foley/Van Dam) for scan converting
335 * The basic algorithm is to start at the top (smallest y)
336 * of the polygon, stepping down to the bottom of
337 * the polygon by incrementing the y coordinate. We
338 * keep a list of edges which the current scanline crosses,
339 * sorted by x. This list is called the Active Edge Table (AET)
340 * As we change the y-coordinate, we update each entry in
341 * in the active edge table to reflect the edges new xcoord.
342 * This list must be sorted at each scanline in case
343 * two edges intersect.
344 * We also keep a data structure known as the Edge Table (ET),
345 * which keeps track of all the edges which the current
346 * scanline has not yet reached. The ET is basically a
347 * list of ScanLineList structures containing a list of
348 * edges which are entered at a given scanline. There is one
349 * ScanLineList per scanline at which an edge is entered.
350 * When we enter a new edge, we move it from the ET to the AET.
352 * From the AET, we can implement the even-odd rule as in
354 * The winding number rule is a little trickier. We also
355 * keep the EdgeTableEntries in the AET linked by the
356 * nextWETE (winding EdgeTableEntry) link. This allows
357 * the edges to be linked just as before for updating
358 * purposes, but only uses the edges linked by the nextWETE
359 * link as edges representing spans of the polygon to
360 * drawn (as with the even-odd rule).
363 typedef struct edge_table_entry
{
365 struct list winding_entry
;
366 INT ymax
; /* ycoord at which we exit this edge. */
367 struct bres_info bres
; /* Bresenham info to run the edge */
368 int ClockWise
; /* flag for winding number rule */
372 typedef struct _ScanLineList
{
373 struct list edgelist
;
374 INT scanline
; /* the scanline represented */
375 struct _ScanLineList
*next
; /* next in the list */
380 INT ymax
; /* ymax for the polygon */
381 INT ymin
; /* ymin for the polygon */
382 ScanLineList scanlines
; /* header node */
387 * Here is a struct to help with storage allocation
388 * so we can allocate a big chunk at a time, and then take
389 * pieces from this heap when we need to.
391 #define SLLSPERBLOCK 25
393 typedef struct _ScanLineListBlock
{
394 ScanLineList SLLs
[SLLSPERBLOCK
];
395 struct _ScanLineListBlock
*next
;
399 /* Note the parameter order is different from the X11 equivalents */
401 static BOOL
REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
402 static BOOL
REGION_OffsetRegion(WINEREGION
*d
, WINEREGION
*s
, INT x
, INT y
);
403 static BOOL
REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
404 static BOOL
REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
405 static BOOL
REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
406 static BOOL
REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
407 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
409 #define RGN_DEFAULT_RECTS 2
412 /***********************************************************************
415 static inline INT
get_region_type( const WINEREGION
*obj
)
417 switch(obj
->numRects
)
419 case 0: return NULLREGION
;
420 case 1: return SIMPLEREGION
;
421 default: return COMPLEXREGION
;
426 /***********************************************************************
428 * Outputs the contents of a WINEREGION
430 static void REGION_DumpRegion(WINEREGION
*pReg
)
432 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
434 TRACE("Region %p: %s %d rects\n", pReg
, wine_dbgstr_rect(&pReg
->extents
), pReg
->numRects
);
435 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
436 TRACE("\t%s\n", wine_dbgstr_rect(pRect
));
441 /***********************************************************************
444 * Initialize a new empty region.
446 static BOOL
init_region( WINEREGION
*pReg
, INT n
)
448 if (!(pReg
->rects
= HeapAlloc(GetProcessHeap(), 0, n
* sizeof( RECT
)))) return FALSE
;
454 /***********************************************************************
457 static void destroy_region( WINEREGION
*pReg
)
459 HeapFree( GetProcessHeap(), 0, pReg
->rects
);
462 /***********************************************************************
465 static void free_region( WINEREGION
*rgn
)
467 destroy_region( rgn
);
468 HeapFree( GetProcessHeap(), 0, rgn
);
471 /***********************************************************************
474 static WINEREGION
*alloc_region( INT n
)
476 WINEREGION
*rgn
= HeapAlloc( GetProcessHeap(), 0, sizeof(*rgn
) );
478 if (rgn
&& !init_region( rgn
, n
))
486 /************************************************************
489 * Move rectangles from src to dst leaving src with no rectangles.
491 static inline void move_rects( WINEREGION
*dst
, WINEREGION
*src
)
493 destroy_region( dst
);
494 dst
->rects
= src
->rects
;
495 dst
->size
= src
->size
;
496 dst
->numRects
= src
->numRects
;
502 /***********************************************************************
503 * REGION_DeleteObject
505 static BOOL
REGION_DeleteObject( HGDIOBJ handle
)
507 WINEREGION
*rgn
= free_gdi_handle( handle
);
509 if (!rgn
) return FALSE
;
514 /***********************************************************************
515 * REGION_SelectObject
517 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, HDC hdc
)
519 return ULongToHandle(SelectClipRgn( hdc
, handle
));
523 /***********************************************************************
524 * REGION_OffsetRegion
525 * Offset a WINEREGION by x,y
527 static BOOL
REGION_OffsetRegion( WINEREGION
*rgn
, WINEREGION
*srcrgn
, INT x
, INT y
)
531 if (!REGION_CopyRegion( rgn
, srcrgn
)) return FALSE
;
534 int nbox
= rgn
->numRects
;
535 RECT
*pbox
= rgn
->rects
;
545 rgn
->extents
.left
+= x
;
546 rgn
->extents
.right
+= x
;
547 rgn
->extents
.top
+= y
;
548 rgn
->extents
.bottom
+= y
;
554 /***********************************************************************
555 * OffsetRgn (GDI32.@)
557 * Moves a region by the specified X- and Y-axis offsets.
560 * hrgn [I] Region to offset.
561 * x [I] Offset right if positive or left if negative.
562 * y [I] Offset down if positive or up if negative.
566 * NULLREGION - The new region is empty.
567 * SIMPLEREGION - The new region can be represented by one rectangle.
568 * COMPLEXREGION - The new region can only be represented by more than
572 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
574 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
577 TRACE("%p %d,%d\n", hrgn
, x
, y
);
582 REGION_OffsetRegion( obj
, obj
, x
, y
);
584 ret
= get_region_type( obj
);
585 GDI_ReleaseObj( hrgn
);
590 /***********************************************************************
591 * GetRgnBox (GDI32.@)
593 * Retrieves the bounding rectangle of the region. The bounding rectangle
594 * is the smallest rectangle that contains the entire region.
597 * hrgn [I] Region to retrieve bounding rectangle from.
598 * rect [O] Rectangle that will receive the coordinates of the bounding
602 * NULLREGION - The new region is empty.
603 * SIMPLEREGION - The new region can be represented by one rectangle.
604 * COMPLEXREGION - The new region can only be represented by more than
607 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
609 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
613 rect
->left
= obj
->extents
.left
;
614 rect
->top
= obj
->extents
.top
;
615 rect
->right
= obj
->extents
.right
;
616 rect
->bottom
= obj
->extents
.bottom
;
617 TRACE("%p %s\n", hrgn
, wine_dbgstr_rect(rect
));
618 ret
= get_region_type( obj
);
619 GDI_ReleaseObj(hrgn
);
626 /***********************************************************************
627 * CreateRectRgn (GDI32.@)
629 * Creates a simple rectangular region.
632 * left [I] Left coordinate of rectangle.
633 * top [I] Top coordinate of rectangle.
634 * right [I] Right coordinate of rectangle.
635 * bottom [I] Bottom coordinate of rectangle.
638 * Success: Handle to region.
641 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
646 if (!(obj
= alloc_region( RGN_DEFAULT_RECTS
))) return 0;
648 if (!(hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
)))
653 TRACE( "%d,%d-%d,%d returning %p\n", left
, top
, right
, bottom
, hrgn
);
654 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
659 /***********************************************************************
660 * CreateRectRgnIndirect (GDI32.@)
662 * Creates a simple rectangular region.
665 * rect [I] Coordinates of rectangular region.
668 * Success: Handle to region.
671 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
673 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
677 /***********************************************************************
678 * SetRectRgn (GDI32.@)
680 * Sets a region to a simple rectangular region.
683 * hrgn [I] Region to convert.
684 * left [I] Left coordinate of rectangle.
685 * top [I] Top coordinate of rectangle.
686 * right [I] Right coordinate of rectangle.
687 * bottom [I] Bottom coordinate of rectangle.
694 * Allows either or both left and top to be greater than right or bottom.
696 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
697 INT right
, INT bottom
)
701 TRACE("%p %d,%d-%d,%d\n", hrgn
, left
, top
, right
, bottom
);
703 if (!(obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
))) return FALSE
;
705 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
706 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
708 if((left
!= right
) && (top
!= bottom
))
710 obj
->rects
->left
= obj
->extents
.left
= left
;
711 obj
->rects
->top
= obj
->extents
.top
= top
;
712 obj
->rects
->right
= obj
->extents
.right
= right
;
713 obj
->rects
->bottom
= obj
->extents
.bottom
= bottom
;
719 GDI_ReleaseObj( hrgn
);
724 /***********************************************************************
725 * CreateRoundRectRgn (GDI32.@)
727 * Creates a rectangular region with rounded corners.
730 * left [I] Left coordinate of rectangle.
731 * top [I] Top coordinate of rectangle.
732 * right [I] Right coordinate of rectangle.
733 * bottom [I] Bottom coordinate of rectangle.
734 * ellipse_width [I] Width of the ellipse at each corner.
735 * ellipse_height [I] Height of the ellipse at each corner.
738 * Success: Handle to region.
742 * If ellipse_width or ellipse_height is less than 2 logical units then
743 * it is treated as though CreateRectRgn() was called instead.
745 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
746 INT right
, INT bottom
,
747 INT ellipse_width
, INT ellipse_height
)
752 INT64 asq
, bsq
, dx
, dy
, err
;
755 /* Make the dimensions sensible */
757 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
758 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
759 /* the region is for the rectangle interior, but only at right and bottom for some reason */
763 ellipse_width
= min( right
- left
, abs( ellipse_width
));
764 ellipse_height
= min( bottom
- top
, abs( ellipse_height
));
766 /* Check if we can do a normal rectangle instead */
768 if ((ellipse_width
< 2) || (ellipse_height
< 2))
769 return CreateRectRgn( left
, top
, right
, bottom
);
771 if (!(obj
= alloc_region( ellipse_height
))) return 0;
772 obj
->numRects
= ellipse_height
;
773 obj
->extents
.left
= left
;
774 obj
->extents
.top
= top
;
775 obj
->extents
.right
= right
;
776 obj
->extents
.bottom
= bottom
;
779 /* based on an algorithm by Alois Zingl */
781 a
= ellipse_width
- 1;
782 b
= ellipse_height
- 1;
783 asq
= (INT64
)8 * a
* a
;
784 bsq
= (INT64
)8 * b
* b
;
785 dx
= (INT64
)4 * b
* b
* (1 - a
);
786 dy
= (INT64
)4 * a
* a
* (1 + (b
% 2));
787 err
= dx
+ dy
+ a
* a
* (b
% 2);
790 y
= ellipse_height
/ 2;
792 rects
[y
].left
= left
;
793 rects
[y
].right
= right
;
795 while (x
<= ellipse_width
/ 2)
807 rects
[y
].left
= left
+ x
;
808 rects
[y
].right
= right
- x
;
811 for (i
= 0; i
< ellipse_height
/ 2; i
++)
813 rects
[i
].left
= rects
[b
- i
].left
;
814 rects
[i
].right
= rects
[b
- i
].right
;
815 rects
[i
].top
= top
+ i
;
816 rects
[i
].bottom
= rects
[i
].top
+ 1;
818 for (; i
< ellipse_height
; i
++)
820 rects
[i
].top
= bottom
- ellipse_height
+ i
;
821 rects
[i
].bottom
= rects
[i
].top
+ 1;
823 rects
[ellipse_height
/ 2].top
= top
+ ellipse_height
/ 2; /* extend to top of rectangle */
825 hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
);
827 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
828 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
829 if (!hrgn
) free_region( obj
);
834 /***********************************************************************
835 * CreateEllipticRgn (GDI32.@)
837 * Creates an elliptical region.
840 * left [I] Left coordinate of bounding rectangle.
841 * top [I] Top coordinate of bounding rectangle.
842 * right [I] Right coordinate of bounding rectangle.
843 * bottom [I] Bottom coordinate of bounding rectangle.
846 * Success: Handle to region.
850 * This is a special case of CreateRoundRectRgn() where the width of the
851 * ellipse at each corner is equal to the width the rectangle and
852 * the same for the height.
854 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
855 INT right
, INT bottom
)
857 return CreateRoundRectRgn( left
, top
, right
, bottom
,
858 right
-left
, bottom
-top
);
862 /***********************************************************************
863 * CreateEllipticRgnIndirect (GDI32.@)
865 * Creates an elliptical region.
868 * rect [I] Pointer to bounding rectangle of the ellipse.
871 * Success: Handle to region.
875 * This is a special case of CreateRoundRectRgn() where the width of the
876 * ellipse at each corner is equal to the width the rectangle and
877 * the same for the height.
879 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
881 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
882 rect
->bottom
, rect
->right
- rect
->left
,
883 rect
->bottom
- rect
->top
);
886 /***********************************************************************
887 * GetRegionData (GDI32.@)
889 * Retrieves the data that specifies the region.
892 * hrgn [I] Region to retrieve the region data from.
893 * count [I] The size of the buffer pointed to by rgndata in bytes.
894 * rgndata [I] The buffer to receive data about the region.
897 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
898 * the number of bytes copied to the output buffer.
902 * The format of the Buffer member of RGNDATA is determined by the iType
903 * member of the region data header.
904 * Currently this is always RDH_RECTANGLES, which specifies that the format
905 * is the array of RECT's that specify the region. The length of the array
906 * is specified by the nCount member of the region data header.
908 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
911 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
913 TRACE(" %p count = %d, rgndata = %p\n", hrgn
, count
, rgndata
);
917 size
= obj
->numRects
* sizeof(RECT
);
918 if (!rgndata
|| count
< FIELD_OFFSET(RGNDATA
, Buffer
[size
]))
920 GDI_ReleaseObj( hrgn
);
921 if (rgndata
) /* buffer is too small, signal it by return 0 */
923 /* user requested buffer size with NULL rgndata */
924 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
927 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
928 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
929 rgndata
->rdh
.nCount
= obj
->numRects
;
930 rgndata
->rdh
.nRgnSize
= size
;
931 rgndata
->rdh
.rcBound
.left
= obj
->extents
.left
;
932 rgndata
->rdh
.rcBound
.top
= obj
->extents
.top
;
933 rgndata
->rdh
.rcBound
.right
= obj
->extents
.right
;
934 rgndata
->rdh
.rcBound
.bottom
= obj
->extents
.bottom
;
936 memcpy( rgndata
->Buffer
, obj
->rects
, size
);
938 GDI_ReleaseObj( hrgn
);
939 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
943 static void translate( POINT
*pt
, UINT count
, const XFORM
*xform
)
949 pt
->x
= floor( x
* xform
->eM11
+ y
* xform
->eM21
+ xform
->eDx
+ 0.5 );
950 pt
->y
= floor( x
* xform
->eM12
+ y
* xform
->eM22
+ xform
->eDy
+ 0.5 );
956 /***********************************************************************
957 * ExtCreateRegion (GDI32.@)
959 * Creates a region as specified by the transformation data and region data.
962 * lpXform [I] World-space to logical-space transformation data.
963 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
964 * rgndata [I] Data that specifies the region.
967 * Success: Handle to region.
971 * See GetRegionData().
973 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
977 const RECT
*pCurRect
, *pEndRect
;
981 SetLastError( ERROR_INVALID_PARAMETER
);
985 if (rgndata
->rdh
.dwSize
< sizeof(RGNDATAHEADER
))
988 /* XP doesn't care about the type */
989 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
990 WARN("(Unsupported region data type: %u)\n", rgndata
->rdh
.iType
);
994 const RECT
*pCurRect
, *pEndRect
;
996 hrgn
= CreateRectRgn( 0, 0, 0, 0 );
998 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
999 for (pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
1001 static const INT count
= 4;
1005 pt
[0].x
= pCurRect
->left
;
1006 pt
[0].y
= pCurRect
->top
;
1007 pt
[1].x
= pCurRect
->right
;
1008 pt
[1].y
= pCurRect
->top
;
1009 pt
[2].x
= pCurRect
->right
;
1010 pt
[2].y
= pCurRect
->bottom
;
1011 pt
[3].x
= pCurRect
->left
;
1012 pt
[3].y
= pCurRect
->bottom
;
1014 translate( pt
, 4, lpXform
);
1015 poly_hrgn
= CreatePolyPolygonRgn( pt
, &count
, 1, WINDING
);
1016 CombineRgn( hrgn
, hrgn
, poly_hrgn
, RGN_OR
);
1017 DeleteObject( poly_hrgn
);
1022 if (!(obj
= alloc_region( rgndata
->rdh
.nCount
))) return 0;
1024 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
1025 for(pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
1027 if (pCurRect
->left
< pCurRect
->right
&& pCurRect
->top
< pCurRect
->bottom
)
1029 if (!REGION_UnionRectWithRegion( pCurRect
, obj
)) goto done
;
1032 hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
);
1035 if (!hrgn
) free_region( obj
);
1037 TRACE("%p %d %p returning %p\n", lpXform
, dwCount
, rgndata
, hrgn
);
1042 /***********************************************************************
1043 * PtInRegion (GDI32.@)
1045 * Tests whether the specified point is inside a region.
1048 * hrgn [I] Region to test.
1049 * x [I] X-coordinate of point to test.
1050 * y [I] Y-coordinate of point to test.
1053 * Non-zero if the point is inside the region or zero otherwise.
1055 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
1060 if ((obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
)))
1062 if (obj
->numRects
> 0 && is_in_rect( &obj
->extents
, x
, y
))
1063 region_find_pt( obj
, x
, y
, &ret
);
1064 GDI_ReleaseObj( hrgn
);
1070 /***********************************************************************
1071 * RectInRegion (GDI32.@)
1073 * Tests if a rectangle is at least partly inside the specified region.
1076 * hrgn [I] Region to test.
1077 * rect [I] Rectangle to test.
1080 * Non-zero if the rectangle is partially inside the region or
1083 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
1090 /* swap the coordinates to make right >= left and bottom >= top */
1091 /* (region building rectangles are normalized the same way) */
1095 if ((obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
)))
1097 if ((obj
->numRects
> 0) && overlapping(&obj
->extents
, &rc
))
1099 for (i
= region_find_pt( obj
, rc
.left
, rc
.top
, &ret
); !ret
&& i
< obj
->numRects
; i
++ )
1101 if (obj
->rects
[i
].bottom
<= rc
.top
)
1102 continue; /* not far enough down yet */
1104 if (obj
->rects
[i
].top
>= rc
.bottom
)
1105 break; /* too far down */
1107 if (obj
->rects
[i
].right
<= rc
.left
)
1108 continue; /* not far enough over yet */
1110 if (obj
->rects
[i
].left
>= rc
.right
)
1116 GDI_ReleaseObj(hrgn
);
1121 /***********************************************************************
1122 * EqualRgn (GDI32.@)
1124 * Tests whether one region is identical to another.
1127 * hrgn1 [I] The first region to compare.
1128 * hrgn2 [I] The second region to compare.
1131 * Non-zero if both regions are identical or zero otherwise.
1133 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
1135 WINEREGION
*obj1
, *obj2
;
1138 if ((obj1
= GDI_GetObjPtr( hrgn1
, OBJ_REGION
)))
1140 if ((obj2
= GDI_GetObjPtr( hrgn2
, OBJ_REGION
)))
1144 if ( obj1
->numRects
!= obj2
->numRects
) goto done
;
1145 if ( obj1
->numRects
== 0 )
1151 if (obj1
->extents
.left
!= obj2
->extents
.left
) goto done
;
1152 if (obj1
->extents
.right
!= obj2
->extents
.right
) goto done
;
1153 if (obj1
->extents
.top
!= obj2
->extents
.top
) goto done
;
1154 if (obj1
->extents
.bottom
!= obj2
->extents
.bottom
) goto done
;
1155 for( i
= 0; i
< obj1
->numRects
; i
++ )
1157 if (obj1
->rects
[i
].left
!= obj2
->rects
[i
].left
) goto done
;
1158 if (obj1
->rects
[i
].right
!= obj2
->rects
[i
].right
) goto done
;
1159 if (obj1
->rects
[i
].top
!= obj2
->rects
[i
].top
) goto done
;
1160 if (obj1
->rects
[i
].bottom
!= obj2
->rects
[i
].bottom
) goto done
;
1164 GDI_ReleaseObj(hrgn2
);
1166 GDI_ReleaseObj(hrgn1
);
1171 /***********************************************************************
1172 * REGION_UnionRectWithRegion
1173 * Adds a rectangle to a WINEREGION
1175 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1179 region
.rects
= ®ion
.extents
;
1180 region
.numRects
= 1;
1182 region
.extents
= *rect
;
1183 return REGION_UnionRegion(rgn
, rgn
, ®ion
);
1187 BOOL
add_rect_to_region( HRGN rgn
, const RECT
*rect
)
1189 WINEREGION
*obj
= GDI_GetObjPtr( rgn
, OBJ_REGION
);
1192 if (!obj
) return FALSE
;
1193 ret
= REGION_UnionRectWithRegion( rect
, obj
);
1194 GDI_ReleaseObj( rgn
);
1198 /***********************************************************************
1199 * REGION_CreateFrameRgn
1201 * Create a region that is a frame around another region.
1202 * Compute the intersection of the region moved in all 4 directions
1203 * ( +x, -x, +y, -y) and subtract from the original.
1204 * The result looks slightly better than in Windows :)
1206 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1210 WINEREGION
* destObj
= NULL
;
1211 WINEREGION
*srcObj
= GDI_GetObjPtr( hSrc
, OBJ_REGION
);
1213 tmprgn
.rects
= NULL
;
1214 if (!srcObj
) return FALSE
;
1215 if (srcObj
->numRects
!= 0)
1217 if (!(destObj
= GDI_GetObjPtr( hDest
, OBJ_REGION
))) goto done
;
1218 if (!init_region( &tmprgn
, srcObj
->numRects
)) goto done
;
1220 if (!REGION_OffsetRegion( destObj
, srcObj
, -x
, 0)) goto done
;
1221 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, x
, 0)) goto done
;
1222 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1223 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, -y
)) goto done
;
1224 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1225 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, y
)) goto done
;
1226 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1227 if (!REGION_SubtractRegion( destObj
, srcObj
, destObj
)) goto done
;
1231 destroy_region( &tmprgn
);
1232 if (destObj
) GDI_ReleaseObj ( hDest
);
1233 GDI_ReleaseObj( hSrc
);
1238 /***********************************************************************
1239 * CombineRgn (GDI32.@)
1241 * Combines two regions with the specified operation and stores the result
1242 * in the specified destination region.
1245 * hDest [I] The region that receives the combined result.
1246 * hSrc1 [I] The first source region.
1247 * hSrc2 [I] The second source region.
1248 * mode [I] The way in which the source regions will be combined. See notes.
1252 * NULLREGION - The new region is empty.
1253 * SIMPLEREGION - The new region can be represented by one rectangle.
1254 * COMPLEXREGION - The new region can only be represented by more than
1259 * The two source regions can be the same region.
1260 * The mode can be one of the following:
1261 *| RGN_AND - Intersection of the regions
1262 *| RGN_OR - Union of the regions
1263 *| RGN_XOR - Unions of the regions minus any intersection.
1264 *| RGN_DIFF - Difference (subtraction) of the regions.
1266 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1268 WINEREGION
*destObj
= GDI_GetObjPtr( hDest
, OBJ_REGION
);
1271 TRACE(" %p,%p -> %p mode=%x\n", hSrc1
, hSrc2
, hDest
, mode
);
1274 WINEREGION
*src1Obj
= GDI_GetObjPtr( hSrc1
, OBJ_REGION
);
1278 TRACE("dump src1Obj:\n");
1279 if(TRACE_ON(region
))
1280 REGION_DumpRegion(src1Obj
);
1281 if (mode
== RGN_COPY
)
1283 if (REGION_CopyRegion( destObj
, src1Obj
))
1284 result
= get_region_type( destObj
);
1288 WINEREGION
*src2Obj
= GDI_GetObjPtr( hSrc2
, OBJ_REGION
);
1292 TRACE("dump src2Obj:\n");
1293 if(TRACE_ON(region
))
1294 REGION_DumpRegion(src2Obj
);
1298 if (REGION_IntersectRegion( destObj
, src1Obj
, src2Obj
))
1299 result
= get_region_type( destObj
);
1302 if (REGION_UnionRegion( destObj
, src1Obj
, src2Obj
))
1303 result
= get_region_type( destObj
);
1306 if (REGION_XorRegion( destObj
, src1Obj
, src2Obj
))
1307 result
= get_region_type( destObj
);
1310 if (REGION_SubtractRegion( destObj
, src1Obj
, src2Obj
))
1311 result
= get_region_type( destObj
);
1314 GDI_ReleaseObj( hSrc2
);
1317 GDI_ReleaseObj( hSrc1
);
1319 TRACE("dump destObj:\n");
1320 if(TRACE_ON(region
))
1321 REGION_DumpRegion(destObj
);
1323 GDI_ReleaseObj( hDest
);
1328 /***********************************************************************
1330 * Re-calculate the extents of a region
1332 static void REGION_SetExtents (WINEREGION
*pReg
)
1334 RECT
*pRect
, *pRectEnd
, *pExtents
;
1336 if (pReg
->numRects
== 0)
1338 pReg
->extents
.left
= 0;
1339 pReg
->extents
.top
= 0;
1340 pReg
->extents
.right
= 0;
1341 pReg
->extents
.bottom
= 0;
1345 pExtents
= &pReg
->extents
;
1346 pRect
= pReg
->rects
;
1347 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1350 * Since pRect is the first rectangle in the region, it must have the
1351 * smallest top and since pRectEnd is the last rectangle in the region,
1352 * it must have the largest bottom, because of banding. Initialize left and
1353 * right from pRect and pRectEnd, resp., as good things to initialize them
1356 pExtents
->left
= pRect
->left
;
1357 pExtents
->top
= pRect
->top
;
1358 pExtents
->right
= pRectEnd
->right
;
1359 pExtents
->bottom
= pRectEnd
->bottom
;
1361 while (pRect
<= pRectEnd
)
1363 if (pRect
->left
< pExtents
->left
)
1364 pExtents
->left
= pRect
->left
;
1365 if (pRect
->right
> pExtents
->right
)
1366 pExtents
->right
= pRect
->right
;
1371 /***********************************************************************
1374 static BOOL
REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1376 if (dst
!= src
) /* don't want to copy to itself */
1378 if (dst
->size
< src
->numRects
&& !grow_region( dst
, src
->numRects
))
1381 dst
->numRects
= src
->numRects
;
1382 dst
->extents
.left
= src
->extents
.left
;
1383 dst
->extents
.top
= src
->extents
.top
;
1384 dst
->extents
.right
= src
->extents
.right
;
1385 dst
->extents
.bottom
= src
->extents
.bottom
;
1386 memcpy(dst
->rects
, src
->rects
, src
->numRects
* sizeof(RECT
));
1391 /***********************************************************************
1392 * REGION_MirrorRegion
1394 static BOOL
REGION_MirrorRegion( WINEREGION
*dst
, WINEREGION
*src
, int width
)
1403 if (!grow_region( dst
, src
->numRects
)) return FALSE
;
1405 dst
->numRects
= src
->numRects
;
1409 if (!init_region( &tmp
, src
->numRects
)) return FALSE
;
1411 tmp
.numRects
= src
->numRects
;
1414 extents
.left
= width
- src
->extents
.right
;
1415 extents
.right
= width
- src
->extents
.left
;
1416 extents
.top
= src
->extents
.top
;
1417 extents
.bottom
= src
->extents
.bottom
;
1419 for (start
= 0; start
< src
->numRects
; start
= end
)
1421 /* find the end of the current band */
1422 for (end
= start
+ 1; end
< src
->numRects
; end
++)
1423 if (src
->rects
[end
].top
!= src
->rects
[end
- 1].top
) break;
1425 for (i
= 0; i
< end
- start
; i
++)
1427 rects
[start
+ i
].left
= width
- src
->rects
[end
- i
- 1].right
;
1428 rects
[start
+ i
].right
= width
- src
->rects
[end
- i
- 1].left
;
1429 rects
[start
+ i
].top
= src
->rects
[end
- i
- 1].top
;
1430 rects
[start
+ i
].bottom
= src
->rects
[end
- i
- 1].bottom
;
1435 move_rects( dst
, &tmp
);
1437 dst
->extents
= extents
;
1441 /***********************************************************************
1444 INT
mirror_region( HRGN dst
, HRGN src
, INT width
)
1446 WINEREGION
*src_rgn
, *dst_rgn
;
1449 if (!(src_rgn
= GDI_GetObjPtr( src
, OBJ_REGION
))) return ERROR
;
1450 if ((dst_rgn
= GDI_GetObjPtr( dst
, OBJ_REGION
)))
1452 if (REGION_MirrorRegion( dst_rgn
, src_rgn
, width
)) ret
= get_region_type( dst_rgn
);
1453 GDI_ReleaseObj( dst_rgn
);
1455 GDI_ReleaseObj( src_rgn
);
1459 /***********************************************************************
1460 * MirrorRgn (GDI32.@)
1462 BOOL WINAPI
MirrorRgn( HWND hwnd
, HRGN hrgn
)
1464 static const WCHAR user32W
[] = {'u','s','e','r','3','2','.','d','l','l',0};
1465 static BOOL (WINAPI
*pGetWindowRect
)( HWND hwnd
, LPRECT rect
);
1468 /* yes, a HWND in gdi32, don't ask */
1469 if (!pGetWindowRect
)
1471 HMODULE user32
= GetModuleHandleW(user32W
);
1472 if (!user32
) return FALSE
;
1473 if (!(pGetWindowRect
= (void *)GetProcAddress( user32
, "GetWindowRect" ))) return FALSE
;
1475 pGetWindowRect( hwnd
, &rect
);
1476 return mirror_region( hrgn
, hrgn
, rect
.right
- rect
.left
) != ERROR
;
1480 /***********************************************************************
1483 * Attempt to merge the rects in the current band with those in the
1484 * previous one. Used only by REGION_RegionOp.
1487 * The new index for the previous band.
1490 * If coalescing takes place:
1491 * - rectangles in the previous band will have their bottom fields
1493 * - pReg->numRects will be decreased.
1496 static INT
REGION_Coalesce (
1497 WINEREGION
*pReg
, /* Region to coalesce */
1498 INT prevStart
, /* Index of start of previous band */
1499 INT curStart
/* Index of start of current band */
1501 RECT
*pPrevRect
; /* Current rect in previous band */
1502 RECT
*pCurRect
; /* Current rect in current band */
1503 RECT
*pRegEnd
; /* End of region */
1504 INT curNumRects
; /* Number of rectangles in current band */
1505 INT prevNumRects
; /* Number of rectangles in previous band */
1506 INT bandtop
; /* top coordinate for current band */
1508 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1510 pPrevRect
= &pReg
->rects
[prevStart
];
1511 prevNumRects
= curStart
- prevStart
;
1514 * Figure out how many rectangles are in the current band. Have to do
1515 * this because multiple bands could have been added in REGION_RegionOp
1516 * at the end when one region has been exhausted.
1518 pCurRect
= &pReg
->rects
[curStart
];
1519 bandtop
= pCurRect
->top
;
1520 for (curNumRects
= 0;
1521 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1527 if (pCurRect
!= pRegEnd
)
1530 * If more than one band was added, we have to find the start
1531 * of the last band added so the next coalescing job can start
1532 * at the right place... (given when multiple bands are added,
1533 * this may be pointless -- see above).
1536 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1540 curStart
= pRegEnd
- pReg
->rects
;
1541 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1544 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1545 pCurRect
-= curNumRects
;
1547 * The bands may only be coalesced if the bottom of the previous
1548 * matches the top scanline of the current.
1550 if (pPrevRect
->bottom
== pCurRect
->top
)
1553 * Make sure the bands have rects in the same places. This
1554 * assumes that rects have been added in such a way that they
1555 * cover the most area possible. I.e. two rects in a band must
1556 * have some horizontal space between them.
1560 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1561 (pPrevRect
->right
!= pCurRect
->right
))
1564 * The bands don't line up so they can't be coalesced.
1571 } while (prevNumRects
!= 0);
1573 pReg
->numRects
-= curNumRects
;
1574 pCurRect
-= curNumRects
;
1575 pPrevRect
-= curNumRects
;
1578 * The bands may be merged, so set the bottom of each rect
1579 * in the previous band to that of the corresponding rect in
1584 pPrevRect
->bottom
= pCurRect
->bottom
;
1588 } while (curNumRects
!= 0);
1591 * If only one band was added to the region, we have to backup
1592 * curStart to the start of the previous band.
1594 * If more than one band was added to the region, copy the
1595 * other bands down. The assumption here is that the other bands
1596 * came from the same region as the current one and no further
1597 * coalescing can be done on them since it's all been done
1598 * already... curStart is already in the right place.
1600 if (pCurRect
== pRegEnd
)
1602 curStart
= prevStart
;
1608 *pPrevRect
++ = *pCurRect
++;
1609 } while (pCurRect
!= pRegEnd
);
1617 /**********************************************************************
1620 * To keep regions from growing without bound, shrink the array of rectangles
1621 * to match the new number of rectangles in the region.
1623 * Only do this if the number of rectangles allocated is more than
1624 * twice the number of rectangles in the region.
1626 static void REGION_compact( WINEREGION
*reg
)
1628 if ((reg
->numRects
< reg
->size
/ 2) && (reg
->numRects
> 2))
1630 RECT
*new_rects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
, reg
->numRects
* sizeof(RECT
) );
1633 reg
->rects
= new_rects
;
1634 reg
->size
= reg
->numRects
;
1639 /***********************************************************************
1642 * Apply an operation to two regions. Called by REGION_Union,
1643 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1649 * The new region is overwritten.
1652 * The idea behind this function is to view the two regions as sets.
1653 * Together they cover a rectangle of area that this function divides
1654 * into horizontal bands where points are covered only by one region
1655 * or by both. For the first case, the nonOverlapFunc is called with
1656 * each the band and the band's upper and lower extents. For the
1657 * second, the overlapFunc is called to process the entire band. It
1658 * is responsible for clipping the rectangles in the band, though
1659 * this function provides the boundaries.
1660 * At the end of each band, the new region is coalesced, if possible,
1661 * to reduce the number of rectangles in the region.
1664 static BOOL
REGION_RegionOp(
1665 WINEREGION
*destReg
, /* Place to store result */
1666 WINEREGION
*reg1
, /* First region in operation */
1667 WINEREGION
*reg2
, /* 2nd region in operation */
1668 BOOL (*overlapFunc
)(WINEREGION
*, RECT
*, RECT
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for over-lapping bands */
1669 BOOL (*nonOverlap1Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for non-overlapping bands in region 1 */
1670 BOOL (*nonOverlap2Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
) /* Function to call for non-overlapping bands in region 2 */
1673 RECT
*r1
; /* Pointer into first region */
1674 RECT
*r2
; /* Pointer into 2d region */
1675 RECT
*r1End
; /* End of 1st region */
1676 RECT
*r2End
; /* End of 2d region */
1677 INT ybot
; /* Bottom of intersection */
1678 INT ytop
; /* Top of intersection */
1679 INT prevBand
; /* Index of start of
1680 * previous band in newReg */
1681 INT curBand
; /* Index of start of current
1683 RECT
*r1BandEnd
; /* End of current band in r1 */
1684 RECT
*r2BandEnd
; /* End of current band in r2 */
1685 INT top
; /* Top of non-overlapping band */
1686 INT bot
; /* Bottom of non-overlapping band */
1690 * set r1, r2, r1End and r2End appropriately, preserve the important
1691 * parts of the destination region until the end in case it's one of
1692 * the two source regions, then mark the "new" region empty, allocating
1693 * another array of rectangles for it to use.
1697 r1End
= r1
+ reg1
->numRects
;
1698 r2End
= r2
+ reg2
->numRects
;
1701 * Allocate a reasonable number of rectangles for the new region. The idea
1702 * is to allocate enough so the individual functions don't need to
1703 * reallocate and copy the array, which is time consuming, yet we don't
1704 * have to worry about using too much memory. I hope to be able to
1705 * nuke the Xrealloc() at the end of this function eventually.
1707 if (!init_region( &newReg
, max(reg1
->numRects
,reg2
->numRects
) * 2 )) return FALSE
;
1710 * Initialize ybot and ytop.
1711 * In the upcoming loop, ybot and ytop serve different functions depending
1712 * on whether the band being handled is an overlapping or non-overlapping
1714 * In the case of a non-overlapping band (only one of the regions
1715 * has points in the band), ybot is the bottom of the most recent
1716 * intersection and thus clips the top of the rectangles in that band.
1717 * ytop is the top of the next intersection between the two regions and
1718 * serves to clip the bottom of the rectangles in the current band.
1719 * For an overlapping band (where the two regions intersect), ytop clips
1720 * the top of the rectangles of both regions and ybot clips the bottoms.
1722 if (reg1
->extents
.top
< reg2
->extents
.top
)
1723 ybot
= reg1
->extents
.top
;
1725 ybot
= reg2
->extents
.top
;
1728 * prevBand serves to mark the start of the previous band so rectangles
1729 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1730 * In the beginning, there is no previous band, so prevBand == curBand
1731 * (curBand is set later on, of course, but the first band will always
1732 * start at index 0). prevBand and curBand must be indices because of
1733 * the possible expansion, and resultant moving, of the new region's
1734 * array of rectangles.
1740 curBand
= newReg
.numRects
;
1743 * This algorithm proceeds one source-band (as opposed to a
1744 * destination band, which is determined by where the two regions
1745 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1746 * rectangle after the last one in the current band for their
1747 * respective regions.
1750 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1756 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1762 * First handle the band that doesn't intersect, if any.
1764 * Note that attention is restricted to one band in the
1765 * non-intersecting region at once, so if a region has n
1766 * bands between the current position and the next place it overlaps
1767 * the other, this entire loop will be passed through n times.
1769 if (r1
->top
< r2
->top
)
1771 top
= max(r1
->top
,ybot
);
1772 bot
= min(r1
->bottom
,r2
->top
);
1774 if ((top
!= bot
) && (nonOverlap1Func
!= NULL
))
1776 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, top
, bot
)) return FALSE
;
1781 else if (r2
->top
< r1
->top
)
1783 top
= max(r2
->top
,ybot
);
1784 bot
= min(r2
->bottom
,r1
->top
);
1786 if ((top
!= bot
) && (nonOverlap2Func
!= NULL
))
1788 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, top
, bot
)) return FALSE
;
1799 * If any rectangles got added to the region, try and coalesce them
1800 * with rectangles from the previous band. Note we could just do
1801 * this test in miCoalesce, but some machines incur a not
1802 * inconsiderable cost for function calls, so...
1804 if (newReg
.numRects
!= curBand
)
1806 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1810 * Now see if we've hit an intersecting band. The two bands only
1811 * intersect if ybot > ytop
1813 ybot
= min(r1
->bottom
, r2
->bottom
);
1814 curBand
= newReg
.numRects
;
1817 if (!overlapFunc(&newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
)) return FALSE
;
1820 if (newReg
.numRects
!= curBand
)
1822 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1826 * If we've finished with a band (bottom == ybot) we skip forward
1827 * in the region to the next band.
1829 if (r1
->bottom
== ybot
)
1833 if (r2
->bottom
== ybot
)
1837 } while ((r1
!= r1End
) && (r2
!= r2End
));
1840 * Deal with whichever region still has rectangles left.
1842 curBand
= newReg
.numRects
;
1845 if (nonOverlap1Func
!= NULL
)
1850 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1854 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, max(r1
->top
,ybot
), r1
->bottom
))
1857 } while (r1
!= r1End
);
1860 else if ((r2
!= r2End
) && (nonOverlap2Func
!= NULL
))
1865 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1869 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, max(r2
->top
,ybot
), r2
->bottom
))
1872 } while (r2
!= r2End
);
1875 if (newReg
.numRects
!= curBand
)
1877 REGION_Coalesce (&newReg
, prevBand
, curBand
);
1880 REGION_compact( &newReg
);
1881 move_rects( destReg
, &newReg
);
1885 /***********************************************************************
1886 * Region Intersection
1887 ***********************************************************************/
1890 /***********************************************************************
1893 * Handle an overlapping band for REGION_Intersect.
1899 * Rectangles may be added to the region.
1902 static BOOL
REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1903 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1908 while ((r1
!= r1End
) && (r2
!= r2End
))
1910 left
= max(r1
->left
, r2
->left
);
1911 right
= min(r1
->right
, r2
->right
);
1914 * If there's any overlap between the two rectangles, add that
1915 * overlap to the new region.
1916 * There's no need to check for subsumption because the only way
1917 * such a need could arise is if some region has two rectangles
1918 * right next to each other. Since that should never happen...
1922 if (!add_rect( pReg
, left
, top
, right
, bottom
)) return FALSE
;
1926 * Need to advance the pointers. Shift the one that extends
1927 * to the right the least, since the other still has a chance to
1928 * overlap with that region's next rectangle, if you see what I mean.
1930 if (r1
->right
< r2
->right
)
1934 else if (r2
->right
< r1
->right
)
1947 /***********************************************************************
1948 * REGION_IntersectRegion
1950 static BOOL
REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1953 /* check for trivial reject */
1954 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1955 (!overlapping(®1
->extents
, ®2
->extents
)))
1956 newReg
->numRects
= 0;
1958 if (!REGION_RegionOp (newReg
, reg1
, reg2
, REGION_IntersectO
, NULL
, NULL
)) return FALSE
;
1961 * Can't alter newReg's extents before we call miRegionOp because
1962 * it might be one of the source regions and miRegionOp depends
1963 * on the extents of those regions being the same. Besides, this
1964 * way there's no checking against rectangles that will be nuked
1965 * due to coalescing, so we have to examine fewer rectangles.
1967 REGION_SetExtents(newReg
);
1971 /***********************************************************************
1973 ***********************************************************************/
1975 /***********************************************************************
1978 * Handle a non-overlapping band for the union operation. Just
1979 * Adds the rectangles into the region. Doesn't have to check for
1980 * subsumption or anything.
1986 * pReg->numRects is incremented and the final rectangles overwritten
1987 * with the rectangles we're passed.
1990 static BOOL
REGION_UnionNonO(WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
1994 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
2000 /***********************************************************************
2003 * Handle an overlapping band for the union operation. Picks the
2004 * left-most rectangle each time and merges it into the region.
2010 * Rectangles are overwritten in pReg->rects and pReg->numRects will
2014 static BOOL
REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2015 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2017 #define MERGERECT(r) \
2018 if ((pReg->numRects != 0) && \
2019 (pReg->rects[pReg->numRects-1].top == top) && \
2020 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
2021 (pReg->rects[pReg->numRects-1].right >= r->left)) \
2023 if (pReg->rects[pReg->numRects-1].right < r->right) \
2024 pReg->rects[pReg->numRects-1].right = r->right; \
2028 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
2032 while ((r1
!= r1End
) && (r2
!= r2End
))
2034 if (r1
->left
< r2
->left
)
2049 } while (r1
!= r1End
);
2051 else while (r2
!= r2End
)
2059 /***********************************************************************
2060 * REGION_UnionRegion
2062 static BOOL
REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
, WINEREGION
*reg2
)
2066 /* checks all the simple cases */
2069 * Region 1 and 2 are the same or region 1 is empty
2071 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
2074 ret
= REGION_CopyRegion(newReg
, reg2
);
2079 * if nothing to union (region 2 empty)
2081 if (!(reg2
->numRects
))
2084 ret
= REGION_CopyRegion(newReg
, reg1
);
2089 * Region 1 completely subsumes region 2
2091 if ((reg1
->numRects
== 1) &&
2092 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
2093 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
2094 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
2095 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
2098 ret
= REGION_CopyRegion(newReg
, reg1
);
2103 * Region 2 completely subsumes region 1
2105 if ((reg2
->numRects
== 1) &&
2106 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
2107 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
2108 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
2109 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
2112 ret
= REGION_CopyRegion(newReg
, reg2
);
2116 if ((ret
= REGION_RegionOp (newReg
, reg1
, reg2
, REGION_UnionO
, REGION_UnionNonO
, REGION_UnionNonO
)))
2118 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
2119 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
2120 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
2121 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
2126 /***********************************************************************
2127 * Region Subtraction
2128 ***********************************************************************/
2130 /***********************************************************************
2131 * REGION_SubtractNonO1
2133 * Deal with non-overlapping band for subtraction. Any parts from
2134 * region 2 we discard. Anything from region 1 we add to the region.
2140 * pReg may be affected.
2143 static BOOL
REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
2147 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
2154 /***********************************************************************
2157 * Overlapping band subtraction. x1 is the left-most point not yet
2164 * pReg may have rectangles added to it.
2167 static BOOL
REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2168 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2170 INT left
= r1
->left
;
2172 while ((r1
!= r1End
) && (r2
!= r2End
))
2174 if (r2
->right
<= left
)
2177 * Subtrahend missed the boat: go to next subtrahend.
2181 else if (r2
->left
<= left
)
2184 * Subtrahend precedes minuend: nuke left edge of minuend.
2187 if (left
>= r1
->right
)
2190 * Minuend completely covered: advance to next minuend and
2191 * reset left fence to edge of new minuend.
2200 * Subtrahend now used up since it doesn't extend beyond
2206 else if (r2
->left
< r1
->right
)
2209 * Left part of subtrahend covers part of minuend: add uncovered
2210 * part of minuend to region and skip to next subtrahend.
2212 if (!add_rect( pReg
, left
, top
, r2
->left
, bottom
)) return FALSE
;
2214 if (left
>= r1
->right
)
2217 * Minuend used up: advance to new...
2226 * Subtrahend used up
2234 * Minuend used up: add any remaining piece before advancing.
2236 if (r1
->right
> left
)
2238 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2247 * Add remaining minuend rectangles to region.
2251 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2261 /***********************************************************************
2262 * REGION_SubtractRegion
2264 * Subtract regS from regM and leave the result in regD.
2265 * S stands for subtrahend, M for minuend and D for difference.
2271 * regD is overwritten.
2274 static BOOL
REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
, WINEREGION
*regS
)
2276 /* check for trivial reject */
2277 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2278 (!overlapping(®M
->extents
, ®S
->extents
)) )
2279 return REGION_CopyRegion(regD
, regM
);
2281 if (!REGION_RegionOp (regD
, regM
, regS
, REGION_SubtractO
, REGION_SubtractNonO1
, NULL
))
2285 * Can't alter newReg's extents before we call miRegionOp because
2286 * it might be one of the source regions and miRegionOp depends
2287 * on the extents of those regions being the unaltered. Besides, this
2288 * way there's no checking against rectangles that will be nuked
2289 * due to coalescing, so we have to examine fewer rectangles.
2291 REGION_SetExtents (regD
);
2295 /***********************************************************************
2298 static BOOL
REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
, WINEREGION
*srb
)
2300 WINEREGION tra
, trb
;
2303 if (!init_region( &tra
, sra
->numRects
+ 1 )) return FALSE
;
2304 if ((ret
= init_region( &trb
, srb
->numRects
+ 1 )))
2306 ret
= REGION_SubtractRegion(&tra
,sra
,srb
) &&
2307 REGION_SubtractRegion(&trb
,srb
,sra
) &&
2308 REGION_UnionRegion(dr
,&tra
,&trb
);
2309 destroy_region(&trb
);
2311 destroy_region(&tra
);
2315 /**************************************************************************
2319 *************************************************************************/
2321 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2322 #define SMALL_COORDINATE 0x80000000
2324 /***********************************************************************
2325 * REGION_InsertEdgeInET
2327 * Insert the given edge into the edge table.
2328 * First we must find the correct bucket in the
2329 * Edge table, then find the right slot in the
2330 * bucket. Finally, we can insert it.
2333 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2334 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2338 ScanLineList
*pSLL
, *pPrevSLL
;
2339 ScanLineListBlock
*tmpSLLBlock
;
2342 * find the right bucket to put the edge into
2344 pPrevSLL
= &ET
->scanlines
;
2345 pSLL
= pPrevSLL
->next
;
2346 while (pSLL
&& (pSLL
->scanline
< scanline
))
2353 * reassign pSLL (pointer to ScanLineList) if necessary
2355 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2357 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2359 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2362 WARN("Can't alloc SLLB\n");
2365 (*SLLBlock
)->next
= tmpSLLBlock
;
2366 tmpSLLBlock
->next
= NULL
;
2367 *SLLBlock
= tmpSLLBlock
;
2370 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2372 pSLL
->next
= pPrevSLL
->next
;
2373 list_init( &pSLL
->edgelist
);
2374 pPrevSLL
->next
= pSLL
;
2376 pSLL
->scanline
= scanline
;
2379 * now insert the edge in the right bucket
2381 LIST_FOR_EACH( ptr
, &pSLL
->edgelist
)
2383 struct edge_table_entry
*entry
= LIST_ENTRY( ptr
, struct edge_table_entry
, entry
);
2384 if (entry
->bres
.minor_axis
>= ETE
->bres
.minor_axis
) break;
2386 list_add_before( ptr
, &ETE
->entry
);
2389 /***********************************************************************
2390 * REGION_CreateEdgeTable
2392 * This routine creates the edge table for
2393 * scan converting polygons.
2394 * The Edge Table (ET) looks like:
2398 * | ymax | ScanLineLists
2399 * |scanline|-->------------>-------------->...
2400 * -------- |scanline| |scanline|
2401 * |edgelist| |edgelist|
2402 * --------- ---------
2406 * list of ETEs list of ETEs
2408 * where ETE is an EdgeTableEntry data structure,
2409 * and there is one ScanLineList per scanline at
2410 * which an edge is initially entered.
2413 static void REGION_CreateEdgeTable(const INT
*Count
, INT nbpolygons
,
2414 const POINT
*pts
, EdgeTable
*ET
,
2415 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2417 const POINT
*top
, *bottom
;
2418 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2424 * initialize the Edge Table.
2426 ET
->scanlines
.next
= NULL
;
2427 ET
->ymax
= SMALL_COORDINATE
;
2428 ET
->ymin
= LARGE_COORDINATE
;
2429 pSLLBlock
->next
= NULL
;
2432 for(poly
= 0; poly
< nbpolygons
; poly
++)
2434 count
= Count
[poly
];
2442 * for each vertex in the array of points.
2443 * In this loop we are dealing with two vertices at
2444 * a time -- these make up one edge of the polygon.
2451 * find out which point is above and which is below.
2453 if (PrevPt
->y
> CurrPt
->y
)
2455 bottom
= PrevPt
, top
= CurrPt
;
2456 pETEs
->ClockWise
= 0;
2460 bottom
= CurrPt
, top
= PrevPt
;
2461 pETEs
->ClockWise
= 1;
2465 * don't add horizontal edges to the Edge table.
2467 if (bottom
->y
!= top
->y
)
2469 pETEs
->ymax
= bottom
->y
-1;
2470 /* -1 so we don't get last scanline */
2473 * initialize integer edge algorithm
2475 dy
= bottom
->y
- top
->y
;
2476 bres_init_polygon(dy
, top
->x
, bottom
->x
, &pETEs
->bres
);
2478 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2481 if (PrevPt
->y
> ET
->ymax
)
2482 ET
->ymax
= PrevPt
->y
;
2483 if (PrevPt
->y
< ET
->ymin
)
2484 ET
->ymin
= PrevPt
->y
;
2493 /***********************************************************************
2496 * This routine moves EdgeTableEntries from the
2497 * EdgeTable into the Active Edge Table,
2498 * leaving them sorted by smaller x coordinate.
2501 static void REGION_loadAET( struct list
*AET
, struct list
*ETEs
)
2503 struct edge_table_entry
*ptr
, *next
, *entry
;
2504 struct list
*active
;
2506 LIST_FOR_EACH_ENTRY_SAFE( ptr
, next
, ETEs
, struct edge_table_entry
, entry
)
2508 LIST_FOR_EACH( active
, AET
)
2510 entry
= LIST_ENTRY( active
, struct edge_table_entry
, entry
);
2511 if (entry
->bres
.minor_axis
>= ptr
->bres
.minor_axis
) break;
2513 list_remove( &ptr
->entry
);
2514 list_add_before( active
, &ptr
->entry
);
2518 /***********************************************************************
2519 * REGION_computeWAET
2521 * This routine links the AET by the
2522 * nextWETE (winding EdgeTableEntry) link for
2523 * use by the winding number rule. The final
2524 * Active Edge Table (AET) might look something
2528 * ---------- --------- ---------
2529 * |ymax | |ymax | |ymax |
2530 * | ... | |... | |... |
2531 * |next |->|next |->|next |->...
2532 * |nextWETE| |nextWETE| |nextWETE|
2533 * --------- --------- ^--------
2535 * V-------------------> V---> ...
2538 static void REGION_computeWAET( struct list
*AET
, struct list
*WETE
)
2540 struct edge_table_entry
*active
;
2545 LIST_FOR_EACH_ENTRY( active
, AET
, struct edge_table_entry
, entry
)
2547 if (active
->ClockWise
)
2552 if ((!inside
&& !isInside
) || (inside
&& isInside
))
2554 list_add_tail( WETE
, &active
->winding_entry
);
2560 /***********************************************************************
2561 * REGION_InsertionSort
2563 * Just a simple insertion sort to sort the Active Edge Table.
2566 static BOOL
REGION_InsertionSort( struct list
*AET
)
2568 struct edge_table_entry
*active
, *next
, *insert
;
2569 BOOL changed
= FALSE
;
2571 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, AET
, struct edge_table_entry
, entry
)
2573 LIST_FOR_EACH_ENTRY( insert
, AET
, struct edge_table_entry
, entry
)
2575 if (insert
== active
) break;
2576 if (insert
->bres
.minor_axis
> active
->bres
.minor_axis
) break;
2578 if (insert
== active
) continue;
2579 list_remove( &active
->entry
);
2580 list_add_before( &insert
->entry
, &active
->entry
);
2586 /***********************************************************************
2587 * REGION_FreeStorage
2591 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2593 ScanLineListBlock
*tmpSLLBlock
;
2597 tmpSLLBlock
= pSLLBlock
->next
;
2598 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2599 pSLLBlock
= tmpSLLBlock
;
2604 /***********************************************************************
2605 * REGION_PtsToRegion
2607 * Create an array of rectangles from a list of points.
2609 static WINEREGION
*REGION_PtsToRegion( struct point_block
*FirstPtBlock
)
2612 struct point_block
*pb
;
2613 int i
, size
, cur_band
= 0, prev_band
= 0;
2617 for (pb
= FirstPtBlock
, size
= 0; pb
; pb
= pb
->next
) size
+= pb
->count
;
2618 if (!(reg
= alloc_region( size
))) return NULL
;
2620 extents
= ®
->extents
;
2621 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2623 for (pb
= FirstPtBlock
; pb
; pb
= pb
->next
)
2625 /* the loop uses 2 points per iteration */
2627 for (pts
= pb
->pts
; i
--; pts
+= 2) {
2628 if (pts
->x
== pts
[1].x
)
2631 if (reg
->numRects
&& pts
[0].y
!= reg
->rects
[cur_band
].top
)
2633 prev_band
= REGION_Coalesce( reg
, prev_band
, cur_band
);
2634 cur_band
= reg
->numRects
;
2637 add_rect( reg
, pts
[0].x
, pts
[0].y
, pts
[1].x
, pts
[1].y
+ 1 );
2638 if (pts
[0].x
< extents
->left
)
2639 extents
->left
= pts
[0].x
;
2640 if (pts
[1].x
> extents
->right
)
2641 extents
->right
= pts
[1].x
;
2645 if (reg
->numRects
) {
2646 REGION_Coalesce( reg
, prev_band
, cur_band
);
2647 extents
->top
= reg
->rects
[0].top
;
2648 extents
->bottom
= reg
->rects
[reg
->numRects
-1].bottom
;
2653 extents
->bottom
= 0;
2655 REGION_compact( reg
);
2660 /***********************************************************************
2661 * CreatePolyPolygonRgn (GDI32.@)
2663 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2664 INT nbpolygons
, INT mode
)
2668 INT y
; /* current scanline */
2669 struct list WETE
, *pWETE
; /* Winding Edge Table */
2670 ScanLineList
*pSLL
; /* current scanLineList */
2671 EdgeTable ET
; /* header node for ET */
2672 struct list AET
; /* header for AET */
2673 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2674 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2675 BOOL fixWAET
= FALSE
;
2676 struct point_block FirstPtBlock
, *block
; /* PtBlock buffers */
2677 struct edge_table_entry
*active
, *next
;
2680 TRACE("%p, count %d, polygons %d, mode %d\n", Pts
, *Count
, nbpolygons
, mode
);
2682 /* special case a rectangle */
2684 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2685 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2686 (((Pts
[0].y
== Pts
[1].y
) &&
2687 (Pts
[1].x
== Pts
[2].x
) &&
2688 (Pts
[2].y
== Pts
[3].y
) &&
2689 (Pts
[3].x
== Pts
[0].x
)) ||
2690 ((Pts
[0].x
== Pts
[1].x
) &&
2691 (Pts
[1].y
== Pts
[2].y
) &&
2692 (Pts
[2].x
== Pts
[3].x
) &&
2693 (Pts
[3].y
== Pts
[0].y
))))
2694 return CreateRectRgn( min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2695 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2697 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2698 total
+= Count
[poly
];
2699 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2702 REGION_CreateEdgeTable(Count
, nbpolygons
, Pts
, &ET
, pETEs
, &SLLBlock
);
2704 pSLL
= ET
.scanlines
.next
;
2705 block
= &FirstPtBlock
;
2706 FirstPtBlock
.count
= 0;
2707 FirstPtBlock
.next
= NULL
;
2709 if (mode
!= WINDING
) {
2713 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2715 * Add a new edge to the active edge table when we
2716 * get to the next edge.
2718 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2719 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2723 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, &AET
, struct edge_table_entry
, entry
)
2725 block
= add_point( block
, active
->bres
.minor_axis
, y
);
2726 if (!block
) goto done
;
2728 if (active
->ymax
== y
) /* leaving this edge */
2729 list_remove( &active
->entry
);
2731 bres_incr_polygon( &active
->bres
);
2733 REGION_InsertionSort(&AET
);
2740 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2742 * Add a new edge to the active edge table when we
2743 * get to the next edge.
2745 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2746 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2747 REGION_computeWAET( &AET
, &WETE
);
2750 pWETE
= list_head( &WETE
);
2753 * for each active edge
2755 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, &AET
, struct edge_table_entry
, entry
)
2758 * add to the buffer only those edges that
2759 * are in the Winding active edge table.
2761 if (pWETE
== &active
->winding_entry
) {
2762 block
= add_point( block
, active
->bres
.minor_axis
, y
);
2763 if (!block
) goto done
;
2764 pWETE
= list_next( &WETE
, pWETE
);
2766 if (active
->ymax
== y
) /* leaving this edge */
2768 list_remove( &active
->entry
);
2772 bres_incr_polygon( &active
->bres
);
2776 * recompute the winding active edge table if
2777 * we just resorted or have exited an edge.
2779 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2780 REGION_computeWAET( &AET
, &WETE
);
2786 if (!(obj
= REGION_PtsToRegion( &FirstPtBlock
))) goto done
;
2787 if (!(hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
)))
2791 REGION_FreeStorage(SLLBlock
.next
);
2792 free_point_blocks( FirstPtBlock
.next
);
2793 HeapFree( GetProcessHeap(), 0, pETEs
);
2798 /***********************************************************************
2799 * CreatePolygonRgn (GDI32.@)
2801 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2804 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);