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...
92 typedef void (*voidProcp
)();
94 /* Note the parameter order is different from the X11 equivalents */
96 static void REGION_CopyRegion(WINEREGION
*d
, WINEREGION
*s
);
97 static void REGION_IntersectRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
98 static void REGION_UnionRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
99 static void REGION_SubtractRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
100 static void REGION_XorRegion(WINEREGION
*d
, WINEREGION
*s1
, WINEREGION
*s2
);
101 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
);
103 #define RGN_DEFAULT_RECTS 2
105 /***********************************************************************
107 * Outputs the contents of a WINEREGION
109 static void REGION_DumpRegion(WINEREGION
*pReg
)
111 RECT
*pRect
, *pRectEnd
= pReg
->rects
+ pReg
->numRects
;
113 TRACE(region
, "Region %p: %d,%d - %d,%d %d rects\n", pReg
,
114 pReg
->extents
.left
, pReg
->extents
.top
,
115 pReg
->extents
.right
, pReg
->extents
.bottom
, pReg
->numRects
);
116 for(pRect
= pReg
->rects
; pRect
< pRectEnd
; pRect
++)
117 TRACE(region
, "\t%d,%d - %d,%d\n", pRect
->left
, pRect
->top
,
118 pRect
->right
, pRect
->bottom
);
123 /***********************************************************************
124 * REGION_AllocWineRegion
125 * Create a new empty WINEREGION.
127 static WINEREGION
*REGION_AllocWineRegion( INT n
)
131 if ((pReg
= HeapAlloc(SystemHeap
, 0, sizeof( WINEREGION
))))
133 if ((pReg
->rects
= HeapAlloc(SystemHeap
, 0, n
* sizeof( RECT
))))
139 HeapFree(SystemHeap
, 0, pReg
);
145 /***********************************************************************
146 * REGION_CreateRegion
147 * Create a new empty region.
149 static HRGN
REGION_CreateRegion( INT n
)
154 if(!(hrgn
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
)))
156 obj
= (RGNOBJ
*) GDI_HEAP_LOCK( hrgn
);
157 if(!(obj
->rgn
= REGION_AllocWineRegion(n
))) {
158 GDI_FreeObject( hrgn
);
161 GDI_HEAP_UNLOCK( hrgn
);
166 /***********************************************************************
167 * REGION_DestroyWineRegion
169 static void REGION_DestroyWineRegion( WINEREGION
* pReg
)
171 HeapFree( SystemHeap
, 0, pReg
->rects
);
172 HeapFree( SystemHeap
, 0, pReg
);
176 /***********************************************************************
177 * REGION_DeleteObject
179 BOOL
REGION_DeleteObject( HRGN hrgn
, RGNOBJ
* obj
)
181 TRACE(region
, " %04x\n", hrgn
);
183 REGION_DestroyWineRegion( obj
->rgn
);
184 return GDI_FreeObject( hrgn
);
187 /***********************************************************************
188 * OffsetRgn16 (GDI.101)
190 INT16 WINAPI
OffsetRgn16( HRGN16 hrgn
, INT16 x
, INT16 y
)
192 return OffsetRgn( hrgn
, x
, y
);
195 /***********************************************************************
196 * OffsetRgn32 (GDI32.256)
198 INT WINAPI
OffsetRgn( HRGN hrgn
, INT x
, INT y
)
200 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
205 int nbox
= obj
->rgn
->numRects
;
206 RECT
*pbox
= obj
->rgn
->rects
;
208 TRACE(region
, " %04x %d,%d\n", hrgn
, x
, y
);
217 obj
->rgn
->extents
.left
+= x
;
218 obj
->rgn
->extents
.right
+= x
;
219 obj
->rgn
->extents
.top
+= y
;
220 obj
->rgn
->extents
.bottom
+= y
;
222 ret
= obj
->rgn
->type
;
223 GDI_HEAP_UNLOCK( hrgn
);
230 /***********************************************************************
231 * GetRgnBox16 (GDI.134)
233 INT16 WINAPI
GetRgnBox16( HRGN16 hrgn
, LPRECT16 rect
)
236 INT16 ret
= (INT16
)GetRgnBox( hrgn
, &r
);
237 CONV_RECT32TO16( &r
, rect
);
241 /***********************************************************************
242 * GetRgnBox32 (GDI32.219)
244 INT WINAPI
GetRgnBox( HRGN hrgn
, LPRECT rect
)
246 RGNOBJ
* obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
250 TRACE(region
, " %04x\n", hrgn
);
251 rect
->left
= obj
->rgn
->extents
.left
;
252 rect
->top
= obj
->rgn
->extents
.top
;
253 rect
->right
= obj
->rgn
->extents
.right
;
254 rect
->bottom
= obj
->rgn
->extents
.bottom
;
255 ret
= obj
->rgn
->type
;
256 GDI_HEAP_UNLOCK(hrgn
);
263 /***********************************************************************
264 * CreateRectRgn16 (GDI.64)
266 * NOTE: Doesn't call CreateRectRgn32 because of differences in SetRectRgn16/32
268 HRGN16 WINAPI
CreateRectRgn16(INT16 left
, INT16 top
, INT16 right
, INT16 bottom
)
272 if (!(hrgn
= (HRGN16
)REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
275 SetRectRgn16(hrgn
, left
, top
, right
, bottom
);
280 /***********************************************************************
281 * CreateRectRgn32 (GDI32.59)
283 HRGN WINAPI
CreateRectRgn(INT left
, INT top
, INT right
, INT bottom
)
287 /* Allocate 2 rects by default to reduce the number of reallocs */
289 if (!(hrgn
= REGION_CreateRegion(RGN_DEFAULT_RECTS
)))
292 SetRectRgn(hrgn
, left
, top
, right
, bottom
);
296 /***********************************************************************
297 * CreateRectRgnIndirect16 (GDI.65)
299 HRGN16 WINAPI
CreateRectRgnIndirect16( const RECT16
* rect
)
301 return CreateRectRgn16( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
305 /***********************************************************************
306 * CreateRectRgnIndirect32 (GDI32.60)
308 HRGN WINAPI
CreateRectRgnIndirect( const RECT
* rect
)
310 return CreateRectRgn( rect
->left
, rect
->top
, rect
->right
, rect
->bottom
);
314 /***********************************************************************
315 * SetRectRgn16 (GDI.172)
317 * NOTE: Win 3.1 sets region to empty if left > right
319 VOID WINAPI
SetRectRgn16( HRGN16 hrgn
, INT16 left
, INT16 top
,
320 INT16 right
, INT16 bottom
)
323 SetRectRgn( hrgn
, left
, top
, right
, bottom
);
325 SetRectRgn( hrgn
, 0, 0, 0, 0 );
329 /***********************************************************************
330 * SetRectRgn32 (GDI32.332)
332 * Allows either or both left and top to be greater than right or bottom.
334 VOID WINAPI
SetRectRgn( HRGN hrgn
, INT left
, INT top
,
335 INT right
, INT bottom
)
339 TRACE(region
, " %04x %d,%d-%d,%d\n",
340 hrgn
, left
, top
, right
, bottom
);
342 if (!(obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
))) return;
344 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
345 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
347 if((left
!= right
) && (top
!= bottom
))
349 obj
->rgn
->rects
->left
= obj
->rgn
->extents
.left
= left
;
350 obj
->rgn
->rects
->top
= obj
->rgn
->extents
.top
= top
;
351 obj
->rgn
->rects
->right
= obj
->rgn
->extents
.right
= right
;
352 obj
->rgn
->rects
->bottom
= obj
->rgn
->extents
.bottom
= bottom
;
353 obj
->rgn
->numRects
= 1;
354 obj
->rgn
->type
= SIMPLEREGION
;
357 EMPTY_REGION(obj
->rgn
);
359 GDI_HEAP_UNLOCK( hrgn
);
363 /***********************************************************************
364 * CreateRoundRectRgn16 (GDI.444)
366 * If either ellipse dimension is zero we call CreateRectRgn16 for its
367 * `special' behaviour. -ve ellipse dimensions can result in GPFs under win3.1
368 * we just let CreateRoundRectRgn32 convert them to +ve values.
371 HRGN16 WINAPI
CreateRoundRectRgn16( INT16 left
, INT16 top
,
372 INT16 right
, INT16 bottom
,
373 INT16 ellipse_width
, INT16 ellipse_height
)
375 if( ellipse_width
== 0 || ellipse_height
== 0 )
376 return CreateRectRgn16( left
, top
, right
, bottom
);
378 return (HRGN16
)CreateRoundRectRgn( left
, top
, right
, bottom
,
379 ellipse_width
, ellipse_height
);
382 /***********************************************************************
383 * CreateRoundRectRgn32 (GDI32.61)
385 HRGN WINAPI
CreateRoundRectRgn( INT left
, INT top
,
386 INT right
, INT bottom
,
387 INT ellipse_width
, INT ellipse_height
)
391 int asq
, bsq
, d
, xd
, yd
;
394 /* Check if we can do a normal rectangle instead */
396 if ((ellipse_width
== 0) || (ellipse_height
== 0))
397 return CreateRectRgn( left
, top
, right
, bottom
);
399 /* Make the dimensions sensible */
401 if (left
> right
) { INT tmp
= left
; left
= right
; right
= tmp
; }
402 if (top
> bottom
) { INT tmp
= top
; top
= bottom
; bottom
= tmp
; }
404 ellipse_width
= abs(ellipse_width
);
405 ellipse_height
= abs(ellipse_height
);
409 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
410 if (!(hrgn
= REGION_CreateRegion(d
))) return 0;
411 obj
= (RGNOBJ
*) GDI_HEAP_LOCK( hrgn
);
412 TRACE(region
,"(%d,%d-%d,%d %dx%d): ret=%04x\n",
413 left
, top
, right
, bottom
, ellipse_width
, ellipse_height
, hrgn
);
415 /* Check parameters */
417 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
418 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
420 /* Ellipse algorithm, based on an article by K. Porter */
421 /* in DDJ Graphics Programming Column, 8/89 */
423 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
424 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
425 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
427 yd
= asq
* ellipse_height
; /* 2a^2b */
429 rect
.left
= left
+ ellipse_width
/ 2;
430 rect
.right
= right
- ellipse_width
/ 2;
432 /* Loop to draw first half of quadrant */
436 if (d
> 0) /* if nearest pixel is toward the center */
438 /* move toward center */
440 rect
.bottom
= rect
.top
+ 1;
441 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
443 rect
.bottom
= rect
.top
+ 1;
444 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
448 rect
.left
--; /* next horiz point */
454 /* Loop to draw second half of quadrant */
456 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
459 /* next vertical point */
461 rect
.bottom
= rect
.top
+ 1;
462 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
464 rect
.bottom
= rect
.top
+ 1;
465 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
466 if (d
< 0) /* if nearest pixel is outside ellipse */
468 rect
.left
--; /* move away from center */
477 /* Add the inside rectangle */
482 rect
.bottom
= bottom
;
483 REGION_UnionRectWithRegion( &rect
, obj
->rgn
);
485 obj
->rgn
->type
= SIMPLEREGION
; /* FIXME? */
486 GDI_HEAP_UNLOCK( hrgn
);
491 /***********************************************************************
492 * CreateEllipticRgn16 (GDI.54)
494 HRGN16 WINAPI
CreateEllipticRgn16( INT16 left
, INT16 top
,
495 INT16 right
, INT16 bottom
)
497 return (HRGN16
)CreateRoundRectRgn( left
, top
, right
, bottom
,
498 right
-left
, bottom
-top
);
502 /***********************************************************************
503 * CreateEllipticRgn32 (GDI32.39)
505 HRGN WINAPI
CreateEllipticRgn( INT left
, INT top
,
506 INT right
, INT bottom
)
508 return CreateRoundRectRgn( left
, top
, right
, bottom
,
509 right
-left
, bottom
-top
);
513 /***********************************************************************
514 * CreateEllipticRgnIndirect16 (GDI.55)
516 HRGN16 WINAPI
CreateEllipticRgnIndirect16( const RECT16
*rect
)
518 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
519 rect
->bottom
, rect
->right
- rect
->left
,
520 rect
->bottom
- rect
->top
);
524 /***********************************************************************
525 * CreateEllipticRgnIndirect32 (GDI32.40)
527 HRGN WINAPI
CreateEllipticRgnIndirect( const RECT
*rect
)
529 return CreateRoundRectRgn( rect
->left
, rect
->top
, rect
->right
,
530 rect
->bottom
, rect
->right
- rect
->left
,
531 rect
->bottom
- rect
->top
);
534 /***********************************************************************
535 * GetRegionData32 (GDI32.217)
538 DWORD WINAPI
GetRegionData(HRGN hrgn
, DWORD count
, LPRGNDATA rgndata
)
541 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
543 TRACE(region
, " %04x count = %ld, rgndata = %p\n",
544 hrgn
, count
, rgndata
);
548 size
= obj
->rgn
->numRects
* sizeof(RECT
);
549 if(count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
551 GDI_HEAP_UNLOCK( hrgn
);
552 return size
+ sizeof(RGNDATAHEADER
);
555 rgndata
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
556 rgndata
->rdh
.iType
= RDH_RECTANGLES
;
557 rgndata
->rdh
.nCount
= obj
->rgn
->numRects
;
558 rgndata
->rdh
.nRgnSize
= size
;
559 rgndata
->rdh
.rcBound
.left
= obj
->rgn
->extents
.left
;
560 rgndata
->rdh
.rcBound
.top
= obj
->rgn
->extents
.top
;
561 rgndata
->rdh
.rcBound
.right
= obj
->rgn
->extents
.right
;
562 rgndata
->rdh
.rcBound
.bottom
= obj
->rgn
->extents
.bottom
;
564 memcpy( rgndata
->Buffer
, obj
->rgn
->rects
, size
);
566 GDI_HEAP_UNLOCK( hrgn
);
570 /***********************************************************************
571 * GetRegionData16 (GDI.607)
572 * FIXME: is LPRGNDATA the same in Win16 and Win32 ?
574 DWORD WINAPI
GetRegionData16(HRGN16 hrgn
, DWORD count
, LPRGNDATA rgndata
)
576 return GetRegionData((HRGN
)hrgn
, count
, rgndata
);
579 /***********************************************************************
580 * ExtCreateRegion (GDI32.94)
583 HRGN WINAPI
ExtCreateRegion( const XFORM
* lpXform
, DWORD dwCount
, const RGNDATA
* rgndata
)
587 TRACE(region
, " %p %ld %p = ", lpXform
, dwCount
, rgndata
);
590 WARN(region
, "(Xform not implemented - ignored) ");
592 if( rgndata
->rdh
.iType
!= RDH_RECTANGLES
)
594 /* FIXME: We can use CreatePolyPolygonRgn() here
595 * for trapezoidal data */
597 WARN(region
, "(Unsupported region data) ");
601 if( (hrgn
= REGION_CreateRegion( rgndata
->rdh
.nCount
)) )
603 RECT
*pCurRect
, *pEndRect
;
604 RGNOBJ
*obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
606 pEndRect
= (RECT
*)rgndata
->Buffer
+ rgndata
->rdh
.nCount
;
607 for(pCurRect
= (RECT
*)rgndata
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
608 REGION_UnionRectWithRegion( pCurRect
, obj
->rgn
);
609 GDI_HEAP_UNLOCK( hrgn
);
611 TRACE(region
,"%04x\n", hrgn
);
615 WARN(region
, "Failed\n");
619 /***********************************************************************
620 * PtInRegion16 (GDI.161)
622 BOOL16 WINAPI
PtInRegion16( HRGN16 hrgn
, INT16 x
, INT16 y
)
624 return PtInRegion( hrgn
, x
, y
);
628 /***********************************************************************
629 * PtInRegion32 (GDI32.278)
631 BOOL WINAPI
PtInRegion( HRGN hrgn
, INT x
, INT y
)
635 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
640 if (obj
->rgn
->numRects
> 0 && INRECT(obj
->rgn
->extents
, x
, y
))
641 for (i
= 0; i
< obj
->rgn
->numRects
; i
++)
642 if (INRECT (obj
->rgn
->rects
[i
], x
, y
))
644 GDI_HEAP_UNLOCK( hrgn
);
651 /***********************************************************************
652 * RectInRegion16 (GDI.181)
654 BOOL16 WINAPI
RectInRegion16( HRGN16 hrgn
, const RECT16
*rect
)
658 CONV_RECT16TO32(rect
, &r32
);
659 return (BOOL16
)RectInRegion(hrgn
, &r32
);
663 /***********************************************************************
664 * RectInRegion32 (GDI32.281)
666 * Returns TRUE if rect is at least partly inside hrgn
668 BOOL WINAPI
RectInRegion( HRGN hrgn
, const RECT
*rect
)
672 if ((obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
)))
674 RECT
*pCurRect
, *pRectEnd
;
677 /* this is (just) a useful optimization */
678 if ((obj
->rgn
->numRects
> 0) && EXTENTCHECK(&obj
->rgn
->extents
,
681 for (pCurRect
= obj
->rgn
->rects
, pRectEnd
= pCurRect
+
682 obj
->rgn
->numRects
; pCurRect
< pRectEnd
; pCurRect
++)
684 if (pCurRect
->bottom
<= rect
->top
)
685 continue; /* not far enough down yet */
687 if (pCurRect
->top
>= rect
->bottom
) {
688 ret
= FALSE
; /* too far down */
692 if (pCurRect
->right
<= rect
->left
)
693 continue; /* not far enough over yet */
695 if (pCurRect
->left
>= rect
->right
) {
703 GDI_HEAP_UNLOCK(hrgn
);
709 /***********************************************************************
710 * EqualRgn16 (GDI.72)
712 BOOL16 WINAPI
EqualRgn16( HRGN16 rgn1
, HRGN16 rgn2
)
714 return EqualRgn( rgn1
, rgn2
);
718 /***********************************************************************
719 * EqualRgn32 (GDI32.90)
721 BOOL WINAPI
EqualRgn( HRGN hrgn1
, HRGN hrgn2
)
726 if ((obj1
= (RGNOBJ
*) GDI_GetObjPtr( hrgn1
, REGION_MAGIC
)))
728 if ((obj2
= (RGNOBJ
*) GDI_GetObjPtr( hrgn2
, REGION_MAGIC
)))
733 if ( obj1
->rgn
->numRects
!= obj2
->rgn
->numRects
) ret
= FALSE
;
734 else if ( obj1
->rgn
->numRects
== 0 ) ret
= TRUE
;
735 else if ( !EqualRect(&obj1
->rgn
->extents
, &obj2
->rgn
->extents
) )
737 else for( i
= 0; i
< obj1
->rgn
->numRects
; i
++ ) {
738 if (!EqualRect(obj1
->rgn
->rects
+ i
, obj2
->rgn
->rects
+ i
)) {
743 GDI_HEAP_UNLOCK(hrgn2
);
745 GDI_HEAP_UNLOCK(hrgn1
);
749 /***********************************************************************
750 * REGION_UnionRectWithRegion
751 * Adds a rectangle to a WINEREGION
752 * See below for REGION_UnionRectWithRgn
754 static void REGION_UnionRectWithRegion(const RECT
*rect
, WINEREGION
*rgn
)
758 region
.rects
= ®ion
.extents
;
761 region
.type
= SIMPLEREGION
;
762 CopyRect(&(region
.extents
), rect
);
763 REGION_UnionRegion(rgn
, rgn
, ®ion
);
767 /***********************************************************************
768 * REGION_UnionRectWithRgn
769 * Adds a rectangle to a HRGN32
770 * A helper used by scroll.c
772 BOOL
REGION_UnionRectWithRgn( HRGN hrgn
, const RECT
*lpRect
)
774 RGNOBJ
*obj
= (RGNOBJ
*) GDI_HEAP_LOCK( hrgn
);
776 if(!obj
) return FALSE
;
777 REGION_UnionRectWithRegion( lpRect
, obj
->rgn
);
778 GDI_HEAP_UNLOCK(hrgn
);
782 /***********************************************************************
783 * REGION_CreateFrameRgn
785 * Create a region that is a frame around another region.
786 * Expand all rectangles by +/- x and y, then subtract original region.
788 BOOL
REGION_FrameRgn( HRGN hDest
, HRGN hSrc
, INT x
, INT y
)
791 RGNOBJ
*srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
);
793 if (srcObj
->rgn
->numRects
!= 0)
795 RGNOBJ
* destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
796 RECT
*pRect
, *pEndRect
;
799 EMPTY_REGION( destObj
->rgn
);
801 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
802 for(pRect
= srcObj
->rgn
->rects
; pRect
< pEndRect
; pRect
++)
804 tempRect
.left
= pRect
->left
- x
;
805 tempRect
.top
= pRect
->top
- y
;
806 tempRect
.right
= pRect
->right
+ x
;
807 tempRect
.bottom
= pRect
->bottom
+ y
;
808 REGION_UnionRectWithRegion( &tempRect
, destObj
->rgn
);
810 REGION_SubtractRegion( destObj
->rgn
, destObj
->rgn
, srcObj
->rgn
);
811 GDI_HEAP_UNLOCK ( hDest
);
816 GDI_HEAP_UNLOCK( hSrc
);
820 /***********************************************************************
823 * Convert region to device co-ords for the supplied dc.
824 * Used by X11DRV_PaintRgn.
826 BOOL
REGION_LPTODP( HDC hdc
, HRGN hDest
, HRGN hSrc
)
828 RECT
*pCurRect
, *pEndRect
;
829 RGNOBJ
*srcObj
, *destObj
;
830 DC
* dc
= DC_GetDCPtr( hdc
);
833 TRACE(region
, " hdc=%04x dest=%04x src=%04x\n",
836 if (dc
->w
.MapMode
== MM_TEXT
) /* Requires only a translation */
838 if( CombineRgn( hDest
, hSrc
, 0, RGN_COPY
) == ERROR
) return FALSE
;
839 OffsetRgn( hDest
, dc
->vportOrgX
- dc
->wndOrgX
,
840 dc
->vportOrgY
- dc
->wndOrgY
);
844 if(!( srcObj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc
, REGION_MAGIC
) ))
846 if(!( destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
) ))
848 GDI_HEAP_UNLOCK( hSrc
);
851 EMPTY_REGION( destObj
->rgn
);
853 pEndRect
= srcObj
->rgn
->rects
+ srcObj
->rgn
->numRects
;
854 for(pCurRect
= srcObj
->rgn
->rects
; pCurRect
< pEndRect
; pCurRect
++)
857 tmpRect
.left
= XLPTODP( dc
, tmpRect
.left
);
858 tmpRect
.top
= YLPTODP( dc
, tmpRect
.top
);
859 tmpRect
.right
= XLPTODP( dc
, tmpRect
.right
);
860 tmpRect
.bottom
= YLPTODP( dc
, tmpRect
.bottom
);
861 REGION_UnionRectWithRegion( &tmpRect
, destObj
->rgn
);
864 GDI_HEAP_UNLOCK( hDest
);
865 GDI_HEAP_UNLOCK( hSrc
);
869 /***********************************************************************
870 * CombineRgn16 (GDI.451)
872 INT16 WINAPI
CombineRgn16(HRGN16 hDest
, HRGN16 hSrc1
, HRGN16 hSrc2
, INT16 mode
)
874 return (INT16
)CombineRgn( hDest
, hSrc1
, hSrc2
, mode
);
878 /***********************************************************************
879 * CombineRgn32 (GDI32.19)
881 * Note: The behavior is correct even if src and dest regions are the same.
883 INT WINAPI
CombineRgn(HRGN hDest
, HRGN hSrc1
, HRGN hSrc2
, INT mode
)
885 RGNOBJ
*destObj
= (RGNOBJ
*) GDI_GetObjPtr( hDest
, REGION_MAGIC
);
888 TRACE(region
, " %04x,%04x -> %04x mode=%x\n",
889 hSrc1
, hSrc2
, hDest
, mode
);
892 RGNOBJ
*src1Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc1
, REGION_MAGIC
);
896 TRACE(region
, "dump:\n");
898 REGION_DumpRegion(src1Obj
->rgn
);
899 if (mode
== RGN_COPY
)
901 REGION_CopyRegion( destObj
->rgn
, src1Obj
->rgn
);
902 result
= destObj
->rgn
->type
;
906 RGNOBJ
*src2Obj
= (RGNOBJ
*) GDI_GetObjPtr( hSrc2
, REGION_MAGIC
);
910 TRACE(region
, "dump:\n");
912 REGION_DumpRegion(src2Obj
->rgn
);
916 REGION_IntersectRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
919 REGION_UnionRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
922 REGION_XorRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
925 REGION_SubtractRegion( destObj
->rgn
, src1Obj
->rgn
, src2Obj
->rgn
);
928 result
= destObj
->rgn
->type
;
929 GDI_HEAP_UNLOCK( hSrc2
);
932 GDI_HEAP_UNLOCK( hSrc1
);
934 TRACE(region
, "dump:\n");
936 REGION_DumpRegion(destObj
->rgn
);
938 GDI_HEAP_UNLOCK( hDest
);
943 /***********************************************************************
945 * Re-calculate the extents of a region
947 static void REGION_SetExtents (WINEREGION
*pReg
)
949 RECT
*pRect
, *pRectEnd
, *pExtents
;
951 if (pReg
->numRects
== 0)
953 pReg
->extents
.left
= 0;
954 pReg
->extents
.top
= 0;
955 pReg
->extents
.right
= 0;
956 pReg
->extents
.bottom
= 0;
960 pExtents
= &pReg
->extents
;
962 pRectEnd
= &pRect
[pReg
->numRects
- 1];
965 * Since pRect is the first rectangle in the region, it must have the
966 * smallest top and since pRectEnd is the last rectangle in the region,
967 * it must have the largest bottom, because of banding. Initialize left and
968 * right from pRect and pRectEnd, resp., as good things to initialize them
971 pExtents
->left
= pRect
->left
;
972 pExtents
->top
= pRect
->top
;
973 pExtents
->right
= pRectEnd
->right
;
974 pExtents
->bottom
= pRectEnd
->bottom
;
976 while (pRect
<= pRectEnd
)
978 if (pRect
->left
< pExtents
->left
)
979 pExtents
->left
= pRect
->left
;
980 if (pRect
->right
> pExtents
->right
)
981 pExtents
->right
= pRect
->right
;
986 /***********************************************************************
989 static void REGION_CopyRegion(WINEREGION
*dst
, WINEREGION
*src
)
991 if (dst
!= src
) /* don't want to copy to itself */
993 if (dst
->size
< src
->numRects
)
995 if (! (dst
->rects
= HeapReAlloc( SystemHeap
, 0, dst
->rects
,
996 src
->numRects
* sizeof(RECT
) )))
998 dst
->size
= src
->numRects
;
1000 dst
->numRects
= src
->numRects
;
1001 dst
->extents
.left
= src
->extents
.left
;
1002 dst
->extents
.top
= src
->extents
.top
;
1003 dst
->extents
.right
= src
->extents
.right
;
1004 dst
->extents
.bottom
= src
->extents
.bottom
;
1005 dst
->type
= src
->type
;
1007 memcpy((char *) dst
->rects
, (char *) src
->rects
,
1008 (int) (src
->numRects
* sizeof(RECT
)));
1013 /***********************************************************************
1016 * Attempt to merge the rects in the current band with those in the
1017 * previous one. Used only by REGION_RegionOp.
1020 * The new index for the previous band.
1023 * If coalescing takes place:
1024 * - rectangles in the previous band will have their bottom fields
1026 * - pReg->numRects will be decreased.
1029 static INT
REGION_Coalesce (
1030 WINEREGION
*pReg
, /* Region to coalesce */
1031 INT prevStart
, /* Index of start of previous band */
1032 INT curStart
/* Index of start of current band */
1034 RECT
*pPrevRect
; /* Current rect in previous band */
1035 RECT
*pCurRect
; /* Current rect in current band */
1036 RECT
*pRegEnd
; /* End of region */
1037 INT curNumRects
; /* Number of rectangles in current band */
1038 INT prevNumRects
; /* Number of rectangles in previous band */
1039 INT bandtop
; /* top coordinate for current band */
1041 pRegEnd
= &pReg
->rects
[pReg
->numRects
];
1043 pPrevRect
= &pReg
->rects
[prevStart
];
1044 prevNumRects
= curStart
- prevStart
;
1047 * Figure out how many rectangles are in the current band. Have to do
1048 * this because multiple bands could have been added in REGION_RegionOp
1049 * at the end when one region has been exhausted.
1051 pCurRect
= &pReg
->rects
[curStart
];
1052 bandtop
= pCurRect
->top
;
1053 for (curNumRects
= 0;
1054 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
1060 if (pCurRect
!= pRegEnd
)
1063 * If more than one band was added, we have to find the start
1064 * of the last band added so the next coalescing job can start
1065 * at the right place... (given when multiple bands are added,
1066 * this may be pointless -- see above).
1069 while (pRegEnd
[-1].top
== pRegEnd
->top
)
1073 curStart
= pRegEnd
- pReg
->rects
;
1074 pRegEnd
= pReg
->rects
+ pReg
->numRects
;
1077 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0)) {
1078 pCurRect
-= curNumRects
;
1080 * The bands may only be coalesced if the bottom of the previous
1081 * matches the top scanline of the current.
1083 if (pPrevRect
->bottom
== pCurRect
->top
)
1086 * Make sure the bands have rects in the same places. This
1087 * assumes that rects have been added in such a way that they
1088 * cover the most area possible. I.e. two rects in a band must
1089 * have some horizontal space between them.
1093 if ((pPrevRect
->left
!= pCurRect
->left
) ||
1094 (pPrevRect
->right
!= pCurRect
->right
))
1097 * The bands don't line up so they can't be coalesced.
1104 } while (prevNumRects
!= 0);
1106 pReg
->numRects
-= curNumRects
;
1107 pCurRect
-= curNumRects
;
1108 pPrevRect
-= curNumRects
;
1111 * The bands may be merged, so set the bottom of each rect
1112 * in the previous band to that of the corresponding rect in
1117 pPrevRect
->bottom
= pCurRect
->bottom
;
1121 } while (curNumRects
!= 0);
1124 * If only one band was added to the region, we have to backup
1125 * curStart to the start of the previous band.
1127 * If more than one band was added to the region, copy the
1128 * other bands down. The assumption here is that the other bands
1129 * came from the same region as the current one and no further
1130 * coalescing can be done on them since it's all been done
1131 * already... curStart is already in the right place.
1133 if (pCurRect
== pRegEnd
)
1135 curStart
= prevStart
;
1141 *pPrevRect
++ = *pCurRect
++;
1142 } while (pCurRect
!= pRegEnd
);
1150 /***********************************************************************
1153 * Apply an operation to two regions. Called by REGION_Union,
1154 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1160 * The new region is overwritten.
1163 * The idea behind this function is to view the two regions as sets.
1164 * Together they cover a rectangle of area that this function divides
1165 * into horizontal bands where points are covered only by one region
1166 * or by both. For the first case, the nonOverlapFunc is called with
1167 * each the band and the band's upper and lower extents. For the
1168 * second, the overlapFunc is called to process the entire band. It
1169 * is responsible for clipping the rectangles in the band, though
1170 * this function provides the boundaries.
1171 * At the end of each band, the new region is coalesced, if possible,
1172 * to reduce the number of rectangles in the region.
1175 static void REGION_RegionOp(
1176 WINEREGION
*newReg
, /* Place to store result */
1177 WINEREGION
*reg1
, /* First region in operation */
1178 WINEREGION
*reg2
, /* 2nd region in operation */
1179 void (*overlapFunc
)(), /* Function to call for over-lapping bands */
1180 void (*nonOverlap1Func
)(), /* Function to call for non-overlapping bands in region 1 */
1181 void (*nonOverlap2Func
)() /* Function to call for non-overlapping bands in region 2 */
1183 RECT
*r1
; /* Pointer into first region */
1184 RECT
*r2
; /* Pointer into 2d region */
1185 RECT
*r1End
; /* End of 1st region */
1186 RECT
*r2End
; /* End of 2d region */
1187 INT ybot
; /* Bottom of intersection */
1188 INT ytop
; /* Top of intersection */
1189 RECT
*oldRects
; /* Old rects for newReg */
1190 INT prevBand
; /* Index of start of
1191 * previous band in newReg */
1192 INT curBand
; /* Index of start of current
1194 RECT
*r1BandEnd
; /* End of current band in r1 */
1195 RECT
*r2BandEnd
; /* End of current band in r2 */
1196 INT top
; /* Top of non-overlapping band */
1197 INT bot
; /* Bottom of non-overlapping band */
1201 * set r1, r2, r1End and r2End appropriately, preserve the important
1202 * parts of the destination region until the end in case it's one of
1203 * the two source regions, then mark the "new" region empty, allocating
1204 * another array of rectangles for it to use.
1208 r1End
= r1
+ reg1
->numRects
;
1209 r2End
= r2
+ reg2
->numRects
;
1213 * newReg may be one of the src regions so we can't empty it. We keep a
1214 * note of its rects pointer (so that we can free them later), preserve its
1215 * extents and simply set numRects to zero.
1218 oldRects
= newReg
->rects
;
1219 newReg
->numRects
= 0;
1222 * Allocate a reasonable number of rectangles for the new region. The idea
1223 * is to allocate enough so the individual functions don't need to
1224 * reallocate and copy the array, which is time consuming, yet we don't
1225 * have to worry about using too much memory. I hope to be able to
1226 * nuke the Xrealloc() at the end of this function eventually.
1228 newReg
->size
= MAX(reg1
->numRects
,reg2
->numRects
) * 2;
1230 if (! (newReg
->rects
= HeapAlloc( SystemHeap
, 0,
1231 sizeof(RECT
) * newReg
->size
)))
1238 * Initialize ybot and ytop.
1239 * In the upcoming loop, ybot and ytop serve different functions depending
1240 * on whether the band being handled is an overlapping or non-overlapping
1242 * In the case of a non-overlapping band (only one of the regions
1243 * has points in the band), ybot is the bottom of the most recent
1244 * intersection and thus clips the top of the rectangles in that band.
1245 * ytop is the top of the next intersection between the two regions and
1246 * serves to clip the bottom of the rectangles in the current band.
1247 * For an overlapping band (where the two regions intersect), ytop clips
1248 * the top of the rectangles of both regions and ybot clips the bottoms.
1250 if (reg1
->extents
.top
< reg2
->extents
.top
)
1251 ybot
= reg1
->extents
.top
;
1253 ybot
= reg2
->extents
.top
;
1256 * prevBand serves to mark the start of the previous band so rectangles
1257 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1258 * In the beginning, there is no previous band, so prevBand == curBand
1259 * (curBand is set later on, of course, but the first band will always
1260 * start at index 0). prevBand and curBand must be indices because of
1261 * the possible expansion, and resultant moving, of the new region's
1262 * array of rectangles.
1268 curBand
= newReg
->numRects
;
1271 * This algorithm proceeds one source-band (as opposed to a
1272 * destination band, which is determined by where the two regions
1273 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1274 * rectangle after the last one in the current band for their
1275 * respective regions.
1278 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1284 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1290 * First handle the band that doesn't intersect, if any.
1292 * Note that attention is restricted to one band in the
1293 * non-intersecting region at once, so if a region has n
1294 * bands between the current position and the next place it overlaps
1295 * the other, this entire loop will be passed through n times.
1297 if (r1
->top
< r2
->top
)
1299 top
= MAX(r1
->top
,ybot
);
1300 bot
= MIN(r1
->bottom
,r2
->top
);
1302 if ((top
!= bot
) && (nonOverlap1Func
!= (void (*)())NULL
))
1304 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1309 else if (r2
->top
< r1
->top
)
1311 top
= MAX(r2
->top
,ybot
);
1312 bot
= MIN(r2
->bottom
,r1
->top
);
1314 if ((top
!= bot
) && (nonOverlap2Func
!= (void (*)())NULL
))
1316 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1327 * If any rectangles got added to the region, try and coalesce them
1328 * with rectangles from the previous band. Note we could just do
1329 * this test in miCoalesce, but some machines incur a not
1330 * inconsiderable cost for function calls, so...
1332 if (newReg
->numRects
!= curBand
)
1334 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1338 * Now see if we've hit an intersecting band. The two bands only
1339 * intersect if ybot > ytop
1341 ybot
= MIN(r1
->bottom
, r2
->bottom
);
1342 curBand
= newReg
->numRects
;
1345 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1349 if (newReg
->numRects
!= curBand
)
1351 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1355 * If we've finished with a band (bottom == ybot) we skip forward
1356 * in the region to the next band.
1358 if (r1
->bottom
== ybot
)
1362 if (r2
->bottom
== ybot
)
1366 } while ((r1
!= r1End
) && (r2
!= r2End
));
1369 * Deal with whichever region still has rectangles left.
1371 curBand
= newReg
->numRects
;
1374 if (nonOverlap1Func
!= (void (*)())NULL
)
1379 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1383 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1384 MAX(r1
->top
,ybot
), r1
->bottom
);
1386 } while (r1
!= r1End
);
1389 else if ((r2
!= r2End
) && (nonOverlap2Func
!= (void (*)())NULL
))
1394 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1398 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1399 MAX(r2
->top
,ybot
), r2
->bottom
);
1401 } while (r2
!= r2End
);
1404 if (newReg
->numRects
!= curBand
)
1406 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1410 * A bit of cleanup. To keep regions from growing without bound,
1411 * we shrink the array of rectangles to match the new number of
1412 * rectangles in the region. This never goes to 0, however...
1414 * Only do this stuff if the number of rectangles allocated is more than
1415 * twice the number of rectangles in the region (a simple optimization...).
1417 if ((newReg
->numRects
< (newReg
->size
>> 1)) && (newReg
->numRects
> 2))
1419 if (REGION_NOT_EMPTY(newReg
))
1421 RECT
*prev_rects
= newReg
->rects
;
1422 newReg
->size
= newReg
->numRects
;
1423 newReg
->rects
= HeapReAlloc( SystemHeap
, 0, newReg
->rects
,
1424 sizeof(RECT
) * newReg
->size
);
1425 if (! newReg
->rects
)
1426 newReg
->rects
= prev_rects
;
1431 * No point in doing the extra work involved in an Xrealloc if
1432 * the region is empty
1435 HeapFree( SystemHeap
, 0, newReg
->rects
);
1436 newReg
->rects
= HeapAlloc( SystemHeap
, 0, sizeof(RECT
) );
1439 HeapFree( SystemHeap
, 0, oldRects
);
1443 /***********************************************************************
1444 * Region Intersection
1445 ***********************************************************************/
1448 /***********************************************************************
1451 * Handle an overlapping band for REGION_Intersect.
1457 * Rectangles may be added to the region.
1460 static void REGION_IntersectO(WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1461 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1467 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1469 while ((r1
!= r1End
) && (r2
!= r2End
))
1471 left
= MAX(r1
->left
, r2
->left
);
1472 right
= MIN(r1
->right
, r2
->right
);
1475 * If there's any overlap between the two rectangles, add that
1476 * overlap to the new region.
1477 * There's no need to check for subsumption because the only way
1478 * such a need could arise is if some region has two rectangles
1479 * right next to each other. Since that should never happen...
1483 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1484 pNextRect
->left
= left
;
1485 pNextRect
->top
= top
;
1486 pNextRect
->right
= right
;
1487 pNextRect
->bottom
= bottom
;
1488 pReg
->numRects
+= 1;
1493 * Need to advance the pointers. Shift the one that extends
1494 * to the right the least, since the other still has a chance to
1495 * overlap with that region's next rectangle, if you see what I mean.
1497 if (r1
->right
< r2
->right
)
1501 else if (r2
->right
< r1
->right
)
1514 /***********************************************************************
1515 * REGION_IntersectRegion
1517 static void REGION_IntersectRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1520 /* check for trivial reject */
1521 if ( (!(reg1
->numRects
)) || (!(reg2
->numRects
)) ||
1522 (!EXTENTCHECK(®1
->extents
, ®2
->extents
)))
1523 newReg
->numRects
= 0;
1525 REGION_RegionOp (newReg
, reg1
, reg2
,
1526 (voidProcp
) REGION_IntersectO
, (voidProcp
) NULL
, (voidProcp
) NULL
);
1529 * Can't alter newReg's extents before we call miRegionOp because
1530 * it might be one of the source regions and miRegionOp depends
1531 * on the extents of those regions being the same. Besides, this
1532 * way there's no checking against rectangles that will be nuked
1533 * due to coalescing, so we have to examine fewer rectangles.
1535 REGION_SetExtents(newReg
);
1536 newReg
->type
= (newReg
->numRects
) ? COMPLEXREGION
: NULLREGION
;
1540 /***********************************************************************
1542 ***********************************************************************/
1544 /***********************************************************************
1547 * Handle a non-overlapping band for the union operation. Just
1548 * Adds the rectangles into the region. Doesn't have to check for
1549 * subsumption or anything.
1555 * pReg->numRects is incremented and the final rectangles overwritten
1556 * with the rectangles we're passed.
1559 static void REGION_UnionNonO (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1560 INT top
, INT bottom
)
1564 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1568 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1569 pNextRect
->left
= r
->left
;
1570 pNextRect
->top
= top
;
1571 pNextRect
->right
= r
->right
;
1572 pNextRect
->bottom
= bottom
;
1573 pReg
->numRects
+= 1;
1580 /***********************************************************************
1583 * Handle an overlapping band for the union operation. Picks the
1584 * left-most rectangle each time and merges it into the region.
1590 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1594 static void REGION_UnionO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1595 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1599 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1601 #define MERGERECT(r) \
1602 if ((pReg->numRects != 0) && \
1603 (pNextRect[-1].top == top) && \
1604 (pNextRect[-1].bottom == bottom) && \
1605 (pNextRect[-1].right >= r->left)) \
1607 if (pNextRect[-1].right < r->right) \
1609 pNextRect[-1].right = r->right; \
1614 MEMCHECK(pReg, pNextRect, pReg->rects); \
1615 pNextRect->top = top; \
1616 pNextRect->bottom = bottom; \
1617 pNextRect->left = r->left; \
1618 pNextRect->right = r->right; \
1619 pReg->numRects += 1; \
1624 while ((r1
!= r1End
) && (r2
!= r2End
))
1626 if (r1
->left
< r2
->left
)
1641 } while (r1
!= r1End
);
1643 else while (r2
!= r2End
)
1650 /***********************************************************************
1651 * REGION_UnionRegion
1653 static void REGION_UnionRegion(WINEREGION
*newReg
, WINEREGION
*reg1
,
1656 /* checks all the simple cases */
1659 * Region 1 and 2 are the same or region 1 is empty
1661 if ( (reg1
== reg2
) || (!(reg1
->numRects
)) )
1664 REGION_CopyRegion(newReg
, reg2
);
1669 * if nothing to union (region 2 empty)
1671 if (!(reg2
->numRects
))
1674 REGION_CopyRegion(newReg
, reg1
);
1679 * Region 1 completely subsumes region 2
1681 if ((reg1
->numRects
== 1) &&
1682 (reg1
->extents
.left
<= reg2
->extents
.left
) &&
1683 (reg1
->extents
.top
<= reg2
->extents
.top
) &&
1684 (reg1
->extents
.right
>= reg2
->extents
.right
) &&
1685 (reg1
->extents
.bottom
>= reg2
->extents
.bottom
))
1688 REGION_CopyRegion(newReg
, reg1
);
1693 * Region 2 completely subsumes region 1
1695 if ((reg2
->numRects
== 1) &&
1696 (reg2
->extents
.left
<= reg1
->extents
.left
) &&
1697 (reg2
->extents
.top
<= reg1
->extents
.top
) &&
1698 (reg2
->extents
.right
>= reg1
->extents
.right
) &&
1699 (reg2
->extents
.bottom
>= reg1
->extents
.bottom
))
1702 REGION_CopyRegion(newReg
, reg2
);
1706 REGION_RegionOp (newReg
, reg1
, reg2
, (voidProcp
) REGION_UnionO
,
1707 (voidProcp
) REGION_UnionNonO
, (voidProcp
) REGION_UnionNonO
);
1709 newReg
->extents
.left
= MIN(reg1
->extents
.left
, reg2
->extents
.left
);
1710 newReg
->extents
.top
= MIN(reg1
->extents
.top
, reg2
->extents
.top
);
1711 newReg
->extents
.right
= MAX(reg1
->extents
.right
, reg2
->extents
.right
);
1712 newReg
->extents
.bottom
= MAX(reg1
->extents
.bottom
, reg2
->extents
.bottom
);
1713 newReg
->type
= (newReg
->numRects
) ? COMPLEXREGION
: NULLREGION
;
1717 /***********************************************************************
1718 * Region Subtraction
1719 ***********************************************************************/
1721 /***********************************************************************
1722 * REGION_SubtractNonO1
1724 * Deal with non-overlapping band for subtraction. Any parts from
1725 * region 2 we discard. Anything from region 1 we add to the region.
1731 * pReg may be affected.
1734 static void REGION_SubtractNonO1 (WINEREGION
*pReg
, RECT
*r
, RECT
*rEnd
,
1735 INT top
, INT bottom
)
1739 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1743 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1744 pNextRect
->left
= r
->left
;
1745 pNextRect
->top
= top
;
1746 pNextRect
->right
= r
->right
;
1747 pNextRect
->bottom
= bottom
;
1748 pReg
->numRects
+= 1;
1756 /***********************************************************************
1759 * Overlapping band subtraction. x1 is the left-most point not yet
1766 * pReg may have rectangles added to it.
1769 static void REGION_SubtractO (WINEREGION
*pReg
, RECT
*r1
, RECT
*r1End
,
1770 RECT
*r2
, RECT
*r2End
, INT top
, INT bottom
)
1776 pNextRect
= &pReg
->rects
[pReg
->numRects
];
1778 while ((r1
!= r1End
) && (r2
!= r2End
))
1780 if (r2
->right
<= left
)
1783 * Subtrahend missed the boat: go to next subtrahend.
1787 else if (r2
->left
<= left
)
1790 * Subtrahend preceeds minuend: nuke left edge of minuend.
1793 if (left
>= r1
->right
)
1796 * Minuend completely covered: advance to next minuend and
1797 * reset left fence to edge of new minuend.
1806 * Subtrahend now used up since it doesn't extend beyond
1812 else if (r2
->left
< r1
->right
)
1815 * Left part of subtrahend covers part of minuend: add uncovered
1816 * part of minuend to region and skip to next subtrahend.
1818 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1819 pNextRect
->left
= left
;
1820 pNextRect
->top
= top
;
1821 pNextRect
->right
= r2
->left
;
1822 pNextRect
->bottom
= bottom
;
1823 pReg
->numRects
+= 1;
1826 if (left
>= r1
->right
)
1829 * Minuend used up: advance to new...
1838 * Subtrahend used up
1846 * Minuend used up: add any remaining piece before advancing.
1848 if (r1
->right
> left
)
1850 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1851 pNextRect
->left
= left
;
1852 pNextRect
->top
= top
;
1853 pNextRect
->right
= r1
->right
;
1854 pNextRect
->bottom
= bottom
;
1855 pReg
->numRects
+= 1;
1864 * Add remaining minuend rectangles to region.
1868 MEMCHECK(pReg
, pNextRect
, pReg
->rects
);
1869 pNextRect
->left
= left
;
1870 pNextRect
->top
= top
;
1871 pNextRect
->right
= r1
->right
;
1872 pNextRect
->bottom
= bottom
;
1873 pReg
->numRects
+= 1;
1884 /***********************************************************************
1885 * REGION_SubtractRegion
1887 * Subtract regS from regM and leave the result in regD.
1888 * S stands for subtrahend, M for minuend and D for difference.
1894 * regD is overwritten.
1897 static void REGION_SubtractRegion(WINEREGION
*regD
, WINEREGION
*regM
,
1900 /* check for trivial reject */
1901 if ( (!(regM
->numRects
)) || (!(regS
->numRects
)) ||
1902 (!EXTENTCHECK(®M
->extents
, ®S
->extents
)) )
1904 REGION_CopyRegion(regD
, regM
);
1908 REGION_RegionOp (regD
, regM
, regS
, (voidProcp
) REGION_SubtractO
,
1909 (voidProcp
) REGION_SubtractNonO1
, (voidProcp
) NULL
);
1912 * Can't alter newReg's extents before we call miRegionOp because
1913 * it might be one of the source regions and miRegionOp depends
1914 * on the extents of those regions being the unaltered. Besides, this
1915 * way there's no checking against rectangles that will be nuked
1916 * due to coalescing, so we have to examine fewer rectangles.
1918 REGION_SetExtents (regD
);
1919 regD
->type
= (regD
->numRects
) ? COMPLEXREGION
: NULLREGION
;
1923 /***********************************************************************
1926 static void REGION_XorRegion(WINEREGION
*dr
, WINEREGION
*sra
,
1929 WINEREGION
*tra
, *trb
;
1931 if ((! (tra
= REGION_AllocWineRegion(sra
->numRects
+ 1))) ||
1932 (! (trb
= REGION_AllocWineRegion(srb
->numRects
+ 1))))
1934 REGION_SubtractRegion(tra
,sra
,srb
);
1935 REGION_SubtractRegion(trb
,srb
,sra
);
1936 REGION_UnionRegion(dr
,tra
,trb
);
1937 REGION_DestroyWineRegion(tra
);
1938 REGION_DestroyWineRegion(trb
);
1942 /**************************************************************************
1946 *************************************************************************/
1948 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
1949 #define SMALL_COORDINATE 0x80000000
1951 /***********************************************************************
1952 * REGION_InsertEdgeInET
1954 * Insert the given edge into the edge table.
1955 * First we must find the correct bucket in the
1956 * Edge table, then find the right slot in the
1957 * bucket. Finally, we can insert it.
1960 static void REGION_InsertEdgeInET(EdgeTable
*ET
, EdgeTableEntry
*ETE
,
1961 INT scanline
, ScanLineListBlock
**SLLBlock
, INT
*iSLLBlock
)
1964 EdgeTableEntry
*start
, *prev
;
1965 ScanLineList
*pSLL
, *pPrevSLL
;
1966 ScanLineListBlock
*tmpSLLBlock
;
1969 * find the right bucket to put the edge into
1971 pPrevSLL
= &ET
->scanlines
;
1972 pSLL
= pPrevSLL
->next
;
1973 while (pSLL
&& (pSLL
->scanline
< scanline
))
1980 * reassign pSLL (pointer to ScanLineList) if necessary
1982 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
1984 if (*iSLLBlock
> SLLSPERBLOCK
-1)
1986 tmpSLLBlock
= HeapAlloc( SystemHeap
, 0, sizeof(ScanLineListBlock
));
1989 WARN(region
, "Can't alloc SLLB\n");
1992 (*SLLBlock
)->next
= tmpSLLBlock
;
1993 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
1994 *SLLBlock
= tmpSLLBlock
;
1997 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
1999 pSLL
->next
= pPrevSLL
->next
;
2000 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
2001 pPrevSLL
->next
= pSLL
;
2003 pSLL
->scanline
= scanline
;
2006 * now insert the edge in the right bucket
2008 prev
= (EdgeTableEntry
*)NULL
;
2009 start
= pSLL
->edgelist
;
2010 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
2013 start
= start
->next
;
2020 pSLL
->edgelist
= ETE
;
2023 /***********************************************************************
2024 * REGION_CreateEdgeTable
2026 * This routine creates the edge table for
2027 * scan converting polygons.
2028 * The Edge Table (ET) looks like:
2032 * | ymax | ScanLineLists
2033 * |scanline|-->------------>-------------->...
2034 * -------- |scanline| |scanline|
2035 * |edgelist| |edgelist|
2036 * --------- ---------
2040 * list of ETEs list of ETEs
2042 * where ETE is an EdgeTableEntry data structure,
2043 * and there is one ScanLineList per scanline at
2044 * which an edge is initially entered.
2047 static void REGION_CreateETandAET(const INT
*Count
, INT nbpolygons
,
2048 const POINT
*pts
, EdgeTable
*ET
, EdgeTableEntry
*AET
,
2049 EdgeTableEntry
*pETEs
, ScanLineListBlock
*pSLLBlock
)
2051 const POINT
*top
, *bottom
;
2052 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
2059 * initialize the Active Edge Table
2061 AET
->next
= (EdgeTableEntry
*)NULL
;
2062 AET
->back
= (EdgeTableEntry
*)NULL
;
2063 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2064 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
2067 * initialize the Edge Table.
2069 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
2070 ET
->ymax
= SMALL_COORDINATE
;
2071 ET
->ymin
= LARGE_COORDINATE
;
2072 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
2075 for(poly
= 0; poly
< nbpolygons
; poly
++)
2077 count
= Count
[poly
];
2085 * for each vertex in the array of points.
2086 * In this loop we are dealing with two vertices at
2087 * a time -- these make up one edge of the polygon.
2094 * find out which point is above and which is below.
2096 if (PrevPt
->y
> CurrPt
->y
)
2098 bottom
= PrevPt
, top
= CurrPt
;
2099 pETEs
->ClockWise
= 0;
2103 bottom
= CurrPt
, top
= PrevPt
;
2104 pETEs
->ClockWise
= 1;
2108 * don't add horizontal edges to the Edge table.
2110 if (bottom
->y
!= top
->y
)
2112 pETEs
->ymax
= bottom
->y
-1;
2113 /* -1 so we don't get last scanline */
2116 * initialize integer edge algorithm
2118 dy
= bottom
->y
- top
->y
;
2119 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
2121 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
2124 if (PrevPt
->y
> ET
->ymax
)
2125 ET
->ymax
= PrevPt
->y
;
2126 if (PrevPt
->y
< ET
->ymin
)
2127 ET
->ymin
= PrevPt
->y
;
2136 /***********************************************************************
2139 * This routine moves EdgeTableEntries from the
2140 * EdgeTable into the Active Edge Table,
2141 * leaving them sorted by smaller x coordinate.
2144 static void REGION_loadAET(EdgeTableEntry
*AET
, EdgeTableEntry
*ETEs
)
2146 EdgeTableEntry
*pPrevAET
;
2147 EdgeTableEntry
*tmp
;
2153 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
2162 ETEs
->back
= pPrevAET
;
2163 pPrevAET
->next
= ETEs
;
2170 /***********************************************************************
2171 * REGION_computeWAET
2173 * This routine links the AET by the
2174 * nextWETE (winding EdgeTableEntry) link for
2175 * use by the winding number rule. The final
2176 * Active Edge Table (AET) might look something
2180 * ---------- --------- ---------
2181 * |ymax | |ymax | |ymax |
2182 * | ... | |... | |... |
2183 * |next |->|next |->|next |->...
2184 * |nextWETE| |nextWETE| |nextWETE|
2185 * --------- --------- ^--------
2187 * V-------------------> V---> ...
2190 static void REGION_computeWAET(EdgeTableEntry
*AET
)
2192 register EdgeTableEntry
*pWETE
;
2193 register int inside
= 1;
2194 register int isInside
= 0;
2196 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
2206 if ((!inside
&& !isInside
) ||
2207 ( inside
&& isInside
))
2209 pWETE
->nextWETE
= AET
;
2215 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
2218 /***********************************************************************
2219 * REGION_InsertionSort
2221 * Just a simple insertion sort using
2222 * pointers and back pointers to sort the Active
2226 static BOOL
REGION_InsertionSort(EdgeTableEntry
*AET
)
2228 EdgeTableEntry
*pETEchase
;
2229 EdgeTableEntry
*pETEinsert
;
2230 EdgeTableEntry
*pETEchaseBackTMP
;
2231 BOOL changed
= FALSE
;
2238 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
2239 pETEchase
= pETEchase
->back
;
2242 if (pETEchase
!= pETEinsert
)
2244 pETEchaseBackTMP
= pETEchase
->back
;
2245 pETEinsert
->back
->next
= AET
;
2247 AET
->back
= pETEinsert
->back
;
2248 pETEinsert
->next
= pETEchase
;
2249 pETEchase
->back
->next
= pETEinsert
;
2250 pETEchase
->back
= pETEinsert
;
2251 pETEinsert
->back
= pETEchaseBackTMP
;
2258 /***********************************************************************
2259 * REGION_FreeStorage
2263 static void REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
2265 ScanLineListBlock
*tmpSLLBlock
;
2269 tmpSLLBlock
= pSLLBlock
->next
;
2270 HeapFree( SystemHeap
, 0, pSLLBlock
);
2271 pSLLBlock
= tmpSLLBlock
;
2276 /***********************************************************************
2277 * REGION_PtsToRegion
2279 * Create an array of rectangles from a list of points.
2281 static int REGION_PtsToRegion(int numFullPtBlocks
, int iCurPtBlock
,
2282 POINTBLOCK
*FirstPtBlock
, WINEREGION
*reg
)
2286 POINTBLOCK
*CurPtBlock
;
2291 extents
= ®
->extents
;
2293 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
2295 if (!(reg
->rects
= HeapReAlloc( SystemHeap
, 0, reg
->rects
,
2296 sizeof(RECT
) * numRects
)))
2299 reg
->size
= numRects
;
2300 CurPtBlock
= FirstPtBlock
;
2301 rects
= reg
->rects
- 1;
2303 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
2305 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--) {
2306 /* the loop uses 2 points per iteration */
2307 i
= NUMPTSTOBUFFER
>> 1;
2308 if (!numFullPtBlocks
)
2309 i
= iCurPtBlock
>> 1;
2310 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2) {
2311 if (pts
->x
== pts
[1].x
)
2313 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
2314 pts
[1].x
== rects
->right
&&
2315 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
2316 (i
&& pts
[2].y
> pts
[1].y
)) {
2317 rects
->bottom
= pts
[1].y
+ 1;
2322 rects
->left
= pts
->x
; rects
->top
= pts
->y
;
2323 rects
->right
= pts
[1].x
; rects
->bottom
= pts
[1].y
+ 1;
2324 if (rects
->left
< extents
->left
)
2325 extents
->left
= rects
->left
;
2326 if (rects
->right
> extents
->right
)
2327 extents
->right
= rects
->right
;
2329 CurPtBlock
= CurPtBlock
->next
;
2333 extents
->top
= reg
->rects
->top
;
2334 extents
->bottom
= rects
->bottom
;
2339 extents
->bottom
= 0;
2341 reg
->numRects
= numRects
;
2346 /***********************************************************************
2347 * CreatePolyPolygonRgn32 (GDI32.57)
2349 HRGN WINAPI
CreatePolyPolygonRgn(const POINT
*Pts
, const INT
*Count
,
2350 INT nbpolygons
, INT mode
)
2355 register EdgeTableEntry
*pAET
; /* Active Edge Table */
2356 register INT y
; /* current scanline */
2357 register int iPts
= 0; /* number of pts in buffer */
2358 register EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
2359 register ScanLineList
*pSLL
; /* current scanLineList */
2360 register POINT
*pts
; /* output buffer */
2361 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
2362 EdgeTable ET
; /* header node for ET */
2363 EdgeTableEntry AET
; /* header node for AET */
2364 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
2365 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
2366 int fixWAET
= FALSE
;
2367 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
2368 POINTBLOCK
*tmpPtBlock
;
2369 int numFullPtBlocks
= 0;
2372 if(!(hrgn
= REGION_CreateRegion(nbpolygons
)))
2374 obj
= (RGNOBJ
*) GDI_GetObjPtr( hrgn
, REGION_MAGIC
);
2377 /* special case a rectangle */
2379 if (((nbpolygons
== 1) && ((*Count
== 4) ||
2380 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
2381 (((Pts
[0].y
== Pts
[1].y
) &&
2382 (Pts
[1].x
== Pts
[2].x
) &&
2383 (Pts
[2].y
== Pts
[3].y
) &&
2384 (Pts
[3].x
== Pts
[0].x
)) ||
2385 ((Pts
[0].x
== Pts
[1].x
) &&
2386 (Pts
[1].y
== Pts
[2].y
) &&
2387 (Pts
[2].x
== Pts
[3].x
) &&
2388 (Pts
[3].y
== Pts
[0].y
))))
2390 SetRectRgn( hrgn
, MIN(Pts
[0].x
, Pts
[2].x
), MIN(Pts
[0].y
, Pts
[2].y
),
2391 MAX(Pts
[0].x
, Pts
[2].x
), MAX(Pts
[0].y
, Pts
[2].y
) );
2392 GDI_HEAP_UNLOCK( hrgn
);
2396 for(poly
= total
= 0; poly
< nbpolygons
; poly
++)
2397 total
+= Count
[poly
];
2398 if (! (pETEs
= HeapAlloc( SystemHeap
, 0, sizeof(EdgeTableEntry
) * total
)))
2400 REGION_DeleteObject( hrgn
, obj
);
2403 pts
= FirstPtBlock
.pts
;
2404 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
2405 pSLL
= ET
.scanlines
.next
;
2406 curPtBlock
= &FirstPtBlock
;
2408 if (mode
!= WINDING
) {
2412 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2414 * Add a new edge to the active edge table when we
2415 * get to the next edge.
2417 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2418 REGION_loadAET(&AET
, pSLL
->edgelist
);
2425 * for each active edge
2428 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2432 * send out the buffer
2434 if (iPts
== NUMPTSTOBUFFER
) {
2435 tmpPtBlock
= HeapAlloc( SystemHeap
, 0, sizeof(POINTBLOCK
));
2437 WARN(region
, "Can't alloc tPB\n");
2440 curPtBlock
->next
= tmpPtBlock
;
2441 curPtBlock
= tmpPtBlock
;
2442 pts
= curPtBlock
->pts
;
2446 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
2448 REGION_InsertionSort(&AET
);
2455 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++) {
2457 * Add a new edge to the active edge table when we
2458 * get to the next edge.
2460 if (pSLL
!= NULL
&& y
== pSLL
->scanline
) {
2461 REGION_loadAET(&AET
, pSLL
->edgelist
);
2462 REGION_computeWAET(&AET
);
2470 * for each active edge
2474 * add to the buffer only those edges that
2475 * are in the Winding active edge table.
2477 if (pWETE
== pAET
) {
2478 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
2482 * send out the buffer
2484 if (iPts
== NUMPTSTOBUFFER
) {
2485 tmpPtBlock
= HeapAlloc( SystemHeap
, 0,
2486 sizeof(POINTBLOCK
) );
2488 WARN(region
, "Can't alloc tPB\n");
2491 curPtBlock
->next
= tmpPtBlock
;
2492 curPtBlock
= tmpPtBlock
;
2493 pts
= curPtBlock
->pts
;
2494 numFullPtBlocks
++; iPts
= 0;
2496 pWETE
= pWETE
->nextWETE
;
2498 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
2502 * recompute the winding active edge table if
2503 * we just resorted or have exited an edge.
2505 if (REGION_InsertionSort(&AET
) || fixWAET
) {
2506 REGION_computeWAET(&AET
);
2511 REGION_FreeStorage(SLLBlock
.next
);
2512 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
2513 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;) {
2514 tmpPtBlock
= curPtBlock
->next
;
2515 HeapFree( SystemHeap
, 0, curPtBlock
);
2516 curPtBlock
= tmpPtBlock
;
2518 HeapFree( SystemHeap
, 0, pETEs
);
2519 GDI_HEAP_UNLOCK( hrgn
);
2524 /***********************************************************************
2525 * CreatePolygonRgn16 (GDI.63)
2527 HRGN16 WINAPI
CreatePolygonRgn16( const POINT16
* points
, INT16 count
,
2530 return CreatePolyPolygonRgn16( points
, &count
, 1, mode
);
2533 /***********************************************************************
2534 * CreatePolyPolygonRgn16 (GDI.451)
2536 HRGN16 WINAPI
CreatePolyPolygonRgn16( const POINT16
*points
,
2537 const INT16
*count
, INT16 nbpolygons
, INT16 mode
)
2544 for (i
= 0; i
< nbpolygons
; i
++)
2546 points32
= HeapAlloc( SystemHeap
, 0, npts
* sizeof(POINT
) );
2547 for (i
= 0; i
< npts
; i
++)
2548 CONV_POINT16TO32( &(points
[i
]), &(points32
[i
]) );
2550 count32
= HeapAlloc( SystemHeap
, 0, nbpolygons
* sizeof(INT
) );
2551 for (i
= 0; i
< nbpolygons
; i
++)
2552 count32
[i
] = count
[i
];
2553 hrgn
= CreatePolyPolygonRgn( points32
, count32
, nbpolygons
, mode
);
2554 HeapFree( SystemHeap
, 0, count32
);
2555 HeapFree( SystemHeap
, 0, points32
);
2559 /***********************************************************************
2560 * CreatePolygonRgn32 (GDI32.58)
2562 HRGN WINAPI
CreatePolygonRgn( const POINT
*points
, INT count
,
2565 return CreatePolyPolygonRgn( points
, &count
, 1, mode
);
2569 /***********************************************************************
2570 * GetRandomRgn [GDI32.215]
2573 * This function is UNDOCUMENTED, it isn't even in the header file.
2574 * I assume that it will return a HRGN32!??
2576 HRGN WINAPI
GetRandomRgn(DWORD dwArg1
, DWORD dwArg2
, DWORD dwArg3
)
2578 FIXME (region
, "(0x%08lx 0x%08lx 0x%08lx): empty stub!\n",
2579 dwArg1
, dwArg2
, dwArg3
);
2584 /***********************************************************************
2585 * REGION_CropAndOffsetRegion
2587 static BOOL
REGION_CropAndOffsetRegion(const POINT
* off
, const RECT
*rect
, WINEREGION
*rgnSrc
, WINEREGION
* rgnDst
)
2589 if( IsRectEmpty(rect
) || !EXTENTCHECK(rect
, &rgnSrc
->extents
) )
2592 if( !rgnDst
->rects
)
2594 rgnDst
->rects
= HeapAlloc(SystemHeap
, 0, sizeof( RECT
));
2601 TRACE(region
,"cropped to empty!\n");
2602 EMPTY_REGION(rgnDst
);
2604 else /* region box and clipping rect appear to intersect */
2607 INT i
, j
, clipa
, clipb
;
2608 INT left
= rgnSrc
->extents
.right
+ off
->x
;
2609 INT right
= rgnSrc
->extents
.left
+ off
->x
;
2611 for( clipa
= 0; rgnSrc
->rects
[clipa
].bottom
<= rect
->top
; clipa
++ )
2612 ; /* skip bands above the clipping rectangle */
2614 for( clipb
= clipa
; clipb
< rgnSrc
->numRects
; clipb
++ )
2615 if( rgnSrc
->rects
[clipb
].top
>= rect
->bottom
)
2616 break; /* and below it */
2618 /* clipa - index of the first rect in the first intersecting band
2619 * clipb - index of the last rect in the last intersecting band
2622 if((rgnDst
!= rgnSrc
) && (rgnDst
->size
< (i
= (clipb
- clipa
))))
2624 rgnDst
->rects
= HeapReAlloc( SystemHeap
, 0,
2625 rgnDst
->rects
, i
* sizeof(RECT
));
2626 if( !rgnDst
->rects
) return FALSE
;
2630 if( TRACE_ON(region
) )
2632 REGION_DumpRegion( rgnSrc
);
2633 TRACE(region
,"\tclipa = %i, clipb = %i\n", clipa
, clipb
);
2636 for( i
= clipa
, j
= 0; i
< clipb
; i
++ )
2638 /* i - src index, j - dst index, j is always <= i for obvious reasons */
2640 lpr
= rgnSrc
->rects
+ i
;
2641 if( lpr
->left
< rect
->right
&& lpr
->right
> rect
->left
)
2643 rgnDst
->rects
[j
].top
= lpr
->top
+ off
->y
;
2644 rgnDst
->rects
[j
].bottom
= lpr
->bottom
+ off
->y
;
2645 rgnDst
->rects
[j
].left
= ((lpr
->left
> rect
->left
) ? lpr
->left
: rect
->left
) + off
->x
;
2646 rgnDst
->rects
[j
].right
= ((lpr
->right
< rect
->right
) ? lpr
->right
: rect
->right
) + off
->x
;
2648 if( rgnDst
->rects
[j
].left
< left
) left
= rgnDst
->rects
[j
].left
;
2649 if( rgnDst
->rects
[j
].right
> right
) right
= rgnDst
->rects
[j
].right
;
2655 if( j
== 0 ) goto empty
;
2657 rgnDst
->extents
.left
= left
;
2658 rgnDst
->extents
.right
= right
;
2660 left
= rect
->top
+ off
->y
;
2661 right
= rect
->bottom
+ off
->y
;
2663 rgnDst
->numRects
= j
--;
2664 for( i
= 0; i
<= j
; i
++ ) /* fixup top band */
2665 if( rgnDst
->rects
[i
].top
< left
)
2666 rgnDst
->rects
[i
].top
= left
;
2670 for( i
= j
; i
>= 0; i
-- ) /* fixup bottom band */
2671 if( rgnDst
->rects
[i
].bottom
> right
)
2672 rgnDst
->rects
[i
].bottom
= right
;
2676 rgnDst
->extents
.top
= rgnDst
->rects
[0].top
;
2677 rgnDst
->extents
.bottom
= rgnDst
->rects
[j
].bottom
;
2679 rgnDst
->type
= (j
>= 1) ? COMPLEXREGION
: SIMPLEREGION
;
2681 if( TRACE_ON(region
) )
2683 TRACE(region
,"result:\n");
2684 REGION_DumpRegion( rgnDst
);
2691 /***********************************************************************
2695 * hSrc: Region to crop and offset.
2696 * lpRect: Clipping rectangle.
2697 * lpPt: Points to offset the cropped region. Can be NULL.
2699 * hDst: Region to hold the result (if 0 a new region is created).
2700 * Allowed to be the same region as hSrc (in place, no extra memory needed).
2702 * Returns: hDst if success, 0 otherwise.
2704 HRGN
REGION_CropRgn( HRGN hDst
, HRGN hSrc
, const RECT
*lpRect
, const POINT
*lpPt
)
2706 /* Optimization of the following generic code:
2708 HRGN h = CreateRectRgn( lpRect->left, lpRect->top, lpRect->right, lpRect->bottom );
2709 if( hDst == 0 ) hDst = h;
2710 CombineRgn( hDst, hSrc, h, RGN_AND );
2712 OffsetRgn( hDst, lpPt->x, lpPt->y );
2719 RGNOBJ
*objSrc
= (RGNOBJ
*) GDI_HEAP_LOCK( hSrc
);
2728 objDst
= (RGNOBJ
*) GDI_HEAP_LOCK( hDst
);
2729 rgnDst
= objDst
->rgn
;
2733 rgnDst
= HeapAlloc(SystemHeap
, 0, sizeof( WINEREGION
));
2736 rgnDst
->size
= rgnDst
->numRects
= 0;
2737 rgnDst
->rects
= NULL
; /* back end will allocate exact number */
2743 POINT pt
= { 0, 0 };
2745 if( !lpPt
) lpPt
= &pt
;
2747 TRACE(region
, "src %p -> dst %p (%i,%i)-(%i,%i) by (%li,%li)\n", objSrc
->rgn
, rgnDst
,
2748 lpRect
->left
, lpRect
->top
, lpRect
->right
, lpRect
->bottom
, lpPt
->x
, lpPt
->y
);
2750 if( REGION_CropAndOffsetRegion( lpPt
, lpRect
, objSrc
->rgn
, rgnDst
) == FALSE
)
2752 if( hDst
) /* existing rgn */
2754 GDI_HEAP_UNLOCK(hDst
);
2760 else if( hDst
== 0 )
2762 if(!(hDst
= GDI_AllocObject( sizeof(RGNOBJ
), REGION_MAGIC
)))
2766 HeapFree( SystemHeap
, 0, rgnDst
->rects
);
2767 HeapFree( SystemHeap
, 0, rgnDst
);
2771 objDst
= (RGNOBJ
*) GDI_HEAP_LOCK( hDst
);
2772 objDst
->rgn
= rgnDst
;
2775 GDI_HEAP_UNLOCK(hDst
);
2779 GDI_HEAP_UNLOCK(hSrc
);