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 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
565 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
568 TRACE("%p %d,%d\n", hrgn
, x
, y
);
574 int nbox
= obj
->rgn
->numRects
;
575 RECT
*pbox
= obj
->rgn
->rects
;
585 obj
->rgn
->extents
.left
+= x
;
586 obj
->rgn
->extents
.right
+= x
;
587 obj
->rgn
->extents
.top
+= y
;
588 obj
->rgn
->extents
.bottom
+= y
;
591 ret
= get_region_type( obj
);
592 GDI_ReleaseObj( hrgn
);
597 /***********************************************************************
598 * GetRgnBox (GDI32.@)
600 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
602 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
606 rect
->left
= obj
->rgn
->extents
.left
;
607 rect
->top
= obj
->rgn
->extents
.top
;
608 rect
->right
= obj
->rgn
->extents
.right
;
609 rect
->bottom
= obj
->rgn
->extents
.bottom
;
610 TRACE("%p (%ld,%ld-%ld,%ld)\n", hrgn
,
611 rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
612 ret
= get_region_type( obj
);
613 GDI_ReleaseObj(hrgn
);
620 /***********************************************************************
621 * CreateRectRgn (GDI32.@)
623 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
627 /* Allocate 2 rects by default to reduce the number of reallocs */
629 if (!(hrgn
= REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
631 TRACE("%d,%d-%d,%d\n", left
, top
, right
, bottom
);
632 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
637 /***********************************************************************
638 * CreateRectRgnIndirect (GDI32.@)
640 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
642 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
646 /***********************************************************************
647 * SetRectRgn (GDI32.@)
649 * Allows either or both left and top to be greater than right or bottom.
651 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
652 INT right
, INT bottom
)
656 TRACE("%p %d,%d-%d,%d\n", hrgn
, left
, top
, right
, bottom
);
658 if (!(obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return FALSE
;
660 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
661 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
663 if((left
!= right
) && (top
!= bottom
))
665 obj
->rgn
->rects
->left
= obj
->rgn
->extents
.left
= left
;
666 obj
->rgn
->rects
->top
= obj
->rgn
->extents
.top
= top
;
667 obj
->rgn
->rects
->right
= obj
->rgn
->extents
.right
= right
;
668 obj
->rgn
->rects
->bottom
= obj
->rgn
->extents
.bottom
= bottom
;
669 obj
->rgn
->numRects
= 1;
672 EMPTY_REGION(obj
->rgn
);
674 GDI_ReleaseObj( hrgn
);
679 /***********************************************************************
680 * CreateRoundRectRgn (GDI32.@)
682 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
683 INT right
, INT bottom
,
684 INT ellipse_width
, INT ellipse_height
)
688 int asq
, bsq
, d
, xd
, yd
;
691 /* Make the dimensions sensible */
693 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
694 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
696 ellipse_width
= abs(ellipse_width
);
697 ellipse_height
= abs(ellipse_height
);
699 /* Check parameters */
701 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
702 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
704 /* Check if we can do a normal rectangle instead */
706 if ((ellipse_width
< 2) || (ellipse_height
< 2))
707 return CreateRectRgn( left
, top
, right
, bottom
);
711 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
712 if (!(hrgn
= REGION_CreateRegion(d
))) return 0;
713 if (!(obj
= GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return 0;
714 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
715 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
717 /* Ellipse algorithm, based on an article by K. Porter */
718 /* in DDJ Graphics Programming Column, 8/89 */
720 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
721 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
722 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
724 yd
= asq
* ellipse_height
; /* 2a^2b */
726 rect
.left
= left
+ ellipse_width
/ 2;
727 rect
.right
= right
- ellipse_width
/ 2;
729 /* Loop to draw first half of quadrant */
733 if (d
> 0) /* if nearest pixel is toward the center */
735 /* move toward center */
737 rect
.bottom
= rect
.top
+ 1;
738 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
740 rect
.bottom
= rect
.top
+ 1;
741 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
745 rect
.left
--; /* next horiz point */
751 /* Loop to draw second half of quadrant */
753 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
756 /* next vertical point */
758 rect
.bottom
= rect
.top
+ 1;
759 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
761 rect
.bottom
= rect
.top
+ 1;
762 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
763 if (d
< 0) /* if nearest pixel is outside ellipse */
765 rect
.left
--; /* move away from center */
774 /* Add the inside rectangle */
779 rect
.bottom
= bottom
;
780 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
782 GDI_ReleaseObj( hrgn
);
787 /***********************************************************************
788 * CreateEllipticRgn (GDI32.@)
790 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
791 INT right
, INT bottom
)
793 return CreateRoundRectRgn( left
, top
, right
, bottom
,
794 right
-left
, bottom
-top
);
798 /***********************************************************************
799 * CreateEllipticRgnIndirect (GDI32.@)
801 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
803 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
804 rect
->bottom
, rect
->right
- rect
->left
,
805 rect
->bottom
- rect
->top
);
808 /***********************************************************************
809 * GetRegionData (GDI32.@)
811 * MSDN: GetRegionData, Return Values:
813 * "If the function succeeds and dwCount specifies an adequate number of bytes,
814 * the return value is always dwCount. If dwCount is too small or the function
815 * fails, the return value is 0. If lpRgnData is NULL, the return value is the
816 * required number of bytes.
818 * If the function fails, the return value is zero."
820 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
823 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
825 TRACE(" %p count = %ld, rgndata = %p\n", hrgn
, count
, rgndata
);
829 size
= obj
->rgn
->numRects
* sizeof(RECT
);
830 if(count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
832 GDI_ReleaseObj( hrgn
);
833 if (rgndata
) /* buffer is too small, signal it by return 0 */
835 else /* user requested buffer size with rgndata NULL */
836 return size
+ sizeof(RGNDATAHEADER
);
839 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
840 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
841 rgndata
->rdh
.nCount
= obj
->rgn
->numRects
;
842 rgndata
->rdh
.nRgnSize
= size
;
843 rgndata
->rdh
.rcBound
.left
= obj
->rgn
->extents
.left
;
844 rgndata
->rdh
.rcBound
.top
= obj
->rgn
->extents
.top
;
845 rgndata
->rdh
.rcBound
.right
= obj
->rgn
->extents
.right
;
846 rgndata
->rdh
.rcBound
.bottom
= obj
->rgn
->extents
.bottom
;
848 memcpy( rgndata
->Buffer
, obj
->rgn
->rects
, size
);
850 GDI_ReleaseObj( hrgn
);
851 return size
+ sizeof(RGNDATAHEADER
);
855 /***********************************************************************
856 * ExtCreateRegion (GDI32.@)
859 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
863 TRACE(" %p %ld %p = ", lpXform
, dwCount
, rgndata
);
866 WARN("(Xform not implemented - ignored)\n");
868 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
870 /* FIXME: We can use CreatePolyPolygonRgn() here
871 * for trapezoidal data */
873 WARN("(Unsupported region data)\n");
877 if( (hrgn
= REGION_CreateRegion( rgndata
->rdh
.nCount
)) )
879 RECT
*pCurRect
, *pEndRect
;
880 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
883 pEndRect
= (RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
884 for(pCurRect
= (RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
885 REGION_UnionRectWithRegion( pCurRect
, obj
->rgn
);
886 GDI_ReleaseObj( hrgn
);
888 TRACE("%p\n", hrgn
);
891 else ERR("Could not get pointer to newborn Region!\n");
899 /***********************************************************************
900 * PtInRegion (GDI32.@)
902 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
907 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
911 if (obj
->rgn
->numRects
> 0 && INRECT(obj
->rgn
->extents
, x
, y
))
912 for (i
= 0; i
< obj
->rgn
->numRects
; i
++)
913 if (INRECT (obj
->rgn
->rects
[i
], x
, y
))
918 GDI_ReleaseObj( hrgn
);
924 /***********************************************************************
925 * RectInRegion (GDI32.@)
927 * Returns TRUE if rect is at least partly inside hrgn
929 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
934 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
936 RECT
*pCurRect
, *pRectEnd
;
938 /* this is (just) a useful optimization */
939 if ((obj
->rgn
->numRects
> 0) && EXTENTCHECK(&obj
->rgn
->extents
,
942 for (pCurRect
= obj
->rgn
->rects
, pRectEnd
= pCurRect
+
943 obj
->rgn
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
945 if (pCurRect
->bottom
<= rect
->top
)
946 continue; /* not far enough down yet */
948 if (pCurRect
->top
>= rect
->bottom
)
949 break; /* too far down */
951 if (pCurRect
->right
<= rect
->left
)
952 continue; /* not far enough over yet */
954 if (pCurRect
->left
>= rect
->right
) {
962 GDI_ReleaseObj(hrgn
);
967 /***********************************************************************
970 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
975 if ((obj1
= (RGNOBJ
*) GDI_GetObjPtr( hrgn1
, REGION_MAGIC
)))
977 if ((obj2
= (RGNOBJ
*) GDI_GetObjPtr( hrgn2
, REGION_MAGIC
)))
981 if ( obj1
->rgn
->numRects
!= obj2
->rgn
->numRects
) goto done
;
982 if ( obj1
->rgn
->numRects
== 0 )
988 if (obj1
->rgn
->extents
.left
!= obj2
->rgn
->extents
.left
) goto done
;
989 if (obj1
->rgn
->extents
.right
!= obj2
->rgn
->extents
.right
) goto done
;
990 if (obj1
->rgn
->extents
.top
!= obj2
->rgn
->extents
.top
) goto done
;
991 if (obj1
->rgn
->extents
.bottom
!= obj2
->rgn
->extents
.bottom
) goto done
;
992 for( i
= 0; i
< obj1
->rgn
->numRects
; i
++ )
994 if (obj1
->rgn
->rects
[i
].left
!= obj2
->rgn
->rects
[i
].left
) goto done
;
995 if (obj1
->rgn
->rects
[i
].right
!= obj2
->rgn
->rects
[i
].right
) goto done
;
996 if (obj1
->rgn
->rects
[i
].top
!= obj2
->rgn
->rects
[i
].top
) goto done
;
997 if (obj1
->rgn
->rects
[i
].bottom
!= obj2
->rgn
->rects
[i
].bottom
) goto done
;
1001 GDI_ReleaseObj(hrgn2
);
1003 GDI_ReleaseObj(hrgn1
);
1008 /***********************************************************************
1009 * REGION_UnionRectWithRegion
1010 * Adds a rectangle to a WINEREGION
1012 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1016 region
.rects
= ®ion
.extents
;
1017 region
.numRects
= 1;
1019 region
.extents
= *rect
;
1020 REGION_UnionRegion(rgn
, rgn
, ®ion
);
1024 /***********************************************************************
1025 * REGION_CreateFrameRgn
1027 * Create a region that is a frame around another region.
1028 * Expand all rectangles by +/- x and y, then subtract original region.
1030 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1033 RGNOBJ
*srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
1035 if (!srcObj
) return FALSE
;
1036 if (srcObj
->rgn
->numRects
!= 0)
1038 RGNOBJ
* destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1039 RECT
*pRect
, *pEndRect
;
1042 EMPTY_REGION( destObj
->rgn
);
1044 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
1045 for(pRect
= srcObj
->rgn
->rects
; pRect
< pEndRect
; pRect
++)
1047 tempRect
.left
= pRect
->left
- x
;
1048 tempRect
.top
= pRect
->top
- y
;
1049 tempRect
.right
= pRect
->right
+ x
;
1050 tempRect
.bottom
= pRect
->bottom
+ y
;
1051 REGION_UnionRectWithRegion( &tempRect
, destObj
->rgn
);
1053 REGION_SubtractRegion( destObj
->rgn
, destObj
->rgn
, srcObj
->rgn
);
1054 GDI_ReleaseObj ( hDest
);
1059 GDI_ReleaseObj( hSrc
);
1064 /***********************************************************************
1065 * CombineRgn (GDI32.@)
1067 * Note: The behavior is correct even if src and dest regions are the same.
1069 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1071 RGNOBJ
*destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1074 TRACE(" %p,%p -> %p mode=%x\n", hSrc1
, hSrc2
, hDest
, mode
);
1077 RGNOBJ
*src1Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc1
, REGION_MAGIC
);
1081 TRACE("dump src1Obj:\n");
1082 if(TRACE_ON(region
))
1083 REGION_DumpRegion(src1Obj
->rgn
);
1084 if (mode
== RGN_COPY
)
1086 REGION_CopyRegion( destObj
->rgn
, src1Obj
->rgn
);
1087 result
= get_region_type( destObj
);
1091 RGNOBJ
*src2Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc2
, REGION_MAGIC
);
1095 TRACE("dump src2Obj:\n");
1096 if(TRACE_ON(region
))
1097 REGION_DumpRegion(src2Obj
->rgn
);
1101 REGION_IntersectRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1104 REGION_UnionRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1107 REGION_XorRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1110 REGION_SubtractRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1113 result
= get_region_type( destObj
);
1114 GDI_ReleaseObj( hSrc2
);
1117 GDI_ReleaseObj( hSrc1
);
1119 TRACE("dump destObj:\n");
1120 if(TRACE_ON(region
))
1121 REGION_DumpRegion(destObj
->rgn
);
1123 GDI_ReleaseObj( hDest
);
1125 ERR("Invalid rgn=%p\n", hDest
);
1130 /***********************************************************************
1132 * Re-calculate the extents of a region
1134 static void REGION_SetExtents (WINEREGION
*pReg
)
1136 RECT
*pRect
, *pRectEnd
, *pExtents
;
1138 if (pReg
->numRects
== 0)
1140 pReg
->extents
.left
= 0;
1141 pReg
->extents
.top
= 0;
1142 pReg
->extents
.right
= 0;
1143 pReg
->extents
.bottom
= 0;
1147 pExtents
= &pReg
->extents
;
1148 pRect
= pReg
->rects
;
1149 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1152 * Since pRect is the first rectangle in the region, it must have the
1153 * smallest top and since pRectEnd is the last rectangle in the region,
1154 * it must have the largest bottom, because of banding. Initialize left and
1155 * right from pRect and pRectEnd, resp., as good things to initialize them
1158 pExtents
->left
= pRect
->left
;
1159 pExtents
->top
= pRect
->top
;
1160 pExtents
->right
= pRectEnd
->right
;
1161 pExtents
->bottom
= pRectEnd
->bottom
;
1163 while (pRect
<= pRectEnd
)
1165 if (pRect
->left
< pExtents
->left
)
1166 pExtents
->left
= pRect
->left
;
1167 if (pRect
->right
> pExtents
->right
)
1168 pExtents
->right
= pRect
->right
;
1173 /***********************************************************************
1176 static void REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1178 if (dst
!= src
) /* don't want to copy to itself */
1180 if (dst
->size
< src
->numRects
)
1182 if (! (dst
->rects
= HeapReAlloc( GetProcessHeap(), 0, dst
->rects
,
1183 src
->numRects
* sizeof(RECT
) )))
1185 dst
->size
= src
->numRects
;
1187 dst
->numRects
= src
->numRects
;
1188 dst
->extents
.left
= src
->extents
.left
;
1189 dst
->extents
.top
= src
->extents
.top
;
1190 dst
->extents
.right
= src
->extents
.right
;
1191 dst
->extents
.bottom
= src
->extents
.bottom
;
1192 memcpy((char *) dst
->rects
, (char *) src
->rects
,
1193 (int) (src
->numRects
* sizeof(RECT
)));
1198 /***********************************************************************
1201 * Attempt to merge the rects in the current band with those in the
1202 * previous one. Used only by REGION_RegionOp.
1205 * The new index for the previous band.
1208 * If coalescing takes place:
1209 * - rectangles in the previous band will have their bottom fields
1211 * - pReg->numRects will be decreased.
1214 static INT
REGION_Coalesce (
1215 WINEREGION
*pReg
, /* Region to coalesce */
1216 INT prevStart
, /* Index of start of previous band */
1217 INT curStart
/* Index of start of current band */
1219 RECT
*pPrevRect
; /* Current rect in previous band */
1220 RECT
*pCurRect
; /* Current rect in current band */
1221 RECT
*pRegEnd
; /* End of region */
1222 INT curNumRects
; /* Number of rectangles in current band */
1223 INT prevNumRects
; /* Number of rectangles in previous band */
1224 INT bandtop
; /* top coordinate for current band */
1226 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1228 pPrevRect
= &pReg
->rects
[prevStart
];
1229 prevNumRects
= curStart
- prevStart
;
1232 * Figure out how many rectangles are in the current band. Have to do
1233 * this because multiple bands could have been added in REGION_RegionOp
1234 * at the end when one region has been exhausted.
1236 pCurRect
= &pReg
->rects
[curStart
];
1237 bandtop
= pCurRect
->top
;
1238 for (curNumRects
= 0;
1239 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1245 if (pCurRect
!= pRegEnd
)
1248 * If more than one band was added, we have to find the start
1249 * of the last band added so the next coalescing job can start
1250 * at the right place... (given when multiple bands are added,
1251 * this may be pointless -- see above).
1254 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1258 curStart
= pRegEnd
- pReg
->rects
;
1259 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1262 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1263 pCurRect
-= curNumRects
;
1265 * The bands may only be coalesced if the bottom of the previous
1266 * matches the top scanline of the current.
1268 if (pPrevRect
->bottom
== pCurRect
->top
)
1271 * Make sure the bands have rects in the same places. This
1272 * assumes that rects have been added in such a way that they
1273 * cover the most area possible. I.e. two rects in a band must
1274 * have some horizontal space between them.
1278 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1279 (pPrevRect
->right
!= pCurRect
->right
))
1282 * The bands don't line up so they can't be coalesced.
1289 } while (prevNumRects
!= 0);
1291 pReg
->numRects
-= curNumRects
;
1292 pCurRect
-= curNumRects
;
1293 pPrevRect
-= curNumRects
;
1296 * The bands may be merged, so set the bottom of each rect
1297 * in the previous band to that of the corresponding rect in
1302 pPrevRect
->bottom
= pCurRect
->bottom
;
1306 } while (curNumRects
!= 0);
1309 * If only one band was added to the region, we have to backup
1310 * curStart to the start of the previous band.
1312 * If more than one band was added to the region, copy the
1313 * other bands down. The assumption here is that the other bands
1314 * came from the same region as the current one and no further
1315 * coalescing can be done on them since it's all been done
1316 * already... curStart is already in the right place.
1318 if (pCurRect
== pRegEnd
)
1320 curStart
= prevStart
;
1326 *pPrevRect
++ = *pCurRect
++;
1327 } while (pCurRect
!= pRegEnd
);
1335 /***********************************************************************
1338 * Apply an operation to two regions. Called by REGION_Union,
1339 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1345 * The new region is overwritten.
1348 * The idea behind this function is to view the two regions as sets.
1349 * Together they cover a rectangle of area that this function divides
1350 * into horizontal bands where points are covered only by one region
1351 * or by both. For the first case, the nonOverlapFunc is called with
1352 * each the band and the band's upper and lower extents. For the
1353 * second, the overlapFunc is called to process the entire band. It
1354 * is responsible for clipping the rectangles in the band, though
1355 * this function provides the boundaries.
1356 * At the end of each band, the new region is coalesced, if possible,
1357 * to reduce the number of rectangles in the region.
1360 static void REGION_RegionOp(
1361 WINEREGION
*newReg
, /* Place to store result */
1362 WINEREGION
*reg1
, /* First region in operation */
1363 WINEREGION
*reg2
, /* 2nd region in operation */
1364 void (*overlapFunc
)(), /* Function to call for over-lapping bands */
1365 void (*nonOverlap1Func
)(), /* Function to call for non-overlapping bands in region 1 */
1366 void (*nonOverlap2Func
)() /* Function to call for non-overlapping bands in region 2 */
1368 RECT
*r1
; /* Pointer into first region */
1369 RECT
*r2
; /* Pointer into 2d region */
1370 RECT
*r1End
; /* End of 1st region */
1371 RECT
*r2End
; /* End of 2d region */
1372 INT ybot
; /* Bottom of intersection */
1373 INT ytop
; /* Top of intersection */
1374 RECT
*oldRects
; /* Old rects for newReg */
1375 INT prevBand
; /* Index of start of
1376 * previous band in newReg */
1377 INT curBand
; /* Index of start of current
1379 RECT
*r1BandEnd
; /* End of current band in r1 */
1380 RECT
*r2BandEnd
; /* End of current band in r2 */
1381 INT top
; /* Top of non-overlapping band */
1382 INT bot
; /* Bottom of non-overlapping band */
1386 * set r1, r2, r1End and r2End appropriately, preserve the important
1387 * parts of the destination region until the end in case it's one of
1388 * the two source regions, then mark the "new" region empty, allocating
1389 * another array of rectangles for it to use.
1393 r1End
= r1
+ reg1
->numRects
;
1394 r2End
= r2
+ reg2
->numRects
;
1398 * newReg may be one of the src regions so we can't empty it. We keep a
1399 * note of its rects pointer (so that we can free them later), preserve its
1400 * extents and simply set numRects to zero.
1403 oldRects
= newReg
->rects
;
1404 newReg
->numRects
= 0;
1407 * Allocate a reasonable number of rectangles for the new region. The idea
1408 * is to allocate enough so the individual functions don't need to
1409 * reallocate and copy the array, which is time consuming, yet we don't
1410 * have to worry about using too much memory. I hope to be able to
1411 * nuke the Xrealloc() at the end of this function eventually.
1413 newReg
->size
= max(reg1
->numRects
,reg2
->numRects
) * 2;
1415 if (! (newReg
->rects
= HeapAlloc( GetProcessHeap(), 0,
1416 sizeof(RECT
) * newReg
->size
)))
1423 * Initialize ybot and ytop.
1424 * In the upcoming loop, ybot and ytop serve different functions depending
1425 * on whether the band being handled is an overlapping or non-overlapping
1427 * In the case of a non-overlapping band (only one of the regions
1428 * has points in the band), ybot is the bottom of the most recent
1429 * intersection and thus clips the top of the rectangles in that band.
1430 * ytop is the top of the next intersection between the two regions and
1431 * serves to clip the bottom of the rectangles in the current band.
1432 * For an overlapping band (where the two regions intersect), ytop clips
1433 * the top of the rectangles of both regions and ybot clips the bottoms.
1435 if (reg1
->extents
.top
< reg2
->extents
.top
)
1436 ybot
= reg1
->extents
.top
;
1438 ybot
= reg2
->extents
.top
;
1441 * prevBand serves to mark the start of the previous band so rectangles
1442 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1443 * In the beginning, there is no previous band, so prevBand == curBand
1444 * (curBand is set later on, of course, but the first band will always
1445 * start at index 0). prevBand and curBand must be indices because of
1446 * the possible expansion, and resultant moving, of the new region's
1447 * array of rectangles.
1453 curBand
= newReg
->numRects
;
1456 * This algorithm proceeds one source-band (as opposed to a
1457 * destination band, which is determined by where the two regions
1458 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1459 * rectangle after the last one in the current band for their
1460 * respective regions.
1463 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1469 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1475 * First handle the band that doesn't intersect, if any.
1477 * Note that attention is restricted to one band in the
1478 * non-intersecting region at once, so if a region has n
1479 * bands between the current position and the next place it overlaps
1480 * the other, this entire loop will be passed through n times.
1482 if (r1
->top
< r2
->top
)
1484 top
= max(r1
->top
,ybot
);
1485 bot
= min(r1
->bottom
,r2
->top
);
1487 if ((top
!= bot
) && (nonOverlap1Func
!= (void (*)())NULL
))
1489 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1494 else if (r2
->top
< r1
->top
)
1496 top
= max(r2
->top
,ybot
);
1497 bot
= min(r2
->bottom
,r1
->top
);
1499 if ((top
!= bot
) && (nonOverlap2Func
!= (void (*)())NULL
))
1501 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1512 * If any rectangles got added to the region, try and coalesce them
1513 * with rectangles from the previous band. Note we could just do
1514 * this test in miCoalesce, but some machines incur a not
1515 * inconsiderable cost for function calls, so...
1517 if (newReg
->numRects
!= curBand
)
1519 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1523 * Now see if we've hit an intersecting band. The two bands only
1524 * intersect if ybot > ytop
1526 ybot
= min(r1
->bottom
, r2
->bottom
);
1527 curBand
= newReg
->numRects
;
1530 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1534 if (newReg
->numRects
!= curBand
)
1536 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1540 * If we've finished with a band (bottom == ybot) we skip forward
1541 * in the region to the next band.
1543 if (r1
->bottom
== ybot
)
1547 if (r2
->bottom
== ybot
)
1551 } while ((r1
!= r1End
) && (r2
!= r2End
));
1554 * Deal with whichever region still has rectangles left.
1556 curBand
= newReg
->numRects
;
1559 if (nonOverlap1Func
!= (void (*)())NULL
)
1564 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1568 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1569 max(r1
->top
,ybot
), r1
->bottom
);
1571 } while (r1
!= r1End
);
1574 else if ((r2
!= r2End
) && (nonOverlap2Func
!= (void (*)())NULL
))
1579 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1583 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1584 max(r2
->top
,ybot
), r2
->bottom
);
1586 } while (r2
!= r2End
);
1589 if (newReg
->numRects
!= curBand
)
1591 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1595 * A bit of cleanup. To keep regions from growing without bound,
1596 * we shrink the array of rectangles to match the new number of
1597 * rectangles in the region. This never goes to 0, however...
1599 * Only do this stuff if the number of rectangles allocated is more than
1600 * twice the number of rectangles in the region (a simple optimization...).
1602 if ((newReg
->numRects
< (newReg
->size
>> 1)) && (newReg
->numRects
> 2))
1604 if (REGION_NOT_EMPTY(newReg
))
1606 RECT
*prev_rects
= newReg
->rects
;
1607 newReg
->size
= newReg
->numRects
;
1608 newReg
->rects
= HeapReAlloc( GetProcessHeap(), 0, newReg
->rects
,
1609 sizeof(RECT
) * newReg
->size
);
1610 if (! newReg
->rects
)
1611 newReg
->rects
= prev_rects
;
1616 * No point in doing the extra work involved in an Xrealloc if
1617 * the region is empty
1620 HeapFree( GetProcessHeap(), 0, newReg
->rects
);
1621 newReg
->rects
= HeapAlloc( GetProcessHeap(), 0, sizeof(RECT
) );
1624 HeapFree( GetProcessHeap(), 0, oldRects
);
1628 /***********************************************************************
1629 * Region Intersection
1630 ***********************************************************************/
1633 /***********************************************************************
1636 * Handle an overlapping band for REGION_Intersect.
1642 * Rectangles may be added to the region.
1645 static void REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1646 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1652 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1654 while ((r1
!= r1End
) && (r2
!= r2End
))
1656 left
= max(r1
->left
, r2
->left
);
1657 right
= min(r1
->right
, r2
->right
);
1660 * If there's any overlap between the two rectangles, add that
1661 * overlap to the new region.
1662 * There's no need to check for subsumption because the only way
1663 * such a need could arise is if some region has two rectangles
1664 * right next to each other. Since that should never happen...
1668 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1669 pNextRect
->left
= left
;
1670 pNextRect
->top
= top
;
1671 pNextRect
->right
= right
;
1672 pNextRect
->bottom
= bottom
;
1673 pReg
->numRects
+= 1;
1678 * Need to advance the pointers. Shift the one that extends
1679 * to the right the least, since the other still has a chance to
1680 * overlap with that region's next rectangle, if you see what I mean.
1682 if (r1
->right
< r2
->right
)
1686 else if (r2
->right
< r1
->right
)
1699 /***********************************************************************
1700 * REGION_IntersectRegion
1702 static void REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1705 /* check for trivial reject */
1706 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1707 (!EXTENTCHECK(®1
->extents
, ®2
->extents
)))
1708 newReg
->numRects
= 0;
1710 REGION_RegionOp (newReg
, reg1
, reg2
,
1711 (voidProcp
) REGION_IntersectO
, (voidProcp
) NULL
, (voidProcp
) NULL
);
1714 * Can't alter newReg's extents before we call miRegionOp because
1715 * it might be one of the source regions and miRegionOp depends
1716 * on the extents of those regions being the same. Besides, this
1717 * way there's no checking against rectangles that will be nuked
1718 * due to coalescing, so we have to examine fewer rectangles.
1720 REGION_SetExtents(newReg
);
1723 /***********************************************************************
1725 ***********************************************************************/
1727 /***********************************************************************
1730 * Handle a non-overlapping band for the union operation. Just
1731 * Adds the rectangles into the region. Doesn't have to check for
1732 * subsumption or anything.
1738 * pReg->numRects is incremented and the final rectangles overwritten
1739 * with the rectangles we're passed.
1742 static void REGION_UnionNonO (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1743 INT top
, INT bottom
)
1747 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1751 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1752 pNextRect
->left
= r
->left
;
1753 pNextRect
->top
= top
;
1754 pNextRect
->right
= r
->right
;
1755 pNextRect
->bottom
= bottom
;
1756 pReg
->numRects
+= 1;
1763 /***********************************************************************
1766 * Handle an overlapping band for the union operation. Picks the
1767 * left-most rectangle each time and merges it into the region.
1773 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1777 static void REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1778 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1782 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1784 #define MERGERECT(r) \
1785 if ((pReg->numRects != 0) && \
1786 (pNextRect[-1].top == top) && \
1787 (pNextRect[-1].bottom == bottom) && \
1788 (pNextRect[-1].right >= r->left)) \
1790 if (pNextRect[-1].right < r->right) \
1792 pNextRect[-1].right = r->right; \
1797 MEMCHECK(pReg, pNextRect, pReg->rects); \
1798 pNextRect->top = top; \
1799 pNextRect->bottom = bottom; \
1800 pNextRect->left = r->left; \
1801 pNextRect->right = r->right; \
1802 pReg->numRects += 1; \
1807 while ((r1
!= r1End
) && (r2
!= r2End
))
1809 if (r1
->left
< r2
->left
)
1824 } while (r1
!= r1End
);
1826 else while (r2
!= r2End
)
1833 /***********************************************************************
1834 * REGION_UnionRegion
1836 static void REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1839 /* checks all the simple cases */
1842 * Region 1 and 2 are the same or region 1 is empty
1844 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
1847 REGION_CopyRegion(newReg
, reg2
);
1852 * if nothing to union (region 2 empty)
1854 if (!(reg2
->numRects
))
1857 REGION_CopyRegion(newReg
, reg1
);
1862 * Region 1 completely subsumes region 2
1864 if ((reg1
->numRects
== 1) &&
1865 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
1866 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
1867 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
1868 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
1871 REGION_CopyRegion(newReg
, reg1
);
1876 * Region 2 completely subsumes region 1
1878 if ((reg2
->numRects
== 1) &&
1879 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
1880 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
1881 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
1882 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
1885 REGION_CopyRegion(newReg
, reg2
);
1889 REGION_RegionOp (newReg
, reg1
, reg2
, (voidProcp
) REGION_UnionO
,
1890 (voidProcp
) REGION_UnionNonO
, (voidProcp
) REGION_UnionNonO
);
1892 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
1893 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
1894 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
1895 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
1898 /***********************************************************************
1899 * Region Subtraction
1900 ***********************************************************************/
1902 /***********************************************************************
1903 * REGION_SubtractNonO1
1905 * Deal with non-overlapping band for subtraction. Any parts from
1906 * region 2 we discard. Anything from region 1 we add to the region.
1912 * pReg may be affected.
1915 static void REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1916 INT top
, INT bottom
)
1920 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1924 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1925 pNextRect
->left
= r
->left
;
1926 pNextRect
->top
= top
;
1927 pNextRect
->right
= r
->right
;
1928 pNextRect
->bottom
= bottom
;
1929 pReg
->numRects
+= 1;
1937 /***********************************************************************
1940 * Overlapping band subtraction. x1 is the left-most point not yet
1947 * pReg may have rectangles added to it.
1950 static void REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1951 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1957 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1959 while ((r1
!= r1End
) && (r2
!= r2End
))
1961 if (r2
->right
<= left
)
1964 * Subtrahend missed the boat: go to next subtrahend.
1968 else if (r2
->left
<= left
)
1971 * Subtrahend preceeds minuend: nuke left edge of minuend.
1974 if (left
>= r1
->right
)
1977 * Minuend completely covered: advance to next minuend and
1978 * reset left fence to edge of new minuend.
1987 * Subtrahend now used up since it doesn't extend beyond
1993 else if (r2
->left
< r1
->right
)
1996 * Left part of subtrahend covers part of minuend: add uncovered
1997 * part of minuend to region and skip to next subtrahend.
1999 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2000 pNextRect
->left
= left
;
2001 pNextRect
->top
= top
;
2002 pNextRect
->right
= r2
->left
;
2003 pNextRect
->bottom
= bottom
;
2004 pReg
->numRects
+= 1;
2007 if (left
>= r1
->right
)
2010 * Minuend used up: advance to new...
2019 * Subtrahend used up
2027 * Minuend used up: add any remaining piece before advancing.
2029 if (r1
->right
> left
)
2031 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2032 pNextRect
->left
= left
;
2033 pNextRect
->top
= top
;
2034 pNextRect
->right
= r1
->right
;
2035 pNextRect
->bottom
= bottom
;
2036 pReg
->numRects
+= 1;
2045 * Add remaining minuend rectangles to region.
2049 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2050 pNextRect
->left
= left
;
2051 pNextRect
->top
= top
;
2052 pNextRect
->right
= r1
->right
;
2053 pNextRect
->bottom
= bottom
;
2054 pReg
->numRects
+= 1;
2065 /***********************************************************************
2066 * REGION_SubtractRegion
2068 * Subtract regS from regM and leave the result in regD.
2069 * S stands for subtrahend, M for minuend and D for difference.
2075 * regD is overwritten.
2078 static void REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
,
2081 /* check for trivial reject */
2082 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2083 (!EXTENTCHECK(®M
->extents
, ®S
->extents
)) )
2085 REGION_CopyRegion(regD
, regM
);
2089 REGION_RegionOp (regD
, regM
, regS
, (voidProcp
) REGION_SubtractO
,
2090 (voidProcp
) REGION_SubtractNonO1
, (voidProcp
) NULL
);
2093 * Can't alter newReg's extents before we call miRegionOp because
2094 * it might be one of the source regions and miRegionOp depends
2095 * on the extents of those regions being the unaltered. Besides, this
2096 * way there's no checking against rectangles that will be nuked
2097 * due to coalescing, so we have to examine fewer rectangles.
2099 REGION_SetExtents (regD
);
2102 /***********************************************************************
2105 static void REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
,
2108 WINEREGION
*tra
, *trb
;
2110 if ((! (tra
= REGION_AllocWineRegion(sra
->numRects
+ 1))) ||
2111 (! (trb
= REGION_AllocWineRegion(srb
->numRects
+ 1))))
2113 REGION_SubtractRegion(tra
,sra
,srb
);
2114 REGION_SubtractRegion(trb
,srb
,sra
);
2115 REGION_UnionRegion(dr
,tra
,trb
);
2116 REGION_DestroyWineRegion(tra
);
2117 REGION_DestroyWineRegion(trb
);
2121 /**************************************************************************
2125 *************************************************************************/
2127 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2128 #define SMALL_COORDINATE 0x80000000
2130 /***********************************************************************
2131 * REGION_InsertEdgeInET
2133 * Insert the given edge into the edge table.
2134 * First we must find the correct bucket in the
2135 * Edge table, then find the right slot in the
2136 * bucket. Finally, we can insert it.
2139 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2140 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2143 EdgeTableEntry
*start
, *prev
;
2144 ScanLineList
*pSLL
, *pPrevSLL
;
2145 ScanLineListBlock
*tmpSLLBlock
;
2148 * find the right bucket to put the edge into
2150 pPrevSLL
= &ET
->scanlines
;
2151 pSLL
= pPrevSLL
->next
;
2152 while (pSLL
&& (pSLL
->scanline
< scanline
))
2159 * reassign pSLL (pointer to ScanLineList) if necessary
2161 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2163 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2165 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2168 WARN("Can't alloc SLLB\n");
2171 (*SLLBlock
)->next
= tmpSLLBlock
;
2172 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2173 *SLLBlock
= tmpSLLBlock
;
2176 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2178 pSLL
->next
= pPrevSLL
->next
;
2179 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
2180 pPrevSLL
->next
= pSLL
;
2182 pSLL
->scanline
= scanline
;
2185 * now insert the edge in the right bucket
2187 prev
= (EdgeTableEntry
*)NULL
;
2188 start
= pSLL
->edgelist
;
2189 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
2192 start
= start
->next
;
2199 pSLL
->edgelist
= ETE
;
2202 /***********************************************************************
2203 * REGION_CreateEdgeTable
2205 * This routine creates the edge table for
2206 * scan converting polygons.
2207 * The Edge Table (ET) looks like:
2211 * | ymax | ScanLineLists
2212 * |scanline|-->------------>-------------->...
2213 * -------- |scanline| |scanline|
2214 * |edgelist| |edgelist|
2215 * --------- ---------
2219 * list of ETEs list of ETEs
2221 * where ETE is an EdgeTableEntry data structure,
2222 * and there is one ScanLineList per scanline at
2223 * which an edge is initially entered.
2226 static void REGION_CreateETandAET(const INT
*Count
, INT nbpolygons
,
2227 const POINT
*pts
, EdgeTable
*ET
, EdgeTableEntry
*AET
,
2228 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2230 const POINT
*top
, *bottom
;
2231 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2238 * initialize the Active Edge Table
2240 AET
->next
= (EdgeTableEntry
*)NULL
;
2241 AET
->back
= (EdgeTableEntry
*)NULL
;
2242 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2243 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
2246 * initialize the Edge Table.
2248 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
2249 ET
->ymax
= SMALL_COORDINATE
;
2250 ET
->ymin
= LARGE_COORDINATE
;
2251 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2254 for(poly
= 0; poly
< nbpolygons
; poly
++)
2256 count
= Count
[poly
];
2264 * for each vertex in the array of points.
2265 * In this loop we are dealing with two vertices at
2266 * a time -- these make up one edge of the polygon.
2273 * find out which point is above and which is below.
2275 if (PrevPt
->y
> CurrPt
->y
)
2277 bottom
= PrevPt
, top
= CurrPt
;
2278 pETEs
->ClockWise
= 0;
2282 bottom
= CurrPt
, top
= PrevPt
;
2283 pETEs
->ClockWise
= 1;
2287 * don't add horizontal edges to the Edge table.
2289 if (bottom
->y
!= top
->y
)
2291 pETEs
->ymax
= bottom
->y
-1;
2292 /* -1 so we don't get last scanline */
2295 * initialize integer edge algorithm
2297 dy
= bottom
->y
- top
->y
;
2298 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
2300 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2303 if (PrevPt
->y
> ET
->ymax
)
2304 ET
->ymax
= PrevPt
->y
;
2305 if (PrevPt
->y
< ET
->ymin
)
2306 ET
->ymin
= PrevPt
->y
;
2315 /***********************************************************************
2318 * This routine moves EdgeTableEntries from the
2319 * EdgeTable into the Active Edge Table,
2320 * leaving them sorted by smaller x coordinate.
2323 static void REGION_loadAET(EdgeTableEntry
*AET
, EdgeTableEntry
*ETEs
)
2325 EdgeTableEntry
*pPrevAET
;
2326 EdgeTableEntry
*tmp
;
2332 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
2341 ETEs
->back
= pPrevAET
;
2342 pPrevAET
->next
= ETEs
;
2349 /***********************************************************************
2350 * REGION_computeWAET
2352 * This routine links the AET by the
2353 * nextWETE (winding EdgeTableEntry) link for
2354 * use by the winding number rule. The final
2355 * Active Edge Table (AET) might look something
2359 * ---------- --------- ---------
2360 * |ymax | |ymax | |ymax |
2361 * | ... | |... | |... |
2362 * |next |->|next |->|next |->...
2363 * |nextWETE| |nextWETE| |nextWETE|
2364 * --------- --------- ^--------
2366 * V-------------------> V---> ...
2369 static void REGION_computeWAET(EdgeTableEntry
*AET
)
2371 register EdgeTableEntry
*pWETE
;
2372 register int inside
= 1;
2373 register int isInside
= 0;
2375 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2385 if ((!inside
&& !isInside
) ||
2386 ( inside
&& isInside
))
2388 pWETE
->nextWETE
= AET
;
2394 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
2397 /***********************************************************************
2398 * REGION_InsertionSort
2400 * Just a simple insertion sort using
2401 * pointers and back pointers to sort the Active
2405 static BOOL
REGION_InsertionSort(EdgeTableEntry
*AET
)
2407 EdgeTableEntry
*pETEchase
;
2408 EdgeTableEntry
*pETEinsert
;
2409 EdgeTableEntry
*pETEchaseBackTMP
;
2410 BOOL changed
= FALSE
;
2417 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
2418 pETEchase
= pETEchase
->back
;
2421 if (pETEchase
!= pETEinsert
)
2423 pETEchaseBackTMP
= pETEchase
->back
;
2424 pETEinsert
->back
->next
= AET
;
2426 AET
->back
= pETEinsert
->back
;
2427 pETEinsert
->next
= pETEchase
;
2428 pETEchase
->back
->next
= pETEinsert
;
2429 pETEchase
->back
= pETEinsert
;
2430 pETEinsert
->back
= pETEchaseBackTMP
;
2437 /***********************************************************************
2438 * REGION_FreeStorage
2442 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2444 ScanLineListBlock
*tmpSLLBlock
;
2448 tmpSLLBlock
= pSLLBlock
->next
;
2449 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2450 pSLLBlock
= tmpSLLBlock
;
2455 /***********************************************************************
2456 * REGION_PtsToRegion
2458 * Create an array of rectangles from a list of points.
2460 static int REGION_PtsToRegion(int numFullPtBlocks
, int iCurPtBlock
,
2461 POINTBLOCK
*FirstPtBlock
, WINEREGION
*reg
)
2465 POINTBLOCK
*CurPtBlock
;
2470 extents
= ®
->extents
;
2472 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
2474 if (!(reg
->rects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
,
2475 sizeof(RECT
) * numRects
)))
2478 reg
->size
= numRects
;
2479 CurPtBlock
= FirstPtBlock
;
2480 rects
= reg
->rects
- 1;
2482 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2484 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--) {
2485 /* the loop uses 2 points per iteration */
2486 i
= NUMPTSTOBUFFER
>> 1;
2487 if (!numFullPtBlocks
)
2488 i
= iCurPtBlock
>> 1;
2489 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2) {
2490 if (pts
->x
== pts
[1].x
)
2492 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2493 pts
[1].x
== rects
->right
&&
2494 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2495 (i
&& pts
[2].y
> pts
[1].y
)) {
2496 rects
->bottom
= pts
[1].y
+ 1;
2501 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2502 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2503 if (rects
->left
< extents
->left
)
2504 extents
->left
= rects
->left
;
2505 if (rects
->right
> extents
->right
)
2506 extents
->right
= rects
->right
;
2508 CurPtBlock
= CurPtBlock
->next
;
2512 extents
->top
= reg
->rects
->top
;
2513 extents
->bottom
= rects
->bottom
;
2518 extents
->bottom
= 0;
2520 reg
->numRects
= numRects
;
2525 /***********************************************************************
2526 * CreatePolyPolygonRgn (GDI32.@)
2528 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2529 INT nbpolygons
, INT mode
)
2534 register EdgeTableEntry
*pAET
; /* Active Edge Table */
2535 register INT y
; /* current scanline */
2536 register int iPts
= 0; /* number of pts in buffer */
2537 register EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
2538 register ScanLineList
*pSLL
; /* current scanLineList */
2539 register POINT
*pts
; /* output buffer */
2540 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
2541 EdgeTable ET
; /* header node for ET */
2542 EdgeTableEntry AET
; /* header node for AET */
2543 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2544 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2545 int fixWAET
= FALSE
;
2546 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
2547 POINTBLOCK
*tmpPtBlock
;
2548 int numFullPtBlocks
= 0;
2551 if(!(hrgn
= REGION_CreateRegion(nbpolygons
)))
2553 obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
2556 /* special case a rectangle */
2558 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2559 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2560 (((Pts
[0].y
== Pts
[1].y
) &&
2561 (Pts
[1].x
== Pts
[2].x
) &&
2562 (Pts
[2].y
== Pts
[3].y
) &&
2563 (Pts
[3].x
== Pts
[0].x
)) ||
2564 ((Pts
[0].x
== Pts
[1].x
) &&
2565 (Pts
[1].y
== Pts
[2].y
) &&
2566 (Pts
[2].x
== Pts
[3].x
) &&
2567 (Pts
[3].y
== Pts
[0].y
))))
2569 SetRectRgn( hrgn
, min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2570 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2571 GDI_ReleaseObj( hrgn
);
2575 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2576 total
+= Count
[poly
];
2577 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2579 REGION_DeleteObject( hrgn
, obj
);
2582 pts
= FirstPtBlock
.pts
;
2583 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
2584 pSLL
= ET
.scanlines
.next
;
2585 curPtBlock
= &FirstPtBlock
;
2587 if (mode
!= WINDING
) {
2591 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2593 * Add a new edge to the active edge table when we
2594 * get to the next edge.
2596 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2597 REGION_loadAET(&AET
, pSLL
->edgelist
);
2604 * for each active edge
2607 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2611 * send out the buffer
2613 if (iPts
== NUMPTSTOBUFFER
) {
2614 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK
));
2616 WARN("Can't alloc tPB\n");
2619 curPtBlock
->next
= tmpPtBlock
;
2620 curPtBlock
= tmpPtBlock
;
2621 pts
= curPtBlock
->pts
;
2625 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
2627 REGION_InsertionSort(&AET
);
2634 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2636 * Add a new edge to the active edge table when we
2637 * get to the next edge.
2639 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2640 REGION_loadAET(&AET
, pSLL
->edgelist
);
2641 REGION_computeWAET(&AET
);
2649 * for each active edge
2653 * add to the buffer only those edges that
2654 * are in the Winding active edge table.
2656 if (pWETE
== pAET
) {
2657 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2661 * send out the buffer
2663 if (iPts
== NUMPTSTOBUFFER
) {
2664 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0,
2665 sizeof(POINTBLOCK
) );
2667 WARN("Can't alloc tPB\n");
2668 REGION_DeleteObject( hrgn
, obj
);
2671 curPtBlock
->next
= tmpPtBlock
;
2672 curPtBlock
= tmpPtBlock
;
2673 pts
= curPtBlock
->pts
;
2674 numFullPtBlocks
++; iPts
= 0;
2676 pWETE
= pWETE
->nextWETE
;
2678 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
2682 * recompute the winding active edge table if
2683 * we just resorted or have exited an edge.
2685 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2686 REGION_computeWAET(&AET
);
2691 REGION_FreeStorage(SLLBlock
.next
);
2692 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
2694 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;) {
2695 tmpPtBlock
= curPtBlock
->next
;
2696 HeapFree( GetProcessHeap(), 0, curPtBlock
);
2697 curPtBlock
= tmpPtBlock
;
2699 HeapFree( GetProcessHeap(), 0, pETEs
);
2700 GDI_ReleaseObj( hrgn
);
2705 /***********************************************************************
2706 * CreatePolygonRgn (GDI32.@)
2708 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2711 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);