Store the windows and system directories as long path names.
[wine.git] / objects / region.c
blob336f58f1b43a2579d3d30dd8ac7b41f5ead1d6d1
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 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public
11 * License as published by the Free Software Foundation; either
12 * version 2.1 of the License, or (at your option) any later version.
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this library; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 /************************************************************************
26 Copyright (c) 1987, 1988 X Consortium
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
52 All Rights Reserved
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
68 SOFTWARE.
70 ************************************************************************/
72 * The functions in this file implement the Region abstraction, similar to one
73 * used in the X11 sample server. A Region is simply an area, as the name
74 * implies, and is implemented as a "y-x-banded" array of rectangles. To
75 * explain: Each Region is made up of a certain number of rectangles sorted
76 * by y coordinate first, and then by x coordinate.
78 * Furthermore, the rectangles are banded such that every rectangle with a
79 * given upper-left y coordinate (y1) will have the same lower-right y
80 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81 * will span the entire vertical distance of the band. This means that some
82 * areas that could be merged into a taller rectangle will be represented as
83 * several shorter rectangles to account for shorter rectangles to its left
84 * or right but within its "vertical scope".
86 * An added constraint on the rectangles is that they must cover as much
87 * horizontal area as possible. E.g. no two rectangles in a band are allowed
88 * to touch.
90 * Whenever possible, bands will be merged together to cover a greater vertical
91 * distance (and thus reduce the number of rectangles). Two bands can be merged
92 * only if the bottom of one touches the top of the other and they have
93 * rectangles in the same places (of the same width, of course). This maintains
94 * the y-x-banding that's so nice to have...
97 #include <stdarg.h>
98 #include <stdlib.h>
99 #include <string.h>
100 #include "windef.h"
101 #include "winbase.h"
102 #include "wingdi.h"
103 #include "gdi.h"
104 #include "gdi_private.h"
105 #include "wine/debug.h"
107 WINE_DEFAULT_DEBUG_CHANNEL(region);
109 typedef struct {
110 INT size;
111 INT numRects;
112 RECT *rects;
113 RECT extents;
114 } WINEREGION;
116 /* GDI logical region object */
117 typedef struct
119 GDIOBJHDR header;
120 WINEREGION *rgn;
121 } RGNOBJ;
124 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, void *obj, HDC hdc );
125 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj );
127 static const struct gdi_obj_funcs region_funcs =
129 REGION_SelectObject, /* pSelectObject */
130 NULL, /* pGetObject16 */
131 NULL, /* pGetObjectA */
132 NULL, /* pGetObjectW */
133 NULL, /* pUnrealizeObject */
134 REGION_DeleteObject /* pDeleteObject */
137 /* 1 if two RECTs overlap.
138 * 0 if two RECTs do not overlap.
140 #define EXTENTCHECK(r1, r2) \
141 ((r1)->right > (r2)->left && \
142 (r1)->left < (r2)->right && \
143 (r1)->bottom > (r2)->top && \
144 (r1)->top < (r2)->bottom)
147 * Check to see if there is enough memory in the present region.
150 static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
151 if (reg->numRects >= (reg->size - 1)) {
152 *firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
153 if (*firstrect == 0)
154 return 0;
155 reg->size *= 2;
156 *rect = (*firstrect)+reg->numRects;
158 return 1;
161 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
163 #define EMPTY_REGION(pReg) { \
164 (pReg)->numRects = 0; \
165 (pReg)->extents.left = (pReg)->extents.top = 0; \
166 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
169 #define REGION_NOT_EMPTY(pReg) pReg->numRects
171 #define INRECT(r, x, y) \
172 ( ( ((r).right > x)) && \
173 ( ((r).left <= x)) && \
174 ( ((r).bottom > y)) && \
175 ( ((r).top <= y)) )
179 * number of points to buffer before sending them off
180 * to scanlines() : Must be an even number
182 #define NUMPTSTOBUFFER 200
185 * used to allocate buffers for points and link
186 * the buffers together
189 typedef struct _POINTBLOCK {
190 POINT pts[NUMPTSTOBUFFER];
191 struct _POINTBLOCK *next;
192 } POINTBLOCK;
197 * This file contains a few macros to help track
198 * the edge of a filled object. The object is assumed
199 * to be filled in scanline order, and thus the
200 * algorithm used is an extension of Bresenham's line
201 * drawing algorithm which assumes that y is always the
202 * major axis.
203 * Since these pieces of code are the same for any filled shape,
204 * it is more convenient to gather the library in one
205 * place, but since these pieces of code are also in
206 * the inner loops of output primitives, procedure call
207 * overhead is out of the question.
208 * See the author for a derivation if needed.
213 * In scan converting polygons, we want to choose those pixels
214 * which are inside the polygon. Thus, we add .5 to the starting
215 * x coordinate for both left and right edges. Now we choose the
216 * first pixel which is inside the pgon for the left edge and the
217 * first pixel which is outside the pgon for the right edge.
218 * Draw the left pixel, but not the right.
220 * How to add .5 to the starting x coordinate:
221 * If the edge is moving to the right, then subtract dy from the
222 * error term from the general form of the algorithm.
223 * If the edge is moving to the left, then add dy to the error term.
225 * The reason for the difference between edges moving to the left
226 * and edges moving to the right is simple: If an edge is moving
227 * to the right, then we want the algorithm to flip immediately.
228 * If it is moving to the left, then we don't want it to flip until
229 * we traverse an entire pixel.
231 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
232 int dx; /* local storage */ \
234 /* \
235 * if the edge is horizontal, then it is ignored \
236 * and assumed not to be processed. Otherwise, do this stuff. \
237 */ \
238 if ((dy) != 0) { \
239 xStart = (x1); \
240 dx = (x2) - xStart; \
241 if (dx < 0) { \
242 m = dx / (dy); \
243 m1 = m - 1; \
244 incr1 = -2 * dx + 2 * (dy) * m1; \
245 incr2 = -2 * dx + 2 * (dy) * m; \
246 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
247 } else { \
248 m = dx / (dy); \
249 m1 = m + 1; \
250 incr1 = 2 * dx - 2 * (dy) * m1; \
251 incr2 = 2 * dx - 2 * (dy) * m; \
252 d = -2 * m * (dy) + 2 * dx; \
257 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
258 if (m1 > 0) { \
259 if (d > 0) { \
260 minval += m1; \
261 d += incr1; \
263 else { \
264 minval += m; \
265 d += incr2; \
267 } else {\
268 if (d >= 0) { \
269 minval += m1; \
270 d += incr1; \
272 else { \
273 minval += m; \
274 d += incr2; \
280 * This structure contains all of the information needed
281 * to run the bresenham algorithm.
282 * The variables may be hardcoded into the declarations
283 * instead of using this structure to make use of
284 * register declarations.
286 typedef struct {
287 INT minor_axis; /* minor axis */
288 INT d; /* decision variable */
289 INT m, m1; /* slope and slope+1 */
290 INT incr1, incr2; /* error increments */
291 } BRESINFO;
294 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
295 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
296 bres.m, bres.m1, bres.incr1, bres.incr2)
298 #define BRESINCRPGONSTRUCT(bres) \
299 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
304 * These are the data structures needed to scan
305 * convert regions. Two different scan conversion
306 * methods are available -- the even-odd method, and
307 * the winding number method.
308 * The even-odd rule states that a point is inside
309 * the polygon if a ray drawn from that point in any
310 * direction will pass through an odd number of
311 * path segments.
312 * By the winding number rule, a point is decided
313 * to be inside the polygon if a ray drawn from that
314 * point in any direction passes through a different
315 * number of clockwise and counter-clockwise path
316 * segments.
318 * These data structures are adapted somewhat from
319 * the algorithm in (Foley/Van Dam) for scan converting
320 * polygons.
321 * The basic algorithm is to start at the top (smallest y)
322 * of the polygon, stepping down to the bottom of
323 * the polygon by incrementing the y coordinate. We
324 * keep a list of edges which the current scanline crosses,
325 * sorted by x. This list is called the Active Edge Table (AET)
326 * As we change the y-coordinate, we update each entry in
327 * in the active edge table to reflect the edges new xcoord.
328 * This list must be sorted at each scanline in case
329 * two edges intersect.
330 * We also keep a data structure known as the Edge Table (ET),
331 * which keeps track of all the edges which the current
332 * scanline has not yet reached. The ET is basically a
333 * list of ScanLineList structures containing a list of
334 * edges which are entered at a given scanline. There is one
335 * ScanLineList per scanline at which an edge is entered.
336 * When we enter a new edge, we move it from the ET to the AET.
338 * From the AET, we can implement the even-odd rule as in
339 * (Foley/Van Dam).
340 * The winding number rule is a little trickier. We also
341 * keep the EdgeTableEntries in the AET linked by the
342 * nextWETE (winding EdgeTableEntry) link. This allows
343 * the edges to be linked just as before for updating
344 * purposes, but only uses the edges linked by the nextWETE
345 * link as edges representing spans of the polygon to
346 * drawn (as with the even-odd rule).
350 * for the winding number rule
352 #define CLOCKWISE 1
353 #define COUNTERCLOCKWISE -1
355 typedef struct _EdgeTableEntry {
356 INT ymax; /* ycoord at which we exit this edge. */
357 BRESINFO bres; /* Bresenham info to run the edge */
358 struct _EdgeTableEntry *next; /* next in the list */
359 struct _EdgeTableEntry *back; /* for insertion sort */
360 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
361 int ClockWise; /* flag for winding number rule */
362 } EdgeTableEntry;
365 typedef struct _ScanLineList{
366 INT scanline; /* the scanline represented */
367 EdgeTableEntry *edgelist; /* header node */
368 struct _ScanLineList *next; /* next in the list */
369 } ScanLineList;
372 typedef struct {
373 INT ymax; /* ymax for the polygon */
374 INT ymin; /* ymin for the polygon */
375 ScanLineList scanlines; /* header node */
376 } EdgeTable;
380 * Here is a struct to help with storage allocation
381 * so we can allocate a big chunk at a time, and then take
382 * pieces from this heap when we need to.
384 #define SLLSPERBLOCK 25
386 typedef struct _ScanLineListBlock {
387 ScanLineList SLLs[SLLSPERBLOCK];
388 struct _ScanLineListBlock *next;
389 } ScanLineListBlock;
394 * a few macros for the inner loops of the fill code where
395 * performance considerations don't allow a procedure call.
397 * Evaluate the given edge at the given scanline.
398 * If the edge has expired, then we leave it and fix up
399 * the active edge table; otherwise, we increment the
400 * x value to be ready for the next scanline.
401 * The winding number rule is in effect, so we must notify
402 * the caller when the edge has been removed so he
403 * can reorder the Winding Active Edge Table.
405 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
406 if (pAET->ymax == y) { /* leaving this edge */ \
407 pPrevAET->next = pAET->next; \
408 pAET = pPrevAET->next; \
409 fixWAET = 1; \
410 if (pAET) \
411 pAET->back = pPrevAET; \
413 else { \
414 BRESINCRPGONSTRUCT(pAET->bres); \
415 pPrevAET = pAET; \
416 pAET = pAET->next; \
422 * Evaluate the given edge at the given scanline.
423 * If the edge has expired, then we leave it and fix up
424 * the active edge table; otherwise, we increment the
425 * x value to be ready for the next scanline.
426 * The even-odd rule is in effect.
428 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
429 if (pAET->ymax == y) { /* leaving this edge */ \
430 pPrevAET->next = pAET->next; \
431 pAET = pPrevAET->next; \
432 if (pAET) \
433 pAET->back = pPrevAET; \
435 else { \
436 BRESINCRPGONSTRUCT(pAET->bres); \
437 pPrevAET = pAET; \
438 pAET = pAET->next; \
442 typedef void (*voidProcp)();
444 /* Note the parameter order is different from the X11 equivalents */
446 static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
447 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
449 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
450 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
451 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
453 #define RGN_DEFAULT_RECTS 2
456 /***********************************************************************
457 * get_region_type
459 inline static INT get_region_type( const RGNOBJ *obj )
461 switch(obj->rgn->numRects)
463 case 0: return NULLREGION;
464 case 1: return SIMPLEREGION;
465 default: return COMPLEXREGION;
470 /***********************************************************************
471 * REGION_DumpRegion
472 * Outputs the contents of a WINEREGION
474 static void REGION_DumpRegion(WINEREGION *pReg)
476 RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
478 TRACE("Region %p: %ld,%ld - %ld,%ld %d rects\n", pReg,
479 pReg->extents.left, pReg->extents.top,
480 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
481 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
482 TRACE("\t%ld,%ld - %ld,%ld\n", pRect->left, pRect->top,
483 pRect->right, pRect->bottom);
484 return;
488 /***********************************************************************
489 * REGION_AllocWineRegion
490 * Create a new empty WINEREGION.
492 static WINEREGION *REGION_AllocWineRegion( INT n )
494 WINEREGION *pReg;
496 if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
498 if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
500 pReg->size = n;
501 EMPTY_REGION(pReg);
502 return pReg;
504 HeapFree(GetProcessHeap(), 0, pReg);
506 return NULL;
510 /***********************************************************************
511 * REGION_CreateRegion
512 * Create a new empty region.
514 static HRGN REGION_CreateRegion( INT n )
516 HRGN hrgn;
517 RGNOBJ *obj;
519 if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, (HGDIOBJ *)&hrgn,
520 &region_funcs ))) return 0;
521 if(!(obj->rgn = REGION_AllocWineRegion(n))) {
522 GDI_FreeObject( hrgn, obj );
523 return 0;
525 GDI_ReleaseObj( hrgn );
526 return hrgn;
529 /***********************************************************************
530 * REGION_DestroyWineRegion
532 static void REGION_DestroyWineRegion( WINEREGION* pReg )
534 HeapFree( GetProcessHeap(), 0, pReg->rects );
535 HeapFree( GetProcessHeap(), 0, pReg );
538 /***********************************************************************
539 * REGION_DeleteObject
541 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj )
543 RGNOBJ *rgn = obj;
545 TRACE(" %p\n", handle );
547 REGION_DestroyWineRegion( rgn->rgn );
548 return GDI_FreeObject( handle, obj );
551 /***********************************************************************
552 * REGION_SelectObject
554 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, void *obj, HDC hdc )
556 return (HGDIOBJ)SelectClipRgn( hdc, handle );
560 /***********************************************************************
561 * OffsetRgn (GDI32.@)
563 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
565 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
566 INT ret;
568 TRACE("%p %d,%d\n", hrgn, x, y);
570 if (!obj)
571 return ERROR;
573 if(x || y) {
574 int nbox = obj->rgn->numRects;
575 RECT *pbox = obj->rgn->rects;
577 if(nbox) {
578 while(nbox--) {
579 pbox->left += x;
580 pbox->right += x;
581 pbox->top += y;
582 pbox->bottom += y;
583 pbox++;
585 obj->rgn->extents.left += x;
586 obj->rgn->extents.right += x;
587 obj->rgn->extents.top += y;
588 obj->rgn->extents.bottom += y;
591 ret = get_region_type( obj );
592 GDI_ReleaseObj( hrgn );
593 return ret;
597 /***********************************************************************
598 * GetRgnBox (GDI32.@)
600 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
602 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
603 if (obj)
605 INT ret;
606 rect->left = obj->rgn->extents.left;
607 rect->top = obj->rgn->extents.top;
608 rect->right = obj->rgn->extents.right;
609 rect->bottom = obj->rgn->extents.bottom;
610 TRACE("%p (%ld,%ld-%ld,%ld)\n", hrgn,
611 rect->left, rect->top, rect->right, rect->bottom);
612 ret = get_region_type( obj );
613 GDI_ReleaseObj(hrgn);
614 return ret;
616 return ERROR;
620 /***********************************************************************
621 * CreateRectRgn (GDI32.@)
623 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
625 HRGN hrgn;
627 /* Allocate 2 rects by default to reduce the number of reallocs */
629 if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
630 return 0;
631 TRACE("%d,%d-%d,%d\n", left, top, right, bottom);
632 SetRectRgn(hrgn, left, top, right, bottom);
633 return hrgn;
637 /***********************************************************************
638 * CreateRectRgnIndirect (GDI32.@)
640 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
642 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
646 /***********************************************************************
647 * SetRectRgn (GDI32.@)
649 * Allows either or both left and top to be greater than right or bottom.
651 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
652 INT right, INT bottom )
654 RGNOBJ * obj;
656 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
658 if (!(obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
660 if (left > right) { INT tmp = left; left = right; right = tmp; }
661 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
663 if((left != right) && (top != bottom))
665 obj->rgn->rects->left = obj->rgn->extents.left = left;
666 obj->rgn->rects->top = obj->rgn->extents.top = top;
667 obj->rgn->rects->right = obj->rgn->extents.right = right;
668 obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
669 obj->rgn->numRects = 1;
671 else
672 EMPTY_REGION(obj->rgn);
674 GDI_ReleaseObj( hrgn );
675 return TRUE;
679 /***********************************************************************
680 * CreateRoundRectRgn (GDI32.@)
682 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
683 INT right, INT bottom,
684 INT ellipse_width, INT ellipse_height )
686 RGNOBJ * obj;
687 HRGN hrgn;
688 int asq, bsq, d, xd, yd;
689 RECT rect;
691 /* Make the dimensions sensible */
693 if (left > right) { INT tmp = left; left = right; right = tmp; }
694 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
696 ellipse_width = abs(ellipse_width);
697 ellipse_height = abs(ellipse_height);
699 /* Check parameters */
701 if (ellipse_width > right-left) ellipse_width = right-left;
702 if (ellipse_height > bottom-top) ellipse_height = bottom-top;
704 /* Check if we can do a normal rectangle instead */
706 if ((ellipse_width < 2) || (ellipse_height < 2))
707 return CreateRectRgn( left, top, right, bottom );
709 /* Create region */
711 d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
712 if (!(hrgn = REGION_CreateRegion(d))) return 0;
713 if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
714 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
715 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
717 /* Ellipse algorithm, based on an article by K. Porter */
718 /* in DDJ Graphics Programming Column, 8/89 */
720 asq = ellipse_width * ellipse_width / 4; /* a^2 */
721 bsq = ellipse_height * ellipse_height / 4; /* b^2 */
722 d = bsq - asq * ellipse_height / 2 + asq / 4; /* b^2 - a^2b + a^2/4 */
723 xd = 0;
724 yd = asq * ellipse_height; /* 2a^2b */
726 rect.left = left + ellipse_width / 2;
727 rect.right = right - ellipse_width / 2;
729 /* Loop to draw first half of quadrant */
731 while (xd < yd)
733 if (d > 0) /* if nearest pixel is toward the center */
735 /* move toward center */
736 rect.top = top++;
737 rect.bottom = rect.top + 1;
738 REGION_UnionRectWithRegion( &rect, obj->rgn );
739 rect.top = --bottom;
740 rect.bottom = rect.top + 1;
741 REGION_UnionRectWithRegion( &rect, obj->rgn );
742 yd -= 2*asq;
743 d -= yd;
745 rect.left--; /* next horiz point */
746 rect.right++;
747 xd += 2*bsq;
748 d += bsq + xd;
751 /* Loop to draw second half of quadrant */
753 d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
754 while (yd >= 0)
756 /* next vertical point */
757 rect.top = top++;
758 rect.bottom = rect.top + 1;
759 REGION_UnionRectWithRegion( &rect, obj->rgn );
760 rect.top = --bottom;
761 rect.bottom = rect.top + 1;
762 REGION_UnionRectWithRegion( &rect, obj->rgn );
763 if (d < 0) /* if nearest pixel is outside ellipse */
765 rect.left--; /* move away from center */
766 rect.right++;
767 xd += 2*bsq;
768 d += xd;
770 yd -= 2*asq;
771 d += asq - yd;
774 /* Add the inside rectangle */
776 if (top <= bottom)
778 rect.top = top;
779 rect.bottom = bottom;
780 REGION_UnionRectWithRegion( &rect, obj->rgn );
782 GDI_ReleaseObj( hrgn );
783 return hrgn;
787 /***********************************************************************
788 * CreateEllipticRgn (GDI32.@)
790 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
791 INT right, INT bottom )
793 return CreateRoundRectRgn( left, top, right, bottom,
794 right-left, bottom-top );
798 /***********************************************************************
799 * CreateEllipticRgnIndirect (GDI32.@)
801 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
803 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
804 rect->bottom, rect->right - rect->left,
805 rect->bottom - rect->top );
808 /***********************************************************************
809 * GetRegionData (GDI32.@)
811 * MSDN: GetRegionData, Return Values:
813 * "If the function succeeds and dwCount specifies an adequate number of bytes,
814 * the return value is always dwCount. If dwCount is too small or the function
815 * fails, the return value is 0. If lpRgnData is NULL, the return value is the
816 * required number of bytes.
818 * If the function fails, the return value is zero."
820 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
822 DWORD size;
823 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
825 TRACE(" %p count = %ld, rgndata = %p\n", hrgn, count, rgndata);
827 if(!obj) return 0;
829 size = obj->rgn->numRects * sizeof(RECT);
830 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
832 GDI_ReleaseObj( hrgn );
833 if (rgndata) /* buffer is too small, signal it by return 0 */
834 return 0;
835 else /* user requested buffer size with rgndata NULL */
836 return size + sizeof(RGNDATAHEADER);
839 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
840 rgndata->rdh.iType = RDH_RECTANGLES;
841 rgndata->rdh.nCount = obj->rgn->numRects;
842 rgndata->rdh.nRgnSize = size;
843 rgndata->rdh.rcBound.left = obj->rgn->extents.left;
844 rgndata->rdh.rcBound.top = obj->rgn->extents.top;
845 rgndata->rdh.rcBound.right = obj->rgn->extents.right;
846 rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
848 memcpy( rgndata->Buffer, obj->rgn->rects, size );
850 GDI_ReleaseObj( hrgn );
851 return size + sizeof(RGNDATAHEADER);
855 /***********************************************************************
856 * ExtCreateRegion (GDI32.@)
859 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
861 HRGN hrgn;
863 TRACE(" %p %ld %p = ", lpXform, dwCount, rgndata );
865 if( lpXform )
866 WARN("(Xform not implemented - ignored)\n");
868 if( rgndata->rdh.iType != RDH_RECTANGLES )
870 /* FIXME: We can use CreatePolyPolygonRgn() here
871 * for trapezoidal data */
873 WARN("(Unsupported region data)\n");
874 goto fail;
877 if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
879 RECT *pCurRect, *pEndRect;
880 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
882 if (obj) {
883 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
884 for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
885 REGION_UnionRectWithRegion( pCurRect, obj->rgn );
886 GDI_ReleaseObj( hrgn );
888 TRACE("%p\n", hrgn );
889 return hrgn;
891 else ERR("Could not get pointer to newborn Region!\n");
893 fail:
894 WARN("Failed\n");
895 return 0;
899 /***********************************************************************
900 * PtInRegion (GDI32.@)
902 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
904 RGNOBJ * obj;
905 BOOL ret = FALSE;
907 if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
909 int i;
911 if (obj->rgn->numRects > 0 && INRECT(obj->rgn->extents, x, y))
912 for (i = 0; i < obj->rgn->numRects; i++)
913 if (INRECT (obj->rgn->rects[i], x, y))
915 ret = TRUE;
916 break;
918 GDI_ReleaseObj( hrgn );
920 return ret;
924 /***********************************************************************
925 * RectInRegion (GDI32.@)
927 * Returns TRUE if rect is at least partly inside hrgn
929 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
931 RGNOBJ * obj;
932 BOOL ret = FALSE;
934 if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
936 RECT *pCurRect, *pRectEnd;
938 /* this is (just) a useful optimization */
939 if ((obj->rgn->numRects > 0) && EXTENTCHECK(&obj->rgn->extents,
940 rect))
942 for (pCurRect = obj->rgn->rects, pRectEnd = pCurRect +
943 obj->rgn->numRects; pCurRect < pRectEnd; pCurRect++)
945 if (pCurRect->bottom <= rect->top)
946 continue; /* not far enough down yet */
948 if (pCurRect->top >= rect->bottom)
949 break; /* too far down */
951 if (pCurRect->right <= rect->left)
952 continue; /* not far enough over yet */
954 if (pCurRect->left >= rect->right) {
955 continue;
958 ret = TRUE;
959 break;
962 GDI_ReleaseObj(hrgn);
964 return ret;
967 /***********************************************************************
968 * EqualRgn (GDI32.@)
970 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
972 RGNOBJ *obj1, *obj2;
973 BOOL ret = FALSE;
975 if ((obj1 = (RGNOBJ *) GDI_GetObjPtr( hrgn1, REGION_MAGIC )))
977 if ((obj2 = (RGNOBJ *) GDI_GetObjPtr( hrgn2, REGION_MAGIC )))
979 int i;
981 if ( obj1->rgn->numRects != obj2->rgn->numRects ) goto done;
982 if ( obj1->rgn->numRects == 0 )
984 ret = TRUE;
985 goto done;
988 if (obj1->rgn->extents.left != obj2->rgn->extents.left) goto done;
989 if (obj1->rgn->extents.right != obj2->rgn->extents.right) goto done;
990 if (obj1->rgn->extents.top != obj2->rgn->extents.top) goto done;
991 if (obj1->rgn->extents.bottom != obj2->rgn->extents.bottom) goto done;
992 for( i = 0; i < obj1->rgn->numRects; i++ )
994 if (obj1->rgn->rects[i].left != obj2->rgn->rects[i].left) goto done;
995 if (obj1->rgn->rects[i].right != obj2->rgn->rects[i].right) goto done;
996 if (obj1->rgn->rects[i].top != obj2->rgn->rects[i].top) goto done;
997 if (obj1->rgn->rects[i].bottom != obj2->rgn->rects[i].bottom) goto done;
999 ret = TRUE;
1000 done:
1001 GDI_ReleaseObj(hrgn2);
1003 GDI_ReleaseObj(hrgn1);
1005 return ret;
1008 /***********************************************************************
1009 * REGION_UnionRectWithRegion
1010 * Adds a rectangle to a WINEREGION
1012 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1014 WINEREGION region;
1016 region.rects = &region.extents;
1017 region.numRects = 1;
1018 region.size = 1;
1019 region.extents = *rect;
1020 REGION_UnionRegion(rgn, rgn, &region);
1024 /***********************************************************************
1025 * REGION_CreateFrameRgn
1027 * Create a region that is a frame around another region.
1028 * Expand all rectangles by +/- x and y, then subtract original region.
1030 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1032 BOOL bRet;
1033 RGNOBJ *srcObj = (RGNOBJ*) GDI_GetObjPtr( hSrc, REGION_MAGIC );
1035 if (!srcObj) return FALSE;
1036 if (srcObj->rgn->numRects != 0)
1038 RGNOBJ* destObj = (RGNOBJ*) GDI_GetObjPtr( hDest, REGION_MAGIC );
1039 RECT *pRect, *pEndRect;
1040 RECT tempRect;
1042 EMPTY_REGION( destObj->rgn );
1044 pEndRect = srcObj->rgn->rects + srcObj->rgn->numRects;
1045 for(pRect = srcObj->rgn->rects; pRect < pEndRect; pRect++)
1047 tempRect.left = pRect->left - x;
1048 tempRect.top = pRect->top - y;
1049 tempRect.right = pRect->right + x;
1050 tempRect.bottom = pRect->bottom + y;
1051 REGION_UnionRectWithRegion( &tempRect, destObj->rgn );
1053 REGION_SubtractRegion( destObj->rgn, destObj->rgn, srcObj->rgn );
1054 GDI_ReleaseObj ( hDest );
1055 bRet = TRUE;
1057 else
1058 bRet = FALSE;
1059 GDI_ReleaseObj( hSrc );
1060 return bRet;
1064 /***********************************************************************
1065 * CombineRgn (GDI32.@)
1067 * Note: The behavior is correct even if src and dest regions are the same.
1069 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1071 RGNOBJ *destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC);
1072 INT result = ERROR;
1074 TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1075 if (destObj)
1077 RGNOBJ *src1Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc1, REGION_MAGIC);
1079 if (src1Obj)
1081 TRACE("dump src1Obj:\n");
1082 if(TRACE_ON(region))
1083 REGION_DumpRegion(src1Obj->rgn);
1084 if (mode == RGN_COPY)
1086 REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
1087 result = get_region_type( destObj );
1089 else
1091 RGNOBJ *src2Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc2, REGION_MAGIC);
1093 if (src2Obj)
1095 TRACE("dump src2Obj:\n");
1096 if(TRACE_ON(region))
1097 REGION_DumpRegion(src2Obj->rgn);
1098 switch (mode)
1100 case RGN_AND:
1101 REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
1102 break;
1103 case RGN_OR:
1104 REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1105 break;
1106 case RGN_XOR:
1107 REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1108 break;
1109 case RGN_DIFF:
1110 REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1111 break;
1113 result = get_region_type( destObj );
1114 GDI_ReleaseObj( hSrc2 );
1117 GDI_ReleaseObj( hSrc1 );
1119 TRACE("dump destObj:\n");
1120 if(TRACE_ON(region))
1121 REGION_DumpRegion(destObj->rgn);
1123 GDI_ReleaseObj( hDest );
1124 } else {
1125 ERR("Invalid rgn=%p\n", hDest);
1127 return result;
1130 /***********************************************************************
1131 * REGION_SetExtents
1132 * Re-calculate the extents of a region
1134 static void REGION_SetExtents (WINEREGION *pReg)
1136 RECT *pRect, *pRectEnd, *pExtents;
1138 if (pReg->numRects == 0)
1140 pReg->extents.left = 0;
1141 pReg->extents.top = 0;
1142 pReg->extents.right = 0;
1143 pReg->extents.bottom = 0;
1144 return;
1147 pExtents = &pReg->extents;
1148 pRect = pReg->rects;
1149 pRectEnd = &pRect[pReg->numRects - 1];
1152 * Since pRect is the first rectangle in the region, it must have the
1153 * smallest top and since pRectEnd is the last rectangle in the region,
1154 * it must have the largest bottom, because of banding. Initialize left and
1155 * right from pRect and pRectEnd, resp., as good things to initialize them
1156 * to...
1158 pExtents->left = pRect->left;
1159 pExtents->top = pRect->top;
1160 pExtents->right = pRectEnd->right;
1161 pExtents->bottom = pRectEnd->bottom;
1163 while (pRect <= pRectEnd)
1165 if (pRect->left < pExtents->left)
1166 pExtents->left = pRect->left;
1167 if (pRect->right > pExtents->right)
1168 pExtents->right = pRect->right;
1169 pRect++;
1173 /***********************************************************************
1174 * REGION_CopyRegion
1176 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1178 if (dst != src) /* don't want to copy to itself */
1180 if (dst->size < src->numRects)
1182 if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1183 src->numRects * sizeof(RECT) )))
1184 return;
1185 dst->size = src->numRects;
1187 dst->numRects = src->numRects;
1188 dst->extents.left = src->extents.left;
1189 dst->extents.top = src->extents.top;
1190 dst->extents.right = src->extents.right;
1191 dst->extents.bottom = src->extents.bottom;
1192 memcpy((char *) dst->rects, (char *) src->rects,
1193 (int) (src->numRects * sizeof(RECT)));
1195 return;
1198 /***********************************************************************
1199 * REGION_Coalesce
1201 * Attempt to merge the rects in the current band with those in the
1202 * previous one. Used only by REGION_RegionOp.
1204 * Results:
1205 * The new index for the previous band.
1207 * Side Effects:
1208 * If coalescing takes place:
1209 * - rectangles in the previous band will have their bottom fields
1210 * altered.
1211 * - pReg->numRects will be decreased.
1214 static INT REGION_Coalesce (
1215 WINEREGION *pReg, /* Region to coalesce */
1216 INT prevStart, /* Index of start of previous band */
1217 INT curStart /* Index of start of current band */
1219 RECT *pPrevRect; /* Current rect in previous band */
1220 RECT *pCurRect; /* Current rect in current band */
1221 RECT *pRegEnd; /* End of region */
1222 INT curNumRects; /* Number of rectangles in current band */
1223 INT prevNumRects; /* Number of rectangles in previous band */
1224 INT bandtop; /* top coordinate for current band */
1226 pRegEnd = &pReg->rects[pReg->numRects];
1228 pPrevRect = &pReg->rects[prevStart];
1229 prevNumRects = curStart - prevStart;
1232 * Figure out how many rectangles are in the current band. Have to do
1233 * this because multiple bands could have been added in REGION_RegionOp
1234 * at the end when one region has been exhausted.
1236 pCurRect = &pReg->rects[curStart];
1237 bandtop = pCurRect->top;
1238 for (curNumRects = 0;
1239 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1240 curNumRects++)
1242 pCurRect++;
1245 if (pCurRect != pRegEnd)
1248 * If more than one band was added, we have to find the start
1249 * of the last band added so the next coalescing job can start
1250 * at the right place... (given when multiple bands are added,
1251 * this may be pointless -- see above).
1253 pRegEnd--;
1254 while (pRegEnd[-1].top == pRegEnd->top)
1256 pRegEnd--;
1258 curStart = pRegEnd - pReg->rects;
1259 pRegEnd = pReg->rects + pReg->numRects;
1262 if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1263 pCurRect -= curNumRects;
1265 * The bands may only be coalesced if the bottom of the previous
1266 * matches the top scanline of the current.
1268 if (pPrevRect->bottom == pCurRect->top)
1271 * Make sure the bands have rects in the same places. This
1272 * assumes that rects have been added in such a way that they
1273 * cover the most area possible. I.e. two rects in a band must
1274 * have some horizontal space between them.
1278 if ((pPrevRect->left != pCurRect->left) ||
1279 (pPrevRect->right != pCurRect->right))
1282 * The bands don't line up so they can't be coalesced.
1284 return (curStart);
1286 pPrevRect++;
1287 pCurRect++;
1288 prevNumRects -= 1;
1289 } while (prevNumRects != 0);
1291 pReg->numRects -= curNumRects;
1292 pCurRect -= curNumRects;
1293 pPrevRect -= curNumRects;
1296 * The bands may be merged, so set the bottom of each rect
1297 * in the previous band to that of the corresponding rect in
1298 * the current band.
1302 pPrevRect->bottom = pCurRect->bottom;
1303 pPrevRect++;
1304 pCurRect++;
1305 curNumRects -= 1;
1306 } while (curNumRects != 0);
1309 * If only one band was added to the region, we have to backup
1310 * curStart to the start of the previous band.
1312 * If more than one band was added to the region, copy the
1313 * other bands down. The assumption here is that the other bands
1314 * came from the same region as the current one and no further
1315 * coalescing can be done on them since it's all been done
1316 * already... curStart is already in the right place.
1318 if (pCurRect == pRegEnd)
1320 curStart = prevStart;
1322 else
1326 *pPrevRect++ = *pCurRect++;
1327 } while (pCurRect != pRegEnd);
1332 return (curStart);
1335 /***********************************************************************
1336 * REGION_RegionOp
1338 * Apply an operation to two regions. Called by REGION_Union,
1339 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
1341 * Results:
1342 * None.
1344 * Side Effects:
1345 * The new region is overwritten.
1347 * Notes:
1348 * The idea behind this function is to view the two regions as sets.
1349 * Together they cover a rectangle of area that this function divides
1350 * into horizontal bands where points are covered only by one region
1351 * or by both. For the first case, the nonOverlapFunc is called with
1352 * each the band and the band's upper and lower extents. For the
1353 * second, the overlapFunc is called to process the entire band. It
1354 * is responsible for clipping the rectangles in the band, though
1355 * this function provides the boundaries.
1356 * At the end of each band, the new region is coalesced, if possible,
1357 * to reduce the number of rectangles in the region.
1360 static void REGION_RegionOp(
1361 WINEREGION *newReg, /* Place to store result */
1362 WINEREGION *reg1, /* First region in operation */
1363 WINEREGION *reg2, /* 2nd region in operation */
1364 void (*overlapFunc)(), /* Function to call for over-lapping bands */
1365 void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
1366 void (*nonOverlap2Func)() /* Function to call for non-overlapping bands in region 2 */
1368 RECT *r1; /* Pointer into first region */
1369 RECT *r2; /* Pointer into 2d region */
1370 RECT *r1End; /* End of 1st region */
1371 RECT *r2End; /* End of 2d region */
1372 INT ybot; /* Bottom of intersection */
1373 INT ytop; /* Top of intersection */
1374 RECT *oldRects; /* Old rects for newReg */
1375 INT prevBand; /* Index of start of
1376 * previous band in newReg */
1377 INT curBand; /* Index of start of current
1378 * band in newReg */
1379 RECT *r1BandEnd; /* End of current band in r1 */
1380 RECT *r2BandEnd; /* End of current band in r2 */
1381 INT top; /* Top of non-overlapping band */
1382 INT bot; /* Bottom of non-overlapping band */
1385 * Initialization:
1386 * set r1, r2, r1End and r2End appropriately, preserve the important
1387 * parts of the destination region until the end in case it's one of
1388 * the two source regions, then mark the "new" region empty, allocating
1389 * another array of rectangles for it to use.
1391 r1 = reg1->rects;
1392 r2 = reg2->rects;
1393 r1End = r1 + reg1->numRects;
1394 r2End = r2 + reg2->numRects;
1398 * newReg may be one of the src regions so we can't empty it. We keep a
1399 * note of its rects pointer (so that we can free them later), preserve its
1400 * extents and simply set numRects to zero.
1403 oldRects = newReg->rects;
1404 newReg->numRects = 0;
1407 * Allocate a reasonable number of rectangles for the new region. The idea
1408 * is to allocate enough so the individual functions don't need to
1409 * reallocate and copy the array, which is time consuming, yet we don't
1410 * have to worry about using too much memory. I hope to be able to
1411 * nuke the Xrealloc() at the end of this function eventually.
1413 newReg->size = max(reg1->numRects,reg2->numRects) * 2;
1415 if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1416 sizeof(RECT) * newReg->size )))
1418 newReg->size = 0;
1419 return;
1423 * Initialize ybot and ytop.
1424 * In the upcoming loop, ybot and ytop serve different functions depending
1425 * on whether the band being handled is an overlapping or non-overlapping
1426 * band.
1427 * In the case of a non-overlapping band (only one of the regions
1428 * has points in the band), ybot is the bottom of the most recent
1429 * intersection and thus clips the top of the rectangles in that band.
1430 * ytop is the top of the next intersection between the two regions and
1431 * serves to clip the bottom of the rectangles in the current band.
1432 * For an overlapping band (where the two regions intersect), ytop clips
1433 * the top of the rectangles of both regions and ybot clips the bottoms.
1435 if (reg1->extents.top < reg2->extents.top)
1436 ybot = reg1->extents.top;
1437 else
1438 ybot = reg2->extents.top;
1441 * prevBand serves to mark the start of the previous band so rectangles
1442 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1443 * In the beginning, there is no previous band, so prevBand == curBand
1444 * (curBand is set later on, of course, but the first band will always
1445 * start at index 0). prevBand and curBand must be indices because of
1446 * the possible expansion, and resultant moving, of the new region's
1447 * array of rectangles.
1449 prevBand = 0;
1453 curBand = newReg->numRects;
1456 * This algorithm proceeds one source-band (as opposed to a
1457 * destination band, which is determined by where the two regions
1458 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1459 * rectangle after the last one in the current band for their
1460 * respective regions.
1462 r1BandEnd = r1;
1463 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1465 r1BandEnd++;
1468 r2BandEnd = r2;
1469 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1471 r2BandEnd++;
1475 * First handle the band that doesn't intersect, if any.
1477 * Note that attention is restricted to one band in the
1478 * non-intersecting region at once, so if a region has n
1479 * bands between the current position and the next place it overlaps
1480 * the other, this entire loop will be passed through n times.
1482 if (r1->top < r2->top)
1484 top = max(r1->top,ybot);
1485 bot = min(r1->bottom,r2->top);
1487 if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
1489 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1492 ytop = r2->top;
1494 else if (r2->top < r1->top)
1496 top = max(r2->top,ybot);
1497 bot = min(r2->bottom,r1->top);
1499 if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
1501 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1504 ytop = r1->top;
1506 else
1508 ytop = r1->top;
1512 * If any rectangles got added to the region, try and coalesce them
1513 * with rectangles from the previous band. Note we could just do
1514 * this test in miCoalesce, but some machines incur a not
1515 * inconsiderable cost for function calls, so...
1517 if (newReg->numRects != curBand)
1519 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1523 * Now see if we've hit an intersecting band. The two bands only
1524 * intersect if ybot > ytop
1526 ybot = min(r1->bottom, r2->bottom);
1527 curBand = newReg->numRects;
1528 if (ybot > ytop)
1530 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1534 if (newReg->numRects != curBand)
1536 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1540 * If we've finished with a band (bottom == ybot) we skip forward
1541 * in the region to the next band.
1543 if (r1->bottom == ybot)
1545 r1 = r1BandEnd;
1547 if (r2->bottom == ybot)
1549 r2 = r2BandEnd;
1551 } while ((r1 != r1End) && (r2 != r2End));
1554 * Deal with whichever region still has rectangles left.
1556 curBand = newReg->numRects;
1557 if (r1 != r1End)
1559 if (nonOverlap1Func != (void (*)())NULL)
1563 r1BandEnd = r1;
1564 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1566 r1BandEnd++;
1568 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1569 max(r1->top,ybot), r1->bottom);
1570 r1 = r1BandEnd;
1571 } while (r1 != r1End);
1574 else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
1578 r2BandEnd = r2;
1579 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1581 r2BandEnd++;
1583 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1584 max(r2->top,ybot), r2->bottom);
1585 r2 = r2BandEnd;
1586 } while (r2 != r2End);
1589 if (newReg->numRects != curBand)
1591 (void) REGION_Coalesce (newReg, prevBand, curBand);
1595 * A bit of cleanup. To keep regions from growing without bound,
1596 * we shrink the array of rectangles to match the new number of
1597 * rectangles in the region. This never goes to 0, however...
1599 * Only do this stuff if the number of rectangles allocated is more than
1600 * twice the number of rectangles in the region (a simple optimization...).
1602 if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1604 if (REGION_NOT_EMPTY(newReg))
1606 RECT *prev_rects = newReg->rects;
1607 newReg->size = newReg->numRects;
1608 newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1609 sizeof(RECT) * newReg->size );
1610 if (! newReg->rects)
1611 newReg->rects = prev_rects;
1613 else
1616 * No point in doing the extra work involved in an Xrealloc if
1617 * the region is empty
1619 newReg->size = 1;
1620 HeapFree( GetProcessHeap(), 0, newReg->rects );
1621 newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
1624 HeapFree( GetProcessHeap(), 0, oldRects );
1625 return;
1628 /***********************************************************************
1629 * Region Intersection
1630 ***********************************************************************/
1633 /***********************************************************************
1634 * REGION_IntersectO
1636 * Handle an overlapping band for REGION_Intersect.
1638 * Results:
1639 * None.
1641 * Side Effects:
1642 * Rectangles may be added to the region.
1645 static void REGION_IntersectO(WINEREGION *pReg, RECT *r1, RECT *r1End,
1646 RECT *r2, RECT *r2End, INT top, INT bottom)
1649 INT left, right;
1650 RECT *pNextRect;
1652 pNextRect = &pReg->rects[pReg->numRects];
1654 while ((r1 != r1End) && (r2 != r2End))
1656 left = max(r1->left, r2->left);
1657 right = min(r1->right, r2->right);
1660 * If there's any overlap between the two rectangles, add that
1661 * overlap to the new region.
1662 * There's no need to check for subsumption because the only way
1663 * such a need could arise is if some region has two rectangles
1664 * right next to each other. Since that should never happen...
1666 if (left < right)
1668 MEMCHECK(pReg, pNextRect, pReg->rects);
1669 pNextRect->left = left;
1670 pNextRect->top = top;
1671 pNextRect->right = right;
1672 pNextRect->bottom = bottom;
1673 pReg->numRects += 1;
1674 pNextRect++;
1678 * Need to advance the pointers. Shift the one that extends
1679 * to the right the least, since the other still has a chance to
1680 * overlap with that region's next rectangle, if you see what I mean.
1682 if (r1->right < r2->right)
1684 r1++;
1686 else if (r2->right < r1->right)
1688 r2++;
1690 else
1692 r1++;
1693 r2++;
1696 return;
1699 /***********************************************************************
1700 * REGION_IntersectRegion
1702 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1703 WINEREGION *reg2)
1705 /* check for trivial reject */
1706 if ( (!(reg1->numRects)) || (!(reg2->numRects)) ||
1707 (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
1708 newReg->numRects = 0;
1709 else
1710 REGION_RegionOp (newReg, reg1, reg2,
1711 (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
1714 * Can't alter newReg's extents before we call miRegionOp because
1715 * it might be one of the source regions and miRegionOp depends
1716 * on the extents of those regions being the same. Besides, this
1717 * way there's no checking against rectangles that will be nuked
1718 * due to coalescing, so we have to examine fewer rectangles.
1720 REGION_SetExtents(newReg);
1723 /***********************************************************************
1724 * Region Union
1725 ***********************************************************************/
1727 /***********************************************************************
1728 * REGION_UnionNonO
1730 * Handle a non-overlapping band for the union operation. Just
1731 * Adds the rectangles into the region. Doesn't have to check for
1732 * subsumption or anything.
1734 * Results:
1735 * None.
1737 * Side Effects:
1738 * pReg->numRects is incremented and the final rectangles overwritten
1739 * with the rectangles we're passed.
1742 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1743 INT top, INT bottom)
1745 RECT *pNextRect;
1747 pNextRect = &pReg->rects[pReg->numRects];
1749 while (r != rEnd)
1751 MEMCHECK(pReg, pNextRect, pReg->rects);
1752 pNextRect->left = r->left;
1753 pNextRect->top = top;
1754 pNextRect->right = r->right;
1755 pNextRect->bottom = bottom;
1756 pReg->numRects += 1;
1757 pNextRect++;
1758 r++;
1760 return;
1763 /***********************************************************************
1764 * REGION_UnionO
1766 * Handle an overlapping band for the union operation. Picks the
1767 * left-most rectangle each time and merges it into the region.
1769 * Results:
1770 * None.
1772 * Side Effects:
1773 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1774 * be changed.
1777 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1778 RECT *r2, RECT *r2End, INT top, INT bottom)
1780 RECT *pNextRect;
1782 pNextRect = &pReg->rects[pReg->numRects];
1784 #define MERGERECT(r) \
1785 if ((pReg->numRects != 0) && \
1786 (pNextRect[-1].top == top) && \
1787 (pNextRect[-1].bottom == bottom) && \
1788 (pNextRect[-1].right >= r->left)) \
1790 if (pNextRect[-1].right < r->right) \
1792 pNextRect[-1].right = r->right; \
1795 else \
1797 MEMCHECK(pReg, pNextRect, pReg->rects); \
1798 pNextRect->top = top; \
1799 pNextRect->bottom = bottom; \
1800 pNextRect->left = r->left; \
1801 pNextRect->right = r->right; \
1802 pReg->numRects += 1; \
1803 pNextRect += 1; \
1805 r++;
1807 while ((r1 != r1End) && (r2 != r2End))
1809 if (r1->left < r2->left)
1811 MERGERECT(r1);
1813 else
1815 MERGERECT(r2);
1819 if (r1 != r1End)
1823 MERGERECT(r1);
1824 } while (r1 != r1End);
1826 else while (r2 != r2End)
1828 MERGERECT(r2);
1830 return;
1833 /***********************************************************************
1834 * REGION_UnionRegion
1836 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
1837 WINEREGION *reg2)
1839 /* checks all the simple cases */
1842 * Region 1 and 2 are the same or region 1 is empty
1844 if ( (reg1 == reg2) || (!(reg1->numRects)) )
1846 if (newReg != reg2)
1847 REGION_CopyRegion(newReg, reg2);
1848 return;
1852 * if nothing to union (region 2 empty)
1854 if (!(reg2->numRects))
1856 if (newReg != reg1)
1857 REGION_CopyRegion(newReg, reg1);
1858 return;
1862 * Region 1 completely subsumes region 2
1864 if ((reg1->numRects == 1) &&
1865 (reg1->extents.left <= reg2->extents.left) &&
1866 (reg1->extents.top <= reg2->extents.top) &&
1867 (reg1->extents.right >= reg2->extents.right) &&
1868 (reg1->extents.bottom >= reg2->extents.bottom))
1870 if (newReg != reg1)
1871 REGION_CopyRegion(newReg, reg1);
1872 return;
1876 * Region 2 completely subsumes region 1
1878 if ((reg2->numRects == 1) &&
1879 (reg2->extents.left <= reg1->extents.left) &&
1880 (reg2->extents.top <= reg1->extents.top) &&
1881 (reg2->extents.right >= reg1->extents.right) &&
1882 (reg2->extents.bottom >= reg1->extents.bottom))
1884 if (newReg != reg2)
1885 REGION_CopyRegion(newReg, reg2);
1886 return;
1889 REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
1890 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
1892 newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
1893 newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
1894 newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
1895 newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
1898 /***********************************************************************
1899 * Region Subtraction
1900 ***********************************************************************/
1902 /***********************************************************************
1903 * REGION_SubtractNonO1
1905 * Deal with non-overlapping band for subtraction. Any parts from
1906 * region 2 we discard. Anything from region 1 we add to the region.
1908 * Results:
1909 * None.
1911 * Side Effects:
1912 * pReg may be affected.
1915 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
1916 INT top, INT bottom)
1918 RECT *pNextRect;
1920 pNextRect = &pReg->rects[pReg->numRects];
1922 while (r != rEnd)
1924 MEMCHECK(pReg, pNextRect, pReg->rects);
1925 pNextRect->left = r->left;
1926 pNextRect->top = top;
1927 pNextRect->right = r->right;
1928 pNextRect->bottom = bottom;
1929 pReg->numRects += 1;
1930 pNextRect++;
1931 r++;
1933 return;
1937 /***********************************************************************
1938 * REGION_SubtractO
1940 * Overlapping band subtraction. x1 is the left-most point not yet
1941 * checked.
1943 * Results:
1944 * None.
1946 * Side Effects:
1947 * pReg may have rectangles added to it.
1950 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1951 RECT *r2, RECT *r2End, INT top, INT bottom)
1953 RECT *pNextRect;
1954 INT left;
1956 left = r1->left;
1957 pNextRect = &pReg->rects[pReg->numRects];
1959 while ((r1 != r1End) && (r2 != r2End))
1961 if (r2->right <= left)
1964 * Subtrahend missed the boat: go to next subtrahend.
1966 r2++;
1968 else if (r2->left <= left)
1971 * Subtrahend preceeds minuend: nuke left edge of minuend.
1973 left = r2->right;
1974 if (left >= r1->right)
1977 * Minuend completely covered: advance to next minuend and
1978 * reset left fence to edge of new minuend.
1980 r1++;
1981 if (r1 != r1End)
1982 left = r1->left;
1984 else
1987 * Subtrahend now used up since it doesn't extend beyond
1988 * minuend
1990 r2++;
1993 else if (r2->left < r1->right)
1996 * Left part of subtrahend covers part of minuend: add uncovered
1997 * part of minuend to region and skip to next subtrahend.
1999 MEMCHECK(pReg, pNextRect, pReg->rects);
2000 pNextRect->left = left;
2001 pNextRect->top = top;
2002 pNextRect->right = r2->left;
2003 pNextRect->bottom = bottom;
2004 pReg->numRects += 1;
2005 pNextRect++;
2006 left = r2->right;
2007 if (left >= r1->right)
2010 * Minuend used up: advance to new...
2012 r1++;
2013 if (r1 != r1End)
2014 left = r1->left;
2016 else
2019 * Subtrahend used up
2021 r2++;
2024 else
2027 * Minuend used up: add any remaining piece before advancing.
2029 if (r1->right > left)
2031 MEMCHECK(pReg, pNextRect, pReg->rects);
2032 pNextRect->left = left;
2033 pNextRect->top = top;
2034 pNextRect->right = r1->right;
2035 pNextRect->bottom = bottom;
2036 pReg->numRects += 1;
2037 pNextRect++;
2039 r1++;
2040 left = r1->left;
2045 * Add remaining minuend rectangles to region.
2047 while (r1 != r1End)
2049 MEMCHECK(pReg, pNextRect, pReg->rects);
2050 pNextRect->left = left;
2051 pNextRect->top = top;
2052 pNextRect->right = r1->right;
2053 pNextRect->bottom = bottom;
2054 pReg->numRects += 1;
2055 pNextRect++;
2056 r1++;
2057 if (r1 != r1End)
2059 left = r1->left;
2062 return;
2065 /***********************************************************************
2066 * REGION_SubtractRegion
2068 * Subtract regS from regM and leave the result in regD.
2069 * S stands for subtrahend, M for minuend and D for difference.
2071 * Results:
2072 * TRUE.
2074 * Side Effects:
2075 * regD is overwritten.
2078 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
2079 WINEREGION *regS )
2081 /* check for trivial reject */
2082 if ( (!(regM->numRects)) || (!(regS->numRects)) ||
2083 (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2085 REGION_CopyRegion(regD, regM);
2086 return;
2089 REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
2090 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
2093 * Can't alter newReg's extents before we call miRegionOp because
2094 * it might be one of the source regions and miRegionOp depends
2095 * on the extents of those regions being the unaltered. Besides, this
2096 * way there's no checking against rectangles that will be nuked
2097 * due to coalescing, so we have to examine fewer rectangles.
2099 REGION_SetExtents (regD);
2102 /***********************************************************************
2103 * REGION_XorRegion
2105 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
2106 WINEREGION *srb)
2108 WINEREGION *tra, *trb;
2110 if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
2111 (! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
2112 return;
2113 REGION_SubtractRegion(tra,sra,srb);
2114 REGION_SubtractRegion(trb,srb,sra);
2115 REGION_UnionRegion(dr,tra,trb);
2116 REGION_DestroyWineRegion(tra);
2117 REGION_DestroyWineRegion(trb);
2118 return;
2121 /**************************************************************************
2123 * Poly Regions
2125 *************************************************************************/
2127 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
2128 #define SMALL_COORDINATE 0x80000000
2130 /***********************************************************************
2131 * REGION_InsertEdgeInET
2133 * Insert the given edge into the edge table.
2134 * First we must find the correct bucket in the
2135 * Edge table, then find the right slot in the
2136 * bucket. Finally, we can insert it.
2139 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2140 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2143 EdgeTableEntry *start, *prev;
2144 ScanLineList *pSLL, *pPrevSLL;
2145 ScanLineListBlock *tmpSLLBlock;
2148 * find the right bucket to put the edge into
2150 pPrevSLL = &ET->scanlines;
2151 pSLL = pPrevSLL->next;
2152 while (pSLL && (pSLL->scanline < scanline))
2154 pPrevSLL = pSLL;
2155 pSLL = pSLL->next;
2159 * reassign pSLL (pointer to ScanLineList) if necessary
2161 if ((!pSLL) || (pSLL->scanline > scanline))
2163 if (*iSLLBlock > SLLSPERBLOCK-1)
2165 tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2166 if(!tmpSLLBlock)
2168 WARN("Can't alloc SLLB\n");
2169 return;
2171 (*SLLBlock)->next = tmpSLLBlock;
2172 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
2173 *SLLBlock = tmpSLLBlock;
2174 *iSLLBlock = 0;
2176 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2178 pSLL->next = pPrevSLL->next;
2179 pSLL->edgelist = (EdgeTableEntry *)NULL;
2180 pPrevSLL->next = pSLL;
2182 pSLL->scanline = scanline;
2185 * now insert the edge in the right bucket
2187 prev = (EdgeTableEntry *)NULL;
2188 start = pSLL->edgelist;
2189 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2191 prev = start;
2192 start = start->next;
2194 ETE->next = start;
2196 if (prev)
2197 prev->next = ETE;
2198 else
2199 pSLL->edgelist = ETE;
2202 /***********************************************************************
2203 * REGION_CreateEdgeTable
2205 * This routine creates the edge table for
2206 * scan converting polygons.
2207 * The Edge Table (ET) looks like:
2209 * EdgeTable
2210 * --------
2211 * | ymax | ScanLineLists
2212 * |scanline|-->------------>-------------->...
2213 * -------- |scanline| |scanline|
2214 * |edgelist| |edgelist|
2215 * --------- ---------
2216 * | |
2217 * | |
2218 * V V
2219 * list of ETEs list of ETEs
2221 * where ETE is an EdgeTableEntry data structure,
2222 * and there is one ScanLineList per scanline at
2223 * which an edge is initially entered.
2226 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2227 const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2228 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2230 const POINT *top, *bottom;
2231 const POINT *PrevPt, *CurrPt, *EndPt;
2232 INT poly, count;
2233 int iSLLBlock = 0;
2234 int dy;
2238 * initialize the Active Edge Table
2240 AET->next = (EdgeTableEntry *)NULL;
2241 AET->back = (EdgeTableEntry *)NULL;
2242 AET->nextWETE = (EdgeTableEntry *)NULL;
2243 AET->bres.minor_axis = SMALL_COORDINATE;
2246 * initialize the Edge Table.
2248 ET->scanlines.next = (ScanLineList *)NULL;
2249 ET->ymax = SMALL_COORDINATE;
2250 ET->ymin = LARGE_COORDINATE;
2251 pSLLBlock->next = (ScanLineListBlock *)NULL;
2253 EndPt = pts - 1;
2254 for(poly = 0; poly < nbpolygons; poly++)
2256 count = Count[poly];
2257 EndPt += count;
2258 if(count < 2)
2259 continue;
2261 PrevPt = EndPt;
2264 * for each vertex in the array of points.
2265 * In this loop we are dealing with two vertices at
2266 * a time -- these make up one edge of the polygon.
2268 while (count--)
2270 CurrPt = pts++;
2273 * find out which point is above and which is below.
2275 if (PrevPt->y > CurrPt->y)
2277 bottom = PrevPt, top = CurrPt;
2278 pETEs->ClockWise = 0;
2280 else
2282 bottom = CurrPt, top = PrevPt;
2283 pETEs->ClockWise = 1;
2287 * don't add horizontal edges to the Edge table.
2289 if (bottom->y != top->y)
2291 pETEs->ymax = bottom->y-1;
2292 /* -1 so we don't get last scanline */
2295 * initialize integer edge algorithm
2297 dy = bottom->y - top->y;
2298 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2300 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2301 &iSLLBlock);
2303 if (PrevPt->y > ET->ymax)
2304 ET->ymax = PrevPt->y;
2305 if (PrevPt->y < ET->ymin)
2306 ET->ymin = PrevPt->y;
2307 pETEs++;
2310 PrevPt = CurrPt;
2315 /***********************************************************************
2316 * REGION_loadAET
2318 * This routine moves EdgeTableEntries from the
2319 * EdgeTable into the Active Edge Table,
2320 * leaving them sorted by smaller x coordinate.
2323 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2325 EdgeTableEntry *pPrevAET;
2326 EdgeTableEntry *tmp;
2328 pPrevAET = AET;
2329 AET = AET->next;
2330 while (ETEs)
2332 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2334 pPrevAET = AET;
2335 AET = AET->next;
2337 tmp = ETEs->next;
2338 ETEs->next = AET;
2339 if (AET)
2340 AET->back = ETEs;
2341 ETEs->back = pPrevAET;
2342 pPrevAET->next = ETEs;
2343 pPrevAET = ETEs;
2345 ETEs = tmp;
2349 /***********************************************************************
2350 * REGION_computeWAET
2352 * This routine links the AET by the
2353 * nextWETE (winding EdgeTableEntry) link for
2354 * use by the winding number rule. The final
2355 * Active Edge Table (AET) might look something
2356 * like:
2358 * AET
2359 * ---------- --------- ---------
2360 * |ymax | |ymax | |ymax |
2361 * | ... | |... | |... |
2362 * |next |->|next |->|next |->...
2363 * |nextWETE| |nextWETE| |nextWETE|
2364 * --------- --------- ^--------
2365 * | | |
2366 * V-------------------> V---> ...
2369 static void REGION_computeWAET(EdgeTableEntry *AET)
2371 register EdgeTableEntry *pWETE;
2372 register int inside = 1;
2373 register int isInside = 0;
2375 AET->nextWETE = (EdgeTableEntry *)NULL;
2376 pWETE = AET;
2377 AET = AET->next;
2378 while (AET)
2380 if (AET->ClockWise)
2381 isInside++;
2382 else
2383 isInside--;
2385 if ((!inside && !isInside) ||
2386 ( inside && isInside))
2388 pWETE->nextWETE = AET;
2389 pWETE = AET;
2390 inside = !inside;
2392 AET = AET->next;
2394 pWETE->nextWETE = (EdgeTableEntry *)NULL;
2397 /***********************************************************************
2398 * REGION_InsertionSort
2400 * Just a simple insertion sort using
2401 * pointers and back pointers to sort the Active
2402 * Edge Table.
2405 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2407 EdgeTableEntry *pETEchase;
2408 EdgeTableEntry *pETEinsert;
2409 EdgeTableEntry *pETEchaseBackTMP;
2410 BOOL changed = FALSE;
2412 AET = AET->next;
2413 while (AET)
2415 pETEinsert = AET;
2416 pETEchase = AET;
2417 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2418 pETEchase = pETEchase->back;
2420 AET = AET->next;
2421 if (pETEchase != pETEinsert)
2423 pETEchaseBackTMP = pETEchase->back;
2424 pETEinsert->back->next = AET;
2425 if (AET)
2426 AET->back = pETEinsert->back;
2427 pETEinsert->next = pETEchase;
2428 pETEchase->back->next = pETEinsert;
2429 pETEchase->back = pETEinsert;
2430 pETEinsert->back = pETEchaseBackTMP;
2431 changed = TRUE;
2434 return changed;
2437 /***********************************************************************
2438 * REGION_FreeStorage
2440 * Clean up our act.
2442 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2444 ScanLineListBlock *tmpSLLBlock;
2446 while (pSLLBlock)
2448 tmpSLLBlock = pSLLBlock->next;
2449 HeapFree( GetProcessHeap(), 0, pSLLBlock );
2450 pSLLBlock = tmpSLLBlock;
2455 /***********************************************************************
2456 * REGION_PtsToRegion
2458 * Create an array of rectangles from a list of points.
2460 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2461 POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2463 RECT *rects;
2464 POINT *pts;
2465 POINTBLOCK *CurPtBlock;
2466 int i;
2467 RECT *extents;
2468 INT numRects;
2470 extents = &reg->extents;
2472 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2474 if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2475 sizeof(RECT) * numRects )))
2476 return(0);
2478 reg->size = numRects;
2479 CurPtBlock = FirstPtBlock;
2480 rects = reg->rects - 1;
2481 numRects = 0;
2482 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2484 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2485 /* the loop uses 2 points per iteration */
2486 i = NUMPTSTOBUFFER >> 1;
2487 if (!numFullPtBlocks)
2488 i = iCurPtBlock >> 1;
2489 for (pts = CurPtBlock->pts; i--; pts += 2) {
2490 if (pts->x == pts[1].x)
2491 continue;
2492 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2493 pts[1].x == rects->right &&
2494 (numRects == 1 || rects[-1].top != rects->top) &&
2495 (i && pts[2].y > pts[1].y)) {
2496 rects->bottom = pts[1].y + 1;
2497 continue;
2499 numRects++;
2500 rects++;
2501 rects->left = pts->x; rects->top = pts->y;
2502 rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
2503 if (rects->left < extents->left)
2504 extents->left = rects->left;
2505 if (rects->right > extents->right)
2506 extents->right = rects->right;
2508 CurPtBlock = CurPtBlock->next;
2511 if (numRects) {
2512 extents->top = reg->rects->top;
2513 extents->bottom = rects->bottom;
2514 } else {
2515 extents->left = 0;
2516 extents->top = 0;
2517 extents->right = 0;
2518 extents->bottom = 0;
2520 reg->numRects = numRects;
2522 return(TRUE);
2525 /***********************************************************************
2526 * CreatePolyPolygonRgn (GDI32.@)
2528 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2529 INT nbpolygons, INT mode)
2531 HRGN hrgn;
2532 RGNOBJ *obj;
2533 WINEREGION *region;
2534 register EdgeTableEntry *pAET; /* Active Edge Table */
2535 register INT y; /* current scanline */
2536 register int iPts = 0; /* number of pts in buffer */
2537 register EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
2538 register ScanLineList *pSLL; /* current scanLineList */
2539 register POINT *pts; /* output buffer */
2540 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
2541 EdgeTable ET; /* header node for ET */
2542 EdgeTableEntry AET; /* header node for AET */
2543 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
2544 ScanLineListBlock SLLBlock; /* header for scanlinelist */
2545 int fixWAET = FALSE;
2546 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
2547 POINTBLOCK *tmpPtBlock;
2548 int numFullPtBlocks = 0;
2549 INT poly, total;
2551 if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2552 return 0;
2553 obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
2554 region = obj->rgn;
2556 /* special case a rectangle */
2558 if (((nbpolygons == 1) && ((*Count == 4) ||
2559 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2560 (((Pts[0].y == Pts[1].y) &&
2561 (Pts[1].x == Pts[2].x) &&
2562 (Pts[2].y == Pts[3].y) &&
2563 (Pts[3].x == Pts[0].x)) ||
2564 ((Pts[0].x == Pts[1].x) &&
2565 (Pts[1].y == Pts[2].y) &&
2566 (Pts[2].x == Pts[3].x) &&
2567 (Pts[3].y == Pts[0].y))))
2569 SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2570 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2571 GDI_ReleaseObj( hrgn );
2572 return hrgn;
2575 for(poly = total = 0; poly < nbpolygons; poly++)
2576 total += Count[poly];
2577 if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2579 REGION_DeleteObject( hrgn, obj );
2580 return 0;
2582 pts = FirstPtBlock.pts;
2583 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2584 pSLL = ET.scanlines.next;
2585 curPtBlock = &FirstPtBlock;
2587 if (mode != WINDING) {
2589 * for each scanline
2591 for (y = ET.ymin; y < ET.ymax; y++) {
2593 * Add a new edge to the active edge table when we
2594 * get to the next edge.
2596 if (pSLL != NULL && y == pSLL->scanline) {
2597 REGION_loadAET(&AET, pSLL->edgelist);
2598 pSLL = pSLL->next;
2600 pPrevAET = &AET;
2601 pAET = AET.next;
2604 * for each active edge
2606 while (pAET) {
2607 pts->x = pAET->bres.minor_axis, pts->y = y;
2608 pts++, iPts++;
2611 * send out the buffer
2613 if (iPts == NUMPTSTOBUFFER) {
2614 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2615 if(!tmpPtBlock) {
2616 WARN("Can't alloc tPB\n");
2617 return 0;
2619 curPtBlock->next = tmpPtBlock;
2620 curPtBlock = tmpPtBlock;
2621 pts = curPtBlock->pts;
2622 numFullPtBlocks++;
2623 iPts = 0;
2625 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2627 REGION_InsertionSort(&AET);
2630 else {
2632 * for each scanline
2634 for (y = ET.ymin; y < ET.ymax; y++) {
2636 * Add a new edge to the active edge table when we
2637 * get to the next edge.
2639 if (pSLL != NULL && y == pSLL->scanline) {
2640 REGION_loadAET(&AET, pSLL->edgelist);
2641 REGION_computeWAET(&AET);
2642 pSLL = pSLL->next;
2644 pPrevAET = &AET;
2645 pAET = AET.next;
2646 pWETE = pAET;
2649 * for each active edge
2651 while (pAET) {
2653 * add to the buffer only those edges that
2654 * are in the Winding active edge table.
2656 if (pWETE == pAET) {
2657 pts->x = pAET->bres.minor_axis, pts->y = y;
2658 pts++, iPts++;
2661 * send out the buffer
2663 if (iPts == NUMPTSTOBUFFER) {
2664 tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2665 sizeof(POINTBLOCK) );
2666 if(!tmpPtBlock) {
2667 WARN("Can't alloc tPB\n");
2668 REGION_DeleteObject( hrgn, obj );
2669 return 0;
2671 curPtBlock->next = tmpPtBlock;
2672 curPtBlock = tmpPtBlock;
2673 pts = curPtBlock->pts;
2674 numFullPtBlocks++; iPts = 0;
2676 pWETE = pWETE->nextWETE;
2678 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2682 * recompute the winding active edge table if
2683 * we just resorted or have exited an edge.
2685 if (REGION_InsertionSort(&AET) || fixWAET) {
2686 REGION_computeWAET(&AET);
2687 fixWAET = FALSE;
2691 REGION_FreeStorage(SLLBlock.next);
2692 REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2694 for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2695 tmpPtBlock = curPtBlock->next;
2696 HeapFree( GetProcessHeap(), 0, curPtBlock );
2697 curPtBlock = tmpPtBlock;
2699 HeapFree( GetProcessHeap(), 0, pETEs );
2700 GDI_ReleaseObj( hrgn );
2701 return hrgn;
2705 /***********************************************************************
2706 * CreatePolygonRgn (GDI32.@)
2708 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2709 INT mode )
2711 return CreatePolyPolygonRgn( points, &count, 1, mode );