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
11 /************************************************************************
13 Copyright (c) 1987, 1988 X Consortium
15 Permission is hereby granted, free of charge, to any person obtaining a copy
16 of this software and associated documentation files (the "Software"), to deal
17 in the Software without restriction, including without limitation the rights
18 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
19 copies of the Software, and to permit persons to whom the Software is
20 furnished to do so, subject to the following conditions:
22 The above copyright notice and this permission notice shall be included in
23 all copies or substantial portions of the Software.
25 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
29 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
30 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 Except as contained in this notice, the name of the X Consortium shall not be
33 used in advertising or otherwise to promote the sale, use or other dealings
34 in this Software without prior written authorization from the X Consortium.
37 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
41 Permission to use, copy, modify, and distribute this software and its
42 documentation for any purpose and without fee is hereby granted,
43 provided that the above copyright notice appear in all copies and that
44 both that copyright notice and this permission notice appear in
45 supporting documentation, and that the name of Digital not be
46 used in advertising or publicity pertaining to distribution of the
47 software without specific, written prior permission.
49 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
50 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
51 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
52 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
53 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
54 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
57 ************************************************************************/
59 * The functions in this file implement the Region abstraction, similar to one
60 * used in the X11 sample server. A Region is simply an area, as the name
61 * implies, and is implemented as a "y-x-banded" array of rectangles. To
62 * explain: Each Region is made up of a certain number of rectangles sorted
63 * by y coordinate first, and then by x coordinate.
65 * Furthermore, the rectangles are banded such that every rectangle with a
66 * given upper-left y coordinate (y1) will have the same lower-right y
67 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
68 * will span the entire vertical distance of the band. This means that some
69 * areas that could be merged into a taller rectangle will be represented as
70 * several shorter rectangles to account for shorter rectangles to its left
71 * or right but within its "vertical scope".
73 * An added constraint on the rectangles is that they must cover as much
74 * horizontal area as possible. E.g. no two rectangles in a band are allowed
77 * Whenever possible, bands will be merged together to cover a greater vertical
78 * distance (and thus reduce the number of rectangles). Two bands can be merged
79 * only if the bottom of one touches the top of the other and they have
80 * rectangles in the same places (of the same width, of course). This maintains
81 * the y-x-banding that's so nice to have...
88 #include "debugtools.h"
93 DEFAULT_DEBUG_CHANNEL(region
);
95 /* 1 if two RECTs overlap.
96 * 0 if two RECTs do not overlap.
98 #define EXTENTCHECK(r1, r2) \
99 ((r1)->right > (r2)->left && \
100 (r1)->left < (r2)->right && \
101 (r1)->bottom > (r2)->top && \
102 (r1)->top < (r2)->bottom)
105 * Check to see if there is enough memory in the present region.
107 #define MEMCHECK(reg, rect, firstrect){\
108 if ((reg)->numRects >= ((reg)->size - 1)){\
109 (firstrect) = HeapReAlloc( GetProcessHeap(), 0, \
110 (firstrect), (2 * (sizeof(RECT)) * ((reg)->size)));\
111 if ((firstrect) == 0)\
114 (rect) = &(firstrect)[(reg)->numRects];\
118 #define EMPTY_REGION(pReg) { \
119 (pReg)->numRects = 0; \
120 (pReg)->extents.left = (pReg)->extents.top = 0; \
121 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
122 (pReg)->type = NULLREGION; \
125 #define REGION_NOT_EMPTY(pReg) pReg->numRects
127 #define INRECT(r, x, y) \
128 ( ( ((r).right > x)) && \
129 ( ((r).left <= x)) && \
130 ( ((r).bottom > y)) && \
135 * number of points to buffer before sending them off
136 * to scanlines() : Must be an even number
138 #define NUMPTSTOBUFFER 200
141 * used to allocate buffers for points and link
142 * the buffers together
145 typedef struct _POINTBLOCK
{
146 POINT pts
[NUMPTSTOBUFFER
];
147 struct _POINTBLOCK
*next
;
153 * This file contains a few macros to help track
154 * the edge of a filled object. The object is assumed
155 * to be filled in scanline order, and thus the
156 * algorithm used is an extension of Bresenham's line
157 * drawing algorithm which assumes that y is always the
159 * Since these pieces of code are the same for any filled shape,
160 * it is more convenient to gather the library in one
161 * place, but since these pieces of code are also in
162 * the inner loops of output primitives, procedure call
163 * overhead is out of the question.
164 * See the author for a derivation if needed.
169 * In scan converting polygons, we want to choose those pixels
170 * which are inside the polygon. Thus, we add .5 to the starting
171 * x coordinate for both left and right edges. Now we choose the
172 * first pixel which is inside the pgon for the left edge and the
173 * first pixel which is outside the pgon for the right edge.
174 * Draw the left pixel, but not the right.
176 * How to add .5 to the starting x coordinate:
177 * If the edge is moving to the right, then subtract dy from the
178 * error term from the general form of the algorithm.
179 * If the edge is moving to the left, then add dy to the error term.
181 * The reason for the difference between edges moving to the left
182 * and edges moving to the right is simple: If an edge is moving
183 * to the right, then we want the algorithm to flip immediately.
184 * If it is moving to the left, then we don't want it to flip until
185 * we traverse an entire pixel.
187 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
188 int dx; /* local storage */ \
191 * if the edge is horizontal, then it is ignored \
192 * and assumed not to be processed. Otherwise, do this stuff. \
196 dx = (x2) - xStart; \
200 incr1 = -2 * dx + 2 * (dy) * m1; \
201 incr2 = -2 * dx + 2 * (dy) * m; \
202 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
206 incr1 = 2 * dx - 2 * (dy) * m1; \
207 incr2 = 2 * dx - 2 * (dy) * m; \
208 d = -2 * m * (dy) + 2 * dx; \
213 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
236 * This structure contains all of the information needed
237 * to run the bresenham algorithm.
238 * The variables may be hardcoded into the declarations
239 * instead of using this structure to make use of
240 * register declarations.
243 INT minor_axis
; /* minor axis */
244 INT d
; /* decision variable */
245 INT m
, m1
; /* slope and slope+1 */
246 INT incr1
, incr2
; /* error increments */
250 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
251 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
252 bres.m, bres.m1, bres.incr1, bres.incr2)
254 #define BRESINCRPGONSTRUCT(bres) \
255 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
260 * These are the data structures needed to scan
261 * convert regions. Two different scan conversion
262 * methods are available -- the even-odd method, and
263 * the winding number method.
264 * The even-odd rule states that a point is inside
265 * the polygon if a ray drawn from that point in any
266 * direction will pass through an odd number of
268 * By the winding number rule, a point is decided
269 * to be inside the polygon if a ray drawn from that
270 * point in any direction passes through a different
271 * number of clockwise and counter-clockwise path
274 * These data structures are adapted somewhat from
275 * the algorithm in (Foley/Van Dam) for scan converting
277 * The basic algorithm is to start at the top (smallest y)
278 * of the polygon, stepping down to the bottom of
279 * the polygon by incrementing the y coordinate. We
280 * keep a list of edges which the current scanline crosses,
281 * sorted by x. This list is called the Active Edge Table (AET)
282 * As we change the y-coordinate, we update each entry in
283 * in the active edge table to reflect the edges new xcoord.
284 * This list must be sorted at each scanline in case
285 * two edges intersect.
286 * We also keep a data structure known as the Edge Table (ET),
287 * which keeps track of all the edges which the current
288 * scanline has not yet reached. The ET is basically a
289 * list of ScanLineList structures containing a list of
290 * edges which are entered at a given scanline. There is one
291 * ScanLineList per scanline at which an edge is entered.
292 * When we enter a new edge, we move it from the ET to the AET.
294 * From the AET, we can implement the even-odd rule as in
296 * The winding number rule is a little trickier. We also
297 * keep the EdgeTableEntries in the AET linked by the
298 * nextWETE (winding EdgeTableEntry) link. This allows
299 * the edges to be linked just as before for updating
300 * purposes, but only uses the edges linked by the nextWETE
301 * link as edges representing spans of the polygon to
302 * drawn (as with the even-odd rule).
306 * for the winding number rule
309 #define COUNTERCLOCKWISE -1
311 typedef struct _EdgeTableEntry
{
312 INT ymax
; /* ycoord at which we exit this edge. */
313 BRESINFO bres
; /* Bresenham info to run the edge */
314 struct _EdgeTableEntry
*next
; /* next in the list */
315 struct _EdgeTableEntry
*back
; /* for insertion sort */
316 struct _EdgeTableEntry
*nextWETE
; /* for winding num rule */
317 int ClockWise
; /* flag for winding number rule */
321 typedef struct _ScanLineList
{
322 INT scanline
; /* the scanline represented */
323 EdgeTableEntry
*edgelist
; /* header node */
324 struct _ScanLineList
*next
; /* next in the list */
329 INT ymax
; /* ymax for the polygon */
330 INT ymin
; /* ymin for the polygon */
331 ScanLineList scanlines
; /* header node */
336 * Here is a struct to help with storage allocation
337 * so we can allocate a big chunk at a time, and then take
338 * pieces from this heap when we need to.
340 #define SLLSPERBLOCK 25
342 typedef struct _ScanLineListBlock
{
343 ScanLineList SLLs
[SLLSPERBLOCK
];
344 struct _ScanLineListBlock
*next
;
350 * a few macros for the inner loops of the fill code where
351 * performance considerations don't allow a procedure call.
353 * Evaluate the given edge at the given scanline.
354 * If the edge has expired, then we leave it and fix up
355 * the active edge table; otherwise, we increment the
356 * x value to be ready for the next scanline.
357 * The winding number rule is in effect, so we must notify
358 * the caller when the edge has been removed so he
359 * can reorder the Winding Active Edge Table.
361 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
362 if (pAET->ymax == y) { /* leaving this edge */ \
363 pPrevAET->next = pAET->next; \
364 pAET = pPrevAET->next; \
367 pAET->back = pPrevAET; \
370 BRESINCRPGONSTRUCT(pAET->bres); \
378 * Evaluate the given edge at the given scanline.
379 * If the edge has expired, then we leave it and fix up
380 * the active edge table; otherwise, we increment the
381 * x value to be ready for the next scanline.
382 * The even-odd rule is in effect.
384 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
385 if (pAET->ymax == y) { /* leaving this edge */ \
386 pPrevAET->next = pAET->next; \
387 pAET = pPrevAET->next; \
389 pAET->back = pPrevAET; \
392 BRESINCRPGONSTRUCT(pAET->bres); \
398 typedef void (*voidProcp
)();
400 /* Note the parameter order is different from the X11 equivalents */
402 static void REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
403 static void REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
404 static void REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
405 static void REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
406 static void REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
407 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
409 #define RGN_DEFAULT_RECTS 2
411 /***********************************************************************
413 * Outputs the contents of a WINEREGION
415 static void REGION_DumpRegion(WINEREGION
*pReg
)
417 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
419 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg
,
420 pReg
->extents
.left
, pReg
->extents
.top
,
421 pReg
->extents
.right
, pReg
->extents
.bottom
, pReg
->numRects
);
422 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
423 TRACE("\t%d,%d - %d,%d\n", pRect
->left
, pRect
->top
,
424 pRect
->right
, pRect
->bottom
);
429 /***********************************************************************
430 * REGION_AllocWineRegion
431 * Create a new empty WINEREGION.
433 static WINEREGION
*REGION_AllocWineRegion( INT n
)
437 if ((pReg
= HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION
))))
439 if ((pReg
->rects
= HeapAlloc(GetProcessHeap(), 0, n
* sizeof( RECT
))))
445 HeapFree(GetProcessHeap(), 0, pReg
);
451 /***********************************************************************
452 * REGION_CreateRegion
453 * Create a new empty region.
455 static HRGN
REGION_CreateRegion( INT n
)
460 if(!(obj
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
, &hrgn
))) return 0;
461 if(!(obj
->rgn
= REGION_AllocWineRegion(n
))) {
462 GDI_FreeObject( hrgn
, obj
);
465 GDI_ReleaseObj( hrgn
);
470 /***********************************************************************
471 * REGION_DestroyWineRegion
473 static void REGION_DestroyWineRegion( WINEREGION
* pReg
)
475 HeapFree( GetProcessHeap(), 0, pReg
->rects
);
476 HeapFree( GetProcessHeap(), 0, pReg
);
480 /***********************************************************************
481 * REGION_DeleteObject
483 BOOL
REGION_DeleteObject( HRGN hrgn
, RGNOBJ
* obj
)
485 TRACE(" %04x\n", hrgn
);
487 REGION_DestroyWineRegion( obj
->rgn
);
488 return GDI_FreeObject( hrgn
, obj
);
491 /***********************************************************************
492 * OffsetRgn16 (GDI.101)
494 INT16 WINAPI
OffsetRgn16( HRGN16 hrgn
, INT16 x
, INT16 y
)
496 return OffsetRgn( hrgn
, x
, y
);
499 /***********************************************************************
500 * OffsetRgn (GDI32.256)
502 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
504 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
507 TRACE("%04x %d,%d\n", hrgn
, x
, y
);
513 int nbox
= obj
->rgn
->numRects
;
514 RECT
*pbox
= obj
->rgn
->rects
;
524 obj
->rgn
->extents
.left
+= x
;
525 obj
->rgn
->extents
.right
+= x
;
526 obj
->rgn
->extents
.top
+= y
;
527 obj
->rgn
->extents
.bottom
+= y
;
530 ret
= obj
->rgn
->type
;
531 GDI_ReleaseObj( hrgn
);
536 /***********************************************************************
537 * GetRgnBox16 (GDI.134)
539 INT16 WINAPI
GetRgnBox16( HRGN16 hrgn
, LPRECT16 rect
)
542 INT16 ret
= (INT16
)GetRgnBox( hrgn
, &r
);
543 CONV_RECT32TO16( &r
, rect
);
547 /***********************************************************************
548 * GetRgnBox (GDI32.219)
550 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
552 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
556 TRACE(" %04x\n", hrgn
);
557 rect
->left
= obj
->rgn
->extents
.left
;
558 rect
->top
= obj
->rgn
->extents
.top
;
559 rect
->right
= obj
->rgn
->extents
.right
;
560 rect
->bottom
= obj
->rgn
->extents
.bottom
;
561 ret
= obj
->rgn
->type
;
562 GDI_ReleaseObj(hrgn
);
569 /***********************************************************************
570 * CreateRectRgn16 (GDI.64)
572 * NOTE: Doesn't call CreateRectRgn because of differences in SetRectRgn16/32
574 HRGN16 WINAPI
CreateRectRgn16(INT16 left
, INT16 top
, INT16 right
, INT16 bottom
)
578 if (!(hrgn
= (HRGN16
)REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
581 SetRectRgn16(hrgn
, left
, top
, right
, bottom
);
586 /***********************************************************************
587 * CreateRectRgn (GDI32.59)
589 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
593 /* Allocate 2 rects by default to reduce the number of reallocs */
595 if (!(hrgn
= REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
598 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
602 /***********************************************************************
603 * CreateRectRgnIndirect16 (GDI.65)
605 HRGN16 WINAPI
CreateRectRgnIndirect16( const RECT16
* rect
)
607 return CreateRectRgn16( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
611 /***********************************************************************
612 * CreateRectRgnIndirect (GDI32.60)
614 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
616 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
620 /***********************************************************************
621 * SetRectRgn16 (GDI.172)
623 * NOTE: Win 3.1 sets region to empty if left > right
625 VOID WINAPI
SetRectRgn16( HRGN16 hrgn
, INT16 left
, INT16 top
,
626 INT16 right
, INT16 bottom
)
629 SetRectRgn( hrgn
, left
, top
, right
, bottom
);
631 SetRectRgn( hrgn
, 0, 0, 0, 0 );
635 /***********************************************************************
636 * SetRectRgn (GDI32.332)
638 * Allows either or both left and top to be greater than right or bottom.
640 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
641 INT right
, INT bottom
)
645 TRACE(" %04x %d,%d-%d,%d\n",
646 hrgn
, left
, top
, right
, bottom
);
648 if (!(obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return FALSE
;
650 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
651 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
653 if((left
!= right
) && (top
!= bottom
))
655 obj
->rgn
->rects
->left
= obj
->rgn
->extents
.left
= left
;
656 obj
->rgn
->rects
->top
= obj
->rgn
->extents
.top
= top
;
657 obj
->rgn
->rects
->right
= obj
->rgn
->extents
.right
= right
;
658 obj
->rgn
->rects
->bottom
= obj
->rgn
->extents
.bottom
= bottom
;
659 obj
->rgn
->numRects
= 1;
660 obj
->rgn
->type
= SIMPLEREGION
;
663 EMPTY_REGION(obj
->rgn
);
665 GDI_ReleaseObj( hrgn
);
670 /***********************************************************************
671 * CreateRoundRectRgn16 (GDI.444)
673 * If either ellipse dimension is zero we call CreateRectRgn16 for its
674 * `special' behaviour. -ve ellipse dimensions can result in GPFs under win3.1
675 * we just let CreateRoundRectRgn convert them to +ve values.
678 HRGN16 WINAPI
CreateRoundRectRgn16( INT16 left
, INT16 top
,
679 INT16 right
, INT16 bottom
,
680 INT16 ellipse_width
, INT16 ellipse_height
)
682 if( ellipse_width
== 0 || ellipse_height
== 0 )
683 return CreateRectRgn16( left
, top
, right
, bottom
);
685 return (HRGN16
)CreateRoundRectRgn( left
, top
, right
, bottom
,
686 ellipse_width
, ellipse_height
);
689 /***********************************************************************
690 * CreateRoundRectRgn (GDI32.61)
692 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
693 INT right
, INT bottom
,
694 INT ellipse_width
, INT ellipse_height
)
698 int asq
, bsq
, d
, xd
, yd
;
701 /* Check if we can do a normal rectangle instead */
703 if ((ellipse_width
== 0) || (ellipse_height
== 0))
704 return CreateRectRgn( left
, top
, right
, bottom
);
706 /* Make the dimensions sensible */
708 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
709 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
711 ellipse_width
= abs(ellipse_width
);
712 ellipse_height
= abs(ellipse_height
);
716 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
717 if (!(hrgn
= REGION_CreateRegion(d
))) return 0;
718 if (!(obj
= GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return 0;
719 TRACE("(%d,%d-%d,%d %dx%d): ret=%04x\n",
720 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
722 /* Check parameters */
724 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
725 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
727 /* Ellipse algorithm, based on an article by K. Porter */
728 /* in DDJ Graphics Programming Column, 8/89 */
730 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
731 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
732 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
734 yd
= asq
* ellipse_height
; /* 2a^2b */
736 rect
.left
= left
+ ellipse_width
/ 2;
737 rect
.right
= right
- ellipse_width
/ 2;
739 /* Loop to draw first half of quadrant */
743 if (d
> 0) /* if nearest pixel is toward the center */
745 /* move toward center */
747 rect
.bottom
= rect
.top
+ 1;
748 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
750 rect
.bottom
= rect
.top
+ 1;
751 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
755 rect
.left
--; /* next horiz point */
761 /* Loop to draw second half of quadrant */
763 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
766 /* next vertical point */
768 rect
.bottom
= rect
.top
+ 1;
769 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
771 rect
.bottom
= rect
.top
+ 1;
772 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
773 if (d
< 0) /* if nearest pixel is outside ellipse */
775 rect
.left
--; /* move away from center */
784 /* Add the inside rectangle */
789 rect
.bottom
= bottom
;
790 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
792 obj
->rgn
->type
= SIMPLEREGION
; /* FIXME? */
793 GDI_ReleaseObj( hrgn
);
798 /***********************************************************************
799 * CreateEllipticRgn16 (GDI.54)
801 HRGN16 WINAPI
CreateEllipticRgn16( INT16 left
, INT16 top
,
802 INT16 right
, INT16 bottom
)
804 return (HRGN16
)CreateRoundRectRgn( left
, top
, right
, bottom
,
805 right
-left
, bottom
-top
);
809 /***********************************************************************
810 * CreateEllipticRgn (GDI32.39)
812 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
813 INT right
, INT bottom
)
815 return CreateRoundRectRgn( left
, top
, right
, bottom
,
816 right
-left
, bottom
-top
);
820 /***********************************************************************
821 * CreateEllipticRgnIndirect16 (GDI.55)
823 HRGN16 WINAPI
CreateEllipticRgnIndirect16( const RECT16
*rect
)
825 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
826 rect
->bottom
, rect
->right
- rect
->left
,
827 rect
->bottom
- rect
->top
);
831 /***********************************************************************
832 * CreateEllipticRgnIndirect (GDI32.40)
834 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
836 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
837 rect
->bottom
, rect
->right
- rect
->left
,
838 rect
->bottom
- rect
->top
);
841 /***********************************************************************
842 * GetRegionData (GDI32.217)
845 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
848 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
850 TRACE(" %04x count = %ld, rgndata = %p\n",
851 hrgn
, count
, rgndata
);
855 size
= obj
->rgn
->numRects
* sizeof(RECT
);
856 if(count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
858 GDI_ReleaseObj( hrgn
);
859 return size
+ sizeof(RGNDATAHEADER
);
862 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
863 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
864 rgndata
->rdh
.nCount
= obj
->rgn
->numRects
;
865 rgndata
->rdh
.nRgnSize
= size
;
866 rgndata
->rdh
.rcBound
.left
= obj
->rgn
->extents
.left
;
867 rgndata
->rdh
.rcBound
.top
= obj
->rgn
->extents
.top
;
868 rgndata
->rdh
.rcBound
.right
= obj
->rgn
->extents
.right
;
869 rgndata
->rdh
.rcBound
.bottom
= obj
->rgn
->extents
.bottom
;
871 memcpy( rgndata
->Buffer
, obj
->rgn
->rects
, size
);
873 GDI_ReleaseObj( hrgn
);
877 /***********************************************************************
878 * GetRegionData16 (GDI.607)
879 * FIXME: is LPRGNDATA the same in Win16 and Win32 ?
881 DWORD WINAPI
GetRegionData16(HRGN16 hrgn
, DWORD count
, LPRGNDATA rgndata
)
883 return GetRegionData((HRGN
)hrgn
, count
, rgndata
);
886 /***********************************************************************
887 * ExtCreateRegion (GDI32.94)
890 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
894 TRACE(" %p %ld %p = ", lpXform
, dwCount
, rgndata
);
897 WARN("(Xform not implemented - ignored) ");
899 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
901 /* FIXME: We can use CreatePolyPolygonRgn() here
902 * for trapezoidal data */
904 WARN("(Unsupported region data) ");
908 if( (hrgn
= REGION_CreateRegion( rgndata
->rdh
.nCount
)) )
910 RECT
*pCurRect
, *pEndRect
;
911 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
914 pEndRect
= (RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
915 for(pCurRect
= (RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
916 REGION_UnionRectWithRegion( pCurRect
, obj
->rgn
);
917 GDI_ReleaseObj( hrgn
);
919 TRACE("%04x\n", hrgn
);
922 else ERR("Could not get pointer to newborn Region!");
929 /***********************************************************************
930 * PtInRegion16 (GDI.161)
932 BOOL16 WINAPI
PtInRegion16( HRGN16 hrgn
, INT16 x
, INT16 y
)
934 return PtInRegion( hrgn
, x
, y
);
938 /***********************************************************************
939 * PtInRegion (GDI32.278)
941 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
946 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
950 if (obj
->rgn
->numRects
> 0 && INRECT(obj
->rgn
->extents
, x
, y
))
951 for (i
= 0; i
< obj
->rgn
->numRects
; i
++)
952 if (INRECT (obj
->rgn
->rects
[i
], x
, y
))
957 GDI_ReleaseObj( hrgn
);
963 /***********************************************************************
964 * RectInRegion16 (GDI.181)
966 BOOL16 WINAPI
RectInRegion16( HRGN16 hrgn
, const RECT16
*rect
)
970 CONV_RECT16TO32(rect
, &r32
);
971 return (BOOL16
)RectInRegion(hrgn
, &r32
);
975 /***********************************************************************
976 * RectInRegion (GDI32.281)
978 * Returns TRUE if rect is at least partly inside hrgn
980 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
985 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
987 RECT
*pCurRect
, *pRectEnd
;
989 /* this is (just) a useful optimization */
990 if ((obj
->rgn
->numRects
> 0) && EXTENTCHECK(&obj
->rgn
->extents
,
993 for (pCurRect
= obj
->rgn
->rects
, pRectEnd
= pCurRect
+
994 obj
->rgn
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
996 if (pCurRect
->bottom
<= rect
->top
)
997 continue; /* not far enough down yet */
999 if (pCurRect
->top
>= rect
->bottom
)
1000 break; /* too far down */
1002 if (pCurRect
->right
<= rect
->left
)
1003 continue; /* not far enough over yet */
1005 if (pCurRect
->left
>= rect
->right
) {
1013 GDI_ReleaseObj(hrgn
);
1018 /***********************************************************************
1019 * EqualRgn16 (GDI.72)
1021 BOOL16 WINAPI
EqualRgn16( HRGN16 rgn1
, HRGN16 rgn2
)
1023 return EqualRgn( rgn1
, rgn2
);
1027 /***********************************************************************
1028 * EqualRgn (GDI32.90)
1030 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
1032 RGNOBJ
*obj1
, *obj2
;
1035 if ((obj1
= (RGNOBJ
*) GDI_GetObjPtr( hrgn1
, REGION_MAGIC
)))
1037 if ((obj2
= (RGNOBJ
*) GDI_GetObjPtr( hrgn2
, REGION_MAGIC
)))
1041 if ( obj1
->rgn
->numRects
!= obj2
->rgn
->numRects
) goto done
;
1042 if ( obj1
->rgn
->numRects
== 0 )
1048 if (obj1
->rgn
->extents
.left
!= obj2
->rgn
->extents
.left
) goto done
;
1049 if (obj1
->rgn
->extents
.right
!= obj2
->rgn
->extents
.right
) goto done
;
1050 if (obj1
->rgn
->extents
.top
!= obj2
->rgn
->extents
.top
) goto done
;
1051 if (obj1
->rgn
->extents
.bottom
!= obj2
->rgn
->extents
.bottom
) goto done
;
1052 for( i
= 0; i
< obj1
->rgn
->numRects
; i
++ )
1054 if (obj1
->rgn
->rects
[i
].left
!= obj2
->rgn
->rects
[i
].left
) goto done
;
1055 if (obj1
->rgn
->rects
[i
].right
!= obj2
->rgn
->rects
[i
].right
) goto done
;
1056 if (obj1
->rgn
->rects
[i
].top
!= obj2
->rgn
->rects
[i
].top
) goto done
;
1057 if (obj1
->rgn
->rects
[i
].bottom
!= obj2
->rgn
->rects
[i
].bottom
) goto done
;
1061 GDI_ReleaseObj(hrgn2
);
1063 GDI_ReleaseObj(hrgn1
);
1067 /***********************************************************************
1068 * REGION_UnionRectWithRegion
1069 * Adds a rectangle to a WINEREGION
1070 * See below for REGION_UnionRectWithRgn
1072 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
1076 region
.rects
= ®ion
.extents
;
1077 region
.numRects
= 1;
1079 region
.type
= SIMPLEREGION
;
1080 region
.extents
= *rect
;
1081 REGION_UnionRegion(rgn
, rgn
, ®ion
);
1085 /***********************************************************************
1086 * REGION_UnionRectWithRgn
1087 * Adds a rectangle to a HRGN
1088 * A helper used by scroll.c
1090 BOOL
REGION_UnionRectWithRgn( HRGN hrgn
, const RECT
*lpRect
)
1092 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
1094 if(!obj
) return FALSE
;
1095 REGION_UnionRectWithRegion( lpRect
, obj
->rgn
);
1096 GDI_ReleaseObj(hrgn
);
1100 /***********************************************************************
1101 * REGION_CreateFrameRgn
1103 * Create a region that is a frame around another region.
1104 * Expand all rectangles by +/- x and y, then subtract original region.
1106 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
1109 RGNOBJ
*srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
1111 if (!srcObj
) return FALSE
;
1112 if (srcObj
->rgn
->numRects
!= 0)
1114 RGNOBJ
* destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1115 RECT
*pRect
, *pEndRect
;
1118 EMPTY_REGION( destObj
->rgn
);
1120 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
1121 for(pRect
= srcObj
->rgn
->rects
; pRect
< pEndRect
; pRect
++)
1123 tempRect
.left
= pRect
->left
- x
;
1124 tempRect
.top
= pRect
->top
- y
;
1125 tempRect
.right
= pRect
->right
+ x
;
1126 tempRect
.bottom
= pRect
->bottom
+ y
;
1127 REGION_UnionRectWithRegion( &tempRect
, destObj
->rgn
);
1129 REGION_SubtractRegion( destObj
->rgn
, destObj
->rgn
, srcObj
->rgn
);
1130 GDI_ReleaseObj ( hDest
);
1135 GDI_ReleaseObj( hSrc
);
1139 /***********************************************************************
1142 * Convert region to device co-ords for the supplied dc.
1144 BOOL
REGION_LPTODP( HDC hdc
, HRGN hDest
, HRGN hSrc
)
1146 RECT
*pCurRect
, *pEndRect
;
1147 RGNOBJ
*srcObj
, *destObj
;
1148 DC
* dc
= DC_GetDCPtr( hdc
);
1152 TRACE(" hdc=%04x dest=%04x src=%04x\n",
1154 if (!dc
) return ret
;
1156 if (dc
->w
.MapMode
== MM_TEXT
) /* Requires only a translation */
1158 if( CombineRgn( hDest
, hSrc
, 0, RGN_COPY
) == ERROR
) goto done
;
1159 OffsetRgn( hDest
, dc
->vportOrgX
- dc
->wndOrgX
,
1160 dc
->vportOrgY
- dc
->wndOrgY
);
1165 if(!( srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
) ))
1167 if(!( destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
) ))
1169 GDI_ReleaseObj( hSrc
);
1172 EMPTY_REGION( destObj
->rgn
);
1174 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
1175 for(pCurRect
= srcObj
->rgn
->rects
; pCurRect
< pEndRect
; pCurRect
++)
1177 tmpRect
= *pCurRect
;
1178 tmpRect
.left
= XLPTODP( dc
, tmpRect
.left
);
1179 tmpRect
.top
= YLPTODP( dc
, tmpRect
.top
);
1180 tmpRect
.right
= XLPTODP( dc
, tmpRect
.right
);
1181 tmpRect
.bottom
= YLPTODP( dc
, tmpRect
.bottom
);
1182 REGION_UnionRectWithRegion( &tmpRect
, destObj
->rgn
);
1185 GDI_ReleaseObj( hDest
);
1186 GDI_ReleaseObj( hSrc
);
1188 GDI_ReleaseObj( hdc
);
1192 /***********************************************************************
1193 * CombineRgn16 (GDI.451)
1195 INT16 WINAPI
CombineRgn16(HRGN16 hDest
, HRGN16 hSrc1
, HRGN16 hSrc2
, INT16 mode
)
1197 return (INT16
)CombineRgn( hDest
, hSrc1
, hSrc2
, mode
);
1201 /***********************************************************************
1202 * CombineRgn (GDI32.19)
1204 * Note: The behavior is correct even if src and dest regions are the same.
1206 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
1208 RGNOBJ
*destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
1211 TRACE(" %04x,%04x -> %04x mode=%x\n",
1212 hSrc1
, hSrc2
, hDest
, mode
);
1215 RGNOBJ
*src1Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc1
, REGION_MAGIC
);
1220 if(TRACE_ON(region
))
1221 REGION_DumpRegion(src1Obj
->rgn
);
1222 if (mode
== RGN_COPY
)
1224 REGION_CopyRegion( destObj
->rgn
, src1Obj
->rgn
);
1225 result
= destObj
->rgn
->type
;
1229 RGNOBJ
*src2Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc2
, REGION_MAGIC
);
1234 if(TRACE_ON(region
))
1235 REGION_DumpRegion(src2Obj
->rgn
);
1239 REGION_IntersectRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1242 REGION_UnionRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1245 REGION_XorRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1248 REGION_SubtractRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
1251 result
= destObj
->rgn
->type
;
1252 GDI_ReleaseObj( hSrc2
);
1255 GDI_ReleaseObj( hSrc1
);
1258 if(TRACE_ON(region
))
1259 REGION_DumpRegion(destObj
->rgn
);
1261 GDI_ReleaseObj( hDest
);
1263 ERR("Invalid rgn=%04x\n", hDest
);
1268 /***********************************************************************
1270 * Re-calculate the extents of a region
1272 static void REGION_SetExtents (WINEREGION
*pReg
)
1274 RECT
*pRect
, *pRectEnd
, *pExtents
;
1276 if (pReg
->numRects
== 0)
1278 pReg
->extents
.left
= 0;
1279 pReg
->extents
.top
= 0;
1280 pReg
->extents
.right
= 0;
1281 pReg
->extents
.bottom
= 0;
1285 pExtents
= &pReg
->extents
;
1286 pRect
= pReg
->rects
;
1287 pRectEnd
= &pRect
[pReg
->numRects
- 1];
1290 * Since pRect is the first rectangle in the region, it must have the
1291 * smallest top and since pRectEnd is the last rectangle in the region,
1292 * it must have the largest bottom, because of banding. Initialize left and
1293 * right from pRect and pRectEnd, resp., as good things to initialize them
1296 pExtents
->left
= pRect
->left
;
1297 pExtents
->top
= pRect
->top
;
1298 pExtents
->right
= pRectEnd
->right
;
1299 pExtents
->bottom
= pRectEnd
->bottom
;
1301 while (pRect
<= pRectEnd
)
1303 if (pRect
->left
< pExtents
->left
)
1304 pExtents
->left
= pRect
->left
;
1305 if (pRect
->right
> pExtents
->right
)
1306 pExtents
->right
= pRect
->right
;
1311 /***********************************************************************
1314 static void REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
1316 if (dst
!= src
) /* don't want to copy to itself */
1318 if (dst
->size
< src
->numRects
)
1320 if (! (dst
->rects
= HeapReAlloc( GetProcessHeap(), 0, dst
->rects
,
1321 src
->numRects
* sizeof(RECT
) )))
1323 dst
->size
= src
->numRects
;
1325 dst
->numRects
= src
->numRects
;
1326 dst
->extents
.left
= src
->extents
.left
;
1327 dst
->extents
.top
= src
->extents
.top
;
1328 dst
->extents
.right
= src
->extents
.right
;
1329 dst
->extents
.bottom
= src
->extents
.bottom
;
1330 dst
->type
= src
->type
;
1332 memcpy((char *) dst
->rects
, (char *) src
->rects
,
1333 (int) (src
->numRects
* sizeof(RECT
)));
1338 /***********************************************************************
1341 * Attempt to merge the rects in the current band with those in the
1342 * previous one. Used only by REGION_RegionOp.
1345 * The new index for the previous band.
1348 * If coalescing takes place:
1349 * - rectangles in the previous band will have their bottom fields
1351 * - pReg->numRects will be decreased.
1354 static INT
REGION_Coalesce (
1355 WINEREGION
*pReg
, /* Region to coalesce */
1356 INT prevStart
, /* Index of start of previous band */
1357 INT curStart
/* Index of start of current band */
1359 RECT
*pPrevRect
; /* Current rect in previous band */
1360 RECT
*pCurRect
; /* Current rect in current band */
1361 RECT
*pRegEnd
; /* End of region */
1362 INT curNumRects
; /* Number of rectangles in current band */
1363 INT prevNumRects
; /* Number of rectangles in previous band */
1364 INT bandtop
; /* top coordinate for current band */
1366 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1368 pPrevRect
= &pReg
->rects
[prevStart
];
1369 prevNumRects
= curStart
- prevStart
;
1372 * Figure out how many rectangles are in the current band. Have to do
1373 * this because multiple bands could have been added in REGION_RegionOp
1374 * at the end when one region has been exhausted.
1376 pCurRect
= &pReg
->rects
[curStart
];
1377 bandtop
= pCurRect
->top
;
1378 for (curNumRects
= 0;
1379 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1385 if (pCurRect
!= pRegEnd
)
1388 * If more than one band was added, we have to find the start
1389 * of the last band added so the next coalescing job can start
1390 * at the right place... (given when multiple bands are added,
1391 * this may be pointless -- see above).
1394 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1398 curStart
= pRegEnd
- pReg
->rects
;
1399 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1402 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1403 pCurRect
-= curNumRects
;
1405 * The bands may only be coalesced if the bottom of the previous
1406 * matches the top scanline of the current.
1408 if (pPrevRect
->bottom
== pCurRect
->top
)
1411 * Make sure the bands have rects in the same places. This
1412 * assumes that rects have been added in such a way that they
1413 * cover the most area possible. I.e. two rects in a band must
1414 * have some horizontal space between them.
1418 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1419 (pPrevRect
->right
!= pCurRect
->right
))
1422 * The bands don't line up so they can't be coalesced.
1429 } while (prevNumRects
!= 0);
1431 pReg
->numRects
-= curNumRects
;
1432 pCurRect
-= curNumRects
;
1433 pPrevRect
-= curNumRects
;
1436 * The bands may be merged, so set the bottom of each rect
1437 * in the previous band to that of the corresponding rect in
1442 pPrevRect
->bottom
= pCurRect
->bottom
;
1446 } while (curNumRects
!= 0);
1449 * If only one band was added to the region, we have to backup
1450 * curStart to the start of the previous band.
1452 * If more than one band was added to the region, copy the
1453 * other bands down. The assumption here is that the other bands
1454 * came from the same region as the current one and no further
1455 * coalescing can be done on them since it's all been done
1456 * already... curStart is already in the right place.
1458 if (pCurRect
== pRegEnd
)
1460 curStart
= prevStart
;
1466 *pPrevRect
++ = *pCurRect
++;
1467 } while (pCurRect
!= pRegEnd
);
1475 /***********************************************************************
1478 * Apply an operation to two regions. Called by REGION_Union,
1479 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1485 * The new region is overwritten.
1488 * The idea behind this function is to view the two regions as sets.
1489 * Together they cover a rectangle of area that this function divides
1490 * into horizontal bands where points are covered only by one region
1491 * or by both. For the first case, the nonOverlapFunc is called with
1492 * each the band and the band's upper and lower extents. For the
1493 * second, the overlapFunc is called to process the entire band. It
1494 * is responsible for clipping the rectangles in the band, though
1495 * this function provides the boundaries.
1496 * At the end of each band, the new region is coalesced, if possible,
1497 * to reduce the number of rectangles in the region.
1500 static void REGION_RegionOp(
1501 WINEREGION
*newReg
, /* Place to store result */
1502 WINEREGION
*reg1
, /* First region in operation */
1503 WINEREGION
*reg2
, /* 2nd region in operation */
1504 void (*overlapFunc
)(), /* Function to call for over-lapping bands */
1505 void (*nonOverlap1Func
)(), /* Function to call for non-overlapping bands in region 1 */
1506 void (*nonOverlap2Func
)() /* Function to call for non-overlapping bands in region 2 */
1508 RECT
*r1
; /* Pointer into first region */
1509 RECT
*r2
; /* Pointer into 2d region */
1510 RECT
*r1End
; /* End of 1st region */
1511 RECT
*r2End
; /* End of 2d region */
1512 INT ybot
; /* Bottom of intersection */
1513 INT ytop
; /* Top of intersection */
1514 RECT
*oldRects
; /* Old rects for newReg */
1515 INT prevBand
; /* Index of start of
1516 * previous band in newReg */
1517 INT curBand
; /* Index of start of current
1519 RECT
*r1BandEnd
; /* End of current band in r1 */
1520 RECT
*r2BandEnd
; /* End of current band in r2 */
1521 INT top
; /* Top of non-overlapping band */
1522 INT bot
; /* Bottom of non-overlapping band */
1526 * set r1, r2, r1End and r2End appropriately, preserve the important
1527 * parts of the destination region until the end in case it's one of
1528 * the two source regions, then mark the "new" region empty, allocating
1529 * another array of rectangles for it to use.
1533 r1End
= r1
+ reg1
->numRects
;
1534 r2End
= r2
+ reg2
->numRects
;
1538 * newReg may be one of the src regions so we can't empty it. We keep a
1539 * note of its rects pointer (so that we can free them later), preserve its
1540 * extents and simply set numRects to zero.
1543 oldRects
= newReg
->rects
;
1544 newReg
->numRects
= 0;
1547 * Allocate a reasonable number of rectangles for the new region. The idea
1548 * is to allocate enough so the individual functions don't need to
1549 * reallocate and copy the array, which is time consuming, yet we don't
1550 * have to worry about using too much memory. I hope to be able to
1551 * nuke the Xrealloc() at the end of this function eventually.
1553 newReg
->size
= max(reg1
->numRects
,reg2
->numRects
) * 2;
1555 if (! (newReg
->rects
= HeapAlloc( GetProcessHeap(), 0,
1556 sizeof(RECT
) * newReg
->size
)))
1563 * Initialize ybot and ytop.
1564 * In the upcoming loop, ybot and ytop serve different functions depending
1565 * on whether the band being handled is an overlapping or non-overlapping
1567 * In the case of a non-overlapping band (only one of the regions
1568 * has points in the band), ybot is the bottom of the most recent
1569 * intersection and thus clips the top of the rectangles in that band.
1570 * ytop is the top of the next intersection between the two regions and
1571 * serves to clip the bottom of the rectangles in the current band.
1572 * For an overlapping band (where the two regions intersect), ytop clips
1573 * the top of the rectangles of both regions and ybot clips the bottoms.
1575 if (reg1
->extents
.top
< reg2
->extents
.top
)
1576 ybot
= reg1
->extents
.top
;
1578 ybot
= reg2
->extents
.top
;
1581 * prevBand serves to mark the start of the previous band so rectangles
1582 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1583 * In the beginning, there is no previous band, so prevBand == curBand
1584 * (curBand is set later on, of course, but the first band will always
1585 * start at index 0). prevBand and curBand must be indices because of
1586 * the possible expansion, and resultant moving, of the new region's
1587 * array of rectangles.
1593 curBand
= newReg
->numRects
;
1596 * This algorithm proceeds one source-band (as opposed to a
1597 * destination band, which is determined by where the two regions
1598 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1599 * rectangle after the last one in the current band for their
1600 * respective regions.
1603 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1609 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1615 * First handle the band that doesn't intersect, if any.
1617 * Note that attention is restricted to one band in the
1618 * non-intersecting region at once, so if a region has n
1619 * bands between the current position and the next place it overlaps
1620 * the other, this entire loop will be passed through n times.
1622 if (r1
->top
< r2
->top
)
1624 top
= max(r1
->top
,ybot
);
1625 bot
= min(r1
->bottom
,r2
->top
);
1627 if ((top
!= bot
) && (nonOverlap1Func
!= (void (*)())NULL
))
1629 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1634 else if (r2
->top
< r1
->top
)
1636 top
= max(r2
->top
,ybot
);
1637 bot
= min(r2
->bottom
,r1
->top
);
1639 if ((top
!= bot
) && (nonOverlap2Func
!= (void (*)())NULL
))
1641 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1652 * If any rectangles got added to the region, try and coalesce them
1653 * with rectangles from the previous band. Note we could just do
1654 * this test in miCoalesce, but some machines incur a not
1655 * inconsiderable cost for function calls, so...
1657 if (newReg
->numRects
!= curBand
)
1659 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1663 * Now see if we've hit an intersecting band. The two bands only
1664 * intersect if ybot > ytop
1666 ybot
= min(r1
->bottom
, r2
->bottom
);
1667 curBand
= newReg
->numRects
;
1670 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1674 if (newReg
->numRects
!= curBand
)
1676 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1680 * If we've finished with a band (bottom == ybot) we skip forward
1681 * in the region to the next band.
1683 if (r1
->bottom
== ybot
)
1687 if (r2
->bottom
== ybot
)
1691 } while ((r1
!= r1End
) && (r2
!= r2End
));
1694 * Deal with whichever region still has rectangles left.
1696 curBand
= newReg
->numRects
;
1699 if (nonOverlap1Func
!= (void (*)())NULL
)
1704 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1708 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1709 max(r1
->top
,ybot
), r1
->bottom
);
1711 } while (r1
!= r1End
);
1714 else if ((r2
!= r2End
) && (nonOverlap2Func
!= (void (*)())NULL
))
1719 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1723 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1724 max(r2
->top
,ybot
), r2
->bottom
);
1726 } while (r2
!= r2End
);
1729 if (newReg
->numRects
!= curBand
)
1731 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1735 * A bit of cleanup. To keep regions from growing without bound,
1736 * we shrink the array of rectangles to match the new number of
1737 * rectangles in the region. This never goes to 0, however...
1739 * Only do this stuff if the number of rectangles allocated is more than
1740 * twice the number of rectangles in the region (a simple optimization...).
1742 if ((newReg
->numRects
< (newReg
->size
>> 1)) && (newReg
->numRects
> 2))
1744 if (REGION_NOT_EMPTY(newReg
))
1746 RECT
*prev_rects
= newReg
->rects
;
1747 newReg
->size
= newReg
->numRects
;
1748 newReg
->rects
= HeapReAlloc( GetProcessHeap(), 0, newReg
->rects
,
1749 sizeof(RECT
) * newReg
->size
);
1750 if (! newReg
->rects
)
1751 newReg
->rects
= prev_rects
;
1756 * No point in doing the extra work involved in an Xrealloc if
1757 * the region is empty
1760 HeapFree( GetProcessHeap(), 0, newReg
->rects
);
1761 newReg
->rects
= HeapAlloc( GetProcessHeap(), 0, sizeof(RECT
) );
1764 HeapFree( GetProcessHeap(), 0, oldRects
);
1768 /***********************************************************************
1769 * Region Intersection
1770 ***********************************************************************/
1773 /***********************************************************************
1776 * Handle an overlapping band for REGION_Intersect.
1782 * Rectangles may be added to the region.
1785 static void REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1786 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1792 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1794 while ((r1
!= r1End
) && (r2
!= r2End
))
1796 left
= max(r1
->left
, r2
->left
);
1797 right
= min(r1
->right
, r2
->right
);
1800 * If there's any overlap between the two rectangles, add that
1801 * overlap to the new region.
1802 * There's no need to check for subsumption because the only way
1803 * such a need could arise is if some region has two rectangles
1804 * right next to each other. Since that should never happen...
1808 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1809 pNextRect
->left
= left
;
1810 pNextRect
->top
= top
;
1811 pNextRect
->right
= right
;
1812 pNextRect
->bottom
= bottom
;
1813 pReg
->numRects
+= 1;
1818 * Need to advance the pointers. Shift the one that extends
1819 * to the right the least, since the other still has a chance to
1820 * overlap with that region's next rectangle, if you see what I mean.
1822 if (r1
->right
< r2
->right
)
1826 else if (r2
->right
< r1
->right
)
1839 /***********************************************************************
1840 * REGION_IntersectRegion
1842 static void REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1845 /* check for trivial reject */
1846 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1847 (!EXTENTCHECK(®1
->extents
, ®2
->extents
)))
1848 newReg
->numRects
= 0;
1850 REGION_RegionOp (newReg
, reg1
, reg2
,
1851 (voidProcp
) REGION_IntersectO
, (voidProcp
) NULL
, (voidProcp
) NULL
);
1854 * Can't alter newReg's extents before we call miRegionOp because
1855 * it might be one of the source regions and miRegionOp depends
1856 * on the extents of those regions being the same. Besides, this
1857 * way there's no checking against rectangles that will be nuked
1858 * due to coalescing, so we have to examine fewer rectangles.
1860 REGION_SetExtents(newReg
);
1861 newReg
->type
= (newReg
->numRects
) ?
1862 ((newReg
->numRects
> 1) ? COMPLEXREGION
: SIMPLEREGION
)
1867 /***********************************************************************
1869 ***********************************************************************/
1871 /***********************************************************************
1874 * Handle a non-overlapping band for the union operation. Just
1875 * Adds the rectangles into the region. Doesn't have to check for
1876 * subsumption or anything.
1882 * pReg->numRects is incremented and the final rectangles overwritten
1883 * with the rectangles we're passed.
1886 static void REGION_UnionNonO (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1887 INT top
, INT bottom
)
1891 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1895 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1896 pNextRect
->left
= r
->left
;
1897 pNextRect
->top
= top
;
1898 pNextRect
->right
= r
->right
;
1899 pNextRect
->bottom
= bottom
;
1900 pReg
->numRects
+= 1;
1907 /***********************************************************************
1910 * Handle an overlapping band for the union operation. Picks the
1911 * left-most rectangle each time and merges it into the region.
1917 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1921 static void REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1922 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1926 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1928 #define MERGERECT(r) \
1929 if ((pReg->numRects != 0) && \
1930 (pNextRect[-1].top == top) && \
1931 (pNextRect[-1].bottom == bottom) && \
1932 (pNextRect[-1].right >= r->left)) \
1934 if (pNextRect[-1].right < r->right) \
1936 pNextRect[-1].right = r->right; \
1941 MEMCHECK(pReg, pNextRect, pReg->rects); \
1942 pNextRect->top = top; \
1943 pNextRect->bottom = bottom; \
1944 pNextRect->left = r->left; \
1945 pNextRect->right = r->right; \
1946 pReg->numRects += 1; \
1951 while ((r1
!= r1End
) && (r2
!= r2End
))
1953 if (r1
->left
< r2
->left
)
1968 } while (r1
!= r1End
);
1970 else while (r2
!= r2End
)
1977 /***********************************************************************
1978 * REGION_UnionRegion
1980 static void REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1983 /* checks all the simple cases */
1986 * Region 1 and 2 are the same or region 1 is empty
1988 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
1991 REGION_CopyRegion(newReg
, reg2
);
1996 * if nothing to union (region 2 empty)
1998 if (!(reg2
->numRects
))
2001 REGION_CopyRegion(newReg
, reg1
);
2006 * Region 1 completely subsumes region 2
2008 if ((reg1
->numRects
== 1) &&
2009 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
2010 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
2011 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
2012 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
2015 REGION_CopyRegion(newReg
, reg1
);
2020 * Region 2 completely subsumes region 1
2022 if ((reg2
->numRects
== 1) &&
2023 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
2024 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
2025 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
2026 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
2029 REGION_CopyRegion(newReg
, reg2
);
2033 REGION_RegionOp (newReg
, reg1
, reg2
, (voidProcp
) REGION_UnionO
,
2034 (voidProcp
) REGION_UnionNonO
, (voidProcp
) REGION_UnionNonO
);
2036 newReg
->extents
.left
= min(reg1
->extents
.left
, reg2
->extents
.left
);
2037 newReg
->extents
.top
= min(reg1
->extents
.top
, reg2
->extents
.top
);
2038 newReg
->extents
.right
= max(reg1
->extents
.right
, reg2
->extents
.right
);
2039 newReg
->extents
.bottom
= max(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
2040 newReg
->type
= (newReg
->numRects
) ?
2041 ((newReg
->numRects
> 1) ? COMPLEXREGION
: SIMPLEREGION
)
2046 /***********************************************************************
2047 * Region Subtraction
2048 ***********************************************************************/
2050 /***********************************************************************
2051 * REGION_SubtractNonO1
2053 * Deal with non-overlapping band for subtraction. Any parts from
2054 * region 2 we discard. Anything from region 1 we add to the region.
2060 * pReg may be affected.
2063 static void REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
2064 INT top
, INT bottom
)
2068 pNextRect
= &pReg
->rects
[pReg
->numRects
];
2072 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2073 pNextRect
->left
= r
->left
;
2074 pNextRect
->top
= top
;
2075 pNextRect
->right
= r
->right
;
2076 pNextRect
->bottom
= bottom
;
2077 pReg
->numRects
+= 1;
2085 /***********************************************************************
2088 * Overlapping band subtraction. x1 is the left-most point not yet
2095 * pReg may have rectangles added to it.
2098 static void REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
2099 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
2105 pNextRect
= &pReg
->rects
[pReg
->numRects
];
2107 while ((r1
!= r1End
) && (r2
!= r2End
))
2109 if (r2
->right
<= left
)
2112 * Subtrahend missed the boat: go to next subtrahend.
2116 else if (r2
->left
<= left
)
2119 * Subtrahend preceeds minuend: nuke left edge of minuend.
2122 if (left
>= r1
->right
)
2125 * Minuend completely covered: advance to next minuend and
2126 * reset left fence to edge of new minuend.
2135 * Subtrahend now used up since it doesn't extend beyond
2141 else if (r2
->left
< r1
->right
)
2144 * Left part of subtrahend covers part of minuend: add uncovered
2145 * part of minuend to region and skip to next subtrahend.
2147 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2148 pNextRect
->left
= left
;
2149 pNextRect
->top
= top
;
2150 pNextRect
->right
= r2
->left
;
2151 pNextRect
->bottom
= bottom
;
2152 pReg
->numRects
+= 1;
2155 if (left
>= r1
->right
)
2158 * Minuend used up: advance to new...
2167 * Subtrahend used up
2175 * Minuend used up: add any remaining piece before advancing.
2177 if (r1
->right
> left
)
2179 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2180 pNextRect
->left
= left
;
2181 pNextRect
->top
= top
;
2182 pNextRect
->right
= r1
->right
;
2183 pNextRect
->bottom
= bottom
;
2184 pReg
->numRects
+= 1;
2193 * Add remaining minuend rectangles to region.
2197 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
2198 pNextRect
->left
= left
;
2199 pNextRect
->top
= top
;
2200 pNextRect
->right
= r1
->right
;
2201 pNextRect
->bottom
= bottom
;
2202 pReg
->numRects
+= 1;
2213 /***********************************************************************
2214 * REGION_SubtractRegion
2216 * Subtract regS from regM and leave the result in regD.
2217 * S stands for subtrahend, M for minuend and D for difference.
2223 * regD is overwritten.
2226 static void REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
,
2229 /* check for trivial reject */
2230 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
2231 (!EXTENTCHECK(®M
->extents
, ®S
->extents
)) )
2233 REGION_CopyRegion(regD
, regM
);
2237 REGION_RegionOp (regD
, regM
, regS
, (voidProcp
) REGION_SubtractO
,
2238 (voidProcp
) REGION_SubtractNonO1
, (voidProcp
) NULL
);
2241 * Can't alter newReg's extents before we call miRegionOp because
2242 * it might be one of the source regions and miRegionOp depends
2243 * on the extents of those regions being the unaltered. Besides, this
2244 * way there's no checking against rectangles that will be nuked
2245 * due to coalescing, so we have to examine fewer rectangles.
2247 REGION_SetExtents (regD
);
2248 regD
->type
= (regD
->numRects
) ?
2249 ((regD
->numRects
> 1) ? COMPLEXREGION
: SIMPLEREGION
)
2254 /***********************************************************************
2257 static void REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
,
2260 WINEREGION
*tra
, *trb
;
2262 if ((! (tra
= REGION_AllocWineRegion(sra
->numRects
+ 1))) ||
2263 (! (trb
= REGION_AllocWineRegion(srb
->numRects
+ 1))))
2265 REGION_SubtractRegion(tra
,sra
,srb
);
2266 REGION_SubtractRegion(trb
,srb
,sra
);
2267 REGION_UnionRegion(dr
,tra
,trb
);
2268 REGION_DestroyWineRegion(tra
);
2269 REGION_DestroyWineRegion(trb
);
2273 /**************************************************************************
2277 *************************************************************************/
2279 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2280 #define SMALL_COORDINATE 0x80000000
2282 /***********************************************************************
2283 * REGION_InsertEdgeInET
2285 * Insert the given edge into the edge table.
2286 * First we must find the correct bucket in the
2287 * Edge table, then find the right slot in the
2288 * bucket. Finally, we can insert it.
2291 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
2292 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
2295 EdgeTableEntry
*start
, *prev
;
2296 ScanLineList
*pSLL
, *pPrevSLL
;
2297 ScanLineListBlock
*tmpSLLBlock
;
2300 * find the right bucket to put the edge into
2302 pPrevSLL
= &ET
->scanlines
;
2303 pSLL
= pPrevSLL
->next
;
2304 while (pSLL
&& (pSLL
->scanline
< scanline
))
2311 * reassign pSLL (pointer to ScanLineList) if necessary
2313 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
2315 if (*iSLLBlock
> SLLSPERBLOCK
-1)
2317 tmpSLLBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock
));
2320 WARN("Can't alloc SLLB\n");
2323 (*SLLBlock
)->next
= tmpSLLBlock
;
2324 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2325 *SLLBlock
= tmpSLLBlock
;
2328 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2330 pSLL
->next
= pPrevSLL
->next
;
2331 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
2332 pPrevSLL
->next
= pSLL
;
2334 pSLL
->scanline
= scanline
;
2337 * now insert the edge in the right bucket
2339 prev
= (EdgeTableEntry
*)NULL
;
2340 start
= pSLL
->edgelist
;
2341 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
2344 start
= start
->next
;
2351 pSLL
->edgelist
= ETE
;
2354 /***********************************************************************
2355 * REGION_CreateEdgeTable
2357 * This routine creates the edge table for
2358 * scan converting polygons.
2359 * The Edge Table (ET) looks like:
2363 * | ymax | ScanLineLists
2364 * |scanline|-->------------>-------------->...
2365 * -------- |scanline| |scanline|
2366 * |edgelist| |edgelist|
2367 * --------- ---------
2371 * list of ETEs list of ETEs
2373 * where ETE is an EdgeTableEntry data structure,
2374 * and there is one ScanLineList per scanline at
2375 * which an edge is initially entered.
2378 static void REGION_CreateETandAET(const INT
*Count
, INT nbpolygons
,
2379 const POINT
*pts
, EdgeTable
*ET
, EdgeTableEntry
*AET
,
2380 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2382 const POINT
*top
, *bottom
;
2383 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2390 * initialize the Active Edge Table
2392 AET
->next
= (EdgeTableEntry
*)NULL
;
2393 AET
->back
= (EdgeTableEntry
*)NULL
;
2394 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2395 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
2398 * initialize the Edge Table.
2400 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
2401 ET
->ymax
= SMALL_COORDINATE
;
2402 ET
->ymin
= LARGE_COORDINATE
;
2403 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2406 for(poly
= 0; poly
< nbpolygons
; poly
++)
2408 count
= Count
[poly
];
2416 * for each vertex in the array of points.
2417 * In this loop we are dealing with two vertices at
2418 * a time -- these make up one edge of the polygon.
2425 * find out which point is above and which is below.
2427 if (PrevPt
->y
> CurrPt
->y
)
2429 bottom
= PrevPt
, top
= CurrPt
;
2430 pETEs
->ClockWise
= 0;
2434 bottom
= CurrPt
, top
= PrevPt
;
2435 pETEs
->ClockWise
= 1;
2439 * don't add horizontal edges to the Edge table.
2441 if (bottom
->y
!= top
->y
)
2443 pETEs
->ymax
= bottom
->y
-1;
2444 /* -1 so we don't get last scanline */
2447 * initialize integer edge algorithm
2449 dy
= bottom
->y
- top
->y
;
2450 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
2452 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2455 if (PrevPt
->y
> ET
->ymax
)
2456 ET
->ymax
= PrevPt
->y
;
2457 if (PrevPt
->y
< ET
->ymin
)
2458 ET
->ymin
= PrevPt
->y
;
2467 /***********************************************************************
2470 * This routine moves EdgeTableEntries from the
2471 * EdgeTable into the Active Edge Table,
2472 * leaving them sorted by smaller x coordinate.
2475 static void REGION_loadAET(EdgeTableEntry
*AET
, EdgeTableEntry
*ETEs
)
2477 EdgeTableEntry
*pPrevAET
;
2478 EdgeTableEntry
*tmp
;
2484 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
2493 ETEs
->back
= pPrevAET
;
2494 pPrevAET
->next
= ETEs
;
2501 /***********************************************************************
2502 * REGION_computeWAET
2504 * This routine links the AET by the
2505 * nextWETE (winding EdgeTableEntry) link for
2506 * use by the winding number rule. The final
2507 * Active Edge Table (AET) might look something
2511 * ---------- --------- ---------
2512 * |ymax | |ymax | |ymax |
2513 * | ... | |... | |... |
2514 * |next |->|next |->|next |->...
2515 * |nextWETE| |nextWETE| |nextWETE|
2516 * --------- --------- ^--------
2518 * V-------------------> V---> ...
2521 static void REGION_computeWAET(EdgeTableEntry
*AET
)
2523 register EdgeTableEntry
*pWETE
;
2524 register int inside
= 1;
2525 register int isInside
= 0;
2527 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2537 if ((!inside
&& !isInside
) ||
2538 ( inside
&& isInside
))
2540 pWETE
->nextWETE
= AET
;
2546 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
2549 /***********************************************************************
2550 * REGION_InsertionSort
2552 * Just a simple insertion sort using
2553 * pointers and back pointers to sort the Active
2557 static BOOL
REGION_InsertionSort(EdgeTableEntry
*AET
)
2559 EdgeTableEntry
*pETEchase
;
2560 EdgeTableEntry
*pETEinsert
;
2561 EdgeTableEntry
*pETEchaseBackTMP
;
2562 BOOL changed
= FALSE
;
2569 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
2570 pETEchase
= pETEchase
->back
;
2573 if (pETEchase
!= pETEinsert
)
2575 pETEchaseBackTMP
= pETEchase
->back
;
2576 pETEinsert
->back
->next
= AET
;
2578 AET
->back
= pETEinsert
->back
;
2579 pETEinsert
->next
= pETEchase
;
2580 pETEchase
->back
->next
= pETEinsert
;
2581 pETEchase
->back
= pETEinsert
;
2582 pETEinsert
->back
= pETEchaseBackTMP
;
2589 /***********************************************************************
2590 * REGION_FreeStorage
2594 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2596 ScanLineListBlock
*tmpSLLBlock
;
2600 tmpSLLBlock
= pSLLBlock
->next
;
2601 HeapFree( GetProcessHeap(), 0, pSLLBlock
);
2602 pSLLBlock
= tmpSLLBlock
;
2607 /***********************************************************************
2608 * REGION_PtsToRegion
2610 * Create an array of rectangles from a list of points.
2612 static int REGION_PtsToRegion(int numFullPtBlocks
, int iCurPtBlock
,
2613 POINTBLOCK
*FirstPtBlock
, WINEREGION
*reg
)
2617 POINTBLOCK
*CurPtBlock
;
2622 extents
= ®
->extents
;
2624 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
2626 if (!(reg
->rects
= HeapReAlloc( GetProcessHeap(), 0, reg
->rects
,
2627 sizeof(RECT
) * numRects
)))
2630 reg
->size
= numRects
;
2631 CurPtBlock
= FirstPtBlock
;
2632 rects
= reg
->rects
- 1;
2634 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2636 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--) {
2637 /* the loop uses 2 points per iteration */
2638 i
= NUMPTSTOBUFFER
>> 1;
2639 if (!numFullPtBlocks
)
2640 i
= iCurPtBlock
>> 1;
2641 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2) {
2642 if (pts
->x
== pts
[1].x
)
2644 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2645 pts
[1].x
== rects
->right
&&
2646 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2647 (i
&& pts
[2].y
> pts
[1].y
)) {
2648 rects
->bottom
= pts
[1].y
+ 1;
2653 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2654 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2655 if (rects
->left
< extents
->left
)
2656 extents
->left
= rects
->left
;
2657 if (rects
->right
> extents
->right
)
2658 extents
->right
= rects
->right
;
2660 CurPtBlock
= CurPtBlock
->next
;
2664 extents
->top
= reg
->rects
->top
;
2665 extents
->bottom
= rects
->bottom
;
2670 extents
->bottom
= 0;
2672 reg
->numRects
= numRects
;
2677 /***********************************************************************
2678 * CreatePolyPolygonRgn (GDI32.57)
2680 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2681 INT nbpolygons
, INT mode
)
2686 register EdgeTableEntry
*pAET
; /* Active Edge Table */
2687 register INT y
; /* current scanline */
2688 register int iPts
= 0; /* number of pts in buffer */
2689 register EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
2690 register ScanLineList
*pSLL
; /* current scanLineList */
2691 register POINT
*pts
; /* output buffer */
2692 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
2693 EdgeTable ET
; /* header node for ET */
2694 EdgeTableEntry AET
; /* header node for AET */
2695 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2696 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2697 int fixWAET
= FALSE
;
2698 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
2699 POINTBLOCK
*tmpPtBlock
;
2700 int numFullPtBlocks
= 0;
2703 if(!(hrgn
= REGION_CreateRegion(nbpolygons
)))
2705 obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
2708 /* special case a rectangle */
2710 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2711 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2712 (((Pts
[0].y
== Pts
[1].y
) &&
2713 (Pts
[1].x
== Pts
[2].x
) &&
2714 (Pts
[2].y
== Pts
[3].y
) &&
2715 (Pts
[3].x
== Pts
[0].x
)) ||
2716 ((Pts
[0].x
== Pts
[1].x
) &&
2717 (Pts
[1].y
== Pts
[2].y
) &&
2718 (Pts
[2].x
== Pts
[3].x
) &&
2719 (Pts
[3].y
== Pts
[0].y
))))
2721 SetRectRgn( hrgn
, min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
2722 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
) );
2723 GDI_ReleaseObj( hrgn
);
2727 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2728 total
+= Count
[poly
];
2729 if (! (pETEs
= HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry
) * total
)))
2731 REGION_DeleteObject( hrgn
, obj
);
2734 pts
= FirstPtBlock
.pts
;
2735 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
2736 pSLL
= ET
.scanlines
.next
;
2737 curPtBlock
= &FirstPtBlock
;
2739 if (mode
!= WINDING
) {
2743 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2745 * Add a new edge to the active edge table when we
2746 * get to the next edge.
2748 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2749 REGION_loadAET(&AET
, pSLL
->edgelist
);
2756 * for each active edge
2759 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2763 * send out the buffer
2765 if (iPts
== NUMPTSTOBUFFER
) {
2766 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK
));
2768 WARN("Can't alloc tPB\n");
2771 curPtBlock
->next
= tmpPtBlock
;
2772 curPtBlock
= tmpPtBlock
;
2773 pts
= curPtBlock
->pts
;
2777 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
2779 REGION_InsertionSort(&AET
);
2786 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2788 * Add a new edge to the active edge table when we
2789 * get to the next edge.
2791 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2792 REGION_loadAET(&AET
, pSLL
->edgelist
);
2793 REGION_computeWAET(&AET
);
2801 * for each active edge
2805 * add to the buffer only those edges that
2806 * are in the Winding active edge table.
2808 if (pWETE
== pAET
) {
2809 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2813 * send out the buffer
2815 if (iPts
== NUMPTSTOBUFFER
) {
2816 tmpPtBlock
= HeapAlloc( GetProcessHeap(), 0,
2817 sizeof(POINTBLOCK
) );
2819 WARN("Can't alloc tPB\n");
2820 REGION_DeleteObject( hrgn
, obj
);
2823 curPtBlock
->next
= tmpPtBlock
;
2824 curPtBlock
= tmpPtBlock
;
2825 pts
= curPtBlock
->pts
;
2826 numFullPtBlocks
++; iPts
= 0;
2828 pWETE
= pWETE
->nextWETE
;
2830 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
2834 * recompute the winding active edge table if
2835 * we just resorted or have exited an edge.
2837 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2838 REGION_computeWAET(&AET
);
2843 REGION_FreeStorage(SLLBlock
.next
);
2844 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
2845 region
->type
= (region
->numRects
) ?
2846 ((region
->numRects
> 1) ? COMPLEXREGION
: SIMPLEREGION
)
2849 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;) {
2850 tmpPtBlock
= curPtBlock
->next
;
2851 HeapFree( GetProcessHeap(), 0, curPtBlock
);
2852 curPtBlock
= tmpPtBlock
;
2854 HeapFree( GetProcessHeap(), 0, pETEs
);
2855 GDI_ReleaseObj( hrgn
);
2860 /***********************************************************************
2861 * CreatePolygonRgn16 (GDI.63)
2863 HRGN16 WINAPI
CreatePolygonRgn16( const POINT16
* points
, INT16 count
,
2866 return CreatePolyPolygonRgn16( points
, &count
, 1, mode
);
2869 /***********************************************************************
2870 * CreatePolyPolygonRgn16 (GDI.451)
2872 HRGN16 WINAPI
CreatePolyPolygonRgn16( const POINT16
*points
,
2873 const INT16
*count
, INT16 nbpolygons
, INT16 mode
)
2880 for (i
= 0; i
< nbpolygons
; i
++)
2882 points32
= HeapAlloc( GetProcessHeap(), 0, npts
* sizeof(POINT
) );
2883 for (i
= 0; i
< npts
; i
++)
2884 CONV_POINT16TO32( &(points
[i
]), &(points32
[i
]) );
2886 count32
= HeapAlloc( GetProcessHeap(), 0, nbpolygons
* sizeof(INT
) );
2887 for (i
= 0; i
< nbpolygons
; i
++)
2888 count32
[i
] = count
[i
];
2889 hrgn
= CreatePolyPolygonRgn( points32
, count32
, nbpolygons
, mode
);
2890 HeapFree( GetProcessHeap(), 0, count32
);
2891 HeapFree( GetProcessHeap(), 0, points32
);
2895 /***********************************************************************
2896 * CreatePolygonRgn (GDI32.58)
2898 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2901 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);
2905 /***********************************************************************
2906 * GetRandomRgn [GDI32.215]
2909 * This function is documented in MSDN online
2911 INT WINAPI
GetRandomRgn(HDC hDC
, HRGN hRgn
, DWORD dwCode
)
2915 case 4: /* == SYSRGN ? */
2917 DC
*dc
= DC_GetDCPtr (hDC
);
2922 CombineRgn (hRgn
, dc
->w
.hVisRgn
, 0, RGN_COPY
);
2924 * On Windows NT/2000,
2925 * the region returned is in screen coordinates.
2927 * the region returned is in window coordinates
2929 vi
.dwOSVersionInfoSize
= sizeof(vi
);
2930 if (GetVersionExA( &vi
) && vi
.dwPlatformId
== VER_PLATFORM_WIN32_NT
)
2931 GetDCOrgEx(hDC
, &org
);
2934 org
.x
-= dc
->w
.DCOrgX
;
2935 org
.y
-= dc
->w
.DCOrgY
;
2936 OffsetRgn (hRgn
, org
.x
, org
.y
);
2937 GDI_ReleaseObj( hDC
);
2941 return GetClipRgn (hDC, hRgn);
2944 WARN("Unknown dwCode %ld\n", dwCode
);
2951 /***********************************************************************
2952 * REGION_CropAndOffsetRegion
2954 static BOOL
REGION_CropAndOffsetRegion(const POINT
* off
, const RECT
*rect
, WINEREGION
*rgnSrc
, WINEREGION
* rgnDst
)
2957 if( !rect
) /* just copy and offset */
2960 if( rgnDst
== rgnSrc
)
2962 if( off
->x
|| off
->y
)
2963 xrect
= rgnDst
->rects
;
2968 xrect
= HeapReAlloc( GetProcessHeap(), 0, rgnDst
->rects
,
2969 rgnSrc
->size
* sizeof( RECT
));
2974 if( rgnDst
!= rgnSrc
)
2975 memcpy( rgnDst
, rgnSrc
, sizeof( WINEREGION
));
2977 if( off
->x
|| off
->y
)
2979 for( i
= 0; i
< rgnDst
->numRects
; i
++ )
2981 xrect
[i
].left
= rgnSrc
->rects
[i
].left
+ off
->x
;
2982 xrect
[i
].right
= rgnSrc
->rects
[i
].right
+ off
->x
;
2983 xrect
[i
].top
= rgnSrc
->rects
[i
].top
+ off
->y
;
2984 xrect
[i
].bottom
= rgnSrc
->rects
[i
].bottom
+ off
->y
;
2986 rgnDst
->extents
.left
+= off
->x
;
2987 rgnDst
->extents
.right
+= off
->x
;
2988 rgnDst
->extents
.top
+= off
->y
;
2989 rgnDst
->extents
.bottom
+= off
->y
;
2992 memcpy( xrect
, rgnSrc
->rects
, rgnDst
->numRects
* sizeof(RECT
));
2993 rgnDst
->rects
= xrect
;
2997 else if ((rect
->left
>= rect
->right
) ||
2998 (rect
->top
>= rect
->bottom
) ||
2999 !EXTENTCHECK(rect
, &rgnSrc
->extents
))
3002 if( !rgnDst
->rects
)
3004 rgnDst
->rects
= HeapAlloc(GetProcessHeap(), 0, RGN_DEFAULT_RECTS
* sizeof( RECT
));
3006 rgnDst
->size
= RGN_DEFAULT_RECTS
;
3011 TRACE("cropped to empty!\n");
3012 EMPTY_REGION(rgnDst
);
3014 else /* region box and clipping rect appear to intersect */
3017 INT i
, j
, clipa
, clipb
;
3018 INT left
= rgnSrc
->extents
.right
+ off
->x
;
3019 INT right
= rgnSrc
->extents
.left
+ off
->x
;
3021 for( clipa
= 0; rgnSrc
->rects
[clipa
].bottom
<= rect
->top
; clipa
++ )
3022 ; /* skip bands above the clipping rectangle */
3024 for( clipb
= clipa
; clipb
< rgnSrc
->numRects
; clipb
++ )
3025 if( rgnSrc
->rects
[clipb
].top
>= rect
->bottom
)
3026 break; /* and below it */
3028 /* clipa - index of the first rect in the first intersecting band
3029 * clipb - index of the last rect in the last intersecting band
3032 if((rgnDst
!= rgnSrc
) && (rgnDst
->size
< (i
= (clipb
- clipa
))))
3034 rgnDst
->rects
= HeapReAlloc( GetProcessHeap(), 0,
3035 rgnDst
->rects
, i
* sizeof(RECT
));
3036 if( !rgnDst
->rects
) return FALSE
;
3040 if( TRACE_ON(region
) )
3042 REGION_DumpRegion( rgnSrc
);
3043 TRACE("\tclipa = %i, clipb = %i\n", clipa
, clipb
);
3046 for( i
= clipa
, j
= 0; i
< clipb
; i
++ )
3048 /* i - src index, j - dst index, j is always <= i for obvious reasons */
3050 lpr
= rgnSrc
->rects
+ i
;
3051 if( lpr
->left
< rect
->right
&& lpr
->right
> rect
->left
)
3053 rgnDst
->rects
[j
].top
= lpr
->top
+ off
->y
;
3054 rgnDst
->rects
[j
].bottom
= lpr
->bottom
+ off
->y
;
3055 rgnDst
->rects
[j
].left
= ((lpr
->left
> rect
->left
) ? lpr
->left
: rect
->left
) + off
->x
;
3056 rgnDst
->rects
[j
].right
= ((lpr
->right
< rect
->right
) ? lpr
->right
: rect
->right
) + off
->x
;
3058 if( rgnDst
->rects
[j
].left
< left
) left
= rgnDst
->rects
[j
].left
;
3059 if( rgnDst
->rects
[j
].right
> right
) right
= rgnDst
->rects
[j
].right
;
3065 if( j
== 0 ) goto empty
;
3067 rgnDst
->extents
.left
= left
;
3068 rgnDst
->extents
.right
= right
;
3070 left
= rect
->top
+ off
->y
;
3071 right
= rect
->bottom
+ off
->y
;
3073 rgnDst
->numRects
= j
--;
3074 for( i
= 0; i
<= j
; i
++ ) /* fixup top band */
3075 if( rgnDst
->rects
[i
].top
< left
)
3076 rgnDst
->rects
[i
].top
= left
;
3080 for( i
= j
; i
>= 0; i
-- ) /* fixup bottom band */
3081 if( rgnDst
->rects
[i
].bottom
> right
)
3082 rgnDst
->rects
[i
].bottom
= right
;
3086 rgnDst
->extents
.top
= rgnDst
->rects
[0].top
;
3087 rgnDst
->extents
.bottom
= rgnDst
->rects
[j
].bottom
;
3089 rgnDst
->type
= (j
>= 1) ? COMPLEXREGION
: SIMPLEREGION
;
3091 if( TRACE_ON(region
) )
3094 REGION_DumpRegion( rgnDst
);
3101 /***********************************************************************
3105 * hSrc: Region to crop and offset.
3106 * lpRect: Clipping rectangle. Can be NULL (no clipping).
3107 * lpPt: Points to offset the cropped region. Can be NULL (no offset).
3109 * hDst: Region to hold the result (a new region is created if it's 0).
3110 * Allowed to be the same region as hSrc in which case everything
3111 * will be done in place, with no memory reallocations.
3113 * Returns: hDst if success, 0 otherwise.
3115 HRGN
REGION_CropRgn( HRGN hDst
, HRGN hSrc
, const RECT
*lpRect
, const POINT
*lpPt
)
3117 /* Optimization of the following generic code:
3122 h = CreateRectRgn( lpRect->left, lpRect->top, lpRect->right, lpRect->bottom );
3124 h = CreateRectRgn( 0, 0, 0, 0 );
3125 if( hDst == 0 ) hDst = h;
3127 CombineRgn( hDst, hSrc, h, RGN_AND );
3129 CombineRgn( hDst, hSrc, 0, RGN_COPY );
3131 OffsetRgn( hDst, lpPt->x, lpPt->y );
3138 RGNOBJ
*objSrc
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
3147 if (!(objDst
= (RGNOBJ
*) GDI_GetObjPtr( hDst
, REGION_MAGIC
)))
3152 rgnDst
= objDst
->rgn
;
3156 if ((rgnDst
= HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION
))))
3158 rgnDst
->size
= rgnDst
->numRects
= 0;
3159 rgnDst
->rects
= NULL
; /* back end will allocate exact number */
3165 POINT pt
= { 0, 0 };
3167 if( !lpPt
) lpPt
= &pt
;
3170 TRACE("src %p -> dst %p (%i,%i)-(%i,%i) by (%li,%li)\n", objSrc
->rgn
, rgnDst
,
3171 lpRect
->left
, lpRect
->top
, lpRect
->right
, lpRect
->bottom
, lpPt
->x
, lpPt
->y
);
3173 TRACE("src %p -> dst %p by (%li,%li)\n", objSrc
->rgn
, rgnDst
, lpPt
->x
, lpPt
->y
);
3175 if( REGION_CropAndOffsetRegion( lpPt
, lpRect
, objSrc
->rgn
, rgnDst
) == FALSE
)
3177 if( hDst
) /* existing rgn */
3179 GDI_ReleaseObj(hDst
);
3185 else if( hDst
== 0 )
3187 if (!(objDst
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
, &hDst
)))
3191 HeapFree( GetProcessHeap(), 0, rgnDst
->rects
);
3192 HeapFree( GetProcessHeap(), 0, rgnDst
);
3195 objDst
->rgn
= rgnDst
;
3198 GDI_ReleaseObj(hDst
);
3202 GDI_ReleaseObj(hSrc
);
3208 /***********************************************************************
3209 * GetMetaRgn (GDI.328)
3211 INT WINAPI
GetMetaRgn( HDC hdc
, HRGN hRgn
)
3219 /***********************************************************************
3220 * SetMetaRgn (GDI.455)
3222 INT WINAPI
SetMetaRgn( HDC hdc
)