2 * GDI region objects. Shamelessly ripped out from the X11 distribution
3 * Thanks for the nice licence.
5 * Copyright 1993, 1994, 1995 Alexandre Julliard
6 * Modifications and additions: Copyright 1998 Huw Davies
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 /************************************************************************
26 Copyright (c) 1987, 1988 X Consortium
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
70 ************************************************************************/
72 * The functions in this file implement the Region abstraction, similar to one
73 * used in the X11 sample server. A Region is simply an area, as the name
74 * implies, and is implemented as a "y-x-banded" array of rectangles. To
75 * explain: Each Region is made up of a certain number of rectangles sorted
76 * by y coordinate first, and then by x coordinate.
78 * Furthermore, the rectangles are banded such that every rectangle with a
79 * given upper-left y coordinate (y1) will have the same lower-right y
80 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81 * will span the entire vertical distance of the band. This means that some
82 * areas that could be merged into a taller rectangle will be represented as
83 * several shorter rectangles to account for shorter rectangles to its left
84 * or right but within its "vertical scope".
86 * An added constraint on the rectangles is that they must cover as much
87 * horizontal area as possible. E.g. no two rectangles in a band are allowed
90 * Whenever possible, bands will be merged together to cover a greater vertical
91 * distance (and thus reduce the number of rectangles). Two bands can be merged
92 * only if the bottom of one touches the top of the other and they have
93 * rectangles in the same places (of the same width, of course). This maintains
94 * the y-x-banding that's so nice to have...
104 #include "gdi_private.h"
105 #include "wine/debug.h"
107 WINE_DEFAULT_DEBUG_CHANNEL(region
);
116 /* GDI logical region object */
124 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, void *obj
, HDC hdc
);
125 static BOOL
REGION_DeleteObject( HGDIOBJ handle
, void *obj
);
127 static const struct gdi_obj_funcs region_funcs
=
129 REGION_SelectObject
, /* pSelectObject */
130 NULL
, /* pGetObject16 */
131 NULL
, /* pGetObjectA */
132 NULL
, /* pGetObjectW */
133 NULL
, /* pUnrealizeObject */
134 REGION_DeleteObject
/* pDeleteObject */
137 /* 1 if two RECTs overlap.
138 * 0 if two RECTs do not overlap.
140 #define EXTENTCHECK(r1, r2) \
141 ((r1)->right > (r2)->left && \
142 (r1)->left < (r2)->right && \
143 (r1)->bottom > (r2)->top && \
144 (r1)->top < (r2)->bottom)
147 * Check to see if there is enough memory in the present region.
150 static inline int xmemcheck(WINEREGION
*reg
, LPRECT
*rect
, LPRECT
*firstrect
) {
151 if (reg
->numRects
>= (reg
->size
- 1)) {
152 *firstrect
= HeapReAlloc( GetProcessHeap(), 0, *firstrect
, (2 * (sizeof(RECT
)) * (reg
->size
)));
156 *rect
= (*firstrect
)+reg
->numRects
;
161 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
163 #define EMPTY_REGION(pReg) { \
164 (pReg)->numRects = 0; \
165 (pReg)->extents.left = (pReg)->extents.top = 0; \
166 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
169 #define REGION_NOT_EMPTY(pReg) pReg->numRects
171 #define INRECT(r, x, y) \
172 ( ( ((r).right > x)) && \
173 ( ((r).left <= x)) && \
174 ( ((r).bottom > y)) && \
179 * number of points to buffer before sending them off
180 * to scanlines() : Must be an even number
182 #define NUMPTSTOBUFFER 200
185 * used to allocate buffers for points and link
186 * the buffers together
189 typedef struct _POINTBLOCK
{
190 POINT pts
[NUMPTSTOBUFFER
];
191 struct _POINTBLOCK
*next
;
197 * This file contains a few macros to help track
198 * the edge of a filled object. The object is assumed
199 * to be filled in scanline order, and thus the
200 * algorithm used is an extension of Bresenham's line
201 * drawing algorithm which assumes that y is always the
203 * Since these pieces of code are the same for any filled shape,
204 * it is more convenient to gather the library in one
205 * place, but since these pieces of code are also in
206 * the inner loops of output primitives, procedure call
207 * overhead is out of the question.
208 * See the author for a derivation if needed.
213 * In scan converting polygons, we want to choose those pixels
214 * which are inside the polygon. Thus, we add .5 to the starting
215 * x coordinate for both left and right edges. Now we choose the
216 * first pixel which is inside the pgon for the left edge and the
217 * first pixel which is outside the pgon for the right edge.
218 * Draw the left pixel, but not the right.
220 * How to add .5 to the starting x coordinate:
221 * If the edge is moving to the right, then subtract dy from the
222 * error term from the general form of the algorithm.
223 * If the edge is moving to the left, then add dy to the error term.
225 * The reason for the difference between edges moving to the left
226 * and edges moving to the right is simple: If an edge is moving
227 * to the right, then we want the algorithm to flip immediately.
228 * If it is moving to the left, then we don't want it to flip until
229 * we traverse an entire pixel.
231 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
232 int dx; /* local storage */ \
235 * if the edge is horizontal, then it is ignored \
236 * and assumed not to be processed. Otherwise, do this stuff. \
240 dx = (x2) - xStart; \
244 incr1 = -2 * dx + 2 * (dy) * m1; \
245 incr2 = -2 * dx + 2 * (dy) * m; \
246 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
250 incr1 = 2 * dx - 2 * (dy) * m1; \
251 incr2 = 2 * dx - 2 * (dy) * m; \
252 d = -2 * m * (dy) + 2 * dx; \
257 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
280 * This structure contains all of the information needed
281 * to run the bresenham algorithm.
282 * The variables may be hardcoded into the declarations
283 * instead of using this structure to make use of
284 * register declarations.
287 INT minor_axis
; /* minor axis */
288 INT d
; /* decision variable */
289 INT m
, m1
; /* slope and slope+1 */
290 INT incr1
, incr2
; /* error increments */
294 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
295 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
296 bres.m, bres.m1, bres.incr1, bres.incr2)
298 #define BRESINCRPGONSTRUCT(bres) \
299 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
304 * These are the data structures needed to scan
305 * convert regions. Two different scan conversion
306 * methods are available -- the even-odd method, and
307 * the winding number method.
308 * The even-odd rule states that a point is inside
309 * the polygon if a ray drawn from that point in any
310 * direction will pass through an odd number of
312 * By the winding number rule, a point is decided
313 * to be inside the polygon if a ray drawn from that
314 * point in any direction passes through a different
315 * number of clockwise and counter-clockwise path
318 * These data structures are adapted somewhat from
319 * the algorithm in (Foley/Van Dam) for scan converting
321 * The basic algorithm is to start at the top (smallest y)
322 * of the polygon, stepping down to the bottom of
323 * the polygon by incrementing the y coordinate. We
324 * keep a list of edges which the current scanline crosses,
325 * sorted by x. This list is called the Active Edge Table (AET)
326 * As we change the y-coordinate, we update each entry in
327 * in the active edge table to reflect the edges new xcoord.
328 * This list must be sorted at each scanline in case
329 * two edges intersect.
330 * We also keep a data structure known as the Edge Table (ET),
331 * which keeps track of all the edges which the current
332 * scanline has not yet reached. The ET is basically a
333 * list of ScanLineList structures containing a list of
334 * edges which are entered at a given scanline. There is one
335 * ScanLineList per scanline at which an edge is entered.
336 * When we enter a new edge, we move it from the ET to the AET.
338 * From the AET, we can implement the even-odd rule as in
340 * The winding number rule is a little trickier. We also
341 * keep the EdgeTableEntries in the AET linked by the
342 * nextWETE (winding EdgeTableEntry) link. This allows
343 * the edges to be linked just as before for updating
344 * purposes, but only uses the edges linked by the nextWETE
345 * link as edges representing spans of the polygon to
346 * drawn (as with the even-odd rule).
350 * for the winding number rule
353 #define COUNTERCLOCKWISE -1
355 typedef struct _EdgeTableEntry
{
356 INT ymax
; /* ycoord at which we exit this edge. */
357 BRESINFO bres
; /* Bresenham info to run the edge */
358 struct _EdgeTableEntry
*next
; /* next in the list */
359 struct _EdgeTableEntry
*back
; /* for insertion sort */
360 struct _EdgeTableEntry
*nextWETE
; /* for winding num rule */
361 int ClockWise
; /* flag for winding number rule */
365 typedef struct _ScanLineList
{
366 INT scanline
; /* the scanline represented */
367 EdgeTableEntry
*edgelist
; /* header node */
368 struct _ScanLineList
*next
; /* next in the list */
373 INT ymax
; /* ymax for the polygon */
374 INT ymin
; /* ymin for the polygon */
375 ScanLineList scanlines
; /* header node */
380 * Here is a struct to help with storage allocation
381 * so we can allocate a big chunk at a time, and then take
382 * pieces from this heap when we need to.
384 #define SLLSPERBLOCK 25
386 typedef struct _ScanLineListBlock
{
387 ScanLineList SLLs
[SLLSPERBLOCK
];
388 struct _ScanLineListBlock
*next
;
394 * a few macros for the inner loops of the fill code where
395 * performance considerations don't allow a procedure call.
397 * Evaluate the given edge at the given scanline.
398 * If the edge has expired, then we leave it and fix up
399 * the active edge table; otherwise, we increment the
400 * x value to be ready for the next scanline.
401 * The winding number rule is in effect, so we must notify
402 * the caller when the edge has been removed so he
403 * can reorder the Winding Active Edge Table.
405 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
406 if (pAET->ymax == y) { /* leaving this edge */ \
407 pPrevAET->next = pAET->next; \
408 pAET = pPrevAET->next; \
411 pAET->back = pPrevAET; \
414 BRESINCRPGONSTRUCT(pAET->bres); \
422 * Evaluate the given edge at the given scanline.
423 * If the edge has expired, then we leave it and fix up
424 * the active edge table; otherwise, we increment the
425 * x value to be ready for the next scanline.
426 * The even-odd rule is in effect.
428 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
429 if (pAET->ymax == y) { /* leaving this edge */ \
430 pPrevAET->next = pAET->next; \
431 pAET = pPrevAET->next; \
433 pAET->back = pPrevAET; \
436 BRESINCRPGONSTRUCT(pAET->bres); \
442 typedef void (*voidProcp
)();
444 /* Note the parameter order is different from the X11 equivalents */
446 static void REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
447 static void REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
448 static void REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
449 static void REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
450 static void REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
451 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
453 #define RGN_DEFAULT_RECTS 2
456 /***********************************************************************
459 inline static INT
get_region_type( const RGNOBJ
*obj
)
461 switch(obj
->rgn
->numRects
)
463 case 0: return NULLREGION
;
464 case 1: return SIMPLEREGION
;
465 default: return COMPLEXREGION
;
470 /***********************************************************************
472 * Outputs the contents of a WINEREGION
474 static void REGION_DumpRegion(WINEREGION
*pReg
)
476 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
478 TRACE("Region %p: %ld,%ld - %ld,%ld %d rects\n", pReg
,
479 pReg
->extents
.left
, pReg
->extents
.top
,
480 pReg
->extents
.right
, pReg
->extents
.bottom
, pReg
->numRects
);
481 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
482 TRACE("\t%ld,%ld - %ld,%ld\n", pRect
->left
, pRect
->top
,
483 pRect
->right
, pRect
->bottom
);
488 /***********************************************************************
489 * REGION_AllocWineRegion
490 * Create a new empty WINEREGION.
492 static WINEREGION
*REGION_AllocWineRegion( INT n
)
496 if ((pReg
= HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION
))))
498 if ((pReg
->rects
= HeapAlloc(GetProcessHeap(), 0, n
* sizeof( RECT
))))
504 HeapFree(GetProcessHeap(), 0, pReg
);
510 /***********************************************************************
511 * REGION_CreateRegion
512 * Create a new empty region.
514 static HRGN
REGION_CreateRegion( INT n
)
519 if(!(obj
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
, (HGDIOBJ
*)&hrgn
,
520 ®ion_funcs
))) return 0;
521 if(!(obj
->rgn
= REGION_AllocWineRegion(n
))) {
522 GDI_FreeObject( hrgn
, obj
);
525 GDI_ReleaseObj( hrgn
);
529 /***********************************************************************
530 * REGION_DestroyWineRegion
532 static void REGION_DestroyWineRegion( WINEREGION
* pReg
)
534 HeapFree( GetProcessHeap(), 0, pReg
->rects
);
535 HeapFree( GetProcessHeap(), 0, pReg
);
538 /***********************************************************************
539 * REGION_DeleteObject
541 static BOOL
REGION_DeleteObject( HGDIOBJ handle
, void *obj
)
545 TRACE(" %p\n", handle
);
547 REGION_DestroyWineRegion( rgn
->rgn
);
548 return GDI_FreeObject( handle
, obj
);
551 /***********************************************************************
552 * REGION_SelectObject
554 static HGDIOBJ
REGION_SelectObject( HGDIOBJ handle
, void *obj
, HDC hdc
)
556 return (HGDIOBJ
)SelectClipRgn( hdc
, handle
);
560 /***********************************************************************
561 * OffsetRgn (GDI32.@)
563 * Moves a region by the specified X- and Y-axis offsets.
566 * hrgn [I] Region to offset.
567 * x [I] Offset right if positive or left if negative.
568 * y [I] Offset down if positive or up if negative.
572 * NULLREGION - The new region is empty.
573 * SIMPLEREGION - The new region can be represented by one rectangle.
574 * COMPLEXREGION - The new region can only be represented by more than
578 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
580 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
583 TRACE("%p %d,%d\n", hrgn
, x
, y
);
589 int nbox
= obj
->rgn
->numRects
;
590 RECT
*pbox
= obj
->rgn
->rects
;
600 obj
->rgn
->extents
.left
+= x
;
601 obj
->rgn
->extents
.right
+= x
;
602 obj
->rgn
->extents
.top
+= y
;
603 obj
->rgn
->extents
.bottom
+= y
;
606 ret
= get_region_type( obj
);
607 GDI_ReleaseObj( hrgn
);
612 /***********************************************************************
613 * GetRgnBox (GDI32.@)
615 * Retrieves the bounding rectangle of the region. The bounding rectangle
616 * is the smallest rectangle that contains the entire region.
619 * hrgn [I] Region to retrieve bounding rectangle from.
620 * rect [O] Rectangle that will receive the coordinates of the bounding
624 * NULLREGION - The new region is empty.
625 * SIMPLEREGION - The new region can be represented by one rectangle.
626 * COMPLEXREGION - The new region can only be represented by more than
629 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
631 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
635 rect
->left
= obj
->rgn
->extents
.left
;
636 rect
->top
= obj
->rgn
->extents
.top
;
637 rect
->right
= obj
->rgn
->extents
.right
;
638 rect
->bottom
= obj
->rgn
->extents
.bottom
;
639 TRACE("%p (%ld,%ld-%ld,%ld)\n", hrgn
,
640 rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
641 ret
= get_region_type( obj
);
642 GDI_ReleaseObj(hrgn
);
649 /***********************************************************************
650 * CreateRectRgn (GDI32.@)
652 * Creates a simple rectangular region.
655 * left [I] Left coordinate of rectangle.
656 * top [I] Top coordinate of rectangle.
657 * right [I] Right coordinate of rectangle.
658 * bottom [I] Bottom coordinate of rectangle.
661 * Success: Handle to region.
664 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
668 /* Allocate 2 rects by default to reduce the number of reallocs */
670 if (!(hrgn
= REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
672 TRACE("%d,%d-%d,%d\n", left
, top
, right
, bottom
);
673 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
678 /***********************************************************************
679 * CreateRectRgnIndirect (GDI32.@)
681 * Creates a simple rectangular region.
684 * rect [I] Coordinates of rectangular region.
687 * Success: Handle to region.
690 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
692 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
696 /***********************************************************************
697 * SetRectRgn (GDI32.@)
699 * Sets a region to a simple rectangular region.
702 * hrgn [I] Region to convert.
703 * left [I] Left coordinate of rectangle.
704 * top [I] Top coordinate of rectangle.
705 * right [I] Right coordinate of rectangle.
706 * bottom [I] Bottom coordinate of rectangle.
713 * Allows either or both left and top to be greater than right or bottom.
715 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
716 INT right
, INT bottom
)
720 TRACE("%p %d,%d-%d,%d\n", hrgn
, left
, top
, right
, bottom
);
722 if (!(obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return FALSE
;
724 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
725 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
727 if((left
!= right
) && (top
!= bottom
))
729 obj
->rgn
->rects
->left
= obj
->rgn
->extents
.left
= left
;
730 obj
->rgn
->rects
->top
= obj
->rgn
->extents
.top
= top
;
731 obj
->rgn
->rects
->right
= obj
->rgn
->extents
.right
= right
;
732 obj
->rgn
->rects
->bottom
= obj
->rgn
->extents
.bottom
= bottom
;
733 obj
->rgn
->numRects
= 1;
736 EMPTY_REGION(obj
->rgn
);
738 GDI_ReleaseObj( hrgn
);
743 /***********************************************************************
744 * CreateRoundRectRgn (GDI32.@)
746 * Creates a rectangular region with rounded corners.
749 * left [I] Left coordinate of rectangle.
750 * top [I] Top coordinate of rectangle.
751 * right [I] Right coordinate of rectangle.
752 * bottom [I] Bottom coordinate of rectangle.
753 * ellipse_width [I] Width of the ellipse at each corner.
754 * ellipse_height [I] Height of the ellipse at each corner.
757 * Success: Handle to region.
761 * If ellipse_width or ellipse_height is less than 2 logical units then
762 * it is treated as though CreateRectRgn() was called instead.
764 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
765 INT right
, INT bottom
,
766 INT ellipse_width
, INT ellipse_height
)
770 int asq
, bsq
, d
, xd
, yd
;
773 /* Make the dimensions sensible */
775 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
776 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
778 ellipse_width
= abs(ellipse_width
);
779 ellipse_height
= abs(ellipse_height
);
781 /* Check parameters */
783 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
784 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
786 /* Check if we can do a normal rectangle instead */
788 if ((ellipse_width
< 2) || (ellipse_height
< 2))
789 return CreateRectRgn( left
, top
, right
, bottom
);
793 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
794 if (!(hrgn
= REGION_CreateRegion(d
))) return 0;
795 if (!(obj
= GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return 0;
796 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
797 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
799 /* Ellipse algorithm, based on an article by K. Porter */
800 /* in DDJ Graphics Programming Column, 8/89 */
802 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
803 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
804 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
806 yd
= asq
* ellipse_height
; /* 2a^2b */
808 rect
.left
= left
+ ellipse_width
/ 2;
809 rect
.right
= right
- ellipse_width
/ 2;
811 /* Loop to draw first half of quadrant */
815 if (d
> 0) /* if nearest pixel is toward the center */
817 /* move toward center */
819 rect
.bottom
= rect
.top
+ 1;
820 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
822 rect
.bottom
= rect
.top
+ 1;
823 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
827 rect
.left
--; /* next horiz point */
833 /* Loop to draw second half of quadrant */
835 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
838 /* next vertical point */
840 rect
.bottom
= rect
.top
+ 1;
841 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
843 rect
.bottom
= rect
.top
+ 1;
844 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
845 if (d
< 0) /* if nearest pixel is outside ellipse */
847 rect
.left
--; /* move away from center */
856 /* Add the inside rectangle */
861 rect
.bottom
= bottom
;
862 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
864 GDI_ReleaseObj( hrgn
);
869 /***********************************************************************
870 * CreateEllipticRgn (GDI32.@)
872 * Creates an elliptical region.
875 * left [I] Left coordinate of bounding rectangle.
876 * top [I] Top coordinate of bounding rectangle.
877 * right [I] Right coordinate of bounding rectangle.
878 * bottom [I] Bottom coordinate of bounding rectangle.
881 * Success: Handle to region.
885 * This is a special case of CreateRoundRectRgn() where the width of the
886 * ellipse at each corner is equal to the width the the rectangle and
887 * the same for the height.
889 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
890 INT right
, INT bottom
)
892 return CreateRoundRectRgn( left
, top
, right
, bottom
,
893 right
-left
, bottom
-top
);
897 /***********************************************************************
898 * CreateEllipticRgnIndirect (GDI32.@)
900 * Creates an elliptical region.
903 * rect [I] Pointer to bounding rectangle of the ellipse.
906 * Success: Handle to region.
910 * This is a special case of CreateRoundRectRgn() where the width of the
911 * ellipse at each corner is equal to the width the the rectangle and
912 * the same for the height.
914 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
916 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
917 rect
->bottom
, rect
->right
- rect
->left
,
918 rect
->bottom
- rect
->top
);
921 /***********************************************************************
922 * GetRegionData (GDI32.@)
924 * Retrieves the data that specifies the region.
927 * hrgn [I] Region to retrieve the region data from.
928 * count [I] The size of the buffer pointed to by rgndata in bytes.
929 * rgndata [I] The buffer to receive data about the region.
932 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
933 * the number of bytes copied to the output buffer.
937 * The format of the Buffer member of RGNDATA is determined by the iType
938 * member of the region data header.
939 * Currently this is always RDH_RECTANGLES, which specifies that the format
940 * is the array of RECT's that specify the region. The length of the array
941 * is specified by the nCount member of the region data header.
943 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
946 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
948 TRACE(" %p count = %ld, rgndata = %p\n", hrgn
, count
, rgndata
);
952 size
= obj
->rgn
->numRects
* sizeof(RECT
);
953 if(count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
955 GDI_ReleaseObj( hrgn
);
956 if (rgndata
) /* buffer is too small, signal it by return 0 */
958 else /* user requested buffer size with rgndata NULL */
959 return size
+ sizeof(RGNDATAHEADER
);
962 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
963 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
964 rgndata
->rdh
.nCount
= obj
->rgn
->numRects
;
965 rgndata
->rdh
.nRgnSize
= size
;
966 rgndata
->rdh
.rcBound
.left
= obj
->rgn
->extents
.left
;
967 rgndata
->rdh
.rcBound
.top
= obj
->rgn
->extents
.top
;
968 rgndata
->rdh
.rcBound
.right
= obj
->rgn
->extents
.right
;
969 rgndata
->rdh
.rcBound
.bottom
= obj
->rgn
->extents
.bottom
;
971 memcpy( rgndata
->Buffer
, obj
->rgn
->rects
, size
);
973 GDI_ReleaseObj( hrgn
);
974 return size
+ sizeof(RGNDATAHEADER
);
978 /***********************************************************************
979 * ExtCreateRegion (GDI32.@)
981 * Creates a region as specified by the transformation data and region data.
984 * lpXform [I] World-space to logical-space transformation data.
985 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
986 * rgndata [I] Data that specifes the region.
989 * Success: Handle to region.
993 * See GetRegionData().
995 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
999 TRACE(" %p %ld %p = ", lpXform
, dwCount
, rgndata
);
1002 WARN("(Xform not implemented - ignored)\n");
1004 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
1006 /* FIXME: We can use CreatePolyPolygonRgn() here
1007 * for trapezoidal data */
1009 WARN("(Unsupported region data)\n");
1013 if( (hrgn
= REGION_CreateRegion( rgndata
->rdh
.nCount
)) )
1015 RECT
*pCurRect
, *pEndRect
;
1016 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
1019 pEndRect
= (RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
1020 for(pCurRect
= (RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
1021 REGION_UnionRectWithRegion( pCurRect
, obj
->rgn
);
1022 GDI_ReleaseObj( hrgn
);
1024 TRACE("%p\n", hrgn
);
1027 else ERR("Could not get pointer to newborn Region!\n");
1035 /***********************************************************************
1036 * PtInRegion (GDI32.@)
1038 * Tests whether the specified point is inside a region.
1041 * hrgn [I] Region to test.
1042 * x [I] X-coordinate of point to test.
1043 * y [I] Y-coordinate of point to test.
1046 * Non-zero if the point is inside the region or zero otherwise.
1048 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
1053 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
1057 if (obj
->rgn
->numRects
> 0 && INRECT(obj
->rgn
->extents
, x
, y
))
1058 for (i
= 0; i
< obj
->rgn
->numRects
; i
++)
1059 if (INRECT (obj
->rgn
->rects
[i
], x
, y
))
1064 GDI_ReleaseObj( hrgn
);
1070 /***********************************************************************
1071 * RectInRegion (GDI32.@)
1073 * Tests if a rectangle is at least partly inside the specified region.
1076 * hrgn [I] Region to test.
1077 * rect [I] Rectangle to test.
1080 * Non-zero if the rectangle is partially inside the region or
1083 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
1088 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
1090 RECT
*pCurRect
, *pRectEnd
;
1092 /* this is (just) a useful optimization */
1093 if ((obj
->rgn
->numRects
> 0) && EXTENTCHECK(&obj
->rgn
->extents
,
1096 for (pCurRect
= obj
->rgn
->rects
, pRectEnd
= pCurRect
+
1097 obj
->rgn
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
1099 if (pCurRect
->bottom
<= rect
->top
)
1100 continue; /* not far enough down yet */
1102 if (pCurRect
->top
>= rect
->bottom
)
1103 break; /* too far down */
1105 if (pCurRect
->right
<= rect
->left
)
1106 continue; /* not far enough over yet */
1108 if (pCurRect
->left
>= rect
->right
) {
1116 GDI_ReleaseObj(hrgn
);
1121 /***********************************************************************
1122 * EqualRgn (GDI32.@)
1124 * Tests whether one region is identical to another.
1127 * hrgn1 [I] The first region to compare.
1128 * hrgn2 [I] The second region to compare.
1131 * Non-zero if both regions are identical or zero otherwise.
1133 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
1135 RGNOBJ
*obj1
, *obj2
;
1138 if ((obj1
= (RGNOBJ
*) GDI_GetObjPtr( hrgn1
, REGION_MAGIC
)))
1140 if ((obj2
= (RGNOBJ
*) GDI_GetObjPtr( hrgn2
, REGION_MAGIC
)))
1144 if ( obj1
->rgn
->numRects
!= obj2
->rgn
->numRects
) goto done
;
1145 if ( obj1
->rgn
->numRects
== 0 )
1151 if (obj1
->rgn
->extents
.left
!= obj2
->rgn
->extents
.left
) goto done
;
1152 if (obj1
->rgn
->extents
.right
!= obj2
->rgn
->extents
.right
) goto done
;
1153 if (obj1
->rgn
->extents
.top
!= obj2
->rgn
->extents
.top
) goto done
;
1154 if (obj1
->rgn
->extents
.bottom
!= obj2
->rgn
->extents
.bottom
) goto done
;
1155 for( i
= 0; i
< obj1
->rgn
->numRects
; i
++ )
1157 if (obj1
->rgn
->rects
[i
].left
!= obj2
->rgn
->rects
[i
].left
) goto done
;
1158 if (obj1
->rgn
->rects
[i
].right
!= obj2
->rgn
->rects
[i
].right
) goto done
;
1159 if (obj1
->rgn
->rects
[i
].top
!= obj2
->rgn
->rects
[i
].top
) goto done
;
1160 if (obj1
->rgn
->rects
[i
].bottom
!= obj2
->rgn
->rects
[i
].bottom
) goto done
;
1164 GDI_ReleaseObj(hrgn2
);
1166 GDI_ReleaseObj(hrgn1
);
1171 /***********************************************************************
1172 * REGION_UnionRectWithRegion
1173 * Adds a rectangle to a WINEREGION
1175 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1179 region
.rects
= ®ion
.extents
;
1180 region
.numRects
= 1;
1182 region
.extents
= *rect
;
1183 REGION_UnionRegion(rgn
, rgn
, ®ion
);
1187 /***********************************************************************
1188 * REGION_CreateFrameRgn
1190 * Create a region that is a frame around another region.
1191 * Expand all rectangles by +/- x and y, then subtract original region.
1193 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1196 RGNOBJ
*srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
1198 if (!srcObj
) return FALSE
;
1199 if (srcObj
->rgn
->numRects
!= 0)
1201 RGNOBJ
* destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1202 RECT
*pRect
, *pEndRect
;
1205 EMPTY_REGION( destObj
->rgn
);
1207 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
1208 for(pRect
= srcObj
->rgn
->rects
; pRect
< pEndRect
; pRect
++)
1210 tempRect
.left
= pRect
->left
- x
;
1211 tempRect
.top
= pRect
->top
- y
;
1212 tempRect
.right
= pRect
->right
+ x
;
1213 tempRect
.bottom
= pRect
->bottom
+ y
;
1214 REGION_UnionRectWithRegion( &tempRect
, destObj
->rgn
);
1216 REGION_SubtractRegion( destObj
->rgn
, destObj
->rgn
, srcObj
->rgn
);
1217 GDI_ReleaseObj ( hDest
);
1222 GDI_ReleaseObj( hSrc
);
1227 /***********************************************************************
1228 * CombineRgn (GDI32.@)
1230 * Combines two regions with the specifed operation and stores the result
1231 * in the specified destination region.
1234 * hDest [I] The region that receives the combined result.
1235 * hSrc1 [I] The first source region.
1236 * hSrc2 [I] The second source region.
1237 * mode [I] The way in which the source regions will be combined. See notes.
1241 * NULLREGION - The new region is empty.
1242 * SIMPLEREGION - The new region can be represented by one rectangle.
1243 * COMPLEXREGION - The new region can only be represented by more than
1248 * The two source regions can be the same region.
1249 * The mode can be one of the following:
1250 *| RGN_AND - Intersection of the regions
1251 *| RGN_OR - Union of the regions
1252 *| RGN_XOR - Unions of the regions minus any intersection.
1253 *| RGN_DIFF - Difference (subtraction) of the regions.
1255 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1257 RGNOBJ
*destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1260 TRACE(" %p,%p -> %p mode=%x\n", hSrc1
, hSrc2
, hDest
, mode
);
1263 RGNOBJ
*src1Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc1
, REGION_MAGIC
);
1267 TRACE("dump src1Obj:\n");
1268 if(TRACE_ON(region
))
1269 REGION_DumpRegion(src1Obj
->rgn
);
1270 if (mode
== RGN_COPY
)
1272 REGION_CopyRegion( destObj
->rgn
, src1Obj
->rgn
);
1273 result
= get_region_type( destObj
);
1277 RGNOBJ
*src2Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc2
, REGION_MAGIC
);
1281 TRACE("dump src2Obj:\n");
1282 if(TRACE_ON(region
))
1283 REGION_DumpRegion(src2Obj
->rgn
);
1287 REGION_IntersectRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1290 REGION_UnionRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1293 REGION_XorRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1296 REGION_SubtractRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1299 result
= get_region_type( destObj
);
1300 GDI_ReleaseObj( hSrc2
);
1303 GDI_ReleaseObj( hSrc1
);
1305 TRACE("dump destObj:\n");
1306 if(TRACE_ON(region
))
1307 REGION_DumpRegion(destObj
->rgn
);
1309 GDI_ReleaseObj( hDest
);
1311 ERR("Invalid rgn=%p\n", hDest
);
1316 /***********************************************************************
1318 * Re-calculate the extents of a region
1320 static void REGION_SetExtents (WINEREGION
*pReg
)
1322 RECT
*pRect
, *pRectEnd
, *pExtents
;
1324 if (pReg
->numRects
== 0)
1326 pReg
->extents
.left
= 0;
1327 pReg
->extents
.top
= 0;
1328 pReg
->extents
.right
= 0;
1329 pReg
->extents
.bottom
= 0;
1333 pExtents
= &pReg
->extents
;
1334 pRect
= pReg
->rects
;
1335 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1338 * Since pRect is the first rectangle in the region, it must have the
1339 * smallest top and since pRectEnd is the last rectangle in the region,
1340 * it must have the largest bottom, because of banding. Initialize left and
1341 * right from pRect and pRectEnd, resp., as good things to initialize them
1344 pExtents
->left
= pRect
->left
;
1345 pExtents
->top
= pRect
->top
;
1346 pExtents
->right
= pRectEnd
->right
;
1347 pExtents
->bottom
= pRectEnd
->bottom
;
1349 while (pRect
<= pRectEnd
)
1351 if (pRect
->left
< pExtents
->left
)
1352 pExtents
->left
= pRect
->left
;
1353 if (pRect
->right
> pExtents
->right
)
1354 pExtents
->right
= pRect
->right
;
1359 /***********************************************************************
1362 static void REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1364 if (dst
!= src
) /* don't want to copy to itself */
1366 if (dst
->size
< src
->numRects
)
1368 if (! (dst
->rects
= HeapReAlloc( GetProcessHeap(), 0, dst
->rects
,
1369 src
->numRects
* sizeof(RECT
) )))
1371 dst
->size
= src
->numRects
;
1373 dst
->numRects
= src
->numRects
;
1374 dst
->extents
.left
= src
->extents
.left
;
1375 dst
->extents
.top
= src
->extents
.top
;
1376 dst
->extents
.right
= src
->extents
.right
;
1377 dst
->extents
.bottom
= src
->extents
.bottom
;
1378 memcpy((char *) dst
->rects
, (char *) src
->rects
,
1379 (int) (src
->numRects
* sizeof(RECT
)));
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 * Apply an operation to two regions. Called by REGION_Union,
1525 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1531 * The new region is overwritten.
1534 * The idea behind this function is to view the two regions as sets.
1535 * Together they cover a rectangle of area that this function divides
1536 * into horizontal bands where points are covered only by one region
1537 * or by both. For the first case, the nonOverlapFunc is called with
1538 * each the band and the band's upper and lower extents. For the
1539 * second, the overlapFunc is called to process the entire band. It
1540 * is responsible for clipping the rectangles in the band, though
1541 * this function provides the boundaries.
1542 * At the end of each band, the new region is coalesced, if possible,
1543 * to reduce the number of rectangles in the region.
1546 static void REGION_RegionOp(
1547 WINEREGION
*newReg
, /* Place to store result */
1548 WINEREGION
*reg1
, /* First region in operation */
1549 WINEREGION
*reg2
, /* 2nd region in operation */
1550 void (*overlapFunc
)(), /* Function to call for over-lapping bands */
1551 void (*nonOverlap1Func
)(), /* Function to call for non-overlapping bands in region 1 */
1552 void (*nonOverlap2Func
)() /* Function to call for non-overlapping bands in region 2 */
1554 RECT
*r1
; /* Pointer into first region */
1555 RECT
*r2
; /* Pointer into 2d region */
1556 RECT
*r1End
; /* End of 1st region */
1557 RECT
*r2End
; /* End of 2d region */
1558 INT ybot
; /* Bottom of intersection */
1559 INT ytop
; /* Top of intersection */
1560 RECT
*oldRects
; /* Old rects for newReg */
1561 INT prevBand
; /* Index of start of
1562 * previous band in newReg */
1563 INT curBand
; /* Index of start of current
1565 RECT
*r1BandEnd
; /* End of current band in r1 */
1566 RECT
*r2BandEnd
; /* End of current band in r2 */
1567 INT top
; /* Top of non-overlapping band */
1568 INT bot
; /* Bottom of non-overlapping band */
1572 * set r1, r2, r1End and r2End appropriately, preserve the important
1573 * parts of the destination region until the end in case it's one of
1574 * the two source regions, then mark the "new" region empty, allocating
1575 * another array of rectangles for it to use.
1579 r1End
= r1
+ reg1
->numRects
;
1580 r2End
= r2
+ reg2
->numRects
;
1584 * newReg may be one of the src regions so we can't empty it. We keep a
1585 * note of its rects pointer (so that we can free them later), preserve its
1586 * extents and simply set numRects to zero.
1589 oldRects
= newReg
->rects
;
1590 newReg
->numRects
= 0;
1593 * Allocate a reasonable number of rectangles for the new region. The idea
1594 * is to allocate enough so the individual functions don't need to
1595 * reallocate and copy the array, which is time consuming, yet we don't
1596 * have to worry about using too much memory. I hope to be able to
1597 * nuke the Xrealloc() at the end of this function eventually.
1599 newReg
->size
= max(reg1
->numRects
,reg2
->numRects
) * 2;
1601 if (! (newReg
->rects
= HeapAlloc( GetProcessHeap(), 0,
1602 sizeof(RECT
) * newReg
->size
)))
1609 * Initialize ybot and ytop.
1610 * In the upcoming loop, ybot and ytop serve different functions depending
1611 * on whether the band being handled is an overlapping or non-overlapping
1613 * In the case of a non-overlapping band (only one of the regions
1614 * has points in the band), ybot is the bottom of the most recent
1615 * intersection and thus clips the top of the rectangles in that band.
1616 * ytop is the top of the next intersection between the two regions and
1617 * serves to clip the bottom of the rectangles in the current band.
1618 * For an overlapping band (where the two regions intersect), ytop clips
1619 * the top of the rectangles of both regions and ybot clips the bottoms.
1621 if (reg1
->extents
.top
< reg2
->extents
.top
)
1622 ybot
= reg1
->extents
.top
;
1624 ybot
= reg2
->extents
.top
;
1627 * prevBand serves to mark the start of the previous band so rectangles
1628 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1629 * In the beginning, there is no previous band, so prevBand == curBand
1630 * (curBand is set later on, of course, but the first band will always
1631 * start at index 0). prevBand and curBand must be indices because of
1632 * the possible expansion, and resultant moving, of the new region's
1633 * array of rectangles.
1639 curBand
= newReg
->numRects
;
1642 * This algorithm proceeds one source-band (as opposed to a
1643 * destination band, which is determined by where the two regions
1644 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1645 * rectangle after the last one in the current band for their
1646 * respective regions.
1649 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1655 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1661 * First handle the band that doesn't intersect, if any.
1663 * Note that attention is restricted to one band in the
1664 * non-intersecting region at once, so if a region has n
1665 * bands between the current position and the next place it overlaps
1666 * the other, this entire loop will be passed through n times.
1668 if (r1
->top
< r2
->top
)
1670 top
= max(r1
->top
,ybot
);
1671 bot
= min(r1
->bottom
,r2
->top
);
1673 if ((top
!= bot
) && (nonOverlap1Func
!= (void (*)())NULL
))
1675 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1680 else if (r2
->top
< r1
->top
)
1682 top
= max(r2
->top
,ybot
);
1683 bot
= min(r2
->bottom
,r1
->top
);
1685 if ((top
!= bot
) && (nonOverlap2Func
!= (void (*)())NULL
))
1687 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1698 * If any rectangles got added to the region, try and coalesce them
1699 * with rectangles from the previous band. Note we could just do
1700 * this test in miCoalesce, but some machines incur a not
1701 * inconsiderable cost for function calls, so...
1703 if (newReg
->numRects
!= curBand
)
1705 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1709 * Now see if we've hit an intersecting band. The two bands only
1710 * intersect if ybot > ytop
1712 ybot
= min(r1
->bottom
, r2
->bottom
);
1713 curBand
= newReg
->numRects
;
1716 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1720 if (newReg
->numRects
!= curBand
)
1722 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1726 * If we've finished with a band (bottom == ybot) we skip forward
1727 * in the region to the next band.
1729 if (r1
->bottom
== ybot
)
1733 if (r2
->bottom
== ybot
)
1737 } while ((r1
!= r1End
) && (r2
!= r2End
));
1740 * Deal with whichever region still has rectangles left.
1742 curBand
= newReg
->numRects
;
1745 if (nonOverlap1Func
!= (void (*)())NULL
)
1750 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1754 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1755 max(r1
->top
,ybot
), r1
->bottom
);
1757 } while (r1
!= r1End
);
1760 else if ((r2
!= r2End
) && (nonOverlap2Func
!= (void (*)())NULL
))
1765 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1769 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1770 max(r2
->top
,ybot
), r2
->bottom
);
1772 } while (r2
!= r2End
);
1775 if (newReg
->numRects
!= curBand
)
1777 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1781 * A bit of cleanup. To keep regions from growing without bound,
1782 * we shrink the array of rectangles to match the new number of
1783 * rectangles in the region. This never goes to 0, however...
1785 * Only do this stuff if the number of rectangles allocated is more than
1786 * twice the number of rectangles in the region (a simple optimization...).
1788 if ((newReg
->numRects
< (newReg
->size
>> 1)) && (newReg
->numRects
> 2))
1790 if (REGION_NOT_EMPTY(newReg
))
1792 RECT
*prev_rects
= newReg
->rects
;
1793 newReg
->size
= newReg
->numRects
;
1794 newReg
->rects
= HeapReAlloc( GetProcessHeap(), 0, newReg
->rects
,
1795 sizeof(RECT
) * newReg
->size
);
1796 if (! newReg
->rects
)
1797 newReg
->rects
= prev_rects
;
1802 * No point in doing the extra work involved in an Xrealloc if
1803 * the region is empty
1806 HeapFree( GetProcessHeap(), 0, newReg
->rects
);
1807 newReg
->rects
= HeapAlloc( GetProcessHeap(), 0, sizeof(RECT
) );
1810 HeapFree( GetProcessHeap(), 0, oldRects
);
1814 /***********************************************************************
1815 * Region Intersection
1816 ***********************************************************************/
1819 /***********************************************************************
1822 * Handle an overlapping band for REGION_Intersect.
1828 * Rectangles may be added to the region.
1831 static void REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1832 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1838 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1840 while ((r1
!= r1End
) && (r2
!= r2End
))
1842 left
= max(r1
->left
, r2
->left
);
1843 right
= min(r1
->right
, r2
->right
);
1846 * If there's any overlap between the two rectangles, add that
1847 * overlap to the new region.
1848 * There's no need to check for subsumption because the only way
1849 * such a need could arise is if some region has two rectangles
1850 * right next to each other. Since that should never happen...
1854 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1855 pNextRect
->left
= left
;
1856 pNextRect
->top
= top
;
1857 pNextRect
->right
= right
;
1858 pNextRect
->bottom
= bottom
;
1859 pReg
->numRects
+= 1;
1864 * Need to advance the pointers. Shift the one that extends
1865 * to the right the least, since the other still has a chance to
1866 * overlap with that region's next rectangle, if you see what I mean.
1868 if (r1
->right
< r2
->right
)
1872 else if (r2
->right
< r1
->right
)
1885 /***********************************************************************
1886 * REGION_IntersectRegion
1888 static void REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1891 /* check for trivial reject */
1892 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1893 (!EXTENTCHECK(®1
->extents
, ®2
->extents
)))
1894 newReg
->numRects
= 0;
1896 REGION_RegionOp (newReg
, reg1
, reg2
,
1897 (voidProcp
) REGION_IntersectO
, (voidProcp
) NULL
, (voidProcp
) NULL
);
1900 * Can't alter newReg's extents before we call miRegionOp because
1901 * it might be one of the source regions and miRegionOp depends
1902 * on the extents of those regions being the same. Besides, this
1903 * way there's no checking against rectangles that will be nuked
1904 * due to coalescing, so we have to examine fewer rectangles.
1906 REGION_SetExtents(newReg
);
1909 /***********************************************************************
1911 ***********************************************************************/
1913 /***********************************************************************
1916 * Handle a non-overlapping band for the union operation. Just
1917 * Adds the rectangles into the region. Doesn't have to check for
1918 * subsumption or anything.
1924 * pReg->numRects is incremented and the final rectangles overwritten
1925 * with the rectangles we're passed.
1928 static void REGION_UnionNonO (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1929 INT top
, INT bottom
)
1933 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1937 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1938 pNextRect
->left
= r
->left
;
1939 pNextRect
->top
= top
;
1940 pNextRect
->right
= r
->right
;
1941 pNextRect
->bottom
= bottom
;
1942 pReg
->numRects
+= 1;
1949 /***********************************************************************
1952 * Handle an overlapping band for the union operation. Picks the
1953 * left-most rectangle each time and merges it into the region.
1959 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1963 static void REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1964 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1968 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1970 #define MERGERECT(r) \
1971 if ((pReg->numRects != 0) && \
1972 (pNextRect[-1].top == top) && \
1973 (pNextRect[-1].bottom == bottom) && \
1974 (pNextRect[-1].right >= r->left)) \
1976 if (pNextRect[-1].right < r->right) \
1978 pNextRect[-1].right = r->right; \
1983 MEMCHECK(pReg, pNextRect, pReg->rects); \
1984 pNextRect->top = top; \
1985 pNextRect->bottom = bottom; \
1986 pNextRect->left = r->left; \
1987 pNextRect->right = r->right; \
1988 pReg->numRects += 1; \
1993 while ((r1
!= r1End
) && (r2
!= r2End
))
1995 if (r1
->left
< r2
->left
)
2010 } while (r1
!= r1End
);
2012 else while (r2
!= r2End
)
2019 /***********************************************************************
2020 * REGION_UnionRegion
2022 static void REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
2025 /* checks all the simple cases */
2028 * Region 1 and 2 are the same or region 1 is empty
2030 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
2033 REGION_CopyRegion(newReg
, reg2
);
2038 * if nothing to union (region 2 empty)
2040 if (!(reg2
->numRects
))
2043 REGION_CopyRegion(newReg
, reg1
);
2048 * Region 1 completely subsumes region 2
2050 if ((reg1
->numRects
== 1) &&
2051 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
2052 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
2053 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
2054 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
2057 REGION_CopyRegion(newReg
, reg1
);
2062 * Region 2 completely subsumes region 1
2064 if ((reg2
->numRects
== 1) &&
2065 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
2066 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
2067 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
2068 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
2071 REGION_CopyRegion(newReg
, reg2
);
2075 REGION_RegionOp (newReg
, reg1
, reg2
, (voidProcp
) REGION_UnionO
,
2076 (voidProcp
) REGION_UnionNonO
, (voidProcp
) REGION_UnionNonO
);
2078 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
2079 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
2080 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
2081 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
2084 /***********************************************************************
2085 * Region Subtraction
2086 ***********************************************************************/
2088 /***********************************************************************
2089 * REGION_SubtractNonO1
2091 * Deal with non-overlapping band for subtraction. Any parts from
2092 * region 2 we discard. Anything from region 1 we add to the region.
2098 * pReg may be affected.
2101 static void REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
2102 INT top
, INT bottom
)
2106 pNextRect
= &pReg
->rects
[pReg
->numRects
];
2110 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2111 pNextRect
->left
= r
->left
;
2112 pNextRect
->top
= top
;
2113 pNextRect
->right
= r
->right
;
2114 pNextRect
->bottom
= bottom
;
2115 pReg
->numRects
+= 1;
2123 /***********************************************************************
2126 * Overlapping band subtraction. x1 is the left-most point not yet
2133 * pReg may have rectangles added to it.
2136 static void REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2137 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2143 pNextRect
= &pReg
->rects
[pReg
->numRects
];
2145 while ((r1
!= r1End
) && (r2
!= r2End
))
2147 if (r2
->right
<= left
)
2150 * Subtrahend missed the boat: go to next subtrahend.
2154 else if (r2
->left
<= left
)
2157 * Subtrahend preceeds minuend: nuke left edge of minuend.
2160 if (left
>= r1
->right
)
2163 * Minuend completely covered: advance to next minuend and
2164 * reset left fence to edge of new minuend.
2173 * Subtrahend now used up since it doesn't extend beyond
2179 else if (r2
->left
< r1
->right
)
2182 * Left part of subtrahend covers part of minuend: add uncovered
2183 * part of minuend to region and skip to next subtrahend.
2185 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2186 pNextRect
->left
= left
;
2187 pNextRect
->top
= top
;
2188 pNextRect
->right
= r2
->left
;
2189 pNextRect
->bottom
= bottom
;
2190 pReg
->numRects
+= 1;
2193 if (left
>= r1
->right
)
2196 * Minuend used up: advance to new...
2205 * Subtrahend used up
2213 * Minuend used up: add any remaining piece before advancing.
2215 if (r1
->right
> left
)
2217 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2218 pNextRect
->left
= left
;
2219 pNextRect
->top
= top
;
2220 pNextRect
->right
= r1
->right
;
2221 pNextRect
->bottom
= bottom
;
2222 pReg
->numRects
+= 1;
2231 * Add remaining minuend rectangles to region.
2235 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2236 pNextRect
->left
= left
;
2237 pNextRect
->top
= top
;
2238 pNextRect
->right
= r1
->right
;
2239 pNextRect
->bottom
= bottom
;
2240 pReg
->numRects
+= 1;
2251 /***********************************************************************
2252 * REGION_SubtractRegion
2254 * Subtract regS from regM and leave the result in regD.
2255 * S stands for subtrahend, M for minuend and D for difference.
2261 * regD is overwritten.
2264 static void REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
,
2267 /* check for trivial reject */
2268 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2269 (!EXTENTCHECK(®M
->extents
, ®S
->extents
)) )
2271 REGION_CopyRegion(regD
, regM
);
2275 REGION_RegionOp (regD
, regM
, regS
, (voidProcp
) REGION_SubtractO
,
2276 (voidProcp
) REGION_SubtractNonO1
, (voidProcp
) NULL
);
2279 * Can't alter newReg's extents before we call miRegionOp because
2280 * it might be one of the source regions and miRegionOp depends
2281 * on the extents of those regions being the unaltered. Besides, this
2282 * way there's no checking against rectangles that will be nuked
2283 * due to coalescing, so we have to examine fewer rectangles.
2285 REGION_SetExtents (regD
);
2288 /***********************************************************************
2291 static void REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
,
2294 WINEREGION
*tra
, *trb
;
2296 if ((! (tra
= REGION_AllocWineRegion(sra
->numRects
+ 1))) ||
2297 (! (trb
= REGION_AllocWineRegion(srb
->numRects
+ 1))))
2299 REGION_SubtractRegion(tra
,sra
,srb
);
2300 REGION_SubtractRegion(trb
,srb
,sra
);
2301 REGION_UnionRegion(dr
,tra
,trb
);
2302 REGION_DestroyWineRegion(tra
);
2303 REGION_DestroyWineRegion(trb
);
2307 /**************************************************************************
2311 *************************************************************************/
2313 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2314 #define SMALL_COORDINATE 0x80000000
2316 /***********************************************************************
2317 * REGION_InsertEdgeInET
2319 * Insert the given edge into the edge table.
2320 * First we must find the correct bucket in the
2321 * Edge table, then find the right slot in the
2322 * bucket. Finally, we can insert it.
2325 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2326 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2329 EdgeTableEntry
*start
, *prev
;
2330 ScanLineList
*pSLL
, *pPrevSLL
;
2331 ScanLineListBlock
*tmpSLLBlock
;
2334 * find the right bucket to put the edge into
2336 pPrevSLL
= &ET
->scanlines
;
2337 pSLL
= pPrevSLL
->next
;
2338 while (pSLL
&& (pSLL
->scanline
< scanline
))
2345 * reassign pSLL (pointer to ScanLineList) if necessary
2347 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2349 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2351 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2354 WARN("Can't alloc SLLB\n");
2357 (*SLLBlock
)->next
= tmpSLLBlock
;
2358 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2359 *SLLBlock
= tmpSLLBlock
;
2362 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2364 pSLL
->next
= pPrevSLL
->next
;
2365 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
2366 pPrevSLL
->next
= pSLL
;
2368 pSLL
->scanline
= scanline
;
2371 * now insert the edge in the right bucket
2373 prev
= (EdgeTableEntry
*)NULL
;
2374 start
= pSLL
->edgelist
;
2375 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
2378 start
= start
->next
;
2385 pSLL
->edgelist
= ETE
;
2388 /***********************************************************************
2389 * REGION_CreateEdgeTable
2391 * This routine creates the edge table for
2392 * scan converting polygons.
2393 * The Edge Table (ET) looks like:
2397 * | ymax | ScanLineLists
2398 * |scanline|-->------------>-------------->...
2399 * -------- |scanline| |scanline|
2400 * |edgelist| |edgelist|
2401 * --------- ---------
2405 * list of ETEs list of ETEs
2407 * where ETE is an EdgeTableEntry data structure,
2408 * and there is one ScanLineList per scanline at
2409 * which an edge is initially entered.
2412 static void REGION_CreateETandAET(const INT
*Count
, INT nbpolygons
,
2413 const POINT
*pts
, EdgeTable
*ET
, EdgeTableEntry
*AET
,
2414 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2416 const POINT
*top
, *bottom
;
2417 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2424 * initialize the Active Edge Table
2426 AET
->next
= (EdgeTableEntry
*)NULL
;
2427 AET
->back
= (EdgeTableEntry
*)NULL
;
2428 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2429 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
2432 * initialize the Edge Table.
2434 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
2435 ET
->ymax
= SMALL_COORDINATE
;
2436 ET
->ymin
= LARGE_COORDINATE
;
2437 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2440 for(poly
= 0; poly
< nbpolygons
; poly
++)
2442 count
= Count
[poly
];
2450 * for each vertex in the array of points.
2451 * In this loop we are dealing with two vertices at
2452 * a time -- these make up one edge of the polygon.
2459 * find out which point is above and which is below.
2461 if (PrevPt
->y
> CurrPt
->y
)
2463 bottom
= PrevPt
, top
= CurrPt
;
2464 pETEs
->ClockWise
= 0;
2468 bottom
= CurrPt
, top
= PrevPt
;
2469 pETEs
->ClockWise
= 1;
2473 * don't add horizontal edges to the Edge table.
2475 if (bottom
->y
!= top
->y
)
2477 pETEs
->ymax
= bottom
->y
-1;
2478 /* -1 so we don't get last scanline */
2481 * initialize integer edge algorithm
2483 dy
= bottom
->y
- top
->y
;
2484 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
2486 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2489 if (PrevPt
->y
> ET
->ymax
)
2490 ET
->ymax
= PrevPt
->y
;
2491 if (PrevPt
->y
< ET
->ymin
)
2492 ET
->ymin
= PrevPt
->y
;
2501 /***********************************************************************
2504 * This routine moves EdgeTableEntries from the
2505 * EdgeTable into the Active Edge Table,
2506 * leaving them sorted by smaller x coordinate.
2509 static void REGION_loadAET(EdgeTableEntry
*AET
, EdgeTableEntry
*ETEs
)
2511 EdgeTableEntry
*pPrevAET
;
2512 EdgeTableEntry
*tmp
;
2518 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
2527 ETEs
->back
= pPrevAET
;
2528 pPrevAET
->next
= ETEs
;
2535 /***********************************************************************
2536 * REGION_computeWAET
2538 * This routine links the AET by the
2539 * nextWETE (winding EdgeTableEntry) link for
2540 * use by the winding number rule. The final
2541 * Active Edge Table (AET) might look something
2545 * ---------- --------- ---------
2546 * |ymax | |ymax | |ymax |
2547 * | ... | |... | |... |
2548 * |next |->|next |->|next |->...
2549 * |nextWETE| |nextWETE| |nextWETE|
2550 * --------- --------- ^--------
2552 * V-------------------> V---> ...
2555 static void REGION_computeWAET(EdgeTableEntry
*AET
)
2557 register EdgeTableEntry
*pWETE
;
2558 register int inside
= 1;
2559 register int isInside
= 0;
2561 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2571 if ((!inside
&& !isInside
) ||
2572 ( inside
&& isInside
))
2574 pWETE
->nextWETE
= AET
;
2580 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
2583 /***********************************************************************
2584 * REGION_InsertionSort
2586 * Just a simple insertion sort using
2587 * pointers and back pointers to sort the Active
2591 static BOOL
REGION_InsertionSort(EdgeTableEntry
*AET
)
2593 EdgeTableEntry
*pETEchase
;
2594 EdgeTableEntry
*pETEinsert
;
2595 EdgeTableEntry
*pETEchaseBackTMP
;
2596 BOOL changed
= FALSE
;
2603 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
2604 pETEchase
= pETEchase
->back
;
2607 if (pETEchase
!= pETEinsert
)
2609 pETEchaseBackTMP
= pETEchase
->back
;
2610 pETEinsert
->back
->next
= AET
;
2612 AET
->back
= pETEinsert
->back
;
2613 pETEinsert
->next
= pETEchase
;
2614 pETEchase
->back
->next
= pETEinsert
;
2615 pETEchase
->back
= pETEinsert
;
2616 pETEinsert
->back
= pETEchaseBackTMP
;
2623 /***********************************************************************
2624 * REGION_FreeStorage
2628 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2630 ScanLineListBlock
*tmpSLLBlock
;
2634 tmpSLLBlock
= pSLLBlock
->next
;
2635 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2636 pSLLBlock
= tmpSLLBlock
;
2641 /***********************************************************************
2642 * REGION_PtsToRegion
2644 * Create an array of rectangles from a list of points.
2646 static int REGION_PtsToRegion(int numFullPtBlocks
, int iCurPtBlock
,
2647 POINTBLOCK
*FirstPtBlock
, WINEREGION
*reg
)
2651 POINTBLOCK
*CurPtBlock
;
2656 extents
= ®
->extents
;
2658 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
2660 if (!(reg
->rects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
,
2661 sizeof(RECT
) * numRects
)))
2664 reg
->size
= numRects
;
2665 CurPtBlock
= FirstPtBlock
;
2666 rects
= reg
->rects
- 1;
2668 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2670 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--) {
2671 /* the loop uses 2 points per iteration */
2672 i
= NUMPTSTOBUFFER
>> 1;
2673 if (!numFullPtBlocks
)
2674 i
= iCurPtBlock
>> 1;
2675 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2) {
2676 if (pts
->x
== pts
[1].x
)
2678 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2679 pts
[1].x
== rects
->right
&&
2680 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2681 (i
&& pts
[2].y
> pts
[1].y
)) {
2682 rects
->bottom
= pts
[1].y
+ 1;
2687 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2688 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2689 if (rects
->left
< extents
->left
)
2690 extents
->left
= rects
->left
;
2691 if (rects
->right
> extents
->right
)
2692 extents
->right
= rects
->right
;
2694 CurPtBlock
= CurPtBlock
->next
;
2698 extents
->top
= reg
->rects
->top
;
2699 extents
->bottom
= rects
->bottom
;
2704 extents
->bottom
= 0;
2706 reg
->numRects
= numRects
;
2711 /***********************************************************************
2712 * CreatePolyPolygonRgn (GDI32.@)
2714 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2715 INT nbpolygons
, INT mode
)
2720 register EdgeTableEntry
*pAET
; /* Active Edge Table */
2721 register INT y
; /* current scanline */
2722 register int iPts
= 0; /* number of pts in buffer */
2723 register EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
2724 register ScanLineList
*pSLL
; /* current scanLineList */
2725 register POINT
*pts
; /* output buffer */
2726 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
2727 EdgeTable ET
; /* header node for ET */
2728 EdgeTableEntry AET
; /* header node for AET */
2729 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2730 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2731 int fixWAET
= FALSE
;
2732 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
2733 POINTBLOCK
*tmpPtBlock
;
2734 int numFullPtBlocks
= 0;
2737 if(!(hrgn
= REGION_CreateRegion(nbpolygons
)))
2739 obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
2742 /* special case a rectangle */
2744 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2745 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2746 (((Pts
[0].y
== Pts
[1].y
) &&
2747 (Pts
[1].x
== Pts
[2].x
) &&
2748 (Pts
[2].y
== Pts
[3].y
) &&
2749 (Pts
[3].x
== Pts
[0].x
)) ||
2750 ((Pts
[0].x
== Pts
[1].x
) &&
2751 (Pts
[1].y
== Pts
[2].y
) &&
2752 (Pts
[2].x
== Pts
[3].x
) &&
2753 (Pts
[3].y
== Pts
[0].y
))))
2755 SetRectRgn( hrgn
, min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2756 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2757 GDI_ReleaseObj( hrgn
);
2761 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2762 total
+= Count
[poly
];
2763 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2765 REGION_DeleteObject( hrgn
, obj
);
2768 pts
= FirstPtBlock
.pts
;
2769 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
2770 pSLL
= ET
.scanlines
.next
;
2771 curPtBlock
= &FirstPtBlock
;
2773 if (mode
!= WINDING
) {
2777 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2779 * Add a new edge to the active edge table when we
2780 * get to the next edge.
2782 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2783 REGION_loadAET(&AET
, pSLL
->edgelist
);
2790 * for each active edge
2793 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2797 * send out the buffer
2799 if (iPts
== NUMPTSTOBUFFER
) {
2800 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK
));
2802 WARN("Can't alloc tPB\n");
2805 curPtBlock
->next
= tmpPtBlock
;
2806 curPtBlock
= tmpPtBlock
;
2807 pts
= curPtBlock
->pts
;
2811 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
2813 REGION_InsertionSort(&AET
);
2820 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2822 * Add a new edge to the active edge table when we
2823 * get to the next edge.
2825 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2826 REGION_loadAET(&AET
, pSLL
->edgelist
);
2827 REGION_computeWAET(&AET
);
2835 * for each active edge
2839 * add to the buffer only those edges that
2840 * are in the Winding active edge table.
2842 if (pWETE
== pAET
) {
2843 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2847 * send out the buffer
2849 if (iPts
== NUMPTSTOBUFFER
) {
2850 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0,
2851 sizeof(POINTBLOCK
) );
2853 WARN("Can't alloc tPB\n");
2854 REGION_DeleteObject( hrgn
, obj
);
2857 curPtBlock
->next
= tmpPtBlock
;
2858 curPtBlock
= tmpPtBlock
;
2859 pts
= curPtBlock
->pts
;
2860 numFullPtBlocks
++; iPts
= 0;
2862 pWETE
= pWETE
->nextWETE
;
2864 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
2868 * recompute the winding active edge table if
2869 * we just resorted or have exited an edge.
2871 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2872 REGION_computeWAET(&AET
);
2877 REGION_FreeStorage(SLLBlock
.next
);
2878 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
2880 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;) {
2881 tmpPtBlock
= curPtBlock
->next
;
2882 HeapFree( GetProcessHeap(), 0, curPtBlock
);
2883 curPtBlock
= tmpPtBlock
;
2885 HeapFree( GetProcessHeap(), 0, pETEs
);
2886 GDI_ReleaseObj( hrgn
);
2891 /***********************************************************************
2892 * CreatePolygonRgn (GDI32.@)
2894 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2897 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);