1 /*
2 * GDI region objects. Shamelessly ripped out from the X11 distribution
3 * Thanks for the nice licence.
4 *
5 * Copyright 1993, 1994, 1995 Alexandre Julliard
6 * Modifications and additions: Copyright 1998 Huw Davies
7 * 1999 Alex Korobka
8 *
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.
13 *
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.
18 *
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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
22 */
23
24 /************************************************************************
25
26 Copyright (c) 1987, 1988 X Consortium
27
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:
34
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
37
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.
44
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.
48
49
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
51
52 All Rights Reserved
53
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.
61
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.
69
70 ************************************************************************/
71 /*
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.
77 *
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".
85 *
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.
89 *
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...
95 */
96
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_private.h"
104 #include "wine/debug.h"
105
106 WINE_DEFAULT_DEBUG_CHANNEL(region);
107
108 typedef struct {
109 INT size;
110 INT numRects;
111 RECT *rects;
112 RECT extents;
113 } WINEREGION;
114
115 /* GDI logical region object */
116 typedef struct
117 {
118 GDIOBJHDR header;
119 WINEREGION *rgn;
120 } RGNOBJ;
121
122
123 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc );
124 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj );
125
126 static const struct gdi_obj_funcs region_funcs =
127 {
128 REGION_SelectObject, /* pSelectObject */
129 NULL, /* pGetObjectA */
130 NULL, /* pGetObjectW */
131 NULL, /* pUnrealizeObject */
132 REGION_DeleteObject /* pDeleteObject */
133 };
134
135 /* 1 if two RECTs overlap.
136 * 0 if two RECTs do not overlap.
137 */
138 #define EXTENTCHECK(r1, r2) \
139 ((r1)->right > (r2)->left && \
140 (r1)->left < (r2)->right && \
141 (r1)->bottom > (r2)->top && \
142 (r1)->top < (r2)->bottom)
143
144 /*
145 * Check to see if there is enough memory in the present region.
146 */
147
148 static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
149 if (reg->numRects >= (reg->size - 1)) {
150 *firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
151 if (*firstrect == 0)
152 return 0;
153 reg->size *= 2;
154 *rect = (*firstrect)+reg->numRects;
155 }
156 return 1;
157 }
158
159 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
160
161 #define EMPTY_REGION(pReg) { \
162 (pReg)->numRects = 0; \
163 (pReg)->extents.left = (pReg)->extents.top = 0; \
164 (pReg)->extents.right = (pReg)->extents.bottom = 0; \
165 }
166
167 #define REGION_NOT_EMPTY(pReg) pReg->numRects
168
169 #define INRECT(r, x, y) \
170 ( ( ((r).right > x)) && \
171 ( ((r).left <= x)) && \
172 ( ((r).bottom > y)) && \
173 ( ((r).top <= y)) )
174
175
176 /*
177 * number of points to buffer before sending them off
178 * to scanlines() : Must be an even number
179 */
180 #define NUMPTSTOBUFFER 200
181
182 /*
183 * used to allocate buffers for points and link
184 * the buffers together
185 */
186
187 typedef struct _POINTBLOCK {
188 POINT pts[NUMPTSTOBUFFER];
189 struct _POINTBLOCK *next;
190 } POINTBLOCK;
191
192
193
194 /*
195 * This file contains a few macros to help track
196 * the edge of a filled object. The object is assumed
197 * to be filled in scanline order, and thus the
198 * algorithm used is an extension of Bresenham's line
199 * drawing algorithm which assumes that y is always the
200 * major axis.
201 * Since these pieces of code are the same for any filled shape,
202 * it is more convenient to gather the library in one
203 * place, but since these pieces of code are also in
204 * the inner loops of output primitives, procedure call
205 * overhead is out of the question.
206 * See the author for a derivation if needed.
207 */
208
209
210 /*
211 * In scan converting polygons, we want to choose those pixels
212 * which are inside the polygon. Thus, we add .5 to the starting
213 * x coordinate for both left and right edges. Now we choose the
214 * first pixel which is inside the pgon for the left edge and the
215 * first pixel which is outside the pgon for the right edge.
216 * Draw the left pixel, but not the right.
217 *
218 * How to add .5 to the starting x coordinate:
219 * If the edge is moving to the right, then subtract dy from the
220 * error term from the general form of the algorithm.
221 * If the edge is moving to the left, then add dy to the error term.
222 *
223 * The reason for the difference between edges moving to the left
224 * and edges moving to the right is simple: If an edge is moving
225 * to the right, then we want the algorithm to flip immediately.
226 * If it is moving to the left, then we don't want it to flip until
227 * we traverse an entire pixel.
228 */
229 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
230 int dx; /* local storage */ \
231 \
232 /* \
233 * if the edge is horizontal, then it is ignored \
234 * and assumed not to be processed. Otherwise, do this stuff. \
235 */ \
236 if ((dy) != 0) { \
237 xStart = (x1); \
238 dx = (x2) - xStart; \
239 if (dx < 0) { \
240 m = dx / (dy); \
241 m1 = m - 1; \
242 incr1 = -2 * dx + 2 * (dy) * m1; \
243 incr2 = -2 * dx + 2 * (dy) * m; \
244 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
245 } else { \
246 m = dx / (dy); \
247 m1 = m + 1; \
248 incr1 = 2 * dx - 2 * (dy) * m1; \
249 incr2 = 2 * dx - 2 * (dy) * m; \
250 d = -2 * m * (dy) + 2 * dx; \
251 } \
252 } \
253 }
254
255 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
256 if (m1 > 0) { \
257 if (d > 0) { \
258 minval += m1; \
259 d += incr1; \
260 } \
261 else { \
262 minval += m; \
263 d += incr2; \
264 } \
265 } else {\
266 if (d >= 0) { \
267 minval += m1; \
268 d += incr1; \
269 } \
270 else { \
271 minval += m; \
272 d += incr2; \
273 } \
274 } \
275 }
276
277 /*
278 * This structure contains all of the information needed
279 * to run the bresenham algorithm.
280 * The variables may be hardcoded into the declarations
281 * instead of using this structure to make use of
282 * register declarations.
283 */
284 typedef struct {
285 INT minor_axis; /* minor axis */
286 INT d; /* decision variable */
287 INT m, m1; /* slope and slope+1 */
288 INT incr1, incr2; /* error increments */
289 } BRESINFO;
290
291
292 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
293 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
294 bres.m, bres.m1, bres.incr1, bres.incr2)
295
296 #define BRESINCRPGONSTRUCT(bres) \
297 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
298
299
300
301 /*
302 * These are the data structures needed to scan
303 * convert regions. Two different scan conversion
304 * methods are available -- the even-odd method, and
305 * the winding number method.
306 * The even-odd rule states that a point is inside
307 * the polygon if a ray drawn from that point in any
308 * direction will pass through an odd number of
309 * path segments.
310 * By the winding number rule, a point is decided
311 * to be inside the polygon if a ray drawn from that
312 * point in any direction passes through a different
313 * number of clockwise and counter-clockwise path
314 * segments.
315 *
316 * These data structures are adapted somewhat from
317 * the algorithm in (Foley/Van Dam) for scan converting
318 * polygons.
319 * The basic algorithm is to start at the top (smallest y)
320 * of the polygon, stepping down to the bottom of
321 * the polygon by incrementing the y coordinate. We
322 * keep a list of edges which the current scanline crosses,
323 * sorted by x. This list is called the Active Edge Table (AET)
324 * As we change the y-coordinate, we update each entry in
325 * in the active edge table to reflect the edges new xcoord.
326 * This list must be sorted at each scanline in case
327 * two edges intersect.
328 * We also keep a data structure known as the Edge Table (ET),
329 * which keeps track of all the edges which the current
330 * scanline has not yet reached. The ET is basically a
331 * list of ScanLineList structures containing a list of
332 * edges which are entered at a given scanline. There is one
333 * ScanLineList per scanline at which an edge is entered.
334 * When we enter a new edge, we move it from the ET to the AET.
335 *
336 * From the AET, we can implement the even-odd rule as in
337 * (Foley/Van Dam).
338 * The winding number rule is a little trickier. We also
339 * keep the EdgeTableEntries in the AET linked by the
340 * nextWETE (winding EdgeTableEntry) link. This allows
341 * the edges to be linked just as before for updating
342 * purposes, but only uses the edges linked by the nextWETE
343 * link as edges representing spans of the polygon to
344 * drawn (as with the even-odd rule).
345 */
346
347 /*
348 * for the winding number rule
349 */
350 #define CLOCKWISE 1
351 #define COUNTERCLOCKWISE -1
352
353 typedef struct _EdgeTableEntry {
354 INT ymax; /* ycoord at which we exit this edge. */
355 BRESINFO bres; /* Bresenham info to run the edge */
356 struct _EdgeTableEntry *next; /* next in the list */
357 struct _EdgeTableEntry *back; /* for insertion sort */
358 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
359 int ClockWise; /* flag for winding number rule */
360 } EdgeTableEntry;
361
362
363 typedef struct _ScanLineList{
364 INT scanline; /* the scanline represented */
365 EdgeTableEntry *edgelist; /* header node */
366 struct _ScanLineList *next; /* next in the list */
367 } ScanLineList;
368
369
370 typedef struct {
371 INT ymax; /* ymax for the polygon */
372 INT ymin; /* ymin for the polygon */
373 ScanLineList scanlines; /* header node */
374 } EdgeTable;
375
376
377 /*
378 * Here is a struct to help with storage allocation
379 * so we can allocate a big chunk at a time, and then take
380 * pieces from this heap when we need to.
381 */
382 #define SLLSPERBLOCK 25
383
384 typedef struct _ScanLineListBlock {
385 ScanLineList SLLs[SLLSPERBLOCK];
386 struct _ScanLineListBlock *next;
387 } ScanLineListBlock;
388
389
390 /*
391 *
392 * a few macros for the inner loops of the fill code where
393 * performance considerations don't allow a procedure call.
394 *
395 * Evaluate the given edge at the given scanline.
396 * If the edge has expired, then we leave it and fix up
397 * the active edge table; otherwise, we increment the
398 * x value to be ready for the next scanline.
399 * The winding number rule is in effect, so we must notify
400 * the caller when the edge has been removed so he
401 * can reorder the Winding Active Edge Table.
402 */
403 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
404 if (pAET->ymax == y) { /* leaving this edge */ \
405 pPrevAET->next = pAET->next; \
406 pAET = pPrevAET->next; \
407 fixWAET = 1; \
408 if (pAET) \
409 pAET->back = pPrevAET; \
410 } \
411 else { \
412 BRESINCRPGONSTRUCT(pAET->bres); \
413 pPrevAET = pAET; \
414 pAET = pAET->next; \
415 } \
416 }
417
418
419 /*
420 * Evaluate the given edge at the given scanline.
421 * If the edge has expired, then we leave it and fix up
422 * the active edge table; otherwise, we increment the
423 * x value to be ready for the next scanline.
424 * The even-odd rule is in effect.
425 */
426 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
427 if (pAET->ymax == y) { /* leaving this edge */ \
428 pPrevAET->next = pAET->next; \
429 pAET = pPrevAET->next; \
430 if (pAET) \
431 pAET->back = pPrevAET; \
432 } \
433 else { \
434 BRESINCRPGONSTRUCT(pAET->bres); \
435 pPrevAET = pAET; \
436 pAET = pAET->next; \
437 } \
438 }
439
440 /* Note the parameter order is different from the X11 equivalents */
441
442 static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
443 static void REGION_OffsetRegion(WINEREGION *d, WINEREGION *s, INT x, INT y);
444 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
445 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
446 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
447 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
449
450 #define RGN_DEFAULT_RECTS 2
451
452
453 /***********************************************************************
454 * get_region_type
455 */
456 static inline INT get_region_type( const RGNOBJ *obj )
457 {
458 switch(obj->rgn->numRects)
459 {
460 case 0: return NULLREGION;
461 case 1: return SIMPLEREGION;
462 default: return COMPLEXREGION;
463 }
464 }
465
466
467 /***********************************************************************
468 * REGION_DumpRegion
469 * Outputs the contents of a WINEREGION
470 */
471 static void REGION_DumpRegion(WINEREGION *pReg)
472 {
473 RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
474
475 TRACE("Region %p: %d,%d - %d,%d %d rects\n", pReg,
476 pReg->extents.left, pReg->extents.top,
477 pReg->extents.right, pReg->extents.bottom, pReg->numRects);
478 for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
479 TRACE("\t%d,%d - %d,%d\n", pRect->left, pRect->top,
480 pRect->right, pRect->bottom);
481 return;
482 }
483
484
485 /***********************************************************************
486 * REGION_AllocWineRegion
487 * Create a new empty WINEREGION.
488 */
489 static WINEREGION *REGION_AllocWineRegion( INT n )
490 {
491 WINEREGION *pReg;
492
493 if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
494 {
495 if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
496 {
497 pReg->size = n;
498 EMPTY_REGION(pReg);
499 return pReg;
500 }
501 HeapFree(GetProcessHeap(), 0, pReg);
502 }
503 return NULL;
504 }
505
506
507 /***********************************************************************
508 * REGION_CreateRegion
509 * Create a new empty region.
510 */
511 static HRGN REGION_CreateRegion( INT n )
512 {
513 HRGN hrgn;
514 RGNOBJ *obj;
515
516 if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, (HGDIOBJ *)&hrgn,
517 ®ion_funcs ))) return 0;
518 if(!(obj->rgn = REGION_AllocWineRegion(n))) {
519 GDI_FreeObject( hrgn, obj );
520 return 0;
521 }
522 GDI_ReleaseObj( hrgn );
523 return hrgn;
524 }
525
526 /***********************************************************************
527 * REGION_DestroyWineRegion
528 */
529 static void REGION_DestroyWineRegion( WINEREGION* pReg )
530 {
531 HeapFree( GetProcessHeap(), 0, pReg->rects );
532 HeapFree( GetProcessHeap(), 0, pReg );
533 }
534
535 /***********************************************************************
536 * REGION_DeleteObject
537 */
538 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj )
539 {
540 RGNOBJ *rgn = obj;
541
542 TRACE(" %p\n", handle );
543
544 REGION_DestroyWineRegion( rgn->rgn );
545 return GDI_FreeObject( handle, obj );
546 }
547
548 /***********************************************************************
549 * REGION_SelectObject
550 */
551 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, HDC hdc )
552 {
553 return ULongToHandle(SelectClipRgn( hdc, handle ));
554 }
555
556
557 /***********************************************************************
558 * REGION_OffsetRegion
559 * Offset a WINEREGION by x,y
560 */
561 static void REGION_OffsetRegion( WINEREGION *rgn, WINEREGION *srcrgn,
562 INT x, INT y )
563 {
564 if( rgn != srcrgn)
565 REGION_CopyRegion( rgn, srcrgn);
566 if(x || y) {
567 int nbox = rgn->numRects;
568 RECT *pbox = rgn->rects;
569
570 if(nbox) {
571 while(nbox--) {
572 pbox->left += x;
573 pbox->right += x;
574 pbox->top += y;
575 pbox->bottom += y;
576 pbox++;
577 }
578 rgn->extents.left += x;
579 rgn->extents.right += x;
580 rgn->extents.top += y;
581 rgn->extents.bottom += y;
582 }
583 }
584 }
585
586 /***********************************************************************
587 * OffsetRgn (GDI32.@)
588 *
589 * Moves a region by the specified X- and Y-axis offsets.
590 *
591 * PARAMS
592 * hrgn [I] Region to offset.
593 * x [I] Offset right if positive or left if negative.
594 * y [I] Offset down if positive or up if negative.
595 *
596 * RETURNS
597 * Success:
598 * NULLREGION - The new region is empty.
599 * SIMPLEREGION - The new region can be represented by one rectangle.
600 * COMPLEXREGION - The new region can only be represented by more than
601 * one rectangle.
602 * Failure: ERROR
603 */
604 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
605 {
606 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
607 INT ret;
608
609 TRACE("%p %d,%d\n", hrgn, x, y);
610
611 if (!obj)
612 return ERROR;
613
614 REGION_OffsetRegion( obj->rgn, obj->rgn, x, y);
615
616 ret = get_region_type( obj );
617 GDI_ReleaseObj( hrgn );
618 return ret;
619 }
620
621
622 /***********************************************************************
623 * GetRgnBox (GDI32.@)
624 *
625 * Retrieves the bounding rectangle of the region. The bounding rectangle
626 * is the smallest rectangle that contains the entire region.
627 *
628 * PARAMS
629 * hrgn [I] Region to retrieve bounding rectangle from.
630 * rect [O] Rectangle that will receive the coordinates of the bounding
631 * rectangle.
632 *
633 * RETURNS
634 * NULLREGION - The new region is empty.
635 * SIMPLEREGION - The new region can be represented by one rectangle.
636 * COMPLEXREGION - The new region can only be represented by more than
637 * one rectangle.
638 */
639 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
640 {
641 RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
642 if (obj)
643 {
644 INT ret;
645 rect->left = obj->rgn->extents.left;
646 rect->top = obj->rgn->extents.top;
647 rect->right = obj->rgn->extents.right;
648 rect->bottom = obj->rgn->extents.bottom;
649 TRACE("%p (%d,%d-%d,%d)\n", hrgn,
650 rect->left, rect->top, rect->right, rect->bottom);
651 ret = get_region_type( obj );
652 GDI_ReleaseObj(hrgn);
653 return ret;
654 }
655 return ERROR;
656 }
657
658
659 /***********************************************************************
660 * CreateRectRgn (GDI32.@)
661 *
662 * Creates a simple rectangular region.
663 *
664 * PARAMS
665 * left [I] Left coordinate of rectangle.
666 * top [I] Top coordinate of rectangle.
667 * right [I] Right coordinate of rectangle.
668 * bottom [I] Bottom coordinate of rectangle.
669 *
670 * RETURNS
671 * Success: Handle to region.
672 * Failure: NULL.
673 */
674 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
675 {
676 HRGN hrgn;
677
678 /* Allocate 2 rects by default to reduce the number of reallocs */
679
680 if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
681 return 0;
682 TRACE("%d,%d-%d,%d\n", left, top, right, bottom);
683 SetRectRgn(hrgn, left, top, right, bottom);
684 return hrgn;
685 }
686
687
688 /***********************************************************************
689 * CreateRectRgnIndirect (GDI32.@)
690 *
691 * Creates a simple rectangular region.
692 *
693 * PARAMS
694 * rect [I] Coordinates of rectangular region.
695 *
696 * RETURNS
697 * Success: Handle to region.
698 * Failure: NULL.
699 */
700 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
701 {
702 return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
703 }
704
705
706 /***********************************************************************
707 * SetRectRgn (GDI32.@)
708 *
709 * Sets a region to a simple rectangular region.
710 *
711 * PARAMS
712 * hrgn [I] Region to convert.
713 * left [I] Left coordinate of rectangle.
714 * top [I] Top coordinate of rectangle.
715 * right [I] Right coordinate of rectangle.
716 * bottom [I] Bottom coordinate of rectangle.
717 *
718 * RETURNS
719 * Success: Non-zero.
720 * Failure: Zero.
721 *
722 * NOTES
723 * Allows either or both left and top to be greater than right or bottom.
724 */
725 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
726 INT right, INT bottom )
727 {
728 RGNOBJ * obj;
729
730 TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
731
732 if (!(obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
733
734 if (left > right) { INT tmp = left; left = right; right = tmp; }
735 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
736
737 if((left != right) && (top != bottom))
738 {
739 obj->rgn->rects->left = obj->rgn->extents.left = left;
740 obj->rgn->rects->top = obj->rgn->extents.top = top;
741 obj->rgn->rects->right = obj->rgn->extents.right = right;
742 obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
743 obj->rgn->numRects = 1;
744 }
745 else
746 EMPTY_REGION(obj->rgn);
747
748 GDI_ReleaseObj( hrgn );
749 return TRUE;
750 }
751
752
753 /***********************************************************************
754 * CreateRoundRectRgn (GDI32.@)
755 *
756 * Creates a rectangular region with rounded corners.
757 *
758 * PARAMS
759 * left [I] Left coordinate of rectangle.
760 * top [I] Top coordinate of rectangle.
761 * right [I] Right coordinate of rectangle.
762 * bottom [I] Bottom coordinate of rectangle.
763 * ellipse_width [I] Width of the ellipse at each corner.
764 * ellipse_height [I] Height of the ellipse at each corner.
765 *
766 * RETURNS
767 * Success: Handle to region.
768 * Failure: NULL.
769 *
770 * NOTES
771 * If ellipse_width or ellipse_height is less than 2 logical units then
772 * it is treated as though CreateRectRgn() was called instead.
773 */
774 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
775 INT right, INT bottom,
776 INT ellipse_width, INT ellipse_height )
777 {
778 RGNOBJ * obj;
779 HRGN hrgn;
780 int asq, bsq, d, xd, yd;
781 RECT rect;
782
783 /* Make the dimensions sensible */
784
785 if (left > right) { INT tmp = left; left = right; right = tmp; }
786 if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
787
788 ellipse_width = abs(ellipse_width);
789 ellipse_height = abs(ellipse_height);
790
791 /* Check parameters */
792
793 if (ellipse_width > right-left) ellipse_width = right-left;
794 if (ellipse_height > bottom-top) ellipse_height = bottom-top;
795
796 /* Check if we can do a normal rectangle instead */
797
798 if ((ellipse_width < 2) || (ellipse_height < 2))
799 return CreateRectRgn( left, top, right, bottom );
800
801 /* Create region */
802
803 d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
804 if (!(hrgn = REGION_CreateRegion(d))) return 0;
805 if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
806 TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
807 left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
808
809 /* Ellipse algorithm, based on an article by K. Porter */
810 /* in DDJ Graphics Programming Column, 8/89 */
811
812 asq = ellipse_width * ellipse_width / 4; /* a^2 */
813 bsq = ellipse_height * ellipse_height / 4; /* b^2 */
814 d = bsq - asq * ellipse_height / 2 + asq / 4; /* b^2 - a^2b + a^2/4 */
815 xd = 0;
816 yd = asq * ellipse_height; /* 2a^2b */
817
818 rect.left = left + ellipse_width / 2;
819 rect.right = right - ellipse_width / 2;
820
821 /* Loop to draw first half of quadrant */
822
823 while (xd < yd)
824 {
825 if (d > 0) /* if nearest pixel is toward the center */
826 {
827 /* move toward center */
828 rect.top = top++;
829 rect.bottom = rect.top + 1;
830 REGION_UnionRectWithRegion( &rect, obj->rgn );
831 rect.top = --bottom;
832 rect.bottom = rect.top + 1;
833 REGION_UnionRectWithRegion( &rect, obj->rgn );
834 yd -= 2*asq;
835 d -= yd;
836 }
837 rect.left--; /* next horiz point */
838 rect.right++;
839 xd += 2*bsq;
840 d += bsq + xd;
841 }
842
843 /* Loop to draw second half of quadrant */
844
845 d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
846 while (yd >= 0)
847 {
848 /* next vertical point */
849 rect.top = top++;
850 rect.bottom = rect.top + 1;
851 REGION_UnionRectWithRegion( &rect, obj->rgn );
852 rect.top = --bottom;
853 rect.bottom = rect.top + 1;
854 REGION_UnionRectWithRegion( &rect, obj->rgn );
855 if (d < 0) /* if nearest pixel is outside ellipse */
856 {
857 rect.left--; /* move away from center */
858 rect.right++;
859 xd += 2*bsq;
860 d += xd;
861 }
862 yd -= 2*asq;
863 d += asq - yd;
864 }
865
866 /* Add the inside rectangle */
867
868 if (top <= bottom)
869 {
870 rect.top = top;
871 rect.bottom = bottom;
872 REGION_UnionRectWithRegion( &rect, obj->rgn );
873 }
874 GDI_ReleaseObj( hrgn );
875 return hrgn;
876 }
877
878
879 /***********************************************************************
880 * CreateEllipticRgn (GDI32.@)
881 *
882 * Creates an elliptical region.
883 *
884 * PARAMS
885 * left [I] Left coordinate of bounding rectangle.
886 * top [I] Top coordinate of bounding rectangle.
887 * right [I] Right coordinate of bounding rectangle.
888 * bottom [I] Bottom coordinate of bounding rectangle.
889 *
890 * RETURNS
891 * Success: Handle to region.
892 * Failure: NULL.
893 *
894 * NOTES
895 * This is a special case of CreateRoundRectRgn() where the width of the
896 * ellipse at each corner is equal to the width the rectangle and
897 * the same for the height.
898 */
899 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
900 INT right, INT bottom )
901 {
902 return CreateRoundRectRgn( left, top, right, bottom,
903 right-left, bottom-top );
904 }
905
906
907 /***********************************************************************
908 * CreateEllipticRgnIndirect (GDI32.@)
909 *
910 * Creates an elliptical region.
911 *
912 * PARAMS
913 * rect [I] Pointer to bounding rectangle of the ellipse.
914 *
915 * RETURNS
916 * Success: Handle to region.
917 * Failure: NULL.
918 *
919 * NOTES
920 * This is a special case of CreateRoundRectRgn() where the width of the
921 * ellipse at each corner is equal to the width the rectangle and
922 * the same for the height.
923 */
924 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
925 {
926 return CreateRoundRectRgn( rect->left, rect->top, rect->right,
927 rect->bottom, rect->right - rect->left,
928 rect->bottom - rect->top );
929 }
930
931 /***********************************************************************
932 * GetRegionData (GDI32.@)
933 *
934 * Retrieves the data that specifies the region.
935 *
936 * PARAMS
937 * hrgn [I] Region to retrieve the region data from.
938 * count [I] The size of the buffer pointed to by rgndata in bytes.
939 * rgndata [I] The buffer to receive data about the region.
940 *
941 * RETURNS
942 * Success: If rgndata is NULL then the required number of bytes. Otherwise,
943 * the number of bytes copied to the output buffer.
944 * Failure: 0.
945 *
946 * NOTES
947 * The format of the Buffer member of RGNDATA is determined by the iType
948 * member of the region data header.
949 * Currently this is always RDH_RECTANGLES, which specifies that the format
950 * is the array of RECT's that specify the region. The length of the array
951 * is specified by the nCount member of the region data header.
952 */
953 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
954 {
955 DWORD size;
956 RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
957
958 TRACE(" %p count = %d, rgndata = %p\n", hrgn, count, rgndata);
959
960 if(!obj) return 0;
961
962 size = obj->rgn->numRects * sizeof(RECT);
963 if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
964 {
965 GDI_ReleaseObj( hrgn );
966 if (rgndata) /* buffer is too small, signal it by return 0 */
967 return 0;
968 else /* user requested buffer size with rgndata NULL */
969 return size + sizeof(RGNDATAHEADER);
970 }
971
972 rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
973 rgndata->rdh.iType = RDH_RECTANGLES;
974 rgndata->rdh.nCount = obj->rgn->numRects;
975 rgndata->rdh.nRgnSize = size;
976 rgndata->rdh.rcBound.left = obj->rgn->extents.left;
977 rgndata->rdh.rcBound.top = obj->rgn->extents.top;
978 rgndata->rdh.rcBound.right = obj->rgn->extents.right;
979 rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
980
981 memcpy( rgndata->Buffer, obj->rgn->rects, size );
982
983 GDI_ReleaseObj( hrgn );
984 return size + sizeof(RGNDATAHEADER);
985 }
986
987
988 static void translate( POINT *pt, UINT count, const XFORM *xform )
989 {
990 while (count--)
991 {
992 FLOAT x = pt->x;
993 FLOAT y = pt->y;
994 pt->x = floor( x * xform->eM11 + y * xform->eM21 + xform->eDx + 0.5 );
995 pt->y = floor( x * xform->eM12 + y * xform->eM22 + xform->eDy + 0.5 );
996 pt++;
997 }
998 }
999
1000
1001 /***********************************************************************
1002 * ExtCreateRegion (GDI32.@)
1003 *
1004 * Creates a region as specified by the transformation data and region data.
1005 *
1006 * PARAMS
1007 * lpXform [I] World-space to logical-space transformation data.
1008 * dwCount [I] Size of the data pointed to by rgndata, in bytes.
1009 * rgndata [I] Data that specifies the region.
1010 *
1011 * RETURNS
1012 * Success: Handle to region.
1013 * Failure: NULL.
1014 *
1015 * NOTES
1016 * See GetRegionData().
1017 */
1018 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
1019 {
1020 HRGN hrgn;
1021
1022 TRACE(" %p %d %p\n", lpXform, dwCount, rgndata );
1023
1024 if (!rgndata)
1025 {
1026 SetLastError( ERROR_INVALID_PARAMETER );
1027 return 0;
1028 }
1029
1030 if (rgndata->rdh.dwSize < sizeof(RGNDATAHEADER))
1031 return 0;
1032
1033 /* XP doesn't care about the type */
1034 if( rgndata->rdh.iType != RDH_RECTANGLES )
1035 WARN("(Unsupported region data type: %u)\n", rgndata->rdh.iType);
1036
1037 if (lpXform)
1038 {
1039 RECT *pCurRect, *pEndRect;
1040
1041 hrgn = CreateRectRgn( 0, 0, 0, 0 );
1042
1043 pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
1044 for (pCurRect = (RECT *)rgndata->Buffer; pCurRect