2 * ReactOS W32 Subsystem
3 * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 ReactOS Team
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
21 * GDI region objects. Shamelessly ripped out from the X11 distribution
22 * Thanks for the nice licence.
24 * Copyright 1993, 1994, 1995 Alexandre Julliard
25 * Modifications and additions: Copyright 1998 Huw Davies
28 * This library is free software; you can redistribute it and/or
29 * modify it under the terms of the GNU Lesser General Public
30 * License as published by the Free Software Foundation; either
31 * version 2.1 of the License, or (at your option) any later version.
33 * This library is distributed in the hope that it will be useful,
34 * but WITHOUT ANY WARRANTY; without even the implied warranty of
35 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
36 * Lesser General Public License for more details.
38 * You should have received a copy of the GNU Lesser General Public
39 * License along with this library; if not, write to the Free Software
40 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
43 /************************************************************************
45 Copyright (c) 1987, 1988 X Consortium
47 Permission is hereby granted, free of charge, to any person obtaining a copy
48 of this software and associated documentation files (the "Software"), to deal
49 in the Software without restriction, including without limitation the rights
50 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
51 copies of the Software, and to permit persons to whom the Software is
52 furnished to do so, subject to the following conditions:
54 The above copyright notice and this permission notice shall be included in
55 all copies or substantial portions of the Software.
57 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
58 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
59 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
60 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
61 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
62 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
64 Except as contained in this notice, the name of the X Consortium shall not be
65 used in advertising or otherwise to promote the sale, use or other dealings
66 in this Software without prior written authorization from the X Consortium.
69 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
73 Permission to use, copy, modify, and distribute this software and its
74 documentation for any purpose and without fee is hereby granted,
75 provided that the above copyright notice appear in all copies and that
76 both that copyright notice and this permission notice appear in
77 supporting documentation, and that the name of Digital not be
78 used in advertising or publicity pertaining to distribution of the
79 software without specific, written prior permission.
81 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
82 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
83 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
84 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
85 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
86 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
89 ************************************************************************/
91 * The functions in this file implement the Region abstraction, similar to one
92 * used in the X11 sample server. A Region is simply an area, as the name
93 * implies, and is implemented as a "y-x-banded" array of rectangles. To
94 * explain: Each Region is made up of a certain number of rectangles sorted
95 * by y coordinate first, and then by x coordinate.
97 * Furthermore, the rectangles are banded such that every rectangle with a
98 * given upper-left y coordinate (y1) will have the same lower-right y
99 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
100 * will span the entire vertical distance of the band. This means that some
101 * areas that could be merged into a taller rectangle will be represented as
102 * several shorter rectangles to account for shorter rectangles to its left
103 * or right but within its "vertical scope".
105 * An added constraint on the rectangles is that they must cover as much
106 * horizontal area as possible. E.g. no two rectangles in a band are allowed
109 * Whenever possible, bands will be merged together to cover a greater vertical
110 * distance (and thus reduce the number of rectangles). Two bands can be merged
111 * only if the bottom of one touches the top of the other and they have
112 * rectangles in the same places (of the same width, of course). This maintains
113 * the y-x-banding that's so nice to have...
121 PROSRGNDATA prgnDefault
= NULL
;
122 HRGN hrgnDefault
= NULL
;
124 // Internal Functions
127 #define COPY_RECTS(dest, src, nRects) \
129 PRECT xDest = (dest); \
130 PRECT xSrc = (src); \
131 UINT xRects = (nRects); \
132 while(xRects-- > 0) { \
133 *(xDest++) = *(xSrc++); \
137 #define COPY_RECTS(dest, src, nRects) RtlCopyMemory(dest, src, (nRects) * sizeof(RECT))
140 #define EMPTY_REGION(pReg) { \
141 (pReg)->rdh.nCount = 0; \
142 (pReg)->rdh.rcBound.left = (pReg)->rdh.rcBound.top = 0; \
143 (pReg)->rdh.rcBound.right = (pReg)->rdh.rcBound.bottom = 0; \
144 (pReg)->rdh.iType = RDH_RECTANGLES; \
147 #define REGION_NOT_EMPTY(pReg) pReg->rdh.nCount
149 #define INRECT(r, x, y) \
150 ( ( ((r).right > x)) && \
151 ( ((r).left <= x)) && \
152 ( ((r).bottom > y)) && \
155 /* 1 if two RECTs overlap.
156 * 0 if two RECTs do not overlap.
158 #define EXTENTCHECK(r1, r2) \
159 ((r1)->right > (r2)->left && \
160 (r1)->left < (r2)->right && \
161 (r1)->bottom > (r2)->top && \
162 (r1)->top < (r2)->bottom)
165 * In scan converting polygons, we want to choose those pixels
166 * which are inside the polygon. Thus, we add .5 to the starting
167 * x coordinate for both left and right edges. Now we choose the
168 * first pixel which is inside the pgon for the left edge and the
169 * first pixel which is outside the pgon for the right edge.
170 * Draw the left pixel, but not the right.
172 * How to add .5 to the starting x coordinate:
173 * If the edge is moving to the right, then subtract dy from the
174 * error term from the general form of the algorithm.
175 * If the edge is moving to the left, then add dy to the error term.
177 * The reason for the difference between edges moving to the left
178 * and edges moving to the right is simple: If an edge is moving
179 * to the right, then we want the algorithm to flip immediately.
180 * If it is moving to the left, then we don't want it to flip until
181 * we traverse an entire pixel.
183 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
184 int dx; /* local storage */ \
187 * if the edge is horizontal, then it is ignored \
188 * and assumed not to be processed. Otherwise, do this stuff. \
192 dx = (x2) - xStart; \
196 incr1 = -2 * dx + 2 * (dy) * m1; \
197 incr2 = -2 * dx + 2 * (dy) * m; \
198 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
202 incr1 = 2 * dx - 2 * (dy) * m1; \
203 incr2 = 2 * dx - 2 * (dy) * m; \
204 d = -2 * m * (dy) + 2 * dx; \
209 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
232 * This structure contains all of the information needed
233 * to run the bresenham algorithm.
234 * The variables may be hardcoded into the declarations
235 * instead of using this structure to make use of
236 * register declarations.
240 INT minor_axis
; /* minor axis */
241 INT d
; /* decision variable */
242 INT m
, m1
; /* slope and slope+1 */
243 INT incr1
, incr2
; /* error increments */
247 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
248 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
249 bres.m, bres.m1, bres.incr1, bres.incr2)
251 #define BRESINCRPGONSTRUCT(bres) \
252 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
257 * These are the data structures needed to scan
258 * convert regions. Two different scan conversion
259 * methods are available -- the even-odd method, and
260 * the winding number method.
261 * The even-odd rule states that a point is inside
262 * the polygon if a ray drawn from that point in any
263 * direction will pass through an odd number of
265 * By the winding number rule, a point is decided
266 * to be inside the polygon if a ray drawn from that
267 * point in any direction passes through a different
268 * number of clockwise and counter-clockwise path
271 * These data structures are adapted somewhat from
272 * the algorithm in (Foley/Van Dam) for scan converting
274 * The basic algorithm is to start at the top (smallest y)
275 * of the polygon, stepping down to the bottom of
276 * the polygon by incrementing the y coordinate. We
277 * keep a list of edges which the current scanline crosses,
278 * sorted by x. This list is called the Active Edge Table (AET)
279 * As we change the y-coordinate, we update each entry in
280 * in the active edge table to reflect the edges new xcoord.
281 * This list must be sorted at each scanline in case
282 * two edges intersect.
283 * We also keep a data structure known as the Edge Table (ET),
284 * which keeps track of all the edges which the current
285 * scanline has not yet reached. The ET is basically a
286 * list of ScanLineList structures containing a list of
287 * edges which are entered at a given scanline. There is one
288 * ScanLineList per scanline at which an edge is entered.
289 * When we enter a new edge, we move it from the ET to the AET.
291 * From the AET, we can implement the even-odd rule as in
293 * The winding number rule is a little trickier. We also
294 * keep the EdgeTableEntries in the AET linked by the
295 * nextWETE (winding EdgeTableEntry) link. This allows
296 * the edges to be linked just as before for updating
297 * purposes, but only uses the edges linked by the nextWETE
298 * link as edges representing spans of the polygon to
299 * drawn (as with the even-odd rule).
303 * for the winding number rule
306 #define COUNTERCLOCKWISE -1
308 typedef struct _EdgeTableEntry
310 INT ymax
; /* ycoord at which we exit this edge. */
311 BRESINFO bres
; /* Bresenham info to run the edge */
312 struct _EdgeTableEntry
*next
; /* next in the list */
313 struct _EdgeTableEntry
*back
; /* for insertion sort */
314 struct _EdgeTableEntry
*nextWETE
; /* for winding num rule */
315 int ClockWise
; /* flag for winding number rule */
319 typedef struct _ScanLineList
321 INT scanline
; /* the scanline represented */
322 EdgeTableEntry
*edgelist
; /* header node */
323 struct _ScanLineList
*next
; /* next in the list */
329 INT ymax
; /* ymax for the polygon */
330 INT ymin
; /* ymin for the polygon */
331 ScanLineList scanlines
; /* header node */
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
344 ScanLineList SLLs
[SLLSPERBLOCK
];
345 struct _ScanLineListBlock
*next
;
351 * a few macros for the inner loops of the fill code where
352 * performance considerations don't allow a procedure call.
354 * Evaluate the given edge at the given scanline.
355 * If the edge has expired, then we leave it and fix up
356 * the active edge table; otherwise, we increment the
357 * x value to be ready for the next scanline.
358 * The winding number rule is in effect, so we must notify
359 * the caller when the edge has been removed so he
360 * can reorder the Winding Active Edge Table.
362 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
363 if (pAET->ymax == y) { /* leaving this edge */ \
364 pPrevAET->next = pAET->next; \
365 pAET = pPrevAET->next; \
368 pAET->back = pPrevAET; \
371 BRESINCRPGONSTRUCT(pAET->bres); \
379 * Evaluate the given edge at the given scanline.
380 * If the edge has expired, then we leave it and fix up
381 * the active edge table; otherwise, we increment the
382 * x value to be ready for the next scanline.
383 * The even-odd rule is in effect.
385 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
386 if (pAET->ymax == y) { /* leaving this edge */ \
387 pPrevAET->next = pAET->next; \
388 pAET = pPrevAET->next; \
390 pAET->back = pPrevAET; \
393 BRESINCRPGONSTRUCT(pAET->bres); \
399 /**************************************************************************
403 *************************************************************************/
405 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
406 #define SMALL_COORDINATE 0x80000000
409 * Check to see if there is enough memory in the present region.
411 static __inline
int xmemcheck(ROSRGNDATA
*reg
, PRECT
*rect
, PRECT
*firstrect
)
413 if ( (reg
->rdh
.nCount
+1) * sizeof(RECT
) >= reg
->rdh
.nRgnSize
)
416 DWORD NewSize
= 2 * reg
->rdh
.nRgnSize
;
417 if (NewSize
< (reg
->rdh
.nCount
+ 1) * sizeof(RECT
))
419 NewSize
= (reg
->rdh
.nCount
+ 1) * sizeof(RECT
);
421 temp
= ExAllocatePoolWithTag(PagedPool
, NewSize
, TAG_REGION
);
428 /* Copy the rectangles */
429 COPY_RECTS(temp
, *firstrect
, reg
->rdh
.nCount
);
431 reg
->rdh
.nRgnSize
= NewSize
;
432 if (*firstrect
!= ®
->rdh
.rcBound
)
434 ExFreePoolWithTag(*firstrect
, TAG_REGION
);
437 *rect
= (*firstrect
)+reg
->rdh
.nCount
;
442 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),(LPRECT *)&(firstrect))
444 typedef void (FASTCALL
*overlapProcp
)(PROSRGNDATA
, PRECT
, PRECT
, PRECT
, PRECT
, INT
, INT
);
445 typedef void (FASTCALL
*nonOverlapProcp
)(PROSRGNDATA
, PRECT
, PRECT
, INT
, INT
);
447 // Number of points to buffer before sending them off to scanlines() : Must be an even number
448 #define NUMPTSTOBUFFER 200
450 #define RGN_DEFAULT_RECTS 2
452 // used to allocate buffers for points and link the buffers together
454 typedef struct _POINTBLOCK
456 POINT pts
[NUMPTSTOBUFFER
];
457 struct _POINTBLOCK
*next
;
462 * This function is left there for debugging purposes.
466 IntDumpRegion(HRGN hRgn
)
470 Data
= REGION_LockRgn(hRgn
);
473 DbgPrint("IntDumpRegion called with invalid region!\n");
477 DbgPrint("IntDumpRegion(%x): %d,%d-%d,%d %d\n",
479 Data
->rdh
.rcBound
.left
,
480 Data
->rdh
.rcBound
.top
,
481 Data
->rdh
.rcBound
.right
,
482 Data
->rdh
.rcBound
.bottom
,
485 REGION_UnlockRgn(Data
);
487 #endif /* not NDEBUG */
492 REGION_Complexity( PROSRGNDATA obj
)
494 if (!obj
) return NULLREGION
;
495 switch(obj
->rdh
.nCount
)
497 DPRINT("Region Complexity -> %d",obj
->rdh
.nCount
);
498 case 0: return NULLREGION
;
499 case 1: return SIMPLEREGION
;
500 default: return COMPLEXREGION
;
512 if (dst
!= src
) // don't want to copy to itself
514 if (dst
->rdh
.nRgnSize
< src
->rdh
.nCount
* sizeof(RECT
))
518 temp
= ExAllocatePoolWithTag(PagedPool
, src
->rdh
.nCount
* sizeof(RECT
), TAG_REGION
);
522 if (dst
->Buffer
&& dst
->Buffer
!= &dst
->rdh
.rcBound
)
523 ExFreePoolWithTag(dst
->Buffer
, TAG_REGION
); //free the old buffer
525 dst
->rdh
.nRgnSize
= src
->rdh
.nCount
* sizeof(RECT
); //size of region buffer
527 dst
->rdh
.nCount
= src
->rdh
.nCount
; //number of rectangles present in Buffer
528 dst
->rdh
.rcBound
.left
= src
->rdh
.rcBound
.left
;
529 dst
->rdh
.rcBound
.top
= src
->rdh
.rcBound
.top
;
530 dst
->rdh
.rcBound
.right
= src
->rdh
.rcBound
.right
;
531 dst
->rdh
.rcBound
.bottom
= src
->rdh
.rcBound
.bottom
;
532 dst
->rdh
.iType
= src
->rdh
.iType
;
533 COPY_RECTS(dst
->Buffer
, src
->Buffer
, src
->rdh
.nCount
);
539 REGION_SetExtents(ROSRGNDATA
*pReg
)
541 RECT
*pRect
, *pRectEnd
, *pExtents
;
543 if (pReg
->rdh
.nCount
== 0)
545 pReg
->rdh
.rcBound
.left
= 0;
546 pReg
->rdh
.rcBound
.top
= 0;
547 pReg
->rdh
.rcBound
.right
= 0;
548 pReg
->rdh
.rcBound
.bottom
= 0;
549 pReg
->rdh
.iType
= RDH_RECTANGLES
;
553 pExtents
= &pReg
->rdh
.rcBound
;
554 pRect
= (PRECT
)pReg
->Buffer
;
555 pRectEnd
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
- 1;
558 * Since pRect is the first rectangle in the region, it must have the
559 * smallest top and since pRectEnd is the last rectangle in the region,
560 * it must have the largest bottom, because of banding. Initialize left and
561 * right from pRect and pRectEnd, resp., as good things to initialize them
564 pExtents
->left
= pRect
->left
;
565 pExtents
->top
= pRect
->top
;
566 pExtents
->right
= pRectEnd
->right
;
567 pExtents
->bottom
= pRectEnd
->bottom
;
569 while (pRect
<= pRectEnd
)
571 if (pRect
->left
< pExtents
->left
)
572 pExtents
->left
= pRect
->left
;
573 if (pRect
->right
> pExtents
->right
)
574 pExtents
->right
= pRect
->right
;
577 pReg
->rdh
.iType
= RDH_RECTANGLES
;
580 // FIXME: This seems to be wrong
581 /***********************************************************************
582 * REGION_CropAndOffsetRegion
585 REGION_CropAndOffsetRegion(
597 if (!rect
) // just copy and offset
600 if (rgnDst
== rgnSrc
)
602 if (off
->x
|| off
->y
)
603 xrect
= (PRECT
)rgnDst
->Buffer
;
609 xrect
= ExAllocatePoolWithTag(PagedPool
, rgnSrc
->rdh
.nCount
* sizeof(RECT
), TAG_REGION
);
610 if (rgnDst
->Buffer
&& rgnDst
->Buffer
!= &rgnDst
->rdh
.rcBound
)
611 ExFreePoolWithTag(rgnDst
->Buffer
, TAG_REGION
); //free the old buffer. will be assigned to xrect below.
618 if (rgnDst
!= rgnSrc
)
623 if (off
->x
|| off
->y
)
625 for (i
= 0; i
< rgnDst
->rdh
.nCount
; i
++)
627 xrect
[i
].left
= ((PRECT
)rgnSrc
->Buffer
+ i
)->left
+ off
->x
;
628 xrect
[i
].right
= ((PRECT
)rgnSrc
->Buffer
+ i
)->right
+ off
->x
;
629 xrect
[i
].top
= ((PRECT
)rgnSrc
->Buffer
+ i
)->top
+ off
->y
;
630 xrect
[i
].bottom
= ((PRECT
)rgnSrc
->Buffer
+ i
)->bottom
+ off
->y
;
632 rgnDst
->rdh
.rcBound
.left
+= off
->x
;
633 rgnDst
->rdh
.rcBound
.right
+= off
->x
;
634 rgnDst
->rdh
.rcBound
.top
+= off
->y
;
635 rgnDst
->rdh
.rcBound
.bottom
+= off
->y
;
639 COPY_RECTS(xrect
, rgnSrc
->Buffer
, rgnDst
->rdh
.nCount
);
642 rgnDst
->Buffer
= xrect
;
647 else if ((rect
->left
>= rect
->right
) ||
648 (rect
->top
>= rect
->bottom
) ||
649 !EXTENTCHECK(rect
, &rgnSrc
->rdh
.rcBound
))
653 else // region box and clipping rect appear to intersect
656 ULONG i
, j
, clipa
, clipb
;
657 INT left
= rgnSrc
->rdh
.rcBound
.right
+ off
->x
;
658 INT right
= rgnSrc
->rdh
.rcBound
.left
+ off
->x
;
660 for (clipa
= 0; ((PRECT
)rgnSrc
->Buffer
+ clipa
)->bottom
<= rect
->top
; clipa
++)
661 //region and rect intersect so we stop before clipa > rgnSrc->rdh.nCount
662 ; // skip bands above the clipping rectangle
664 for (clipb
= clipa
; clipb
< rgnSrc
->rdh
.nCount
; clipb
++)
665 if (((PRECT
)rgnSrc
->Buffer
+ clipb
)->top
>= rect
->bottom
)
666 break; // and below it
668 // clipa - index of the first rect in the first intersecting band
669 // clipb - index of the last rect in the last intersecting band
671 if ((rgnDst
!= rgnSrc
) && (rgnDst
->rdh
.nCount
< (i
= (clipb
- clipa
))))
674 temp
= ExAllocatePoolWithTag(PagedPool
, i
* sizeof(RECT
), TAG_REGION
);
678 if (rgnDst
->Buffer
&& rgnDst
->Buffer
!= &rgnDst
->rdh
.rcBound
)
679 ExFreePoolWithTag(rgnDst
->Buffer
, TAG_REGION
); //free the old buffer
680 rgnDst
->Buffer
= temp
;
681 rgnDst
->rdh
.nCount
= i
;
682 rgnDst
->rdh
.nRgnSize
= i
* sizeof(RECT
);
685 for (i
= clipa
, j
= 0; i
< clipb
; i
++)
687 // i - src index, j - dst index, j is always <= i for obvious reasons
689 lpr
= (PRECT
)rgnSrc
->Buffer
+ i
;
691 if (lpr
->left
< rect
->right
&& lpr
->right
> rect
->left
)
693 rpr
= (PRECT
)rgnDst
->Buffer
+ j
;
695 rpr
->top
= lpr
->top
+ off
->y
;
696 rpr
->bottom
= lpr
->bottom
+ off
->y
;
697 rpr
->left
= ((lpr
->left
> rect
->left
) ? lpr
->left
: rect
->left
) + off
->x
;
698 rpr
->right
= ((lpr
->right
< rect
->right
) ? lpr
->right
: rect
->right
) + off
->x
;
700 if (rpr
->left
< left
) left
= rpr
->left
;
701 if (rpr
->right
> right
) right
= rpr
->right
;
707 if (j
== 0) goto empty
;
709 rgnDst
->rdh
.rcBound
.left
= left
;
710 rgnDst
->rdh
.rcBound
.right
= right
;
712 left
= rect
->top
+ off
->y
;
713 right
= rect
->bottom
+ off
->y
;
715 rgnDst
->rdh
.nCount
= j
--;
716 for (i
= 0; i
<= j
; i
++) // fixup top band
717 if ((rgnDst
->Buffer
+ i
)->top
< left
)
718 (rgnDst
->Buffer
+ i
)->top
= left
;
722 for (i
= j
; i
> 0; i
--) // fixup bottom band
723 if (((PRECT
)rgnDst
->Buffer
+ i
)->bottom
> right
)
724 ((PRECT
)rgnDst
->Buffer
+ i
)->bottom
= right
;
728 rgnDst
->rdh
.rcBound
.top
= ((PRECT
)rgnDst
->Buffer
)->top
;
729 rgnDst
->rdh
.rcBound
.bottom
= ((PRECT
)rgnDst
->Buffer
+ j
)->bottom
;
731 rgnDst
->rdh
.iType
= RDH_RECTANGLES
;
739 rgnDst
->Buffer
= (PRECT
)ExAllocatePoolWithTag(PagedPool
, RGN_DEFAULT_RECTS
* sizeof(RECT
), TAG_REGION
);
742 rgnDst
->rdh
.nCount
= RGN_DEFAULT_RECTS
;
743 rgnDst
->rdh
.nRgnSize
= RGN_DEFAULT_RECTS
* sizeof(RECT
);
748 EMPTY_REGION(rgnDst
);
754 * Attempt to merge the rects in the current band with those in the
755 * previous one. Used only by REGION_RegionOp.
758 * The new index for the previous band.
760 * \note Side Effects:
761 * If coalescing takes place:
762 * - rectangles in the previous band will have their bottom fields
764 * - pReg->numRects will be decreased.
769 PROSRGNDATA pReg
, /* Region to coalesce */
770 INT prevStart
, /* Index of start of previous band */
771 INT curStart
/* Index of start of current band */
774 RECT
*pPrevRect
; /* Current rect in previous band */
775 RECT
*pCurRect
; /* Current rect in current band */
776 RECT
*pRegEnd
; /* End of region */
777 INT curNumRects
; /* Number of rectangles in current band */
778 INT prevNumRects
; /* Number of rectangles in previous band */
779 INT bandtop
; /* top coordinate for current band */
781 pRegEnd
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
782 pPrevRect
= (PRECT
)pReg
->Buffer
+ prevStart
;
783 prevNumRects
= curStart
- prevStart
;
786 * Figure out how many rectangles are in the current band. Have to do
787 * this because multiple bands could have been added in REGION_RegionOp
788 * at the end when one region has been exhausted.
790 pCurRect
= (PRECT
)pReg
->Buffer
+ curStart
;
791 bandtop
= pCurRect
->top
;
792 for (curNumRects
= 0;
793 (pCurRect
!= pRegEnd
) && (pCurRect
->top
== bandtop
);
799 if (pCurRect
!= pRegEnd
)
802 * If more than one band was added, we have to find the start
803 * of the last band added so the next coalescing job can start
804 * at the right place... (given when multiple bands are added,
805 * this may be pointless -- see above).
808 while ((pRegEnd
-1)->top
== pRegEnd
->top
)
812 curStart
= pRegEnd
- (PRECT
)pReg
->Buffer
;
813 pRegEnd
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
816 if ((curNumRects
== prevNumRects
) && (curNumRects
!= 0))
818 pCurRect
-= curNumRects
;
820 * The bands may only be coalesced if the bottom of the previous
821 * matches the top scanline of the current.
823 if (pPrevRect
->bottom
== pCurRect
->top
)
826 * Make sure the bands have rects in the same places. This
827 * assumes that rects have been added in such a way that they
828 * cover the most area possible. I.e. two rects in a band must
829 * have some horizontal space between them.
833 if ((pPrevRect
->left
!= pCurRect
->left
) ||
834 (pPrevRect
->right
!= pCurRect
->right
))
837 * The bands don't line up so they can't be coalesced.
845 while (prevNumRects
!= 0);
847 pReg
->rdh
.nCount
-= curNumRects
;
848 pCurRect
-= curNumRects
;
849 pPrevRect
-= curNumRects
;
852 * The bands may be merged, so set the bottom of each rect
853 * in the previous band to that of the corresponding rect in
858 pPrevRect
->bottom
= pCurRect
->bottom
;
863 while (curNumRects
!= 0);
866 * If only one band was added to the region, we have to backup
867 * curStart to the start of the previous band.
869 * If more than one band was added to the region, copy the
870 * other bands down. The assumption here is that the other bands
871 * came from the same region as the current one and no further
872 * coalescing can be done on them since it's all been done
873 * already... curStart is already in the right place.
875 if (pCurRect
== pRegEnd
)
877 curStart
= prevStart
;
883 *pPrevRect
++ = *pCurRect
++;
885 while (pCurRect
!= pRegEnd
);
893 * Apply an operation to two regions. Called by REGION_Union,
894 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
900 * The new region is overwritten.
902 *\note The idea behind this function is to view the two regions as sets.
903 * Together they cover a rectangle of area that this function divides
904 * into horizontal bands where points are covered only by one region
905 * or by both. For the first case, the nonOverlapFunc is called with
906 * each the band and the band's upper and lower extents. For the
907 * second, the overlapFunc is called to process the entire band. It
908 * is responsible for clipping the rectangles in the band, though
909 * this function provides the boundaries.
910 * At the end of each band, the new region is coalesced, if possible,
911 * to reduce the number of rectangles in the region.
916 ROSRGNDATA
*newReg
, /* Place to store result */
917 ROSRGNDATA
*reg1
, /* First region in operation */
918 ROSRGNDATA
*reg2
, /* 2nd region in operation */
919 overlapProcp overlapFunc
, /* Function to call for over-lapping bands */
920 nonOverlapProcp nonOverlap1Func
, /* Function to call for non-overlapping bands in region 1 */
921 nonOverlapProcp nonOverlap2Func
/* Function to call for non-overlapping bands in region 2 */
924 RECT
*r1
; /* Pointer into first region */
925 RECT
*r2
; /* Pointer into 2d region */
926 RECT
*r1End
; /* End of 1st region */
927 RECT
*r2End
; /* End of 2d region */
928 INT ybot
; /* Bottom of intersection */
929 INT ytop
; /* Top of intersection */
930 RECT
*oldRects
; /* Old rects for newReg */
931 ULONG prevBand
; /* Index of start of
932 * previous band in newReg */
933 ULONG curBand
; /* Index of start of current band in newReg */
934 RECT
*r1BandEnd
; /* End of current band in r1 */
935 RECT
*r2BandEnd
; /* End of current band in r2 */
936 ULONG top
; /* Top of non-overlapping band */
937 ULONG bot
; /* Bottom of non-overlapping band */
941 * set r1, r2, r1End and r2End appropriately, preserve the important
942 * parts of the destination region until the end in case it's one of
943 * the two source regions, then mark the "new" region empty, allocating
944 * another array of rectangles for it to use.
946 r1
= (PRECT
)reg1
->Buffer
;
947 r2
= (PRECT
)reg2
->Buffer
;
948 r1End
= r1
+ reg1
->rdh
.nCount
;
949 r2End
= r2
+ reg2
->rdh
.nCount
;
953 * newReg may be one of the src regions so we can't empty it. We keep a
954 * note of its rects pointer (so that we can free them later), preserve its
955 * extents and simply set numRects to zero.
958 oldRects
= (PRECT
)newReg
->Buffer
;
959 newReg
->rdh
.nCount
= 0;
962 * Allocate a reasonable number of rectangles for the new region. The idea
963 * is to allocate enough so the individual functions don't need to
964 * reallocate and copy the array, which is time consuming, yet we don't
965 * have to worry about using too much memory. I hope to be able to
966 * nuke the Xrealloc() at the end of this function eventually.
968 newReg
->rdh
.nRgnSize
= max(reg1
->rdh
.nCount
,reg2
->rdh
.nCount
) * 2 * sizeof(RECT
);
970 if (! (newReg
->Buffer
= ExAllocatePoolWithTag(PagedPool
, newReg
->rdh
.nRgnSize
, TAG_REGION
)))
972 newReg
->rdh
.nRgnSize
= 0;
977 * Initialize ybot and ytop.
978 * In the upcoming loop, ybot and ytop serve different functions depending
979 * on whether the band being handled is an overlapping or non-overlapping
981 * In the case of a non-overlapping band (only one of the regions
982 * has points in the band), ybot is the bottom of the most recent
983 * intersection and thus clips the top of the rectangles in that band.
984 * ytop is the top of the next intersection between the two regions and
985 * serves to clip the bottom of the rectangles in the current band.
986 * For an overlapping band (where the two regions intersect), ytop clips
987 * the top of the rectangles of both regions and ybot clips the bottoms.
989 if (reg1
->rdh
.rcBound
.top
< reg2
->rdh
.rcBound
.top
)
990 ybot
= reg1
->rdh
.rcBound
.top
;
992 ybot
= reg2
->rdh
.rcBound
.top
;
995 * prevBand serves to mark the start of the previous band so rectangles
996 * can be coalesced into larger rectangles. qv. miCoalesce, above.
997 * In the beginning, there is no previous band, so prevBand == curBand
998 * (curBand is set later on, of course, but the first band will always
999 * start at index 0). prevBand and curBand must be indices because of
1000 * the possible expansion, and resultant moving, of the new region's
1001 * array of rectangles.
1007 curBand
= newReg
->rdh
.nCount
;
1010 * This algorithm proceeds one source-band (as opposed to a
1011 * destination band, which is determined by where the two regions
1012 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1013 * rectangle after the last one in the current band for their
1014 * respective regions.
1017 while ((r1BandEnd
!= r1End
) && (r1BandEnd
->top
== r1
->top
))
1023 while ((r2BandEnd
!= r2End
) && (r2BandEnd
->top
== r2
->top
))
1029 * First handle the band that doesn't intersect, if any.
1031 * Note that attention is restricted to one band in the
1032 * non-intersecting region at once, so if a region has n
1033 * bands between the current position and the next place it overlaps
1034 * the other, this entire loop will be passed through n times.
1036 if (r1
->top
< r2
->top
)
1038 top
= max(r1
->top
,ybot
);
1039 bot
= min(r1
->bottom
,r2
->top
);
1041 if ((top
!= bot
) && (nonOverlap1Func
!= NULL
))
1043 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
, top
, bot
);
1048 else if (r2
->top
< r1
->top
)
1050 top
= max(r2
->top
,ybot
);
1051 bot
= min(r2
->bottom
,r1
->top
);
1053 if ((top
!= bot
) && (nonOverlap2Func
!= NULL
))
1055 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
, top
, bot
);
1066 * If any rectangles got added to the region, try and coalesce them
1067 * with rectangles from the previous band. Note we could just do
1068 * this test in miCoalesce, but some machines incur a not
1069 * inconsiderable cost for function calls, so...
1071 if (newReg
->rdh
.nCount
!= curBand
)
1073 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1077 * Now see if we've hit an intersecting band. The two bands only
1078 * intersect if ybot > ytop
1080 ybot
= min(r1
->bottom
, r2
->bottom
);
1081 curBand
= newReg
->rdh
.nCount
;
1084 (* overlapFunc
) (newReg
, r1
, r1BandEnd
, r2
, r2BandEnd
, ytop
, ybot
);
1087 if (newReg
->rdh
.nCount
!= curBand
)
1089 prevBand
= REGION_Coalesce (newReg
, prevBand
, curBand
);
1093 * If we've finished with a band (bottom == ybot) we skip forward
1094 * in the region to the next band.
1096 if (r1
->bottom
== ybot
)
1100 if (r2
->bottom
== ybot
)
1105 while ((r1
!= r1End
) && (r2
!= r2End
));
1108 * Deal with whichever region still has rectangles left.
1110 curBand
= newReg
->rdh
.nCount
;
1113 if (nonOverlap1Func
!= NULL
)
1118 while ((r1BandEnd
< r1End
) && (r1BandEnd
->top
== r1
->top
))
1122 (* nonOverlap1Func
) (newReg
, r1
, r1BandEnd
,
1123 max(r1
->top
,ybot
), r1
->bottom
);
1126 while (r1
!= r1End
);
1129 else if ((r2
!= r2End
) && (nonOverlap2Func
!= NULL
))
1134 while ((r2BandEnd
< r2End
) && (r2BandEnd
->top
== r2
->top
))
1138 (* nonOverlap2Func
) (newReg
, r2
, r2BandEnd
,
1139 max(r2
->top
,ybot
), r2
->bottom
);
1142 while (r2
!= r2End
);
1145 if (newReg
->rdh
.nCount
!= curBand
)
1147 (void) REGION_Coalesce (newReg
, prevBand
, curBand
);
1151 * A bit of cleanup. To keep regions from growing without bound,
1152 * we shrink the array of rectangles to match the new number of
1153 * rectangles in the region. This never goes to 0, however...
1155 * Only do this stuff if the number of rectangles allocated is more than
1156 * twice the number of rectangles in the region (a simple optimization...).
1158 if ((2 * newReg
->rdh
.nCount
*sizeof(RECT
) < newReg
->rdh
.nRgnSize
&& (newReg
->rdh
.nCount
> 2)))
1160 if (REGION_NOT_EMPTY(newReg
))
1162 RECT
*prev_rects
= (PRECT
)newReg
->Buffer
;
1163 newReg
->Buffer
= ExAllocatePoolWithTag(PagedPool
, newReg
->rdh
.nCount
*sizeof(RECT
), TAG_REGION
);
1165 if (! newReg
->Buffer
)
1166 newReg
->Buffer
= prev_rects
;
1169 newReg
->rdh
.nRgnSize
= newReg
->rdh
.nCount
*sizeof(RECT
);
1170 COPY_RECTS(newReg
->Buffer
, prev_rects
, newReg
->rdh
.nCount
);
1171 if (prev_rects
!= &newReg
->rdh
.rcBound
)
1172 ExFreePoolWithTag(prev_rects
, TAG_REGION
);
1178 * No point in doing the extra work involved in an Xrealloc if
1179 * the region is empty
1181 newReg
->rdh
.nRgnSize
= sizeof(RECT
);
1182 if (newReg
->Buffer
!= &newReg
->rdh
.rcBound
)
1183 ExFreePoolWithTag(newReg
->Buffer
, TAG_REGION
);
1184 newReg
->Buffer
= ExAllocatePoolWithTag(PagedPool
, sizeof(RECT
), TAG_REGION
);
1185 ASSERT(newReg
->Buffer
);
1188 newReg
->rdh
.iType
= RDH_RECTANGLES
;
1190 if (oldRects
!= &newReg
->rdh
.rcBound
)
1191 ExFreePoolWithTag(oldRects
, TAG_REGION
);
1195 /***********************************************************************
1196 * Region Intersection
1197 ***********************************************************************/
1201 * Handle an overlapping band for REGION_Intersect.
1206 * \note Side Effects:
1207 * Rectangles may be added to the region.
1210 static void FASTCALL
1224 pNextRect
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
1226 while ((r1
!= r1End
) && (r2
!= r2End
))
1228 left
= max(r1
->left
, r2
->left
);
1229 right
= min(r1
->right
, r2
->right
);
1232 * If there's any overlap between the two rectangles, add that
1233 * overlap to the new region.
1234 * There's no need to check for subsumption because the only way
1235 * such a need could arise is if some region has two rectangles
1236 * right next to each other. Since that should never happen...
1240 MEMCHECK(pReg
, pNextRect
, pReg
->Buffer
);
1241 pNextRect
->left
= left
;
1242 pNextRect
->top
= top
;
1243 pNextRect
->right
= right
;
1244 pNextRect
->bottom
= bottom
;
1245 pReg
->rdh
.nCount
+= 1;
1250 * Need to advance the pointers. Shift the one that extends
1251 * to the right the least, since the other still has a chance to
1252 * overlap with that region's next rectangle, if you see what I mean.
1254 if (r1
->right
< r2
->right
)
1258 else if (r2
->right
< r1
->right
)
1271 /***********************************************************************
1272 * REGION_IntersectRegion
1274 static void FASTCALL
1275 REGION_IntersectRegion(
1281 /* check for trivial reject */
1282 if ( (!(reg1
->rdh
.nCount
)) || (!(reg2
->rdh
.nCount
)) ||
1283 (!EXTENTCHECK(®1
->rdh
.rcBound
, ®2
->rdh
.rcBound
)) )
1284 newReg
->rdh
.nCount
= 0;
1286 REGION_RegionOp (newReg
, reg1
, reg2
,
1287 REGION_IntersectO
, NULL
, NULL
);
1290 * Can't alter newReg's extents before we call miRegionOp because
1291 * it might be one of the source regions and miRegionOp depends
1292 * on the extents of those regions being the same. Besides, this
1293 * way there's no checking against rectangles that will be nuked
1294 * due to coalescing, so we have to examine fewer rectangles.
1297 REGION_SetExtents(newReg
);
1300 /***********************************************************************
1302 ***********************************************************************/
1305 * Handle a non-overlapping band for the union operation. Just
1306 * Adds the rectangles into the region. Doesn't have to check for
1307 * subsumption or anything.
1312 * \note Side Effects:
1313 * pReg->numRects is incremented and the final rectangles overwritten
1314 * with the rectangles we're passed.
1317 static void FASTCALL
1328 pNextRect
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
1332 MEMCHECK(pReg
, pNextRect
, pReg
->Buffer
);
1333 pNextRect
->left
= r
->left
;
1334 pNextRect
->top
= top
;
1335 pNextRect
->right
= r
->right
;
1336 pNextRect
->bottom
= bottom
;
1337 pReg
->rdh
.nCount
+= 1;
1345 * Handle an overlapping band for the union operation. Picks the
1346 * left-most rectangle each time and merges it into the region.
1351 * \note Side Effects:
1352 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1356 static void FASTCALL
1369 pNextRect
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
1371 #define MERGERECT(r) \
1372 if ((pReg->rdh.nCount != 0) && \
1373 ((pNextRect-1)->top == top) && \
1374 ((pNextRect-1)->bottom == bottom) && \
1375 ((pNextRect-1)->right >= r->left)) \
1377 if ((pNextRect-1)->right < r->right) \
1379 (pNextRect-1)->right = r->right; \
1384 MEMCHECK(pReg, pNextRect, pReg->Buffer); \
1385 pNextRect->top = top; \
1386 pNextRect->bottom = bottom; \
1387 pNextRect->left = r->left; \
1388 pNextRect->right = r->right; \
1389 pReg->rdh.nCount += 1; \
1394 while ((r1
!= r1End
) && (r2
!= r2End
))
1396 if (r1
->left
< r2
->left
)
1412 while (r1
!= r1End
);
1414 else while (r2
!= r2End
)
1421 /***********************************************************************
1422 * REGION_UnionRegion
1424 static void FASTCALL
1431 /* checks all the simple cases */
1434 * Region 1 and 2 are the same or region 1 is empty
1436 if (reg1
== reg2
|| 0 == reg1
->rdh
.nCount
||
1437 reg1
->rdh
.rcBound
.right
<= reg1
->rdh
.rcBound
.left
||
1438 reg1
->rdh
.rcBound
.bottom
<= reg1
->rdh
.rcBound
.top
)
1442 REGION_CopyRegion(newReg
, reg2
);
1448 * if nothing to union (region 2 empty)
1450 if (0 == reg2
->rdh
.nCount
||
1451 reg2
->rdh
.rcBound
.right
<= reg2
->rdh
.rcBound
.left
||
1452 reg2
->rdh
.rcBound
.bottom
<= reg2
->rdh
.rcBound
.top
)
1456 REGION_CopyRegion(newReg
, reg1
);
1462 * Region 1 completely subsumes region 2
1464 if (1 == reg1
->rdh
.nCount
&&
1465 reg1
->rdh
.rcBound
.left
<= reg2
->rdh
.rcBound
.left
&&
1466 reg1
->rdh
.rcBound
.top
<= reg2
->rdh
.rcBound
.top
&&
1467 reg2
->rdh
.rcBound
.right
<= reg1
->rdh
.rcBound
.right
&&
1468 reg2
->rdh
.rcBound
.bottom
<= reg1
->rdh
.rcBound
.bottom
)
1472 REGION_CopyRegion(newReg
, reg1
);
1478 * Region 2 completely subsumes region 1
1480 if (1 == reg2
->rdh
.nCount
&&
1481 reg2
->rdh
.rcBound
.left
<= reg1
->rdh
.rcBound
.left
&&
1482 reg2
->rdh
.rcBound
.top
<= reg1
->rdh
.rcBound
.top
&&
1483 reg1
->rdh
.rcBound
.right
<= reg2
->rdh
.rcBound
.right
&&
1484 reg1
->rdh
.rcBound
.bottom
<= reg2
->rdh
.rcBound
.bottom
)
1488 REGION_CopyRegion(newReg
, reg2
);
1493 REGION_RegionOp (newReg
, reg1
, reg2
, REGION_UnionO
,
1494 REGION_UnionNonO
, REGION_UnionNonO
);
1495 newReg
->rdh
.rcBound
.left
= min(reg1
->rdh
.rcBound
.left
, reg2
->rdh
.rcBound
.left
);
1496 newReg
->rdh
.rcBound
.top
= min(reg1
->rdh
.rcBound
.top
, reg2
->rdh
.rcBound
.top
);
1497 newReg
->rdh
.rcBound
.right
= max(reg1
->rdh
.rcBound
.right
, reg2
->rdh
.rcBound
.right
);
1498 newReg
->rdh
.rcBound
.bottom
= max(reg1
->rdh
.rcBound
.bottom
, reg2
->rdh
.rcBound
.bottom
);
1501 /***********************************************************************
1502 * Region Subtraction
1503 ***********************************************************************/
1506 * Deal with non-overlapping band for subtraction. Any parts from
1507 * region 2 we discard. Anything from region 1 we add to the region.
1512 * \note Side Effects:
1513 * pReg may be affected.
1516 static void FASTCALL
1517 REGION_SubtractNonO1(
1527 pNextRect
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
1531 MEMCHECK(pReg
, pNextRect
, pReg
->Buffer
);
1532 pNextRect
->left
= r
->left
;
1533 pNextRect
->top
= top
;
1534 pNextRect
->right
= r
->right
;
1535 pNextRect
->bottom
= bottom
;
1536 pReg
->rdh
.nCount
+= 1;
1545 * Overlapping band subtraction. x1 is the left-most point not yet
1551 * \note Side Effects:
1552 * pReg may have rectangles added to it.
1555 static void FASTCALL
1570 pNextRect
= (PRECT
)pReg
->Buffer
+ pReg
->rdh
.nCount
;
1572 while ((r1
!= r1End
) && (r2
!= r2End
))
1574 if (r2
->right
<= left
)
1577 * Subtrahend missed the boat: go to next subtrahend.
1581 else if (r2
->left
<= left
)
1584 * Subtrahend preceeds minuend: nuke left edge of minuend.
1587 if (left
>= r1
->right
)
1590 * Minuend completely covered: advance to next minuend and
1591 * reset left fence to edge of new minuend.
1600 * Subtrahend now used up since it doesn't extend beyond
1606 else if (r2
->left
< r1
->right
)
1609 * Left part of subtrahend covers part of minuend: add uncovered
1610 * part of minuend to region and skip to next subtrahend.
1612 MEMCHECK(pReg
, pNextRect
, pReg
->Buffer
);
1613 pNextRect
->left
= left
;
1614 pNextRect
->top
= top
;
1615 pNextRect
->right
= r2
->left
;
1616 pNextRect
->bottom
= bottom
;
1617 pReg
->rdh
.nCount
+= 1;
1620 if (left
>= r1
->right
)
1623 * Minuend used up: advance to new...
1632 * Subtrahend used up
1640 * Minuend used up: add any remaining piece before advancing.
1642 if (r1
->right
> left
)
1644 MEMCHECK(pReg
, pNextRect
, pReg
->Buffer
);
1645 pNextRect
->left
= left
;
1646 pNextRect
->top
= top
;
1647 pNextRect
->right
= r1
->right
;
1648 pNextRect
->bottom
= bottom
;
1649 pReg
->rdh
.nCount
+= 1;
1658 * Add remaining minuend rectangles to region.
1662 MEMCHECK(pReg
, pNextRect
, pReg
->Buffer
);
1663 pNextRect
->left
= left
;
1664 pNextRect
->top
= top
;
1665 pNextRect
->right
= r1
->right
;
1666 pNextRect
->bottom
= bottom
;
1667 pReg
->rdh
.nCount
+= 1;
1679 * Subtract regS from regM and leave the result in regD.
1680 * S stands for subtrahend, M for minuend and D for difference.
1685 * \note Side Effects:
1686 * regD is overwritten.
1689 static void FASTCALL
1690 REGION_SubtractRegion(
1696 /* check for trivial reject */
1697 if ( (!(regM
->rdh
.nCount
)) || (!(regS
->rdh
.nCount
)) ||
1698 (!EXTENTCHECK(®M
->rdh
.rcBound
, ®S
->rdh
.rcBound
)) )
1700 REGION_CopyRegion(regD
, regM
);
1704 REGION_RegionOp (regD
, regM
, regS
, REGION_SubtractO
,
1705 REGION_SubtractNonO1
, NULL
);
1708 * Can't alter newReg's extents before we call miRegionOp because
1709 * it might be one of the source regions and miRegionOp depends
1710 * on the extents of those regions being the unaltered. Besides, this
1711 * way there's no checking against rectangles that will be nuked
1712 * due to coalescing, so we have to examine fewer rectangles.
1714 REGION_SetExtents (regD
);
1717 /***********************************************************************
1720 static void FASTCALL
1728 ROSRGNDATA
*tra
, *trb
;
1730 // FIXME: don't use a handle
1731 tra
= REGION_AllocRgnWithHandle(sra
->rdh
.nCount
+ 1);
1736 htra
= tra
->BaseObject
.hHmgr
;
1738 // FIXME: don't use a handle
1739 trb
= REGION_AllocRgnWithHandle(srb
->rdh
.nCount
+ 1);
1742 REGION_UnlockRgn(tra
);
1743 NtGdiDeleteObject(htra
);
1746 htrb
= trb
->BaseObject
.hHmgr
;
1748 REGION_SubtractRegion(tra
, sra
, srb
);
1749 REGION_SubtractRegion(trb
, srb
, sra
);
1750 REGION_UnionRegion(dr
, tra
, trb
);
1751 REGION_UnlockRgn(tra
);
1752 REGION_UnlockRgn(trb
);
1754 NtGdiDeleteObject(htra
);
1755 NtGdiDeleteObject(htrb
);
1761 * Adds a rectangle to a REGION
1764 REGION_UnionRectWithRgn(
1771 region
.Buffer
= ®ion
.rdh
.rcBound
;
1772 region
.rdh
.nCount
= 1;
1773 region
.rdh
.nRgnSize
= sizeof(RECT
);
1774 region
.rdh
.rcBound
= *rect
;
1775 REGION_UnionRegion(rgn
, rgn
, ®ion
);
1779 REGION_CreateSimpleFrameRgn(
1788 if (x
!= 0 || y
!= 0)
1792 if (rgn
->rdh
.rcBound
.bottom
- rgn
->rdh
.rcBound
.top
> y
* 2 &&
1793 rgn
->rdh
.rcBound
.right
- rgn
->rdh
.rcBound
.left
> x
* 2)
1798 prc
->left
= rgn
->rdh
.rcBound
.left
;
1799 prc
->top
= rgn
->rdh
.rcBound
.top
;
1800 prc
->right
= rgn
->rdh
.rcBound
.right
;
1801 prc
->bottom
= prc
->top
+ y
;
1807 /* left rectangle */
1808 prc
->left
= rgn
->rdh
.rcBound
.left
;
1809 prc
->top
= rgn
->rdh
.rcBound
.top
+ y
;
1810 prc
->right
= prc
->left
+ x
;
1811 prc
->bottom
= rgn
->rdh
.rcBound
.bottom
- y
;
1814 /* right rectangle */
1815 prc
->left
= rgn
->rdh
.rcBound
.right
- x
;
1816 prc
->top
= rgn
->rdh
.rcBound
.top
+ y
;
1817 prc
->right
= rgn
->rdh
.rcBound
.right
;
1818 prc
->bottom
= rgn
->rdh
.rcBound
.bottom
- y
;
1824 /* bottom rectangle */
1825 prc
->left
= rgn
->rdh
.rcBound
.left
;
1826 prc
->top
= rgn
->rdh
.rcBound
.bottom
- y
;
1827 prc
->right
= rgn
->rdh
.rcBound
.right
;
1828 prc
->bottom
= rgn
->rdh
.rcBound
.bottom
;
1835 /* The frame results in a complex region. rcBounds remains
1836 the same, though. */
1837 rgn
->rdh
.nCount
= (DWORD
)(prc
- rc
);
1838 ASSERT(rgn
->rdh
.nCount
> 1);
1839 rgn
->rdh
.nRgnSize
= rgn
->rdh
.nCount
* sizeof(RECT
);
1840 rgn
->Buffer
= ExAllocatePoolWithTag(PagedPool
, rgn
->rdh
.nRgnSize
, TAG_REGION
);
1843 rgn
->rdh
.nRgnSize
= 0;
1847 COPY_RECTS(rgn
->Buffer
, rc
, rgn
->rdh
.nCount
);
1855 REGION_CreateFrameRgn(
1862 PROSRGNDATA srcObj
, destObj
;
1866 if (!(srcObj
= REGION_LockRgn(hSrc
)))
1870 if (!REGION_NOT_EMPTY(srcObj
))
1872 REGION_UnlockRgn(srcObj
);
1875 if (!(destObj
= REGION_LockRgn(hDest
)))
1877 REGION_UnlockRgn(srcObj
);
1881 EMPTY_REGION(destObj
);
1882 if (!REGION_CopyRegion(destObj
, srcObj
))
1884 REGION_UnlockRgn(destObj
);
1885 REGION_UnlockRgn(srcObj
);
1889 if (REGION_Complexity(srcObj
) == SIMPLEREGION
)
1891 if (!REGION_CreateSimpleFrameRgn(destObj
, x
, y
))
1893 EMPTY_REGION(destObj
);
1894 REGION_UnlockRgn(destObj
);
1895 REGION_UnlockRgn(srcObj
);
1901 /* Original region moved to right */
1902 rc
= (PRECT
)srcObj
->Buffer
;
1903 for (i
= 0; i
< srcObj
->rdh
.nCount
; i
++)
1909 REGION_IntersectRegion(destObj
, destObj
, srcObj
);
1911 /* Original region moved to left */
1912 rc
= (PRECT
)srcObj
->Buffer
;
1913 for (i
= 0; i
< srcObj
->rdh
.nCount
; i
++)
1919 REGION_IntersectRegion(destObj
, destObj
, srcObj
);
1921 /* Original region moved down */
1922 rc
= (PRECT
)srcObj
->Buffer
;
1923 for (i
= 0; i
< srcObj
->rdh
.nCount
; i
++)
1931 REGION_IntersectRegion(destObj
, destObj
, srcObj
);
1933 /* Original region moved up */
1934 rc
= (PRECT
)srcObj
->Buffer
;
1935 for (i
= 0; i
< srcObj
->rdh
.nCount
; i
++)
1938 rc
->bottom
-= 2 * y
;
1941 REGION_IntersectRegion(destObj
, destObj
, srcObj
);
1943 /* Restore the original region */
1944 rc
= (PRECT
)srcObj
->Buffer
;
1945 for (i
= 0; i
< srcObj
->rdh
.nCount
; i
++)
1951 REGION_SubtractRegion(destObj
, srcObj
, destObj
);
1954 REGION_UnlockRgn(destObj
);
1955 REGION_UnlockRgn(srcObj
);
1966 RECT
*pCurRect
, *pEndRect
;
1967 PROSRGNDATA srcObj
= NULL
;
1968 PROSRGNDATA destObj
= NULL
;
1976 Dc_Attr
= dc
->pDc_Attr
;
1977 if (!Dc_Attr
) Dc_Attr
= &dc
->Dc_Attr
;
1979 if (Dc_Attr
->iMapMode
== MM_TEXT
) // Requires only a translation
1981 if (NtGdiCombineRgn(hDest
, hSrc
, 0, RGN_COPY
) == ERROR
)
1984 NtGdiOffsetRgn(hDest
, Dc_Attr
->ptlViewportOrg
.x
- Dc_Attr
->ptlWindowOrg
.x
,
1985 Dc_Attr
->ptlViewportOrg
.y
- Dc_Attr
->ptlWindowOrg
.y
);
1990 if ( !(srcObj
= REGION_LockRgn(hSrc
)) )
1992 if ( !(destObj
= REGION_LockRgn(hDest
)) )
1994 REGION_UnlockRgn(srcObj
);
1997 EMPTY_REGION(destObj
);
1999 pEndRect
= (PRECT
)srcObj
->Buffer
+ srcObj
->rdh
.nCount
;
2000 for (pCurRect
= (PRECT
)srcObj
->Buffer
; pCurRect
< pEndRect
; pCurRect
++)
2002 tmpRect
= *pCurRect
;
2003 tmpRect
.left
= XLPTODP(Dc_Attr
, tmpRect
.left
);
2004 tmpRect
.top
= YLPTODP(Dc_Attr
, tmpRect
.top
);
2005 tmpRect
.right
= XLPTODP(Dc_Attr
, tmpRect
.right
);
2006 tmpRect
.bottom
= YLPTODP(Dc_Attr
, tmpRect
.bottom
);
2008 if (tmpRect
.left
> tmpRect
.right
)
2010 INT tmp
= tmpRect
.left
;
2011 tmpRect
.left
= tmpRect
.right
;
2012 tmpRect
.right
= tmp
;
2014 if (tmpRect
.top
> tmpRect
.bottom
)
2016 INT tmp
= tmpRect
.top
;
2017 tmpRect
.top
= tmpRect
.bottom
;
2018 tmpRect
.bottom
= tmp
;
2021 REGION_UnionRectWithRgn(destObj
, &tmpRect
);
2025 REGION_UnlockRgn(srcObj
);
2026 REGION_UnlockRgn(destObj
);
2034 REGION_AllocRgnWithHandle(INT nReg
)
2039 pReg
= (PROSRGNDATA
)GDIOBJ_AllocObjWithHandle(GDI_OBJECT_TYPE_REGION
);
2045 hReg
= pReg
->BaseObject
.hHmgr
;
2049 /* Testing shows that > 95% of all regions have only 1 rect.
2050 Including that here saves us from having to do another allocation */
2051 pReg
->Buffer
= &pReg
->rdh
.rcBound
;
2055 pReg
->Buffer
= ExAllocatePoolWithTag(PagedPool
, nReg
* sizeof(RECT
), TAG_REGION
);
2058 REGION_UnlockRgn(pReg
);
2059 GDIOBJ_FreeObjByHandle(hReg
, GDI_OBJECT_TYPE_REGION
);
2065 pReg
->rdh
.dwSize
= sizeof(RGNDATAHEADER
);
2066 pReg
->rdh
.nCount
= nReg
;
2067 pReg
->rdh
.nRgnSize
= nReg
* sizeof(RECT
);
2073 REGION_Cleanup(PVOID ObjectBody
)
2075 PROSRGNDATA pRgn
= (PROSRGNDATA
)ObjectBody
;
2076 if (pRgn
->Buffer
&& pRgn
->Buffer
!= &pRgn
->rdh
.rcBound
)
2077 ExFreePool(pRgn
->Buffer
);
2082 REGION_Delete(PROSRGNDATA pRgn
)
2084 if ( pRgn
== prgnDefault
) return;
2085 return REGION_FreeRgn(pRgn
);
2090 IntGdiReleaseRaoRgn(PDC pDC
)
2092 INT Index
= GDI_HANDLE_GET_INDEX(pDC
->BaseObject
.hHmgr
);
2093 PGDI_TABLE_ENTRY Entry
= &GdiHandleTable
->Entries
[Index
];
2094 pDC
->DC_Flags
|= DC_FLAG_DIRTY_RAO
;
2095 Entry
->Flags
|= GDI_ENTRY_VALIDATE_VIS
;
2096 IntGdiSetEmptyRect((PRECT
)&pDC
->erclClip
);
2101 IntGdiReleaseVisRgn(PDC pDC
)
2103 INT Index
= GDI_HANDLE_GET_INDEX(pDC
->BaseObject
.hHmgr
);
2104 PGDI_TABLE_ENTRY Entry
= &GdiHandleTable
->Entries
[Index
];
2105 pDC
->DC_Flags
|= DC_FLAG_DIRTY_RAO
;
2106 Entry
->Flags
|= GDI_ENTRY_VALIDATE_VIS
;
2107 IntGdiSetEmptyRect((PRECT
)&pDC
->erclClip
);
2108 REGION_Delete(pDC
->prgnVis
);
2109 pDC
->prgnVis
= prgnDefault
;
2113 IntUpdateVisRectRgn(PDC pDC
, PROSRGNDATA pRgn
)
2115 INT Index
= GDI_HANDLE_GET_INDEX(pDC
->BaseObject
.hHmgr
);
2116 PGDI_TABLE_ENTRY Entry
= &GdiHandleTable
->Entries
[Index
];
2120 if (Entry
->Flags
& GDI_ENTRY_VALIDATE_VIS
)
2122 pDc_Attr
= pDC
->pDc_Attr
;
2123 if ( !pDc_Attr
) pDc_Attr
= &pDC
->Dc_Attr
;
2125 pDc_Attr
->VisRectRegion
.Flags
= REGION_Complexity(pRgn
);
2127 if (pRgn
&& pDc_Attr
->VisRectRegion
.Flags
!= NULLREGION
)
2129 rcl
.left
= pRgn
->rdh
.rcBound
.left
;
2130 rcl
.top
= pRgn
->rdh
.rcBound
.top
;
2131 rcl
.right
= pRgn
->rdh
.rcBound
.right
;
2132 rcl
.bottom
= pRgn
->rdh
.rcBound
.bottom
;
2134 rcl
.left
-= pDC
->erclWindow
.left
;
2135 rcl
.top
-= pDC
->erclWindow
.top
;
2136 rcl
.right
-= pDC
->erclWindow
.left
;
2137 rcl
.bottom
-= pDC
->erclWindow
.top
;
2140 IntGdiSetEmptyRect((PRECT
)&rcl
);
2142 pDc_Attr
->VisRectRegion
.Rect
= rcl
;
2144 Entry
->Flags
&= ~GDI_ENTRY_VALIDATE_VIS
;
2150 IntGdiCombineRgn(PROSRGNDATA destRgn
,
2151 PROSRGNDATA src1Rgn
,
2152 PROSRGNDATA src2Rgn
,
2161 if (CombineMode
== RGN_COPY
)
2163 if ( !REGION_CopyRegion(destRgn
, src1Rgn
) )
2165 result
= REGION_Complexity(destRgn
);
2171 switch (CombineMode
)
2174 REGION_IntersectRegion(destRgn
, src1Rgn
, src2Rgn
);
2177 REGION_UnionRegion(destRgn
, src1Rgn
, src2Rgn
);
2180 REGION_XorRegion(destRgn
, src1Rgn
, src2Rgn
);
2183 REGION_SubtractRegion(destRgn
, src1Rgn
, src2Rgn
);
2186 result
= REGION_Complexity(destRgn
);
2188 else if (src2Rgn
== NULL
)
2190 DPRINT1("IntGdiCombineRgn requires hSrc2 != NULL for combine mode %d!\n", CombineMode
);
2197 DPRINT("IntGdiCombineRgn: hDest unavailable\n");
2204 // NtGdi Exported Functions
2207 NtGdiCombineRgn(HRGN hDest
,
2213 PROSRGNDATA destRgn
, src1Rgn
, src2Rgn
;
2215 destRgn
= REGION_LockRgn(hDest
);
2218 src1Rgn
= REGION_LockRgn(hSrc1
);
2221 if (CombineMode
== RGN_COPY
)
2223 if ( !REGION_CopyRegion(destRgn
, src1Rgn
) )
2225 result
= REGION_Complexity(destRgn
);
2229 src2Rgn
= REGION_LockRgn(hSrc2
);
2232 switch (CombineMode
)
2235 REGION_IntersectRegion(destRgn
, src1Rgn
, src2Rgn
);
2238 REGION_UnionRegion(destRgn
, src1Rgn
, src2Rgn
);
2241 REGION_XorRegion(destRgn
, src1Rgn
, src2Rgn
);
2244 REGION_SubtractRegion(destRgn
, src1Rgn
, src2Rgn
);
2247 REGION_UnlockRgn(src2Rgn
);
2248 result
= REGION_Complexity(destRgn
);
2250 else if (hSrc2
== NULL
)
2252 DPRINT1("NtGdiCombineRgn requires hSrc2 != NULL for combine mode %d!\n", CombineMode
);
2256 REGION_UnlockRgn(src1Rgn
);
2259 REGION_UnlockRgn(destRgn
);
2263 DPRINT("NtGdiCombineRgn: hDest unavailable\n");
2272 NtGdiCreateEllipticRgn(
2279 return NtGdiCreateRoundRectRgn(Left
, Top
, Right
, Bottom
,
2280 Right
- Left
, Bottom
- Top
);
2285 IntGdiCreateRectRgn(INT LeftRect
, INT TopRect
, INT RightRect
, INT BottomRect
)
2289 if (!(pRgn
= REGION_AllocRgnWithHandle(1))) return NULL
;
2291 REGION_SetRectRgn(pRgn
, LeftRect
, TopRect
, RightRect
, BottomRect
);
2292 REGION_UnlockRgn(pRgn
);
2293 // Return pointer with Share locks.
2294 pRgn
= GDIOBJ_ShareLockObj(pRgn
->BaseObject
.hHmgr
, GDI_OBJECT_TYPE_REGION
);
2301 NtGdiCreateRectRgn(INT LeftRect
, INT TopRect
, INT RightRect
, INT BottomRect
)
2306 /* Allocate region data structure with space for 1 RECT */
2307 if (!(pRgn
= REGION_AllocRgnWithHandle(1)))
2309 SetLastWin32Error(ERROR_NOT_ENOUGH_MEMORY
);
2312 hRgn
= pRgn
->BaseObject
.hHmgr
;
2314 REGION_SetRectRgn(pRgn
, LeftRect
, TopRect
, RightRect
, BottomRect
);
2315 REGION_UnlockRgn(pRgn
);
2323 NtGdiCreateRoundRectRgn(
2334 int asq
, bsq
, d
, xd
, yd
;
2337 /* Make the dimensions sensible */
2352 ellipse_width
= abs(ellipse_width
);
2353 ellipse_height
= abs(ellipse_height
);
2355 /* Check parameters */
2357 if (ellipse_width
> right
-left
) ellipse_width
= right
-left
;
2358 if (ellipse_height
> bottom
-top
) ellipse_height
= bottom
-top
;
2360 /* Check if we can do a normal rectangle instead */
2362 if ((ellipse_width
< 2) || (ellipse_height
< 2))
2363 return NtGdiCreateRectRgn(left
, top
, right
, bottom
);
2367 d
= (ellipse_height
< 128) ? ((3 * ellipse_height
) >> 2) : 64;
2368 if (!(obj
= REGION_AllocRgnWithHandle(d
))) return 0;
2369 hrgn
= obj
->BaseObject
.hHmgr
;
2371 /* Ellipse algorithm, based on an article by K. Porter */
2372 /* in DDJ Graphics Programming Column, 8/89 */
2374 asq
= ellipse_width
* ellipse_width
/ 4; /* a^2 */
2375 bsq
= ellipse_height
* ellipse_height
/ 4; /* b^2 */
2376 d
= bsq
- asq
* ellipse_height
/ 2 + asq
/ 4; /* b^2 - a^2b + a^2/4 */
2378 yd
= asq
* ellipse_height
; /* 2a^2b */
2380 rect
.left
= left
+ ellipse_width
/ 2;
2381 rect
.right
= right
- ellipse_width
/ 2;
2383 /* Loop to draw first half of quadrant */
2387 if (d
> 0) /* if nearest pixel is toward the center */
2389 /* move toward center */
2391 rect
.bottom
= rect
.top
+ 1;
2392 REGION_UnionRectWithRgn(obj
, &rect
);
2393 rect
.top
= --bottom
;
2394 rect
.bottom
= rect
.top
+ 1;
2395 REGION_UnionRectWithRgn(obj
, &rect
);
2399 rect
.left
--; /* next horiz point */
2404 /* Loop to draw second half of quadrant */
2406 d
+= (3 * (asq
-bsq
) / 2 - (xd
+yd
)) / 2;
2409 /* next vertical point */
2411 rect
.bottom
= rect
.top
+ 1;
2412 REGION_UnionRectWithRgn(obj
, &rect
);
2413 rect
.top
= --bottom
;
2414 rect
.bottom
= rect
.top
+ 1;
2415 REGION_UnionRectWithRgn(obj
, &rect
);
2416 if (d
< 0) /* if nearest pixel is outside ellipse */
2418 rect
.left
--; /* move away from center */
2426 /* Add the inside rectangle */
2431 rect
.bottom
= bottom
;
2432 REGION_UnionRectWithRgn(obj
, &rect
);
2435 REGION_UnlockRgn(obj
);
2446 PROSRGNDATA rgn1
, rgn2
;
2447 PRECT tRect1
, tRect2
;
2451 if ( !(rgn1
= REGION_LockRgn(hSrcRgn1
)) )
2454 if ( !(rgn2
= REGION_LockRgn(hSrcRgn2
)) )
2456 REGION_UnlockRgn(rgn1
);
2460 if (rgn1
->rdh
.nCount
!= rgn2
->rdh
.nCount
||
2461 rgn1
->rdh
.nCount
== 0 ||
2462 rgn1
->rdh
.rcBound
.left
!= rgn2
->rdh
.rcBound
.left
||
2463 rgn1
->rdh
.rcBound
.right
!= rgn2
->rdh
.rcBound
.right
||
2464 rgn1
->rdh
.rcBound
.top
!= rgn2
->rdh
.rcBound
.top
||
2465 rgn1
->rdh
.rcBound
.bottom
!= rgn2
->rdh
.rcBound
.bottom
)
2468 tRect1
= (PRECT
)rgn1
->Buffer
;
2469 tRect2
= (PRECT
)rgn2
->Buffer
;
2471 if (!tRect1
|| !tRect2
)
2474 for (i
=0; i
< rgn1
->rdh
.nCount
; i
++)
2476 if (tRect1
[i
].left
!= tRect2
[i
].left
||
2477 tRect1
[i
].right
!= tRect2
[i
].right
||
2478 tRect1
[i
].top
!= tRect2
[i
].top
||
2479 tRect1
[i
].bottom
!= tRect2
[i
].bottom
)
2485 REGION_UnlockRgn(rgn1
);
2486 REGION_UnlockRgn(rgn2
);
2492 NtGdiExtCreateRegion(
2493 OPTIONAL LPXFORM Xform
,
2501 NTSTATUS Status
= STATUS_SUCCESS
;
2504 DPRINT("NtGdiExtCreateRegion\n");
2507 ProbeForRead(RgnData
, Count
, 1);
2508 nCount
= RgnData
->rdh
.nCount
;
2509 if (Count
< sizeof(RGNDATAHEADER
) + nCount
* sizeof(RECT
) ||
2511 RgnData
->rdh
.iType
!= RDH_RECTANGLES
||
2512 RgnData
->rdh
.dwSize
!= sizeof(RGNDATAHEADER
))
2514 Status
= STATUS_INVALID_PARAMETER
;
2520 Status
= _SEH_GetExceptionCode();
2523 if (!NT_SUCCESS(Status
))
2525 SetLastNtError(Status
);
2529 Region
= REGION_AllocRgnWithHandle(nCount
);
2533 SetLastWin32Error(ERROR_NOT_ENOUGH_MEMORY
);
2536 hRgn
= Region
->BaseObject
.hHmgr
;
2541 Region
->rdh
= RgnData
->rdh
;
2547 /* Init the XFORMOBJ from the Xform struct */
2548 Status
= STATUS_INVALID_PARAMETER
;
2549 ret
= XFORMOBJ_iSetXform((XFORMOBJ
*)&matrix
, (XFORML
*)Xform
);
2551 /* Check for error, also no scale and shear allowed */
2552 if (ret
!= DDI_ERROR
&& ret
!= GX_GENERAL
)
2554 /* Apply the coordinate transformation on the rects */
2555 if (XFORMOBJ_bApplyXform((XFORMOBJ
*)&matrix
,
2561 Status
= STATUS_SUCCESS
;
2567 /* Copy rect coordinates */
2568 RtlCopyMemory(Region
->Buffer
,
2570 nCount
* sizeof(RECT
));
2575 Status
= _SEH_GetExceptionCode();
2578 if (!NT_SUCCESS(Status
))
2580 SetLastWin32Error(ERROR_INVALID_PARAMETER
);
2581 REGION_UnlockRgn(Region
);
2582 NtGdiDeleteObject(hRgn
);
2586 REGION_UnlockRgn(Region
);
2603 if (NULL
== (rgn
= REGION_LockRgn(hRgn
)))
2608 if (NULL
== (oldhBrush
= NtGdiSelectBrush(hDC
, hBrush
)))
2610 REGION_UnlockRgn(rgn
);
2614 for (r
= rgn
->Buffer
; r
< rgn
->Buffer
+ rgn
->rdh
.nCount
; r
++)
2616 NtGdiPatBlt(hDC
, r
->left
, r
->top
, r
->right
- r
->left
, r
->bottom
- r
->top
, PATCOPY
);
2619 REGION_UnlockRgn(rgn
);
2620 NtGdiSelectBrush(hDC
, oldhBrush
);
2638 if (!(FrameRgn
= NtGdiCreateRectRgn(0, 0, 0, 0)))
2642 if (!REGION_CreateFrameRgn(FrameRgn
, hRgn
, Width
, Height
))
2644 NtGdiDeleteObject(FrameRgn
);
2648 Ret
= NtGdiFillRgn(hDC
, FrameRgn
, hBrush
);
2650 NtGdiDeleteObject(FrameRgn
);
2664 *pRect
= Rgn
->rdh
.rcBound
;
2665 ret
= REGION_Complexity(Rgn
);
2669 return 0; //if invalid region return zero
2673 /* See wine, msdn, osr and Feng Yuan - Windows Graphics Programming Win32 Gdi And Directdraw
2675 1st: http://www.codeproject.com/gdi/cliprgnguide.asp is wrong!
2677 The intersection of the clip with the meta region is not Rao it's API!
2678 Go back and read 7.2 Clipping pages 418-19:
2680 1) The Rao region is the intersection of the API region and the system region,
2681 named after the Microsoft engineer who initially proposed it.
2682 2) The Rao region can be calculated from the API region and the system region.
2685 API region is the intersection of the meta region and the clipping region,
2686 clearly named after the fact that it is controlled by GDI API calls.
2700 pDC
= DC_LockDc(hDC
);
2703 SetLastWin32Error(ERROR_INVALID_HANDLE
);
2710 hSrc
= pDC
->w
.hClipRgn
;
2711 // if (pDC->DcLevel.prgnClip) hSrc = ((PROSRGNDATA)pDC->DcLevel.prgnClip)->BaseObject.hHmgr;
2714 if (pDC
->DcLevel
.prgnMeta
) hSrc
= ((PROSRGNDATA
)pDC
->DcLevel
.prgnMeta
)->BaseObject
.hHmgr
;
2717 DPRINT1("hMetaRgn not implemented\n");
2718 //hSrc = dc->hMetaClipRgn;
2719 if (!hSrc
) hSrc
= pDC
->w
.hClipRgn
;
2720 //if (!hSrc) rgn = dc->hMetaRgn;
2721 // if (pDC->prgnAPI) hSrc = ((PROSRGNDATA)pDC->prgnAPI)->BaseObject.hHmgr;
2722 // else if (pDC->DcLevel.prgnClip) hSrc = ((PROSRGNDATA)pDC->DcLevel.prgnClip)->BaseObject.hHmgr;
2723 // else if (pDC->DcLevel.prgnMeta) hSrc = ((PROSRGNDATA)pDC->DcLevel.prgnMeta)->BaseObject.hHmgr;
2726 hSrc
= pDC
->w
.hVisRgn
;
2727 // if (pDC->prgnVis) hSrc = ((PROSRGNDATA)pDC->prgnVis)->BaseObject.hHmgr;
2734 if (NtGdiCombineRgn(hDest
, hSrc
, 0, RGN_COPY
) == ERROR
)
2743 if (iCode
== SYSRGN
)
2745 IntGdiGetDCOrg(pDC
, &org
);
2746 NtGdiOffsetRgn(hDest
, org
.x
, org
.y
);
2763 if (!(Rgn
= REGION_LockRgn(hRgn
)))
2768 ret
= REGION_GetRgnBox(Rgn
, pRect
);
2769 REGION_UnlockRgn(Rgn
);
2784 NTSTATUS Status
= STATUS_SUCCESS
;
2786 if (!(Rgn
= REGION_LockRgn(hRgn
)))
2791 ret
= REGION_GetRgnBox(Rgn
, &SafeRect
);
2792 REGION_UnlockRgn(Rgn
);
2800 ProbeForWrite(pRect
, sizeof(RECT
), 1);
2805 Status
= _SEH_GetExceptionCode();
2808 if (!NT_SUCCESS(Status
))
2823 PROSRGNDATA RgnData
;
2827 if (!(RgnData
= REGION_LockRgn(hRgn
)))
2829 SetLastWin32Error(ERROR_INVALID_HANDLE
);
2833 rc
= (PRECT
)RgnData
->Buffer
;
2834 for (i
= 0; i
< RgnData
->rdh
.nCount
; i
++)
2837 if (!NtGdiPatBlt(hDC
, rc
->left
, rc
->top
, rc
->right
- rc
->left
, rc
->bottom
- rc
->top
, DSTINVERT
))
2839 REGION_UnlockRgn(RgnData
);
2845 REGION_UnlockRgn(RgnData
);
2857 PROSRGNDATA rgn
= REGION_LockRgn(hRgn
);
2860 DPRINT("NtGdiOffsetRgn: hRgn %d Xoffs %d Yoffs %d rgn %x\n", hRgn
, XOffset
, YOffset
, rgn
);
2864 DPRINT("NtGdiOffsetRgn: hRgn error\n");
2868 if (XOffset
|| YOffset
)
2870 int nbox
= rgn
->rdh
.nCount
;
2871 PRECT pbox
= (PRECT
)rgn
->Buffer
;
2877 pbox
->left
+= XOffset
;
2878 pbox
->right
+= XOffset
;
2879 pbox
->top
+= YOffset
;
2880 pbox
->bottom
+= YOffset
;
2883 if (rgn
->Buffer
!= &rgn
->rdh
.rcBound
)
2885 rgn
->rdh
.rcBound
.left
+= XOffset
;
2886 rgn
->rdh
.rcBound
.right
+= XOffset
;
2887 rgn
->rdh
.rcBound
.top
+= YOffset
;
2888 rgn
->rdh
.rcBound
.bottom
+= YOffset
;
2892 ret
= REGION_Complexity(rgn
);
2893 REGION_UnlockRgn(rgn
);
2906 CLIPOBJ
* ClipRegion
;
2908 PGDIBRUSHOBJ pBrush
;
2909 GDIBRUSHINST BrushInst
;
2911 BITMAPOBJ
*BitmapObj
;
2914 if (!dc
) return FALSE
;
2915 Dc_Attr
= dc
->pDc_Attr
;
2916 if (!Dc_Attr
) Dc_Attr
= &dc
->Dc_Attr
;
2918 if (!(tmpVisRgn
= NtGdiCreateRectRgn(0, 0, 0, 0))) return FALSE
;
2920 // Transform region into device co-ords
2921 if (!REGION_LPTODP(dc
, tmpVisRgn
, hRgn
) ||
2922 NtGdiOffsetRgn(tmpVisRgn
, dc
->ptlDCOrig
.x
, dc
->ptlDCOrig
.y
) == ERROR
)
2924 NtGdiDeleteObject(tmpVisRgn
);
2928 NtGdiCombineRgn(tmpVisRgn
, tmpVisRgn
, dc
->w
.hGCClipRgn
, RGN_AND
);
2930 visrgn
= REGION_LockRgn(tmpVisRgn
);
2933 NtGdiDeleteObject(tmpVisRgn
);
2937 ClipRegion
= IntEngCreateClipRegion(visrgn
->rdh
.nCount
,
2938 (PRECTL
)visrgn
->Buffer
,
2939 (PRECTL
)&visrgn
->rdh
.rcBound
);
2941 pBrush
= BRUSHOBJ_LockBrush(Dc_Attr
->hbrush
);
2943 IntGdiInitBrushInstance(&BrushInst
, pBrush
, dc
->XlateBrush
);
2945 BrushOrigin
.x
= Dc_Attr
->ptlBrushOrigin
.x
;
2946 BrushOrigin
.y
= Dc_Attr
->ptlBrushOrigin
.y
;
2947 BitmapObj
= BITMAPOBJ_LockBitmap(dc
->w
.hBitmap
);
2948 /* FIXME - Handle BitmapObj == NULL !!!! */
2950 bRet
= IntEngPaint(&BitmapObj
->SurfObj
,
2952 &BrushInst
.BrushObject
,
2954 0xFFFF);//FIXME:don't know what to put here
2956 BITMAPOBJ_UnlockBitmap(BitmapObj
);
2957 BRUSHOBJ_UnlockBrush(pBrush
);
2958 REGION_UnlockRgn(visrgn
);
2959 NtGdiDeleteObject(tmpVisRgn
);
2977 if (!(rgn
= REGION_LockRgn(hRgn
) ) )
2980 if (rgn
->rdh
.nCount
> 0 && INRECT(rgn
->rdh
.rcBound
, X
, Y
))
2982 r
= (PRECT
) rgn
->Buffer
;
2983 for (i
= 0; i
< rgn
->rdh
.nCount
; i
++)
2985 if (INRECT(*r
, X
, Y
))
2987 REGION_UnlockRgn(rgn
);
2993 REGION_UnlockRgn(rgn
);
2999 REGION_RectInRegion(
3004 PRECT pCurRect
, pRectEnd
;
3006 // this is (just) a useful optimization
3007 if ((Rgn
->rdh
.nCount
> 0) && EXTENTCHECK(&Rgn
->rdh
.rcBound
, rc
))
3009 for (pCurRect
= (PRECT
)Rgn
->Buffer
, pRectEnd
= pCurRect
+ Rgn
->rdh
.nCount
; pCurRect
< pRectEnd
; pCurRect
++)
3011 if (pCurRect
->bottom
<= rc
->top
) continue; // not far enough down yet
3012 if (pCurRect
->top
>= rc
->bottom
) break; // too far down
3013 if (pCurRect
->right
<= rc
->left
) continue; // not far enough over yet
3014 if (pCurRect
->left
>= rc
->right
) continue;
3032 NTSTATUS Status
= STATUS_SUCCESS
;
3034 if (!(Rgn
= REGION_LockRgn(hRgn
)))
3041 ProbeForRead(unsaferc
, sizeof(RECT
), 1);
3046 Status
= _SEH_GetExceptionCode();
3050 if (!NT_SUCCESS(Status
))
3052 REGION_UnlockRgn(Rgn
);
3053 SetLastNtError(Status
);
3054 DPRINT1("NtGdiRectInRegion: bogus rc\n");
3058 Ret
= REGION_RectInRegion(Rgn
, &rc
);
3059 REGION_UnlockRgn(Rgn
);
3075 if (LeftRect
> RightRect
)
3078 LeftRect
= RightRect
;
3081 if (TopRect
> BottomRect
)
3084 TopRect
= BottomRect
;
3088 if ((LeftRect
!= RightRect
) && (TopRect
!= BottomRect
))
3090 firstRect
= (PRECT
)rgn
->Buffer
;
3092 firstRect
->left
= rgn
->rdh
.rcBound
.left
= LeftRect
;
3093 firstRect
->top
= rgn
->rdh
.rcBound
.top
= TopRect
;
3094 firstRect
->right
= rgn
->rdh
.rcBound
.right
= RightRect
;
3095 firstRect
->bottom
= rgn
->rdh
.rcBound
.bottom
= BottomRect
;
3096 rgn
->rdh
.nCount
= 1;
3097 rgn
->rdh
.iType
= RDH_RECTANGLES
;
3115 if ( !(rgn
= REGION_LockRgn(hRgn
)) )
3117 return 0; //per documentation
3120 REGION_SetRectRgn(rgn
, LeftRect
, TopRect
, RightRect
, BottomRect
);
3122 REGION_UnlockRgn(rgn
);
3127 NtGdiUnionRectWithRgn(
3129 CONST PRECT UnsafeRect
3132 RECT SafeRect
= {0};
3134 NTSTATUS Status
= STATUS_SUCCESS
;
3136 if (!(Rgn
= REGION_LockRgn(hDest
)))
3138 SetLastWin32Error(ERROR_INVALID_HANDLE
);
3144 ProbeForRead(UnsafeRect
, sizeof(RECT
), 1);
3145 SafeRect
= *UnsafeRect
;
3149 Status
= _SEH_GetExceptionCode();
3153 if (! NT_SUCCESS(Status
))
3155 REGION_UnlockRgn(Rgn
);
3156 SetLastNtError(Status
);
3160 REGION_UnionRectWithRgn(Rgn
, &SafeRect
);
3161 REGION_UnlockRgn(Rgn
);
3166 * MSDN: GetRegionData, Return Values:
3168 * "If the function succeeds and dwCount specifies an adequate number of bytes,
3169 * the return value is always dwCount. If dwCount is too small or the function
3170 * fails, the return value is 0. If lpRgnData is NULL, the return value is the
3171 * required number of bytes.
3173 * If the function fails, the return value is zero."
3183 PROSRGNDATA obj
= REGION_LockRgn(hrgn
);
3184 NTSTATUS Status
= STATUS_SUCCESS
;
3189 size
= obj
->rdh
.nCount
* sizeof(RECT
);
3190 if (count
< (size
+ sizeof(RGNDATAHEADER
)) || rgndata
== NULL
)
3192 REGION_UnlockRgn(obj
);
3193 if (rgndata
) /* buffer is too small, signal it by return 0 */
3195 else /* user requested buffer size with rgndata NULL */
3196 return size
+ sizeof(RGNDATAHEADER
);
3201 ProbeForWrite(rgndata
, count
, 1);
3202 RtlCopyMemory(rgndata
, &obj
->rdh
, sizeof(RGNDATAHEADER
));
3203 RtlCopyMemory(rgndata
->Buffer
, obj
->Buffer
, size
);
3207 Status
= _SEH_GetExceptionCode();
3211 if (!NT_SUCCESS(Status
))
3213 SetLastNtError(Status
);
3214 REGION_UnlockRgn(obj
);
3218 REGION_UnlockRgn(obj
);
3219 return size
+ sizeof(RGNDATAHEADER
);
3223 /***********************************************************************
3224 * REGION_InsertEdgeInET
3226 * Insert the given edge into the edge table.
3227 * First we must find the correct bucket in the
3228 * Edge table, then find the right slot in the
3229 * bucket. Finally, we can insert it.
3232 static void FASTCALL
3233 REGION_InsertEdgeInET(
3235 EdgeTableEntry
*ETE
,
3237 ScanLineListBlock
**SLLBlock
,
3241 EdgeTableEntry
*start
, *prev
;
3242 ScanLineList
*pSLL
, *pPrevSLL
;
3243 ScanLineListBlock
*tmpSLLBlock
;
3246 * find the right bucket to put the edge into
3248 pPrevSLL
= &ET
->scanlines
;
3249 pSLL
= pPrevSLL
->next
;
3250 while (pSLL
&& (pSLL
->scanline
< scanline
))
3257 * reassign pSLL (pointer to ScanLineList) if necessary
3259 if ((!pSLL
) || (pSLL
->scanline
> scanline
))
3261 if (*iSLLBlock
> SLLSPERBLOCK
-1)
3263 tmpSLLBlock
= ExAllocatePoolWithTag(PagedPool
, sizeof(ScanLineListBlock
), TAG_REGION
);
3266 DPRINT1("REGION_InsertEdgeInETL(): Can't alloc SLLB\n");
3267 /* FIXME - free resources? */
3270 (*SLLBlock
)->next
= tmpSLLBlock
;
3271 tmpSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
3272 *SLLBlock
= tmpSLLBlock
;
3275 pSLL
= &((*SLLBlock
)->SLLs
[(*iSLLBlock
)++]);
3277 pSLL
->next
= pPrevSLL
->next
;
3278 pSLL
->edgelist
= (EdgeTableEntry
*)NULL
;
3279 pPrevSLL
->next
= pSLL
;
3281 pSLL
->scanline
= scanline
;
3284 * now insert the edge in the right bucket
3286 prev
= (EdgeTableEntry
*)NULL
;
3287 start
= pSLL
->edgelist
;
3288 while (start
&& (start
->bres
.minor_axis
< ETE
->bres
.minor_axis
))
3291 start
= start
->next
;
3298 pSLL
->edgelist
= ETE
;
3301 /***********************************************************************
3304 * This routine moves EdgeTableEntries from the
3305 * EdgeTable into the Active Edge Table,
3306 * leaving them sorted by smaller x coordinate.
3309 static void FASTCALL
3311 EdgeTableEntry
*AET
,
3312 EdgeTableEntry
*ETEs
3315 EdgeTableEntry
*pPrevAET
;
3316 EdgeTableEntry
*tmp
;
3322 while (AET
&& (AET
->bres
.minor_axis
< ETEs
->bres
.minor_axis
))
3331 ETEs
->back
= pPrevAET
;
3332 pPrevAET
->next
= ETEs
;
3339 /***********************************************************************
3340 * REGION_computeWAET
3342 * This routine links the AET by the
3343 * nextWETE (winding EdgeTableEntry) link for
3344 * use by the winding number rule. The final
3345 * Active Edge Table (AET) might look something
3349 * ---------- --------- ---------
3350 * |ymax | |ymax | |ymax |
3351 * | ... | |... | |... |
3352 * |next |->|next |->|next |->...
3353 * |nextWETE| |nextWETE| |nextWETE|
3354 * --------- --------- ^--------
3356 * V-------------------> V---> ...
3359 static void FASTCALL
3360 REGION_computeWAET(EdgeTableEntry
*AET
)
3362 register EdgeTableEntry
*pWETE
;
3363 register int inside
= 1;
3364 register int isInside
= 0;
3366 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
3376 if ( (!inside
&& !isInside
) ||
3377 ( inside
&& isInside
) )
3379 pWETE
->nextWETE
= AET
;
3385 pWETE
->nextWETE
= (EdgeTableEntry
*)NULL
;
3388 /***********************************************************************
3389 * REGION_InsertionSort
3391 * Just a simple insertion sort using
3392 * pointers and back pointers to sort the Active
3396 static BOOL FASTCALL
3397 REGION_InsertionSort(EdgeTableEntry
*AET
)
3399 EdgeTableEntry
*pETEchase
;
3400 EdgeTableEntry
*pETEinsert
;
3401 EdgeTableEntry
*pETEchaseBackTMP
;
3402 BOOL changed
= FALSE
;
3409 while (pETEchase
->back
->bres
.minor_axis
> AET
->bres
.minor_axis
)
3410 pETEchase
= pETEchase
->back
;
3413 if (pETEchase
!= pETEinsert
)
3415 pETEchaseBackTMP
= pETEchase
->back
;
3416 pETEinsert
->back
->next
= AET
;
3418 AET
->back
= pETEinsert
->back
;
3419 pETEinsert
->next
= pETEchase
;
3420 pETEchase
->back
->next
= pETEinsert
;
3421 pETEchase
->back
= pETEinsert
;
3422 pETEinsert
->back
= pETEchaseBackTMP
;
3429 /***********************************************************************
3430 * REGION_FreeStorage
3434 static void FASTCALL
3435 REGION_FreeStorage(ScanLineListBlock
*pSLLBlock
)
3437 ScanLineListBlock
*tmpSLLBlock
;
3441 tmpSLLBlock
= pSLLBlock
->next
;
3442 ExFreePool(pSLLBlock
);
3443 pSLLBlock
= tmpSLLBlock
;
3448 /***********************************************************************
3449 * REGION_PtsToRegion
3451 * Create an array of rectangles from a list of points.
3455 int numFullPtBlocks
,
3457 POINTBLOCK
*FirstPtBlock
,
3462 POINTBLOCK
*CurPtBlock
;
3464 RECT
*extents
, *temp
;
3467 extents
= ®
->rdh
.rcBound
;
3469 numRects
= ((numFullPtBlocks
* NUMPTSTOBUFFER
) + iCurPtBlock
) >> 1;
3471 if (!(temp
= ExAllocatePoolWithTag(PagedPool
, numRects
* sizeof(RECT
), TAG_REGION
)))
3475 if (reg
->Buffer
!= NULL
)
3477 COPY_RECTS(temp
, reg
->Buffer
, reg
->rdh
.nCount
);
3478 if (reg
->Buffer
!= ®
->rdh
.rcBound
)
3479 ExFreePoolWithTag(reg
->Buffer
, TAG_REGION
);
3483 reg
->rdh
.nCount
= numRects
;
3484 CurPtBlock
= FirstPtBlock
;
3485 rects
= reg
->Buffer
- 1;
3487 extents
->left
= LARGE_COORDINATE
, extents
->right
= SMALL_COORDINATE
;
3489 for ( ; numFullPtBlocks
>= 0; numFullPtBlocks
--)
3491 /* the loop uses 2 points per iteration */
3492 i
= NUMPTSTOBUFFER
>> 1;
3493 if (!numFullPtBlocks
)
3494 i
= iCurPtBlock
>> 1;
3495 for (pts
= CurPtBlock
->pts
; i
--; pts
+= 2)
3497 if (pts
->x
== pts
[1].x
)
3499 if (numRects
&& pts
->x
== rects
->left
&& pts
->y
== rects
->bottom
&&
3500 pts
[1].x
== rects
->right
&&
3501 (numRects
== 1 || rects
[-1].top
!= rects
->top
) &&
3502 (i
&& pts
[2].y
> pts
[1].y
))
3504 rects
->bottom
= pts
[1].y
+ 1;
3509 rects
->left
= pts
->x
;
3510 rects
->top
= pts
->y
;
3511 rects
->right
= pts
[1].x
;
3512 rects
->bottom
= pts
[1].y
+ 1;
3513 if (rects
->left
< extents
->left
)
3514 extents
->left
= rects
->left
;
3515 if (rects
->right
> extents
->right
)
3516 extents
->right
= rects
->right
;
3518 CurPtBlock
= CurPtBlock
->next
;
3523 extents
->top
= reg
->Buffer
->top
;
3524 extents
->bottom
= rects
->bottom
;
3531 extents
->bottom
= 0;
3533 reg
->rdh
.nCount
= numRects
;
3538 /***********************************************************************
3539 * REGION_CreateEdgeTable
3541 * This routine creates the edge table for
3542 * scan converting polygons.
3543 * The Edge Table (ET) looks like:
3547 * | ymax | ScanLineLists
3548 * |scanline|-->------------>-------------->...
3549 * -------- |scanline| |scanline|
3550 * |edgelist| |edgelist|
3551 * --------- ---------
3555 * list of ETEs list of ETEs
3557 * where ETE is an EdgeTableEntry data structure,
3558 * and there is one ScanLineList per scanline at
3559 * which an edge is initially entered.
3562 static void FASTCALL
3563 REGION_CreateETandAET(
3568 EdgeTableEntry
*AET
,
3569 EdgeTableEntry
*pETEs
,
3570 ScanLineListBlock
*pSLLBlock
3573 const POINT
*top
, *bottom
;
3574 const POINT
*PrevPt
, *CurrPt
, *EndPt
;
3581 * initialize the Active Edge Table
3583 AET
->next
= (EdgeTableEntry
*)NULL
;
3584 AET
->back
= (EdgeTableEntry
*)NULL
;
3585 AET
->nextWETE
= (EdgeTableEntry
*)NULL
;
3586 AET
->bres
.minor_axis
= SMALL_COORDINATE
;
3589 * initialize the Edge Table.
3591 ET
->scanlines
.next
= (ScanLineList
*)NULL
;
3592 ET
->ymax
= SMALL_COORDINATE
;
3593 ET
->ymin
= LARGE_COORDINATE
;
3594 pSLLBlock
->next
= (ScanLineListBlock
*)NULL
;
3597 for (poly
= 0; poly
< nbpolygons
; poly
++)
3599 count
= Count
[poly
];
3607 * for each vertex in the array of points.
3608 * In this loop we are dealing with two vertices at
3609 * a time -- these make up one edge of the polygon.
3616 * find out which point is above and which is below.
3618 if (PrevPt
->y
> CurrPt
->y
)
3620 bottom
= PrevPt
, top
= CurrPt
;
3621 pETEs
->ClockWise
= 0;
3625 bottom
= CurrPt
, top
= PrevPt
;
3626 pETEs
->ClockWise
= 1;
3630 * don't add horizontal edges to the Edge table.
3632 if (bottom
->y
!= top
->y
)
3634 pETEs
->ymax
= bottom
->y
-1;
3635 /* -1 so we don't get last scanline */
3638 * initialize integer edge algorithm
3640 dy
= bottom
->y
- top
->y
;
3641 BRESINITPGONSTRUCT(dy
, top
->x
, bottom
->x
, pETEs
->bres
);
3643 REGION_InsertEdgeInET(ET
, pETEs
, top
->y
, &pSLLBlock
,
3646 if (PrevPt
->y
> ET
->ymax
)
3647 ET
->ymax
= PrevPt
->y
;
3648 if (PrevPt
->y
< ET
->ymin
)
3649 ET
->ymin
= PrevPt
->y
;
3659 IntCreatePolyPolygonRgn(
3668 EdgeTableEntry
*pAET
; /* Active Edge Table */
3669 INT y
; /* current scanline */
3670 int iPts
= 0; /* number of pts in buffer */
3671 EdgeTableEntry
*pWETE
; /* Winding Edge Table Entry*/
3672 ScanLineList
*pSLL
; /* current scanLineList */
3673 POINT
*pts
; /* output buffer */
3674 EdgeTableEntry
*pPrevAET
; /* ptr to previous AET */
3675 EdgeTable ET
; /* header node for ET */
3676 EdgeTableEntry AET
; /* header node for AET */
3677 EdgeTableEntry
*pETEs
; /* EdgeTableEntries pool */
3678 ScanLineListBlock SLLBlock
; /* header for scanlinelist */
3679 int fixWAET
= FALSE
;
3680 POINTBLOCK FirstPtBlock
, *curPtBlock
; /* PtBlock buffers */
3681 POINTBLOCK
*tmpPtBlock
;
3682 int numFullPtBlocks
= 0;
3685 if (mode
== 0 || mode
> 2) return 0;
3687 if (!(region
= REGION_AllocRgnWithHandle(nbpolygons
)))
3689 hrgn
= region
->BaseObject
.hHmgr
;
3691 /* special case a rectangle */
3693 if (((nbpolygons
== 1) && ((*Count
== 4) ||
3694 ((*Count
== 5) && (Pts
[4].x
== Pts
[0].x
) && (Pts
[4].y
== Pts
[0].y
)))) &&
3695 (((Pts
[0].y
== Pts
[1].y
) &&
3696 (Pts
[1].x
== Pts
[2].x
) &&
3697 (Pts
[2].y
== Pts
[3].y
) &&
3698 (Pts
[3].x
== Pts
[0].x
)) ||
3699 ((Pts
[0].x
== Pts
[1].x
) &&
3700 (Pts
[1].y
== Pts
[2].y
) &&
3701 (Pts
[2].x
== Pts
[3].x
) &&
3702 (Pts
[3].y
== Pts
[0].y
))))
3704 REGION_UnlockRgn(region
);
3705 NtGdiSetRectRgn(hrgn
, min(Pts
[0].x
, Pts
[2].x
), min(Pts
[0].y
, Pts
[2].y
),
3706 max(Pts
[0].x
, Pts
[2].x
), max(Pts
[0].y
, Pts
[2].y
));
3710 for (poly
= total
= 0; poly
< nbpolygons
; poly
++)
3711 total
+= Count
[poly
];
3712 if (! (pETEs
= ExAllocatePoolWithTag(PagedPool
, sizeof(EdgeTableEntry
) * total
, TAG_REGION
)) )
3714 NtGdiDeleteObject(hrgn
);
3717 pts
= FirstPtBlock
.pts
;
3718 REGION_CreateETandAET(Count
, nbpolygons
, Pts
, &ET
, &AET
, pETEs
, &SLLBlock
);
3719 pSLL
= ET
.scanlines
.next
;
3720 curPtBlock
= &FirstPtBlock
;
3722 if (mode
!= WINDING
)
3727 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++)
3730 * Add a new edge to the active edge table when we
3731 * get to the next edge.
3733 if (pSLL
!= NULL
&& y
== pSLL
->scanline
)
3735 REGION_loadAET(&AET
, pSLL
->edgelist
);
3742 * for each active edge
3746 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
3750 * send out the buffer
3752 if (iPts
== NUMPTSTOBUFFER
)
3754 tmpPtBlock
= ExAllocatePoolWithTag(PagedPool
, sizeof(POINTBLOCK
), TAG_REGION
);
3757 DPRINT1("Can't alloc tPB\n");
3758 ExFreePoolWithTag(pETEs
, TAG_REGION
);
3761 curPtBlock
->next
= tmpPtBlock
;
3762 curPtBlock
= tmpPtBlock
;
3763 pts
= curPtBlock
->pts
;
3767 EVALUATEEDGEEVENODD(pAET
, pPrevAET
, y
);
3769 REGION_InsertionSort(&AET
);
3777 for (y
= ET
.ymin
; y
< ET
.ymax
; y
++)
3780 * Add a new edge to the active edge table when we
3781 * get to the next edge.
3783 if (pSLL
!= NULL
&& y
== pSLL
->scanline
)
3785 REGION_loadAET(&AET
, pSLL
->edgelist
);
3786 REGION_computeWAET(&AET
);
3794 * for each active edge
3799 * add to the buffer only those edges that
3800 * are in the Winding active edge table.
3804 pts
->x
= pAET
->bres
.minor_axis
, pts
->y
= y
;
3808 * send out the buffer
3810 if (iPts
== NUMPTSTOBUFFER
)
3812 tmpPtBlock
= ExAllocatePoolWithTag(PagedPool
,
3813 sizeof(POINTBLOCK
), TAG_REGION
);
3816 DPRINT1("Can't alloc tPB\n");
3817 ExFreePoolWithTag(pETEs
, TAG_REGION
);
3818 NtGdiDeleteObject(hrgn
);
3821 curPtBlock
->next
= tmpPtBlock
;
3822 curPtBlock
= tmpPtBlock
;
3823 pts
= curPtBlock
->pts
;
3827 pWETE
= pWETE
->nextWETE
;
3829 EVALUATEEDGEWINDING(pAET
, pPrevAET
, y
, fixWAET
);
3833 * recompute the winding active edge table if
3834 * we just resorted or have exited an edge.
3836 if (REGION_InsertionSort(&AET
) || fixWAET
)
3838 REGION_computeWAET(&AET
);
3843 REGION_FreeStorage(SLLBlock
.next
);
3844 REGION_PtsToRegion(numFullPtBlocks
, iPts
, &FirstPtBlock
, region
);
3846 for (curPtBlock
= FirstPtBlock
.next
; --numFullPtBlocks
>= 0;)
3848 tmpPtBlock
= curPtBlock
->next
;
3849 ExFreePoolWithTag(curPtBlock
, TAG_REGION
);
3850 curPtBlock
= tmpPtBlock
;
3852 ExFreePoolWithTag(pETEs
, TAG_REGION
);
3853 REGION_UnlockRgn(region
);