src/osx/carbon/region.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // File:      src/osx/carbon/region.cpp
   3 // Purpose:   Region class
   4 // Author:    Stefan Csomor
   5 // Created:   Fri Oct 24 10:46:34 MET 1997
   6 // RCS-ID:    $Id$
   7 // Copyright: (c) 1997 Stefan Csomor
   8 // Licence:   wxWindows licence
   9 /////////////////////////////////////////////////////////////////////////////
  10
  11 #include "wx/wxprec.h"
  12
  13 #if wxOSX_USE_COCOA_OR_CARBON
  14
  15 #include "wx/region.h"
  16
  17 #ifndef WX_PRECOMP
  18     #include "wx/gdicmn.h"
  19     #include "wx/dcmemory.h"
  20 #endif
  21
  22 #include "wx/osx/private.h"
  23
  24 IMPLEMENT_DYNAMIC_CLASS(wxRegion, wxGDIObject)
  25 IMPLEMENT_DYNAMIC_CLASS(wxRegionIterator, wxObject)
  26
  27 #define OSX_USE_SCANLINES 1
  28
  29 //-----------------------------------------------------------------------------
  30 // wxRegionRefData implementation
  31 //-----------------------------------------------------------------------------
  32
  33 class WXDLLEXPORT wxRegionRefData : public wxGDIRefData
  34 {
  35 public:
  36     wxRegionRefData()
  37     {
  38         m_macRgn.reset( HIShapeCreateMutable() );
  39     }
  40
  41     wxRegionRefData(wxCFRef<HIShapeRef> &region)
  42     {
  43         m_macRgn.reset( HIShapeCreateMutableCopy(region) );
  44     }
  45
  46     wxRegionRefData(long x, long y, long w, long h)
  47     {
  48         CGRect r = CGRectMake(x,y,w,h);
  49         wxCFRef<HIShapeRef> rect(HIShapeCreateWithRect(&r));
  50         m_macRgn.reset( HIShapeCreateMutableCopy(rect) );
  51     }
  52
  53     wxRegionRefData(const wxRegionRefData& data)
  54         : wxGDIRefData()
  55     {
  56         m_macRgn.reset( HIShapeCreateMutableCopy(data.m_macRgn) );
  57     }
  58
  59     virtual ~wxRegionRefData()
  60     {
  61     }
  62
  63     wxCFRef<HIMutableShapeRef> m_macRgn;
  64 };
  65
  66 #define M_REGION (((wxRegionRefData*)m_refData)->m_macRgn)
  67 #define OTHER_M_REGION(a) (((wxRegionRefData*)(a.m_refData))->m_macRgn)
  68
  69 //-----------------------------------------------------------------------------
  70 // wxRegion
  71 //-----------------------------------------------------------------------------
  72
  73 wxRegion::wxRegion(WXHRGN hRegion )
  74 {
  75     wxCFRef< HIShapeRef > shape( (HIShapeRef) hRegion );
  76     m_refData = new wxRegionRefData(shape);
  77 }
  78
  79 wxRegion::wxRegion(long x, long y, long w, long h)
  80 {
  81     m_refData = new wxRegionRefData(x , y , w , h );
  82 }
  83
  84 wxRegion::wxRegion(const wxPoint& topLeft, const wxPoint& bottomRight)
  85 {
  86     m_refData = new wxRegionRefData(topLeft.x , topLeft.y ,
  87                                     bottomRight.x - topLeft.x,
  88                                     bottomRight.y - topLeft.y);
  89 }
  90
  91 wxRegion::wxRegion(const wxRect& rect)
  92 {
  93     m_refData = new wxRegionRefData(rect.x , rect.y , rect.width , rect.height);
  94 }
  95
  96 #if OSX_USE_SCANLINES
  97
  98 /*
  99
 100  Copyright 1987, 1998  The Open Group
 101
 102  Permission to use, copy, modify, distribute, and sell this software and its
 103  documentation for any purpose is hereby granted without fee, provided that
 104  the above copyright notice appear in all copies and that both that
 105  copyright notice and this permission notice appear in supporting
 106  documentation.
 107
 108  The above copyright notice and this permission notice shall be included
 109  in all copies or substantial portions of the Software.
 110
 111  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 112  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 113  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 114  IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
 115  OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 116  ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 117  OTHER DEALINGS IN THE SOFTWARE.
 118
 119  Except as contained in this notice, the name of The Open Group shall
 120  not be used in advertising or otherwise to promote the sale, use or
 121  other dealings in this Software without prior written authorization
 122  from The Open Group.
 123
 124  */
 125
 126 /* miscanfill.h */
 127
 128 /*
 129  *     scanfill.h
 130  *
 131  *     Written by Brian Kelleher; Jan 1985
 132  *
 133  *     This file contains a few macros to help track
 134  *     the edge of a filled object.  The object is assumed
 135  *     to be filled in scanline order, and thus the
 136  *     algorithm used is an extension of Bresenham's line
 137  *     drawing algorithm which assumes that y is always the
 138  *     major axis.
 139  *     Since these pieces of code are the same for any filled shape,
 140  *     it is more convenient to gather the library in one
 141  *     place, but since these pieces of code are also in
 142  *     the inner loops of output primitives, procedure call
 143  *     overhead is out of the question.
 144  *     See the author for a derivation if needed.
 145  */
 146
 147
 148 /*
 149  *  In scan converting polygons, we want to choose those pixels
 150  *  which are inside the polygon.  Thus, we add .5 to the starting
 151  *  x coordinate for both left and right edges.  Now we choose the
 152  *  first pixel which is inside the pgon for the left edge and the
 153  *  first pixel which is outside the pgon for the right edge.
 154  *  Draw the left pixel, but not the right.
 155  *
 156  *  How to add .5 to the starting x coordinate:
 157  *      If the edge is moving to the right, then subtract dy from the
 158  *  error term from the general form of the algorithm.
 159  *      If the edge is moving to the left, then add dy to the error term.
 160  *
 161  *  The reason for the difference between edges moving to the left
 162  *  and edges moving to the right is simple:  If an edge is moving
 163  *  to the right, then we want the algorithm to flip immediately.
 164  *  If it is moving to the left, then we don't want it to flip until
 165  *  we traverse an entire pixel.
 166  */
 167 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
 168 int dx;      /* local storage */ \
 169 \
 170 /* \
 171 *  if the edge is horizontal, then it is ignored \
 172 *  and assumed not to be processed.  Otherwise, do this stuff. \
 173 */ \
 174 if ((dy) != 0) { \
 175 xStart = (x1); \
 176 dx = (x2) - xStart; \
 177 if (dx < 0) { \
 178 m = dx / (dy); \
 179 m1 = m - 1; \
 180 incr1 = -2 * dx + 2 * (dy) * m1; \
 181 incr2 = -2 * dx + 2 * (dy) * m; \
 182 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
 183 } else { \
 184 m = dx / (dy); \
 185 m1 = m + 1; \
 186 incr1 = 2 * dx - 2 * (dy) * m1; \
 187 incr2 = 2 * dx - 2 * (dy) * m; \
 188 d = -2 * m * (dy) + 2 * dx; \
 189 } \
 190 } \
 191 }
 192
 193 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
 194 if (m1 > 0) { \
 195 if (d > 0) { \
 196 minval += m1; \
 197 d += incr1; \
 198 } \
 199 else { \
 200 minval += m; \
 201 d += incr2; \
 202 } \
 203 } else {\
 204 if (d >= 0) { \
 205 minval += m1; \
 206 d += incr1; \
 207 } \
 208 else { \
 209 minval += m; \
 210 d += incr2; \
 211 } \
 212 } \
 213 }
 214
 215
 216 /*
 217  *     This structure contains all of the information needed
 218  *     to run the bresenham algorithm.
 219  *     The variables may be hardcoded into the declarations
 220  *     instead of using this structure to make use of
 221  *     register declarations.
 222  */
 223 typedef struct {
 224     int minor;         /* minor axis        */
 225     int d;           /* decision variable */
 226     int m, m1;       /* slope and slope+1 */
 227     int incr1, incr2; /* error increments */
 228 } BRESINFO;
 229
 230
 231 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
 232 BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \
 233 bres.m, bres.m1, bres.incr1, bres.incr2)
 234
 235 #define BRESINCRPGONSTRUCT(bres) \
 236 BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2)
 237
 238
 239 /* mipoly.h */
 240
 241 /*
 242  *     fill.h
 243  *
 244  *     Created by Brian Kelleher; Oct 1985
 245  *
 246  *     Include file for filled polygon routines.
 247  *
 248  *     These are the data structures needed to scan
 249  *     convert regions.  Two different scan conversion
 250  *     methods are available -- the even-odd method, and
 251  *     the winding number method.
 252  *     The even-odd rule states that a point is inside
 253  *     the polygon if a ray drawn from that point in any
 254  *     direction will pass through an odd number of
 255  *     path segments.
 256  *     By the winding number rule, a point is decided
 257  *     to be inside the polygon if a ray drawn from that
 258  *     point in any direction passes through a different
 259  *     number of clockwise and counter-clockwise path
 260  *     segments.
 261  *
 262  *     These data structures are adapted somewhat from
 263  *     the algorithm in (Foley/Van Dam) for scan converting
 264  *     polygons.
 265  *     The basic algorithm is to start at the top (smallest y)
 266  *     of the polygon, stepping down to the bottom of
 267  *     the polygon by incrementing the y coordinate.  We
 268  *     keep a list of edges which the current scanline crosses,
 269  *     sorted by x.  This list is called the Active Edge Table (AET)
 270  *     As we change the y-coordinate, we update each entry in
 271  *     in the active edge table to reflect the edges new xcoord.
 272  *     This list must be sorted at each scanline in case
 273  *     two edges intersect.
 274  *     We also keep a data structure known as the Edge Table (ET),
 275  *     which keeps track of all the edges which the current
 276  *     scanline has not yet reached.  The ET is basically a
 277  *     list of ScanLineList structures containing a list of
 278  *     edges which are entered at a given scanline.  There is one
 279  *     ScanLineList per scanline at which an edge is entered.
 280  *     When we enter a new edge, we move it from the ET to the AET.
 281  *
 282  *     From the AET, we can implement the even-odd rule as in
 283  *     (Foley/Van Dam).
 284  *     The winding number rule is a little trickier.  We also
 285  *     keep the EdgeTableEntries in the AET linked by the
 286  *     nextWETE (winding EdgeTableEntry) link.  This allows
 287  *     the edges to be linked just as before for updating
 288  *     purposes, but only uses the edges linked by the nextWETE
 289  *     link as edges representing spans of the polygon to
 290  *     drawn (as with the even-odd rule).
 291  */
 292
 293 /*
 294  * for the winding number rule
 295  */
 296 #define CLOCKWISE          1
 297 #define COUNTERCLOCKWISE  -1
 298
 299 typedef struct _EdgeTableEntry {
 300     int ymax;             /* ycoord at which we exit this edge. */
 301     BRESINFO bres;        /* Bresenham info to run the edge     */
 302     struct _EdgeTableEntry *next;       /* next in the list     */
 303     struct _EdgeTableEntry *back;       /* for insertion sort   */
 304     struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
 305     int ClockWise;        /* flag for winding number rule       */
 306 } EdgeTableEntry;
 307
 308
 309 typedef struct _ScanLineList{
 310     int scanline;              /* the scanline represented */
 311     EdgeTableEntry *edgelist;  /* header node              */
 312     struct _ScanLineList *next;  /* next in the list       */
 313 } ScanLineList;
 314
 315
 316 typedef struct {
 317     int ymax;                 /* ymax for the polygon     */
 318     int ymin;                 /* ymin for the polygon     */
 319     ScanLineList scanlines;   /* header node              */
 320 } EdgeTable;
 321
 322
 323 /*
 324  * Here is a struct to help with storage allocation
 325  * so we can allocate a big chunk at a time, and then take
 326  * pieces from this heap when we need to.
 327  */
 328 #define SLLSPERBLOCK 25
 329
 330 typedef struct _ScanLineListBlock {
 331     ScanLineList SLLs[SLLSPERBLOCK];
 332     struct _ScanLineListBlock *next;
 333 } ScanLineListBlock;
 334
 335 /*
 336  * number of points to buffer before sending them off
 337  * to scanlines() :  Must be an even number
 338  */
 339 #define NUMPTSTOBUFFER 200
 340
 341
 342 /*
 343  *
 344  *     a few macros for the inner loops of the fill code where
 345  *     performance considerations don't allow a procedure call.
 346  *
 347  *     Evaluate the given edge at the given scanline.
 348  *     If the edge has expired, then we leave it and fix up
 349  *     the active edge table; otherwise, we increment the
 350  *     x value to be ready for the next scanline.
 351  *     The winding number rule is in effect, so we must notify
 352  *     the caller when the edge has been removed so he
 353  *     can reorder the Winding Active Edge Table.
 354  */
 355 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
 356 if (pAET->ymax == y) {          /* leaving this edge */ \
 357 pPrevAET->next = pAET->next; \
 358 pAET = pPrevAET->next; \
 359 fixWAET = 1; \
 360 if (pAET) \
 361 pAET->back = pPrevAET; \
 362 } \
 363 else { \
 364 BRESINCRPGONSTRUCT(pAET->bres); \
 365 pPrevAET = pAET; \
 366 pAET = pAET->next; \
 367 } \
 368 }
 369
 370
 371 /*
 372  *     Evaluate the given edge at the given scanline.
 373  *     If the edge has expired, then we leave it and fix up
 374  *     the active edge table; otherwise, we increment the
 375  *     x value to be ready for the next scanline.
 376  *     The even-odd rule is in effect.
 377  */
 378 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
 379 if (pAET->ymax == y) {          /* leaving this edge */ \
 380 pPrevAET->next = pAET->next; \
 381 pAET = pPrevAET->next; \
 382 if (pAET) \
 383 pAET->back = pPrevAET; \
 384 } \
 385 else { \
 386 BRESINCRPGONSTRUCT(pAET->bres); \
 387 pPrevAET = pAET; \
 388 pAET = pAET->next; \
 389 } \
 390 }
 391
 392 /* mipolyutil.c */
 393
 394 static bool miCreateETandAET(
 395                              int /*count*/,
 396                              const wxPoint * /*pts*/,
 397                              EdgeTable * /*ET*/,
 398                              EdgeTableEntry * /*AET*/,
 399                              EdgeTableEntry * /*pETEs*/,
 400                              ScanLineListBlock * /*pSLLBlock*/
 401                              );
 402
 403 static void miloadAET(
 404                       EdgeTableEntry * /*AET*/,
 405                       EdgeTableEntry * /*ETEs*/
 406                       );
 407
 408 static void micomputeWAET(
 409                           EdgeTableEntry * /*AET*/
 410                           );
 411
 412 static int miInsertionSort(
 413                            EdgeTableEntry * /*AET*/
 414                            );
 415
 416 static void miFreeStorage(
 417                           ScanLineListBlock * /*pSLLBlock*/
 418                           );
 419
 420 /*
 421  *     fillUtils.c
 422  *
 423  *     Written by Brian Kelleher;  Oct. 1985
 424  *
 425  *     This module contains all of the utility functions
 426  *     needed to scan convert a polygon.
 427  *
 428  */
 429
 430 /*
 431  *     InsertEdgeInET
 432  *
 433  *     Insert the given edge into the edge table.
 434  *     First we must find the correct bucket in the
 435  *     Edge table, then find the right slot in the
 436  *     bucket.  Finally, we can insert it.
 437  *
 438  */
 439 static bool
 440 miInsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,  int scanline,
 441                  ScanLineListBlock **SLLBlock, int *iSLLBlock)
 442 {
 443     EdgeTableEntry *start, *prev;
 444     ScanLineList *pSLL, *pPrevSLL;
 445     ScanLineListBlock *tmpSLLBlock;
 446
 447     /*
 448      * find the right bucket to put the edge into
 449      */
 450     pPrevSLL = &ET->scanlines;
 451     pSLL = pPrevSLL->next;
 452     while (pSLL && (pSLL->scanline < scanline))
 453     {
 454         pPrevSLL = pSLL;
 455         pSLL = pSLL->next;
 456     }
 457
 458     /*
 459      * reassign pSLL (pointer to ScanLineList) if necessary
 460      */
 461     if ((!pSLL) || (pSLL->scanline > scanline))
 462     {
 463         if (*iSLLBlock > SLLSPERBLOCK-1)
 464         {
 465             tmpSLLBlock =
 466             (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
 467             if (!tmpSLLBlock)
 468                 return FALSE;
 469             (*SLLBlock)->next = tmpSLLBlock;
 470             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
 471             *SLLBlock = tmpSLLBlock;
 472             *iSLLBlock = 0;
 473         }
 474         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 475
 476         pSLL->next = pPrevSLL->next;
 477         pSLL->edgelist = (EdgeTableEntry *)NULL;
 478         pPrevSLL->next = pSLL;
 479     }
 480     pSLL->scanline = scanline;
 481
 482     /*
 483      * now insert the edge in the right bucket
 484      */
 485     prev = (EdgeTableEntry *)NULL;
 486     start = pSLL->edgelist;
 487     while (start && (start->bres.minor < ETE->bres.minor))
 488     {
 489         prev = start;
 490         start = start->next;
 491     }
 492     ETE->next = start;
 493
 494     if (prev)
 495         prev->next = ETE;
 496     else
 497         pSLL->edgelist = ETE;
 498     return TRUE;
 499 }
 500
 501 /*
 502  *     CreateEdgeTable
 503  *
 504  *     This routine creates the edge table for
 505  *     scan converting polygons.
 506  *     The Edge Table (ET) looks like:
 507  *
 508  *    EdgeTable
 509  *     --------
 510  *    |  ymax  |        ScanLineLists
 511  *    |scanline|-->------------>-------------->...
 512  *     --------   |scanline|   |scanline|
 513  *                |edgelist|   |edgelist|
 514  *                ---------    ---------
 515  *                    |             |
 516  *                    |             |
 517  *                    V             V
 518  *              list of ETEs   list of ETEs
 519  *
 520  *     where ETE is an EdgeTableEntry data structure,
 521  *     and there is one ScanLineList per scanline at
 522  *     which an edge is initially entered.
 523  *
 524  */
 525
 526 static bool
 527 miCreateETandAET(int count, const wxPoint * pts, EdgeTable *ET, EdgeTableEntry *AET,
 528                  EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
 529 {
 530     const wxPoint* top, *bottom;
 531     const wxPoint* PrevPt, *CurrPt;
 532     int iSLLBlock = 0;
 533
 534     int dy;
 535
 536     if (count < 2)  return TRUE;
 537
 538     /*
 539      *  initialize the Active Edge Table
 540      */
 541     AET->next = (EdgeTableEntry *)NULL;
 542     AET->back = (EdgeTableEntry *)NULL;
 543     AET->nextWETE = (EdgeTableEntry *)NULL;
 544     AET->bres.minor = INT_MIN;
 545
 546     /*
 547      *  initialize the Edge Table.
 548      */
 549     ET->scanlines.next = (ScanLineList *)NULL;
 550     ET->ymax = INT_MIN;
 551     ET->ymin = INT_MAX;
 552     pSLLBlock->next = (ScanLineListBlock *)NULL;
 553
 554     PrevPt = &pts[count-1];
 555
 556     /*
 557      *  for each vertex in the array of points.
 558      *  In this loop we are dealing with two vertices at
 559      *  a time -- these make up one edge of the polygon.
 560      */
 561     while (count--)
 562     {
 563         CurrPt = pts++;
 564
 565         /*
 566          *  find out which point is above and which is below.
 567          */
 568         if (PrevPt->y > CurrPt->y)
 569         {
 570             bottom = PrevPt, top = CurrPt;
 571             pETEs->ClockWise = 0;
 572         }
 573         else
 574         {
 575             bottom = CurrPt, top = PrevPt;
 576             pETEs->ClockWise = 1;
 577         }
 578
 579         /*
 580          * don't add horizontal edges to the Edge table.
 581          */
 582         if (bottom->y != top->y)
 583         {
 584             pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
 585
 586             /*
 587              *  initialize integer edge algorithm
 588              */
 589             dy = bottom->y - top->y;
 590             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
 591
 592             if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
 593             {
 594                 miFreeStorage(pSLLBlock->next);
 595                 return FALSE;
 596             }
 597
 598             ET->ymax = wxMax(ET->ymax, PrevPt->y);
 599             ET->ymin = wxMin(ET->ymin, PrevPt->y);
 600             pETEs++;
 601         }
 602
 603         PrevPt = CurrPt;
 604     }
 605     return TRUE;
 606 }
 607
 608 /*
 609  *     loadAET
 610  *
 611  *     This routine moves EdgeTableEntries from the
 612  *     EdgeTable into the Active Edge Table,
 613  *     leaving them sorted by smaller x coordinate.
 614  *
 615  */
 616
 617 static void
 618 miloadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
 619 {
 620     EdgeTableEntry *pPrevAET;
 621     EdgeTableEntry *tmp;
 622
 623     pPrevAET = AET;
 624     AET = AET->next;
 625     while (ETEs)
 626     {
 627         while (AET && (AET->bres.minor < ETEs->bres.minor))
 628         {
 629             pPrevAET = AET;
 630             AET = AET->next;
 631         }
 632         tmp = ETEs->next;
 633         ETEs->next = AET;
 634         if (AET)
 635             AET->back = ETEs;
 636         ETEs->back = pPrevAET;
 637         pPrevAET->next = ETEs;
 638         pPrevAET = ETEs;
 639
 640         ETEs = tmp;
 641     }
 642 }
 643
 644 /*
 645  *     computeWAET
 646  *
 647  *     This routine links the AET by the
 648  *     nextWETE (winding EdgeTableEntry) link for
 649  *     use by the winding number rule.  The final
 650  *     Active Edge Table (AET) might look something
 651  *     like:
 652  *
 653  *     AET
 654  *     ----------  ---------   ---------
 655  *     |ymax    |  |ymax    |  |ymax    |
 656  *     | ...    |  |...     |  |...     |
 657  *     |next    |->|next    |->|next    |->...
 658  *     |nextWETE|  |nextWETE|  |nextWETE|
 659  *     ---------   ---------   ^--------
 660  *         |                   |       |
 661  *         V------------------->       V---> ...
 662  *
 663  */
 664 static void
 665 micomputeWAET(EdgeTableEntry *AET)
 666 {
 667     EdgeTableEntry *pWETE;
 668     int inside = 1;
 669     int isInside = 0;
 670
 671     AET->nextWETE = (EdgeTableEntry *)NULL;
 672     pWETE = AET;
 673     AET = AET->next;
 674     while (AET)
 675     {
 676         if (AET->ClockWise)
 677             isInside++;
 678         else
 679             isInside--;
 680
 681         if ((!inside && !isInside) ||
 682             ( inside &&  isInside))
 683         {
 684             pWETE->nextWETE = AET;
 685             pWETE = AET;
 686             inside = !inside;
 687         }
 688         AET = AET->next;
 689     }
 690     pWETE->nextWETE = (EdgeTableEntry *)NULL;
 691 }
 692
 693 /*
 694  *     InsertionSort
 695  *
 696  *     Just a simple insertion sort using
 697  *     pointers and back pointers to sort the Active
 698  *     Edge Table.
 699  *
 700  */
 701
 702 static int
 703 miInsertionSort(EdgeTableEntry *AET)
 704 {
 705     EdgeTableEntry *pETEchase;
 706     EdgeTableEntry *pETEinsert;
 707     EdgeTableEntry *pETEchaseBackTMP;
 708     int changed = 0;
 709
 710     AET = AET->next;
 711     while (AET)
 712     {
 713         pETEinsert = AET;
 714         pETEchase = AET;
 715         while (pETEchase->back->bres.minor > AET->bres.minor)
 716             pETEchase = pETEchase->back;
 717
 718         AET = AET->next;
 719         if (pETEchase != pETEinsert)
 720         {
 721             pETEchaseBackTMP = pETEchase->back;
 722             pETEinsert->back->next = AET;
 723             if (AET)
 724                 AET->back = pETEinsert->back;
 725             pETEinsert->next = pETEchase;
 726             pETEchase->back->next = pETEinsert;
 727             pETEchase->back = pETEinsert;
 728             pETEinsert->back = pETEchaseBackTMP;
 729             changed = 1;
 730         }
 731     }
 732     return(changed);
 733 }
 734
 735 /*
 736  *     Clean up our act.
 737  */
 738 static void
 739 miFreeStorage(ScanLineListBlock *pSLLBlock)
 740 {
 741     ScanLineListBlock   *tmpSLLBlock;
 742
 743     while (pSLLBlock)
 744     {
 745         tmpSLLBlock = pSLLBlock->next;
 746         free(pSLLBlock);
 747         pSLLBlock = tmpSLLBlock;
 748     }
 749 }
 750
 751 /* mipolygen.c */
 752
 753 static bool
 754 scanFillGeneralPoly( wxRegion* rgn,
 755                   int   count,              /* number of points        */
 756                   const wxPoint *ptsIn,               /* the points              */
 757                   wxPolygonFillMode fillStyle
 758                   )
 759 {
 760     EdgeTableEntry *pAET;  /* the Active Edge Table   */
 761     int y;                 /* the current scanline    */
 762     int nPts = 0;          /* number of pts in buffer */
 763     EdgeTableEntry *pWETE; /* Winding Edge Table      */
 764     ScanLineList *pSLL;    /* Current ScanLineList    */
 765     wxPoint * ptsOut;      /* ptr to output buffers   */
 766     int *width;
 767     wxPoint FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */
 768     int FirstWidth[NUMPTSTOBUFFER];
 769     EdgeTableEntry *pPrevAET;       /* previous AET entry      */
 770     EdgeTable ET;                   /* Edge Table header node  */
 771     EdgeTableEntry AET;             /* Active ET header node   */
 772     EdgeTableEntry *pETEs;          /* Edge Table Entries buff */
 773     ScanLineListBlock SLLBlock;     /* header for ScanLineList */
 774     int fixWAET = 0;
 775
 776     if (count < 3)
 777         return(TRUE);
 778
 779     if(!(pETEs = (EdgeTableEntry *)
 780          malloc(sizeof(EdgeTableEntry) * count)))
 781         return(FALSE);
 782     ptsOut = FirstPoint;
 783     width = FirstWidth;
 784     if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock))
 785     {
 786         free(pETEs);
 787         return(FALSE);
 788     }
 789     pSLL = ET.scanlines.next;
 790
 791     if (fillStyle == wxODDEVEN_RULE)
 792     {
 793         /*
 794          *  for each scanline
 795          */
 796         for (y = ET.ymin; y < ET.ymax; y++)
 797         {
 798             /*
 799              *  Add a new edge to the active edge table when we
 800              *  get to the next edge.
 801              */
 802             if (pSLL && y == pSLL->scanline)
 803             {
 804                 miloadAET(&AET, pSLL->edgelist);
 805                 pSLL = pSLL->next;
 806             }
 807             pPrevAET = &AET;
 808             pAET = AET.next;
 809
 810             /*
 811              *  for each active edge
 812              */
 813             while (pAET)
 814             {
 815                 ptsOut->x = pAET->bres.minor;
 816                 ptsOut++->y = y;
 817                 *width++ = pAET->next->bres.minor - pAET->bres.minor;
 818                 nPts++;
 819
 820                 /*
 821                  *  send out the buffer when its full
 822                  */
 823                 if (nPts == NUMPTSTOBUFFER)
 824                 {
 825                     // (*pgc->ops->FillSpans)(dst, pgc,
 826                     //     nPts, FirstPoint, FirstWidth,1);
 827
 828                     for ( int i = 0 ; i < nPts; ++i)
 829                     {
 830                         wxRect rect;
 831                         rect.y = FirstPoint[i].y;
 832                         rect.x = FirstPoint[i].x;
 833                         rect.height = 1;
 834                         rect.width = FirstWidth[i];
 835                         rgn->Union(rect);
 836                     }
 837                     ptsOut = FirstPoint;
 838                     width = FirstWidth;
 839                     nPts = 0;
 840                 }
 841                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
 842                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
 843             }
 844             miInsertionSort(&AET);
 845         }
 846     }
 847     else      /* default to WindingNumber */
 848     {
 849         /*
 850          *  for each scanline
 851          */
 852         for (y = ET.ymin; y < ET.ymax; y++)
 853         {
 854             /*
 855              *  Add a new edge to the active edge table when we
 856              *  get to the next edge.
 857              */
 858             if (pSLL && y == pSLL->scanline)
 859             {
 860                 miloadAET(&AET, pSLL->edgelist);
 861                 micomputeWAET(&AET);
 862                 pSLL = pSLL->next;
 863             }
 864             pPrevAET = &AET;
 865             pAET = AET.next;
 866             pWETE = pAET;
 867
 868             /*
 869              *  for each active edge
 870              */
 871             while (pAET)
 872             {
 873                 /*
 874                  *  if the next edge in the active edge table is
 875                  *  also the next edge in the winding active edge
 876                  *  table.
 877                  */
 878                 if (pWETE == pAET)
 879                 {
 880                     ptsOut->x = pAET->bres.minor;
 881                     ptsOut++->y = y;
 882                     *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor;
 883                     nPts++;
 884
 885                     /*
 886                      *  send out the buffer
 887                      */
 888                     if (nPts == NUMPTSTOBUFFER)
 889                     {
 890                         // (*pgc->ops->FillSpans)(dst, pgc,
 891                         //     nPts, FirstPoint, FirstWidth,1);
 892                         for ( int i = 0 ; i < nPts ; ++i)
 893                         {
 894                             wxRect rect;
 895                             rect.y = FirstPoint[i].y;
 896                             rect.x = FirstPoint[i].x;
 897                             rect.height = 1;
 898                             rect.width = FirstWidth[i];
 899                             rgn->Union(rect);
 900                         }
 901                         ptsOut = FirstPoint;
 902                         width  = FirstWidth;
 903                         nPts = 0;
 904                     }
 905
 906                     pWETE = pWETE->nextWETE;
 907                     while (pWETE != pAET)
 908                         EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
 909                     pWETE = pWETE->nextWETE;
 910                 }
 911                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
 912             }
 913
 914             /*
 915              *  reevaluate the Winding active edge table if we
 916              *  just had to resort it or if we just exited an edge.
 917              */
 918             if (miInsertionSort(&AET) || fixWAET)
 919             {
 920                 micomputeWAET(&AET);
 921                 fixWAET = 0;
 922             }
 923         }
 924     }
 925
 926     /*
 927      *     Get any spans that we missed by buffering
 928      */
 929     // (*pgc->ops->FillSpans)(dst, pgc,
 930     //     nPts, FirstPoint, FirstWidth,1);
 931     for ( int i = 0 ; i < nPts; ++i)
 932     {
 933         wxRect rect;
 934         rect.y = FirstPoint[i].y;
 935         rect.x = FirstPoint[i].x;
 936         rect.height = 1;
 937         rect.width = FirstWidth[i];
 938         rgn->Union(rect);
 939     }
 940
 941     free(pETEs);
 942     miFreeStorage(SLLBlock.next);
 943     return(TRUE);
 944 }
 945
 946 #endif
 947
 948 wxRegion::wxRegion(size_t n, const wxPoint *points, wxPolygonFillMode fillStyle)
 949 {
 950     // Set the region to a polygon shape generically using a bitmap with the
 951     // polygon drawn on it.
 952
 953     m_refData = new wxRegionRefData();
 954
 955 #if OSX_USE_SCANLINES
 956     scanFillGeneralPoly(this,n,points,fillStyle);
 957 #else
 958     wxCoord mx = 0;
 959     wxCoord my = 0;
 960     wxPoint p;
 961     size_t idx;
 962
 963     // Find the max size needed to draw the polygon
 964     for (idx=0; idx<n; idx++)
 965     {
 966         wxPoint pt = points[idx];
 967         if (pt.x > mx)
 968             mx = pt.x;
 969         if (pt.y > my)
 970             my = pt.y;
 971     }
 972
 973     // Make the bitmap
 974     wxBitmap bmp(mx, my);
 975     wxMemoryDC dc(bmp);
 976     dc.SetBackground(*wxBLACK_BRUSH);
 977     dc.Clear();
 978     dc.SetPen(*wxWHITE_PEN);
 979     dc.SetBrush(*wxWHITE_BRUSH);
 980     dc.DrawPolygon(n, (wxPoint*)points, 0, 0, fillStyle);
 981     dc.SelectObject(wxNullBitmap);
 982     bmp.SetMask(new wxMask(bmp, *wxBLACK));
 983
 984     // Use it to set this region
 985     Union(bmp);
 986 #endif
 987 }
 988
 989 wxRegion::~wxRegion()
 990 {
 991     // m_refData unrefed in ~wxObject
 992 }
 993
 994 wxGDIRefData *wxRegion::CreateGDIRefData() const
 995 {
 996     return new wxRegionRefData;
 997 }
 998
 999 wxGDIRefData *wxRegion::CloneGDIRefData(const wxGDIRefData *data) const
