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
add_rect( WINEREGION
*reg
, INT left
, INT top
, INT right
, INT bottom
)
131 if (reg
->numRects
>= reg
->size
)
133 RECT
*newrects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
, 2 * sizeof(RECT
) * reg
->size
);
134 if (!newrects
) return FALSE
;
135 reg
->rects
= newrects
;
138 rect
= reg
->rects
+ reg
->numRects
++;
142 rect
->bottom
= bottom
;
146 static inline void empty_region( WINEREGION
*reg
)
149 reg
->extents
.left
= reg
->extents
.top
= reg
->extents
.right
= reg
->extents
.bottom
= 0;
152 static inline BOOL
is_in_rect( const RECT
*rect
, int x
, int y
)
154 return (rect
->right
> x
&& rect
->left
<= x
&& rect
->bottom
> y
&& rect
->top
<= y
);
158 * number of points to buffer before sending them off
159 * to scanlines() : Must be an even number
161 #define NUMPTSTOBUFFER 200
164 * used to allocate buffers for points and link
165 * the buffers together
170 POINT pts
[NUMPTSTOBUFFER
];
172 struct point_block
*next
;
175 static struct point_block
*add_point( struct point_block
*block
, int x
, int y
)
177 if (block
->count
== NUMPTSTOBUFFER
)
179 struct point_block
*new = HeapAlloc( GetProcessHeap(), 0, sizeof(*new) );
180 if (!new) return NULL
;
186 block
->pts
[block
->count
].x
= x
;
187 block
->pts
[block
->count
].y
= y
;
192 static void free_point_blocks( struct point_block
*block
)
196 struct point_block
*tmp
= block
->next
;
197 HeapFree( GetProcessHeap(), 0, block
);
204 * This file contains a few macros to help track
205 * the edge of a filled object. The object is assumed
206 * to be filled in scanline order, and thus the
207 * algorithm used is an extension of Bresenham's line
208 * drawing algorithm which assumes that y is always the
210 * Since these pieces of code are the same for any filled shape,
211 * it is more convenient to gather the library in one
212 * place, but since these pieces of code are also in
213 * the inner loops of output primitives, procedure call
214 * overhead is out of the question.
215 * See the author for a derivation if needed.
220 * This structure contains all of the information needed
221 * to run the bresenham algorithm.
222 * The variables may be hardcoded into the declarations
223 * instead of using this structure to make use of
224 * register declarations.
228 INT minor_axis
; /* minor axis */
229 INT d
; /* decision variable */
230 INT m
, m1
; /* slope and slope+1 */
231 INT incr1
, incr2
; /* error increments */
236 * In scan converting polygons, we want to choose those pixels
237 * which are inside the polygon. Thus, we add .5 to the starting
238 * x coordinate for both left and right edges. Now we choose the
239 * first pixel which is inside the pgon for the left edge and the
240 * first pixel which is outside the pgon for the right edge.
241 * Draw the left pixel, but not the right.
243 * How to add .5 to the starting x coordinate:
244 * If the edge is moving to the right, then subtract dy from the
245 * error term from the general form of the algorithm.
246 * If the edge is moving to the left, then add dy to the error term.
248 * The reason for the difference between edges moving to the left
249 * and edges moving to the right is simple: If an edge is moving
250 * to the right, then we want the algorithm to flip immediately.
251 * If it is moving to the left, then we don't want it to flip until
252 * we traverse an entire pixel.
254 static inline void bres_init_polygon( int dy
, int x1
, int x2
, struct bres_info
*bres
)
259 * if the edge is horizontal, then it is ignored
260 * and assumed not to be processed. Otherwise, do this stuff.
264 bres
->minor_axis
= x1
;
269 bres
->m1
= bres
->m
- 1;
270 bres
->incr1
= -2 * dx
+ 2 * dy
* bres
->m1
;
271 bres
->incr2
= -2 * dx
+ 2 * dy
* bres
->m
;
272 bres
->d
= 2 * bres
->m
* dy
- 2 * dx
- 2 * dy
;
277 bres
->m1
= bres
->m
+ 1;
278 bres
->incr1
= 2 * dx
- 2 * dy
* bres
->m1
;
279 bres
->incr2
= 2 * dx
- 2 * dy
* bres
->m
;
280 bres
->d
= -2 * bres
->m
* dy
+ 2 * dx
;
284 static inline void bres_incr_polygon( struct bres_info
*bres
)
288 bres
->minor_axis
+= bres
->m1
;
289 bres
->d
+= bres
->incr1
;
292 bres
->minor_axis
+= bres
->m
;
293 bres
->d
+= bres
->incr2
;
297 bres
->minor_axis
+= bres
->m1
;
298 bres
->d
+= bres
->incr1
;
301 bres
->minor_axis
+= bres
->m
;
302 bres
->d
+= bres
->incr2
;
309 * These are the data structures needed to scan
310 * convert regions. Two different scan conversion
311 * methods are available -- the even-odd method, and
312 * the winding number method.
313 * The even-odd rule states that a point is inside
314 * the polygon if a ray drawn from that point in any
315 * direction will pass through an odd number of
317 * By the winding number rule, a point is decided
318 * to be inside the polygon if a ray drawn from that
319 * point in any direction passes through a different
320 * number of clockwise and counter-clockwise path
323 * These data structures are adapted somewhat from
324 * the algorithm in (Foley/Van Dam) for scan converting
326 * The basic algorithm is to start at the top (smallest y)
327 * of the polygon, stepping down to the bottom of
328 * the polygon by incrementing the y coordinate. We
329 * keep a list of edges which the current scanline crosses,
330 * sorted by x. This list is called the Active Edge Table (AET)
331 * As we change the y-coordinate, we update each entry in
332 * in the active edge table to reflect the edges new xcoord.
333 * This list must be sorted at each scanline in case
334 * two edges intersect.
335 * We also keep a data structure known as the Edge Table (ET),
336 * which keeps track of all the edges which the current
337 * scanline has not yet reached. The ET is basically a
338 * list of ScanLineList structures containing a list of
339 * edges which are entered at a given scanline. There is one
340 * ScanLineList per scanline at which an edge is entered.
341 * When we enter a new edge, we move it from the ET to the AET.
343 * From the AET, we can implement the even-odd rule as in
345 * The winding number rule is a little trickier. We also
346 * keep the EdgeTableEntries in the AET linked by the
347 * nextWETE (winding EdgeTableEntry) link. This allows
348 * the edges to be linked just as before for updating
349 * purposes, but only uses the edges linked by the nextWETE
350 * link as edges representing spans of the polygon to
351 * drawn (as with the even-odd rule).
354 typedef struct edge_table_entry
{
356 struct list winding_entry
;
357 INT ymax
; /* ycoord at which we exit this edge. */
358 struct bres_info bres
; /* Bresenham info to run the edge */
359 int ClockWise
; /* flag for winding number rule */
363 typedef struct _ScanLineList
{
364 struct list edgelist
;
365 INT scanline
; /* the scanline represented */
366 struct _ScanLineList
*next
; /* next in the list */
371 INT ymax
; /* ymax for the polygon */
372 INT ymin
; /* ymin for the polygon */
373 ScanLineList scanlines
; /* header node */
378 * Here is a struct to help with storage allocation
379 * so we can allocate a big chunk at a time, and then take
380 * pieces from this heap when we need to.
382 #define SLLSPERBLOCK 25
384 typedef struct _ScanLineListBlock
{
385 ScanLineList SLLs
[SLLSPERBLOCK
];
386 struct _ScanLineListBlock
*next
;
390 /* Note the parameter order is different from the X11 equivalents */
392 static BOOL
REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
393 static BOOL
REGION_OffsetRegion(WINEREGION
*d
, WINEREGION
*s
, INT x
, INT y
);
394 static BOOL
REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
395 static BOOL
REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
396 static BOOL
REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
397 static BOOL
REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
398 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
400 #define RGN_DEFAULT_RECTS 2
403 /***********************************************************************
406 static inline INT
get_region_type( const WINEREGION
*obj
)
408 switch(obj
->numRects
)
410 case 0: return NULLREGION
;
411 case 1: return SIMPLEREGION
;
412 default: return COMPLEXREGION
;
417 /***********************************************************************
419 * Outputs the contents of a WINEREGION
421 static void REGION_DumpRegion(WINEREGION
*pReg
)
423 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
425 TRACE("Region %p: %s %d rects\n", pReg
, wine_dbgstr_rect(&pReg
->extents
), pReg
->numRects
);
426 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
427 TRACE("\t%s\n", wine_dbgstr_rect(pRect
));
432 /***********************************************************************
435 * Initialize a new empty region.
437 static BOOL
init_region( WINEREGION
*pReg
, INT n
)
439 if (!(pReg
->rects
= HeapAlloc(GetProcessHeap(), 0, n
* sizeof( RECT
)))) return FALSE
;
445 /***********************************************************************
448 static void destroy_region( WINEREGION
*pReg
)
450 HeapFree( GetProcessHeap(), 0, pReg
->rects
);
453 /***********************************************************************
454 * REGION_DeleteObject
456 static BOOL
REGION_DeleteObject( HGDIOBJ handle
)
458 WINEREGION
*rgn
= free_gdi_handle( handle
);
460 if (!rgn
) return FALSE
;
461 HeapFree( GetProcessHeap(), 0, rgn
->rects
);
462 HeapFree( GetProcessHeap(), 0, rgn
);
466 /***********************************************************************
467 * REGION_SelectObject
469 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, HDC hdc
)
471 return ULongToHandle(SelectClipRgn( hdc
, handle
));
475 /***********************************************************************
476 * REGION_OffsetRegion
477 * Offset a WINEREGION by x,y
479 static BOOL
REGION_OffsetRegion( WINEREGION
*rgn
, WINEREGION
*srcrgn
, INT x
, INT y
)
483 if (!REGION_CopyRegion( rgn
, srcrgn
)) return FALSE
;
486 int nbox
= rgn
->numRects
;
487 RECT
*pbox
= rgn
->rects
;
497 rgn
->extents
.left
+= x
;
498 rgn
->extents
.right
+= x
;
499 rgn
->extents
.top
+= y
;
500 rgn
->extents
.bottom
+= y
;
506 /***********************************************************************
507 * OffsetRgn (GDI32.@)
509 * Moves a region by the specified X- and Y-axis offsets.
512 * hrgn [I] Region to offset.
513 * x [I] Offset right if positive or left if negative.
514 * y [I] Offset down if positive or up if negative.
518 * NULLREGION - The new region is empty.
519 * SIMPLEREGION - The new region can be represented by one rectangle.
520 * COMPLEXREGION - The new region can only be represented by more than
524 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
526 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
529 TRACE("%p %d,%d\n", hrgn
, x
, y
);
534 REGION_OffsetRegion( obj
, obj
, x
, y
);
536 ret
= get_region_type( obj
);
537 GDI_ReleaseObj( hrgn
);
542 /***********************************************************************
543 * GetRgnBox (GDI32.@)
545 * Retrieves the bounding rectangle of the region. The bounding rectangle
546 * is the smallest rectangle that contains the entire region.
549 * hrgn [I] Region to retrieve bounding rectangle from.
550 * rect [O] Rectangle that will receive the coordinates of the bounding
554 * NULLREGION - The new region is empty.
555 * SIMPLEREGION - The new region can be represented by one rectangle.
556 * COMPLEXREGION - The new region can only be represented by more than
559 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
561 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
565 rect
->left
= obj
->extents
.left
;
566 rect
->top
= obj
->extents
.top
;
567 rect
->right
= obj
->extents
.right
;
568 rect
->bottom
= obj
->extents
.bottom
;
569 TRACE("%p %s\n", hrgn
, wine_dbgstr_rect(rect
));
570 ret
= get_region_type( obj
);
571 GDI_ReleaseObj(hrgn
);
578 /***********************************************************************
579 * CreateRectRgn (GDI32.@)
581 * Creates a simple rectangular region.
584 * left [I] Left coordinate of rectangle.
585 * top [I] Top coordinate of rectangle.
586 * right [I] Right coordinate of rectangle.
587 * bottom [I] Bottom coordinate of rectangle.
590 * Success: Handle to region.
593 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
598 if (!(obj
= HeapAlloc( GetProcessHeap(), 0, sizeof(*obj
) ))) return 0;
600 /* Allocate 2 rects by default to reduce the number of reallocs */
601 if (!init_region( obj
, RGN_DEFAULT_RECTS
))
603 HeapFree( GetProcessHeap(), 0, obj
);
606 if (!(hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
)))
608 HeapFree( GetProcessHeap(), 0, obj
->rects
);
609 HeapFree( GetProcessHeap(), 0, obj
);
612 TRACE( "%d,%d-%d,%d returning %p\n", left
, top
, right
, bottom
, hrgn
);
613 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
618 /***********************************************************************
619 * CreateRectRgnIndirect (GDI32.@)
621 * Creates a simple rectangular region.
624 * rect [I] Coordinates of rectangular region.
627 * Success: Handle to region.
630 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
632 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
636 /***********************************************************************
637 * SetRectRgn (GDI32.@)
639 * Sets a region to a simple rectangular region.
642 * hrgn [I] Region to convert.
643 * left [I] Left coordinate of rectangle.
644 * top [I] Top coordinate of rectangle.
645 * right [I] Right coordinate of rectangle.
646 * bottom [I] Bottom coordinate of rectangle.
653 * Allows either or both left and top to be greater than right or bottom.
655 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
656 INT right
, INT bottom
)
660 TRACE("%p %d,%d-%d,%d\n", hrgn
, left
, top
, right
, bottom
);
662 if (!(obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
))) return FALSE
;
664 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
665 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
667 if((left
!= right
) && (top
!= bottom
))
669 obj
->rects
->left
= obj
->extents
.left
= left
;
670 obj
->rects
->top
= obj
->extents
.top
= top
;
671 obj
->rects
->right
= obj
->extents
.right
= right
;
672 obj
->rects
->bottom
= obj
->extents
.bottom
= bottom
;
678 GDI_ReleaseObj( hrgn
);
683 /***********************************************************************
684 * CreateRoundRectRgn (GDI32.@)
686 * Creates a rectangular region with rounded corners.
689 * left [I] Left coordinate of rectangle.
690 * top [I] Top coordinate of rectangle.
691 * right [I] Right coordinate of rectangle.
692 * bottom [I] Bottom coordinate of rectangle.
693 * ellipse_width [I] Width of the ellipse at each corner.
694 * ellipse_height [I] Height of the ellipse at each corner.
697 * Success: Handle to region.
701 * If ellipse_width or ellipse_height is less than 2 logical units then
702 * it is treated as though CreateRectRgn() was called instead.
704 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
705 INT right
, INT bottom
,
706 INT ellipse_width
, INT ellipse_height
)
711 INT64 asq
, bsq
, dx
, dy
, err
;
714 /* Make the dimensions sensible */
716 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
717 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
718 /* the region is for the rectangle interior, but only at right and bottom for some reason */
722 ellipse_width
= min( right
- left
, abs( ellipse_width
));
723 ellipse_height
= min( bottom
- top
, abs( ellipse_height
));
725 /* Check if we can do a normal rectangle instead */
727 if ((ellipse_width
< 2) || (ellipse_height
< 2))
728 return CreateRectRgn( left
, top
, right
, bottom
);
730 if (!(obj
= HeapAlloc( GetProcessHeap(), 0, sizeof(*obj
) ))) return 0;
731 obj
->size
= ellipse_height
;
732 obj
->numRects
= ellipse_height
;
733 obj
->extents
.left
= left
;
734 obj
->extents
.top
= top
;
735 obj
->extents
.right
= right
;
736 obj
->extents
.bottom
= bottom
;
738 obj
->rects
= rects
= HeapAlloc( GetProcessHeap(), 0, obj
->size
* sizeof(RECT
) );
739 if (!rects
) goto done
;
741 /* based on an algorithm by Alois Zingl */
743 a
= ellipse_width
- 1;
744 b
= ellipse_height
- 1;
745 asq
= (INT64
)8 * a
* a
;
746 bsq
= (INT64
)8 * b
* b
;
747 dx
= (INT64
)4 * b
* b
* (1 - a
);
748 dy
= (INT64
)4 * a
* a
* (1 + (b
% 2));
749 err
= dx
+ dy
+ a
* a
* (b
% 2);
752 y
= ellipse_height
/ 2;
754 rects
[y
].left
= left
;
755 rects
[y
].right
= right
;
757 while (x
<= ellipse_width
/ 2)
769 rects
[y
].left
= left
+ x
;
770 rects
[y
].right
= right
- x
;
773 for (i
= 0; i
< ellipse_height
/ 2; i
++)
775 rects
[i
].left
= rects
[b
- i
].left
;
776 rects
[i
].right
= rects
[b
- i
].right
;
777 rects
[i
].top
= top
+ i
;
778 rects
[i
].bottom
= rects
[i
].top
+ 1;
780 for (; i
< ellipse_height
; i
++)
782 rects
[i
].top
= bottom
- ellipse_height
+ i
;
783 rects
[i
].bottom
= rects
[i
].top
+ 1;
785 rects
[ellipse_height
/ 2].top
= top
+ ellipse_height
/ 2; /* extend to top of rectangle */
787 hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
);
789 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
790 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
794 HeapFree( GetProcessHeap(), 0, obj
->rects
);
795 HeapFree( GetProcessHeap(), 0, obj
);
801 /***********************************************************************
802 * CreateEllipticRgn (GDI32.@)
804 * Creates an elliptical region.
807 * left [I] Left coordinate of bounding rectangle.
808 * top [I] Top coordinate of bounding rectangle.
809 * right [I] Right coordinate of bounding rectangle.
810 * bottom [I] Bottom coordinate of bounding rectangle.
813 * Success: Handle to region.
817 * This is a special case of CreateRoundRectRgn() where the width of the
818 * ellipse at each corner is equal to the width the rectangle and
819 * the same for the height.
821 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
822 INT right
, INT bottom
)
824 return CreateRoundRectRgn( left
, top
, right
, bottom
,
825 right
-left
, bottom
-top
);
829 /***********************************************************************
830 * CreateEllipticRgnIndirect (GDI32.@)
832 * Creates an elliptical region.
835 * rect [I] Pointer to bounding rectangle of the ellipse.
838 * Success: Handle to region.
842 * This is a special case of CreateRoundRectRgn() where the width of the
843 * ellipse at each corner is equal to the width the rectangle and
844 * the same for the height.
846 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
848 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
849 rect
->bottom
, rect
->right
- rect
->left
,
850 rect
->bottom
- rect
->top
);
853 /***********************************************************************
854 * GetRegionData (GDI32.@)
856 * Retrieves the data that specifies the region.
859 * hrgn [I] Region to retrieve the region data from.
860 * count [I] The size of the buffer pointed to by rgndata in bytes.
861 * rgndata [I] The buffer to receive data about the region.
864 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
865 * the number of bytes copied to the output buffer.
869 * The format of the Buffer member of RGNDATA is determined by the iType
870 * member of the region data header.
871 * Currently this is always RDH_RECTANGLES, which specifies that the format
872 * is the array of RECT's that specify the region. The length of the array
873 * is specified by the nCount member of the region data header.
875 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
878 WINEREGION
*obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
);
880 TRACE(" %p count = %d, rgndata = %p\n", hrgn
, count
, rgndata
);
884 size
= obj
->numRects
* sizeof(RECT
);
885 if (!rgndata
|| count
< FIELD_OFFSET(RGNDATA
, Buffer
[size
]))
887 GDI_ReleaseObj( hrgn
);
888 if (rgndata
) /* buffer is too small, signal it by return 0 */
890 /* user requested buffer size with NULL rgndata */
891 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
894 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
895 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
896 rgndata
->rdh
.nCount
= obj
->numRects
;
897 rgndata
->rdh
.nRgnSize
= size
;
898 rgndata
->rdh
.rcBound
.left
= obj
->extents
.left
;
899 rgndata
->rdh
.rcBound
.top
= obj
->extents
.top
;
900 rgndata
->rdh
.rcBound
.right
= obj
->extents
.right
;
901 rgndata
->rdh
.rcBound
.bottom
= obj
->extents
.bottom
;
903 memcpy( rgndata
->Buffer
, obj
->rects
, size
);
905 GDI_ReleaseObj( hrgn
);
906 return FIELD_OFFSET(RGNDATA
, Buffer
[size
]);
910 static void translate( POINT
*pt
, UINT count
, const XFORM
*xform
)
916 pt
->x
= floor( x
* xform
->eM11
+ y
* xform
->eM21
+ xform
->eDx
+ 0.5 );
917 pt
->y
= floor( x
* xform
->eM12
+ y
* xform
->eM22
+ xform
->eDy
+ 0.5 );
923 /***********************************************************************
924 * ExtCreateRegion (GDI32.@)
926 * Creates a region as specified by the transformation data and region data.
929 * lpXform [I] World-space to logical-space transformation data.
930 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
931 * rgndata [I] Data that specifies the region.
934 * Success: Handle to region.
938 * See GetRegionData().
940 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
947 SetLastError( ERROR_INVALID_PARAMETER
);
951 if (rgndata
->rdh
.dwSize
< sizeof(RGNDATAHEADER
))
954 /* XP doesn't care about the type */
955 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
956 WARN("(Unsupported region data type: %u)\n", rgndata
->rdh
.iType
);
960 const RECT
*pCurRect
, *pEndRect
;
962 hrgn
= CreateRectRgn( 0, 0, 0, 0 );
964 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
965 for (pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
967 static const INT count
= 4;
971 pt
[0].x
= pCurRect
->left
;
972 pt
[0].y
= pCurRect
->top
;
973 pt
[1].x
= pCurRect
->right
;
974 pt
[1].y
= pCurRect
->top
;
975 pt
[2].x
= pCurRect
->right
;
976 pt
[2].y
= pCurRect
->bottom
;
977 pt
[3].x
= pCurRect
->left
;
978 pt
[3].y
= pCurRect
->bottom
;
980 translate( pt
, 4, lpXform
);
981 poly_hrgn
= CreatePolyPolygonRgn( pt
, &count
, 1, WINDING
);
982 CombineRgn( hrgn
, hrgn
, poly_hrgn
, RGN_OR
);
983 DeleteObject( poly_hrgn
);
988 if (!(obj
= HeapAlloc( GetProcessHeap(), 0, sizeof(*obj
) ))) return 0;
990 if (init_region( obj
, rgndata
->rdh
.nCount
))
992 const RECT
*pCurRect
, *pEndRect
;
994 pEndRect
= (const RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
995 for(pCurRect
= (const RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
997 if (pCurRect
->left
< pCurRect
->right
&& pCurRect
->top
< pCurRect
->bottom
)
999 if (!REGION_UnionRectWithRegion( pCurRect
, obj
)) goto done
;
1002 hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
);
1006 HeapFree( GetProcessHeap(), 0, obj
);
1013 HeapFree( GetProcessHeap(), 0, obj
->rects
);
1014 HeapFree( GetProcessHeap(), 0, obj
);
1016 TRACE("%p %d %p returning %p\n", lpXform
, dwCount
, rgndata
, hrgn
);
1021 /***********************************************************************
1022 * PtInRegion (GDI32.@)
1024 * Tests whether the specified point is inside a region.
1027 * hrgn [I] Region to test.
1028 * x [I] X-coordinate of point to test.
1029 * y [I] Y-coordinate of point to test.
1032 * Non-zero if the point is inside the region or zero otherwise.
1034 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
1039 if ((obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
)))
1043 if (obj
->numRects
> 0 && is_in_rect(&obj
->extents
, x
, y
))
1044 for (i
= 0; i
< obj
->numRects
; i
++)
1045 if (is_in_rect(&obj
->rects
[i
], x
, y
))
1050 GDI_ReleaseObj( hrgn
);
1056 /***********************************************************************
1057 * RectInRegion (GDI32.@)
1059 * Tests if a rectangle is at least partly inside the specified region.
1062 * hrgn [I] Region to test.
1063 * rect [I] Rectangle to test.
1066 * Non-zero if the rectangle is partially inside the region or
1069 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
1075 /* swap the coordinates to make right >= left and bottom >= top */
1076 /* (region building rectangles are normalized the same way) */
1080 if ((obj
= GDI_GetObjPtr( hrgn
, OBJ_REGION
)))
1082 RECT
*pCurRect
, *pRectEnd
;
1084 /* this is (just) a useful optimization */
1085 if ((obj
->numRects
> 0) && overlapping(&obj
->extents
, &rc
))
1087 for (pCurRect
= obj
->rects
, pRectEnd
= pCurRect
+
1088 obj
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
1090 if (pCurRect
->bottom
<= rc
.top
)
1091 continue; /* not far enough down yet */
1093 if (pCurRect
->top
>= rc
.bottom
)
1094 break; /* too far down */
1096 if (pCurRect
->right
<= rc
.left
)
1097 continue; /* not far enough over yet */
1099 if (pCurRect
->left
>= rc
.right
) {
1107 GDI_ReleaseObj(hrgn
);
1112 /***********************************************************************
1113 * EqualRgn (GDI32.@)
1115 * Tests whether one region is identical to another.
1118 * hrgn1 [I] The first region to compare.
1119 * hrgn2 [I] The second region to compare.
1122 * Non-zero if both regions are identical or zero otherwise.
1124 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
1126 WINEREGION
*obj1
, *obj2
;
1129 if ((obj1
= GDI_GetObjPtr( hrgn1
, OBJ_REGION
)))
1131 if ((obj2
= GDI_GetObjPtr( hrgn2
, OBJ_REGION
)))
1135 if ( obj1
->numRects
!= obj2
->numRects
) goto done
;
1136 if ( obj1
->numRects
== 0 )
1142 if (obj1
->extents
.left
!= obj2
->extents
.left
) goto done
;
1143 if (obj1
->extents
.right
!= obj2
->extents
.right
) goto done
;
1144 if (obj1
->extents
.top
!= obj2
->extents
.top
) goto done
;
1145 if (obj1
->extents
.bottom
!= obj2
->extents
.bottom
) goto done
;
1146 for( i
= 0; i
< obj1
->numRects
; i
++ )
1148 if (obj1
->rects
[i
].left
!= obj2
->rects
[i
].left
) goto done
;
1149 if (obj1
->rects
[i
].right
!= obj2
->rects
[i
].right
) goto done
;
1150 if (obj1
->rects
[i
].top
!= obj2
->rects
[i
].top
) goto done
;
1151 if (obj1
->rects
[i
].bottom
!= obj2
->rects
[i
].bottom
) goto done
;
1155 GDI_ReleaseObj(hrgn2
);
1157 GDI_ReleaseObj(hrgn1
);
1162 /***********************************************************************
1163 * REGION_UnionRectWithRegion
1164 * Adds a rectangle to a WINEREGION
1166 static BOOL
REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1170 region
.rects
= ®ion
.extents
;
1171 region
.numRects
= 1;
1173 region
.extents
= *rect
;
1174 return REGION_UnionRegion(rgn
, rgn
, ®ion
);
1178 BOOL
add_rect_to_region( HRGN rgn
, const RECT
*rect
)
1180 WINEREGION
*obj
= GDI_GetObjPtr( rgn
, OBJ_REGION
);
1183 if (!obj
) return FALSE
;
1184 ret
= REGION_UnionRectWithRegion( rect
, obj
);
1185 GDI_ReleaseObj( rgn
);
1189 /***********************************************************************
1190 * REGION_CreateFrameRgn
1192 * Create a region that is a frame around another region.
1193 * Compute the intersection of the region moved in all 4 directions
1194 * ( +x, -x, +y, -y) and subtract from the original.
1195 * The result looks slightly better than in Windows :)
1197 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1201 WINEREGION
* destObj
= NULL
;
1202 WINEREGION
*srcObj
= GDI_GetObjPtr( hSrc
, OBJ_REGION
);
1204 tmprgn
.rects
= NULL
;
1205 if (!srcObj
) return FALSE
;
1206 if (srcObj
->numRects
!= 0)
1208 if (!(destObj
= GDI_GetObjPtr( hDest
, OBJ_REGION
))) goto done
;
1209 if (!init_region( &tmprgn
, srcObj
->numRects
)) goto done
;
1211 if (!REGION_OffsetRegion( destObj
, srcObj
, -x
, 0)) goto done
;
1212 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, x
, 0)) goto done
;
1213 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1214 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, -y
)) goto done
;
1215 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1216 if (!REGION_OffsetRegion( &tmprgn
, srcObj
, 0, y
)) goto done
;
1217 if (!REGION_IntersectRegion( destObj
, destObj
, &tmprgn
)) goto done
;
1218 if (!REGION_SubtractRegion( destObj
, srcObj
, destObj
)) goto done
;
1222 HeapFree( GetProcessHeap(), 0, tmprgn
.rects
);
1223 if (destObj
) GDI_ReleaseObj ( hDest
);
1224 GDI_ReleaseObj( hSrc
);
1229 /***********************************************************************
1230 * CombineRgn (GDI32.@)
1232 * Combines two regions with the specified operation and stores the result
1233 * in the specified destination region.
1236 * hDest [I] The region that receives the combined result.
1237 * hSrc1 [I] The first source region.
1238 * hSrc2 [I] The second source region.
1239 * mode [I] The way in which the source regions will be combined. See notes.
1243 * NULLREGION - The new region is empty.
1244 * SIMPLEREGION - The new region can be represented by one rectangle.
1245 * COMPLEXREGION - The new region can only be represented by more than
1250 * The two source regions can be the same region.
1251 * The mode can be one of the following:
1252 *| RGN_AND - Intersection of the regions
1253 *| RGN_OR - Union of the regions
1254 *| RGN_XOR - Unions of the regions minus any intersection.
1255 *| RGN_DIFF - Difference (subtraction) of the regions.
1257 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1259 WINEREGION
*destObj
= GDI_GetObjPtr( hDest
, OBJ_REGION
);
1262 TRACE(" %p,%p -> %p mode=%x\n", hSrc1
, hSrc2
, hDest
, mode
);
1265 WINEREGION
*src1Obj
= GDI_GetObjPtr( hSrc1
, OBJ_REGION
);
1269 TRACE("dump src1Obj:\n");
1270 if(TRACE_ON(region
))
1271 REGION_DumpRegion(src1Obj
);
1272 if (mode
== RGN_COPY
)
1274 if (REGION_CopyRegion( destObj
, src1Obj
))
1275 result
= get_region_type( destObj
);
1279 WINEREGION
*src2Obj
= GDI_GetObjPtr( hSrc2
, OBJ_REGION
);
1283 TRACE("dump src2Obj:\n");
1284 if(TRACE_ON(region
))
1285 REGION_DumpRegion(src2Obj
);
1289 if (REGION_IntersectRegion( destObj
, src1Obj
, src2Obj
))
1290 result
= get_region_type( destObj
);
1293 if (REGION_UnionRegion( destObj
, src1Obj
, src2Obj
))
1294 result
= get_region_type( destObj
);
1297 if (REGION_XorRegion( destObj
, src1Obj
, src2Obj
))
1298 result
= get_region_type( destObj
);
1301 if (REGION_SubtractRegion( destObj
, src1Obj
, src2Obj
))
1302 result
= get_region_type( destObj
);
1305 GDI_ReleaseObj( hSrc2
);
1308 GDI_ReleaseObj( hSrc1
);
1310 TRACE("dump destObj:\n");
1311 if(TRACE_ON(region
))
1312 REGION_DumpRegion(destObj
);
1314 GDI_ReleaseObj( hDest
);
1319 /***********************************************************************
1321 * Re-calculate the extents of a region
1323 static void REGION_SetExtents (WINEREGION
*pReg
)
1325 RECT
*pRect
, *pRectEnd
, *pExtents
;
1327 if (pReg
->numRects
== 0)
1329 pReg
->extents
.left
= 0;
1330 pReg
->extents
.top
= 0;
1331 pReg
->extents
.right
= 0;
1332 pReg
->extents
.bottom
= 0;
1336 pExtents
= &pReg
->extents
;
1337 pRect
= pReg
->rects
;
1338 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1341 * Since pRect is the first rectangle in the region, it must have the
1342 * smallest top and since pRectEnd is the last rectangle in the region,
1343 * it must have the largest bottom, because of banding. Initialize left and
1344 * right from pRect and pRectEnd, resp., as good things to initialize them
1347 pExtents
->left
= pRect
->left
;
1348 pExtents
->top
= pRect
->top
;
1349 pExtents
->right
= pRectEnd
->right
;
1350 pExtents
->bottom
= pRectEnd
->bottom
;
1352 while (pRect
<= pRectEnd
)
1354 if (pRect
->left
< pExtents
->left
)
1355 pExtents
->left
= pRect
->left
;
1356 if (pRect
->right
> pExtents
->right
)
1357 pExtents
->right
= pRect
->right
;
1362 /***********************************************************************
1365 static BOOL
REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1367 if (dst
!= src
) /* don't want to copy to itself */
1369 if (dst
->size
< src
->numRects
)
1371 RECT
*rects
= HeapReAlloc( GetProcessHeap(), 0, dst
->rects
, src
->numRects
* sizeof(RECT
) );
1372 if (!rects
) return FALSE
;
1374 dst
->size
= src
->numRects
;
1376 dst
->numRects
= src
->numRects
;
1377 dst
->extents
.left
= src
->extents
.left
;
1378 dst
->extents
.top
= src
->extents
.top
;
1379 dst
->extents
.right
= src
->extents
.right
;
1380 dst
->extents
.bottom
= src
->extents
.bottom
;
1381 memcpy(dst
->rects
, src
->rects
, src
->numRects
* sizeof(RECT
));
1386 /***********************************************************************
1387 * REGION_MirrorRegion
1389 static BOOL
REGION_MirrorRegion( WINEREGION
*dst
, WINEREGION
*src
, int width
)
1393 RECT
*rects
= HeapAlloc( GetProcessHeap(), 0, src
->numRects
* sizeof(RECT
) );
1395 if (!rects
) return FALSE
;
1397 extents
.left
= width
- src
->extents
.right
;
1398 extents
.right
= width
- src
->extents
.left
;
1399 extents
.top
= src
->extents
.top
;
1400 extents
.bottom
= src
->extents
.bottom
;
1402 for (start
= 0; start
< src
->numRects
; start
= end
)
1404 /* find the end of the current band */
1405 for (end
= start
+ 1; end
< src
->numRects
; end
++)
1406 if (src
->rects
[end
].top
!= src
->rects
[end
- 1].top
) break;
1408 for (i
= 0; i
< end
- start
; i
++)
1410 rects
[start
+ i
].left
= width
- src
->rects
[end
- i
- 1].right
;
1411 rects
[start
+ i
].right
= width
- src
->rects
[end
- i
- 1].left
;
1412 rects
[start
+ i
].top
= src
->rects
[end
- i
- 1].top
;
1413 rects
[start
+ i
].bottom
= src
->rects
[end
- i
- 1].bottom
;
1417 HeapFree( GetProcessHeap(), 0, dst
->rects
);
1419 dst
->size
= src
->numRects
;
1420 dst
->numRects
= src
->numRects
;
1421 dst
->extents
= extents
;
1425 /***********************************************************************
1428 INT
mirror_region( HRGN dst
, HRGN src
, INT width
)
1430 WINEREGION
*src_rgn
, *dst_rgn
;
1433 if (!(src_rgn
= GDI_GetObjPtr( src
, OBJ_REGION
))) return ERROR
;
1434 if ((dst_rgn
= GDI_GetObjPtr( dst
, OBJ_REGION
)))
1436 if (REGION_MirrorRegion( dst_rgn
, src_rgn
, width
)) ret
= get_region_type( dst_rgn
);
1437 GDI_ReleaseObj( dst_rgn
);
1439 GDI_ReleaseObj( src_rgn
);
1443 /***********************************************************************
1444 * MirrorRgn (GDI32.@)
1446 BOOL WINAPI
MirrorRgn( HWND hwnd
, HRGN hrgn
)
1448 static const WCHAR user32W
[] = {'u','s','e','r','3','2','.','d','l','l',0};
1449 static BOOL (WINAPI
*pGetWindowRect
)( HWND hwnd
, LPRECT rect
);
1452 /* yes, a HWND in gdi32, don't ask */
1453 if (!pGetWindowRect
)
1455 HMODULE user32
= GetModuleHandleW(user32W
);
1456 if (!user32
) return FALSE
;
1457 if (!(pGetWindowRect
= (void *)GetProcAddress( user32
, "GetWindowRect" ))) return FALSE
;
1459 pGetWindowRect( hwnd
, &rect
);
1460 return mirror_region( hrgn
, hrgn
, rect
.right
- rect
.left
) != ERROR
;
1464 /***********************************************************************
1467 * Attempt to merge the rects in the current band with those in the
1468 * previous one. Used only by REGION_RegionOp.
1471 * The new index for the previous band.
1474 * If coalescing takes place:
1475 * - rectangles in the previous band will have their bottom fields
1477 * - pReg->numRects will be decreased.
1480 static INT
REGION_Coalesce (
1481 WINEREGION
*pReg
, /* Region to coalesce */
1482 INT prevStart
, /* Index of start of previous band */
1483 INT curStart
/* Index of start of current band */
1485 RECT
*pPrevRect
; /* Current rect in previous band */
1486 RECT
*pCurRect
; /* Current rect in current band */
1487 RECT
*pRegEnd
; /* End of region */
1488 INT curNumRects
; /* Number of rectangles in current band */
1489 INT prevNumRects
; /* Number of rectangles in previous band */
1490 INT bandtop
; /* top coordinate for current band */
1492 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1494 pPrevRect
= &pReg
->rects
[prevStart
];
1495 prevNumRects
= curStart
- prevStart
;
1498 * Figure out how many rectangles are in the current band. Have to do
1499 * this because multiple bands could have been added in REGION_RegionOp
1500 * at the end when one region has been exhausted.
1502 pCurRect
= &pReg
->rects
[curStart
];
1503 bandtop
= pCurRect
->top
;
1504 for (curNumRects
= 0;
1505 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1511 if (pCurRect
!= pRegEnd
)
1514 * If more than one band was added, we have to find the start
1515 * of the last band added so the next coalescing job can start
1516 * at the right place... (given when multiple bands are added,
1517 * this may be pointless -- see above).
1520 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1524 curStart
= pRegEnd
- pReg
->rects
;
1525 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1528 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1529 pCurRect
-= curNumRects
;
1531 * The bands may only be coalesced if the bottom of the previous
1532 * matches the top scanline of the current.
1534 if (pPrevRect
->bottom
== pCurRect
->top
)
1537 * Make sure the bands have rects in the same places. This
1538 * assumes that rects have been added in such a way that they
1539 * cover the most area possible. I.e. two rects in a band must
1540 * have some horizontal space between them.
1544 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1545 (pPrevRect
->right
!= pCurRect
->right
))
1548 * The bands don't line up so they can't be coalesced.
1555 } while (prevNumRects
!= 0);
1557 pReg
->numRects
-= curNumRects
;
1558 pCurRect
-= curNumRects
;
1559 pPrevRect
-= curNumRects
;
1562 * The bands may be merged, so set the bottom of each rect
1563 * in the previous band to that of the corresponding rect in
1568 pPrevRect
->bottom
= pCurRect
->bottom
;
1572 } while (curNumRects
!= 0);
1575 * If only one band was added to the region, we have to backup
1576 * curStart to the start of the previous band.
1578 * If more than one band was added to the region, copy the
1579 * other bands down. The assumption here is that the other bands
1580 * came from the same region as the current one and no further
1581 * coalescing can be done on them since it's all been done
1582 * already... curStart is already in the right place.
1584 if (pCurRect
== pRegEnd
)
1586 curStart
= prevStart
;
1592 *pPrevRect
++ = *pCurRect
++;
1593 } while (pCurRect
!= pRegEnd
);
1601 /***********************************************************************
1604 * Apply an operation to two regions. Called by REGION_Union,
1605 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1611 * The new region is overwritten.
1614 * The idea behind this function is to view the two regions as sets.
1615 * Together they cover a rectangle of area that this function divides
1616 * into horizontal bands where points are covered only by one region
1617 * or by both. For the first case, the nonOverlapFunc is called with
1618 * each the band and the band's upper and lower extents. For the
1619 * second, the overlapFunc is called to process the entire band. It
1620 * is responsible for clipping the rectangles in the band, though
1621 * this function provides the boundaries.
1622 * At the end of each band, the new region is coalesced, if possible,
1623 * to reduce the number of rectangles in the region.
1626 static BOOL
REGION_RegionOp(
1627 WINEREGION
*destReg
, /* Place to store result */
1628 WINEREGION
*reg1
, /* First region in operation */
1629 WINEREGION
*reg2
, /* 2nd region in operation */
1630 BOOL (*overlapFunc
)(WINEREGION
*, RECT
*, RECT
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for over-lapping bands */
1631 BOOL (*nonOverlap1Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
), /* Function to call for non-overlapping bands in region 1 */
1632 BOOL (*nonOverlap2Func
)(WINEREGION
*, RECT
*, RECT
*, INT
, INT
) /* Function to call for non-overlapping bands in region 2 */
1635 RECT
*r1
; /* Pointer into first region */
1636 RECT
*r2
; /* Pointer into 2d region */
1637 RECT
*r1End
; /* End of 1st region */
1638 RECT
*r2End
; /* End of 2d region */
1639 INT ybot
; /* Bottom of intersection */
1640 INT ytop
; /* Top of intersection */
1641 INT prevBand
; /* Index of start of
1642 * previous band in newReg */
1643 INT curBand
; /* Index of start of current
1645 RECT
*r1BandEnd
; /* End of current band in r1 */
1646 RECT
*r2BandEnd
; /* End of current band in r2 */
1647 INT top
; /* Top of non-overlapping band */
1648 INT bot
; /* Bottom of non-overlapping band */
1652 * set r1, r2, r1End and r2End appropriately, preserve the important
1653 * parts of the destination region until the end in case it's one of
1654 * the two source regions, then mark the "new" region empty, allocating
1655 * another array of rectangles for it to use.
1659 r1End
= r1
+ reg1
->numRects
;
1660 r2End
= r2
+ reg2
->numRects
;
1663 * Allocate a reasonable number of rectangles for the new region. The idea
1664 * is to allocate enough so the individual functions don't need to
1665 * reallocate and copy the array, which is time consuming, yet we don't
1666 * have to worry about using too much memory. I hope to be able to
1667 * nuke the Xrealloc() at the end of this function eventually.
1669 if (!init_region( &newReg
, max(reg1
->numRects
,reg2
->numRects
) * 2 )) return FALSE
;
1672 * Initialize ybot and ytop.
1673 * In the upcoming loop, ybot and ytop serve different functions depending
1674 * on whether the band being handled is an overlapping or non-overlapping
1676 * In the case of a non-overlapping band (only one of the regions
1677 * has points in the band), ybot is the bottom of the most recent
1678 * intersection and thus clips the top of the rectangles in that band.
1679 * ytop is the top of the next intersection between the two regions and
1680 * serves to clip the bottom of the rectangles in the current band.
1681 * For an overlapping band (where the two regions intersect), ytop clips
1682 * the top of the rectangles of both regions and ybot clips the bottoms.
1684 if (reg1
->extents
.top
< reg2
->extents
.top
)
1685 ybot
= reg1
->extents
.top
;
1687 ybot
= reg2
->extents
.top
;
1690 * prevBand serves to mark the start of the previous band so rectangles
1691 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1692 * In the beginning, there is no previous band, so prevBand == curBand
1693 * (curBand is set later on, of course, but the first band will always
1694 * start at index 0). prevBand and curBand must be indices because of
1695 * the possible expansion, and resultant moving, of the new region's
1696 * array of rectangles.
1702 curBand
= newReg
.numRects
;
1705 * This algorithm proceeds one source-band (as opposed to a
1706 * destination band, which is determined by where the two regions
1707 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1708 * rectangle after the last one in the current band for their
1709 * respective regions.
1712 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1718 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1724 * First handle the band that doesn't intersect, if any.
1726 * Note that attention is restricted to one band in the
1727 * non-intersecting region at once, so if a region has n
1728 * bands between the current position and the next place it overlaps
1729 * the other, this entire loop will be passed through n times.
1731 if (r1
->top
< r2
->top
)
1733 top
= max(r1
->top
,ybot
);
1734 bot
= min(r1
->bottom
,r2
->top
);
1736 if ((top
!= bot
) && (nonOverlap1Func
!= NULL
))
1738 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, top
, bot
)) return FALSE
;
1743 else if (r2
->top
< r1
->top
)
1745 top
= max(r2
->top
,ybot
);
1746 bot
= min(r2
->bottom
,r1
->top
);
1748 if ((top
!= bot
) && (nonOverlap2Func
!= NULL
))
1750 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, top
, bot
)) return FALSE
;
1761 * If any rectangles got added to the region, try and coalesce them
1762 * with rectangles from the previous band. Note we could just do
1763 * this test in miCoalesce, but some machines incur a not
1764 * inconsiderable cost for function calls, so...
1766 if (newReg
.numRects
!= curBand
)
1768 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1772 * Now see if we've hit an intersecting band. The two bands only
1773 * intersect if ybot > ytop
1775 ybot
= min(r1
->bottom
, r2
->bottom
);
1776 curBand
= newReg
.numRects
;
1779 if (!overlapFunc(&newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
)) return FALSE
;
1782 if (newReg
.numRects
!= curBand
)
1784 prevBand
= REGION_Coalesce (&newReg
, prevBand
, curBand
);
1788 * If we've finished with a band (bottom == ybot) we skip forward
1789 * in the region to the next band.
1791 if (r1
->bottom
== ybot
)
1795 if (r2
->bottom
== ybot
)
1799 } while ((r1
!= r1End
) && (r2
!= r2End
));
1802 * Deal with whichever region still has rectangles left.
1804 curBand
= newReg
.numRects
;
1807 if (nonOverlap1Func
!= NULL
)
1812 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1816 if (!nonOverlap1Func(&newReg
, r1
, r1BandEnd
, max(r1
->top
,ybot
), r1
->bottom
))
1819 } while (r1
!= r1End
);
1822 else if ((r2
!= r2End
) && (nonOverlap2Func
!= NULL
))
1827 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1831 if (!nonOverlap2Func(&newReg
, r2
, r2BandEnd
, max(r2
->top
,ybot
), r2
->bottom
))
1834 } while (r2
!= r2End
);
1837 if (newReg
.numRects
!= curBand
)
1839 REGION_Coalesce (&newReg
, prevBand
, curBand
);
1843 * A bit of cleanup. To keep regions from growing without bound,
1844 * we shrink the array of rectangles to match the new number of
1845 * rectangles in the region. This never goes to 0, however...
1847 * Only do this stuff if the number of rectangles allocated is more than
1848 * twice the number of rectangles in the region (a simple optimization...).
1850 if ((newReg
.numRects
< (newReg
.size
>> 1)) && (newReg
.numRects
> 2))
1852 RECT
*new_rects
= HeapReAlloc( GetProcessHeap(), 0, newReg
.rects
, newReg
.numRects
* sizeof(RECT
) );
1855 newReg
.rects
= new_rects
;
1856 newReg
.size
= newReg
.numRects
;
1859 HeapFree( GetProcessHeap(), 0, destReg
->rects
);
1860 destReg
->rects
= newReg
.rects
;
1861 destReg
->size
= newReg
.size
;
1862 destReg
->numRects
= newReg
.numRects
;
1866 /***********************************************************************
1867 * Region Intersection
1868 ***********************************************************************/
1871 /***********************************************************************
1874 * Handle an overlapping band for REGION_Intersect.
1880 * Rectangles may be added to the region.
1883 static BOOL
REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1884 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1889 while ((r1
!= r1End
) && (r2
!= r2End
))
1891 left
= max(r1
->left
, r2
->left
);
1892 right
= min(r1
->right
, r2
->right
);
1895 * If there's any overlap between the two rectangles, add that
1896 * overlap to the new region.
1897 * There's no need to check for subsumption because the only way
1898 * such a need could arise is if some region has two rectangles
1899 * right next to each other. Since that should never happen...
1903 if (!add_rect( pReg
, left
, top
, right
, bottom
)) return FALSE
;
1907 * Need to advance the pointers. Shift the one that extends
1908 * to the right the least, since the other still has a chance to
1909 * overlap with that region's next rectangle, if you see what I mean.
1911 if (r1
->right
< r2
->right
)
1915 else if (r2
->right
< r1
->right
)
1928 /***********************************************************************
1929 * REGION_IntersectRegion
1931 static BOOL
REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1934 /* check for trivial reject */
1935 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1936 (!overlapping(®1
->extents
, ®2
->extents
)))
1937 newReg
->numRects
= 0;
1939 if (!REGION_RegionOp (newReg
, reg1
, reg2
, REGION_IntersectO
, NULL
, NULL
)) return FALSE
;
1942 * Can't alter newReg's extents before we call miRegionOp because
1943 * it might be one of the source regions and miRegionOp depends
1944 * on the extents of those regions being the same. Besides, this
1945 * way there's no checking against rectangles that will be nuked
1946 * due to coalescing, so we have to examine fewer rectangles.
1948 REGION_SetExtents(newReg
);
1952 /***********************************************************************
1954 ***********************************************************************/
1956 /***********************************************************************
1959 * Handle a non-overlapping band for the union operation. Just
1960 * Adds the rectangles into the region. Doesn't have to check for
1961 * subsumption or anything.
1967 * pReg->numRects is incremented and the final rectangles overwritten
1968 * with the rectangles we're passed.
1971 static BOOL
REGION_UnionNonO(WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
1975 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
1981 /***********************************************************************
1984 * Handle an overlapping band for the union operation. Picks the
1985 * left-most rectangle each time and merges it into the region.
1991 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1995 static BOOL
REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1996 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1998 #define MERGERECT(r) \
1999 if ((pReg->numRects != 0) && \
2000 (pReg->rects[pReg->numRects-1].top == top) && \
2001 (pReg->rects[pReg->numRects-1].bottom == bottom) && \
2002 (pReg->rects[pReg->numRects-1].right >= r->left)) \
2004 if (pReg->rects[pReg->numRects-1].right < r->right) \
2005 pReg->rects[pReg->numRects-1].right = r->right; \
2009 if (!add_rect( pReg, r->left, top, r->right, bottom )) return FALSE; \
2013 while ((r1
!= r1End
) && (r2
!= r2End
))
2015 if (r1
->left
< r2
->left
)
2030 } while (r1
!= r1End
);
2032 else while (r2
!= r2End
)
2040 /***********************************************************************
2041 * REGION_UnionRegion
2043 static BOOL
REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
, WINEREGION
*reg2
)
2047 /* checks all the simple cases */
2050 * Region 1 and 2 are the same or region 1 is empty
2052 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
2055 ret
= REGION_CopyRegion(newReg
, reg2
);
2060 * if nothing to union (region 2 empty)
2062 if (!(reg2
->numRects
))
2065 ret
= REGION_CopyRegion(newReg
, reg1
);
2070 * Region 1 completely subsumes region 2
2072 if ((reg1
->numRects
== 1) &&
2073 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
2074 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
2075 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
2076 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
2079 ret
= REGION_CopyRegion(newReg
, reg1
);
2084 * Region 2 completely subsumes region 1
2086 if ((reg2
->numRects
== 1) &&
2087 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
2088 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
2089 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
2090 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
2093 ret
= REGION_CopyRegion(newReg
, reg2
);
2097 if ((ret
= REGION_RegionOp (newReg
, reg1
, reg2
, REGION_UnionO
, REGION_UnionNonO
, REGION_UnionNonO
)))
2099 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
2100 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
2101 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
2102 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
2107 /***********************************************************************
2108 * Region Subtraction
2109 ***********************************************************************/
2111 /***********************************************************************
2112 * REGION_SubtractNonO1
2114 * Deal with non-overlapping band for subtraction. Any parts from
2115 * region 2 we discard. Anything from region 1 we add to the region.
2121 * pReg may be affected.
2124 static BOOL
REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
, INT top
, INT bottom
)
2128 if (!add_rect( pReg
, r
->left
, top
, r
->right
, bottom
)) return FALSE
;
2135 /***********************************************************************
2138 * Overlapping band subtraction. x1 is the left-most point not yet
2145 * pReg may have rectangles added to it.
2148 static BOOL
REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2149 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2151 INT left
= r1
->left
;
2153 while ((r1
!= r1End
) && (r2
!= r2End
))
2155 if (r2
->right
<= left
)
2158 * Subtrahend missed the boat: go to next subtrahend.
2162 else if (r2
->left
<= left
)
2165 * Subtrahend precedes minuend: nuke left edge of minuend.
2168 if (left
>= r1
->right
)
2171 * Minuend completely covered: advance to next minuend and
2172 * reset left fence to edge of new minuend.
2181 * Subtrahend now used up since it doesn't extend beyond
2187 else if (r2
->left
< r1
->right
)
2190 * Left part of subtrahend covers part of minuend: add uncovered
2191 * part of minuend to region and skip to next subtrahend.
2193 if (!add_rect( pReg
, left
, top
, r2
->left
, bottom
)) return FALSE
;
2195 if (left
>= r1
->right
)
2198 * Minuend used up: advance to new...
2207 * Subtrahend used up
2215 * Minuend used up: add any remaining piece before advancing.
2217 if (r1
->right
> left
)
2219 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2228 * Add remaining minuend rectangles to region.
2232 if (!add_rect( pReg
, left
, top
, r1
->right
, bottom
)) return FALSE
;
2242 /***********************************************************************
2243 * REGION_SubtractRegion
2245 * Subtract regS from regM and leave the result in regD.
2246 * S stands for subtrahend, M for minuend and D for difference.
2252 * regD is overwritten.
2255 static BOOL
REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
, WINEREGION
*regS
)
2257 /* check for trivial reject */
2258 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2259 (!overlapping(®M
->extents
, ®S
->extents
)) )
2260 return REGION_CopyRegion(regD
, regM
);
2262 if (!REGION_RegionOp (regD
, regM
, regS
, REGION_SubtractO
, REGION_SubtractNonO1
, NULL
))
2266 * Can't alter newReg's extents before we call miRegionOp because
2267 * it might be one of the source regions and miRegionOp depends
2268 * on the extents of those regions being the unaltered. Besides, this
2269 * way there's no checking against rectangles that will be nuked
2270 * due to coalescing, so we have to examine fewer rectangles.
2272 REGION_SetExtents (regD
);
2276 /***********************************************************************
2279 static BOOL
REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
, WINEREGION
*srb
)
2281 WINEREGION tra
, trb
;
2284 if (!init_region( &tra
, sra
->numRects
+ 1 )) return FALSE
;
2285 if ((ret
= init_region( &trb
, srb
->numRects
+ 1 )))
2287 ret
= REGION_SubtractRegion(&tra
,sra
,srb
) &&
2288 REGION_SubtractRegion(&trb
,srb
,sra
) &&
2289 REGION_UnionRegion(dr
,&tra
,&trb
);
2290 destroy_region(&trb
);
2292 destroy_region(&tra
);
2296 /**************************************************************************
2300 *************************************************************************/
2302 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2303 #define SMALL_COORDINATE 0x80000000
2305 /***********************************************************************
2306 * REGION_InsertEdgeInET
2308 * Insert the given edge into the edge table.
2309 * First we must find the correct bucket in the
2310 * Edge table, then find the right slot in the
2311 * bucket. Finally, we can insert it.
2314 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2315 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2319 ScanLineList
*pSLL
, *pPrevSLL
;
2320 ScanLineListBlock
*tmpSLLBlock
;
2323 * find the right bucket to put the edge into
2325 pPrevSLL
= &ET
->scanlines
;
2326 pSLL
= pPrevSLL
->next
;
2327 while (pSLL
&& (pSLL
->scanline
< scanline
))
2334 * reassign pSLL (pointer to ScanLineList) if necessary
2336 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2338 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2340 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2343 WARN("Can't alloc SLLB\n");
2346 (*SLLBlock
)->next
= tmpSLLBlock
;
2347 tmpSLLBlock
->next
= NULL
;
2348 *SLLBlock
= tmpSLLBlock
;
2351 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2353 pSLL
->next
= pPrevSLL
->next
;
2354 list_init( &pSLL
->edgelist
);
2355 pPrevSLL
->next
= pSLL
;
2357 pSLL
->scanline
= scanline
;
2360 * now insert the edge in the right bucket
2362 LIST_FOR_EACH( ptr
, &pSLL
->edgelist
)
2364 struct edge_table_entry
*entry
= LIST_ENTRY( ptr
, struct edge_table_entry
, entry
);
2365 if (entry
->bres
.minor_axis
>= ETE
->bres
.minor_axis
) break;
2367 list_add_before( ptr
, &ETE
->entry
);
2370 /***********************************************************************
2371 * REGION_CreateEdgeTable
2373 * This routine creates the edge table for
2374 * scan converting polygons.
2375 * The Edge Table (ET) looks like:
2379 * | ymax | ScanLineLists
2380 * |scanline|-->------------>-------------->...
2381 * -------- |scanline| |scanline|
2382 * |edgelist| |edgelist|
2383 * --------- ---------
2387 * list of ETEs list of ETEs
2389 * where ETE is an EdgeTableEntry data structure,
2390 * and there is one ScanLineList per scanline at
2391 * which an edge is initially entered.
2394 static void REGION_CreateEdgeTable(const INT
*Count
, INT nbpolygons
,
2395 const POINT
*pts
, EdgeTable
*ET
,
2396 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2398 const POINT
*top
, *bottom
;
2399 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2405 * initialize the Edge Table.
2407 ET
->scanlines
.next
= NULL
;
2408 ET
->ymax
= SMALL_COORDINATE
;
2409 ET
->ymin
= LARGE_COORDINATE
;
2410 pSLLBlock
->next
= NULL
;
2413 for(poly
= 0; poly
< nbpolygons
; poly
++)
2415 count
= Count
[poly
];
2423 * for each vertex in the array of points.
2424 * In this loop we are dealing with two vertices at
2425 * a time -- these make up one edge of the polygon.
2432 * find out which point is above and which is below.
2434 if (PrevPt
->y
> CurrPt
->y
)
2436 bottom
= PrevPt
, top
= CurrPt
;
2437 pETEs
->ClockWise
= 0;
2441 bottom
= CurrPt
, top
= PrevPt
;
2442 pETEs
->ClockWise
= 1;
2446 * don't add horizontal edges to the Edge table.
2448 if (bottom
->y
!= top
->y
)
2450 pETEs
->ymax
= bottom
->y
-1;
2451 /* -1 so we don't get last scanline */
2454 * initialize integer edge algorithm
2456 dy
= bottom
->y
- top
->y
;
2457 bres_init_polygon(dy
, top
->x
, bottom
->x
, &pETEs
->bres
);
2459 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2462 if (PrevPt
->y
> ET
->ymax
)
2463 ET
->ymax
= PrevPt
->y
;
2464 if (PrevPt
->y
< ET
->ymin
)
2465 ET
->ymin
= PrevPt
->y
;
2474 /***********************************************************************
2477 * This routine moves EdgeTableEntries from the
2478 * EdgeTable into the Active Edge Table,
2479 * leaving them sorted by smaller x coordinate.
2482 static void REGION_loadAET( struct list
*AET
, struct list
*ETEs
)
2484 struct edge_table_entry
*ptr
, *next
, *entry
;
2485 struct list
*active
;
2487 LIST_FOR_EACH_ENTRY_SAFE( ptr
, next
, ETEs
, struct edge_table_entry
, entry
)
2489 LIST_FOR_EACH( active
, AET
)
2491 entry
= LIST_ENTRY( active
, struct edge_table_entry
, entry
);
2492 if (entry
->bres
.minor_axis
>= ptr
->bres
.minor_axis
) break;
2494 list_remove( &ptr
->entry
);
2495 list_add_before( active
, &ptr
->entry
);
2499 /***********************************************************************
2500 * REGION_computeWAET
2502 * This routine links the AET by the
2503 * nextWETE (winding EdgeTableEntry) link for
2504 * use by the winding number rule. The final
2505 * Active Edge Table (AET) might look something
2509 * ---------- --------- ---------
2510 * |ymax | |ymax | |ymax |
2511 * | ... | |... | |... |
2512 * |next |->|next |->|next |->...
2513 * |nextWETE| |nextWETE| |nextWETE|
2514 * --------- --------- ^--------
2516 * V-------------------> V---> ...
2519 static void REGION_computeWAET( struct list
*AET
, struct list
*WETE
)
2521 struct edge_table_entry
*active
;
2526 LIST_FOR_EACH_ENTRY( active
, AET
, struct edge_table_entry
, entry
)
2528 if (active
->ClockWise
)
2533 if ((!inside
&& !isInside
) || (inside
&& isInside
))
2535 list_add_tail( WETE
, &active
->winding_entry
);
2541 /***********************************************************************
2542 * REGION_InsertionSort
2544 * Just a simple insertion sort to sort the Active Edge Table.
2547 static BOOL
REGION_InsertionSort( struct list
*AET
)
2549 struct edge_table_entry
*active
, *next
, *insert
;
2550 BOOL changed
= FALSE
;
2552 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, AET
, struct edge_table_entry
, entry
)
2554 LIST_FOR_EACH_ENTRY( insert
, AET
, struct edge_table_entry
, entry
)
2556 if (insert
== active
) break;
2557 if (insert
->bres
.minor_axis
> active
->bres
.minor_axis
) break;
2559 if (insert
== active
) continue;
2560 list_remove( &active
->entry
);
2561 list_add_before( &insert
->entry
, &active
->entry
);
2567 /***********************************************************************
2568 * REGION_FreeStorage
2572 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2574 ScanLineListBlock
*tmpSLLBlock
;
2578 tmpSLLBlock
= pSLLBlock
->next
;
2579 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2580 pSLLBlock
= tmpSLLBlock
;
2585 /***********************************************************************
2586 * REGION_PtsToRegion
2588 * Create an array of rectangles from a list of points.
2590 static BOOL
REGION_PtsToRegion( struct point_block
*FirstPtBlock
, WINEREGION
*reg
)
2594 struct point_block
*pb
;
2599 extents
= ®
->extents
;
2601 for (pb
= FirstPtBlock
, numRects
= 0; pb
; pb
= pb
->next
) numRects
+= pb
->count
;
2602 if (!init_region( reg
, numRects
)) return FALSE
;
2604 reg
->size
= numRects
;
2605 rects
= reg
->rects
- 1;
2607 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2609 for (pb
= FirstPtBlock
; pb
; pb
= pb
->next
)
2611 /* the loop uses 2 points per iteration */
2613 for (pts
= pb
->pts
; i
--; pts
+= 2) {
2614 if (pts
->x
== pts
[1].x
)
2616 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2617 pts
[1].x
== rects
->right
&&
2618 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2619 (i
&& pts
[2].y
> pts
[1].y
)) {
2620 rects
->bottom
= pts
[1].y
+ 1;
2625 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2626 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2627 if (rects
->left
< extents
->left
)
2628 extents
->left
= rects
->left
;
2629 if (rects
->right
> extents
->right
)
2630 extents
->right
= rects
->right
;
2635 extents
->top
= reg
->rects
->top
;
2636 extents
->bottom
= rects
->bottom
;
2641 extents
->bottom
= 0;
2643 reg
->numRects
= numRects
;
2648 /***********************************************************************
2649 * CreatePolyPolygonRgn (GDI32.@)
2651 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2652 INT nbpolygons
, INT mode
)
2656 INT y
; /* current scanline */
2657 struct list WETE
, *pWETE
; /* Winding Edge Table */
2658 ScanLineList
*pSLL
; /* current scanLineList */
2659 EdgeTable ET
; /* header node for ET */
2660 struct list AET
; /* header for AET */
2661 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2662 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2663 BOOL fixWAET
= FALSE
;
2664 struct point_block FirstPtBlock
, *block
; /* PtBlock buffers */
2665 struct edge_table_entry
*active
, *next
;
2668 TRACE("%p, count %d, polygons %d, mode %d\n", Pts
, *Count
, nbpolygons
, mode
);
2670 /* special case a rectangle */
2672 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2673 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2674 (((Pts
[0].y
== Pts
[1].y
) &&
2675 (Pts
[1].x
== Pts
[2].x
) &&
2676 (Pts
[2].y
== Pts
[3].y
) &&
2677 (Pts
[3].x
== Pts
[0].x
)) ||
2678 ((Pts
[0].x
== Pts
[1].x
) &&
2679 (Pts
[1].y
== Pts
[2].y
) &&
2680 (Pts
[2].x
== Pts
[3].x
) &&
2681 (Pts
[3].y
== Pts
[0].y
))))
2682 return CreateRectRgn( min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2683 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2685 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2686 total
+= Count
[poly
];
2687 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2690 REGION_CreateEdgeTable(Count
, nbpolygons
, Pts
, &ET
, pETEs
, &SLLBlock
);
2692 pSLL
= ET
.scanlines
.next
;
2693 block
= &FirstPtBlock
;
2694 FirstPtBlock
.count
= 0;
2695 FirstPtBlock
.next
= NULL
;
2697 if (mode
!= WINDING
) {
2701 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2703 * Add a new edge to the active edge table when we
2704 * get to the next edge.
2706 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2707 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2711 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, &AET
, struct edge_table_entry
, entry
)
2713 block
= add_point( block
, active
->bres
.minor_axis
, y
);
2714 if (!block
) goto done
;
2716 if (active
->ymax
== y
) /* leaving this edge */
2717 list_remove( &active
->entry
);
2719 bres_incr_polygon( &active
->bres
);
2721 REGION_InsertionSort(&AET
);
2728 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2730 * Add a new edge to the active edge table when we
2731 * get to the next edge.
2733 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2734 REGION_loadAET(&AET
, &pSLL
->edgelist
);
2735 REGION_computeWAET( &AET
, &WETE
);
2738 pWETE
= list_head( &WETE
);
2741 * for each active edge
2743 LIST_FOR_EACH_ENTRY_SAFE( active
, next
, &AET
, struct edge_table_entry
, entry
)
2746 * add to the buffer only those edges that
2747 * are in the Winding active edge table.
2749 if (pWETE
== &active
->winding_entry
) {
2750 block
= add_point( block
, active
->bres
.minor_axis
, y
);
2751 if (!block
) goto done
;
2752 pWETE
= list_next( &WETE
, pWETE
);
2754 if (active
->ymax
== y
) /* leaving this edge */
2756 list_remove( &active
->entry
);
2760 bres_incr_polygon( &active
->bres
);
2764 * recompute the winding active edge table if
2765 * we just resorted or have exited an edge.
2767 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2768 REGION_computeWAET( &AET
, &WETE
);
2774 if (!(obj
= HeapAlloc( GetProcessHeap(), 0, sizeof(*obj
) ))) goto done
;
2776 if (!REGION_PtsToRegion(&FirstPtBlock
, obj
))
2778 HeapFree( GetProcessHeap(), 0, obj
);
2781 if (!(hrgn
= alloc_gdi_handle( obj
, OBJ_REGION
, ®ion_funcs
)))
2783 HeapFree( GetProcessHeap(), 0, obj
->rects
);
2784 HeapFree( GetProcessHeap(), 0, obj
);
2788 REGION_FreeStorage(SLLBlock
.next
);
2789 free_point_blocks( FirstPtBlock
.next
);
2790 HeapFree( GetProcessHeap(), 0, pETEs
);
2795 /***********************************************************************
2796 * CreatePolygonRgn (GDI32.@)
2798 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2801 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);