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...
89 #include "debugtools.h"
94 DEFAULT_DEBUG_CHANNEL(region
);
96 typedef void (*voidProcp
)();
98 /* Note the parameter order is different from the X11 equivalents */
100 static void REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
101 static void REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
102 static void REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
103 static void REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
104 static void REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
105 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
107 #define RGN_DEFAULT_RECTS 2
109 /***********************************************************************
111 * Outputs the contents of a WINEREGION
113 static void REGION_DumpRegion(WINEREGION
*pReg
)
115 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
117 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg
,
118 pReg
->extents
.left
, pReg
->extents
.top
,
119 pReg
->extents
.right
, pReg
->extents
.bottom
, pReg
->numRects
);
120 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
121 TRACE("\t%d,%d - %d,%d\n", pRect
->left
, pRect
->top
,
122 pRect
->right
, pRect
->bottom
);
127 /***********************************************************************
128 * REGION_AllocWineRegion
129 * Create a new empty WINEREGION.
131 static WINEREGION
*REGION_AllocWineRegion( INT n
)
135 if ((pReg
= HeapAlloc(SystemHeap
, 0, sizeof( WINEREGION
))))
137 if ((pReg
->rects
= HeapAlloc(SystemHeap
, 0, n
* sizeof( RECT
))))
143 HeapFree(SystemHeap
, 0, pReg
);
149 /***********************************************************************
150 * REGION_CreateRegion
151 * Create a new empty region.
153 static HRGN
REGION_CreateRegion( INT n
)
158 if(!(hrgn
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
)))
160 obj
= (RGNOBJ
*) GDI_HEAP_LOCK( hrgn
);
161 if(!(obj
->rgn
= REGION_AllocWineRegion(n
))) {
162 GDI_FreeObject( hrgn
);
165 GDI_HEAP_UNLOCK( hrgn
);
170 /***********************************************************************
171 * REGION_DestroyWineRegion
173 static void REGION_DestroyWineRegion( WINEREGION
* pReg
)
175 HeapFree( SystemHeap
, 0, pReg
->rects
);
176 HeapFree( SystemHeap
, 0, pReg
);
180 /***********************************************************************
181 * REGION_DeleteObject
183 BOOL
REGION_DeleteObject( HRGN hrgn
, RGNOBJ
* obj
)
185 TRACE(" %04x\n", hrgn
);
187 REGION_DestroyWineRegion( obj
->rgn
);
188 return GDI_FreeObject( hrgn
);
191 /***********************************************************************
192 * OffsetRgn16 (GDI.101)
194 INT16 WINAPI
OffsetRgn16( HRGN16 hrgn
, INT16 x
, INT16 y
)
196 return OffsetRgn( hrgn
, x
, y
);
199 /***********************************************************************
200 * OffsetRgn32 (GDI32.256)
202 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
204 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
209 int nbox
= obj
->rgn
->numRects
;
210 RECT
*pbox
= obj
->rgn
->rects
;
212 TRACE(" %04x %d,%d\n", hrgn
, x
, y
);
221 obj
->rgn
->extents
.left
+= x
;
222 obj
->rgn
->extents
.right
+= x
;
223 obj
->rgn
->extents
.top
+= y
;
224 obj
->rgn
->extents
.bottom
+= y
;
226 ret
= obj
->rgn
->type
;
227 GDI_HEAP_UNLOCK( hrgn
);
234 /***********************************************************************
235 * GetRgnBox16 (GDI.134)
237 INT16 WINAPI
GetRgnBox16( HRGN16 hrgn
, LPRECT16 rect
)
240 INT16 ret
= (INT16
)GetRgnBox( hrgn
, &r
);
241 CONV_RECT32TO16( &r
, rect
);
245 /***********************************************************************
246 * GetRgnBox32 (GDI32.219)
248 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
250 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
254 TRACE(" %04x\n", hrgn
);
255 rect
->left
= obj
->rgn
->extents
.left
;
256 rect
->top
= obj
->rgn
->extents
.top
;
257 rect
->right
= obj
->rgn
->extents
.right
;
258 rect
->bottom
= obj
->rgn
->extents
.bottom
;
259 ret
= obj
->rgn
->type
;
260 GDI_HEAP_UNLOCK(hrgn
);
267 /***********************************************************************
268 * CreateRectRgn16 (GDI.64)
270 * NOTE: Doesn't call CreateRectRgn32 because of differences in SetRectRgn16/32
272 HRGN16 WINAPI
CreateRectRgn16(INT16 left
, INT16 top
, INT16 right
, INT16 bottom
)
276 if (!(hrgn
= (HRGN16
)REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
279 SetRectRgn16(hrgn
, left
, top
, right
, bottom
);
284 /***********************************************************************
285 * CreateRectRgn32 (GDI32.59)
287 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
291 /* Allocate 2 rects by default to reduce the number of reallocs */
293 if (!(hrgn
= REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
296 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
300 /***********************************************************************
301 * CreateRectRgnIndirect16 (GDI.65)
303 HRGN16 WINAPI
CreateRectRgnIndirect16( const RECT16
* rect
)
305 return CreateRectRgn16( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
309 /***********************************************************************
310 * CreateRectRgnIndirect32 (GDI32.60)
312 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
314 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
318 /***********************************************************************
319 * SetRectRgn16 (GDI.172)
321 * NOTE: Win 3.1 sets region to empty if left > right
323 VOID WINAPI
SetRectRgn16( HRGN16 hrgn
, INT16 left
, INT16 top
,
324 INT16 right
, INT16 bottom
)
327 SetRectRgn( hrgn
, left
, top
, right
, bottom
);
329 SetRectRgn( hrgn
, 0, 0, 0, 0 );
333 /***********************************************************************
334 * SetRectRgn32 (GDI32.332)
336 * Allows either or both left and top to be greater than right or bottom.
338 BOOL WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
339 INT right
, INT bottom
)
343 TRACE(" %04x %d,%d-%d,%d\n",
344 hrgn
, left
, top
, right
, bottom
);
346 if (!(obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return FALSE
;
348 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
349 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
351 if((left
!= right
) && (top
!= bottom
))
353 obj
->rgn
->rects
->left
= obj
->rgn
->extents
.left
= left
;
354 obj
->rgn
->rects
->top
= obj
->rgn
->extents
.top
= top
;
355 obj
->rgn
->rects
->right
= obj
->rgn
->extents
.right
= right
;
356 obj
->rgn
->rects
->bottom
= obj
->rgn
->extents
.bottom
= bottom
;
357 obj
->rgn
->numRects
= 1;
358 obj
->rgn
->type
= SIMPLEREGION
;
361 EMPTY_REGION(obj
->rgn
);
363 GDI_HEAP_UNLOCK( hrgn
);
368 /***********************************************************************
369 * CreateRoundRectRgn16 (GDI.444)
371 * If either ellipse dimension is zero we call CreateRectRgn16 for its
372 * `special' behaviour. -ve ellipse dimensions can result in GPFs under win3.1
373 * we just let CreateRoundRectRgn32 convert them to +ve values.
376 HRGN16 WINAPI
CreateRoundRectRgn16( INT16 left
, INT16 top
,
377 INT16 right
, INT16 bottom
,
378 INT16 ellipse_width
, INT16 ellipse_height
)
380 if( ellipse_width
== 0 || ellipse_height
== 0 )
381 return CreateRectRgn16( left
, top
, right
, bottom
);
383 return (HRGN16
)CreateRoundRectRgn( left
, top
, right
, bottom
,
384 ellipse_width
, ellipse_height
);
387 /***********************************************************************
388 * CreateRoundRectRgn32 (GDI32.61)
390 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
391 INT right
, INT bottom
,
392 INT ellipse_width
, INT ellipse_height
)
396 int asq
, bsq
, d
, xd
, yd
;
399 /* Check if we can do a normal rectangle instead */
401 if ((ellipse_width
== 0) || (ellipse_height
== 0))
402 return CreateRectRgn( left
, top
, right
, bottom
);
404 /* Make the dimensions sensible */
406 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
407 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
409 ellipse_width
= abs(ellipse_width
);
410 ellipse_height
= abs(ellipse_height
);
414 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
415 if (!(hrgn
= REGION_CreateRegion(d
))) return 0;
416 obj
= (RGNOBJ
*) GDI_HEAP_LOCK( hrgn
);
417 TRACE("(%d,%d-%d,%d %dx%d): ret=%04x\n",
418 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
420 /* Check parameters */
422 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
423 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
425 /* Ellipse algorithm, based on an article by K. Porter */
426 /* in DDJ Graphics Programming Column, 8/89 */
428 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
429 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
430 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
432 yd
= asq
* ellipse_height
; /* 2a^2b */
434 rect
.left
= left
+ ellipse_width
/ 2;
435 rect
.right
= right
- ellipse_width
/ 2;
437 /* Loop to draw first half of quadrant */
441 if (d
> 0) /* if nearest pixel is toward the center */
443 /* move toward center */
445 rect
.bottom
= rect
.top
+ 1;
446 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
448 rect
.bottom
= rect
.top
+ 1;
449 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
453 rect
.left
--; /* next horiz point */
459 /* Loop to draw second half of quadrant */
461 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
464 /* next vertical point */
466 rect
.bottom
= rect
.top
+ 1;
467 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
469 rect
.bottom
= rect
.top
+ 1;
470 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
471 if (d
< 0) /* if nearest pixel is outside ellipse */
473 rect
.left
--; /* move away from center */
482 /* Add the inside rectangle */
487 rect
.bottom
= bottom
;
488 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
490 obj
->rgn
->type
= SIMPLEREGION
; /* FIXME? */
491 GDI_HEAP_UNLOCK( hrgn
);
496 /***********************************************************************
497 * CreateEllipticRgn16 (GDI.54)
499 HRGN16 WINAPI
CreateEllipticRgn16( INT16 left
, INT16 top
,
500 INT16 right
, INT16 bottom
)
502 return (HRGN16
)CreateRoundRectRgn( left
, top
, right
, bottom
,
503 right
-left
, bottom
-top
);
507 /***********************************************************************
508 * CreateEllipticRgn32 (GDI32.39)
510 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
511 INT right
, INT bottom
)
513 return CreateRoundRectRgn( left
, top
, right
, bottom
,
514 right
-left
, bottom
-top
);
518 /***********************************************************************
519 * CreateEllipticRgnIndirect16 (GDI.55)
521 HRGN16 WINAPI
CreateEllipticRgnIndirect16( const RECT16
*rect
)
523 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
524 rect
->bottom
, rect
->right
- rect
->left
,
525 rect
->bottom
- rect
->top
);
529 /***********************************************************************
530 * CreateEllipticRgnIndirect32 (GDI32.40)
532 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
534 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
535 rect
->bottom
, rect
->right
- rect
->left
,
536 rect
->bottom
- rect
->top
);
539 /***********************************************************************
540 * GetRegionData32 (GDI32.217)
543 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
546 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
548 TRACE(" %04x count = %ld, rgndata = %p\n",
549 hrgn
, count
, rgndata
);
553 size
= obj
->rgn
->numRects
* sizeof(RECT
);
554 if(count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
556 GDI_HEAP_UNLOCK( hrgn
);
557 return size
+ sizeof(RGNDATAHEADER
);
560 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
561 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
562 rgndata
->rdh
.nCount
= obj
->rgn
->numRects
;
563 rgndata
->rdh
.nRgnSize
= size
;
564 rgndata
->rdh
.rcBound
.left
= obj
->rgn
->extents
.left
;
565 rgndata
->rdh
.rcBound
.top
= obj
->rgn
->extents
.top
;
566 rgndata
->rdh
.rcBound
.right
= obj
->rgn
->extents
.right
;
567 rgndata
->rdh
.rcBound
.bottom
= obj
->rgn
->extents
.bottom
;
569 memcpy( rgndata
->Buffer
, obj
->rgn
->rects
, size
);
571 GDI_HEAP_UNLOCK( hrgn
);
575 /***********************************************************************
576 * GetRegionData16 (GDI.607)
577 * FIXME: is LPRGNDATA the same in Win16 and Win32 ?
579 DWORD WINAPI
GetRegionData16(HRGN16 hrgn
, DWORD count
, LPRGNDATA rgndata
)
581 return GetRegionData((HRGN
)hrgn
, count
, rgndata
);
584 /***********************************************************************
585 * ExtCreateRegion (GDI32.94)
588 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
592 TRACE(" %p %ld %p = ", lpXform
, dwCount
, rgndata
);
595 WARN("(Xform not implemented - ignored) ");
597 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
599 /* FIXME: We can use CreatePolyPolygonRgn() here
600 * for trapezoidal data */
602 WARN("(Unsupported region data) ");
606 if( (hrgn
= REGION_CreateRegion( rgndata
->rdh
.nCount
)) )
608 RECT
*pCurRect
, *pEndRect
;
609 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
611 pEndRect
= (RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
612 for(pCurRect
= (RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
613 REGION_UnionRectWithRegion( pCurRect
, obj
->rgn
);
614 GDI_HEAP_UNLOCK( hrgn
);
616 TRACE("%04x\n", hrgn
);
624 /***********************************************************************
625 * PtInRegion16 (GDI.161)
627 BOOL16 WINAPI
PtInRegion16( HRGN16 hrgn
, INT16 x
, INT16 y
)
629 return PtInRegion( hrgn
, x
, y
);
633 /***********************************************************************
634 * PtInRegion32 (GDI32.278)
636 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
640 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
645 if (obj
->rgn
->numRects
> 0 && INRECT(obj
->rgn
->extents
, x
, y
))
646 for (i
= 0; i
< obj
->rgn
->numRects
; i
++)
647 if (INRECT (obj
->rgn
->rects
[i
], x
, y
))
649 GDI_HEAP_UNLOCK( hrgn
);
656 /***********************************************************************
657 * RectInRegion16 (GDI.181)
659 BOOL16 WINAPI
RectInRegion16( HRGN16 hrgn
, const RECT16
*rect
)
663 CONV_RECT16TO32(rect
, &r32
);
664 return (BOOL16
)RectInRegion(hrgn
, &r32
);
668 /***********************************************************************
669 * RectInRegion32 (GDI32.281)
671 * Returns TRUE if rect is at least partly inside hrgn
673 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
677 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
679 RECT
*pCurRect
, *pRectEnd
;
682 /* this is (just) a useful optimization */
683 if ((obj
->rgn
->numRects
> 0) && EXTENTCHECK(&obj
->rgn
->extents
,
686 for (pCurRect
= obj
->rgn
->rects
, pRectEnd
= pCurRect
+
687 obj
->rgn
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
689 if (pCurRect
->bottom
<= rect
->top
)
690 continue; /* not far enough down yet */
692 if (pCurRect
->top
>= rect
->bottom
) {
693 ret
= FALSE
; /* too far down */
697 if (pCurRect
->right
<= rect
->left
)
698 continue; /* not far enough over yet */
700 if (pCurRect
->left
>= rect
->right
) {
708 GDI_HEAP_UNLOCK(hrgn
);
714 /***********************************************************************
715 * EqualRgn16 (GDI.72)
717 BOOL16 WINAPI
EqualRgn16( HRGN16 rgn1
, HRGN16 rgn2
)
719 return EqualRgn( rgn1
, rgn2
);
723 /***********************************************************************
724 * EqualRgn32 (GDI32.90)
726 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
731 if ((obj1
= (RGNOBJ
*) GDI_GetObjPtr( hrgn1
, REGION_MAGIC
)))
733 if ((obj2
= (RGNOBJ
*) GDI_GetObjPtr( hrgn2
, REGION_MAGIC
)))
738 if ( obj1
->rgn
->numRects
!= obj2
->rgn
->numRects
) ret
= FALSE
;
739 else if ( obj1
->rgn
->numRects
== 0 ) ret
= TRUE
;
740 else if ( !EqualRect(&obj1
->rgn
->extents
, &obj2
->rgn
->extents
) )
742 else for( i
= 0; i
< obj1
->rgn
->numRects
; i
++ ) {
743 if (!EqualRect(obj1
->rgn
->rects
+ i
, obj2
->rgn
->rects
+ i
)) {
748 GDI_HEAP_UNLOCK(hrgn2
);
750 GDI_HEAP_UNLOCK(hrgn1
);
754 /***********************************************************************
755 * REGION_UnionRectWithRegion
756 * Adds a rectangle to a WINEREGION
757 * See below for REGION_UnionRectWithRgn
759 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
763 region
.rects
= ®ion
.extents
;
766 region
.type
= SIMPLEREGION
;
767 CopyRect(&(region
.extents
), rect
);
768 REGION_UnionRegion(rgn
, rgn
, ®ion
);
772 /***********************************************************************
773 * REGION_UnionRectWithRgn
774 * Adds a rectangle to a HRGN32
775 * A helper used by scroll.c
777 BOOL
REGION_UnionRectWithRgn( HRGN hrgn
, const RECT
*lpRect
)
779 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
781 if(!obj
) return FALSE
;
782 REGION_UnionRectWithRegion( lpRect
, obj
->rgn
);
783 GDI_HEAP_UNLOCK(hrgn
);
787 /***********************************************************************
788 * REGION_CreateFrameRgn
790 * Create a region that is a frame around another region.
791 * Expand all rectangles by +/- x and y, then subtract original region.
793 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
796 RGNOBJ
*srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
798 if (srcObj
->rgn
->numRects
!= 0)
800 RGNOBJ
* destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
801 RECT
*pRect
, *pEndRect
;
804 EMPTY_REGION( destObj
->rgn
);
806 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
807 for(pRect
= srcObj
->rgn
->rects
; pRect
< pEndRect
; pRect
++)
809 tempRect
.left
= pRect
->left
- x
;
810 tempRect
.top
= pRect
->top
- y
;
811 tempRect
.right
= pRect
->right
+ x
;
812 tempRect
.bottom
= pRect
->bottom
+ y
;
813 REGION_UnionRectWithRegion( &tempRect
, destObj
->rgn
);
815 REGION_SubtractRegion( destObj
->rgn
, destObj
->rgn
, srcObj
->rgn
);
816 GDI_HEAP_UNLOCK ( hDest
);
821 GDI_HEAP_UNLOCK( hSrc
);
825 /***********************************************************************
828 * Convert region to device co-ords for the supplied dc.
830 BOOL
REGION_LPTODP( HDC hdc
, HRGN hDest
, HRGN hSrc
)
832 RECT
*pCurRect
, *pEndRect
;
833 RGNOBJ
*srcObj
, *destObj
;
834 DC
* dc
= DC_GetDCPtr( hdc
);
837 TRACE(" hdc=%04x dest=%04x src=%04x\n",
840 if (dc
->w
.MapMode
== MM_TEXT
) /* Requires only a translation */
842 if( CombineRgn( hDest
, hSrc
, 0, RGN_COPY
) == ERROR
) return FALSE
;
843 OffsetRgn( hDest
, dc
->vportOrgX
- dc
->wndOrgX
,
844 dc
->vportOrgY
- dc
->wndOrgY
);
848 if(!( srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
) ))
850 if(!( destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
) ))
852 GDI_HEAP_UNLOCK( hSrc
);
855 EMPTY_REGION( destObj
->rgn
);
857 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
858 for(pCurRect
= srcObj
->rgn
->rects
; pCurRect
< pEndRect
; pCurRect
++)
861 tmpRect
.left
= XLPTODP( dc
, tmpRect
.left
);
862 tmpRect
.top
= YLPTODP( dc
, tmpRect
.top
);
863 tmpRect
.right
= XLPTODP( dc
, tmpRect
.right
);
864 tmpRect
.bottom
= YLPTODP( dc
, tmpRect
.bottom
);
865 REGION_UnionRectWithRegion( &tmpRect
, destObj
->rgn
);
868 GDI_HEAP_UNLOCK( hDest
);
869 GDI_HEAP_UNLOCK( hSrc
);
873 /***********************************************************************
874 * CombineRgn16 (GDI.451)
876 INT16 WINAPI
CombineRgn16(HRGN16 hDest
, HRGN16 hSrc1
, HRGN16 hSrc2
, INT16 mode
)
878 return (INT16
)CombineRgn( hDest
, hSrc1
, hSrc2
, mode
);
882 /***********************************************************************
883 * CombineRgn32 (GDI32.19)
885 * Note: The behavior is correct even if src and dest regions are the same.
887 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
889 RGNOBJ
*destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
892 TRACE(" %04x,%04x -> %04x mode=%x\n",
893 hSrc1
, hSrc2
, hDest
, mode
);
896 RGNOBJ
*src1Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc1
, REGION_MAGIC
);
902 REGION_DumpRegion(src1Obj
->rgn
);
903 if (mode
== RGN_COPY
)
905 REGION_CopyRegion( destObj
->rgn
, src1Obj
->rgn
);
906 result
= destObj
->rgn
->type
;
910 RGNOBJ
*src2Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc2
, REGION_MAGIC
);
916 REGION_DumpRegion(src2Obj
->rgn
);
920 REGION_IntersectRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
923 REGION_UnionRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
926 REGION_XorRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
929 REGION_SubtractRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
932 result
= destObj
->rgn
->type
;
933 GDI_HEAP_UNLOCK( hSrc2
);
936 GDI_HEAP_UNLOCK( hSrc1
);
940 REGION_DumpRegion(destObj
->rgn
);
942 GDI_HEAP_UNLOCK( hDest
);
944 ERR("Invalid rgn=%04x\n", hDest
);
949 /***********************************************************************
951 * Re-calculate the extents of a region
953 static void REGION_SetExtents (WINEREGION
*pReg
)
955 RECT
*pRect
, *pRectEnd
, *pExtents
;
957 if (pReg
->numRects
== 0)
959 pReg
->extents
.left
= 0;
960 pReg
->extents
.top
= 0;
961 pReg
->extents
.right
= 0;
962 pReg
->extents
.bottom
= 0;
966 pExtents
= &pReg
->extents
;
968 pRectEnd
= &pRect
[pReg
->numRects
- 1];
971 * Since pRect is the first rectangle in the region, it must have the
972 * smallest top and since pRectEnd is the last rectangle in the region,
973 * it must have the largest bottom, because of banding. Initialize left and
974 * right from pRect and pRectEnd, resp., as good things to initialize them
977 pExtents
->left
= pRect
->left
;
978 pExtents
->top
= pRect
->top
;
979 pExtents
->right
= pRectEnd
->right
;
980 pExtents
->bottom
= pRectEnd
->bottom
;
982 while (pRect
<= pRectEnd
)
984 if (pRect
->left
< pExtents
->left
)
985 pExtents
->left
= pRect
->left
;
986 if (pRect
->right
> pExtents
->right
)
987 pExtents
->right
= pRect
->right
;
992 /***********************************************************************
995 static void REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
997 if (dst
!= src
) /* don't want to copy to itself */
999 if (dst
->size
< src
->numRects
)
1001 if (! (dst
->rects
= HeapReAlloc( SystemHeap
, 0, dst
->rects
,
1002 src
->numRects
* sizeof(RECT
) )))
1004 dst
->size
= src
->numRects
;
1006 dst
->numRects
= src
->numRects
;
1007 dst
->extents
.left
= src
->extents
.left
;
1008 dst
->extents
.top
= src
->extents
.top
;
1009 dst
->extents
.right
= src
->extents
.right
;
1010 dst
->extents
.bottom
= src
->extents
.bottom
;
1011 dst
->type
= src
->type
;
1013 memcpy((char *) dst
->rects
, (char *) src
->rects
,
1014 (int) (src
->numRects
* sizeof(RECT
)));
1019 /***********************************************************************
1022 * Attempt to merge the rects in the current band with those in the
1023 * previous one. Used only by REGION_RegionOp.
1026 * The new index for the previous band.
1029 * If coalescing takes place:
1030 * - rectangles in the previous band will have their bottom fields
1032 * - pReg->numRects will be decreased.
1035 static INT
REGION_Coalesce (
1036 WINEREGION
*pReg
, /* Region to coalesce */
1037 INT prevStart
, /* Index of start of previous band */
1038 INT curStart
/* Index of start of current band */
1040 RECT
*pPrevRect
; /* Current rect in previous band */
1041 RECT
*pCurRect
; /* Current rect in current band */
1042 RECT
*pRegEnd
; /* End of region */
1043 INT curNumRects
; /* Number of rectangles in current band */
1044 INT prevNumRects
; /* Number of rectangles in previous band */
1045 INT bandtop
; /* top coordinate for current band */
1047 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1049 pPrevRect
= &pReg
->rects
[prevStart
];
1050 prevNumRects
= curStart
- prevStart
;
1053 * Figure out how many rectangles are in the current band. Have to do
1054 * this because multiple bands could have been added in REGION_RegionOp
1055 * at the end when one region has been exhausted.
1057 pCurRect
= &pReg
->rects
[curStart
];
1058 bandtop
= pCurRect
->top
;
1059 for (curNumRects
= 0;
1060 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1066 if (pCurRect
!= pRegEnd
)
1069 * If more than one band was added, we have to find the start
1070 * of the last band added so the next coalescing job can start
1071 * at the right place... (given when multiple bands are added,
1072 * this may be pointless -- see above).
1075 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1079 curStart
= pRegEnd
- pReg
->rects
;
1080 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1083 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1084 pCurRect
-= curNumRects
;
1086 * The bands may only be coalesced if the bottom of the previous
1087 * matches the top scanline of the current.
1089 if (pPrevRect
->bottom
== pCurRect
->top
)
1092 * Make sure the bands have rects in the same places. This
1093 * assumes that rects have been added in such a way that they
1094 * cover the most area possible. I.e. two rects in a band must
1095 * have some horizontal space between them.
1099 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1100 (pPrevRect
->right
!= pCurRect
->right
))
1103 * The bands don't line up so they can't be coalesced.
1110 } while (prevNumRects
!= 0);
1112 pReg
->numRects
-= curNumRects
;
1113 pCurRect
-= curNumRects
;
1114 pPrevRect
-= curNumRects
;
1117 * The bands may be merged, so set the bottom of each rect
1118 * in the previous band to that of the corresponding rect in
1123 pPrevRect
->bottom
= pCurRect
->bottom
;
1127 } while (curNumRects
!= 0);
1130 * If only one band was added to the region, we have to backup
1131 * curStart to the start of the previous band.
1133 * If more than one band was added to the region, copy the
1134 * other bands down. The assumption here is that the other bands
1135 * came from the same region as the current one and no further
1136 * coalescing can be done on them since it's all been done
1137 * already... curStart is already in the right place.
1139 if (pCurRect
== pRegEnd
)
1141 curStart
= prevStart
;
1147 *pPrevRect
++ = *pCurRect
++;
1148 } while (pCurRect
!= pRegEnd
);
1156 /***********************************************************************
1159 * Apply an operation to two regions. Called by REGION_Union,
1160 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1166 * The new region is overwritten.
1169 * The idea behind this function is to view the two regions as sets.
1170 * Together they cover a rectangle of area that this function divides
1171 * into horizontal bands where points are covered only by one region
1172 * or by both. For the first case, the nonOverlapFunc is called with
1173 * each the band and the band's upper and lower extents. For the
1174 * second, the overlapFunc is called to process the entire band. It
1175 * is responsible for clipping the rectangles in the band, though
1176 * this function provides the boundaries.
1177 * At the end of each band, the new region is coalesced, if possible,
1178 * to reduce the number of rectangles in the region.
1181 static void REGION_RegionOp(
1182 WINEREGION
*newReg
, /* Place to store result */
1183 WINEREGION
*reg1
, /* First region in operation */
1184 WINEREGION
*reg2
, /* 2nd region in operation */
1185 void (*overlapFunc
)(), /* Function to call for over-lapping bands */
1186 void (*nonOverlap1Func
)(), /* Function to call for non-overlapping bands in region 1 */
1187 void (*nonOverlap2Func
)() /* Function to call for non-overlapping bands in region 2 */
1189 RECT
*r1
; /* Pointer into first region */
1190 RECT
*r2
; /* Pointer into 2d region */
1191 RECT
*r1End
; /* End of 1st region */
1192 RECT
*r2End
; /* End of 2d region */
1193 INT ybot
; /* Bottom of intersection */
1194 INT ytop
; /* Top of intersection */
1195 RECT
*oldRects
; /* Old rects for newReg */
1196 INT prevBand
; /* Index of start of
1197 * previous band in newReg */
1198 INT curBand
; /* Index of start of current
1200 RECT
*r1BandEnd
; /* End of current band in r1 */
1201 RECT
*r2BandEnd
; /* End of current band in r2 */
1202 INT top
; /* Top of non-overlapping band */
1203 INT bot
; /* Bottom of non-overlapping band */
1207 * set r1, r2, r1End and r2End appropriately, preserve the important
1208 * parts of the destination region until the end in case it's one of
1209 * the two source regions, then mark the "new" region empty, allocating
1210 * another array of rectangles for it to use.
1214 r1End
= r1
+ reg1
->numRects
;
1215 r2End
= r2
+ reg2
->numRects
;
1219 * newReg may be one of the src regions so we can't empty it. We keep a
1220 * note of its rects pointer (so that we can free them later), preserve its
1221 * extents and simply set numRects to zero.
1224 oldRects
= newReg
->rects
;
1225 newReg
->numRects
= 0;
1228 * Allocate a reasonable number of rectangles for the new region. The idea
1229 * is to allocate enough so the individual functions don't need to
1230 * reallocate and copy the array, which is time consuming, yet we don't
1231 * have to worry about using too much memory. I hope to be able to
1232 * nuke the Xrealloc() at the end of this function eventually.
1234 newReg
->size
= MAX(reg1
->numRects
,reg2
->numRects
) * 2;
1236 if (! (newReg
->rects
= HeapAlloc( SystemHeap
, 0,
1237 sizeof(RECT
) * newReg
->size
)))
1244 * Initialize ybot and ytop.
1245 * In the upcoming loop, ybot and ytop serve different functions depending
1246 * on whether the band being handled is an overlapping or non-overlapping
1248 * In the case of a non-overlapping band (only one of the regions
1249 * has points in the band), ybot is the bottom of the most recent
1250 * intersection and thus clips the top of the rectangles in that band.
1251 * ytop is the top of the next intersection between the two regions and
1252 * serves to clip the bottom of the rectangles in the current band.
1253 * For an overlapping band (where the two regions intersect), ytop clips
1254 * the top of the rectangles of both regions and ybot clips the bottoms.
1256 if (reg1
->extents
.top
< reg2
->extents
.top
)
1257 ybot
= reg1
->extents
.top
;
1259 ybot
= reg2
->extents
.top
;
1262 * prevBand serves to mark the start of the previous band so rectangles
1263 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1264 * In the beginning, there is no previous band, so prevBand == curBand
1265 * (curBand is set later on, of course, but the first band will always
1266 * start at index 0). prevBand and curBand must be indices because of
1267 * the possible expansion, and resultant moving, of the new region's
1268 * array of rectangles.
1274 curBand
= newReg
->numRects
;
1277 * This algorithm proceeds one source-band (as opposed to a
1278 * destination band, which is determined by where the two regions
1279 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1280 * rectangle after the last one in the current band for their
1281 * respective regions.
1284 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1290 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1296 * First handle the band that doesn't intersect, if any.
1298 * Note that attention is restricted to one band in the
1299 * non-intersecting region at once, so if a region has n
1300 * bands between the current position and the next place it overlaps
1301 * the other, this entire loop will be passed through n times.
1303 if (r1
->top
< r2
->top
)
1305 top
= MAX(r1
->top
,ybot
);
1306 bot
= MIN(r1
->bottom
,r2
->top
);
1308 if ((top
!= bot
) && (nonOverlap1Func
!= (void (*)())NULL
))
1310 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1315 else if (r2
->top
< r1
->top
)
1317 top
= MAX(r2
->top
,ybot
);
1318 bot
= MIN(r2
->bottom
,r1
->top
);
1320 if ((top
!= bot
) && (nonOverlap2Func
!= (void (*)())NULL
))
1322 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1333 * If any rectangles got added to the region, try and coalesce them
1334 * with rectangles from the previous band. Note we could just do
1335 * this test in miCoalesce, but some machines incur a not
1336 * inconsiderable cost for function calls, so...
1338 if (newReg
->numRects
!= curBand
)
1340 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1344 * Now see if we've hit an intersecting band. The two bands only
1345 * intersect if ybot > ytop
1347 ybot
= MIN(r1
->bottom
, r2
->bottom
);
1348 curBand
= newReg
->numRects
;
1351 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1355 if (newReg
->numRects
!= curBand
)
1357 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1361 * If we've finished with a band (bottom == ybot) we skip forward
1362 * in the region to the next band.
1364 if (r1
->bottom
== ybot
)
1368 if (r2
->bottom
== ybot
)
1372 } while ((r1
!= r1End
) && (r2
!= r2End
));
1375 * Deal with whichever region still has rectangles left.
1377 curBand
= newReg
->numRects
;
1380 if (nonOverlap1Func
!= (void (*)())NULL
)
1385 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1389 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1390 MAX(r1
->top
,ybot
), r1
->bottom
);
1392 } while (r1
!= r1End
);
1395 else if ((r2
!= r2End
) && (nonOverlap2Func
!= (void (*)())NULL
))
1400 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1404 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1405 MAX(r2
->top
,ybot
), r2
->bottom
);
1407 } while (r2
!= r2End
);
1410 if (newReg
->numRects
!= curBand
)
1412 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1416 * A bit of cleanup. To keep regions from growing without bound,
1417 * we shrink the array of rectangles to match the new number of
1418 * rectangles in the region. This never goes to 0, however...
1420 * Only do this stuff if the number of rectangles allocated is more than
1421 * twice the number of rectangles in the region (a simple optimization...).
1423 if ((newReg
->numRects
< (newReg
->size
>> 1)) && (newReg
->numRects
> 2))
1425 if (REGION_NOT_EMPTY(newReg
))
1427 RECT
*prev_rects
= newReg
->rects
;
1428 newReg
->size
= newReg
->numRects
;
1429 newReg
->rects
= HeapReAlloc( SystemHeap
, 0, newReg
->rects
,
1430 sizeof(RECT
) * newReg
->size
);
1431 if (! newReg
->rects
)
1432 newReg
->rects
= prev_rects
;
1437 * No point in doing the extra work involved in an Xrealloc if
1438 * the region is empty
1441 HeapFree( SystemHeap
, 0, newReg
->rects
);
1442 newReg
->rects
= HeapAlloc( SystemHeap
, 0, sizeof(RECT
) );
1445 HeapFree( SystemHeap
, 0, oldRects
);
1449 /***********************************************************************
1450 * Region Intersection
1451 ***********************************************************************/
1454 /***********************************************************************
1457 * Handle an overlapping band for REGION_Intersect.
1463 * Rectangles may be added to the region.
1466 static void REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1467 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1473 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1475 while ((r1
!= r1End
) && (r2
!= r2End
))
1477 left
= MAX(r1
->left
, r2
->left
);
1478 right
= MIN(r1
->right
, r2
->right
);
1481 * If there's any overlap between the two rectangles, add that
1482 * overlap to the new region.
1483 * There's no need to check for subsumption because the only way
1484 * such a need could arise is if some region has two rectangles
1485 * right next to each other. Since that should never happen...
1489 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1490 pNextRect
->left
= left
;
1491 pNextRect
->top
= top
;
1492 pNextRect
->right
= right
;
1493 pNextRect
->bottom
= bottom
;
1494 pReg
->numRects
+= 1;
1499 * Need to advance the pointers. Shift the one that extends
1500 * to the right the least, since the other still has a chance to
1501 * overlap with that region's next rectangle, if you see what I mean.
1503 if (r1
->right
< r2
->right
)
1507 else if (r2
->right
< r1
->right
)
1520 /***********************************************************************
1521 * REGION_IntersectRegion
1523 static void REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1526 /* check for trivial reject */
1527 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1528 (!EXTENTCHECK(®1
->extents
, ®2
->extents
)))
1529 newReg
->numRects
= 0;
1531 REGION_RegionOp (newReg
, reg1
, reg2
,
1532 (voidProcp
) REGION_IntersectO
, (voidProcp
) NULL
, (voidProcp
) NULL
);
1535 * Can't alter newReg's extents before we call miRegionOp because
1536 * it might be one of the source regions and miRegionOp depends
1537 * on the extents of those regions being the same. Besides, this
1538 * way there's no checking against rectangles that will be nuked
1539 * due to coalescing, so we have to examine fewer rectangles.
1541 REGION_SetExtents(newReg
);
1542 newReg
->type
= (newReg
->numRects
) ? COMPLEXREGION
: NULLREGION
;
1546 /***********************************************************************
1548 ***********************************************************************/
1550 /***********************************************************************
1553 * Handle a non-overlapping band for the union operation. Just
1554 * Adds the rectangles into the region. Doesn't have to check for
1555 * subsumption or anything.
1561 * pReg->numRects is incremented and the final rectangles overwritten
1562 * with the rectangles we're passed.
1565 static void REGION_UnionNonO (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1566 INT top
, INT bottom
)
1570 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1574 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1575 pNextRect
->left
= r
->left
;
1576 pNextRect
->top
= top
;
1577 pNextRect
->right
= r
->right
;
1578 pNextRect
->bottom
= bottom
;
1579 pReg
->numRects
+= 1;
1586 /***********************************************************************
1589 * Handle an overlapping band for the union operation. Picks the
1590 * left-most rectangle each time and merges it into the region.
1596 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1600 static void REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1601 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1605 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1607 #define MERGERECT(r) \
1608 if ((pReg->numRects != 0) && \
1609 (pNextRect[-1].top == top) && \
1610 (pNextRect[-1].bottom == bottom) && \
1611 (pNextRect[-1].right >= r->left)) \
1613 if (pNextRect[-1].right < r->right) \
1615 pNextRect[-1].right = r->right; \
1620 MEMCHECK(pReg, pNextRect, pReg->rects); \
1621 pNextRect->top = top; \
1622 pNextRect->bottom = bottom; \
1623 pNextRect->left = r->left; \
1624 pNextRect->right = r->right; \
1625 pReg->numRects += 1; \
1630 while ((r1
!= r1End
) && (r2
!= r2End
))
1632 if (r1
->left
< r2
->left
)
1647 } while (r1
!= r1End
);
1649 else while (r2
!= r2End
)
1656 /***********************************************************************
1657 * REGION_UnionRegion
1659 static void REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1662 /* checks all the simple cases */
1665 * Region 1 and 2 are the same or region 1 is empty
1667 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
1670 REGION_CopyRegion(newReg
, reg2
);
1675 * if nothing to union (region 2 empty)
1677 if (!(reg2
->numRects
))
1680 REGION_CopyRegion(newReg
, reg1
);
1685 * Region 1 completely subsumes region 2
1687 if ((reg1
->numRects
== 1) &&
1688 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
1689 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
1690 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
1691 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
1694 REGION_CopyRegion(newReg
, reg1
);
1699 * Region 2 completely subsumes region 1
1701 if ((reg2
->numRects
== 1) &&
1702 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
1703 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
1704 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
1705 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
1708 REGION_CopyRegion(newReg
, reg2
);
1712 REGION_RegionOp (newReg
, reg1
, reg2
, (voidProcp
) REGION_UnionO
,
1713 (voidProcp
) REGION_UnionNonO
, (voidProcp
) REGION_UnionNonO
);
1715 newReg
->extents
.left
= MIN(reg1
->extents
.left
, reg2
->extents
.left
);
1716 newReg
->extents
.top
= MIN(reg1
->extents
.top
, reg2
->extents
.top
);
1717 newReg
->extents
.right
= MAX(reg1
->extents
.right
, reg2
->extents
.right
);
1718 newReg
->extents
.bottom
= MAX(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
1719 newReg
->type
= (newReg
->numRects
) ? COMPLEXREGION
: NULLREGION
;
1723 /***********************************************************************
1724 * Region Subtraction
1725 ***********************************************************************/
1727 /***********************************************************************
1728 * REGION_SubtractNonO1
1730 * Deal with non-overlapping band for subtraction. Any parts from
1731 * region 2 we discard. Anything from region 1 we add to the region.
1737 * pReg may be affected.
1740 static void REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1741 INT top
, INT bottom
)
1745 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1749 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1750 pNextRect
->left
= r
->left
;
1751 pNextRect
->top
= top
;
1752 pNextRect
->right
= r
->right
;
1753 pNextRect
->bottom
= bottom
;
1754 pReg
->numRects
+= 1;
1762 /***********************************************************************
1765 * Overlapping band subtraction. x1 is the left-most point not yet
1772 * pReg may have rectangles added to it.
1775 static void REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1776 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1782 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1784 while ((r1
!= r1End
) && (r2
!= r2End
))
1786 if (r2
->right
<= left
)
1789 * Subtrahend missed the boat: go to next subtrahend.
1793 else if (r2
->left
<= left
)
1796 * Subtrahend preceeds minuend: nuke left edge of minuend.
1799 if (left
>= r1
->right
)
1802 * Minuend completely covered: advance to next minuend and
1803 * reset left fence to edge of new minuend.
1812 * Subtrahend now used up since it doesn't extend beyond
1818 else if (r2
->left
< r1
->right
)
1821 * Left part of subtrahend covers part of minuend: add uncovered
1822 * part of minuend to region and skip to next subtrahend.
1824 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1825 pNextRect
->left
= left
;
1826 pNextRect
->top
= top
;
1827 pNextRect
->right
= r2
->left
;
1828 pNextRect
->bottom
= bottom
;
1829 pReg
->numRects
+= 1;
1832 if (left
>= r1
->right
)
1835 * Minuend used up: advance to new...
1844 * Subtrahend used up
1852 * Minuend used up: add any remaining piece before advancing.
1854 if (r1
->right
> left
)
1856 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1857 pNextRect
->left
= left
;
1858 pNextRect
->top
= top
;
1859 pNextRect
->right
= r1
->right
;
1860 pNextRect
->bottom
= bottom
;
1861 pReg
->numRects
+= 1;
1870 * Add remaining minuend rectangles to region.
1874 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1875 pNextRect
->left
= left
;
1876 pNextRect
->top
= top
;
1877 pNextRect
->right
= r1
->right
;
1878 pNextRect
->bottom
= bottom
;
1879 pReg
->numRects
+= 1;
1890 /***********************************************************************
1891 * REGION_SubtractRegion
1893 * Subtract regS from regM and leave the result in regD.
1894 * S stands for subtrahend, M for minuend and D for difference.
1900 * regD is overwritten.
1903 static void REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
,
1906 /* check for trivial reject */
1907 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
1908 (!EXTENTCHECK(®M
->extents
, ®S
->extents
)) )
1910 REGION_CopyRegion(regD
, regM
);
1914 REGION_RegionOp (regD
, regM
, regS
, (voidProcp
) REGION_SubtractO
,
1915 (voidProcp
) REGION_SubtractNonO1
, (voidProcp
) NULL
);
1918 * Can't alter newReg's extents before we call miRegionOp because
1919 * it might be one of the source regions and miRegionOp depends
1920 * on the extents of those regions being the unaltered. Besides, this
1921 * way there's no checking against rectangles that will be nuked
1922 * due to coalescing, so we have to examine fewer rectangles.
1924 REGION_SetExtents (regD
);
1925 regD
->type
= (regD
->numRects
) ? COMPLEXREGION
: NULLREGION
;
1929 /***********************************************************************
1932 static void REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
,
1935 WINEREGION
*tra
, *trb
;
1937 if ((! (tra
= REGION_AllocWineRegion(sra
->numRects
+ 1))) ||
1938 (! (trb
= REGION_AllocWineRegion(srb
->numRects
+ 1))))
1940 REGION_SubtractRegion(tra
,sra
,srb
);
1941 REGION_SubtractRegion(trb
,srb
,sra
);
1942 REGION_UnionRegion(dr
,tra
,trb
);
1943 REGION_DestroyWineRegion(tra
);
1944 REGION_DestroyWineRegion(trb
);
1948 /**************************************************************************
1952 *************************************************************************/
1954 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
1955 #define SMALL_COORDINATE 0x80000000
1957 /***********************************************************************
1958 * REGION_InsertEdgeInET
1960 * Insert the given edge into the edge table.
1961 * First we must find the correct bucket in the
1962 * Edge table, then find the right slot in the
1963 * bucket. Finally, we can insert it.
1966 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
1967 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
1970 EdgeTableEntry
*start
, *prev
;
1971 ScanLineList
*pSLL
, *pPrevSLL
;
1972 ScanLineListBlock
*tmpSLLBlock
;
1975 * find the right bucket to put the edge into
1977 pPrevSLL
= &ET
->scanlines
;
1978 pSLL
= pPrevSLL
->next
;
1979 while (pSLL
&& (pSLL
->scanline
< scanline
))
1986 * reassign pSLL (pointer to ScanLineList) if necessary
1988 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
1990 if (*iSLLBlock
> SLLSPERBLOCK
-1)
1992 tmpSLLBlock
= HeapAlloc( SystemHeap
, 0, sizeof(ScanLineListBlock
));
1995 WARN("Can't alloc SLLB\n");
1998 (*SLLBlock
)->next
= tmpSLLBlock
;
1999 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2000 *SLLBlock
= tmpSLLBlock
;
2003 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
2005 pSLL
->next
= pPrevSLL
->next
;
2006 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
2007 pPrevSLL
->next
= pSLL
;
2009 pSLL
->scanline
= scanline
;
2012 * now insert the edge in the right bucket
2014 prev
= (EdgeTableEntry
*)NULL
;
2015 start
= pSLL
->edgelist
;
2016 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
2019 start
= start
->next
;
2026 pSLL
->edgelist
= ETE
;
2029 /***********************************************************************
2030 * REGION_CreateEdgeTable
2032 * This routine creates the edge table for
2033 * scan converting polygons.
2034 * The Edge Table (ET) looks like:
2038 * | ymax | ScanLineLists
2039 * |scanline|-->------------>-------------->...
2040 * -------- |scanline| |scanline|
2041 * |edgelist| |edgelist|
2042 * --------- ---------
2046 * list of ETEs list of ETEs
2048 * where ETE is an EdgeTableEntry data structure,
2049 * and there is one ScanLineList per scanline at
2050 * which an edge is initially entered.
2053 static void REGION_CreateETandAET(const INT
*Count
, INT nbpolygons
,
2054 const POINT
*pts
, EdgeTable
*ET
, EdgeTableEntry
*AET
,
2055 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2057 const POINT
*top
, *bottom
;
2058 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2065 * initialize the Active Edge Table
2067 AET
->next
= (EdgeTableEntry
*)NULL
;
2068 AET
->back
= (EdgeTableEntry
*)NULL
;
2069 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2070 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
2073 * initialize the Edge Table.
2075 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
2076 ET
->ymax
= SMALL_COORDINATE
;
2077 ET
->ymin
= LARGE_COORDINATE
;
2078 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2081 for(poly
= 0; poly
< nbpolygons
; poly
++)
2083 count
= Count
[poly
];
2091 * for each vertex in the array of points.
2092 * In this loop we are dealing with two vertices at
2093 * a time -- these make up one edge of the polygon.
2100 * find out which point is above and which is below.
2102 if (PrevPt
->y
> CurrPt
->y
)
2104 bottom
= PrevPt
, top
= CurrPt
;
2105 pETEs
->ClockWise
= 0;
2109 bottom
= CurrPt
, top
= PrevPt
;
2110 pETEs
->ClockWise
= 1;
2114 * don't add horizontal edges to the Edge table.
2116 if (bottom
->y
!= top
->y
)
2118 pETEs
->ymax
= bottom
->y
-1;
2119 /* -1 so we don't get last scanline */
2122 * initialize integer edge algorithm
2124 dy
= bottom
->y
- top
->y
;
2125 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
2127 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2130 if (PrevPt
->y
> ET
->ymax
)
2131 ET
->ymax
= PrevPt
->y
;
2132 if (PrevPt
->y
< ET
->ymin
)
2133 ET
->ymin
= PrevPt
->y
;
2142 /***********************************************************************
2145 * This routine moves EdgeTableEntries from the
2146 * EdgeTable into the Active Edge Table,
2147 * leaving them sorted by smaller x coordinate.
2150 static void REGION_loadAET(EdgeTableEntry
*AET
, EdgeTableEntry
*ETEs
)
2152 EdgeTableEntry
*pPrevAET
;
2153 EdgeTableEntry
*tmp
;
2159 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
2168 ETEs
->back
= pPrevAET
;
2169 pPrevAET
->next
= ETEs
;
2176 /***********************************************************************
2177 * REGION_computeWAET
2179 * This routine links the AET by the
2180 * nextWETE (winding EdgeTableEntry) link for
2181 * use by the winding number rule. The final
2182 * Active Edge Table (AET) might look something
2186 * ---------- --------- ---------
2187 * |ymax | |ymax | |ymax |
2188 * | ... | |... | |... |
2189 * |next |->|next |->|next |->...
2190 * |nextWETE| |nextWETE| |nextWETE|
2191 * --------- --------- ^--------
2193 * V-------------------> V---> ...
2196 static void REGION_computeWAET(EdgeTableEntry
*AET
)
2198 register EdgeTableEntry
*pWETE
;
2199 register int inside
= 1;
2200 register int isInside
= 0;
2202 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2212 if ((!inside
&& !isInside
) ||
2213 ( inside
&& isInside
))
2215 pWETE
->nextWETE
= AET
;
2221 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
2224 /***********************************************************************
2225 * REGION_InsertionSort
2227 * Just a simple insertion sort using
2228 * pointers and back pointers to sort the Active
2232 static BOOL
REGION_InsertionSort(EdgeTableEntry
*AET
)
2234 EdgeTableEntry
*pETEchase
;
2235 EdgeTableEntry
*pETEinsert
;
2236 EdgeTableEntry
*pETEchaseBackTMP
;
2237 BOOL changed
= FALSE
;
2244 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
2245 pETEchase
= pETEchase
->back
;
2248 if (pETEchase
!= pETEinsert
)
2250 pETEchaseBackTMP
= pETEchase
->back
;
2251 pETEinsert
->back
->next
= AET
;
2253 AET
->back
= pETEinsert
->back
;
2254 pETEinsert
->next
= pETEchase
;
2255 pETEchase
->back
->next
= pETEinsert
;
2256 pETEchase
->back
= pETEinsert
;
2257 pETEinsert
->back
= pETEchaseBackTMP
;
2264 /***********************************************************************
2265 * REGION_FreeStorage
2269 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2271 ScanLineListBlock
*tmpSLLBlock
;
2275 tmpSLLBlock
= pSLLBlock
->next
;
2276 HeapFree( SystemHeap
, 0, pSLLBlock
);
2277 pSLLBlock
= tmpSLLBlock
;
2282 /***********************************************************************
2283 * REGION_PtsToRegion
2285 * Create an array of rectangles from a list of points.
2287 static int REGION_PtsToRegion(int numFullPtBlocks
, int iCurPtBlock
,
2288 POINTBLOCK
*FirstPtBlock
, WINEREGION
*reg
)
2292 POINTBLOCK
*CurPtBlock
;
2297 extents
= ®
->extents
;
2299 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
2301 if (!(reg
->rects
= HeapReAlloc( SystemHeap
, 0, reg
->rects
,
2302 sizeof(RECT
) * numRects
)))
2305 reg
->size
= numRects
;
2306 CurPtBlock
= FirstPtBlock
;
2307 rects
= reg
->rects
- 1;
2309 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2311 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--) {
2312 /* the loop uses 2 points per iteration */
2313 i
= NUMPTSTOBUFFER
>> 1;
2314 if (!numFullPtBlocks
)
2315 i
= iCurPtBlock
>> 1;
2316 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2) {
2317 if (pts
->x
== pts
[1].x
)
2319 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2320 pts
[1].x
== rects
->right
&&
2321 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2322 (i
&& pts
[2].y
> pts
[1].y
)) {
2323 rects
->bottom
= pts
[1].y
+ 1;
2328 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2329 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2330 if (rects
->left
< extents
->left
)
2331 extents
->left
= rects
->left
;
2332 if (rects
->right
> extents
->right
)
2333 extents
->right
= rects
->right
;
2335 CurPtBlock
= CurPtBlock
->next
;
2339 extents
->top
= reg
->rects
->top
;
2340 extents
->bottom
= rects
->bottom
;
2345 extents
->bottom
= 0;
2347 reg
->numRects
= numRects
;
2352 /***********************************************************************
2353 * CreatePolyPolygonRgn32 (GDI32.57)
2355 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2356 INT nbpolygons
, INT mode
)
2361 register EdgeTableEntry
*pAET
; /* Active Edge Table */
2362 register INT y
; /* current scanline */
2363 register int iPts
= 0; /* number of pts in buffer */
2364 register EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
2365 register ScanLineList
*pSLL
; /* current scanLineList */
2366 register POINT
*pts
; /* output buffer */
2367 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
2368 EdgeTable ET
; /* header node for ET */
2369 EdgeTableEntry AET
; /* header node for AET */
2370 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2371 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2372 int fixWAET
= FALSE
;
2373 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
2374 POINTBLOCK
*tmpPtBlock
;
2375 int numFullPtBlocks
= 0;
2378 if(!(hrgn
= REGION_CreateRegion(nbpolygons
)))
2380 obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
2383 /* special case a rectangle */
2385 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2386 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2387 (((Pts
[0].y
== Pts
[1].y
) &&
2388 (Pts
[1].x
== Pts
[2].x
) &&
2389 (Pts
[2].y
== Pts
[3].y
) &&
2390 (Pts
[3].x
== Pts
[0].x
)) ||
2391 ((Pts
[0].x
== Pts
[1].x
) &&
2392 (Pts
[1].y
== Pts
[2].y
) &&
2393 (Pts
[2].x
== Pts
[3].x
) &&
2394 (Pts
[3].y
== Pts
[0].y
))))
2396 SetRectRgn( hrgn
, MIN(Pts
[0].x
, Pts
[2].x
), MIN(Pts
[0].y
, Pts
[2].y
),
2397 MAX(Pts
[0].x
, Pts
[2].x
), MAX(Pts
[0].y
, Pts
[2].y
) );
2398 GDI_HEAP_UNLOCK( hrgn
);
2402 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2403 total
+= Count
[poly
];
2404 if (! (pETEs
= HeapAlloc( SystemHeap
, 0, sizeof(EdgeTableEntry
) * total
)))
2406 REGION_DeleteObject( hrgn
, obj
);
2409 pts
= FirstPtBlock
.pts
;
2410 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
2411 pSLL
= ET
.scanlines
.next
;
2412 curPtBlock
= &FirstPtBlock
;
2414 if (mode
!= WINDING
) {
2418 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2420 * Add a new edge to the active edge table when we
2421 * get to the next edge.
2423 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2424 REGION_loadAET(&AET
, pSLL
->edgelist
);
2431 * for each active edge
2434 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2438 * send out the buffer
2440 if (iPts
== NUMPTSTOBUFFER
) {
2441 tmpPtBlock
= HeapAlloc( SystemHeap
, 0, sizeof(POINTBLOCK
));
2443 WARN("Can't alloc tPB\n");
2446 curPtBlock
->next
= tmpPtBlock
;
2447 curPtBlock
= tmpPtBlock
;
2448 pts
= curPtBlock
->pts
;
2452 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
2454 REGION_InsertionSort(&AET
);
2461 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2463 * Add a new edge to the active edge table when we
2464 * get to the next edge.
2466 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2467 REGION_loadAET(&AET
, pSLL
->edgelist
);
2468 REGION_computeWAET(&AET
);
2476 * for each active edge
2480 * add to the buffer only those edges that
2481 * are in the Winding active edge table.
2483 if (pWETE
== pAET
) {
2484 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2488 * send out the buffer
2490 if (iPts
== NUMPTSTOBUFFER
) {
2491 tmpPtBlock
= HeapAlloc( SystemHeap
, 0,
2492 sizeof(POINTBLOCK
) );
2494 WARN("Can't alloc tPB\n");
2497 curPtBlock
->next
= tmpPtBlock
;
2498 curPtBlock
= tmpPtBlock
;
2499 pts
= curPtBlock
->pts
;
2500 numFullPtBlocks
++; iPts
= 0;
2502 pWETE
= pWETE
->nextWETE
;
2504 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
2508 * recompute the winding active edge table if
2509 * we just resorted or have exited an edge.
2511 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2512 REGION_computeWAET(&AET
);
2517 REGION_FreeStorage(SLLBlock
.next
);
2518 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
2519 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;) {
2520 tmpPtBlock
= curPtBlock
->next
;
2521 HeapFree( SystemHeap
, 0, curPtBlock
);
2522 curPtBlock
= tmpPtBlock
;
2524 HeapFree( SystemHeap
, 0, pETEs
);
2525 GDI_HEAP_UNLOCK( hrgn
);
2530 /***********************************************************************
2531 * CreatePolygonRgn16 (GDI.63)
2533 HRGN16 WINAPI
CreatePolygonRgn16( const POINT16
* points
, INT16 count
,
2536 return CreatePolyPolygonRgn16( points
, &count
, 1, mode
);
2539 /***********************************************************************
2540 * CreatePolyPolygonRgn16 (GDI.451)
2542 HRGN16 WINAPI
CreatePolyPolygonRgn16( const POINT16
*points
,
2543 const INT16
*count
, INT16 nbpolygons
, INT16 mode
)
2550 for (i
= 0; i
< nbpolygons
; i
++)
2552 points32
= HeapAlloc( SystemHeap
, 0, npts
* sizeof(POINT
) );
2553 for (i
= 0; i
< npts
; i
++)
2554 CONV_POINT16TO32( &(points
[i
]), &(points32
[i
]) );
2556 count32
= HeapAlloc( SystemHeap
, 0, nbpolygons
* sizeof(INT
) );
2557 for (i
= 0; i
< nbpolygons
; i
++)
2558 count32
[i
] = count
[i
];
2559 hrgn
= CreatePolyPolygonRgn( points32
, count32
, nbpolygons
, mode
);
2560 HeapFree( SystemHeap
, 0, count32
);
2561 HeapFree( SystemHeap
, 0, points32
);
2565 /***********************************************************************
2566 * CreatePolygonRgn32 (GDI32.58)
2568 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2571 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);
2575 /***********************************************************************
2576 * GetRandomRgn [GDI32.215]
2579 * This function is documented in MSDN online
2581 INT WINAPI
GetRandomRgn(HDC hDC
, HRGN hRgn
, DWORD dwCode
)
2585 case 4: /* == SYSRGN ? */
2587 DC
*dc
= DC_GetDCPtr (hDC
);
2590 CombineRgn (hRgn
, dc
->w
.hVisRgn
, 0, RGN_COPY
);
2592 * On Windows NT/2000,
2593 * the region returned is in screen coordinates.
2595 * the region returned is in window coordinates
2597 vi
.dwOSVersionInfoSize
= sizeof(vi
);
2598 if (GetVersionExA( &vi
) && vi
.dwPlatformId
== VER_PLATFORM_WIN32_NT
)
2599 GetDCOrgEx(hDC
, &org
);
2602 org
.x
-= dc
->w
.DCOrgX
;
2603 org
.y
-= dc
->w
.DCOrgY
;
2604 OffsetRgn (hRgn
, org
.x
, org
.y
);
2609 return GetClipRgn (hDC, hRgn);
2612 WARN("Unknown dwCode %ld\n", dwCode
);
2619 /***********************************************************************
2620 * REGION_CropAndOffsetRegion
2622 static BOOL
REGION_CropAndOffsetRegion(const POINT
* off
, const RECT
*rect
, WINEREGION
*rgnSrc
, WINEREGION
* rgnDst
)
2625 if( !rect
) /* just copy and offset */
2628 if( rgnDst
== rgnSrc
)
2630 if( off
->x
|| off
->y
)
2631 xrect
= rgnDst
->rects
;
2636 xrect
= HeapReAlloc( SystemHeap
, 0, rgnDst
->rects
,
2637 rgnSrc
->size
* sizeof( RECT
));
2642 if( rgnDst
!= rgnSrc
)
2643 memcpy( rgnDst
, rgnSrc
, sizeof( WINEREGION
));
2645 if( off
->x
|| off
->y
)
2647 for( i
= 0; i
< rgnDst
->numRects
; i
++ )
2649 xrect
[i
].left
= rgnSrc
->rects
[i
].left
+ off
->x
;
2650 xrect
[i
].right
= rgnSrc
->rects
[i
].right
+ off
->x
;
2651 xrect
[i
].top
= rgnSrc
->rects
[i
].top
+ off
->y
;
2652 xrect
[i
].bottom
= rgnSrc
->rects
[i
].bottom
+ off
->y
;
2654 OffsetRect( &rgnDst
->extents
, off
->x
, off
->y
);
2657 memcpy( xrect
, rgnSrc
->rects
, rgnDst
->numRects
* sizeof(RECT
));
2658 rgnDst
->rects
= xrect
;
2662 else if( IsRectEmpty(rect
) || !EXTENTCHECK(rect
, &rgnSrc
->extents
) )
2665 if( !rgnDst
->rects
)
2667 rgnDst
->rects
= HeapAlloc(SystemHeap
, 0, RGN_DEFAULT_RECTS
* sizeof( RECT
));
2669 rgnDst
->size
= RGN_DEFAULT_RECTS
;
2674 TRACE("cropped to empty!\n");
2675 EMPTY_REGION(rgnDst
);
2677 else /* region box and clipping rect appear to intersect */
2680 INT i
, j
, clipa
, clipb
;
2681 INT left
= rgnSrc
->extents
.right
+ off
->x
;
2682 INT right
= rgnSrc
->extents
.left
+ off
->x
;
2684 for( clipa
= 0; rgnSrc
->rects
[clipa
].bottom
<= rect
->top
; clipa
++ )
2685 ; /* skip bands above the clipping rectangle */
2687 for( clipb
= clipa
; clipb
< rgnSrc
->numRects
; clipb
++ )
2688 if( rgnSrc
->rects
[clipb
].top
>= rect
->bottom
)
2689 break; /* and below it */
2691 /* clipa - index of the first rect in the first intersecting band
2692 * clipb - index of the last rect in the last intersecting band
2695 if((rgnDst
!= rgnSrc
) && (rgnDst
->size
< (i
= (clipb
- clipa
))))
2697 rgnDst
->rects
= HeapReAlloc( SystemHeap
, 0,
2698 rgnDst
->rects
, i
* sizeof(RECT
));
2699 if( !rgnDst
->rects
) return FALSE
;
2703 if( TRACE_ON(region
) )
2705 REGION_DumpRegion( rgnSrc
);
2706 TRACE("\tclipa = %i, clipb = %i\n", clipa
, clipb
);
2709 for( i
= clipa
, j
= 0; i
< clipb
; i
++ )
2711 /* i - src index, j - dst index, j is always <= i for obvious reasons */
2713 lpr
= rgnSrc
->rects
+ i
;
2714 if( lpr
->left
< rect
->right
&& lpr
->right
> rect
->left
)
2716 rgnDst
->rects
[j
].top
= lpr
->top
+ off
->y
;
2717 rgnDst
->rects
[j
].bottom
= lpr
->bottom
+ off
->y
;
2718 rgnDst
->rects
[j
].left
= ((lpr
->left
> rect
->left
) ? lpr
->left
: rect
->left
) + off
->x
;
2719 rgnDst
->rects
[j
].right
= ((lpr
->right
< rect
->right
) ? lpr
->right
: rect
->right
) + off
->x
;
2721 if( rgnDst
->rects
[j
].left
< left
) left
= rgnDst
->rects
[j
].left
;
2722 if( rgnDst
->rects
[j
].right
> right
) right
= rgnDst
->rects
[j
].right
;
2728 if( j
== 0 ) goto empty
;
2730 rgnDst
->extents
.left
= left
;
2731 rgnDst
->extents
.right
= right
;
2733 left
= rect
->top
+ off
->y
;
2734 right
= rect
->bottom
+ off
->y
;
2736 rgnDst
->numRects
= j
--;
2737 for( i
= 0; i
<= j
; i
++ ) /* fixup top band */
2738 if( rgnDst
->rects
[i
].top
< left
)
2739 rgnDst
->rects
[i
].top
= left
;
2743 for( i
= j
; i
>= 0; i
-- ) /* fixup bottom band */
2744 if( rgnDst
->rects
[i
].bottom
> right
)
2745 rgnDst
->rects
[i
].bottom
= right
;
2749 rgnDst
->extents
.top
= rgnDst
->rects
[0].top
;
2750 rgnDst
->extents
.bottom
= rgnDst
->rects
[j
].bottom
;
2752 rgnDst
->type
= (j
>= 1) ? COMPLEXREGION
: SIMPLEREGION
;
2754 if( TRACE_ON(region
) )
2757 REGION_DumpRegion( rgnDst
);
2764 /***********************************************************************
2768 * hSrc: Region to crop and offset.
2769 * lpRect: Clipping rectangle. Can be NULL (no clipping).
2770 * lpPt: Points to offset the cropped region. Can be NULL (no offset).
2772 * hDst: Region to hold the result (a new region is created if it's 0).
2773 * Allowed to be the same region as hSrc in which case everything
2774 * will be done in place, with no memory reallocations.
2776 * Returns: hDst if success, 0 otherwise.
2778 HRGN
REGION_CropRgn( HRGN hDst
, HRGN hSrc
, const RECT
*lpRect
, const POINT
*lpPt
)
2780 /* Optimization of the following generic code:
2785 h = CreateRectRgn( lpRect->left, lpRect->top, lpRect->right, lpRect->bottom );
2787 h = CreateRectRgn( 0, 0, 0, 0 );
2788 if( hDst == 0 ) hDst = h;
2790 CombineRgn( hDst, hSrc, h, RGN_AND );
2792 CombineRgn( hDst, hSrc, 0, RGN_COPY );
2794 OffsetRgn( hDst, lpPt->x, lpPt->y );
2801 RGNOBJ
*objSrc
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
2810 if (!(objDst
= (RGNOBJ
*) GDI_GetObjPtr( hDst
, REGION_MAGIC
)))
2815 rgnDst
= objDst
->rgn
;
2819 if ((rgnDst
= HeapAlloc(SystemHeap
, 0, sizeof( WINEREGION
))))
2821 rgnDst
->size
= rgnDst
->numRects
= 0;
2822 rgnDst
->rects
= NULL
; /* back end will allocate exact number */
2828 POINT pt
= { 0, 0 };
2830 if( !lpPt
) lpPt
= &pt
;
2833 TRACE("src %p -> dst %p (%i,%i)-(%i,%i) by (%li,%li)\n", objSrc
->rgn
, rgnDst
,
2834 lpRect
->left
, lpRect
->top
, lpRect
->right
, lpRect
->bottom
, lpPt
->x
, lpPt
->y
);
2836 TRACE("src %p -> dst %p by (%li,%li)\n", objSrc
->rgn
, rgnDst
, lpPt
->x
, lpPt
->y
);
2838 if( REGION_CropAndOffsetRegion( lpPt
, lpRect
, objSrc
->rgn
, rgnDst
) == FALSE
)
2840 if( hDst
) /* existing rgn */
2842 GDI_HEAP_UNLOCK(hDst
);
2848 else if( hDst
== 0 )
2850 if(!(hDst
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
)))
2854 HeapFree( SystemHeap
, 0, rgnDst
->rects
);
2855 HeapFree( SystemHeap
, 0, rgnDst
);
2859 objDst
= (RGNOBJ
*) GDI_HEAP_LOCK( hDst
);
2860 objDst
->rgn
= rgnDst
;
2863 GDI_HEAP_UNLOCK(hDst
);
2867 GDI_HEAP_UNLOCK(hSrc
);
2873 /***********************************************************************
2874 * GetMetaRgn (GDI.328)
2876 INT WINAPI
GetMetaRgn( HDC hdc
, HRGN hRgn
)
2884 /***********************************************************************
2885 * SetMetaRgn (GDI.455)
2887 INT WINAPI
SetMetaRgn( HDC hdc
)