1000 {
1001     return new wxRegionRefData(*static_cast<const wxRegionRefData *>(data));
1002 }
1003
1004 //-----------------------------------------------------------------------------
1005 //# Modify region
1006 //-----------------------------------------------------------------------------
1007
1008 //! Clear current region
1009 void wxRegion::Clear()
1010 {
1011     UnRef();
1012 }
1013
1014 // Move the region
1015 bool wxRegion::DoOffset(wxCoord x, wxCoord y)
1016 {
1017     wxCHECK_MSG( m_refData, false, wxT("invalid wxRegion") );
1018
1019     if ( !x && !y )
1020         // nothing to do
1021         return true;
1022
1023     AllocExclusive();
1024
1025     verify_noerr( HIShapeOffset( M_REGION , x , y ) ) ;
1026
1027     return true ;
1028 }
1029
1030 bool wxRegion::DoUnionWithRect(const wxRect& rect)
1031 {
1032     if ( !m_refData )
1033     {
1034         m_refData = new wxRegionRefData(rect.x , rect.y , rect.width , rect.height);
1035         return true;
1036     }
1037
1038     AllocExclusive();
1039
1040     CGRect r = CGRectMake(rect.x , rect.y , rect.width , rect.height);
1041     HIShapeUnionWithRect(M_REGION , &r);
1042
1043     return true;
1044 }
1045
1046 //! Union /e region with this.
1047 bool wxRegion::DoCombine(const wxRegion& region, wxRegionOp op)
1048 {
1049     wxCHECK_MSG( region.IsOk(), false, wxT("invalid wxRegion") );
1050
1051     // Handle the special case of not initialized (e.g. default constructed)
1052     // region as we can't use HIShape functions if we don't have any shape.
1053     if ( !m_refData )
1054     {
1055         switch ( op )
1056         {
1057             case wxRGN_COPY:
1058             case wxRGN_OR:
1059             case wxRGN_XOR:
1060                 // These operations make sense with a null region.
1061                 *this = region;
1062                 return true;
1063
1064             case wxRGN_AND:
1065             case wxRGN_DIFF:
1066                 // Those ones don't really make sense so just leave this region
1067                 // empty/invalid.
1068                 return false;
1069         }
1070
1071         wxFAIL_MSG( wxT("Unknown region operation") );
1072         return false;
1073     }
1074
1075     AllocExclusive();
1076
1077     switch (op)
1078     {
1079         case wxRGN_AND:
1080             verify_noerr( HIShapeIntersect( M_REGION , OTHER_M_REGION(region) , M_REGION ) );
1081             break ;
1082
1083         case wxRGN_OR:
1084             verify_noerr( HIShapeUnion( M_REGION , OTHER_M_REGION(region) , M_REGION ) );
1085             break ;
1086
1087         case wxRGN_XOR:
1088             {
1089                 // XOR is defined as the difference between union and intersection
1090                 wxCFRef< HIShapeRef > unionshape( HIShapeCreateUnion( M_REGION , OTHER_M_REGION(region) ) );
1091                 wxCFRef< HIShapeRef > intersectionshape( HIShapeCreateIntersection( M_REGION , OTHER_M_REGION(region) ) );
1092                 verify_noerr( HIShapeDifference( unionshape, intersectionshape, M_REGION ) );
1093             }
1094             break ;
1095
1096         case wxRGN_DIFF:
1097             verify_noerr( HIShapeDifference( M_REGION , OTHER_M_REGION(region) , M_REGION ) ) ;
1098             break ;
1099
1100         case wxRGN_COPY:
1101         default:
1102             M_REGION.reset( HIShapeCreateMutableCopy( OTHER_M_REGION(region) ) );
1103             break ;
1104     }
1105
1106     return true;
1107 }
1108
1109 //-----------------------------------------------------------------------------
1110 //# Information on region
1111 //-----------------------------------------------------------------------------
1112
1113 bool wxRegion::DoIsEqual(const wxRegion& region) const
1114 {
1115     // There doesn't seem to be any native function for checking the equality
1116     // of HIShapes so we compute their differences to determine if they are
1117     // equal.
1118     wxRegion r(*this);
1119     r.Subtract(region);
1120
1121     if ( !r.IsEmpty() )
1122         return false;
1123
1124     wxRegion r2(region);
1125     r2.Subtract(*this);
1126
1127     return r2.IsEmpty();
1128 }
1129
1130 // Outer bounds of region
1131 bool wxRegion::DoGetBox(wxCoord& x, wxCoord& y, wxCoord& w, wxCoord& h) const
1132 {
1133     if (m_refData)
1134     {
1135         CGRect box ;
1136         HIShapeGetBounds( M_REGION , &box ) ;
1137         x = static_cast<int>(box.origin.x);
1138         y = static_cast<int>(box.origin.y);
1139         w = static_cast<int>(box.size.width);
1140         h = static_cast<int>(box.size.height);
1141
1142         return true;
1143     }
1144     else
1145     {
1146         x = y = w = h = 0;
1147
1148         return false;
1149     }
1150 }
1151
1152 // Is region empty?
1153 bool wxRegion::IsEmpty() const
1154 {
1155     if ( m_refData )
1156         return HIShapeIsEmpty( M_REGION ) ;
1157     else
1158         return true ;
1159 }
1160
1161 WXHRGN wxRegion::GetWXHRGN() const
1162 {
1163     if ( !m_refData )
1164         return NULL;
1165
1166     return M_REGION ;
1167 }
1168
1169 //-----------------------------------------------------------------------------
1170 //# Tests
1171 //-----------------------------------------------------------------------------
1172
1173 // Does the region contain the point?
1174 wxRegionContain wxRegion::DoContainsPoint(wxCoord x, wxCoord y) const
1175 {
1176     if (!m_refData)
1177         return wxOutRegion;
1178
1179     CGPoint p = CGPointMake( x, y ) ;
1180     if (HIShapeContainsPoint( M_REGION , &p ) )
1181         return wxInRegion;
1182
1183     return wxOutRegion;
1184 }
1185
1186 // Does the region contain the rectangle (x, y, w, h)?
1187 wxRegionContain wxRegion::DoContainsRect(const wxRect& r) const
1188 {
1189     if (!m_refData)
1190         return wxOutRegion;
1191
1192     CGRect rect = CGRectMake(r.x,r.y,r.width,r.height);
1193     wxCFRef<HIShapeRef> rectshape(HIShapeCreateWithRect(&rect));
1194     wxCFRef<HIShapeRef> intersect(HIShapeCreateIntersection(rectshape,M_REGION));
1195     CGRect bounds;
1196     HIShapeGetBounds(intersect, &bounds);
1197
1198     if ( HIShapeIsRectangular(intersect) && CGRectEqualToRect(rect,bounds) )
1199         return wxInRegion;
1200     else if ( HIShapeIsEmpty( intersect ) )
1201         return wxOutRegion;
1202     else
1203         return wxPartRegion;
1204 }
1205
1206 ///////////////////////////////////////////////////////////////////////////////
1207 //                                                                           //
1208 //                               wxRegionIterator                            //
1209 //                                                                           //
1210 ///////////////////////////////////////////////////////////////////////////////
1211
1212 /*!
1213  * Initialize empty iterator
1214  */
1215 wxRegionIterator::wxRegionIterator()
1216     : m_current(0), m_numRects(0), m_rects(NULL)
1217 {
1218 }
1219
1220 wxRegionIterator::~wxRegionIterator()
1221 {
1222     wxDELETEA(m_rects);
1223 }
1224
1225 wxRegionIterator::wxRegionIterator(const wxRegionIterator& iterator)
1226     : wxObject()
1227     , m_current(iterator.m_current)
1228     , m_numRects(0)
1229     , m_rects(NULL)
1230 {
1231     SetRects(iterator.m_numRects, iterator.m_rects);
1232 }
1233
1234 wxRegionIterator& wxRegionIterator::operator=(const wxRegionIterator& iterator)
1235 {
1236     m_current  = iterator.m_current;
1237     SetRects(iterator.m_numRects, iterator.m_rects);
1238
1239     return *this;
1240 }
1241
1242 /*!
1243  * Set iterator rects for region
1244  */
1245 void wxRegionIterator::SetRects(long numRects, wxRect *rects)
1246 {
1247     wxDELETEA(m_rects);
1248
1249     if (rects && (numRects > 0))
1250     {
1251         int i;
1252
1253         m_rects = new wxRect[numRects];
1254         for (i = 0; i < numRects; i++)
1255             m_rects[i] = rects[i];
1256     }
1257
1258     m_numRects = numRects;
1259 }
1260
1261 /*!
1262  * Initialize iterator for region
1263  */
1264 wxRegionIterator::wxRegionIterator(const wxRegion& region)
1265 {
1266     m_rects = NULL;
1267
1268     Reset(region);
1269 }
1270
1271 /*!
1272  * Reset iterator for a new /e region.
1273  */
1274
1275 class RegionToRectsCallbackData
1276 {
1277 public :
1278     wxRect* m_rects ;
1279     long m_current ;
1280 };
1281
1282 OSStatus wxOSXRegionToRectsCounterCallback(
1283     int message, HIShapeRef WXUNUSED(region), const CGRect *WXUNUSED(rect), void *data )
1284 {
1285     long *m_numRects = (long*) data ;
1286     if ( message == kHIShapeEnumerateInit )
1287     {
1288         (*m_numRects) = 0 ;
1289     }
1290     else if (message == kHIShapeEnumerateRect)
1291     {
1292         (*m_numRects) += 1 ;
1293     }
1294
1295     return noErr;
1296 }
1297
1298 OSStatus wxOSXRegionToRectsSetterCallback(
1299     int message, HIShapeRef WXUNUSED(region), const CGRect *rect, void *data )
1300 {
1301     if (message == kHIShapeEnumerateRect)
1302     {
1303         RegionToRectsCallbackData *cb = (RegionToRectsCallbackData*) data ;
1304         cb->m_rects[cb->m_current++] = wxRect( rect->origin.x , rect->origin.y , rect->size.width , rect->size.height ) ;
1305     }
1306
1307     return noErr;
1308 }
1309
1310 void wxRegionIterator::Reset(const wxRegion& region)
1311 {
1312     m_current = 0;
1313     m_region = region;
1314
1315     wxDELETEA(m_rects);
1316
1317     if (m_region.IsEmpty())
1318     {
1319         m_numRects = 0;
1320     }
1321     else
1322     {
1323 #if 0
1324         // fallback code in case we ever need it again
1325         // copying this to a path and dissecting the path would be an option
1326         m_numRects = 1;
1327         m_rects = new wxRect[m_numRects];
1328         m_rects[0] = m_region.GetBox();
1329 #endif
1330         OSStatus err = HIShapeEnumerate (OTHER_M_REGION(region), kHIShapeParseFromTopLeft, wxOSXRegionToRectsCounterCallback,
1331             (void*)&m_numRects);
1332         if (err == noErr)
1333         {
1334             m_rects = new wxRect[m_numRects];
1335             RegionToRectsCallbackData data ;
1336             data.m_rects = m_rects ;
1337             data.m_current = 0 ;
1338             HIShapeEnumerate( OTHER_M_REGION(region), kHIShapeParseFromTopLeft, wxOSXRegionToRectsSetterCallback,
1339                 (void*)&data );
1340         }
1341         else
1342         {
1343             m_numRects = 0;
1344         }
1345     }
1346 }
1347
1348 /*!
1349  * Increment iterator. The rectangle returned is the one after the
1350  * incrementation.
1351  */
1352 wxRegionIterator& wxRegionIterator::operator ++ ()
1353 {
1354     if (m_current < m_numRects)
1355         ++m_current;
1356
1357     return *this;
1358 }
1359
1360 /*!
1361  * Increment iterator. The rectangle returned is the one before the
1362  * incrementation.
1363  */
1364 wxRegionIterator wxRegionIterator::operator ++ (int)
1365 {
1366     wxRegionIterator previous(*this);
1367
1368     if (m_current < m_numRects)
1369         ++m_current;
1370
1371     return previous;
1372 }
1373
1374 long wxRegionIterator::GetX() const
1375 {
1376     if (m_current < m_numRects)
1377         return m_rects[m_current].x;
1378
1379     return 0;
1380 }
1381
1382 long wxRegionIterator::GetY() const
1383 {
1384     if (m_current < m_numRects)
1385         return m_rects[m_current].y;
1386
1387     return 0;
1388 }
1389
1390 long wxRegionIterator::GetW() const
1391 {
1392     if (m_current < m_numRects)
1393         return m_rects[m_current].width ;
1394
1395     return 0;
1396 }
1397
1398 long wxRegionIterator::GetH() const
1399 {
1400     if (m_current < m_numRects)
1401         return m_rects[m_current].height;
1402
1403     return 0;
1404 }
1405
1406 #endif