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...
102 #include "ntgdi_private.h"
103 #include "ntuser_private.h"
104 #include "wine/debug.h"
106 WINE_DEFAULT_DEBUG_CHANNEL(region
);
109 static BOOL
REGION_DeleteObject( HGDIOBJ handle
);
111 static const struct gdi_obj_funcs region_funcs
=
113 NULL
, /* pGetObjectW */
114 NULL
, /* pUnrealizeObject */
115 REGION_DeleteObject
/* pDeleteObject */
118 /* Check if two RECTs overlap. */
119 static inline BOOL
overlapping( const RECT
*r1
, const RECT
*r2
)
121 return (r1
->right
> r2
->left
&& r1
->left
< r2
->right
&&
122 r1
->bottom
> r2
->top
&& r1
->top
< r2
->bottom
);
125 static BOOL
grow_region( WINEREGION
*rgn
, int size
)
129 if (size
<= rgn
->size
) return TRUE
;
131 if (rgn
->rects
== rgn
->rects_buf
)
133 new_rects
= malloc( size
* sizeof(RECT
) );
134 if (!new_rects
) return FALSE
;
135 memcpy( new_rects
, rgn
->rects
, rgn
->numRects
* sizeof(RECT
) );
139 new_rects
= realloc( rgn
->rects
, size
* sizeof(RECT
) );
140 if (!new_rects
) return FALSE
;
142 rgn
->rects
= new_rects
;
147 static BOOL
add_rect( WINEREGION
*reg
, INT left
, INT top
, INT right
, INT bottom
)
150 if (reg
->numRects
>= reg
->size
&& !grow_region( reg
, 2 * reg
->size
))
153 rect
= reg
->rects
+ reg
->numRects
++;
157 rect
->bottom
= bottom
;
161 static inline void empty_region( WINEREGION
*reg
)
164 reg
->extents
.left
= reg
->extents
.top
= reg
->extents
.right
= reg
->extents
.bottom
= 0;
167 static inline BOOL
is_in_rect( const RECT
*rect
, int x
, int y
)
169 return (rect
->right
> x
&& rect
->left
<= x
&& rect
->bottom
> y
&& rect
->top
<= y
);
174 * This file contains a few macros to help track
175 * the edge of a filled object. The object is assumed
176 * to be filled in scanline order, and thus the
177 * algorithm used is an extension of Bresenham's line
178 * drawing algorithm which assumes that y is always the
180 * Since these pieces of code are the same for any filled shape,
181 * it is more convenient to gather the library in one
182 * place, but since these pieces of code are also in
183 * the inner loops of output primitives, procedure call
184 * overhead is out of the question.
185 * See the author for a derivation if needed.
190 * This structure contains all of the information needed
191 * to run the bresenham algorithm.
192 * The variables may be hardcoded into the declarations
193 * instead of using this structure to make use of
194 * register declarations.
198 INT minor_axis
; /* minor axis */
199 INT d
; /* decision variable */
200 INT m
, m1
; /* slope and slope+1 */
201 INT incr1
, incr2
; /* error increments */
206 * In scan converting polygons, we want to choose those pixels
207 * which are inside the polygon. Thus, we add .5 to the starting
208 * x coordinate for both left and right edges. Now we choose the
209 * first pixel which is inside the pgon for the left edge and the
210 * first pixel which is outside the pgon for the right edge.
211 * Draw the left pixel, but not the right.
213 * How to add .5 to the starting x coordinate:
214 * If the edge is moving to the right, then subtract dy from the
215 * error term from the general form of the algorithm.
216 * If the edge is moving to the left, then add dy to the error term.
218 * The reason for the difference between edges moving to the left
219 * and edges moving to the right is simple: If an edge is moving
220 * to the right, then we want the algorithm to flip immediately.
221 * If it is moving to the left, then we don't want it to flip until
222 * we traverse an entire pixel.
224 static inline void bres_init_polygon( int dy
, int x1
, int x2
, struct bres_info
*bres
)
229 * if the edge is horizontal, then it is ignored
230 * and assumed not to be processed. Otherwise, do this stuff.
234 bres
->minor_axis
= x1
;
239 bres
->m1
= bres
->m
- 1;
240 bres
->incr1
= -2 * dx
+ 2 * dy
* bres
->m1
;
241 bres
->incr2
= -2 * dx
+ 2 * dy
* bres
->m
;
242 bres
->d
= 2 * bres
->m
* dy
- 2 * dx
- 2 * dy
;
247 bres
->m1
= bres
->m
+ 1;
248 bres
->incr1
= 2 * dx
- 2 * dy
* bres
->m1
;
249 bres
->incr2
= 2 * dx
- 2 * dy
* bres
->m
;
250 bres
->d
= -2 * bres
->m
* dy
+ 2 * dx
;
254 static inline void bres_incr_polygon( struct bres_info
*bres
)
258 bres
->minor_axis
+= bres
->m1
;
259 bres
->d
+= bres
->incr1
;
262 bres
->minor_axis
+= bres
->m
;
263 bres
->d
+= bres
->incr2
;
267 bres
->minor_axis
+= bres
->m1
;
268 bres
->d
+= bres
->incr1
;
271 bres
->minor_axis
+= bres
->m
;
272 bres
->d
+= bres
->incr2
;
279 * These are the data structures needed to scan
280 * convert regions. Two different scan conversion
281 * methods are available -- the even-odd method, and
282 * the winding number method.
283 * The even-odd rule states that a point is inside
284 * the polygon if a ray drawn from that point in any
285 * direction will pass through an odd number of
287 * By the winding number rule, a point is decided
288 * to be inside the polygon if a ray drawn from that
289 * point in any direction passes through a different
290 * number of clockwise and counter-clockwise path
293 * These data structures are adapted somewhat from
294 * the algorithm in (Foley/Van Dam) for scan converting
296 * The basic algorithm is to start at the top (smallest y)
297 * of the polygon, stepping down to the bottom of
298 * the polygon by incrementing the y coordinate. We
299 * keep a list of edges which the current scanline crosses,
300 * sorted by x. This list is called the Active Edge Table (AET)
301 * As we change the y-coordinate, we update each entry in
302 * in the active edge table to reflect the edges new xcoord.
303 * This list must be sorted at each scanline in case
304 * two edges intersect.
305 * We also keep a data structure known as the Edge Table (ET),
306 * which keeps track of all the edges which the current
307 * scanline has not yet reached. The ET is basically a
308 * list of ScanLineList structures containing a list of
309 * edges which are entered at a given scanline. There is one
310 * ScanLineList per scanline at which an edge is entered.
311 * When we enter a new edge, we move it from the ET to the AET.
313 * From the AET, we can implement the even-odd rule as in
315 * The winding number rule is a little trickier. We also
316 * keep the EdgeTableEntries in the AET linked by the
317 * nextWETE (winding EdgeTableEntry) link. This allows
318 * the edges to be linked just as before for updating
319 * purposes, but only uses the edges linked by the nextWETE
320 * link as edges representing spans of the polygon to
321 * drawn (as with the even-odd rule).
324 typedef struct edge_table_entry
{
326 struct list winding_entry
;
327 INT ymax
; /* ycoord at which we exit this edge. */
328 struct bres_info bres
; /* Bresenham info to run the edge */
329 int ClockWise
; /* flag for winding number rule */
333 typedef struct _ScanLineList
{
334 struct list edgelist
;
335 INT scanline
; /* the scanline represented */
336 struct _ScanLineList
*next
; /* next in the list */
341 INT ymax
; /* ymax for the polygon */
342 INT ymin
; /* ymin for the polygon */
343 ScanLineList scanlines
; /* header node */
348 * Here is a struct to help with storage allocation
349 * so we can allocate a big chunk at a time, and then take
350 * pieces from this heap when we need to.
352 #define SLLSPERBLOCK 25
354 typedef struct _ScanLineListBlock
{
355 ScanLineList SLLs
[SLLSPERBLOCK
];
356 struct _ScanLineListBlock
*next
;
360 /* Note the parameter order is different from the X11 equivalents */
362 static BOOL
REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
363 static BOOL
REGION_OffsetRegion(WINEREGION
*d
, WINEREGION
*s
, INT x
, INT y
);
364 static BOOL
REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
365 static BOOL
REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
366 static BOOL
REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
367 static BOOL
REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
368 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
370 /***********************************************************************
373 static inline INT
get_region_type( const WINEREGION
*obj
)
375 switch(obj
->numRects
)
377 case 0: return NULLREGION
;
378 case 1: return SIMPLEREGION
;
379 default: return COMPLEXREGION
;
384 /***********************************************************************
386 * Outputs the contents of a WINEREGION
388 static void REGION_DumpRegion(WINEREGION
*pReg
)
390 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
392 TRACE("Region %p: %s %d rects\n", pReg
, wine_dbgstr_rect(&pReg
->extents
), pReg
->numRects
);
393 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
394 TRACE("\t%s\n", wine_dbgstr_rect(pRect
));
399 /***********************************************************************
402 * Initialize a new empty region.
404 static BOOL
init_region( WINEREGION
*pReg
, INT n
)
406 n
= max( n
, RGN_DEFAULT_RECTS
);
408 if (n
> RGN_DEFAULT_RECTS
)
410 if (n
> INT_MAX
/ sizeof(RECT
)) return FALSE
;
411 if (!(pReg
->rects
= malloc( n
* sizeof( RECT
) )))
415 pReg
->rects
= pReg
->rects_buf
;
422 /***********************************************************************
425 static void destroy_region( WINEREGION
*pReg
)
427 if (pReg
->rects
!= pReg
->rects_buf
)
431 /***********************************************************************
434 static void free_region( WINEREGION
*rgn
)
436 destroy_region( rgn
);
440 /***********************************************************************
443 static WINEREGION
*alloc_region( INT n
)
445 WINEREGION
*rgn
= malloc( sizeof(*rgn
) );
447 if (rgn
&& !init_region( rgn
, n
))
455 /************************************************************
458 * Move rectangles from src to dst leaving src with no rectangles.
460 static inline void move_rects( WINEREGION
*dst
, WINEREGION
*src
)
462 destroy_region( dst
);
463 if (src
->rects
== src
->rects_buf
)
465 dst
->rects
= dst
->rects_buf
;
466 memcpy( dst
->rects
, src
->rects
, src
->numRects
* sizeof(RECT
) );
469 dst
->rects
= src
->rects
;
470 dst
->size
= src
->size
;
471 dst
->numRects
= src
->numRects
;
472 init_region( src
, 0 );
475 /***********************************************************************
476 * REGION_DeleteObject
478 static BOOL
REGION_DeleteObject( HGDIOBJ handle
)
480 WINEREGION
*rgn
= free_gdi_handle( handle
);
482 if (!rgn
) return FALSE
;
488 /***********************************************************************
489 * REGION_OffsetRegion
490 * Offset a WINEREGION by x,y
492 static BOOL
REGION_OffsetRegion( WINEREGION
*rgn
, WINEREGION
*srcrgn
, INT x
, INT y
)
496 if (!REGION_CopyRegion( rgn
, srcrgn
)) return FALSE
;
499 int nbox
= rgn
->numRects
;
500 RECT
*pbox
= rgn
->rects
;
510 rgn
->extents
.left
+= x
;
511 rgn
->extents
.right
+= x
;
512 rgn
->extents
.top
+= y
;
513 rgn
->extents
.bottom
+= y
;
519 /***********************************************************************
520 * NtGdiOffsetRgn (win32u.@)
522 * Moves a region by the specified X- and Y-axis offsets.
525 * hrgn [I] Region to offset.
526 * x [I] Offset right if positive or left if negative.
527 * y [I] Offset down if positive or up if negative.
531 * NULLREGION - The new region is empty.
532 * SIMPLEREGION - The new region can be represented by one rectangle.
533 * COMPLEXREGION - The new region can only be represented by more than
537 INT WINAPI
NtGdiOffsetRgn( HRGN hrgn
, INT x
, INT y
)
539 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, NTGDI_OBJ_REGION
);
542 TRACE("%p %d,%d\n", hrgn
, x
, y
);
547 REGION_OffsetRegion( obj
, obj
, x
, y
);
549 ret
= get_region_type( obj
);
550 GDI_ReleaseObj( hrgn
);
555 /***********************************************************************
556 * NtGdiGetRgnBox (win32u.@)
558 * Retrieves the bounding rectangle of the region. The bounding rectangle
559 * is the smallest rectangle that contains the entire region.
562 * hrgn [I] Region to retrieve bounding rectangle from.
563 * rect [O] Rectangle that will receive the coordinates of the bounding
567 * NULLREGION - The new region is empty.
568 * SIMPLEREGION - The new region can be represented by one rectangle.
569 * COMPLEXREGION - The new region can only be represented by more than
572 INT WINAPI
NtGdiGetRgnBox( HRGN hrgn
, RECT
*rect
)
574 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, NTGDI_OBJ_REGION
);
578 rect
->left
= obj
->extents
.left
;
579 rect
->top
= obj
->extents
.top
;
580 rect
->right
= obj
->extents
.right
;
581 rect
->bottom
= obj
->extents
.bottom
;
582 TRACE("%p %s\n", hrgn
, wine_dbgstr_rect(rect
));
583 ret
= get_region_type( obj
);
584 GDI_ReleaseObj(hrgn
);
591 /***********************************************************************
592 * NtGdiCreateRectRgn (win32u.@)
594 * Creates a simple rectangular region.
597 * left [I] Left coordinate of rectangle.
598 * top [I] Top coordinate of rectangle.
599 * right [I] Right coordinate of rectangle.
600 * bottom [I] Bottom coordinate of rectangle.
603 * Success: Handle to region.
606 HRGN WINAPI
NtGdiCreateRectRgn( INT left
, INT top
, INT right
, INT bottom
)
611 if (!(obj
= alloc_region( RGN_DEFAULT_RECTS
))) return 0;
613 if (!(hrgn
= alloc_gdi_handle( &obj
->obj
, NTGDI_OBJ_REGION
, ®ion_funcs
)))
618 TRACE( "%d,%d-%d,%d returning %p\n", left
, top
, right
, bottom
, hrgn
);
619 NtGdiSetRectRgn( hrgn
, left
, top
, right
, bottom
);
624 /***********************************************************************
625 * NtGdiSetRectRgn (win32u.@)
627 * Sets a region to a simple rectangular region.
630 * hrgn [I] Region to convert.
631 * left [I] Left coordinate of rectangle.
632 * top [I] Top coordinate of rectangle.
633 * right [I] Right coordinate of rectangle.
634 * bottom [I] Bottom coordinate of rectangle.
641 * Allows either or both left and top to be greater than right or bottom.
643 BOOL WINAPI
NtGdiSetRectRgn( HRGN hrgn
, INT left
, INT top
, INT right
, INT bottom
)
647 TRACE("%p %d,%d-%d,%d\n", hrgn
, left
, top
, right
, bottom
);
649 if (!(obj
= GDI_GetObjPtr( hrgn
, NTGDI_OBJ_REGION
))) return FALSE
;
651 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
652 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
654 if((left
!= right
) && (top
!= bottom
))
656 obj
->rects
->left
= obj
->extents
.left
= left
;
657 obj
->rects
->top
= obj
->extents
.top
= top
;
658 obj
->rects
->right
= obj
->extents
.right
= right
;
659 obj
->rects
->bottom
= obj
->extents
.bottom
= bottom
;
665 GDI_ReleaseObj( hrgn
);
670 /***********************************************************************
671 * NtGdiCreateRoundRectRgn (win32u.@)
673 * Creates a rectangular region with rounded corners.
676 * left [I] Left coordinate of rectangle.
677 * top [I] Top coordinate of rectangle.
678 * right [I] Right coordinate of rectangle.
679 * bottom [I] Bottom coordinate of rectangle.
680 * ellipse_width [I] Width of the ellipse at each corner.
681 * ellipse_height [I] Height of the ellipse at each corner.
684 * Success: Handle to region.
688 * If ellipse_width or ellipse_height is less than 2 logical units then
689 * it is treated as though CreateRectRgn() was called instead.
691 HRGN WINAPI
NtGdiCreateRoundRectRgn( INT left
, INT top
, INT right
, INT bottom
,
692 INT ellipse_width
, INT ellipse_height
)
697 INT64 asq
, bsq
, dx
, dy
, err
;
700 /* Make the dimensions sensible */
702 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
703 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
704 /* the region is for the rectangle interior, but only at right and bottom for some reason */
708 ellipse_width
= min( right
- left
, abs( ellipse_width
));
709 ellipse_height
= min( bottom
- top
, abs( ellipse_height
));
711 /* Check if we can do a normal rectangle instead */
713 if ((ellipse_width
< 2) || (ellipse_height
< 2))
714 return NtGdiCreateRectRgn( left
, top
, right
, bottom
);
716 if (!(obj
= alloc_region( ellipse_height
))) return 0;
717 obj
->numRects
= ellipse_height
;
718 obj
->extents
.left
= left
;
719 obj
->extents
.top
= top
;
720 obj
->extents
.right
= right
;
721 obj
->extents
.bottom
= bottom
;
724 /* based on an algorithm by Alois Zingl */
726 a
= ellipse_width
- 1;
727 b
= ellipse_height
- 1;
728 asq
= (INT64
)8 * a
* a
;
729 bsq
= (INT64
)8 * b
* b
;
730 dx
= (INT64
)4 * b
* b
* (1 - a
);
731 dy
= (INT64
)4 * a
* a
* (1 + (b
% 2));
732 err
= dx
+ dy
+ a
* a
* (b
% 2);
735 y
= ellipse_height
/ 2;
737 rects
[y
].left
= left
;
738 rects
[y
].right
= right
;
740 while (x
<= ellipse_width
/ 2)
752 rects
[y
].left
= left
+ x
;
753 rects
[y
].right
= right
- x
;
756 for (i
= 0; i
< ellipse_height
/ 2; i
++)
758 rects
[i
].left
= rects
[b
- i
].left
;
759 rects
[i
].right
= rects
[b
- i
].right
;
760 rects
[i
].top
= top
+ i
;
761 rects
[i
].bottom
= rects
[i
].top
+ 1;
763 for (; i
< ellipse_height
; i
++)
765 rects
[i
].top
= bottom
- ellipse_height
+ i
;
766 rects
[i
].bottom
= rects
[i
].top
+ 1;
768 rects
[ellipse_height
/ 2].top
= top
+ ellipse_height
/ 2; /* extend to top of rectangle */
770 hrgn
= alloc_gdi_handle( &obj
->obj
, NTGDI_OBJ_REGION
, ®ion_funcs
);
772 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
773 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
774 if (!hrgn
) free_region( obj
);
779 /***********************************************************************
780 * NtGdiCreateEllipticRgn (win32u.@)
782 * Creates an elliptical region.
785 * left [I] Left coordinate of bounding rectangle.
786 * top [I] Top coordinate of bounding rectangle.
787 * right [I] Right coordinate of bounding rectangle.
788 * bottom [I] Bottom coordinate of bounding rectangle.
791 * Success: Handle to region.
795 * This is a special case of CreateRoundRectRgn() where the width of the
796 * ellipse at each corner is equal to the width the rectangle and
797 * the same for the height.
799 HRGN WINAPI
NtGdiCreateEllipticRgn( INT left
, INT top
, INT right
, INT bottom
)
801 return NtGdiCreateRoundRectRgn( left
, top
, right
, bottom
,
802 right
- left
, bottom
- top
);
806 /***********************************************************************
807 * NtGdiGetRegionData (win32u.@)
809 * Retrieves the data that specifies the region.
812 * hrgn [I] Region to retrieve the region data from.
813 * count [I] The size of the buffer pointed to by rgndata in bytes.
814 * rgndata [I] The buffer to receive data about the region.
817 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
818 * the number of bytes copied to the output buffer.
822 * The format of the Buffer member of RGNDATA is determined by the iType
823 * member of the region data header.
824 * Currently this is always RDH_RECTANGLES, which specifies that the format
825 * is the array of RECT's that specify the region. The length of the array
826 * is specified by the nCount member of the region data header.
828 DWORD WINAPI
NtGdiGetRegionData( HRGN hrgn
, DWORD count
, RGNDATA
*rgndata
)
831 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, NTGDI_OBJ_REGION
);
833 TRACE(" %p count = %d, rgndata = %p\n", hrgn
, (int)count
, rgndata
);
837 size
= obj
->numRects
* sizeof(RECT
);
838 if (!rgndata
|| count
< FIELD_OFFSET(RGNDATA
, Buffer
[size
]))
840 GDI_ReleaseObj( hrgn
);
841 if (rgndata
) /* buffer is too small, signal it by return 0 */
843 /* user requested buffer size with NULL rgndata */
844 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
847 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
848 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
849 rgndata
->rdh
.nCount
= obj
->numRects
;
850 rgndata
->rdh
.nRgnSize
= size
;
851 rgndata
->rdh
.rcBound
.left
= obj
->extents
.left
;
852 rgndata
->rdh
.rcBound
.top
= obj
->extents
.top
;
853 rgndata
->rdh
.rcBound
.right
= obj
->extents
.right
;
854 rgndata
->rdh
.rcBound
.bottom
= obj
->extents
.bottom
;
856 memcpy( rgndata
->Buffer
, obj
->rects
, size
);
858 GDI_ReleaseObj( hrgn
);
859 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
863 static void translate( POINT
*pt
, UINT count
, const XFORM
*xform
)
869 pt
->x
= GDI_ROUND( x
* xform
->eM11
+ y
* xform
->eM21
+ xform
->eDx
);
870 pt
->y
= GDI_ROUND( x
* xform
->eM12
+ y
* xform
->eM22
+ xform
->eDy
);
876 /***********************************************************************
877 * NtGdiExtCreateRegion (win32u.@)
879 * Creates a region as specified by the transformation data and region data.
882 * lpXform [I] World-space to logical-space transformation data.
883 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
884 * rgndata [I] Data that specifies the region.
887 * Success: Handle to region.
891 * See GetRegionData().
893 HRGN WINAPI
NtGdiExtCreateRegion( const XFORM
*xform
, DWORD count
, const RGNDATA
*rgndata
)
897 const RECT
*pCurRect
, *pEndRect
;
899 if (!rgndata
|| rgndata
->rdh
.dwSize
< sizeof(RGNDATAHEADER
))
902 /* XP doesn't care about the type */
903 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
904 WARN("(Unsupported region data type: %u)\n", (int)rgndata
->rdh
.iType
);
908 const RECT
*pCurRect
, *pEndRect
;
910 hrgn
= NtGdiCreateRectRgn( 0, 0, 0, 0 );
912 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
913 for (pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
915 static const INT count
= 4;
919 pt
[0].x
= pCurRect
->left
;
920 pt
[0].y
= pCurRect
->top
;
921 pt
[1].x
= pCurRect
->right
;
922 pt
[1].y
= pCurRect
->top
;
923 pt
[2].x
= pCurRect
->right
;
924 pt
[2].y
= pCurRect
->bottom
;
925 pt
[3].x
= pCurRect
->left
;
926 pt
[3].y
= pCurRect
->bottom
;
928 translate( pt
, 4, xform
);
929 poly_hrgn
= create_polypolygon_region( pt
, &count
, 1, WINDING
, NULL
);
930 NtGdiCombineRgn( hrgn
, hrgn
, poly_hrgn
, RGN_OR
);
931 NtGdiDeleteObjectApp( poly_hrgn
);
936 if (!(obj
= alloc_region( rgndata
->rdh
.nCount
))) return 0;
938 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
939 for(pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
941 if (pCurRect
->left
< pCurRect
->right
&& pCurRect
->top
< pCurRect
->bottom
)
943 if (!REGION_UnionRectWithRegion( pCurRect
, obj
)) goto done
;
946 hrgn
= alloc_gdi_handle( &obj
->obj
, NTGDI_OBJ_REGION
, ®ion_funcs
);
949 if (!hrgn
) free_region( obj
);
951 TRACE("%p %d %p returning %p\n", xform
, (int)count
, rgndata
, hrgn
);
956 /***********************************************************************
957 * NtGdiPtInRegion (win32u.@)
959 * Tests whether the specified point is inside a region.
962 * hrgn [I] Region to test.
963 * x [I] X-coordinate of point to test.
964 * y [I] Y-coordinate of point to test.
967 * Non-zero if the point is inside the region or zero otherwise.
969 BOOL WINAPI
NtGdiPtInRegion( HRGN hrgn
, INT x
, INT y
)
974 if ((obj
= GDI_GetObjPtr( hrgn
, NTGDI_OBJ_REGION
)))
976 if (obj
->numRects
> 0 && is_in_rect( &obj
->extents
, x
, y
))
977 region_find_pt( obj
, x
, y
, &ret
);
978 GDI_ReleaseObj( hrgn
);
984 /***********************************************************************
985 * NtGdiRectInRegion (win32u.@)
987 * Tests if a rectangle is at least partly inside the specified region.
990 * hrgn [I] Region to test.
991 * rect [I] Rectangle to test.
994 * Non-zero if the rectangle is partially inside the region or
997 BOOL WINAPI
NtGdiRectInRegion( HRGN hrgn
, const RECT
*rect
)
1004 /* swap the coordinates to make right >= left and bottom >= top */
1005 /* (region building rectangles are normalized the same way) */
1009 if ((obj
= GDI_GetObjPtr( hrgn
, NTGDI_OBJ_REGION
)))
1011 if ((obj
->numRects
> 0) && overlapping(&obj
->extents
, &rc
))
1013 for (i
= region_find_pt( obj
, rc
.left
, rc
.top
, &ret
); !ret
&& i
< obj
->numRects
; i
++ )
1015 if (obj
->rects
[i
].bottom
<= rc
.top
)
1016 continue; /* not far enough down yet */
1018 if (obj
->rects
[i
].top
>= rc
.bottom
)
1019 break; /* too far down */
1021 if (obj
->rects
[i
].right
<= rc
.left
)
1022 continue; /* not far enough over yet */
1024 if (obj
->rects
[i
].left
>= rc
.right
)
1030 GDI_ReleaseObj(hrgn
);
1035 /***********************************************************************
1036 * NtGdiEqualRgn (win32u.@)
1038 * Tests whether one region is identical to another.
1041 * hrgn1 [I] The first region to compare.
1042 * hrgn2 [I] The second region to compare.
1045 * Non-zero if both regions are identical or zero otherwise.
1047 BOOL WINAPI
NtGdiEqualRgn( HRGN hrgn1
, HRGN hrgn2
)
1049 WINEREGION
*obj1
, *obj2
;
1052 if ((obj1
= GDI_GetObjPtr( hrgn1
, NTGDI_OBJ_REGION
)))
1054 if ((obj2
= GDI_GetObjPtr( hrgn2
, NTGDI_OBJ_REGION
)))
1058 if ( obj1
->numRects
!= obj2
->numRects
) goto done
;
1059 if ( obj1
->numRects
== 0 )
1065 if (obj1
->extents
.left
!= obj2
->extents
.left
) goto done
;
1066 if (obj1
->extents
.right
!= obj2
->extents
.right
) goto done
;
1067 if (obj1
->extents
.top
!= obj2
->extents
.top
) goto done
;
1068 if (obj1
->extents
.bottom
!= obj2
->extents
.bottom
) goto done
;
1069 for( i
= 0; i
< obj1
->numRects
; i
++ )
1071 if (obj1
->rects
[i
].left
!= obj2
->rects
[i
].left
) goto done
;
1072 if (obj1
->rects
[i
].right
!= obj2
->rects
[i
].right
) goto done
;
1073 if (obj1
->rects
[i
].top
!= obj2
->rects
[i
].top
) goto done
;
1074 if (obj1
->rects
[i
].bottom
!= obj2
->rects
[i
].bottom
) goto done
;
1078 GDI_ReleaseObj(hrgn2
);
1080 GDI_ReleaseObj(hrgn1
);
1085 /***********************************************************************
1086 * REGION_UnionRectWithRegion
1087 * Adds a rectangle to a WINEREGION
1089 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1093 init_region( ®ion
, 1 );
1094 region
.numRects
= 1;
1095 region
.extents
= *region
.rects
= *rect
;
1096 return REGION_UnionRegion(rgn
, rgn
, ®ion
);
1100 BOOL
add_rect_to_region( HRGN rgn
, const RECT
*rect
)
1102 WINEREGION
*obj
= GDI_GetObjPtr( rgn
, NTGDI_OBJ_REGION
);
1105 if (!obj
) return FALSE
;
1106 ret
= REGION_UnionRectWithRegion( rect
, obj
);
1107 GDI_ReleaseObj( rgn
);
1111 /***********************************************************************
1112 * REGION_CreateFrameRgn
1114 * Create a region that is a frame around another region.
1115 * Compute the intersection of the region moved in all 4 directions
1116 * ( +x, -x, +y, -y) and subtract from the original.
1117 * The result looks slightly better than in Windows :)
1119 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1123 WINEREGION
* destObj
= NULL
;
1124 WINEREGION
*srcObj
= GDI_GetObjPtr( hSrc
, NTGDI_OBJ_REGION
);
1126 tmprgn
.rects
= NULL
;
1127 if (!srcObj
) return FALSE
;
1128 if (srcObj
->numRects
!= 0)
1130 if (!(destObj
= GDI_GetObjPtr( hDest
, NTGDI_OBJ_REGION
))) goto done
;
1131 if (!init_region( &tmprgn
, srcObj
->numRects
)) goto done
;
1133 if (!REGION_OffsetRegion( destObj
, srcObj
, -x
, 0)) goto done
;
1134 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, x
, 0)) goto done
;
1135 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1136 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, -y
)) goto done
;
1137 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1138 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, y
)) goto done
;
1139 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1140 if (!REGION_SubtractRegion( destObj
, srcObj
, destObj
)) goto done
;
1144 destroy_region( &tmprgn
);
1145 if (destObj
) GDI_ReleaseObj ( hDest
);
1146 GDI_ReleaseObj( hSrc
);
1151 /***********************************************************************
1152 * NtGdiCombineRgn (win32u.@)
1154 * Combines two regions with the specified operation and stores the result
1155 * in the specified destination region.
1158 * hDest [I] The region that receives the combined result.
1159 * hSrc1 [I] The first source region.
1160 * hSrc2 [I] The second source region.
1161 * mode [I] The way in which the source regions will be combined. See notes.
1165 * NULLREGION - The new region is empty.
1166 * SIMPLEREGION - The new region can be represented by one rectangle.
1167 * COMPLEXREGION - The new region can only be represented by more than
1172 * The two source regions can be the same region.
1173 * The mode can be one of the following:
1174 *| RGN_AND - Intersection of the regions
1175 *| RGN_OR - Union of the regions
1176 *| RGN_XOR - Unions of the regions minus any intersection.
1177 *| RGN_DIFF - Difference (subtraction) of the regions.
1179 INT WINAPI
NtGdiCombineRgn( HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1181 WINEREGION
*destObj
= GDI_GetObjPtr( hDest
, NTGDI_OBJ_REGION
);
1184 TRACE(" %p,%p -> %p mode=%x\n", hSrc1
, hSrc2
, hDest
, mode
);
1187 WINEREGION
*src1Obj
= GDI_GetObjPtr( hSrc1
, NTGDI_OBJ_REGION
);
1191 TRACE("dump src1Obj:\n");
1192 if(TRACE_ON(region
))
1193 REGION_DumpRegion(src1Obj
);
1194 if (mode
== RGN_COPY
)
1196 if (REGION_CopyRegion( destObj
, src1Obj
))
1197 result
= get_region_type( destObj
);
1201 WINEREGION
*src2Obj
= GDI_GetObjPtr( hSrc2
, NTGDI_OBJ_REGION
);
1205 TRACE("dump src2Obj:\n");
1206 if(TRACE_ON(region
))
1207 REGION_DumpRegion(src2Obj
);
1211 if (REGION_IntersectRegion( destObj
, src1Obj
, src2Obj
))
1212 result
= get_region_type( destObj
);
1215 if (REGION_UnionRegion( destObj
, src1Obj
, src2Obj
))
1216 result
= get_region_type( destObj
);
1219 if (REGION_XorRegion( destObj
, src1Obj
, src2Obj
))
1220 result
= get_region_type( destObj
);
1223 if (REGION_SubtractRegion( destObj
, src1Obj
, src2Obj
))
1224 result
= get_region_type( destObj
);
1227 GDI_ReleaseObj( hSrc2
);
1230 GDI_ReleaseObj( hSrc1
);
1232 TRACE("dump destObj:\n");
1233 if(TRACE_ON(region
))
1234 REGION_DumpRegion(destObj
);
1236 GDI_ReleaseObj( hDest
);
1241 /***********************************************************************
1243 * Re-calculate the extents of a region
1245 static void REGION_SetExtents (WINEREGION
*pReg
)
1247 RECT
*pRect
, *pRectEnd
, *pExtents
;
1249 if (pReg
->numRects
== 0)
1251 pReg
->extents
.left
= 0;
1252 pReg
->extents
.top
= 0;
1253 pReg
->extents
.right
= 0;
1254 pReg
->extents
.bottom
= 0;
1258 pExtents
= &pReg
->extents
;
1259 pRect
= pReg
->rects
;
1260 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1263 * Since pRect is the first rectangle in the region, it must have the
1264 * smallest top and since pRectEnd is the last rectangle in the region,
1265 * it must have the largest bottom, because of banding. Initialize left and
1266 * right from pRect and pRectEnd, resp., as good things to initialize them
1269 pExtents
->left
= pRect
->left
;
1270 pExtents
->top
= pRect
->top
;
1271 pExtents
->right
= pRectEnd
->right
;
1272 pExtents
->bottom
= pRectEnd
->bottom
;
1274 while (pRect
<= pRectEnd
)
1276 if (pRect
->left
< pExtents
->left
)
1277 pExtents
->left
= pRect
->left
;
1278 if (pRect
->right
> pExtents
->right
)
1279 pExtents
->right
= pRect
->right
;
1284 /***********************************************************************
1287 static BOOL
REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1289 if (dst
!= src
) /* don't want to copy to itself */
1291 if (dst
->size
< src
->numRects
&& !grow_region( dst
, src
->numRects
))
1294 dst
->numRects
= src
->numRects
;
1295 dst
->extents
.left
= src
->extents
.left
;
1296 dst
->extents
.top
= src
->extents
.top
;
1297 dst
->extents
.right
= src
->extents
.right
;
1298 dst
->extents
.bottom
= src
->extents
.bottom
;
1299 memcpy(dst
->rects
, src
->rects
, src
->numRects
* sizeof(RECT
));
1304 /***********************************************************************
1305 * REGION_MirrorRegion
1307 static BOOL
REGION_MirrorRegion( WINEREGION
*dst
, WINEREGION
*src
, int width
)
1316 if (!grow_region( dst
, src
->numRects
)) return FALSE
;
1318 dst
->numRects
= src
->numRects
;
1322 if (!init_region( &tmp
, src
->numRects
)) return FALSE
;
1324 tmp
.numRects
= src
->numRects
;
1327 extents
.left
= width
- src
->extents
.right
;
1328 extents
.right
= width
- src
->extents
.left
;
1329 extents
.top
= src
->extents
.top
;
1330 extents
.bottom
= src
->extents
.bottom
;
1332 for (start
= 0; start
< src
->numRects
; start
= end
)
1334 /* find the end of the current band */
1335 for (end
= start
+ 1; end
< src
->numRects
; end
++)
1336 if (src
->rects
[end
].top
!= src
->rects
[end
- 1].top
) break;
1338 for (i
= 0; i
< end
- start
; i
++)
1340 rects
[start
+ i
].left
= width
- src
->rects
[end
- i
- 1].right
;
1341 rects
[start
+ i
].right
= width
- src
->rects
[end
- i
- 1].left
;
1342 rects
[start
+ i
].top
= src
->rects
[end
- i
- 1].top
;
1343 rects
[start
+ i
].bottom
= src
->rects
[end
- i
- 1].bottom
;
1348 move_rects( dst
, &tmp
);
1350 dst
->extents
= extents
;
1354 /***********************************************************************
1357 INT
mirror_region( HRGN dst
, HRGN src
, INT width
)
1359 WINEREGION
*src_rgn
, *dst_rgn
;
1362 if (!(src_rgn
= GDI_GetObjPtr( src
, NTGDI_OBJ_REGION
))) return ERROR
;
1363 if ((dst_rgn
= GDI_GetObjPtr( dst
, NTGDI_OBJ_REGION
)))
1365 if (REGION_MirrorRegion( dst_rgn
, src_rgn
, width
)) ret
= get_region_type( dst_rgn
);
1366 GDI_ReleaseObj( dst_rgn
);
1368 GDI_ReleaseObj( src_rgn
);
1372 /***********************************************************************
1373 * mirror_window_region
1375 BOOL
mirror_window_region( HWND hwnd
, HRGN hrgn
)
1379 if (!get_window_rect( hwnd
, &rect
, get_thread_dpi() )) return FALSE
;
1380 return mirror_region( hrgn
, hrgn
, rect
.right
- rect
.left
) != ERROR
;
1384 /***********************************************************************
1387 * Attempt to merge the rects in the current band with those in the
1388 * previous one. Used only by REGION_RegionOp.
1391 * The new index for the previous band.
1394 * If coalescing takes place:
1395 * - rectangles in the previous band will have their bottom fields
1397 * - pReg->numRects will be decreased.
1400 static INT
REGION_Coalesce (
1401 WINEREGION
*pReg
, /* Region to coalesce */
1402 INT prevStart
, /* Index of start of previous band */
1403 INT curStart
/* Index of start of current band */
1405 RECT
*pPrevRect
; /* Current rect in previous band */
1406 RECT
*pCurRect
; /* Current rect in current band */
1407 RECT
*pRegEnd
; /* End of region */
1408 INT curNumRects
; /* Number of rectangles in current band */
1409 INT prevNumRects
; /* Number of rectangles in previous band */
1410 INT bandtop
; /* top coordinate for current band */
1412 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1414 pPrevRect
= &pReg
->rects
[prevStart
];
1415 prevNumRects
= curStart
- prevStart
;
1418 * Figure out how many rectangles are in the current band. Have to do
1419 * this because multiple bands could have been added in REGION_RegionOp
1420 * at the end when one region has been exhausted.
1422 pCurRect
= &pReg
->rects
[curStart
];
1423 bandtop
= pCurRect
->top
;
1424 for (curNumRects
= 0;
1425 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1431 if (pCurRect
!= pRegEnd
)
1434 * If more than one band was added, we have to find the start
1435 * of the last band added so the next coalescing job can start
1436 * at the right place... (given when multiple bands are added,
1437 * this may be pointless -- see above).
1440 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1444 curStart
= pRegEnd
- pReg
->rects
;
1445 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1448 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1449 pCurRect
-= curNumRects
;
1451 * The bands may only be coalesced if the bottom of the previous
1452 * matches the top scanline of the current.
1454 if (pPrevRect
->bottom
== pCurRect
->top
)
1457 * Make sure the bands have rects in the same places. This
1458 * assumes that rects have been added in such a way that they
1459 * cover the most area possible. I.e. two rects in a band must
1460 * have some horizontal space between them.
1464 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1465 (pPrevRect
->right
!= pCurRect
->right
))
1468 * The bands don't line up so they can't be coalesced.
1475 } while (prevNumRects
!= 0);
1477 pReg
->numRects
-= curNumRects
;
1478 pCurRect
-= curNumRects
;
1479 pPrevRect
-= curNumRects
;
1482 * The bands may be merged, so set the bottom of each rect
1483 * in the previous band to that of the corresponding rect in
1488 pPrevRect
->bottom
= pCurRect
->bottom
;
1492 } while (curNumRects
!= 0);
1495 * If only one band was added to the region, we have to backup
1496 * curStart to the start of the previous band.
1498 * If more than one band was added to the region, copy the
1499 * other bands down. The assumption here is that the other bands
1500 * came from the same region as the current one and no further
1501 * coalescing can be done on them since it's all been done
1502 * already... curStart is already in the right place.
1504 if (pCurRect
== pRegEnd
)
1506 curStart
= prevStart
;
1512 *pPrevRect
++ = *pCurRect
++;
1513 } while (pCurRect
!= pRegEnd
);
1521 /**********************************************************************
1524 * To keep regions from growing without bound, shrink the array of rectangles
1525 * to match the new number of rectangles in the region.
1527 * Only do this if the number of rectangles allocated is more than
1528 * twice the number of rectangles in the region.
1530 static void REGION_compact( WINEREGION
*reg
)
1532 if ((reg
->numRects
< reg
->size
/ 2) && (reg
->numRects
> RGN_DEFAULT_RECTS
))
1534 RECT
*new_rects
= realloc( reg
->rects
, reg
->numRects
* sizeof(RECT
) );
1537 reg
->rects
= new_rects
;
1538 reg
->size
= reg
->numRects
;
1543 /***********************************************************************
1546 * Apply an operation to two regions. Called by REGION_Union,
1547 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1553 * The new region is overwritten.
1556 * The idea behind this function is to view the two regions as sets.
1557 * Together they cover a rectangle of area that this function divides
1558 * into horizontal bands where points are covered only by one region
1559 * or by both. For the first case, the nonOverlapFunc is called with
1560 * each the band and the band's upper and lower extents. For the
1561 * second, the overlapFunc is called to process the entire band. It
1562 * is responsible for clipping the rectangles in the band, though
1563 * this function provides the boundaries.
1564 * At the end of each band, the new region is coalesced, if possible,
1565 * to reduce the number of rectangles in the region.
1568 static BOOL
REGION_RegionOp(
1569 WINEREGION
*destReg
, /* Place to store result */
1570 WINEREGION
*reg1
, /* First region in operation */
1571 WINEREGION
*reg2
, /* 2nd region in operation */
1572 BOOL (*overlapFunc
)(WINEREGION
*, RECT
*, RECT
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for over-lapping bands */
1573 BOOL (*nonOverlap1Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for non-overlapping bands in region 1 */
1574 BOOL (*nonOverlap2Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
) /* Function to call for non-overlapping bands in region 2 */
1577 RECT
*r1
; /* Pointer into first region */
1578 RECT
*r2
; /* Pointer into 2d region */
1579 RECT
*r1End
; /* End of 1st region */
1580 RECT
*r2End
; /* End of 2d region */
1581 INT ybot
; /* Bottom of intersection */
1582 INT ytop
; /* Top of intersection */
1583 INT prevBand
; /* Index of start of
1584 * previous band in newReg */
1585 INT curBand
; /* Index of start of current
1587 RECT
*r1BandEnd
; /* End of current band in r1 */
1588 RECT
*r2BandEnd
; /* End of current band in r2 */
1589 INT top
; /* Top of non-overlapping band */
1590 INT bot
; /* Bottom of non-overlapping band */
1594 * set r1, r2, r1End and r2End appropriately, preserve the important
1595 * parts of the destination region until the end in case it's one of
1596 * the two source regions, then mark the "new" region empty, allocating
1597 * another array of rectangles for it to use.
1601 r1End
= r1
+ reg1
->numRects
;
1602 r2End
= r2
+ reg2
->numRects
;
1605 * Allocate a reasonable number of rectangles for the new region. The idea
1606 * is to allocate enough so the individual functions don't need to
1607 * reallocate and copy the array, which is time consuming, yet we don't
1608 * have to worry about using too much memory. I hope to be able to
1609 * nuke the Xrealloc() at the end of this function eventually.
1611 if (!init_region( &newReg
, max(reg1
->numRects
,reg2
->numRects
) * 2 )) return FALSE
;
1614 * Initialize ybot and ytop.
1615 * In the upcoming loop, ybot and ytop serve different functions depending
1616 * on whether the band being handled is an overlapping or non-overlapping
1618 * In the case of a non-overlapping band (only one of the regions
1619 * has points in the band), ybot is the bottom of the most recent
1620 * intersection and thus clips the top of the rectangles in that band.
1621 * ytop is the top of the next intersection between the two regions and
1622 * serves to clip the bottom of the rectangles in the current band.
1623 * For an overlapping band (where the two regions intersect), ytop clips
1624 * the top of the rectangles of both regions and ybot clips the bottoms.
1626 if (reg1
->extents
.top
< reg2
->extents
.top
)
1627 ybot
= reg1
->extents
.top
;
1629 ybot
= reg2
->extents
.top
;
1632 * prevBand serves to mark the start of the previous band so rectangles
1633 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1634 * In the beginning, there is no previous band, so prevBand == curBand
1635 * (curBand is set later on, of course, but the first band will always
1636 * start at index 0). prevBand and curBand must be indices because of
1637 * the possible expansion, and resultant moving, of the new region's
1638 * array of rectangles.
1644 curBand
= newReg
.numRects
;
1647 * This algorithm proceeds one source-band (as opposed to a
1648 * destination band, which is determined by where the two regions
1649 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1650 * rectangle after the last one in the current band for their
1651 * respective regions.
1654 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1660 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1666 * First handle the band that doesn't intersect, if any.
1668 * Note that attention is restricted to one band in the
1669 * non-intersecting region at once, so if a region has n
1670 * bands between the current position and the next place it overlaps
1671 * the other, this entire loop will be passed through n times.
1673 if (r1
->top
< r2
->top
)
1675 top
= max(r1
->top
,ybot
);
1676 bot
= min(r1
->bottom
,r2
->top
);
1678 if ((top
!= bot
) && (nonOverlap1Func
!= NULL
))
1680 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, top
, bot
)) return FALSE
;
1685 else if (r2
->top
< r1
->top
)
1687 top
= max(r2
->top
,ybot
);
1688 bot
= min(r2
->bottom
,r1
->top
);
1690 if ((top
!= bot
) && (nonOverlap2Func
!= NULL
))
1692 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, top
, bot
)) return FALSE
;
1703 * If any rectangles got added to the region, try and coalesce them
1704 * with rectangles from the previous band. Note we could just do
1705 * this test in miCoalesce, but some machines incur a not
1706 * inconsiderable cost for function calls, so...
1708 if (newReg
.numRects
!= curBand
)
1710 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1714 * Now see if we've hit an intersecting band. The two bands only
1715 * intersect if ybot > ytop
1717 ybot
= min(r1
->bottom
, r2
->bottom
);
1718 curBand
= newReg
.numRects
;
1721 if (!overlapFunc(&newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
)) return FALSE
;
1724 if (newReg
.numRects
!= curBand
)
1726 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1730 * If we've finished with a band (bottom == ybot) we skip forward
1731 * in the region to the next band.
1733 if (r1
->bottom
== ybot
)
1737 if (r2
->bottom
== ybot
)
1741 } while ((r1
!= r1End
) && (r2
!= r2End
));
1744 * Deal with whichever region still has rectangles left.
1746 curBand
= newReg
.numRects
;
1749 if (nonOverlap1Func
!= NULL
)
1754 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1758 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, max(r1
->top
,ybot
), r1
->bottom
))
1761 } while (r1
!= r1End
);
1764 else if ((r2
!= r2End
) && (nonOverlap2Func
!= NULL
))
1769 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1773 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, max(r2
->top
,ybot
), r2
->bottom
))
1776 } while (r2
!= r2End
);
1779 if (newReg
.numRects
!= curBand
)
1781 REGION_Coalesce (&newReg
, prevBand
, curBand
);
1784 REGION_compact( &newReg
);
1785 move_rects( destReg
, &newReg
);
1789 /***********************************************************************
1790 * Region Intersection
1791 ***********************************************************************/
1794 /***********************************************************************
1797 * Handle an overlapping band for REGION_Intersect.
1803 * Rectangles may be added to the region.
1806 static BOOL
REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1807 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1812 while ((r1
!= r1End
) && (r2
!= r2End
))
1814 left
= max(r1
->left
, r2
->left
);
1815 right
= min(r1
->right
, r2
->right
);
1818 * If there's any overlap between the two rectangles, add that
1819 * overlap to the new region.
1820 * There's no need to check for subsumption because the only way
1821 * such a need could arise is if some region has two rectangles
1822 * right next to each other. Since that should never happen...
1826 if (!add_rect( pReg
, left
, top
, right
, bottom
)) return FALSE
;
1830 * Need to advance the pointers. Shift the one that extends
1831 * to the right the least, since the other still has a chance to
1832 * overlap with that region's next rectangle, if you see what I mean.
1834 if (r1
->right
< r2
->right
)
1838 else if (r2
->right
< r1
->right
)
1851 /***********************************************************************
1852 * REGION_IntersectRegion
1854 static BOOL
REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1857 /* check for trivial reject */
1858 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1859 (!overlapping(®1
->extents
, ®2
->extents
)))
1860 newReg
->numRects
= 0;
1862 if (!REGION_RegionOp (newReg
, reg1
, reg2
, REGION_IntersectO
, NULL
, NULL
)) return FALSE
;
1865 * Can't alter newReg's extents before we call miRegionOp because
1866 * it might be one of the source regions and miRegionOp depends
1867 * on the extents of those regions being the same. Besides, this
1868 * way there's no checking against rectangles that will be nuked
1869 * due to coalescing, so we have to examine fewer rectangles.
1871 REGION_SetExtents(newReg
);
1875 /***********************************************************************
1877 ***********************************************************************/
1879 /***********************************************************************
1882 * Handle a non-overlapping band for the union operation. Just
1883 * Adds the rectangles into the region. Doesn't have to check for
1884 * subsumption or anything.
1890 * pReg->numRects is incremented and the final rectangles overwritten
1891 * with the rectangles we're passed.
1894 static BOOL
REGION_UnionNonO(WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
1898 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
1904 /***********************************************************************
1907 * Handle an overlapping band for the union operation. Picks the
1908 * left-most rectangle each time and merges it into the region.
1914 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1918 static BOOL
REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1919 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1921 #define MERGERECT(r) \
1922 if ((pReg->numRects != 0) && \
1923 (pReg->rects[pReg->numRects-1].top == top) && \
1924 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
1925 (pReg->rects[pReg->numRects-1].right >= r->left)) \
1927 if (pReg->rects[pReg->numRects-1].right < r->right) \
1928 pReg->rects[pReg->numRects-1].right = r->right; \
1932 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
1936 while ((r1
!= r1End
) && (r2
!= r2End
))
1938 if (r1
->left
< r2
->left
)
1953 } while (r1
!= r1End
);
1955 else while (r2
!= r2End
)
1963 /***********************************************************************
1964 * REGION_UnionRegion
1966 static BOOL
REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
, WINEREGION
*reg2
)
1970 /* checks all the simple cases */
1973 * Region 1 and 2 are the same or region 1 is empty
1975 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
1978 ret
= REGION_CopyRegion(newReg
, reg2
);
1983 * if nothing to union (region 2 empty)
1985 if (!(reg2
->numRects
))
1988 ret
= REGION_CopyRegion(newReg
, reg1
);
1993 * Region 1 completely subsumes region 2
1995 if ((reg1
->numRects
== 1) &&
1996 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
1997 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
1998 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
1999 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
2002 ret
= REGION_CopyRegion(newReg
, reg1
);
2007 * Region 2 completely subsumes region 1
2009 if ((reg2
->numRects
== 1) &&
2010 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
2011 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
2012 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
2013 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
2016 ret
= REGION_CopyRegion(newReg
, reg2
);
2020 if ((ret
= REGION_RegionOp (newReg
, reg1
, reg2
, REGION_UnionO
, REGION_UnionNonO
, REGION_UnionNonO
)))
2022 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
2023 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
2024 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
2025 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
2030 /***********************************************************************
2031 * Region Subtraction
2032 ***********************************************************************/
2034 /***********************************************************************
2035 * REGION_SubtractNonO1
2037 * Deal with non-overlapping band for subtraction. Any parts from
2038 * region 2 we discard. Anything from region 1 we add to the region.
2044 * pReg may be affected.
2047 static BOOL
REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
2051 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
2058 /***********************************************************************
2061 * Overlapping band subtraction. x1 is the left-most point not yet
2068 * pReg may have rectangles added to it.
2071 static BOOL
REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2072 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2074 INT left
= r1
->left
;
2076 while ((r1
!= r1End
) && (r2
!= r2End
))
2078 if (r2
->right
<= left
)
2081 * Subtrahend missed the boat: go to next subtrahend.
2085 else if (r2
->left
<= left
)
2088 * Subtrahend precedes minuend: nuke left edge of minuend.
2091 if (left
>= r1
->right
)
2094 * Minuend completely covered: advance to next minuend and
2095 * reset left fence to edge of new minuend.
2104 * Subtrahend now used up since it doesn't extend beyond
2110 else if (r2
->left
< r1
->right
)
2113 * Left part of subtrahend covers part of minuend: add uncovered
2114 * part of minuend to region and skip to next subtrahend.
2116 if (!add_rect( pReg
, left
, top
, r2
->left
, bottom
)) return FALSE
;
2118 if (left
>= r1
->right
)
2121 * Minuend used up: advance to new...
2130 * Subtrahend used up
2138 * Minuend used up: add any remaining piece before advancing.
2140 if (r1
->right
> left
)
2142 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2151 * Add remaining minuend rectangles to region.
2155 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2165 /***********************************************************************
2166 * REGION_SubtractRegion
2168 * Subtract regS from regM and leave the result in regD.
2169 * S stands for subtrahend, M for minuend and D for difference.
2175 * regD is overwritten.
2178 static BOOL
REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
, WINEREGION
*regS
)
2180 /* check for trivial reject */
2181 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2182 (!overlapping(®M
->extents
, ®S
->extents
)) )
2183 return REGION_CopyRegion(regD
, regM
);
2185 if (!REGION_RegionOp (regD
, regM
, regS
, REGION_SubtractO
, REGION_SubtractNonO1
, NULL
))
2189 * Can't alter newReg's extents before we call miRegionOp because
2190 * it might be one of the source regions and miRegionOp depends
2191 * on the extents of those regions being the unaltered. Besides, this
2192 * way there's no checking against rectangles that will be nuked
2193 * due to coalescing, so we have to examine fewer rectangles.
2195 REGION_SetExtents (regD
);
2199 /***********************************************************************
2202 static BOOL
REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
, WINEREGION
*srb
)
2204 WINEREGION tra
, trb
;
2207 if (!init_region( &tra
, sra
->numRects
+ 1 )) return FALSE
;
2208 if ((ret
= init_region( &trb
, srb
->numRects
+ 1 )))
2210 ret
= REGION_SubtractRegion(&tra
,sra
,srb
) &&
2211 REGION_SubtractRegion(&trb
,srb
,sra
) &&
2212 REGION_UnionRegion(dr
,&tra
,&trb
);
2213 destroy_region(&trb
);
2215 destroy_region(&tra
);
2219 /**************************************************************************
2223 *************************************************************************/
2225 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2226 #define SMALL_COORDINATE 0x80000000
2228 /***********************************************************************
2229 * REGION_InsertEdgeInET
2231 * Insert the given edge into the edge table.
2232 * First we must find the correct bucket in the
2233 * Edge table, then find the right slot in the
2234 * bucket. Finally, we can insert it.
2237 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2238 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2242 ScanLineList
*pSLL
, *pPrevSLL
;
2243 ScanLineListBlock
*tmpSLLBlock
;
2246 * find the right bucket to put the edge into
2248 pPrevSLL
= &ET
->scanlines
;
2249 pSLL
= pPrevSLL
->next
;
2250 while (pSLL
&& (pSLL
->scanline
< scanline
))
2257 * reassign pSLL (pointer to ScanLineList) if necessary
2259 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2261 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2263 tmpSLLBlock
= malloc( sizeof(ScanLineListBlock
) );
2266 WARN("Can't alloc SLLB\n");
2269 (*SLLBlock
)->next
= tmpSLLBlock
;
2270 tmpSLLBlock
->next
= NULL
;
2271 *SLLBlock
= tmpSLLBlock
;
2274 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2276 pSLL
->next
= pPrevSLL
->next
;
2277 list_init( &pSLL
->edgelist
);
2278 pPrevSLL
->next
= pSLL
;
2280 pSLL
->scanline
= scanline
;
2283 * now insert the edge in the right bucket
2285 LIST_FOR_EACH( ptr
, &pSLL
->edgelist
)
2287 struct edge_table_entry
*entry
= LIST_ENTRY( ptr
, struct edge_table_entry
, entry
);
2288 if (entry
->bres
.minor_axis
>= ETE
->bres
.minor_axis
) break;
2290 list_add_before( ptr
, &ETE
->entry
);
2293 /***********************************************************************
2294 * REGION_CreateEdgeTable
2296 * This routine creates the edge table for
2297 * scan converting polygons.
2298 * The Edge Table (ET) looks like:
2302 * | ymax | ScanLineLists
2303 * |scanline|-->------------>-------------->...
2304 * -------- |scanline| |scanline|
2305 * |edgelist| |edgelist|
2306 * --------- ---------
2310 * list of ETEs list of ETEs
2312 * where ETE is an EdgeTableEntry data structure,
2313 * and there is one ScanLineList per scanline at
2314 * which an edge is initially entered.
2317 static unsigned int REGION_CreateEdgeTable(const INT
*Count
, INT nbpolygons
,
2318 const POINT
*pts
, EdgeTable
*ET
,
2319 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
,
2320 const RECT
*clip_rect
)
2322 const POINT
*top
, *bottom
;
2323 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2326 unsigned int dy
, total
= 0;
2329 * initialize the Edge Table.
2331 ET
->scanlines
.next
= NULL
;
2332 ET
->ymax
= SMALL_COORDINATE
;
2333 ET
->ymin
= LARGE_COORDINATE
;
2334 pSLLBlock
->next
= NULL
;
2337 for(poly
= 0; poly
< nbpolygons
; poly
++)
2339 count
= Count
[poly
];
2347 * for each vertex in the array of points.
2348 * In this loop we are dealing with two vertices at
2349 * a time -- these make up one edge of the polygon.
2351 for ( ; count
; PrevPt
= CurrPt
, count
--)
2356 * find out which point is above and which is below.
2358 if (PrevPt
->y
> CurrPt
->y
)
2360 bottom
= PrevPt
, top
= CurrPt
;
2361 pETEs
->ClockWise
= 0;
2365 bottom
= CurrPt
, top
= PrevPt
;
2366 pETEs
->ClockWise
= 1;
2370 * don't add horizontal edges to the Edge table.
2372 if (bottom
->y
== top
->y
) continue;
2373 if (clip_rect
&& (top
->y
>= clip_rect
->bottom
|| bottom
->y
<= clip_rect
->top
)) continue;
2374 pETEs
->ymax
= bottom
->y
-1; /* -1 so we don't get last scanline */
2377 * initialize integer edge algorithm
2379 dy
= bottom
->y
- top
->y
;
2380 bres_init_polygon(dy
, top
->x
, bottom
->x
, &pETEs
->bres
);
2382 if (clip_rect
) dy
= min( bottom
->y
, clip_rect
->bottom
) - max( top
->y
, clip_rect
->top
);
2383 if (total
+ dy
< total
) return 0; /* overflow */
2386 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
, &iSLLBlock
);
2388 if (top
->y
< ET
->ymin
) ET
->ymin
= top
->y
;
2389 if (bottom
->y
> ET
->ymax
) ET
->ymax
= bottom
->y
;
2396 /***********************************************************************
2399 * This routine moves EdgeTableEntries from the
2400 * EdgeTable into the Active Edge Table,
2401 * leaving them sorted by smaller x coordinate.
2404 static void REGION_loadAET( struct list
*AET
, struct list
*ETEs
)
2406 struct edge_table_entry
*ptr
, *next
, *entry
;
2407 struct list
*active
;
2409 LIST_FOR_EACH_ENTRY_SAFE( ptr
, next
, ETEs
, struct edge_table_entry
, entry
)
2411 LIST_FOR_EACH( active
, AET
)
2413 entry
= LIST_ENTRY( active
, struct edge_table_entry
, entry
);
2414 if (entry
->bres
.minor_axis
>= ptr
->bres
.minor_axis
) break;
2416 list_remove( &ptr
->entry
);
2417 list_add_before( active
, &ptr
->entry
);
2421 /***********************************************************************
2422 * REGION_computeWAET
2424 * This routine links the AET by the
2425 * nextWETE (winding EdgeTableEntry) link for
2426 * use by the winding number rule. The final
2427 * Active Edge Table (AET) might look something
2431 * ---------- --------- ---------
2432 * |ymax | |ymax | |ymax |
2433 * | ... | |... | |... |
2434 * |next |->|next |->|next |->...
2435 * |nextWETE| |nextWETE| |nextWETE|
2436 * --------- --------- ^--------
2438 * V-------------------> V---> ...
2441 static void REGION_computeWAET( struct list
*AET
, struct list
*WETE
)
2443 struct edge_table_entry
*active
;
2448 LIST_FOR_EACH_ENTRY( active
, AET
, struct edge_table_entry
, entry
)
2450 if (active
->ClockWise
)
2455 if ((!inside
&& !isInside
) || (inside
&& isInside
))
2457 list_add_tail( WETE
, &active
->winding_entry
);
2463 /***********************************************************************
2466 * Update the Active Edge Table for the next scan line and sort it again.
2468 static inline BOOL
next_scanline( struct list
*AET
, int y
)
2470 struct edge_table_entry
*active
, *next
, *insert
;
2471 BOOL changed
= FALSE
;
2473 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, AET
, struct edge_table_entry
, entry
)
2475 if (active
->ymax
== y
) /* leaving this edge */
2477 list_remove( &active
->entry
);
2480 else bres_incr_polygon( &active
->bres
);
2482 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, AET
, struct edge_table_entry
, entry
)
2484 LIST_FOR_EACH_ENTRY( insert
, AET
, struct edge_table_entry
, entry
)
2486 if (insert
== active
) break;
2487 if (insert
->bres
.minor_axis
> active
->bres
.minor_axis
) break;
2489 if (insert
== active
) continue;
2490 list_remove( &active
->entry
);
2491 list_add_before( &insert
->entry
, &active
->entry
);
2497 /***********************************************************************
2498 * REGION_FreeStorage
2502 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2504 ScanLineListBlock
*tmpSLLBlock
;
2508 tmpSLLBlock
= pSLLBlock
->next
;
2510 pSLLBlock
= tmpSLLBlock
;
2514 static void scan_convert( WINEREGION
*obj
, EdgeTable
*ET
, INT mode
, const RECT
*clip_rect
)
2518 struct edge_table_entry
*active
;
2519 INT i
, y
, first
= 1, cur_band
= 0, prev_band
= 0;
2521 if (clip_rect
) ET
->ymax
= min( ET
->ymax
, clip_rect
->bottom
);
2524 pSLL
= ET
->scanlines
.next
;
2526 if (mode
!= WINDING
)
2528 for (y
= ET
->ymin
; y
< ET
->ymax
; y
++)
2530 /* Add a new edge to the active edge table when we get to the next edge. */
2531 if (pSLL
!= NULL
&& y
== pSLL
->scanline
)
2533 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2537 if (!clip_rect
|| y
>= clip_rect
->top
)
2539 LIST_FOR_EACH_ENTRY( active
, &AET
, struct edge_table_entry
, entry
)
2543 obj
->rects
[obj
->numRects
].left
= active
->bres
.minor_axis
;
2544 obj
->rects
[obj
->numRects
].top
= y
;
2545 obj
->rects
[obj
->numRects
].bottom
= y
+ 1;
2547 else if (obj
->rects
[obj
->numRects
].left
!= active
->bres
.minor_axis
)
2549 /* create new rect only if we can't merge with the previous one */
2550 if (!obj
->numRects
|| obj
->rects
[obj
->numRects
-1].top
!= y
||
2551 obj
->rects
[obj
->numRects
-1].right
< obj
->rects
[obj
->numRects
].left
)
2553 obj
->rects
[obj
->numRects
-1].right
= active
->bres
.minor_axis
;
2559 next_scanline( &AET
, y
);
2563 prev_band
= REGION_Coalesce( obj
, prev_band
, cur_band
);
2564 cur_band
= obj
->numRects
;
2568 else /* mode == WINDING */
2570 struct list WETE
, *pWETE
;
2572 for (y
= ET
->ymin
; y
< ET
->ymax
; y
++)
2574 /* Add a new edge to the active edge table when we get to the next edge. */
2575 if (pSLL
!= NULL
&& y
== pSLL
->scanline
)
2577 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2578 REGION_computeWAET( &AET
, &WETE
);
2581 pWETE
= list_head( &WETE
);
2583 if (!clip_rect
|| y
>= clip_rect
->top
)
2585 LIST_FOR_EACH_ENTRY( active
, &AET
, struct edge_table_entry
, entry
)
2587 /* Add to the buffer only those edges that are in the Winding active edge table. */
2588 if (pWETE
== &active
->winding_entry
)
2592 obj
->rects
[obj
->numRects
].left
= active
->bres
.minor_axis
;
2593 obj
->rects
[obj
->numRects
].top
= y
;
2595 else if (obj
->rects
[obj
->numRects
].left
!= active
->bres
.minor_axis
)
2597 obj
->rects
[obj
->numRects
].right
= active
->bres
.minor_axis
;
2598 obj
->rects
[obj
->numRects
].bottom
= y
+ 1;
2602 pWETE
= list_next( &WETE
, pWETE
);
2607 /* Recompute the winding active edge table if we just resorted or have exited an edge. */
2608 if (next_scanline( &AET
, y
)) REGION_computeWAET( &AET
, &WETE
);
2612 prev_band
= REGION_Coalesce( obj
, prev_band
, cur_band
);
2613 cur_band
= obj
->numRects
;
2618 assert( obj
->numRects
<= obj
->size
);
2622 obj
->extents
.left
= INT_MAX
;
2623 obj
->extents
.right
= INT_MIN
;
2624 obj
->extents
.top
= obj
->rects
[0].top
;
2625 obj
->extents
.bottom
= obj
->rects
[obj
->numRects
-1].bottom
;
2626 for (i
= 0; i
< obj
->numRects
; i
++)
2628 obj
->extents
.left
= min( obj
->extents
.left
, obj
->rects
[i
].left
);
2629 obj
->extents
.right
= max( obj
->extents
.right
, obj
->rects
[i
].right
);
2632 REGION_compact( obj
);
2635 /***********************************************************************
2636 * create_polypolygon_region
2638 * Helper for CreatePolyPolygonRgn.
2640 HRGN
create_polypolygon_region( const POINT
*Pts
, const INT
*Count
, INT nbpolygons
, INT mode
,
2641 const RECT
*clip_rect
)
2644 WINEREGION
*obj
= NULL
;
2645 EdgeTable ET
; /* header node for ET */
2646 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2647 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2648 unsigned int nb_points
;
2651 TRACE("%p, count %d, polygons %d, mode %d\n", Pts
, *Count
, nbpolygons
, mode
);
2653 /* special case a rectangle */
2655 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2656 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2657 (((Pts
[0].y
== Pts
[1].y
) &&
2658 (Pts
[1].x
== Pts
[2].x
) &&
2659 (Pts
[2].y
== Pts
[3].y
) &&
2660 (Pts
[3].x
== Pts
[0].x
)) ||
2661 ((Pts
[0].x
== Pts
[1].x
) &&
2662 (Pts
[1].y
== Pts
[2].y
) &&
2663 (Pts
[2].x
== Pts
[3].x
) &&
2664 (Pts
[3].y
== Pts
[0].y
))))
2665 return NtGdiCreateRectRgn( min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2666 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2668 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2669 total
+= Count
[poly
];
2670 if (! (pETEs
= malloc( sizeof(EdgeTableEntry
) * total
)))
2673 nb_points
= REGION_CreateEdgeTable( Count
, nbpolygons
, Pts
, &ET
, pETEs
, &SLLBlock
, clip_rect
);
2674 if ((obj
= alloc_region( nb_points
/ 2 )))
2676 if (nb_points
) scan_convert( obj
, &ET
, mode
, clip_rect
);
2678 if (!(hrgn
= alloc_gdi_handle( &obj
->obj
, NTGDI_OBJ_REGION
, ®ion_funcs
)))
2682 REGION_FreeStorage(SLLBlock
.next
);