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.
825 BOOL REGION_LPTODP( HDC hdc, HRGN hDest, HRGN hSrc )
827 RECT *pCurRect, *pEndRect;
828 RGNOBJ *srcObj, *destObj;
829 DC * dc = DC_GetDCPtr( hdc );
832 TRACE(region, " hdc=%04x dest=%04x src=%04x\n",
835 if (dc->w.MapMode == MM_TEXT) /* Requires only a translation */
837 if( CombineRgn( hDest, hSrc, 0, RGN_COPY ) == ERROR ) return FALSE;
838 OffsetRgn( hDest, dc->vportOrgX - dc->wndOrgX,
839 dc->vportOrgY - dc->wndOrgY );
843 if(!( srcObj = (RGNOBJ *) GDI_GetObjPtr( hSrc, REGION_MAGIC) ))
845 if(!( destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC) ))
847 GDI_HEAP_UNLOCK( hSrc );
850 EMPTY_REGION( destObj->rgn );
852 pEndRect = srcObj->rgn->rects + srcObj->rgn->numRects;
853 for(pCurRect = srcObj->rgn->rects; pCurRect < pEndRect; pCurRect++)
856 tmpRect.left = XLPTODP( dc, tmpRect.left );
857 tmpRect.top = YLPTODP( dc, tmpRect.top );
858 tmpRect.right = XLPTODP( dc, tmpRect.right );
859 tmpRect.bottom = YLPTODP( dc, tmpRect.bottom );
860 REGION_UnionRectWithRegion( &tmpRect, destObj->rgn );
863 GDI_HEAP_UNLOCK( hDest );
864 GDI_HEAP_UNLOCK( hSrc );
868 /***********************************************************************
869 * CombineRgn16 (GDI.451)
871 INT16 WINAPI CombineRgn16(HRGN16 hDest, HRGN16 hSrc1, HRGN16 hSrc2, INT16 mode)
873 return (INT16)CombineRgn( hDest, hSrc1, hSrc2, mode );
877 /***********************************************************************
878 * CombineRgn32 (GDI32.19)
880 * Note: The behavior is correct even if src and dest regions are the same.
882 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
884 RGNOBJ *destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC);
887 TRACE(region, " %04x,%04x -> %04x mode=%x\n",
888 hSrc1, hSrc2, hDest, mode );
891 RGNOBJ *src1Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc1, REGION_MAGIC);
895 TRACE(region, "dump:\n");
897 REGION_DumpRegion(src1Obj->rgn);
898 if (mode == RGN_COPY)
900 REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
901 result = destObj->rgn->type;
905 RGNOBJ *src2Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc2, REGION_MAGIC);
909 TRACE(region, "dump:\n");
911 REGION_DumpRegion(src2Obj->rgn);
915 REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
918 REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
921 REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
924 REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
927 result = destObj->rgn->type;
928 GDI_HEAP_UNLOCK( hSrc2 );
931 GDI_HEAP_UNLOCK( hSrc1 );
933 TRACE(region, "dump:\n");
935 REGION_DumpRegion(destObj->rgn);
937 GDI_HEAP_UNLOCK( hDest );
942 /***********************************************************************
944 * Re-calculate the extents of a region
946 static void REGION_SetExtents (WINEREGION *pReg)
948 RECT *pRect, *pRectEnd, *pExtents;
950 if (pReg->numRects == 0)
952 pReg->extents.left = 0;
953 pReg->extents.top = 0;
954 pReg->extents.right = 0;
955 pReg->extents.bottom = 0;
959 pExtents = &pReg->extents;
961 pRectEnd = &pRect[pReg->numRects - 1];
964 * Since pRect is the first rectangle in the region, it must have the
965 * smallest top and since pRectEnd is the last rectangle in the region,
966 * it must have the largest bottom, because of banding. Initialize left and
967 * right from pRect and pRectEnd, resp., as good things to initialize them
970 pExtents->left = pRect->left;
971 pExtents->top = pRect->top;
972 pExtents->right = pRectEnd->right;
973 pExtents->bottom = pRectEnd->bottom;
975 while (pRect <= pRectEnd)
977 if (pRect->left < pExtents->left)
978 pExtents->left = pRect->left;
979 if (pRect->right > pExtents->right)
980 pExtents->right = pRect->right;
985 /***********************************************************************
988 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
990 if (dst != src) /* don't want to copy to itself */
992 if (dst->size < src->numRects)
994 if (! (dst->rects = HeapReAlloc( SystemHeap, 0, dst->rects,
995 src->numRects * sizeof(RECT) )))
997 dst->size = src->numRects;
999 dst->numRects = src->numRects;
1000 dst->extents.left = src->extents.left;
1001 dst->extents.top = src->extents.top;
1002 dst->extents.right = src->extents.right;
1003 dst->extents.bottom = src->extents.bottom;
1004 dst->type = src->type;
1006 memcpy((char *) dst->rects, (char *) src->rects,
1007 (int) (src->numRects * sizeof(RECT)));
1012 /***********************************************************************
1015 * Attempt to merge the rects in the current band with those in the
1016 * previous one. Used only by REGION_RegionOp.
1019 * The new index for the previous band.
1022 * If coalescing takes place:
1023 * - rectangles in the previous band will have their bottom fields
1025 * - pReg->numRects will be decreased.
1028 static INT REGION_Coalesce (
1029 WINEREGION *pReg, /* Region to coalesce */
1030 INT prevStart, /* Index of start of previous band */
1031 INT curStart /* Index of start of current band */
1033 RECT *pPrevRect; /* Current rect in previous band */
1034 RECT *pCurRect; /* Current rect in current band */
1035 RECT *pRegEnd; /* End of region */
1036 INT curNumRects; /* Number of rectangles in current band */
1037 INT prevNumRects; /* Number of rectangles in previous band */
1038 INT bandtop; /* top coordinate for current band */
1040 pRegEnd = &pReg->rects[pReg->numRects];
1042 pPrevRect = &pReg->rects[prevStart];
1043 prevNumRects = curStart - prevStart;
1046 * Figure out how many rectangles are in the current band. Have to do
1047 * this because multiple bands could have been added in REGION_RegionOp
1048 * at the end when one region has been exhausted.
1050 pCurRect = &pReg->rects[curStart];
1051 bandtop = pCurRect->top;
1052 for (curNumRects = 0;
1053 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1059 if (pCurRect != pRegEnd)
1062 * If more than one band was added, we have to find the start
1063 * of the last band added so the next coalescing job can start
1064 * at the right place... (given when multiple bands are added,
1065 * this may be pointless -- see above).
1068 while (pRegEnd[-1].top == pRegEnd->top)
1072 curStart = pRegEnd - pReg->rects;
1073 pRegEnd = pReg->rects + pReg->numRects;
1076 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1077 pCurRect -= curNumRects;
1079 * The bands may only be coalesced if the bottom of the previous
1080 * matches the top scanline of the current.
1082 if (pPrevRect->bottom == pCurRect->top)
1085 * Make sure the bands have rects in the same places. This
1086 * assumes that rects have been added in such a way that they
1087 * cover the most area possible. I.e. two rects in a band must
1088 * have some horizontal space between them.
1092 if ((pPrevRect->left != pCurRect->left) ||
1093 (pPrevRect->right != pCurRect->right))
1096 * The bands don't line up so they can't be coalesced.
1103 } while (prevNumRects != 0);
1105 pReg->numRects -= curNumRects;
1106 pCurRect -= curNumRects;
1107 pPrevRect -= curNumRects;
1110 * The bands may be merged, so set the bottom of each rect
1111 * in the previous band to that of the corresponding rect in
1116 pPrevRect->bottom = pCurRect->bottom;
1120 } while (curNumRects != 0);
1123 * If only one band was added to the region, we have to backup
1124 * curStart to the start of the previous band.
1126 * If more than one band was added to the region, copy the
1127 * other bands down. The assumption here is that the other bands
1128 * came from the same region as the current one and no further
1129 * coalescing can be done on them since it's all been done
1130 * already... curStart is already in the right place.
1132 if (pCurRect == pRegEnd)
1134 curStart = prevStart;
1140 *pPrevRect++ = *pCurRect++;
1141 } while (pCurRect != pRegEnd);
1149 /***********************************************************************
1152 * Apply an operation to two regions. Called by REGION_Union,
1153 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1159 * The new region is overwritten.
1162 * The idea behind this function is to view the two regions as sets.
1163 * Together they cover a rectangle of area that this function divides
1164 * into horizontal bands where points are covered only by one region
1165 * or by both. For the first case, the nonOverlapFunc is called with
1166 * each the band and the band's upper and lower extents. For the
1167 * second, the overlapFunc is called to process the entire band. It
1168 * is responsible for clipping the rectangles in the band, though
1169 * this function provides the boundaries.
1170 * At the end of each band, the new region is coalesced, if possible,
1171 * to reduce the number of rectangles in the region.
1174 static void REGION_RegionOp(
1175 WINEREGION *newReg, /* Place to store result */
1176 WINEREGION *reg1, /* First region in operation */
1177 WINEREGION *reg2, /* 2nd region in operation */
1178 void (*overlapFunc)(), /* Function to call for over-lapping bands */
1179 void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
1180 void (*nonOverlap2Func)() /* Function to call for non-overlapping bands in region 2 */
1182 RECT *r1; /* Pointer into first region */
1183 RECT *r2; /* Pointer into 2d region */
1184 RECT *r1End; /* End of 1st region */
1185 RECT *r2End; /* End of 2d region */
1186 INT ybot; /* Bottom of intersection */
1187 INT ytop; /* Top of intersection */
1188 RECT *oldRects; /* Old rects for newReg */
1189 INT prevBand; /* Index of start of
1190 * previous band in newReg */
1191 INT curBand; /* Index of start of current
1193 RECT *r1BandEnd; /* End of current band in r1 */
1194 RECT *r2BandEnd; /* End of current band in r2 */
1195 INT top; /* Top of non-overlapping band */
1196 INT bot; /* Bottom of non-overlapping band */
1200 * set r1, r2, r1End and r2End appropriately, preserve the important
1201 * parts of the destination region until the end in case it's one of
1202 * the two source regions, then mark the "new" region empty, allocating
1203 * another array of rectangles for it to use.
1207 r1End = r1 + reg1->numRects;
1208 r2End = r2 + reg2->numRects;
1212 * newReg may be one of the src regions so we can't empty it. We keep a
1213 * note of its rects pointer (so that we can free them later), preserve its
1214 * extents and simply set numRects to zero.
1217 oldRects = newReg->rects;
1218 newReg->numRects = 0;
1221 * Allocate a reasonable number of rectangles for the new region. The idea
1222 * is to allocate enough so the individual functions don't need to
1223 * reallocate and copy the array, which is time consuming, yet we don't
1224 * have to worry about using too much memory. I hope to be able to
1225 * nuke the Xrealloc() at the end of this function eventually.
1227 newReg->size = MAX(reg1->numRects,reg2->numRects) * 2;
1229 if (! (newReg->rects = HeapAlloc( SystemHeap, 0,
1230 sizeof(RECT) * newReg->size )))
1237 * Initialize ybot and ytop.
1238 * In the upcoming loop, ybot and ytop serve different functions depending
1239 * on whether the band being handled is an overlapping or non-overlapping
1241 * In the case of a non-overlapping band (only one of the regions
1242 * has points in the band), ybot is the bottom of the most recent
1243 * intersection and thus clips the top of the rectangles in that band.
1244 * ytop is the top of the next intersection between the two regions and
1245 * serves to clip the bottom of the rectangles in the current band.
1246 * For an overlapping band (where the two regions intersect), ytop clips
1247 * the top of the rectangles of both regions and ybot clips the bottoms.
1249 if (reg1->extents.top < reg2->extents.top)
1250 ybot = reg1->extents.top;
1252 ybot = reg2->extents.top;
1255 * prevBand serves to mark the start of the previous band so rectangles
1256 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1257 * In the beginning, there is no previous band, so prevBand == curBand
1258 * (curBand is set later on, of course, but the first band will always
1259 * start at index 0). prevBand and curBand must be indices because of
1260 * the possible expansion, and resultant moving, of the new region's
1261 * array of rectangles.
1267 curBand = newReg->numRects;
1270 * This algorithm proceeds one source-band (as opposed to a
1271 * destination band, which is determined by where the two regions
1272 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1273 * rectangle after the last one in the current band for their
1274 * respective regions.
1277 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1283 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1289 * First handle the band that doesn't intersect, if any.
1291 * Note that attention is restricted to one band in the
1292 * non-intersecting region at once, so if a region has n
1293 * bands between the current position and the next place it overlaps
1294 * the other, this entire loop will be passed through n times.
1296 if (r1->top < r2->top)
1298 top = MAX(r1->top,ybot);
1299 bot = MIN(r1->bottom,r2->top);
1301 if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
1303 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1308 else if (r2->top < r1->top)
1310 top = MAX(r2->top,ybot);
1311 bot = MIN(r2->bottom,r1->top);
1313 if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
1315 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1326 * If any rectangles got added to the region, try and coalesce them
1327 * with rectangles from the previous band. Note we could just do
1328 * this test in miCoalesce, but some machines incur a not
1329 * inconsiderable cost for function calls, so...
1331 if (newReg->numRects != curBand)
1333 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1337 * Now see if we've hit an intersecting band. The two bands only
1338 * intersect if ybot > ytop
1340 ybot = MIN(r1->bottom, r2->bottom);
1341 curBand = newReg->numRects;
1344 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1348 if (newReg->numRects != curBand)
1350 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1354 * If we've finished with a band (bottom == ybot) we skip forward
1355 * in the region to the next band.
1357 if (r1->bottom == ybot)
1361 if (r2->bottom == ybot)
1365 } while ((r1 != r1End) && (r2 != r2End));
1368 * Deal with whichever region still has rectangles left.
1370 curBand = newReg->numRects;
1373 if (nonOverlap1Func != (void (*)())NULL)
1378 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1382 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1383 MAX(r1->top,ybot), r1->bottom);
1385 } while (r1 != r1End);
1388 else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
1393 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1397 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1398 MAX(r2->top,ybot), r2->bottom);
1400 } while (r2 != r2End);
1403 if (newReg->numRects != curBand)
1405 (void) REGION_Coalesce (newReg, prevBand, curBand);
1409 * A bit of cleanup. To keep regions from growing without bound,
1410 * we shrink the array of rectangles to match the new number of
1411 * rectangles in the region. This never goes to 0, however...
1413 * Only do this stuff if the number of rectangles allocated is more than
1414 * twice the number of rectangles in the region (a simple optimization...).
1416 if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1418 if (REGION_NOT_EMPTY(newReg))
1420 RECT *prev_rects = newReg->rects;
1421 newReg->size = newReg->numRects;
1422 newReg->rects = HeapReAlloc( SystemHeap, 0, newReg->rects,
1423 sizeof(RECT) * newReg->size );
1424 if (! newReg->rects)
1425 newReg->rects = prev_rects;
1430 * No point in doing the extra work involved in an Xrealloc if
1431 * the region is empty
1434 HeapFree( SystemHeap, 0, newReg->rects );
1435 newReg->rects = HeapAlloc( SystemHeap, 0, sizeof(RECT) );
1438 HeapFree( SystemHeap, 0, oldRects );
1442 /***********************************************************************
1443 * Region Intersection
1444 ***********************************************************************/
1447 /***********************************************************************
1450 * Handle an overlapping band for REGION_Intersect.
1456 * Rectangles may be added to the region.
1459 static void REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1460 RECT *r2, RECT *r2End, INT top, INT bottom)
1466 pNextRect = &pReg->rects[pReg->numRects];
1468 while ((r1 != r1End) && (r2 != r2End))
1470 left = MAX(r1->left, r2->left);
1471 right = MIN(r1->right, r2->right);
1474 * If there's any overlap between the two rectangles, add that
1475 * overlap to the new region.
1476 * There's no need to check for subsumption because the only way
1477 * such a need could arise is if some region has two rectangles
1478 * right next to each other. Since that should never happen...
1482 MEMCHECK(pReg, pNextRect, pReg->rects);
1483 pNextRect->left = left;
1484 pNextRect->top = top;
1485 pNextRect->right = right;
1486 pNextRect->bottom = bottom;
1487 pReg->numRects += 1;
1492 * Need to advance the pointers. Shift the one that extends
1493 * to the right the least, since the other still has a chance to
1494 * overlap with that region's next rectangle, if you see what I mean.
1496 if (r1->right < r2->right)
1500 else if (r2->right < r1->right)
1513 /***********************************************************************
1514 * REGION_IntersectRegion
1516 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1519 /* check for trivial reject */
1520 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1521 (!EXTENTCHECK(®1->extents, ®2->extents)))
1522 newReg->numRects = 0;
1524 REGION_RegionOp (newReg, reg1, reg2,
1525 (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
1528 * Can't alter newReg's extents before we call miRegionOp because
1529 * it might be one of the source regions and miRegionOp depends
1530 * on the extents of those regions being the same. Besides, this
1531 * way there's no checking against rectangles that will be nuked
1532 * due to coalescing, so we have to examine fewer rectangles.
1534 REGION_SetExtents(newReg);
1535 newReg->type = (newReg->numRects) ? COMPLEXREGION : NULLREGION ;
1539 /***********************************************************************
1541 ***********************************************************************/
1543 /***********************************************************************
1546 * Handle a non-overlapping band for the union operation. Just
1547 * Adds the rectangles into the region. Doesn't have to check for
1548 * subsumption or anything.
1554 * pReg->numRects is incremented and the final rectangles overwritten
1555 * with the rectangles we're passed.
1558 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1559 INT top, INT bottom)
1563 pNextRect = &pReg->rects[pReg->numRects];
1567 MEMCHECK(pReg, pNextRect, pReg->rects);
1568 pNextRect->left = r->left;
1569 pNextRect->top = top;
1570 pNextRect->right = r->right;
1571 pNextRect->bottom = bottom;
1572 pReg->numRects += 1;
1579 /***********************************************************************
1582 * Handle an overlapping band for the union operation. Picks the
1583 * left-most rectangle each time and merges it into the region.
1589 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1593 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1594 RECT *r2, RECT *r2End, INT top, INT bottom)
1598 pNextRect = &pReg->rects[pReg->numRects];
1600 #define MERGERECT(r) \
1601 if ((pReg->numRects != 0) && \
1602 (pNextRect[-1].top == top) && \
1603 (pNextRect[-1].bottom == bottom) && \
1604 (pNextRect[-1].right >= r->left)) \
1606 if (pNextRect[-1].right < r->right) \
1608 pNextRect[-1].right = r->right; \
1613 MEMCHECK(pReg, pNextRect, pReg->rects); \
1614 pNextRect->top = top; \
1615 pNextRect->bottom = bottom; \
1616 pNextRect->left = r->left; \
1617 pNextRect->right = r->right; \
1618 pReg->numRects += 1; \
1623 while ((r1 != r1End) && (r2 != r2End))
1625 if (r1->left < r2->left)
1640 } while (r1 != r1End);
1642 else while (r2 != r2End)
1649 /***********************************************************************
1650 * REGION_UnionRegion
1652 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
1655 /* checks all the simple cases */
1658 * Region 1 and 2 are the same or region 1 is empty
1660 if ( (reg1 == reg2) || (!(reg1->numRects)) )
1663 REGION_CopyRegion(newReg, reg2);
1668 * if nothing to union (region 2 empty)
1670 if (!(reg2->numRects))
1673 REGION_CopyRegion(newReg, reg1);
1678 * Region 1 completely subsumes region 2
1680 if ((reg1->numRects == 1) &&
1681 (reg1->extents.left <= reg2->extents.left) &&
1682 (reg1->extents.top <= reg2->extents.top) &&
1683 (reg1->extents.right >= reg2->extents.right) &&
1684 (reg1->extents.bottom >= reg2->extents.bottom))
1687 REGION_CopyRegion(newReg, reg1);
1692 * Region 2 completely subsumes region 1
1694 if ((reg2->numRects == 1) &&
1695 (reg2->extents.left <= reg1->extents.left) &&
1696 (reg2->extents.top <= reg1->extents.top) &&
1697 (reg2->extents.right >= reg1->extents.right) &&
1698 (reg2->extents.bottom >= reg1->extents.bottom))
1701 REGION_CopyRegion(newReg, reg2);
1705 REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
1706 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
1708 newReg->extents.left = MIN(reg1->extents.left, reg2->extents.left);
1709 newReg->extents.top = MIN(reg1->extents.top, reg2->extents.top);
1710 newReg->extents.right = MAX(reg1->extents.right, reg2->extents.right);
1711 newReg->extents.bottom = MAX(reg1->extents.bottom, reg2->extents.bottom);
1712 newReg->type = (newReg->numRects) ? COMPLEXREGION : NULLREGION ;
1716 /***********************************************************************
1717 * Region Subtraction
1718 ***********************************************************************/
1720 /***********************************************************************
1721 * REGION_SubtractNonO1
1723 * Deal with non-overlapping band for subtraction. Any parts from
1724 * region 2 we discard. Anything from region 1 we add to the region.
1730 * pReg may be affected.
1733 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
1734 INT top, INT bottom)
1738 pNextRect = &pReg->rects[pReg->numRects];
1742 MEMCHECK(pReg, pNextRect, pReg->rects);
1743 pNextRect->left = r->left;
1744 pNextRect->top = top;
1745 pNextRect->right = r->right;
1746 pNextRect->bottom = bottom;
1747 pReg->numRects += 1;
1755 /***********************************************************************
1758 * Overlapping band subtraction. x1 is the left-most point not yet
1765 * pReg may have rectangles added to it.
1768 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1769 RECT *r2, RECT *r2End, INT top, INT bottom)
1775 pNextRect = &pReg->rects[pReg->numRects];
1777 while ((r1 != r1End) && (r2 != r2End))
1779 if (r2->right <= left)
1782 * Subtrahend missed the boat: go to next subtrahend.
1786 else if (r2->left <= left)
1789 * Subtrahend preceeds minuend: nuke left edge of minuend.
1792 if (left >= r1->right)
1795 * Minuend completely covered: advance to next minuend and
1796 * reset left fence to edge of new minuend.
1805 * Subtrahend now used up since it doesn't extend beyond
1811 else if (r2->left < r1->right)
1814 * Left part of subtrahend covers part of minuend: add uncovered
1815 * part of minuend to region and skip to next subtrahend.
1817 MEMCHECK(pReg, pNextRect, pReg->rects);
1818 pNextRect->left = left;
1819 pNextRect->top = top;
1820 pNextRect->right = r2->left;
1821 pNextRect->bottom = bottom;
1822 pReg->numRects += 1;
1825 if (left >= r1->right)
1828 * Minuend used up: advance to new...
1837 * Subtrahend used up
1845 * Minuend used up: add any remaining piece before advancing.
1847 if (r1->right > left)
1849 MEMCHECK(pReg, pNextRect, pReg->rects);
1850 pNextRect->left = left;
1851 pNextRect->top = top;
1852 pNextRect->right = r1->right;
1853 pNextRect->bottom = bottom;
1854 pReg->numRects += 1;
1863 * Add remaining minuend rectangles to region.
1867 MEMCHECK(pReg, pNextRect, pReg->rects);
1868 pNextRect->left = left;
1869 pNextRect->top = top;
1870 pNextRect->right = r1->right;
1871 pNextRect->bottom = bottom;
1872 pReg->numRects += 1;
1883 /***********************************************************************
1884 * REGION_SubtractRegion
1886 * Subtract regS from regM and leave the result in regD.
1887 * S stands for subtrahend, M for minuend and D for difference.
1893 * regD is overwritten.
1896 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
1899 /* check for trivial reject */
1900 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
1901 (!EXTENTCHECK(®M->extents, ®S->extents)) )
1903 REGION_CopyRegion(regD, regM);
1907 REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
1908 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
1911 * Can't alter newReg's extents before we call miRegionOp because
1912 * it might be one of the source regions and miRegionOp depends
1913 * on the extents of those regions being the unaltered. Besides, this
1914 * way there's no checking against rectangles that will be nuked
1915 * due to coalescing, so we have to examine fewer rectangles.
1917 REGION_SetExtents (regD);
1918 regD->type = (regD->numRects) ? COMPLEXREGION : NULLREGION ;
1922 /***********************************************************************
1925 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
1928 WINEREGION *tra, *trb;
1930 if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
1931 (! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
1933 REGION_SubtractRegion(tra,sra,srb);
1934 REGION_SubtractRegion(trb,srb,sra);
1935 REGION_UnionRegion(dr,tra,trb);
1936 REGION_DestroyWineRegion(tra);
1937 REGION_DestroyWineRegion(trb);
1941 /**************************************************************************
1945 *************************************************************************/
1947 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
1948 #define SMALL_COORDINATE 0x80000000
1950 /***********************************************************************
1951 * REGION_InsertEdgeInET
1953 * Insert the given edge into the edge table.
1954 * First we must find the correct bucket in the
1955 * Edge table, then find the right slot in the
1956 * bucket. Finally, we can insert it.
1959 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
1960 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
1963 EdgeTableEntry *start, *prev;
1964 ScanLineList *pSLL, *pPrevSLL;
1965 ScanLineListBlock *tmpSLLBlock;
1968 * find the right bucket to put the edge into
1970 pPrevSLL = &ET->scanlines;
1971 pSLL = pPrevSLL->next;
1972 while (pSLL && (pSLL->scanline < scanline))
1979 * reassign pSLL (pointer to ScanLineList) if necessary
1981 if ((!pSLL) || (pSLL->scanline > scanline))
1983 if (*iSLLBlock > SLLSPERBLOCK-1)
1985 tmpSLLBlock = HeapAlloc( SystemHeap, 0, sizeof(ScanLineListBlock));
1988 WARN(region, "Can't alloc SLLB\n");
1991 (*SLLBlock)->next = tmpSLLBlock;
1992 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
1993 *SLLBlock = tmpSLLBlock;
1996 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
1998 pSLL->next = pPrevSLL->next;
1999 pSLL->edgelist = (EdgeTableEntry *)NULL;
2000 pPrevSLL->next = pSLL;
2002 pSLL->scanline = scanline;
2005 * now insert the edge in the right bucket
2007 prev = (EdgeTableEntry *)NULL;
2008 start = pSLL->edgelist;
2009 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2012 start = start->next;
2019 pSLL->edgelist = ETE;
2022 /***********************************************************************
2023 * REGION_CreateEdgeTable
2025 * This routine creates the edge table for
2026 * scan converting polygons.
2027 * The Edge Table (ET) looks like:
2031 * | ymax | ScanLineLists
2032 * |scanline|-->------------>-------------->...
2033 * -------- |scanline| |scanline|
2034 * |edgelist| |edgelist|
2035 * --------- ---------
2039 * list of ETEs list of ETEs
2041 * where ETE is an EdgeTableEntry data structure,
2042 * and there is one ScanLineList per scanline at
2043 * which an edge is initially entered.
2046 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2047 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2048 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2050 const POINT *top, *bottom;
2051 const POINT *PrevPt, *CurrPt, *EndPt;
2058 * initialize the Active Edge Table
2060 AET->next = (EdgeTableEntry *)NULL;
2061 AET->back = (EdgeTableEntry *)NULL;
2062 AET->nextWETE = (EdgeTableEntry *)NULL;
2063 AET->bres.minor_axis = SMALL_COORDINATE;
2066 * initialize the Edge Table.
2068 ET->scanlines.next = (ScanLineList *)NULL;
2069 ET->ymax = SMALL_COORDINATE;
2070 ET->ymin = LARGE_COORDINATE;
2071 pSLLBlock->next = (ScanLineListBlock *)NULL;
2074 for(poly = 0; poly < nbpolygons; poly++)
2076 count = Count[poly];
2084 * for each vertex in the array of points.
2085 * In this loop we are dealing with two vertices at
2086 * a time -- these make up one edge of the polygon.
2093 * find out which point is above and which is below.
2095 if (PrevPt->y > CurrPt->y)
2097 bottom = PrevPt, top = CurrPt;
2098 pETEs->ClockWise = 0;
2102 bottom = CurrPt, top = PrevPt;
2103 pETEs->ClockWise = 1;
2107 * don't add horizontal edges to the Edge table.
2109 if (bottom->y != top->y)
2111 pETEs->ymax = bottom->y-1;
2112 /* -1 so we don't get last scanline */
2115 * initialize integer edge algorithm
2117 dy = bottom->y - top->y;
2118 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2120 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2123 if (PrevPt->y > ET->ymax)
2124 ET->ymax = PrevPt->y;
2125 if (PrevPt->y < ET->ymin)
2126 ET->ymin = PrevPt->y;
2135 /***********************************************************************
2138 * This routine moves EdgeTableEntries from the
2139 * EdgeTable into the Active Edge Table,
2140 * leaving them sorted by smaller x coordinate.
2143 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2145 EdgeTableEntry *pPrevAET;
2146 EdgeTableEntry *tmp;
2152 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2161 ETEs->back = pPrevAET;
2162 pPrevAET->next = ETEs;
2169 /***********************************************************************
2170 * REGION_computeWAET
2172 * This routine links the AET by the
2173 * nextWETE (winding EdgeTableEntry) link for
2174 * use by the winding number rule. The final
2175 * Active Edge Table (AET) might look something
2179 * ---------- --------- ---------
2180 * |ymax | |ymax | |ymax |
2181 * | ... | |... | |... |
2182 * |next |->|next |->|next |->...
2183 * |nextWETE| |nextWETE| |nextWETE|
2184 * --------- --------- ^--------
2186 * V-------------------> V---> ...
2189 static void REGION_computeWAET(EdgeTableEntry *AET)
2191 register EdgeTableEntry *pWETE;
2192 register int inside = 1;
2193 register int isInside = 0;
2195 AET->nextWETE = (EdgeTableEntry *)NULL;
2205 if ((!inside && !isInside) ||
2206 ( inside && isInside))
2208 pWETE->nextWETE = AET;
2214 pWETE->nextWETE = (EdgeTableEntry *)NULL;
2217 /***********************************************************************
2218 * REGION_InsertionSort
2220 * Just a simple insertion sort using
2221 * pointers and back pointers to sort the Active
2225 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2227 EdgeTableEntry *pETEchase;
2228 EdgeTableEntry *pETEinsert;
2229 EdgeTableEntry *pETEchaseBackTMP;
2230 BOOL changed = FALSE;
2237 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2238 pETEchase = pETEchase->back;
2241 if (pETEchase != pETEinsert)
2243 pETEchaseBackTMP = pETEchase->back;
2244 pETEinsert->back->next = AET;
2246 AET->back = pETEinsert->back;
2247 pETEinsert->next = pETEchase;
2248 pETEchase->back->next = pETEinsert;
2249 pETEchase->back = pETEinsert;
2250 pETEinsert->back = pETEchaseBackTMP;
2257 /***********************************************************************
2258 * REGION_FreeStorage
2262 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2264 ScanLineListBlock *tmpSLLBlock;
2268 tmpSLLBlock = pSLLBlock->next;
2269 HeapFree( SystemHeap, 0, pSLLBlock );
2270 pSLLBlock = tmpSLLBlock;
2275 /***********************************************************************
2276 * REGION_PtsToRegion
2278 * Create an array of rectangles from a list of points.
2280 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2281 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2285 POINTBLOCK *CurPtBlock;
2290 extents = ®->extents;
2292 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2294 if (!(reg->rects = HeapReAlloc( SystemHeap, 0, reg->rects,
2295 sizeof(RECT) * numRects )))
2298 reg->size = numRects;
2299 CurPtBlock = FirstPtBlock;
2300 rects = reg->rects - 1;
2302 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2304 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2305 /* the loop uses 2 points per iteration */
2306 i = NUMPTSTOBUFFER >> 1;
2307 if (!numFullPtBlocks)
2308 i = iCurPtBlock >> 1;
2309 for (pts = CurPtBlock->pts; i--; pts += 2) {
2310 if (pts->x == pts[1].x)
2312 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2313 pts[1].x == rects->right &&
2314 (numRects == 1 || rects[-1].top != rects->top) &&
2315 (i && pts[2].y > pts[1].y)) {
2316 rects->bottom = pts[1].y + 1;
2321 rects->left = pts->x; rects->top = pts->y;
2322 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2323 if (rects->left < extents->left)
2324 extents->left = rects->left;
2325 if (rects->right > extents->right)
2326 extents->right = rects->right;
2328 CurPtBlock = CurPtBlock->next;
2332 extents->top = reg->rects->top;
2333 extents->bottom = rects->bottom;
2338 extents->bottom = 0;
2340 reg->numRects = numRects;
2345 /***********************************************************************
2346 * CreatePolyPolygonRgn32 (GDI32.57)
2348 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2349 INT nbpolygons, INT mode)
2354 register EdgeTableEntry *pAET; /* Active Edge Table */
2355 register INT y; /* current scanline */
2356 register int iPts = 0; /* number of pts in buffer */
2357 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2358 register ScanLineList *pSLL; /* current scanLineList */
2359 register POINT *pts; /* output buffer */
2360 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2361 EdgeTable ET; /* header node for ET */
2362 EdgeTableEntry AET; /* header node for AET */
2363 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2364 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2365 int fixWAET = FALSE;
2366 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2367 POINTBLOCK *tmpPtBlock;
2368 int numFullPtBlocks = 0;
2371 if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2373 obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
2376 /* special case a rectangle */
2378 if (((nbpolygons == 1) && ((*Count == 4) ||
2379 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2380 (((Pts[0].y == Pts[1].y) &&
2381 (Pts[1].x == Pts[2].x) &&
2382 (Pts[2].y == Pts[3].y) &&
2383 (Pts[3].x == Pts[0].x)) ||
2384 ((Pts[0].x == Pts[1].x) &&
2385 (Pts[1].y == Pts[2].y) &&
2386 (Pts[2].x == Pts[3].x) &&
2387 (Pts[3].y == Pts[0].y))))
2389 SetRectRgn( hrgn, MIN(Pts[0].x, Pts[2].x), MIN(Pts[0].y, Pts[2].y),
2390 MAX(Pts[0].x, Pts[2].x), MAX(Pts[0].y, Pts[2].y) );
2391 GDI_HEAP_UNLOCK( hrgn );
2395 for(poly = total = 0; poly < nbpolygons; poly++)
2396 total += Count[poly];
2397 if (! (pETEs = HeapAlloc( SystemHeap, 0, sizeof(EdgeTableEntry) * total )))
2399 REGION_DeleteObject( hrgn, obj );
2402 pts = FirstPtBlock.pts;
2403 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2404 pSLL = ET.scanlines.next;
2405 curPtBlock = &FirstPtBlock;
2407 if (mode != WINDING) {
2411 for (y = ET.ymin; y < ET.ymax; y++) {
2413 * Add a new edge to the active edge table when we
2414 * get to the next edge.
2416 if (pSLL != NULL && y == pSLL->scanline) {
2417 REGION_loadAET(&AET, pSLL->edgelist);
2424 * for each active edge
2427 pts->x = pAET->bres.minor_axis, pts->y = y;
2431 * send out the buffer
2433 if (iPts == NUMPTSTOBUFFER) {
2434 tmpPtBlock = HeapAlloc( SystemHeap, 0, sizeof(POINTBLOCK));
2436 WARN(region, "Can't alloc tPB\n");
2439 curPtBlock->next = tmpPtBlock;
2440 curPtBlock = tmpPtBlock;
2441 pts = curPtBlock->pts;
2445 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2447 REGION_InsertionSort(&AET);
2454 for (y = ET.ymin; y < ET.ymax; y++) {
2456 * Add a new edge to the active edge table when we
2457 * get to the next edge.
2459 if (pSLL != NULL && y == pSLL->scanline) {
2460 REGION_loadAET(&AET, pSLL->edgelist);
2461 REGION_computeWAET(&AET);
2469 * for each active edge
2473 * add to the buffer only those edges that
2474 * are in the Winding active edge table.
2476 if (pWETE == pAET) {
2477 pts->x = pAET->bres.minor_axis, pts->y = y;
2481 * send out the buffer
2483 if (iPts == NUMPTSTOBUFFER) {
2484 tmpPtBlock = HeapAlloc( SystemHeap, 0,
2485 sizeof(POINTBLOCK) );
2487 WARN(region, "Can't alloc tPB\n");
2490 curPtBlock->next = tmpPtBlock;
2491 curPtBlock = tmpPtBlock;
2492 pts = curPtBlock->pts;
2493 numFullPtBlocks++; iPts = 0;
2495 pWETE = pWETE->nextWETE;
2497 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2501 * recompute the winding active edge table if
2502 * we just resorted or have exited an edge.
2504 if (REGION_InsertionSort(&AET) || fixWAET) {
2505 REGION_computeWAET(&AET);
2510 REGION_FreeStorage(SLLBlock.next);
2511 REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2512 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2513 tmpPtBlock = curPtBlock->next;
2514 HeapFree( SystemHeap, 0, curPtBlock );
2515 curPtBlock = tmpPtBlock;
2517 HeapFree( SystemHeap, 0, pETEs );
2518 GDI_HEAP_UNLOCK( hrgn );
2523 /***********************************************************************
2524 * CreatePolygonRgn16 (GDI.63)
2526 HRGN16 WINAPI CreatePolygonRgn16( const POINT16 * points, INT16 count,
2529 return CreatePolyPolygonRgn16( points, &count, 1, mode );
2532 /***********************************************************************
2533 * CreatePolyPolygonRgn16 (GDI.451)
2535 HRGN16 WINAPI CreatePolyPolygonRgn16( const POINT16 *points,
2536 const INT16 *count, INT16 nbpolygons, INT16 mode )
2543 for (i = 0; i < nbpolygons; i++)
2545 points32 = HeapAlloc( SystemHeap, 0, npts * sizeof(POINT) );
2546 for (i = 0; i < npts; i++)
2547 CONV_POINT16TO32( &(points[i]), &(points32[i]) );
2549 count32 = HeapAlloc( SystemHeap, 0, nbpolygons * sizeof(INT) );
2550 for (i = 0; i < nbpolygons; i++)
2551 count32[i] = count[i];
2552 hrgn = CreatePolyPolygonRgn( points32, count32, nbpolygons, mode );
2553 HeapFree( SystemHeap, 0, count32 );
2554 HeapFree( SystemHeap, 0, points32 );
2558 /***********************************************************************
2559 * CreatePolygonRgn32 (GDI32.58)
2561 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2564 return CreatePolyPolygonRgn( points, &count, 1, mode );
2568 /***********************************************************************
2569 * GetRandomRgn [GDI32.215]
2572 * This function is UNDOCUMENTED, it isn't even in the header file.
2573 * I assume that it will return a HRGN32!??
2575 HRGN WINAPI GetRandomRgn(DWORD dwArg1, DWORD dwArg2, DWORD dwArg3)
2577 FIXME (region, "(0x%08lx 0x%08lx 0x%08lx): empty stub!\n",
2578 dwArg1, dwArg2, dwArg3);
2583 /***********************************************************************
2584 * REGION_CropAndOffsetRegion
2586 static BOOL REGION_CropAndOffsetRegion(const POINT* off, const RECT *rect, WINEREGION *rgnSrc, WINEREGION* rgnDst)
2588 if( IsRectEmpty(rect) || !EXTENTCHECK(rect, &rgnSrc->extents) )
2591 if( !rgnDst->rects )
2593 rgnDst->rects = HeapAlloc(SystemHeap, 0, sizeof( RECT ));
2600 TRACE(region,"cropped to empty!\n");
2601 EMPTY_REGION(rgnDst);
2603 else /* region box and clipping rect appear to intersect */
2606 INT i, j, clipa, clipb;
2607 INT left = rgnSrc->extents.right + off->x;
2608 INT right = rgnSrc->extents.left + off->x;
2610 for( clipa = 0; rgnSrc->rects[clipa].bottom <= rect->top; clipa++ )
2611 ; /* skip bands above the clipping rectangle */
2613 for( clipb = clipa; clipb < rgnSrc->numRects; clipb++ )
2614 if( rgnSrc->rects[clipb].top >= rect->bottom )
2615 break; /* and below it */
2617 /* clipa - index of the first rect in the first intersecting band
2618 * clipb - index of the last rect in the last intersecting band
2621 if((rgnDst != rgnSrc) && (rgnDst->size < (i = (clipb - clipa))))
2623 rgnDst->rects = HeapReAlloc( SystemHeap, 0,
2624 rgnDst->rects, i * sizeof(RECT));
2625 if( !rgnDst->rects ) return FALSE;
2629 if( TRACE_ON(region) )
2631 REGION_DumpRegion( rgnSrc );
2632 TRACE(region,"\tclipa = %i, clipb = %i\n", clipa, clipb );
2635 for( i = clipa, j = 0; i < clipb ; i++ )
2637 /* i - src index, j - dst index, j is always <= i for obvious reasons */
2639 lpr = rgnSrc->rects + i;
2640 if( lpr->left < rect->right && lpr->right > rect->left )
2642 rgnDst->rects[j].top = lpr->top + off->y;
2643 rgnDst->rects[j].bottom = lpr->bottom + off->y;
2644 rgnDst->rects[j].left = ((lpr->left > rect->left) ? lpr->left : rect->left) + off->x;
2645 rgnDst->rects[j].right = ((lpr->right < rect->right) ? lpr->right : rect->right) + off->x;
2647 if( rgnDst->rects[j].left < left ) left = rgnDst->rects[j].left;
2648 if( rgnDst->rects[j].right > right ) right = rgnDst->rects[j].right;
2654 if( j == 0 ) goto empty;
2656 rgnDst->extents.left = left;
2657 rgnDst->extents.right = right;
2659 left = rect->top + off->y;
2660 right = rect->bottom + off->y;
2662 rgnDst->numRects = j--;
2663 for( i = 0; i <= j; i++ ) /* fixup top band */
2664 if( rgnDst->rects[i].top < left )
2665 rgnDst->rects[i].top = left;
2669 for( i = j; i >= 0; i-- ) /* fixup bottom band */
2670 if( rgnDst->rects[i].bottom > right )
2671 rgnDst->rects[i].bottom = right;
2675 rgnDst->extents.top = rgnDst->rects[0].top;
2676 rgnDst->extents.bottom = rgnDst->rects[j].bottom;
2678 rgnDst->type = (j >= 1) ? COMPLEXREGION : SIMPLEREGION;
2680 if( TRACE_ON(region) )
2682 TRACE(region,"result:\n");
2683 REGION_DumpRegion( rgnDst );
2690 /***********************************************************************
2694 * hSrc: Region to crop and offset.
2695 * lpRect: Clipping rectangle.
2696 * lpPt: Points to offset the cropped region. Can be NULL.
2698 * hDst: Region to hold the result (if 0 a new region is created).
2699 * Allowed to be the same region as hSrc (in place, no extra memory needed).
2701 * Returns: hDst if success, 0 otherwise.
2703 HRGN REGION_CropRgn( HRGN hDst, HRGN hSrc, const RECT *lpRect, const POINT *lpPt )
2705 /* Optimization of the following generic code:
2707 HRGN h = CreateRectRgn( lpRect->left, lpRect->top, lpRect->right, lpRect->bottom );
2708 if( hDst == 0 ) hDst = h;
2709 CombineRgn( hDst, hSrc, h, RGN_AND );
2711 OffsetRgn( hDst, lpPt->x, lpPt->y );
2718 RGNOBJ *objSrc = (RGNOBJ *) GDI_HEAP_LOCK( hSrc );
2727 objDst = (RGNOBJ *) GDI_HEAP_LOCK( hDst );
2728 rgnDst = objDst->rgn;
2732 rgnDst = HeapAlloc(SystemHeap, 0, sizeof( WINEREGION ));
2735 rgnDst->size = rgnDst->numRects = 0;
2736 rgnDst->rects = NULL; /* back end will allocate exact number */
2742 POINT pt = { 0, 0 };
2744 if( !lpPt ) lpPt = &pt;
2746 TRACE(region, "src %p -> dst %p (%i,%i)-(%i,%i) by (%li,%li)\n", objSrc->rgn, rgnDst,
2747 lpRect->left, lpRect->top, lpRect->right, lpRect->bottom, lpPt->x, lpPt->y );
2749 if( REGION_CropAndOffsetRegion( lpPt, lpRect, objSrc->rgn, rgnDst ) == FALSE )
2751 if( hDst ) /* existing rgn */
2753 GDI_HEAP_UNLOCK(hDst);
2759 else if( hDst == 0 )
2761 if(!(hDst = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC )))
2765 HeapFree( SystemHeap, 0, rgnDst->rects );
2766 HeapFree( SystemHeap, 0, rgnDst );
2770 objDst = (RGNOBJ *) GDI_HEAP_LOCK( hDst );
2771 objDst->rgn = rgnDst;
2774 GDI_HEAP_UNLOCK(hDst);
2778 GDI_HEAP_UNLOCK(hSrc);