Various registry-related PostScript driver enhancements.
[wine.git] / objects / region.c
blob29a1092cbdd912479347bb02d5246fdacf597a98
1 /*
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
7 * 1999 Alex Korobka
9 */
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.
39 All Rights Reserved
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
55 SOFTWARE.
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
75 * to touch.
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...
84 #include <stdlib.h>
85 #include <string.h>
86 #include "windef.h"
87 #include "wingdi.h"
88 #include "debugtools.h"
89 #include "region.h"
90 #include "heap.h"
91 #include "gdi.h"
93 DEFAULT_DEBUG_CHANNEL(region);
95 /* 1 if two RECTs overlap.
96 * 0 if two RECTs do not overlap.
98 #define EXTENTCHECK(r1, r2) \
99 ((r1)->right > (r2)->left && \
100 (r1)->left < (r2)->right && \
101 (r1)->bottom > (r2)->top && \
102 (r1)->top < (r2)->bottom)
105 * Check to see if there is enough memory in the present region.
107 #define MEMCHECK(reg, rect, firstrect){\
108 if ((reg)->numRects >= ((reg)->size - 1)){\
109 (firstrect) = HeapReAlloc( GetProcessHeap(), 0, \
110 (firstrect), (2 * (sizeof(RECT)) * ((reg)->size)));\
111 if ((firstrect) == 0)\
112 return;\
113 (reg)->size *= 2;\
114 (rect) = &(firstrect)[(reg)->numRects];\
118 #define EMPTY_REGION(pReg) { \
119 (pReg)->numRects = 0; \
120 (pReg)->extents.left = (pReg)->extents.top = 0; \
121 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
122 (pReg)->type = NULLREGION; \
125 #define REGION_NOT_EMPTY(pReg) pReg->numRects
127 #define INRECT(r, x, y) \
128 ( ( ((r).right > x)) && \
129 ( ((r).left <= x)) && \
130 ( ((r).bottom > y)) && \
131 ( ((r).top <= y)) )
135 * number of points to buffer before sending them off
136 * to scanlines() : Must be an even number
138 #define NUMPTSTOBUFFER 200
141 * used to allocate buffers for points and link
142 * the buffers together
145 typedef struct _POINTBLOCK {
146 POINT pts[NUMPTSTOBUFFER];
147 struct _POINTBLOCK *next;
148 } POINTBLOCK;
153 * This file contains a few macros to help track
154 * the edge of a filled object. The object is assumed
155 * to be filled in scanline order, and thus the
156 * algorithm used is an extension of Bresenham's line
157 * drawing algorithm which assumes that y is always the
158 * major axis.
159 * Since these pieces of code are the same for any filled shape,
160 * it is more convenient to gather the library in one
161 * place, but since these pieces of code are also in
162 * the inner loops of output primitives, procedure call
163 * overhead is out of the question.
164 * See the author for a derivation if needed.
169 * In scan converting polygons, we want to choose those pixels
170 * which are inside the polygon. Thus, we add .5 to the starting
171 * x coordinate for both left and right edges. Now we choose the
172 * first pixel which is inside the pgon for the left edge and the
173 * first pixel which is outside the pgon for the right edge.
174 * Draw the left pixel, but not the right.
176 * How to add .5 to the starting x coordinate:
177 * If the edge is moving to the right, then subtract dy from the
178 * error term from the general form of the algorithm.
179 * If the edge is moving to the left, then add dy to the error term.
181 * The reason for the difference between edges moving to the left
182 * and edges moving to the right is simple: If an edge is moving
183 * to the right, then we want the algorithm to flip immediately.
184 * If it is moving to the left, then we don't want it to flip until
185 * we traverse an entire pixel.
187 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
188 int dx; /* local storage */ \
190 /* \
191 * if the edge is horizontal, then it is ignored \
192 * and assumed not to be processed. Otherwise, do this stuff. \
193 */ \
194 if ((dy) != 0) { \
195 xStart = (x1); \
196 dx = (x2) - xStart; \
197 if (dx < 0) { \
198 m = dx / (dy); \
199 m1 = m - 1; \
200 incr1 = -2 * dx + 2 * (dy) * m1; \
201 incr2 = -2 * dx + 2 * (dy) * m; \
202 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
203 } else { \
204 m = dx / (dy); \
205 m1 = m + 1; \
206 incr1 = 2 * dx - 2 * (dy) * m1; \
207 incr2 = 2 * dx - 2 * (dy) * m; \
208 d = -2 * m * (dy) + 2 * dx; \
213 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
214 if (m1 > 0) { \
215 if (d > 0) { \
216 minval += m1; \
217 d += incr1; \
219 else { \
220 minval += m; \
221 d += incr2; \
223 } else {\
224 if (d >= 0) { \
225 minval += m1; \
226 d += incr1; \
228 else { \
229 minval += m; \
230 d += incr2; \
236 * This structure contains all of the information needed
237 * to run the bresenham algorithm.
238 * The variables may be hardcoded into the declarations
239 * instead of using this structure to make use of
240 * register declarations.
242 typedef struct {
243 INT minor_axis; /* minor axis */
244 INT d; /* decision variable */
245 INT m, m1; /* slope and slope+1 */
246 INT incr1, incr2; /* error increments */
247 } BRESINFO;
250 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
251 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
252 bres.m, bres.m1, bres.incr1, bres.incr2)
254 #define BRESINCRPGONSTRUCT(bres) \
255 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
260 * These are the data structures needed to scan
261 * convert regions. Two different scan conversion
262 * methods are available -- the even-odd method, and
263 * the winding number method.
264 * The even-odd rule states that a point is inside
265 * the polygon if a ray drawn from that point in any
266 * direction will pass through an odd number of
267 * path segments.
268 * By the winding number rule, a point is decided
269 * to be inside the polygon if a ray drawn from that
270 * point in any direction passes through a different
271 * number of clockwise and counter-clockwise path
272 * segments.
274 * These data structures are adapted somewhat from
275 * the algorithm in (Foley/Van Dam) for scan converting
276 * polygons.
277 * The basic algorithm is to start at the top (smallest y)
278 * of the polygon, stepping down to the bottom of
279 * the polygon by incrementing the y coordinate. We
280 * keep a list of edges which the current scanline crosses,
281 * sorted by x. This list is called the Active Edge Table (AET)
282 * As we change the y-coordinate, we update each entry in
283 * in the active edge table to reflect the edges new xcoord.
284 * This list must be sorted at each scanline in case
285 * two edges intersect.
286 * We also keep a data structure known as the Edge Table (ET),
287 * which keeps track of all the edges which the current
288 * scanline has not yet reached. The ET is basically a
289 * list of ScanLineList structures containing a list of
290 * edges which are entered at a given scanline. There is one
291 * ScanLineList per scanline at which an edge is entered.
292 * When we enter a new edge, we move it from the ET to the AET.
294 * From the AET, we can implement the even-odd rule as in
295 * (Foley/Van Dam).
296 * The winding number rule is a little trickier. We also
297 * keep the EdgeTableEntries in the AET linked by the
298 * nextWETE (winding EdgeTableEntry) link. This allows
299 * the edges to be linked just as before for updating
300 * purposes, but only uses the edges linked by the nextWETE
301 * link as edges representing spans of the polygon to
302 * drawn (as with the even-odd rule).
306 * for the winding number rule
308 #define CLOCKWISE 1
309 #define COUNTERCLOCKWISE -1
311 typedef struct _EdgeTableEntry {
312 INT ymax; /* ycoord at which we exit this edge. */
313 BRESINFO bres; /* Bresenham info to run the edge */
314 struct _EdgeTableEntry *next; /* next in the list */
315 struct _EdgeTableEntry *back; /* for insertion sort */
316 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
317 int ClockWise; /* flag for winding number rule */
318 } EdgeTableEntry;
321 typedef struct _ScanLineList{
322 INT scanline; /* the scanline represented */
323 EdgeTableEntry *edgelist; /* header node */
324 struct _ScanLineList *next; /* next in the list */
325 } ScanLineList;
328 typedef struct {
329 INT ymax; /* ymax for the polygon */
330 INT ymin; /* ymin for the polygon */
331 ScanLineList scanlines; /* header node */
332 } EdgeTable;
336 * Here is a struct to help with storage allocation
337 * so we can allocate a big chunk at a time, and then take
338 * pieces from this heap when we need to.
340 #define SLLSPERBLOCK 25
342 typedef struct _ScanLineListBlock {
343 ScanLineList SLLs[SLLSPERBLOCK];
344 struct _ScanLineListBlock *next;
345 } ScanLineListBlock;
350 * a few macros for the inner loops of the fill code where
351 * performance considerations don't allow a procedure call.
353 * Evaluate the given edge at the given scanline.
354 * If the edge has expired, then we leave it and fix up
355 * the active edge table; otherwise, we increment the
356 * x value to be ready for the next scanline.
357 * The winding number rule is in effect, so we must notify
358 * the caller when the edge has been removed so he
359 * can reorder the Winding Active Edge Table.
361 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
362 if (pAET->ymax == y) { /* leaving this edge */ \
363 pPrevAET->next = pAET->next; \
364 pAET = pPrevAET->next; \
365 fixWAET = 1; \
366 if (pAET) \
367 pAET->back = pPrevAET; \
369 else { \
370 BRESINCRPGONSTRUCT(pAET->bres); \
371 pPrevAET = pAET; \
372 pAET = pAET->next; \
378 * Evaluate the given edge at the given scanline.
379 * If the edge has expired, then we leave it and fix up
380 * the active edge table; otherwise, we increment the
381 * x value to be ready for the next scanline.
382 * The even-odd rule is in effect.
384 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
385 if (pAET->ymax == y) { /* leaving this edge */ \
386 pPrevAET->next = pAET->next; \
387 pAET = pPrevAET->next; \
388 if (pAET) \
389 pAET->back = pPrevAET; \
391 else { \
392 BRESINCRPGONSTRUCT(pAET->bres); \
393 pPrevAET = pAET; \
394 pAET = pAET->next; \
398 typedef void (*voidProcp)();
400 /* Note the parameter order is different from the X11 equivalents */
402 static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
403 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
404 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
405 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
406 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
407 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
409 #define RGN_DEFAULT_RECTS 2
411 /***********************************************************************
412 * REGION_DumpRegion
413 * Outputs the contents of a WINEREGION
415 static void REGION_DumpRegion(WINEREGION *pReg)
417 RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
419 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg,
420 pReg->extents.left, pReg->extents.top,
421 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
422 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
423 TRACE("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
424 pRect->right, pRect->bottom);
425 return;
429 /***********************************************************************
430 * REGION_AllocWineRegion
431 * Create a new empty WINEREGION.
433 static WINEREGION *REGION_AllocWineRegion( INT n )
435 WINEREGION *pReg;
437 if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
439 if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
441 pReg->size = n;
442 EMPTY_REGION(pReg);
443 return pReg;
445 HeapFree(GetProcessHeap(), 0, pReg);
447 return NULL;
451 /***********************************************************************
452 * REGION_CreateRegion
453 * Create a new empty region.
455 static HRGN REGION_CreateRegion( INT n )
457 HRGN hrgn;
458 RGNOBJ *obj;
460 if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, &hrgn ))) return 0;
461 if(!(obj->rgn = REGION_AllocWineRegion(n))) {
462 GDI_FreeObject( hrgn, obj );
463 return 0;
465 GDI_ReleaseObj( hrgn );
466 return hrgn;
470 /***********************************************************************
471 * REGION_DestroyWineRegion
473 static void REGION_DestroyWineRegion( WINEREGION* pReg )
475 HeapFree( GetProcessHeap(), 0, pReg->rects );
476 HeapFree( GetProcessHeap(), 0, pReg );
477 return;
480 /***********************************************************************
481 * REGION_DeleteObject
483 BOOL REGION_DeleteObject( HRGN hrgn, RGNOBJ * obj )
485 TRACE(" %04x\n", hrgn );
487 REGION_DestroyWineRegion( obj->rgn );
488 return GDI_FreeObject( hrgn, obj );
491 /***********************************************************************
492 * OffsetRgn16 (GDI.101)
494 INT16 WINAPI OffsetRgn16( HRGN16 hrgn, INT16 x, INT16 y )
496 return OffsetRgn( hrgn, x, y );
499 /***********************************************************************
500 * OffsetRgn (GDI32.@)
502 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
504 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
505 INT ret;
507 TRACE("%04x %d,%d\n", hrgn, x, y);
509 if (!obj)
510 return ERROR;
512 if(x || y) {
513 int nbox = obj->rgn->numRects;
514 RECT *pbox = obj->rgn->rects;
516 if(nbox) {
517 while(nbox--) {
518 pbox->left += x;
519 pbox->right += x;
520 pbox->top += y;
521 pbox->bottom += y;
522 pbox++;
524 obj->rgn->extents.left += x;
525 obj->rgn->extents.right += x;
526 obj->rgn->extents.top += y;
527 obj->rgn->extents.bottom += y;
530 ret = obj->rgn->type;
531 GDI_ReleaseObj( hrgn );
532 return ret;
536 /***********************************************************************
537 * GetRgnBox16 (GDI.134)
539 INT16 WINAPI GetRgnBox16( HRGN16 hrgn, LPRECT16 rect )
541 RECT r;
542 INT16 ret = (INT16)GetRgnBox( hrgn, &r );
543 CONV_RECT32TO16( &r, rect );
544 return ret;
547 /***********************************************************************
548 * GetRgnBox (GDI32.@)
550 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
552 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
553 if (obj)
555 INT ret;
556 TRACE(" %04x\n", hrgn );
557 rect->left = obj->rgn->extents.left;
558 rect->top = obj->rgn->extents.top;
559 rect->right = obj->rgn->extents.right;
560 rect->bottom = obj->rgn->extents.bottom;
561 ret = obj->rgn->type;
562 GDI_ReleaseObj(hrgn);
563 return ret;
565 return ERROR;
569 /***********************************************************************
570 * CreateRectRgn16 (GDI.64)
572 * NOTE: Doesn't call CreateRectRgn because of differences in SetRectRgn16/32
574 HRGN16 WINAPI CreateRectRgn16(INT16 left, INT16 top, INT16 right, INT16 bottom)
576 HRGN16 hrgn;
578 if (!(hrgn = (HRGN16)REGION_CreateRegion(RGN_DEFAULT_RECTS)))
579 return 0;
580 TRACE("\n");
581 SetRectRgn16(hrgn, left, top, right, bottom);
582 return hrgn;
586 /***********************************************************************
587 * CreateRectRgn (GDI32.@)
589 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
591 HRGN hrgn;
593 /* Allocate 2 rects by default to reduce the number of reallocs */
595 if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
596 return 0;
597 TRACE("\n");
598 SetRectRgn(hrgn, left, top, right, bottom);
599 return hrgn;
602 /***********************************************************************
603 * CreateRectRgnIndirect16 (GDI.65)
605 HRGN16 WINAPI CreateRectRgnIndirect16( const RECT16* rect )
607 return CreateRectRgn16( rect->left, rect->top, rect->right, rect->bottom );
611 /***********************************************************************
612 * CreateRectRgnIndirect (GDI32.@)
614 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
616 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
620 /***********************************************************************
621 * SetRectRgn16 (GDI.172)
623 * NOTE: Win 3.1 sets region to empty if left > right
625 VOID WINAPI SetRectRgn16( HRGN16 hrgn, INT16 left, INT16 top,
626 INT16 right, INT16 bottom )
628 if(left < right)
629 SetRectRgn( hrgn, left, top, right, bottom );
630 else
631 SetRectRgn( hrgn, 0, 0, 0, 0 );
635 /***********************************************************************
636 * SetRectRgn (GDI32.@)
638 * Allows either or both left and top to be greater than right or bottom.
640 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
641 INT right, INT bottom )
643 RGNOBJ * obj;
645 TRACE(" %04x %d,%d-%d,%d\n",
646 hrgn, left, top, right, bottom );
648 if (!(obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
650 if (left > right) { INT tmp = left; left = right; right = tmp; }
651 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
653 if((left != right) && (top != bottom))
655 obj->rgn->rects->left = obj->rgn->extents.left = left;
656 obj->rgn->rects->top = obj->rgn->extents.top = top;
657 obj->rgn->rects->right = obj->rgn->extents.right = right;
658 obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
659 obj->rgn->numRects = 1;
660 obj->rgn->type = SIMPLEREGION;
662 else
663 EMPTY_REGION(obj->rgn);
665 GDI_ReleaseObj( hrgn );
666 return TRUE;
670 /***********************************************************************
671 * CreateRoundRectRgn16 (GDI.444)
673 * If either ellipse dimension is zero we call CreateRectRgn16 for its
674 * `special' behaviour. -ve ellipse dimensions can result in GPFs under win3.1
675 * we just let CreateRoundRectRgn convert them to +ve values.
678 HRGN16 WINAPI CreateRoundRectRgn16( INT16 left, INT16 top,
679 INT16 right, INT16 bottom,
680 INT16 ellipse_width, INT16 ellipse_height )
682 if( ellipse_width == 0 || ellipse_height == 0 )
683 return CreateRectRgn16( left, top, right, bottom );
684 else
685 return (HRGN16)CreateRoundRectRgn( left, top, right, bottom,
686 ellipse_width, ellipse_height );
689 /***********************************************************************
690 * CreateRoundRectRgn (GDI32.@)
692 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
693 INT right, INT bottom,
694 INT ellipse_width, INT ellipse_height )
696 RGNOBJ * obj;
697 HRGN hrgn;
698 int asq, bsq, d, xd, yd;
699 RECT rect;
701 /* Make the dimensions sensible */
703 if (left > right) { INT tmp = left; left = right; right = tmp; }
704 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
706 ellipse_width = abs(ellipse_width);
707 ellipse_height = abs(ellipse_height);
709 /* Check parameters */
711 if (ellipse_width > right-left) ellipse_width = right-left;
712 if (ellipse_height > bottom-top) ellipse_height = bottom-top;
714 /* Check if we can do a normal rectangle instead */
716 if ((ellipse_width < 2) || (ellipse_height < 2))
717 return CreateRectRgn( left, top, right, bottom );
719 /* Create region */
721 d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
722 if (!(hrgn = REGION_CreateRegion(d))) return 0;
723 if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
724 TRACE("(%d,%d-%d,%d %dx%d): ret=%04x\n",
725 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
727 /* Ellipse algorithm, based on an article by K. Porter */
728 /* in DDJ Graphics Programming Column, 8/89 */
730 asq = ellipse_width * ellipse_width / 4; /* a^2 */
731 bsq = ellipse_height * ellipse_height / 4; /* b^2 */
732 d = bsq - asq * ellipse_height / 2 + asq / 4; /* b^2 - a^2b + a^2/4 */
733 xd = 0;
734 yd = asq * ellipse_height; /* 2a^2b */
736 rect.left = left + ellipse_width / 2;
737 rect.right = right - ellipse_width / 2;
739 /* Loop to draw first half of quadrant */
741 while (xd < yd)
743 if (d > 0) /* if nearest pixel is toward the center */
745 /* move toward center */
746 rect.top = top++;
747 rect.bottom = rect.top + 1;
748 REGION_UnionRectWithRegion( &rect, obj->rgn );
749 rect.top = --bottom;
750 rect.bottom = rect.top + 1;
751 REGION_UnionRectWithRegion( &rect, obj->rgn );
752 yd -= 2*asq;
753 d -= yd;
755 rect.left--; /* next horiz point */
756 rect.right++;
757 xd += 2*bsq;
758 d += bsq + xd;
761 /* Loop to draw second half of quadrant */
763 d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
764 while (yd >= 0)
766 /* next vertical point */
767 rect.top = top++;
768 rect.bottom = rect.top + 1;
769 REGION_UnionRectWithRegion( &rect, obj->rgn );
770 rect.top = --bottom;
771 rect.bottom = rect.top + 1;
772 REGION_UnionRectWithRegion( &rect, obj->rgn );
773 if (d < 0) /* if nearest pixel is outside ellipse */
775 rect.left--; /* move away from center */
776 rect.right++;
777 xd += 2*bsq;
778 d += xd;
780 yd -= 2*asq;
781 d += asq - yd;
784 /* Add the inside rectangle */
786 if (top <= bottom)
788 rect.top = top;
789 rect.bottom = bottom;
790 REGION_UnionRectWithRegion( &rect, obj->rgn );
792 obj->rgn->type = SIMPLEREGION; /* FIXME? */
793 GDI_ReleaseObj( hrgn );
794 return hrgn;
798 /***********************************************************************
799 * CreateEllipticRgn16 (GDI.54)
801 HRGN16 WINAPI CreateEllipticRgn16( INT16 left, INT16 top,
802 INT16 right, INT16 bottom )
804 return (HRGN16)CreateRoundRectRgn( left, top, right, bottom,
805 right-left, bottom-top );
809 /***********************************************************************
810 * CreateEllipticRgn (GDI32.@)
812 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
813 INT right, INT bottom )
815 return CreateRoundRectRgn( left, top, right, bottom,
816 right-left, bottom-top );
820 /***********************************************************************
821 * CreateEllipticRgnIndirect16 (GDI.55)
823 HRGN16 WINAPI CreateEllipticRgnIndirect16( const RECT16 *rect )
825 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
826 rect->bottom, rect->right - rect->left,
827 rect->bottom - rect->top );
831 /***********************************************************************
832 * CreateEllipticRgnIndirect (GDI32.@)
834 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
836 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
837 rect->bottom, rect->right - rect->left,
838 rect->bottom - rect->top );
841 /***********************************************************************
842 * GetRegionData (GDI32.@)
844 * MSDN: GetRegionData, Return Values:
846 * "If the function succeeds and dwCount specifies an adequate number of bytes,
847 * the return value is always dwCount. If dwCount is too small or the function
848 * fails, the return value is 0. If lpRgnData is NULL, the return value is the
849 * required number of bytes.
851 * If the function fails, the return value is zero."
853 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
855 DWORD size;
856 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
858 TRACE(" %04x count = %ld, rgndata = %p\n",
859 hrgn, count, rgndata);
861 if(!obj) return 0;
863 size = obj->rgn->numRects * sizeof(RECT);
864 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
866 GDI_ReleaseObj( hrgn );
867 if (rgndata) /* buffer is too small, signal it by return 0 */
868 return 0;
869 else /* user requested buffer size with rgndata NULL */
870 return size + sizeof(RGNDATAHEADER);
873 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
874 rgndata->rdh.iType = RDH_RECTANGLES;
875 rgndata->rdh.nCount = obj->rgn->numRects;
876 rgndata->rdh.nRgnSize = size;
877 rgndata->rdh.rcBound.left = obj->rgn->extents.left;
878 rgndata->rdh.rcBound.top = obj->rgn->extents.top;
879 rgndata->rdh.rcBound.right = obj->rgn->extents.right;
880 rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
882 memcpy( rgndata->Buffer, obj->rgn->rects, size );
884 GDI_ReleaseObj( hrgn );
885 return size + sizeof(RGNDATAHEADER);
888 /***********************************************************************
889 * GetRegionData16 (GDI.607)
890 * FIXME: is LPRGNDATA the same in Win16 and Win32 ?
892 DWORD WINAPI GetRegionData16(HRGN16 hrgn, DWORD count, LPRGNDATA rgndata)
894 return GetRegionData((HRGN)hrgn, count, rgndata);
897 /***********************************************************************
898 * ExtCreateRegion (GDI32.@)
901 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
903 HRGN hrgn;
905 TRACE(" %p %ld %p = ", lpXform, dwCount, rgndata );
907 if( lpXform )
908 WARN("(Xform not implemented - ignored) ");
910 if( rgndata->rdh.iType != RDH_RECTANGLES )
912 /* FIXME: We can use CreatePolyPolygonRgn() here
913 * for trapezoidal data */
915 WARN("(Unsupported region data) ");
916 goto fail;
919 if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
921 RECT *pCurRect, *pEndRect;
922 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
924 if (obj) {
925 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
926 for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
927 REGION_UnionRectWithRegion( pCurRect, obj->rgn );
928 GDI_ReleaseObj( hrgn );
930 TRACE("%04x\n", hrgn );
931 return hrgn;
933 else ERR("Could not get pointer to newborn Region!");
935 fail:
936 WARN("Failed\n");
937 return 0;
940 /***********************************************************************
941 * PtInRegion16 (GDI.161)
943 BOOL16 WINAPI PtInRegion16( HRGN16 hrgn, INT16 x, INT16 y )
945 return PtInRegion( hrgn, x, y );
949 /***********************************************************************
950 * PtInRegion (GDI32.@)
952 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
954 RGNOBJ * obj;
955 BOOL ret = FALSE;
957 if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
959 int i;
961 if (obj->rgn->numRects > 0 && INRECT(obj->rgn->extents, x, y))
962 for (i = 0; i < obj->rgn->numRects; i++)
963 if (INRECT (obj->rgn->rects[i], x, y))
965 ret = TRUE;
966 break;
968 GDI_ReleaseObj( hrgn );
970 return ret;
974 /***********************************************************************
975 * RectInRegion16 (GDI.466)
977 BOOL16 WINAPI RectInRegion16( HRGN16 hrgn, const RECT16 *rect )
979 RECT r32;
981 CONV_RECT16TO32(rect, &r32);
982 return (BOOL16)RectInRegion(hrgn, &r32);
986 /***********************************************************************
987 * RectInRegion (GDI32.@)
989 * Returns TRUE if rect is at least partly inside hrgn
991 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
993 RGNOBJ * obj;
994 BOOL ret = FALSE;
996 if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
998 RECT *pCurRect, *pRectEnd;
1000 /* this is (just) a useful optimization */
1001 if ((obj->rgn->numRects > 0) && EXTENTCHECK(&obj->rgn->extents,
1002 rect))
1004 for (pCurRect = obj->rgn->rects, pRectEnd = pCurRect +
1005 obj->rgn->numRects; pCurRect < pRectEnd; pCurRect++)
1007 if (pCurRect->bottom <= rect->top)
1008 continue; /* not far enough down yet */
1010 if (pCurRect->top >= rect->bottom)
1011 break; /* too far down */
1013 if (pCurRect->right <= rect->left)
1014 continue; /* not far enough over yet */
1016 if (pCurRect->left >= rect->right) {
1017 continue;
1020 ret = TRUE;
1021 break;
1024 GDI_ReleaseObj(hrgn);
1026 return ret;
1029 /***********************************************************************
1030 * EqualRgn16 (GDI.72)
1032 BOOL16 WINAPI EqualRgn16( HRGN16 rgn1, HRGN16 rgn2 )
1034 return EqualRgn( rgn1, rgn2 );
1038 /***********************************************************************
1039 * EqualRgn (GDI32.@)
1041 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
1043 RGNOBJ *obj1, *obj2;
1044 BOOL ret = FALSE;
1046 if ((obj1 = (RGNOBJ *) GDI_GetObjPtr( hrgn1, REGION_MAGIC )))
1048 if ((obj2 = (RGNOBJ *) GDI_GetObjPtr( hrgn2, REGION_MAGIC )))
1050 int i;
1052 if ( obj1->rgn->numRects != obj2->rgn->numRects ) goto done;
1053 if ( obj1->rgn->numRects == 0 )
1055 ret = TRUE;
1056 goto done;
1059 if (obj1->rgn->extents.left != obj2->rgn->extents.left) goto done;
1060 if (obj1->rgn->extents.right != obj2->rgn->extents.right) goto done;
1061 if (obj1->rgn->extents.top != obj2->rgn->extents.top) goto done;
1062 if (obj1->rgn->extents.bottom != obj2->rgn->extents.bottom) goto done;
1063 for( i = 0; i < obj1->rgn->numRects; i++ )
1065 if (obj1->rgn->rects[i].left != obj2->rgn->rects[i].left) goto done;
1066 if (obj1->rgn->rects[i].right != obj2->rgn->rects[i].right) goto done;
1067 if (obj1->rgn->rects[i].top != obj2->rgn->rects[i].top) goto done;
1068 if (obj1->rgn->rects[i].bottom != obj2->rgn->rects[i].bottom) goto done;
1070 ret = TRUE;
1071 done:
1072 GDI_ReleaseObj(hrgn2);
1074 GDI_ReleaseObj(hrgn1);
1076 return ret;
1078 /***********************************************************************
1079 * REGION_UnionRectWithRegion
1080 * Adds a rectangle to a WINEREGION
1081 * See below for REGION_UnionRectWithRgn
1083 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1085 WINEREGION region;
1087 region.rects = &region.extents;
1088 region.numRects = 1;
1089 region.size = 1;
1090 region.type = SIMPLEREGION;
1091 region.extents = *rect;
1092 REGION_UnionRegion(rgn, rgn, &region);
1093 return;
1096 /***********************************************************************
1097 * REGION_UnionRectWithRgn
1098 * Adds a rectangle to a HRGN
1099 * A helper used by scroll.c
1101 BOOL REGION_UnionRectWithRgn( HRGN hrgn, const RECT *lpRect )
1103 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
1105 if(!obj) return FALSE;
1106 REGION_UnionRectWithRegion( lpRect, obj->rgn );
1107 GDI_ReleaseObj(hrgn);
1108 return TRUE;
1111 /***********************************************************************
1112 * REGION_CreateFrameRgn
1114 * Create a region that is a frame around another region.
1115 * Expand all rectangles by +/- x and y, then subtract original region.
1117 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1119 BOOL bRet;
1120 RGNOBJ *srcObj = (RGNOBJ*) GDI_GetObjPtr( hSrc, REGION_MAGIC );
1122 if (!srcObj) return FALSE;
1123 if (srcObj->rgn->numRects != 0)
1125 RGNOBJ* destObj = (RGNOBJ*) GDI_GetObjPtr( hDest, REGION_MAGIC );
1126 RECT *pRect, *pEndRect;
1127 RECT tempRect;
1129 EMPTY_REGION( destObj->rgn );
1131 pEndRect = srcObj->rgn->rects + srcObj->rgn->numRects;
1132 for(pRect = srcObj->rgn->rects; pRect < pEndRect; pRect++)
1134 tempRect.left = pRect->left - x;
1135 tempRect.top = pRect->top - y;
1136 tempRect.right = pRect->right + x;
1137 tempRect.bottom = pRect->bottom + y;
1138 REGION_UnionRectWithRegion( &tempRect, destObj->rgn );
1140 REGION_SubtractRegion( destObj->rgn, destObj->rgn, srcObj->rgn );
1141 GDI_ReleaseObj ( hDest );
1142 bRet = TRUE;
1144 else
1145 bRet = FALSE;
1146 GDI_ReleaseObj( hSrc );
1147 return bRet;
1150 /***********************************************************************
1151 * REGION_LPTODP
1153 * Convert region to device co-ords for the supplied dc.
1155 BOOL REGION_LPTODP( HDC hdc, HRGN hDest, HRGN hSrc )
1157 RECT *pCurRect, *pEndRect;
1158 RGNOBJ *srcObj, *destObj;
1159 DC * dc = DC_GetDCPtr( hdc );
1160 RECT tmpRect;
1161 BOOL ret = FALSE;
1163 TRACE(" hdc=%04x dest=%04x src=%04x\n",
1164 hdc, hDest, hSrc) ;
1165 if (!dc) return ret;
1167 if (dc->MapMode == MM_TEXT) /* Requires only a translation */
1169 if( CombineRgn( hDest, hSrc, 0, RGN_COPY ) == ERROR ) goto done;
1170 OffsetRgn( hDest, dc->vportOrgX - dc->wndOrgX,
1171 dc->vportOrgY - dc->wndOrgY );
1172 ret = TRUE;
1173 goto done;
1176 if(!( srcObj = (RGNOBJ *) GDI_GetObjPtr( hSrc, REGION_MAGIC) ))
1177 goto done;
1178 if(!( destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC) ))
1180 GDI_ReleaseObj( hSrc );
1181 goto done;
1183 EMPTY_REGION( destObj->rgn );
1185 pEndRect = srcObj->rgn->rects + srcObj->rgn->numRects;
1186 for(pCurRect = srcObj->rgn->rects; pCurRect < pEndRect; pCurRect++)
1188 tmpRect = *pCurRect;
1189 tmpRect.left = XLPTODP( dc, tmpRect.left );
1190 tmpRect.top = YLPTODP( dc, tmpRect.top );
1191 tmpRect.right = XLPTODP( dc, tmpRect.right );
1192 tmpRect.bottom = YLPTODP( dc, tmpRect.bottom );
1194 if (tmpRect.left > tmpRect.right)
1195 { INT tmp = tmpRect.left; tmpRect.left = tmpRect.right; tmpRect.right = tmp; }
1196 if (tmpRect.top > tmpRect.bottom)
1197 { INT tmp = tmpRect.top; tmpRect.top = tmpRect.bottom; tmpRect.bottom = tmp; }
1199 REGION_UnionRectWithRegion( &tmpRect, destObj->rgn );
1201 ret = TRUE;
1203 GDI_ReleaseObj( hDest );
1204 GDI_ReleaseObj( hSrc );
1205 done:
1206 GDI_ReleaseObj( hdc );
1207 return ret;
1210 /***********************************************************************
1211 * CombineRgn16 (GDI.47)
1213 INT16 WINAPI CombineRgn16(HRGN16 hDest, HRGN16 hSrc1, HRGN16 hSrc2, INT16 mode)
1215 return (INT16)CombineRgn( hDest, hSrc1, hSrc2, mode );
1219 /***********************************************************************
1220 * CombineRgn (GDI32.@)
1222 * Note: The behavior is correct even if src and dest regions are the same.
1224 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1226 RGNOBJ *destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC);
1227 INT result = ERROR;
1229 TRACE(" %04x,%04x -> %04x mode=%x\n",
1230 hSrc1, hSrc2, hDest, mode );
1231 if (destObj)
1233 RGNOBJ *src1Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc1, REGION_MAGIC);
1235 if (src1Obj)
1237 TRACE("dump:\n");
1238 if(TRACE_ON(region))
1239 REGION_DumpRegion(src1Obj->rgn);
1240 if (mode == RGN_COPY)
1242 REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
1243 result = destObj->rgn->type;
1245 else
1247 RGNOBJ *src2Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc2, REGION_MAGIC);
1249 if (src2Obj)
1251 TRACE("dump:\n");
1252 if(TRACE_ON(region))
1253 REGION_DumpRegion(src2Obj->rgn);
1254 switch (mode)
1256 case RGN_AND:
1257 REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
1258 break;
1259 case RGN_OR:
1260 REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1261 break;
1262 case RGN_XOR:
1263 REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1264 break;
1265 case RGN_DIFF:
1266 REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1267 break;
1269 result = destObj->rgn->type;
1270 GDI_ReleaseObj( hSrc2 );
1273 GDI_ReleaseObj( hSrc1 );
1275 TRACE("dump:\n");
1276 if(TRACE_ON(region))
1277 REGION_DumpRegion(destObj->rgn);
1279 GDI_ReleaseObj( hDest );
1280 } else {
1281 ERR("Invalid rgn=%04x\n", hDest);
1283 return result;
1286 /***********************************************************************
1287 * REGION_SetExtents
1288 * Re-calculate the extents of a region
1290 static void REGION_SetExtents (WINEREGION *pReg)
1292 RECT *pRect, *pRectEnd, *pExtents;
1294 if (pReg->numRects == 0)
1296 pReg->extents.left = 0;
1297 pReg->extents.top = 0;
1298 pReg->extents.right = 0;
1299 pReg->extents.bottom = 0;
1300 return;
1303 pExtents = &pReg->extents;
1304 pRect = pReg->rects;
1305 pRectEnd = &pRect[pReg->numRects - 1];
1308 * Since pRect is the first rectangle in the region, it must have the
1309 * smallest top and since pRectEnd is the last rectangle in the region,
1310 * it must have the largest bottom, because of banding. Initialize left and
1311 * right from pRect and pRectEnd, resp., as good things to initialize them
1312 * to...
1314 pExtents->left = pRect->left;
1315 pExtents->top = pRect->top;
1316 pExtents->right = pRectEnd->right;
1317 pExtents->bottom = pRectEnd->bottom;
1319 while (pRect <= pRectEnd)
1321 if (pRect->left < pExtents->left)
1322 pExtents->left = pRect->left;
1323 if (pRect->right > pExtents->right)
1324 pExtents->right = pRect->right;
1325 pRect++;
1329 /***********************************************************************
1330 * REGION_CopyRegion
1332 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1334 if (dst != src) /* don't want to copy to itself */
1336 if (dst->size < src->numRects)
1338 if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1339 src->numRects * sizeof(RECT) )))
1340 return;
1341 dst->size = src->numRects;
1343 dst->numRects = src->numRects;
1344 dst->extents.left = src->extents.left;
1345 dst->extents.top = src->extents.top;
1346 dst->extents.right = src->extents.right;
1347 dst->extents.bottom = src->extents.bottom;
1348 dst->type = src->type;
1350 memcpy((char *) dst->rects, (char *) src->rects,
1351 (int) (src->numRects * sizeof(RECT)));
1353 return;
1356 /***********************************************************************
1357 * REGION_Coalesce
1359 * Attempt to merge the rects in the current band with those in the
1360 * previous one. Used only by REGION_RegionOp.
1362 * Results:
1363 * The new index for the previous band.
1365 * Side Effects:
1366 * If coalescing takes place:
1367 * - rectangles in the previous band will have their bottom fields
1368 * altered.
1369 * - pReg->numRects will be decreased.
1372 static INT REGION_Coalesce (
1373 WINEREGION *pReg, /* Region to coalesce */
1374 INT prevStart, /* Index of start of previous band */
1375 INT curStart /* Index of start of current band */
1377 RECT *pPrevRect; /* Current rect in previous band */
1378 RECT *pCurRect; /* Current rect in current band */
1379 RECT *pRegEnd; /* End of region */
1380 INT curNumRects; /* Number of rectangles in current band */
1381 INT prevNumRects; /* Number of rectangles in previous band */
1382 INT bandtop; /* top coordinate for current band */
1384 pRegEnd = &pReg->rects[pReg->numRects];
1386 pPrevRect = &pReg->rects[prevStart];
1387 prevNumRects = curStart - prevStart;
1390 * Figure out how many rectangles are in the current band. Have to do
1391 * this because multiple bands could have been added in REGION_RegionOp
1392 * at the end when one region has been exhausted.
1394 pCurRect = &pReg->rects[curStart];
1395 bandtop = pCurRect->top;
1396 for (curNumRects = 0;
1397 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1398 curNumRects++)
1400 pCurRect++;
1403 if (pCurRect != pRegEnd)
1406 * If more than one band was added, we have to find the start
1407 * of the last band added so the next coalescing job can start
1408 * at the right place... (given when multiple bands are added,
1409 * this may be pointless -- see above).
1411 pRegEnd--;
1412 while (pRegEnd[-1].top == pRegEnd->top)
1414 pRegEnd--;
1416 curStart = pRegEnd - pReg->rects;
1417 pRegEnd = pReg->rects + pReg->numRects;
1420 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1421 pCurRect -= curNumRects;
1423 * The bands may only be coalesced if the bottom of the previous
1424 * matches the top scanline of the current.
1426 if (pPrevRect->bottom == pCurRect->top)
1429 * Make sure the bands have rects in the same places. This
1430 * assumes that rects have been added in such a way that they
1431 * cover the most area possible. I.e. two rects in a band must
1432 * have some horizontal space between them.
1436 if ((pPrevRect->left != pCurRect->left) ||
1437 (pPrevRect->right != pCurRect->right))
1440 * The bands don't line up so they can't be coalesced.
1442 return (curStart);
1444 pPrevRect++;
1445 pCurRect++;
1446 prevNumRects -= 1;
1447 } while (prevNumRects != 0);
1449 pReg->numRects -= curNumRects;
1450 pCurRect -= curNumRects;
1451 pPrevRect -= curNumRects;
1454 * The bands may be merged, so set the bottom of each rect
1455 * in the previous band to that of the corresponding rect in
1456 * the current band.
1460 pPrevRect->bottom = pCurRect->bottom;
1461 pPrevRect++;
1462 pCurRect++;
1463 curNumRects -= 1;
1464 } while (curNumRects != 0);
1467 * If only one band was added to the region, we have to backup
1468 * curStart to the start of the previous band.
1470 * If more than one band was added to the region, copy the
1471 * other bands down. The assumption here is that the other bands
1472 * came from the same region as the current one and no further
1473 * coalescing can be done on them since it's all been done
1474 * already... curStart is already in the right place.
1476 if (pCurRect == pRegEnd)
1478 curStart = prevStart;
1480 else
1484 *pPrevRect++ = *pCurRect++;
1485 } while (pCurRect != pRegEnd);
1490 return (curStart);
1493 /***********************************************************************
1494 * REGION_RegionOp
1496 * Apply an operation to two regions. Called by REGION_Union,
1497 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1499 * Results:
1500 * None.
1502 * Side Effects:
1503 * The new region is overwritten.
1505 * Notes:
1506 * The idea behind this function is to view the two regions as sets.
1507 * Together they cover a rectangle of area that this function divides
1508 * into horizontal bands where points are covered only by one region
1509 * or by both. For the first case, the nonOverlapFunc is called with
1510 * each the band and the band's upper and lower extents. For the
1511 * second, the overlapFunc is called to process the entire band. It
1512 * is responsible for clipping the rectangles in the band, though
1513 * this function provides the boundaries.
1514 * At the end of each band, the new region is coalesced, if possible,
1515 * to reduce the number of rectangles in the region.
1518 static void REGION_RegionOp(
1519 WINEREGION *newReg, /* Place to store result */
1520 WINEREGION *reg1, /* First region in operation */
1521 WINEREGION *reg2, /* 2nd region in operation */
1522 void (*overlapFunc)(), /* Function to call for over-lapping bands */
1523 void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
1524 void (*nonOverlap2Func)() /* Function to call for non-overlapping bands in region 2 */
1526 RECT *r1; /* Pointer into first region */
1527 RECT *r2; /* Pointer into 2d region */
1528 RECT *r1End; /* End of 1st region */
1529 RECT *r2End; /* End of 2d region */
1530 INT ybot; /* Bottom of intersection */
1531 INT ytop; /* Top of intersection */
1532 RECT *oldRects; /* Old rects for newReg */
1533 INT prevBand; /* Index of start of
1534 * previous band in newReg */
1535 INT curBand; /* Index of start of current
1536 * band in newReg */
1537 RECT *r1BandEnd; /* End of current band in r1 */
1538 RECT *r2BandEnd; /* End of current band in r2 */
1539 INT top; /* Top of non-overlapping band */
1540 INT bot; /* Bottom of non-overlapping band */
1543 * Initialization:
1544 * set r1, r2, r1End and r2End appropriately, preserve the important
1545 * parts of the destination region until the end in case it's one of
1546 * the two source regions, then mark the "new" region empty, allocating
1547 * another array of rectangles for it to use.
1549 r1 = reg1->rects;
1550 r2 = reg2->rects;
1551 r1End = r1 + reg1->numRects;
1552 r2End = r2 + reg2->numRects;
1556 * newReg may be one of the src regions so we can't empty it. We keep a
1557 * note of its rects pointer (so that we can free them later), preserve its
1558 * extents and simply set numRects to zero.
1561 oldRects = newReg->rects;
1562 newReg->numRects = 0;
1565 * Allocate a reasonable number of rectangles for the new region. The idea
1566 * is to allocate enough so the individual functions don't need to
1567 * reallocate and copy the array, which is time consuming, yet we don't
1568 * have to worry about using too much memory. I hope to be able to
1569 * nuke the Xrealloc() at the end of this function eventually.
1571 newReg->size = max(reg1->numRects,reg2->numRects) * 2;
1573 if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1574 sizeof(RECT) * newReg->size )))
1576 newReg->size = 0;
1577 return;
1581 * Initialize ybot and ytop.
1582 * In the upcoming loop, ybot and ytop serve different functions depending
1583 * on whether the band being handled is an overlapping or non-overlapping
1584 * band.
1585 * In the case of a non-overlapping band (only one of the regions
1586 * has points in the band), ybot is the bottom of the most recent
1587 * intersection and thus clips the top of the rectangles in that band.
1588 * ytop is the top of the next intersection between the two regions and
1589 * serves to clip the bottom of the rectangles in the current band.
1590 * For an overlapping band (where the two regions intersect), ytop clips
1591 * the top of the rectangles of both regions and ybot clips the bottoms.
1593 if (reg1->extents.top < reg2->extents.top)
1594 ybot = reg1->extents.top;
1595 else
1596 ybot = reg2->extents.top;
1599 * prevBand serves to mark the start of the previous band so rectangles
1600 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1601 * In the beginning, there is no previous band, so prevBand == curBand
1602 * (curBand is set later on, of course, but the first band will always
1603 * start at index 0). prevBand and curBand must be indices because of
1604 * the possible expansion, and resultant moving, of the new region's
1605 * array of rectangles.
1607 prevBand = 0;
1611 curBand = newReg->numRects;
1614 * This algorithm proceeds one source-band (as opposed to a
1615 * destination band, which is determined by where the two regions
1616 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1617 * rectangle after the last one in the current band for their
1618 * respective regions.
1620 r1BandEnd = r1;
1621 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1623 r1BandEnd++;
1626 r2BandEnd = r2;
1627 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1629 r2BandEnd++;
1633 * First handle the band that doesn't intersect, if any.
1635 * Note that attention is restricted to one band in the
1636 * non-intersecting region at once, so if a region has n
1637 * bands between the current position and the next place it overlaps
1638 * the other, this entire loop will be passed through n times.
1640 if (r1->top < r2->top)
1642 top = max(r1->top,ybot);
1643 bot = min(r1->bottom,r2->top);
1645 if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
1647 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1650 ytop = r2->top;
1652 else if (r2->top < r1->top)
1654 top = max(r2->top,ybot);
1655 bot = min(r2->bottom,r1->top);
1657 if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
1659 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1662 ytop = r1->top;
1664 else
1666 ytop = r1->top;
1670 * If any rectangles got added to the region, try and coalesce them
1671 * with rectangles from the previous band. Note we could just do
1672 * this test in miCoalesce, but some machines incur a not
1673 * inconsiderable cost for function calls, so...
1675 if (newReg->numRects != curBand)
1677 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1681 * Now see if we've hit an intersecting band. The two bands only
1682 * intersect if ybot > ytop
1684 ybot = min(r1->bottom, r2->bottom);
1685 curBand = newReg->numRects;
1686 if (ybot > ytop)
1688 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1692 if (newReg->numRects != curBand)
1694 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1698 * If we've finished with a band (bottom == ybot) we skip forward
1699 * in the region to the next band.
1701 if (r1->bottom == ybot)
1703 r1 = r1BandEnd;
1705 if (r2->bottom == ybot)
1707 r2 = r2BandEnd;
1709 } while ((r1 != r1End) && (r2 != r2End));
1712 * Deal with whichever region still has rectangles left.
1714 curBand = newReg->numRects;
1715 if (r1 != r1End)
1717 if (nonOverlap1Func != (void (*)())NULL)
1721 r1BandEnd = r1;
1722 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1724 r1BandEnd++;
1726 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1727 max(r1->top,ybot), r1->bottom);
1728 r1 = r1BandEnd;
1729 } while (r1 != r1End);
1732 else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
1736 r2BandEnd = r2;
1737 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1739 r2BandEnd++;
1741 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1742 max(r2->top,ybot), r2->bottom);
1743 r2 = r2BandEnd;
1744 } while (r2 != r2End);
1747 if (newReg->numRects != curBand)
1749 (void) REGION_Coalesce (newReg, prevBand, curBand);
1753 * A bit of cleanup. To keep regions from growing without bound,
1754 * we shrink the array of rectangles to match the new number of
1755 * rectangles in the region. This never goes to 0, however...
1757 * Only do this stuff if the number of rectangles allocated is more than
1758 * twice the number of rectangles in the region (a simple optimization...).
1760 if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1762 if (REGION_NOT_EMPTY(newReg))
1764 RECT *prev_rects = newReg->rects;
1765 newReg->size = newReg->numRects;
1766 newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1767 sizeof(RECT) * newReg->size );
1768 if (! newReg->rects)
1769 newReg->rects = prev_rects;
1771 else
1774 * No point in doing the extra work involved in an Xrealloc if
1775 * the region is empty
1777 newReg->size = 1;
1778 HeapFree( GetProcessHeap(), 0, newReg->rects );
1779 newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
1782 HeapFree( GetProcessHeap(), 0, oldRects );
1783 return;
1786 /***********************************************************************
1787 * Region Intersection
1788 ***********************************************************************/
1791 /***********************************************************************
1792 * REGION_IntersectO
1794 * Handle an overlapping band for REGION_Intersect.
1796 * Results:
1797 * None.
1799 * Side Effects:
1800 * Rectangles may be added to the region.
1803 static void REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1804 RECT *r2, RECT *r2End, INT top, INT bottom)
1807 INT left, right;
1808 RECT *pNextRect;
1810 pNextRect = &pReg->rects[pReg->numRects];
1812 while ((r1 != r1End) && (r2 != r2End))
1814 left = max(r1->left, r2->left);
1815 right = min(r1->right, r2->right);
1818 * If there's any overlap between the two rectangles, add that
1819 * overlap to the new region.
1820 * There's no need to check for subsumption because the only way
1821 * such a need could arise is if some region has two rectangles
1822 * right next to each other. Since that should never happen...
1824 if (left < right)
1826 MEMCHECK(pReg, pNextRect, pReg->rects);
1827 pNextRect->left = left;
1828 pNextRect->top = top;
1829 pNextRect->right = right;
1830 pNextRect->bottom = bottom;
1831 pReg->numRects += 1;
1832 pNextRect++;
1836 * Need to advance the pointers. Shift the one that extends
1837 * to the right the least, since the other still has a chance to
1838 * overlap with that region's next rectangle, if you see what I mean.
1840 if (r1->right < r2->right)
1842 r1++;
1844 else if (r2->right < r1->right)
1846 r2++;
1848 else
1850 r1++;
1851 r2++;
1854 return;
1857 /***********************************************************************
1858 * REGION_IntersectRegion
1860 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1861 WINEREGION *reg2)
1863 /* check for trivial reject */
1864 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1865 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
1866 newReg->numRects = 0;
1867 else
1868 REGION_RegionOp (newReg, reg1, reg2,
1869 (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
1872 * Can't alter newReg's extents before we call miRegionOp because
1873 * it might be one of the source regions and miRegionOp depends
1874 * on the extents of those regions being the same. Besides, this
1875 * way there's no checking against rectangles that will be nuked
1876 * due to coalescing, so we have to examine fewer rectangles.
1878 REGION_SetExtents(newReg);
1879 newReg->type = (newReg->numRects) ?
1880 ((newReg->numRects > 1) ? COMPLEXREGION : SIMPLEREGION)
1881 : NULLREGION ;
1882 return;
1885 /***********************************************************************
1886 * Region Union
1887 ***********************************************************************/
1889 /***********************************************************************
1890 * REGION_UnionNonO
1892 * Handle a non-overlapping band for the union operation. Just
1893 * Adds the rectangles into the region. Doesn't have to check for
1894 * subsumption or anything.
1896 * Results:
1897 * None.
1899 * Side Effects:
1900 * pReg->numRects is incremented and the final rectangles overwritten
1901 * with the rectangles we're passed.
1904 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1905 INT top, INT bottom)
1907 RECT *pNextRect;
1909 pNextRect = &pReg->rects[pReg->numRects];
1911 while (r != rEnd)
1913 MEMCHECK(pReg, pNextRect, pReg->rects);
1914 pNextRect->left = r->left;
1915 pNextRect->top = top;
1916 pNextRect->right = r->right;
1917 pNextRect->bottom = bottom;
1918 pReg->numRects += 1;
1919 pNextRect++;
1920 r++;
1922 return;
1925 /***********************************************************************
1926 * REGION_UnionO
1928 * Handle an overlapping band for the union operation. Picks the
1929 * left-most rectangle each time and merges it into the region.
1931 * Results:
1932 * None.
1934 * Side Effects:
1935 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1936 * be changed.
1939 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1940 RECT *r2, RECT *r2End, INT top, INT bottom)
1942 RECT *pNextRect;
1944 pNextRect = &pReg->rects[pReg->numRects];
1946 #define MERGERECT(r) \
1947 if ((pReg->numRects != 0) && \
1948 (pNextRect[-1].top == top) && \
1949 (pNextRect[-1].bottom == bottom) && \
1950 (pNextRect[-1].right >= r->left)) \
1952 if (pNextRect[-1].right < r->right) \
1954 pNextRect[-1].right = r->right; \
1957 else \
1959 MEMCHECK(pReg, pNextRect, pReg->rects); \
1960 pNextRect->top = top; \
1961 pNextRect->bottom = bottom; \
1962 pNextRect->left = r->left; \
1963 pNextRect->right = r->right; \
1964 pReg->numRects += 1; \
1965 pNextRect += 1; \
1967 r++;
1969 while ((r1 != r1End) && (r2 != r2End))
1971 if (r1->left < r2->left)
1973 MERGERECT(r1);
1975 else
1977 MERGERECT(r2);
1981 if (r1 != r1End)
1985 MERGERECT(r1);
1986 } while (r1 != r1End);
1988 else while (r2 != r2End)
1990 MERGERECT(r2);
1992 return;
1995 /***********************************************************************
1996 * REGION_UnionRegion
1998 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
1999 WINEREGION *reg2)
2001 /* checks all the simple cases */
2004 * Region 1 and 2 are the same or region 1 is empty
2006 if ( (reg1 == reg2) || (!(reg1->numRects)) )
2008 if (newReg != reg2)
2009 REGION_CopyRegion(newReg, reg2);
2010 return;
2014 * if nothing to union (region 2 empty)
2016 if (!(reg2->numRects))
2018 if (newReg != reg1)
2019 REGION_CopyRegion(newReg, reg1);
2020 return;
2024 * Region 1 completely subsumes region 2
2026 if ((reg1->numRects == 1) &&
2027 (reg1->extents.left <= reg2->extents.left) &&
2028 (reg1->extents.top <= reg2->extents.top) &&
2029 (reg1->extents.right >= reg2->extents.right) &&
2030 (reg1->extents.bottom >= reg2->extents.bottom))
2032 if (newReg != reg1)
2033 REGION_CopyRegion(newReg, reg1);
2034 return;
2038 * Region 2 completely subsumes region 1
2040 if ((reg2->numRects == 1) &&
2041 (reg2->extents.left <= reg1->extents.left) &&
2042 (reg2->extents.top <= reg1->extents.top) &&
2043 (reg2->extents.right >= reg1->extents.right) &&
2044 (reg2->extents.bottom >= reg1->extents.bottom))
2046 if (newReg != reg2)
2047 REGION_CopyRegion(newReg, reg2);
2048 return;
2051 REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
2052 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
2054 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
2055 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
2056 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
2057 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
2058 newReg->type = (newReg->numRects) ?
2059 ((newReg->numRects > 1) ? COMPLEXREGION : SIMPLEREGION)
2060 : NULLREGION ;
2061 return;
2064 /***********************************************************************
2065 * Region Subtraction
2066 ***********************************************************************/
2068 /***********************************************************************
2069 * REGION_SubtractNonO1
2071 * Deal with non-overlapping band for subtraction. Any parts from
2072 * region 2 we discard. Anything from region 1 we add to the region.
2074 * Results:
2075 * None.
2077 * Side Effects:
2078 * pReg may be affected.
2081 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
2082 INT top, INT bottom)
2084 RECT *pNextRect;
2086 pNextRect = &pReg->rects[pReg->numRects];
2088 while (r != rEnd)
2090 MEMCHECK(pReg, pNextRect, pReg->rects);
2091 pNextRect->left = r->left;
2092 pNextRect->top = top;
2093 pNextRect->right = r->right;
2094 pNextRect->bottom = bottom;
2095 pReg->numRects += 1;
2096 pNextRect++;
2097 r++;
2099 return;
2103 /***********************************************************************
2104 * REGION_SubtractO
2106 * Overlapping band subtraction. x1 is the left-most point not yet
2107 * checked.
2109 * Results:
2110 * None.
2112 * Side Effects:
2113 * pReg may have rectangles added to it.
2116 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
2117 RECT *r2, RECT *r2End, INT top, INT bottom)
2119 RECT *pNextRect;
2120 INT left;
2122 left = r1->left;
2123 pNextRect = &pReg->rects[pReg->numRects];
2125 while ((r1 != r1End) && (r2 != r2End))
2127 if (r2->right <= left)
2130 * Subtrahend missed the boat: go to next subtrahend.
2132 r2++;
2134 else if (r2->left <= left)
2137 * Subtrahend preceeds minuend: nuke left edge of minuend.
2139 left = r2->right;
2140 if (left >= r1->right)
2143 * Minuend completely covered: advance to next minuend and
2144 * reset left fence to edge of new minuend.
2146 r1++;
2147 if (r1 != r1End)
2148 left = r1->left;
2150 else
2153 * Subtrahend now used up since it doesn't extend beyond
2154 * minuend
2156 r2++;
2159 else if (r2->left < r1->right)
2162 * Left part of subtrahend covers part of minuend: add uncovered
2163 * part of minuend to region and skip to next subtrahend.
2165 MEMCHECK(pReg, pNextRect, pReg->rects);
2166 pNextRect->left = left;
2167 pNextRect->top = top;
2168 pNextRect->right = r2->left;
2169 pNextRect->bottom = bottom;
2170 pReg->numRects += 1;
2171 pNextRect++;
2172 left = r2->right;
2173 if (left >= r1->right)
2176 * Minuend used up: advance to new...
2178 r1++;
2179 if (r1 != r1End)
2180 left = r1->left;
2182 else
2185 * Subtrahend used up
2187 r2++;
2190 else
2193 * Minuend used up: add any remaining piece before advancing.
2195 if (r1->right > left)
2197 MEMCHECK(pReg, pNextRect, pReg->rects);
2198 pNextRect->left = left;
2199 pNextRect->top = top;
2200 pNextRect->right = r1->right;
2201 pNextRect->bottom = bottom;
2202 pReg->numRects += 1;
2203 pNextRect++;
2205 r1++;
2206 left = r1->left;
2211 * Add remaining minuend rectangles to region.
2213 while (r1 != r1End)
2215 MEMCHECK(pReg, pNextRect, pReg->rects);
2216 pNextRect->left = left;
2217 pNextRect->top = top;
2218 pNextRect->right = r1->right;
2219 pNextRect->bottom = bottom;
2220 pReg->numRects += 1;
2221 pNextRect++;
2222 r1++;
2223 if (r1 != r1End)
2225 left = r1->left;
2228 return;
2231 /***********************************************************************
2232 * REGION_SubtractRegion
2234 * Subtract regS from regM and leave the result in regD.
2235 * S stands for subtrahend, M for minuend and D for difference.
2237 * Results:
2238 * TRUE.
2240 * Side Effects:
2241 * regD is overwritten.
2244 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
2245 WINEREGION *regS )
2247 /* check for trivial reject */
2248 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2249 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2251 REGION_CopyRegion(regD, regM);
2252 return;
2255 REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
2256 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
2259 * Can't alter newReg's extents before we call miRegionOp because
2260 * it might be one of the source regions and miRegionOp depends
2261 * on the extents of those regions being the unaltered. Besides, this
2262 * way there's no checking against rectangles that will be nuked
2263 * due to coalescing, so we have to examine fewer rectangles.
2265 REGION_SetExtents (regD);
2266 regD->type = (regD->numRects) ?
2267 ((regD->numRects > 1) ? COMPLEXREGION : SIMPLEREGION)
2268 : NULLREGION ;
2269 return;
2272 /***********************************************************************
2273 * REGION_XorRegion
2275 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
2276 WINEREGION *srb)
2278 WINEREGION *tra, *trb;
2280 if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
2281 (! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
2282 return;
2283 REGION_SubtractRegion(tra,sra,srb);
2284 REGION_SubtractRegion(trb,srb,sra);
2285 REGION_UnionRegion(dr,tra,trb);
2286 REGION_DestroyWineRegion(tra);
2287 REGION_DestroyWineRegion(trb);
2288 return;
2291 /**************************************************************************
2293 * Poly Regions
2295 *************************************************************************/
2297 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2298 #define SMALL_COORDINATE 0x80000000
2300 /***********************************************************************
2301 * REGION_InsertEdgeInET
2303 * Insert the given edge into the edge table.
2304 * First we must find the correct bucket in the
2305 * Edge table, then find the right slot in the
2306 * bucket. Finally, we can insert it.
2309 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2310 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2313 EdgeTableEntry *start, *prev;
2314 ScanLineList *pSLL, *pPrevSLL;
2315 ScanLineListBlock *tmpSLLBlock;
2318 * find the right bucket to put the edge into
2320 pPrevSLL = &ET->scanlines;
2321 pSLL = pPrevSLL->next;
2322 while (pSLL && (pSLL->scanline < scanline))
2324 pPrevSLL = pSLL;
2325 pSLL = pSLL->next;
2329 * reassign pSLL (pointer to ScanLineList) if necessary
2331 if ((!pSLL) || (pSLL->scanline > scanline))
2333 if (*iSLLBlock > SLLSPERBLOCK-1)
2335 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2336 if(!tmpSLLBlock)
2338 WARN("Can't alloc SLLB\n");
2339 return;
2341 (*SLLBlock)->next = tmpSLLBlock;
2342 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
2343 *SLLBlock = tmpSLLBlock;
2344 *iSLLBlock = 0;
2346 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2348 pSLL->next = pPrevSLL->next;
2349 pSLL->edgelist = (EdgeTableEntry *)NULL;
2350 pPrevSLL->next = pSLL;
2352 pSLL->scanline = scanline;
2355 * now insert the edge in the right bucket
2357 prev = (EdgeTableEntry *)NULL;
2358 start = pSLL->edgelist;
2359 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2361 prev = start;
2362 start = start->next;
2364 ETE->next = start;
2366 if (prev)
2367 prev->next = ETE;
2368 else
2369 pSLL->edgelist = ETE;
2372 /***********************************************************************
2373 * REGION_CreateEdgeTable
2375 * This routine creates the edge table for
2376 * scan converting polygons.
2377 * The Edge Table (ET) looks like:
2379 * EdgeTable
2380 * --------
2381 * | ymax | ScanLineLists
2382 * |scanline|-->------------>-------------->...
2383 * -------- |scanline| |scanline|
2384 * |edgelist| |edgelist|
2385 * --------- ---------
2386 * | |
2387 * | |
2388 * V V
2389 * list of ETEs list of ETEs
2391 * where ETE is an EdgeTableEntry data structure,
2392 * and there is one ScanLineList per scanline at
2393 * which an edge is initially entered.
2396 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2397 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2398 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2400 const POINT *top, *bottom;
2401 const POINT *PrevPt, *CurrPt, *EndPt;
2402 INT poly, count;
2403 int iSLLBlock = 0;
2404 int dy;
2408 * initialize the Active Edge Table
2410 AET->next = (EdgeTableEntry *)NULL;
2411 AET->back = (EdgeTableEntry *)NULL;
2412 AET->nextWETE = (EdgeTableEntry *)NULL;
2413 AET->bres.minor_axis = SMALL_COORDINATE;
2416 * initialize the Edge Table.
2418 ET->scanlines.next = (ScanLineList *)NULL;
2419 ET->ymax = SMALL_COORDINATE;
2420 ET->ymin = LARGE_COORDINATE;
2421 pSLLBlock->next = (ScanLineListBlock *)NULL;
2423 EndPt = pts - 1;
2424 for(poly = 0; poly < nbpolygons; poly++)
2426 count = Count[poly];
2427 EndPt += count;
2428 if(count < 2)
2429 continue;
2431 PrevPt = EndPt;
2434 * for each vertex in the array of points.
2435 * In this loop we are dealing with two vertices at
2436 * a time -- these make up one edge of the polygon.
2438 while (count--)
2440 CurrPt = pts++;
2443 * find out which point is above and which is below.
2445 if (PrevPt->y > CurrPt->y)
2447 bottom = PrevPt, top = CurrPt;
2448 pETEs->ClockWise = 0;
2450 else
2452 bottom = CurrPt, top = PrevPt;
2453 pETEs->ClockWise = 1;
2457 * don't add horizontal edges to the Edge table.
2459 if (bottom->y != top->y)
2461 pETEs->ymax = bottom->y-1;
2462 /* -1 so we don't get last scanline */
2465 * initialize integer edge algorithm
2467 dy = bottom->y - top->y;
2468 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2470 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2471 &iSLLBlock);
2473 if (PrevPt->y > ET->ymax)
2474 ET->ymax = PrevPt->y;
2475 if (PrevPt->y < ET->ymin)
2476 ET->ymin = PrevPt->y;
2477 pETEs++;
2480 PrevPt = CurrPt;
2485 /***********************************************************************
2486 * REGION_loadAET
2488 * This routine moves EdgeTableEntries from the
2489 * EdgeTable into the Active Edge Table,
2490 * leaving them sorted by smaller x coordinate.
2493 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2495 EdgeTableEntry *pPrevAET;
2496 EdgeTableEntry *tmp;
2498 pPrevAET = AET;
2499 AET = AET->next;
2500 while (ETEs)
2502 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2504 pPrevAET = AET;
2505 AET = AET->next;
2507 tmp = ETEs->next;
2508 ETEs->next = AET;
2509 if (AET)
2510 AET->back = ETEs;
2511 ETEs->back = pPrevAET;
2512 pPrevAET->next = ETEs;
2513 pPrevAET = ETEs;
2515 ETEs = tmp;
2519 /***********************************************************************
2520 * REGION_computeWAET
2522 * This routine links the AET by the
2523 * nextWETE (winding EdgeTableEntry) link for
2524 * use by the winding number rule. The final
2525 * Active Edge Table (AET) might look something
2526 * like:
2528 * AET
2529 * ---------- --------- ---------
2530 * |ymax | |ymax | |ymax |
2531 * | ... | |... | |... |
2532 * |next |->|next |->|next |->...
2533 * |nextWETE| |nextWETE| |nextWETE|
2534 * --------- --------- ^--------
2535 * | | |
2536 * V-------------------> V---> ...
2539 static void REGION_computeWAET(EdgeTableEntry *AET)
2541 register EdgeTableEntry *pWETE;
2542 register int inside = 1;
2543 register int isInside = 0;
2545 AET->nextWETE = (EdgeTableEntry *)NULL;
2546 pWETE = AET;
2547 AET = AET->next;
2548 while (AET)
2550 if (AET->ClockWise)
2551 isInside++;
2552 else
2553 isInside--;
2555 if ((!inside && !isInside) ||
2556 ( inside && isInside))
2558 pWETE->nextWETE = AET;
2559 pWETE = AET;
2560 inside = !inside;
2562 AET = AET->next;
2564 pWETE->nextWETE = (EdgeTableEntry *)NULL;
2567 /***********************************************************************
2568 * REGION_InsertionSort
2570 * Just a simple insertion sort using
2571 * pointers and back pointers to sort the Active
2572 * Edge Table.
2575 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2577 EdgeTableEntry *pETEchase;
2578 EdgeTableEntry *pETEinsert;
2579 EdgeTableEntry *pETEchaseBackTMP;
2580 BOOL changed = FALSE;
2582 AET = AET->next;
2583 while (AET)
2585 pETEinsert = AET;
2586 pETEchase = AET;
2587 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2588 pETEchase = pETEchase->back;
2590 AET = AET->next;
2591 if (pETEchase != pETEinsert)
2593 pETEchaseBackTMP = pETEchase->back;
2594 pETEinsert->back->next = AET;
2595 if (AET)
2596 AET->back = pETEinsert->back;
2597 pETEinsert->next = pETEchase;
2598 pETEchase->back->next = pETEinsert;
2599 pETEchase->back = pETEinsert;
2600 pETEinsert->back = pETEchaseBackTMP;
2601 changed = TRUE;
2604 return changed;
2607 /***********************************************************************
2608 * REGION_FreeStorage
2610 * Clean up our act.
2612 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2614 ScanLineListBlock *tmpSLLBlock;
2616 while (pSLLBlock)
2618 tmpSLLBlock = pSLLBlock->next;
2619 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2620 pSLLBlock = tmpSLLBlock;
2625 /***********************************************************************
2626 * REGION_PtsToRegion
2628 * Create an array of rectangles from a list of points.
2630 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2631 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2633 RECT *rects;
2634 POINT *pts;
2635 POINTBLOCK *CurPtBlock;
2636 int i;
2637 RECT *extents;
2638 INT numRects;
2640 extents = &reg->extents;
2642 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2644 if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2645 sizeof(RECT) * numRects )))
2646 return(0);
2648 reg->size = numRects;
2649 CurPtBlock = FirstPtBlock;
2650 rects = reg->rects - 1;
2651 numRects = 0;
2652 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2654 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2655 /* the loop uses 2 points per iteration */
2656 i = NUMPTSTOBUFFER >> 1;
2657 if (!numFullPtBlocks)
2658 i = iCurPtBlock >> 1;
2659 for (pts = CurPtBlock->pts; i--; pts += 2) {
2660 if (pts->x == pts[1].x)
2661 continue;
2662 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2663 pts[1].x == rects->right &&
2664 (numRects == 1 || rects[-1].top != rects->top) &&
2665 (i && pts[2].y > pts[1].y)) {
2666 rects->bottom = pts[1].y + 1;
2667 continue;
2669 numRects++;
2670 rects++;
2671 rects->left = pts->x; rects->top = pts->y;
2672 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2673 if (rects->left < extents->left)
2674 extents->left = rects->left;
2675 if (rects->right > extents->right)
2676 extents->right = rects->right;
2678 CurPtBlock = CurPtBlock->next;
2681 if (numRects) {
2682 extents->top = reg->rects->top;
2683 extents->bottom = rects->bottom;
2684 } else {
2685 extents->left = 0;
2686 extents->top = 0;
2687 extents->right = 0;
2688 extents->bottom = 0;
2690 reg->numRects = numRects;
2692 return(TRUE);
2695 /***********************************************************************
2696 * CreatePolyPolygonRgn (GDI32.@)
2698 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2699 INT nbpolygons, INT mode)
2701 HRGN hrgn;
2702 RGNOBJ *obj;
2703 WINEREGION *region;
2704 register EdgeTableEntry *pAET; /* Active Edge Table */
2705 register INT y; /* current scanline */
2706 register int iPts = 0; /* number of pts in buffer */
2707 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2708 register ScanLineList *pSLL; /* current scanLineList */
2709 register POINT *pts; /* output buffer */
2710 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2711 EdgeTable ET; /* header node for ET */
2712 EdgeTableEntry AET; /* header node for AET */
2713 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2714 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2715 int fixWAET = FALSE;
2716 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2717 POINTBLOCK *tmpPtBlock;
2718 int numFullPtBlocks = 0;
2719 INT poly, total;
2721 if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2722 return 0;
2723 obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
2724 region = obj->rgn;
2726 /* special case a rectangle */
2728 if (((nbpolygons == 1) && ((*Count == 4) ||
2729 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2730 (((Pts[0].y == Pts[1].y) &&
2731 (Pts[1].x == Pts[2].x) &&
2732 (Pts[2].y == Pts[3].y) &&
2733 (Pts[3].x == Pts[0].x)) ||
2734 ((Pts[0].x == Pts[1].x) &&
2735 (Pts[1].y == Pts[2].y) &&
2736 (Pts[2].x == Pts[3].x) &&
2737 (Pts[3].y == Pts[0].y))))
2739 SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2740 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2741 GDI_ReleaseObj( hrgn );
2742 return hrgn;
2745 for(poly = total = 0; poly < nbpolygons; poly++)
2746 total += Count[poly];
2747 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2749 REGION_DeleteObject( hrgn, obj );
2750 return 0;
2752 pts = FirstPtBlock.pts;
2753 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2754 pSLL = ET.scanlines.next;
2755 curPtBlock = &FirstPtBlock;
2757 if (mode != WINDING) {
2759 * for each scanline
2761 for (y = ET.ymin; y < ET.ymax; y++) {
2763 * Add a new edge to the active edge table when we
2764 * get to the next edge.
2766 if (pSLL != NULL && y == pSLL->scanline) {
2767 REGION_loadAET(&AET, pSLL->edgelist);
2768 pSLL = pSLL->next;
2770 pPrevAET = &AET;
2771 pAET = AET.next;
2774 * for each active edge
2776 while (pAET) {
2777 pts->x = pAET->bres.minor_axis, pts->y = y;
2778 pts++, iPts++;
2781 * send out the buffer
2783 if (iPts == NUMPTSTOBUFFER) {
2784 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2785 if(!tmpPtBlock) {
2786 WARN("Can't alloc tPB\n");
2787 return 0;
2789 curPtBlock->next = tmpPtBlock;
2790 curPtBlock = tmpPtBlock;
2791 pts = curPtBlock->pts;
2792 numFullPtBlocks++;
2793 iPts = 0;
2795 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2797 REGION_InsertionSort(&AET);
2800 else {
2802 * for each scanline
2804 for (y = ET.ymin; y < ET.ymax; y++) {
2806 * Add a new edge to the active edge table when we
2807 * get to the next edge.
2809 if (pSLL != NULL && y == pSLL->scanline) {
2810 REGION_loadAET(&AET, pSLL->edgelist);
2811 REGION_computeWAET(&AET);
2812 pSLL = pSLL->next;
2814 pPrevAET = &AET;
2815 pAET = AET.next;
2816 pWETE = pAET;
2819 * for each active edge
2821 while (pAET) {
2823 * add to the buffer only those edges that
2824 * are in the Winding active edge table.
2826 if (pWETE == pAET) {
2827 pts->x = pAET->bres.minor_axis, pts->y = y;
2828 pts++, iPts++;
2831 * send out the buffer
2833 if (iPts == NUMPTSTOBUFFER) {
2834 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2835 sizeof(POINTBLOCK) );
2836 if(!tmpPtBlock) {
2837 WARN("Can't alloc tPB\n");
2838 REGION_DeleteObject( hrgn, obj );
2839 return 0;
2841 curPtBlock->next = tmpPtBlock;
2842 curPtBlock = tmpPtBlock;
2843 pts = curPtBlock->pts;
2844 numFullPtBlocks++; iPts = 0;
2846 pWETE = pWETE->nextWETE;
2848 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2852 * recompute the winding active edge table if
2853 * we just resorted or have exited an edge.
2855 if (REGION_InsertionSort(&AET) || fixWAET) {
2856 REGION_computeWAET(&AET);
2857 fixWAET = FALSE;
2861 REGION_FreeStorage(SLLBlock.next);
2862 REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2863 region->type = (region->numRects) ?
2864 ((region->numRects > 1) ? COMPLEXREGION : SIMPLEREGION)
2865 : NULLREGION;
2867 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2868 tmpPtBlock = curPtBlock->next;
2869 HeapFree( GetProcessHeap(), 0, curPtBlock );
2870 curPtBlock = tmpPtBlock;
2872 HeapFree( GetProcessHeap(), 0, pETEs );
2873 GDI_ReleaseObj( hrgn );
2874 return hrgn;
2878 /***********************************************************************
2879 * CreatePolygonRgn16 (GDI.63)
2881 HRGN16 WINAPI CreatePolygonRgn16( const POINT16 * points, INT16 count,
2882 INT16 mode )
2884 return CreatePolyPolygonRgn16( points, &count, 1, mode );
2887 /***********************************************************************
2888 * CreatePolyPolygonRgn16 (GDI.451)
2890 HRGN16 WINAPI CreatePolyPolygonRgn16( const POINT16 *points,
2891 const INT16 *count, INT16 nbpolygons, INT16 mode )
2893 HRGN hrgn;
2894 int i, npts = 0;
2895 INT *count32;
2896 POINT *points32;
2898 for (i = 0; i < nbpolygons; i++)
2899 npts += count[i];
2900 points32 = HeapAlloc( GetProcessHeap(), 0, npts * sizeof(POINT) );
2901 for (i = 0; i < npts; i++)
2902 CONV_POINT16TO32( &(points[i]), &(points32[i]) );
2904 count32 = HeapAlloc( GetProcessHeap(), 0, nbpolygons * sizeof(INT) );
2905 for (i = 0; i < nbpolygons; i++)
2906 count32[i] = count[i];
2907 hrgn = CreatePolyPolygonRgn( points32, count32, nbpolygons, mode );
2908 HeapFree( GetProcessHeap(), 0, count32 );
2909 HeapFree( GetProcessHeap(), 0, points32 );
2910 return hrgn;
2913 /***********************************************************************
2914 * CreatePolygonRgn (GDI32.@)
2916 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2917 INT mode )
2919 return CreatePolyPolygonRgn( points, &count, 1, mode );
2923 /***********************************************************************
2924 * GetRandomRgn [GDI32.@]
2926 * NOTES
2927 * This function is documented in MSDN online
2929 INT WINAPI GetRandomRgn(HDC hDC, HRGN hRgn, DWORD dwCode)
2931 switch (dwCode)
2933 case 4: /* == SYSRGN ? */
2935 DC *dc = DC_GetDCPtr (hDC);
2936 OSVERSIONINFOA vi;
2937 POINT org;
2939 if (!dc) return -1;
2940 CombineRgn (hRgn, dc->hVisRgn, 0, RGN_COPY);
2942 * On Windows NT/2000,
2943 * the region returned is in screen coordinates.
2944 * On Windows 95/98,
2945 * the region returned is in window coordinates
2947 vi.dwOSVersionInfoSize = sizeof(vi);
2948 if (GetVersionExA( &vi ) && vi.dwPlatformId == VER_PLATFORM_WIN32_NT)
2949 GetDCOrgEx(hDC, &org);
2950 else
2951 org.x = org.y = 0;
2952 org.x -= dc->DCOrgX;
2953 org.y -= dc->DCOrgY;
2954 OffsetRgn (hRgn, org.x, org.y);
2955 GDI_ReleaseObj( hDC );
2956 return 1;
2958 /* case 1:
2959 return GetClipRgn (hDC, hRgn);
2961 default:
2962 WARN("Unknown dwCode %ld\n", dwCode);
2963 return -1;
2966 return -1;
2969 /***********************************************************************
2970 * REGION_CropAndOffsetRegion
2972 static BOOL REGION_CropAndOffsetRegion(const POINT* off, const RECT *rect, WINEREGION *rgnSrc, WINEREGION* rgnDst)
2975 if( !rect ) /* just copy and offset */
2977 RECT *xrect;
2978 if( rgnDst == rgnSrc )
2980 if( off->x || off->y )
2981 xrect = rgnDst->rects;
2982 else
2983 return TRUE;
2985 else
2986 xrect = HeapReAlloc( GetProcessHeap(), 0, rgnDst->rects,
2987 rgnSrc->size * sizeof( RECT ));
2988 if( xrect )
2990 INT i;
2992 if( rgnDst != rgnSrc )
2993 memcpy( rgnDst, rgnSrc, sizeof( WINEREGION ));
2995 if( off->x || off->y )
2997 for( i = 0; i < rgnDst->numRects; i++ )
2999 xrect[i].left = rgnSrc->rects[i].left + off->x;
3000 xrect[i].right = rgnSrc->rects[i].right + off->x;
3001 xrect[i].top = rgnSrc->rects[i].top + off->y;
3002 xrect[i].bottom = rgnSrc->rects[i].bottom + off->y;
3004 rgnDst->extents.left += off->x;
3005 rgnDst->extents.right += off->x;
3006 rgnDst->extents.top += off->y;
3007 rgnDst->extents.bottom += off->y;
3009 else
3010 memcpy( xrect, rgnSrc->rects, rgnDst->numRects * sizeof(RECT));
3011 rgnDst->rects = xrect;
3012 } else
3013 return FALSE;
3015 else if ((rect->left >= rect->right) ||
3016 (rect->top >= rect->bottom) ||
3017 !EXTENTCHECK(rect, &rgnSrc->extents))
3019 empty:
3020 if( !rgnDst->rects )
3022 rgnDst->rects = HeapAlloc(GetProcessHeap(), 0, RGN_DEFAULT_RECTS * sizeof( RECT ));
3023 if( rgnDst->rects )
3024 rgnDst->size = RGN_DEFAULT_RECTS;
3025 else
3026 return FALSE;
3029 TRACE("cropped to empty!\n");
3030 EMPTY_REGION(rgnDst);
3032 else /* region box and clipping rect appear to intersect */
3034 RECT *lpr;
3035 INT i, j, clipa, clipb;
3036 INT left = rgnSrc->extents.right + off->x;
3037 INT right = rgnSrc->extents.left + off->x;
3039 for( clipa = 0; rgnSrc->rects[clipa].bottom <= rect->top; clipa++ )
3040 ; /* skip bands above the clipping rectangle */
3042 for( clipb = clipa; clipb < rgnSrc->numRects; clipb++ )
3043 if( rgnSrc->rects[clipb].top >= rect->bottom )
3044 break; /* and below it */
3046 /* clipa - index of the first rect in the first intersecting band
3047 * clipb - index of the last rect in the last intersecting band
3050 if((rgnDst != rgnSrc) && (rgnDst->size < (i = (clipb - clipa))))
3052 rgnDst->rects = HeapReAlloc( GetProcessHeap(), 0,
3053 rgnDst->rects, i * sizeof(RECT));
3054 if( !rgnDst->rects ) return FALSE;
3055 rgnDst->size = i;
3058 if( TRACE_ON(region) )
3060 REGION_DumpRegion( rgnSrc );
3061 TRACE("\tclipa = %i, clipb = %i\n", clipa, clipb );
3064 for( i = clipa, j = 0; i < clipb ; i++ )
3066 /* i - src index, j - dst index, j is always <= i for obvious reasons */
3068 lpr = rgnSrc->rects + i;
3069 if( lpr->left < rect->right && lpr->right > rect->left )
3071 rgnDst->rects[j].top = lpr->top + off->y;
3072 rgnDst->rects[j].bottom = lpr->bottom + off->y;
3073 rgnDst->rects[j].left = ((lpr->left > rect->left) ? lpr->left : rect->left) + off->x;
3074 rgnDst->rects[j].right = ((lpr->right < rect->right) ? lpr->right : rect->right) + off->x;
3076 if( rgnDst->rects[j].left < left ) left = rgnDst->rects[j].left;
3077 if( rgnDst->rects[j].right > right ) right = rgnDst->rects[j].right;
3079 j++;
3083 if( j == 0 ) goto empty;
3085 rgnDst->extents.left = left;
3086 rgnDst->extents.right = right;
3088 left = rect->top + off->y;
3089 right = rect->bottom + off->y;
3091 rgnDst->numRects = j--;
3092 for( i = 0; i <= j; i++ ) /* fixup top band */
3093 if( rgnDst->rects[i].top < left )
3094 rgnDst->rects[i].top = left;
3095 else
3096 break;
3098 for( i = j; i >= 0; i-- ) /* fixup bottom band */
3099 if( rgnDst->rects[i].bottom > right )
3100 rgnDst->rects[i].bottom = right;
3101 else
3102 break;
3104 rgnDst->extents.top = rgnDst->rects[0].top;
3105 rgnDst->extents.bottom = rgnDst->rects[j].bottom;
3107 rgnDst->type = (j >= 1) ? COMPLEXREGION : SIMPLEREGION;
3109 if( TRACE_ON(region) )
3111 TRACE("result:\n");
3112 REGION_DumpRegion( rgnDst );
3116 return TRUE;
3119 /***********************************************************************
3120 * REGION_CropRgn
3123 * hSrc: Region to crop and offset.
3124 * lpRect: Clipping rectangle. Can be NULL (no clipping).
3125 * lpPt: Points to offset the cropped region. Can be NULL (no offset).
3127 * hDst: Region to hold the result (a new region is created if it's 0).
3128 * Allowed to be the same region as hSrc in which case everything
3129 * will be done in place, with no memory reallocations.
3131 * Returns: hDst if success, 0 otherwise.
3133 HRGN REGION_CropRgn( HRGN hDst, HRGN hSrc, const RECT *lpRect, const POINT *lpPt )
3135 /* Optimization of the following generic code:
3137 HRGN h;
3139 if( lpRect )
3140 h = CreateRectRgn( lpRect->left, lpRect->top, lpRect->right, lpRect->bottom );
3141 else
3142 h = CreateRectRgn( 0, 0, 0, 0 );
3143 if( hDst == 0 ) hDst = h;
3144 if( lpRect )
3145 CombineRgn( hDst, hSrc, h, RGN_AND );
3146 else
3147 CombineRgn( hDst, hSrc, 0, RGN_COPY );
3148 if( lpPt )
3149 OffsetRgn( hDst, lpPt->x, lpPt->y );
3150 if( hDst != h )
3151 DeleteObject( h );
3152 return hDst;
3156 RGNOBJ *objSrc = (RGNOBJ *) GDI_GetObjPtr( hSrc, REGION_MAGIC );
3158 if(objSrc)
3160 RGNOBJ *objDst;
3161 WINEREGION *rgnDst;
3163 if( hDst )
3165 if (!(objDst = (RGNOBJ *) GDI_GetObjPtr( hDst, REGION_MAGIC )))
3167 hDst = 0;
3168 goto done;
3170 rgnDst = objDst->rgn;
3172 else
3174 if ((rgnDst = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
3176 rgnDst->size = rgnDst->numRects = 0;
3177 rgnDst->rects = NULL; /* back end will allocate exact number */
3181 if( rgnDst )
3183 POINT pt = { 0, 0 };
3185 if( !lpPt ) lpPt = &pt;
3187 if( lpRect )
3188 TRACE("src %p -> dst %p (%i,%i)-(%i,%i) by (%li,%li)\n", objSrc->rgn, rgnDst,
3189 lpRect->left, lpRect->top, lpRect->right, lpRect->bottom, lpPt->x, lpPt->y );
3190 else
3191 TRACE("src %p -> dst %p by (%li,%li)\n", objSrc->rgn, rgnDst, lpPt->x, lpPt->y );
3193 if( REGION_CropAndOffsetRegion( lpPt, lpRect, objSrc->rgn, rgnDst ) == FALSE )
3195 if( hDst ) /* existing rgn */
3197 GDI_ReleaseObj(hDst);
3198 hDst = 0;
3199 goto done;
3201 goto fail;
3203 else if( hDst == 0 )
3205 if (!(objDst = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, &hDst )))
3207 fail:
3208 if( rgnDst->rects )
3209 HeapFree( GetProcessHeap(), 0, rgnDst->rects );
3210 HeapFree( GetProcessHeap(), 0, rgnDst );
3211 goto done;
3213 objDst->rgn = rgnDst;
3216 GDI_ReleaseObj(hDst);
3218 else hDst = 0;
3219 done:
3220 GDI_ReleaseObj(hSrc);
3221 return hDst;
3223 return 0;
3226 /***********************************************************************
3227 * GetMetaRgn (GDI.328)
3228 * GetMetaRgn (GDI32.@)
3230 INT WINAPI GetMetaRgn( HDC hdc, HRGN hRgn )
3232 FIXME( "stub\n" );
3234 return 0;
3238 /***********************************************************************
3239 * SetMetaRgn (GDI.455)
3240 * SetMetaRgn (GDI32.@)
3242 INT WINAPI SetMetaRgn( HDC hdc )
3244 FIXME( "stub\n" );
3246 return ERROR;