graphics/path.c

   1 /*
   2  * Graphics paths (BeginPath, EndPath etc.)
   3  *
   4  * Copyright 1997, 1998 Martin Boehme
   5  */
   6
   7 #include <assert.h>
   8 #include <malloc.h>
   9 #include <math.h>
  10
  11 #include "windows.h"
  12 #include "winerror.h"
  13
  14 #include "dc.h"
  15 #include "debug.h"
  16 #include "path.h"
  17
  18 /* Notes on the implementation
  19  *
  20  * The implementation is based on dynamically resizable arrays of points and
  21  * flags. I dithered for a bit before deciding on this implementation, and
  22  * I had even done a bit of work on a linked list version before switching
  23  * to arrays. It's a bit of a tradeoff. When you use linked lists, the
  24  * implementation of FlattenPath is easier, because you can rip the
  25  * PT_BEZIERTO entries out of the middle of the list and link the
  26  * corresponding PT_LINETO entries in. However, when you use arrays,
  27  * PathToRegion becomes easier, since you can essentially just pass your array
  28  * of points to CreatePolyPolygonRgn. Also, if I'd used linked lists, I would
  29  * have had the extra effort of creating a chunk-based allocation scheme
  30  * in order to use memory effectively. That's why I finally decided to use
  31  * arrays. Note by the way that the array based implementation has the same
  32  * linear time complexity that linked lists would have since the arrays grow
  33  * exponentially.
  34  *
  35  * The points are stored in the path in device coordinates. This is
  36  * consistent with the way Windows does things (for instance, see the Win32
  37  * SDK documentation for GetPath).
  38  *
  39  * The word "stroke" appears in several places (e.g. in the flag
  40  * GdiPath.newStroke). A stroke consists of a PT_MOVETO followed by one or
  41  * more PT_LINETOs or PT_BEZIERTOs, up to, but not including, the next
  42  * PT_MOVETO. Note that this is not the same as the definition of a figure;
  43  * a figure can contain several strokes.
  44  *
  45  * I modified the drawing functions (MoveTo, LineTo etc.) to test whether
  46  * the path is open and to call the corresponding function in path.c if this
  47  * is the case. A more elegant approach would be to modify the function
  48  * pointers in the DC_FUNCTIONS structure; however, this would be a lot more
  49  * complex. Also, the performance degradation caused by my approach in the
  50  * case where no path is open is so small that it cannot be measured.
  51  *
  52  * Martin Boehme
  53  */
  54
  55 /* FIXME: A lot of stuff isn't implemented yet. There is much more to come. */
  56
  57 #define NUM_ENTRIES_INITIAL 16  /* Initial size of points / flags arrays  */
  58 #define GROW_FACTOR_NUMER    2  /* Numerator of grow factor for the array */
  59 #define GROW_FACTOR_DENOM    1  /* Denominator of grow factor             */
  60
  61
  62 static BOOL32 PATH_PathToRegion(const GdiPath *pPath, INT32 nPolyFillMode,
  63    HRGN32 *pHrgn);
  64 static void   PATH_EmptyPath(GdiPath *pPath);
  65 static BOOL32 PATH_AddEntry(GdiPath *pPath, POINT32 point, BYTE flags);
  66 static BOOL32 PATH_ReserveEntries(GdiPath *pPath, INT32 numEntries);
  67 static BOOL32 PATH_GetPathFromHDC(HDC32 hdc, GdiPath **ppPath);
  68 static BOOL32 PATH_DoArcPart(GdiPath *pPath, POINT32 corners[],
  69    double angleStart, double angleEnd, BOOL32 addMoveTo);
  70 static void PATH_ScaleNormalizedPoint(POINT32 corners[], double x, double y,
  71    POINT32 *pPoint);
  72 static void PATH_NormalizePoint(POINT32 corners[], const POINT32 *pPoint,
  73    double *pX, double *pY);
  74
  75
  76 /***********************************************************************
  77  *           BeginPath16    (GDI.512)
  78  */
  79 BOOL16 WINAPI BeginPath16(HDC16 hdc)
  80 {
  81    return (BOOL16)BeginPath32((HDC32)hdc);
  82 }
  83
  84
  85 /***********************************************************************
  86  *           BeginPath32    (GDI32.9)
  87  */
  88 BOOL32 WINAPI BeginPath32(HDC32 hdc)
  89 {
  90    GdiPath *pPath;
  91
  92    /* Get pointer to path */
  93    if(!PATH_GetPathFromHDC(hdc, &pPath))
  94    {
  95       SetLastError(ERROR_INVALID_HANDLE);
  96       return FALSE;
  97    }
  98
  99    /* If path is already open, do nothing */
 100    if(pPath->state==PATH_Open)
 101       return TRUE;
 102
 103    /* Make sure that path is empty */
 104    PATH_EmptyPath(pPath);
 105
 106    /* Initialize variables for new path */
 107    pPath->newStroke=TRUE;
 108    pPath->state=PATH_Open;
 109
 110    return TRUE;
 111 }
 112
 113
 114 /***********************************************************************
 115  *           EndPath16    (GDI.514)
 116  */
 117 BOOL16 WINAPI EndPath16(HDC16 hdc)
 118 {
 119    return (BOOL16)EndPath32((HDC32)hdc);
 120 }
 121
 122
 123 /***********************************************************************
 124  *           EndPath32    (GDI32.78)
 125  */
 126 BOOL32 WINAPI EndPath32(HDC32 hdc)
 127 {
 128    GdiPath *pPath;
 129
 130    /* Get pointer to path */
 131    if(!PATH_GetPathFromHDC(hdc, &pPath))
 132    {
 133       SetLastError(ERROR_INVALID_HANDLE);
 134       return FALSE;
 135    }
 136
 137    /* Check that path is currently being constructed */
 138    if(pPath->state!=PATH_Open)
 139    {
 140       SetLastError(ERROR_CAN_NOT_COMPLETE);
 141       return FALSE;
 142    }
 143
 144    /* Set flag to indicate that path is finished */
 145    pPath->state=PATH_Closed;
 146
 147    return TRUE;
 148 }
 149
 150
 151 /***********************************************************************
 152  *           AbortPath16    (GDI.511)
 153  */
 154 BOOL16 WINAPI AbortPath16(HDC16 hdc)
 155 {
 156    return (BOOL16)AbortPath32((HDC32)hdc);
 157 }
 158
 159
 160 /******************************************************************************
 161  * AbortPath32 [GDI32.1]
 162  * Closes and discards paths from device context
 163  *
 164  * NOTES
 165  *    Check that SetLastError is being called correctly
 166  *
 167  * PARAMS
 168  *    hdc [I] Handle to device context
 169  *
 170  * RETURNS STD
 171  */
 172 BOOL32 WINAPI AbortPath32( HDC32 hdc )
 173 {
 174    GdiPath *pPath;
 175
 176    /* Get pointer to path */
 177    if(!PATH_GetPathFromHDC(hdc, &pPath))
 178    {
 179       SetLastError(ERROR_INVALID_PARAMETER);
 180       return FALSE;
 181    }
 182
 183    /* Remove all entries from the path */
 184    PATH_EmptyPath(pPath);
 185
 186    return TRUE;
 187 }
 188
 189
 190 /***********************************************************************
 191  *           CloseFigure16    (GDI.513)
 192  */
 193 BOOL16 WINAPI CloseFigure16(HDC16 hdc)
 194 {
 195    return (BOOL16)CloseFigure32((HDC32)hdc);
 196 }
 197
 198
 199 /***********************************************************************
 200  *           CloseFigure32    (GDI32.16)
 201  */
 202 BOOL32 WINAPI CloseFigure32(HDC32 hdc)
 203 /* FIXME: Check that SetLastError is being called correctly */
 204 {
 205    GdiPath *pPath;
 206
 207    /* Get pointer to path */
 208    if(!PATH_GetPathFromHDC(hdc, &pPath))
 209    {
 210       SetLastError(ERROR_INVALID_PARAMETER);
 211       return FALSE;
 212    }
 213
 214    /* Check that path is open */
 215    if(pPath->state!=PATH_Open)
 216    {
 217       SetLastError(ERROR_CAN_NOT_COMPLETE);
 218       return FALSE;
 219    }
 220
 221    /* Set PT_CLOSEFIGURE on the last entry and start a new stroke */
 222    if(pPath->numEntriesUsed)
 223    {
 224       pPath->pFlags[pPath->numEntriesUsed-1]|=PT_CLOSEFIGURE;
 225       pPath->newStroke=TRUE;
 226    }
 227
 228    return TRUE;
 229 }
 230
 231
 232 /***********************************************************************
 233  *           GetPath16    (GDI.517)
 234  */
 235 INT16 WINAPI GetPath16(HDC16 hdc, LPPOINT16 pPoints, LPBYTE pTypes,
 236    INT16 nSize)
 237 {
 238    FIXME(gdi, "Unimplemented stub\n");
 239
 240    return 0;
 241 }
 242
 243
 244 /***********************************************************************
 245  *           GetPath32    (GDI32.210)
 246  */
 247 INT32 WINAPI GetPath32(HDC32 hdc, LPPOINT32 pPoints, LPBYTE pTypes,
 248    INT32 nSize)
 249 {
 250    GdiPath *pPath;
 251
 252    /* Get pointer to path */
 253    if(!PATH_GetPathFromHDC(hdc, &pPath))
 254    {
 255       SetLastError(ERROR_INVALID_PARAMETER);
 256       return -1;
 257    }
 258
 259    /* Check that path is closed */
 260    if(pPath->state!=PATH_Closed)
 261    {
 262       SetLastError(ERROR_CAN_NOT_COMPLETE);
 263       return -1;
 264    }
 265
 266    if(nSize==0)
 267       return pPath->numEntriesUsed;
 268    else if(nSize<pPath->numEntriesUsed)
 269    {
 270       SetLastError(ERROR_INVALID_PARAMETER);
 271       return -1;
 272    }
 273    else
 274    {
 275       memcpy(pPoints, pPath->pPoints, sizeof(POINT32)*pPath->numEntriesUsed);
 276       memcpy(pTypes, pPath->pFlags, sizeof(BYTE)*pPath->numEntriesUsed);
 277
 278       /* Convert the points to logical coordinates */
 279       if(!DPtoLP32(hdc, pPoints, pPath->numEntriesUsed))
 280       {
 281          /* FIXME: Is this the correct value? */
 282          SetLastError(ERROR_CAN_NOT_COMPLETE);
 283          return -1;
 284       }
 285
 286       return pPath->numEntriesUsed;
 287    }
 288 }
 289
 290
 291 /***********************************************************************
 292  *           PathToRegion32    (GDI32.261)
 293  */
 294 HRGN32 WINAPI PathToRegion32(HDC32 hdc)
 295 /* FIXME: Check that SetLastError is being called correctly */
 296 /* The documentation does not state this explicitly, but a test under Windows
 297  * shows that the region which is returned should be in device coordinates.
 298  */
 299 {
 300    GdiPath *pPath;
 301    HRGN32  hrgnRval;
 302
 303    /* Get pointer to path */
 304    if(!PATH_GetPathFromHDC(hdc, &pPath))
 305    {
 306       SetLastError(ERROR_INVALID_PARAMETER);
 307       return 0;
 308    }
 309
 310    /* Check that path is closed */
 311    if(pPath->state!=PATH_Closed)
 312    {
 313       SetLastError(ERROR_CAN_NOT_COMPLETE);
 314       return 0;
 315    }
 316
 317    /* FIXME: Should we empty the path even if conversion failed? */
 318    if(PATH_PathToRegion(pPath, GetPolyFillMode32(hdc), &hrgnRval))
 319       PATH_EmptyPath(pPath);
 320    else
 321       hrgnRval=0;
 322
 323    return hrgnRval;
 324 }
 325
 326
 327 /***********************************************************************
 328  *           FillPath32    (GDI32.100)
 329  */
 330 BOOL32 WINAPI FillPath32(HDC32 hdc)
 331 /* FIXME: Check that SetLastError is being called correctly */
 332 {
 333    GdiPath *pPath;
 334    INT32   mapMode, graphicsMode;
 335    POINT32 ptViewportExt, ptViewportOrg, ptWindowExt, ptWindowOrg;
 336    XFORM   xform;
 337    HRGN32  hrgn;
 338
 339    /* Get pointer to path */
 340    if(!PATH_GetPathFromHDC(hdc, &pPath))
 341    {
 342       SetLastError(ERROR_INVALID_PARAMETER);
 343       return FALSE;
 344    }
 345
 346    /* Check that path is closed */
 347    if(pPath->state!=PATH_Closed)
 348    {
 349       SetLastError(ERROR_CAN_NOT_COMPLETE);
 350       return FALSE;
 351    }
 352
 353    /* Construct a region from the path and fill it */
 354    if(PATH_PathToRegion(pPath, GetPolyFillMode32(hdc), &hrgn))
 355    {
 356       /* Since PaintRgn interprets the region as being in logical coordinates
 357        * but the points we store for the path are already in device
 358        * coordinates, we have to set the mapping mode to MM_TEXT temporarily.
 359        * Using SaveDC to save information about the mapping mode / world
 360        * transform would be easier but would require more overhead, especially
 361        * now that SaveDC saves the current path.
 362        */
 363
 364       /* Save the information about the old mapping mode */
 365       mapMode=GetMapMode32(hdc);
 366       GetViewportExtEx32(hdc, &ptViewportExt);
 367       GetViewportOrgEx32(hdc, &ptViewportOrg);
 368       GetWindowExtEx32(hdc, &ptWindowExt);
 369       GetWindowOrgEx32(hdc, &ptWindowOrg);
 370
 371       /* Save world transform
 372        * NB: The Windows documentation on world transforms would lead one to
 373        * believe that this has to be done only in GM_ADVANCED; however, my
 374        * tests show that resetting the graphics mode to GM_COMPATIBLE does
 375        * not reset the world transform.
 376        */
 377       GetWorldTransform(hdc, &xform);
 378
 379       /* Set MM_TEXT */
 380       SetMapMode32(hdc, MM_TEXT);
 381
 382       /* Paint the region */
 383       PaintRgn32(hdc, hrgn);
 384
 385       /* Restore the old mapping mode */
 386       SetMapMode32(hdc, mapMode);
 387       SetViewportExtEx32(hdc, ptViewportExt.x, ptViewportExt.y, NULL);
 388       SetViewportOrgEx32(hdc, ptViewportOrg.x, ptViewportOrg.y, NULL);
 389       SetWindowExtEx32(hdc, ptWindowExt.x, ptWindowExt.y, NULL);
 390       SetWindowOrgEx32(hdc, ptWindowOrg.x, ptWindowOrg.y, NULL);
 391
 392       /* Go to GM_ADVANCED temporarily to restore the world transform */
 393       graphicsMode=GetGraphicsMode(hdc);
 394       SetGraphicsMode(hdc, GM_ADVANCED);
 395       SetWorldTransform(hdc, &xform);
 396       SetGraphicsMode(hdc, graphicsMode);
 397
 398       /* Empty the path */
 399       PATH_EmptyPath(pPath);
 400       return TRUE;
 401    }
 402    else
 403    {
 404       /* FIXME: Should the path be emptied even if conversion failed? */
 405       /* PATH_EmptyPath(pPath); */
 406       return FALSE;
 407    }
 408 }
 409
 410
 411 /***********************************************************************
 412  *           SelectClipPath32    (GDI32.296)
 413  */
 414 BOOL32 WINAPI SelectClipPath32(HDC32 hdc, INT32 iMode)
 415 /* FIXME: Check that SetLastError is being called correctly */
 416 {
 417    GdiPath *pPath;
 418    HRGN32  hrgnPath, hrgnClip;
 419    BOOL32  success;
 420
 421    /* Get pointer to path */
 422    if(!PATH_GetPathFromHDC(hdc, &pPath))
 423    {
 424       SetLastError(ERROR_INVALID_PARAMETER);
 425       return FALSE;
 426    }
 427
 428    /* Check that path is closed */
 429    if(pPath->state!=PATH_Closed)
 430    {
 431       SetLastError(ERROR_CAN_NOT_COMPLETE);
 432       return FALSE;
 433    }
 434
 435    /* Construct a region from the path */
 436    if(PATH_PathToRegion(pPath, GetPolyFillMode32(hdc), &hrgnPath))
 437    {
 438       hrgnClip=CreateRectRgn32(0, 0, 0, 0);
 439       if(hrgnClip==NULL)
 440          success=FALSE;
 441       else
 442       {
 443          success=(GetClipRgn32(hdc, hrgnClip)!=-1) &&
 444             (CombineRgn32(hrgnClip, hrgnClip, hrgnPath, iMode)!=ERROR) &&
 445             (SelectClipRgn32(hdc, hrgnClip)!=ERROR);
 446          DeleteObject32(hrgnClip);
 447       }
 448
 449       DeleteObject32(hrgnPath);
 450
 451       /* Empty the path */
 452       if(success)
 453          PATH_EmptyPath(pPath);
 454       /* FIXME: Should this function delete the path even if it failed? */
 455
 456       return success;
 457    }
 458    else
 459       return FALSE;
 460 }
 461
 462
 463 /***********************************************************************
 464  * Exported functions
 465  */
 466
 467 /* PATH_InitGdiPath
 468  *
 469  * Initializes the GdiPath structure.
 470  */
 471 void PATH_InitGdiPath(GdiPath *pPath)
 472 {
 473    assert(pPath!=NULL);
 474
 475    pPath->state=PATH_Null;
 476    pPath->pPoints=NULL;
 477    pPath->pFlags=NULL;
 478    pPath->numEntriesUsed=0;
 479    pPath->numEntriesAllocated=0;
 480 }
 481
 482 /* PATH_DestroyGdiPath
 483  *
 484  * Destroys a GdiPath structure (frees the memory in the arrays).
 485  */
 486 void PATH_DestroyGdiPath(GdiPath *pPath)
 487 {
 488    assert(pPath!=NULL);
 489
 490    free(pPath->pPoints);
 491    free(pPath->pFlags);
 492 }
 493
 494 /* PATH_AssignGdiPath
 495  *
 496  * Copies the GdiPath structure "pPathSrc" to "pPathDest". A deep copy is
 497  * performed, i.e. the contents of the pPoints and pFlags arrays are copied,
 498  * not just the pointers. Since this means that the arrays in pPathDest may
 499  * need to be resized, pPathDest should have been initialized using
 500  * PATH_InitGdiPath (in C++, this function would be an assignment operator,
 501  * not a copy constructor).
 502  * Returns TRUE if successful, else FALSE.
 503  */
 504 BOOL32 PATH_AssignGdiPath(GdiPath *pPathDest, const GdiPath *pPathSrc)
 505 {
 506    assert(pPathDest!=NULL && pPathSrc!=NULL);
 507
 508    /* Make sure destination arrays are big enough */
 509    if(!PATH_ReserveEntries(pPathDest, pPathSrc->numEntriesUsed))
 510       return FALSE;
 511
 512    /* Perform the copy operation */
 513    memcpy(pPathDest->pPoints, pPathSrc->pPoints,
 514       sizeof(POINT32)*pPathSrc->numEntriesUsed);
 515    memcpy(pPathDest->pFlags, pPathSrc->pFlags,
 516       sizeof(INT32)*pPathSrc->numEntriesUsed);
 517    pPathDest->state=pPathSrc->state;
 518    pPathDest->numEntriesUsed=pPathSrc->numEntriesUsed;
 519    pPathDest->newStroke=pPathSrc->newStroke;
 520
 521    return TRUE;
 522 }
 523
 524 /* PATH_MoveTo
 525  *
 526  * Should be called when a MoveTo is performed on a DC that has an
 527  * open path. This starts a new stroke. Returns TRUE if successful, else
 528  * FALSE.
 529  */
 530 BOOL32 PATH_MoveTo(HDC32 hdc)
 531 {
 532    GdiPath *pPath;
 533
 534    /* Get pointer to path */
 535    if(!PATH_GetPathFromHDC(hdc, &pPath))
 536       return FALSE;
 537
 538    /* Check that path is open */
 539    if(pPath->state!=PATH_Open)
 540       /* FIXME: Do we have to call SetLastError? */
 541       return FALSE;
 542
 543    /* Start a new stroke */
 544    pPath->newStroke=TRUE;
 545
 546    return TRUE;
 547 }
 548
 549 /* PATH_LineTo
 550  *
 551  * Should be called when a LineTo is performed on a DC that has an
 552  * open path. This adds a PT_LINETO entry to the path (and possibly
 553  * a PT_MOVETO entry, if this is the first LineTo in a stroke).
 554  * Returns TRUE if successful, else FALSE.
 555  */
 556 BOOL32 PATH_LineTo(HDC32 hdc, INT32 x, INT32 y)
 557 {
 558    GdiPath *pPath;
 559    POINT32 point, pointCurPos;
 560
 561    /* Get pointer to path */
 562    if(!PATH_GetPathFromHDC(hdc, &pPath))
 563       return FALSE;
 564
 565    /* Check that path is open */
 566    if(pPath->state!=PATH_Open)
 567       /* FIXME: Do we have to call SetLastError? */
 568       return FALSE;
 569
 570    /* Convert point to device coordinates */
 571    point.x=x;
 572    point.y=y;
 573    if(!LPtoDP32(hdc, &point, 1))
 574       return FALSE;
 575
 576    /* Add a PT_MOVETO if necessary */
 577    if(pPath->newStroke)
 578    {
 579       pPath->newStroke=FALSE;
 580       if(!GetCurrentPositionEx32(hdc, &pointCurPos) ||
 581          !LPtoDP32(hdc, &pointCurPos, 1))
 582          return FALSE;
 583       if(!PATH_AddEntry(pPath, pointCurPos, PT_MOVETO))
 584          return FALSE;
 585    }
 586
 587    /* Add a PT_LINETO entry */
 588    return PATH_AddEntry(pPath, point, PT_LINETO);
 589 }
 590
 591 /* PATH_Ellipse
 592  *
 593  * Should be called when a call to Ellipse is performed on a DC that has
 594  * an open path. This adds four Bezier splines representing the ellipse
 595  * to the path. Returns TRUE if successful, else FALSE.
 596  */
 597 BOOL32 PATH_Ellipse(HDC32 hdc, INT32 x1, INT32 y1, INT32 x2, INT32 y2)
 598 {
 599    return PATH_Arc(hdc, x1, y1, x2, y2, x1, 0, x1, 0);
 600 }
 601
 602 /* PATH_Arc
 603  *
 604  * Should be called when a call to Arc is performed on a DC that has
 605  * an open path. This adds up to five Bezier splines representing the arc
 606  * to the path. Returns TRUE if successful, else FALSE.
 607  */
 608 BOOL32 PATH_Arc(HDC32 hdc, INT32 x1, INT32 y1, INT32 x2, INT32 y2,
 609    INT32 xStart, INT32 yStart, INT32 xEnd, INT32 yEnd)
 610 {
 611    GdiPath *pPath;
 612    double  angleStart, angleEnd, angleStartQuadrant, angleEndQuadrant=0.0;
 613            /* Initialize angleEndQuadrant to silence gcc's warning */
 614    double  x, y;
 615    POINT32 corners[2], pointStart, pointEnd;
 616    BOOL32  start, end;
 617    INT32   temp;
 618
 619    /* FIXME: This function should check for all possible error returns */
 620
 621    /* Get pointer to path */
 622    if(!PATH_GetPathFromHDC(hdc, &pPath))
 623       return FALSE;
 624
 625    /* Check that path is open */
 626    if(pPath->state!=PATH_Open)
 627       return FALSE;
 628
 629    /* Check for zero height / width */
 630    /* FIXME: Should we do this before or after LPtoDP? */
 631    if(x1==x2 || y1==y2)
 632       return TRUE;
 633
 634    /* In GM_COMPATIBLE, don't include bottom and right edges */
 635    if(GetGraphicsMode(hdc)==GM_COMPATIBLE)
 636    {
 637       /* FIXME: Should we do this before or after LPtoDP? */
 638       x2--;
 639       y2--;
 640    }
 641
 642    /* Convert points to device coordinates */
 643    corners[0].x=x1;
 644    corners[0].y=y1;
 645    corners[1].x=x2;
 646    corners[1].y=y2;
 647    pointStart.x=xStart;
 648    pointStart.y=yStart;
 649    pointEnd.x=xEnd;
 650    pointEnd.y=yEnd;
 651    if(!LPtoDP32(hdc, corners, 2) || !LPtoDP32(hdc, &pointStart, 1) ||
 652       !LPtoDP32(hdc, &pointEnd, 1))
 653       return FALSE;
 654
 655    /* Make sure first corner is top left and right corner is bottom right */
 656    /* FIXME: Should we do this before or after LPtoDP? */
 657    if(corners[0].x>corners[1].x)
 658    {
 659       temp=corners[0].x;
 660       corners[0].x=corners[1].x;
 661       corners[1].x=temp;
 662    }
 663    if(corners[0].y>corners[1].y)
 664    {
 665       temp=corners[0].y;
 666       corners[0].y=corners[1].y;
 667       corners[1].y=temp;
 668    }
 669
 670    /* Compute start and end angle */
 671    PATH_NormalizePoint(corners, &pointStart, &x, &y);
 672    angleStart=atan2(y, x);
 673    PATH_NormalizePoint(corners, &pointEnd, &x, &y);
 674    angleEnd=atan2(y, x);
 675
 676    /* Make sure the end angle is "on the right side" of the start angle */
 677    if(GetArcDirection32(hdc)==AD_CLOCKWISE)
 678    {
 679       if(angleEnd<=angleStart)
 680       {
 681          angleEnd+=2*M_PI;
 682          assert(angleEnd>=angleStart);
 683       }
 684    }
 685    else
 686    {
 687       if(angleEnd>=angleStart)
 688       {
 689          angleEnd-=2*M_PI;
 690          assert(angleEnd<=angleStart);
 691       }
 692    }
 693
 694    /* Add the arc to the path with one Bezier spline per quadrant that the
 695     * arc spans */
 696    start=TRUE;
 697    end=FALSE;
 698    do
 699    {
 700       /* Determine the start and end angles for this quadrant */
 701       if(start)
 702       {
 703          angleStartQuadrant=angleStart;
 704          if(GetArcDirection32(hdc)==AD_CLOCKWISE)
 705             angleEndQuadrant=(floor(angleStart/M_PI_2)+1.0)*M_PI_2;
 706          else
 707             angleEndQuadrant=(ceil(angleStart/M_PI_2)-1.0)*M_PI_2;
 708       }
 709       else
 710       {
 711          angleStartQuadrant=angleEndQuadrant;
 712          if(GetArcDirection32(hdc)==AD_CLOCKWISE)
 713             angleEndQuadrant+=M_PI_2;
 714          else
 715             angleEndQuadrant-=M_PI_2;
 716       }
 717
 718       /* Have we reached the last part of the arc? */
 719       if((GetArcDirection32(hdc)==AD_CLOCKWISE &&
 720          angleEnd<=angleEndQuadrant) ||
 721          (GetArcDirection32(hdc)==AD_COUNTERCLOCKWISE &&
 722          angleEnd>=angleEndQuadrant))
 723       {
 724          /* Adjust the end angle for this quadrant */
 725          angleEndQuadrant=angleEnd;
 726          end=TRUE;
 727       }
 728
 729       /* Add the Bezier spline to the path */
 730       PATH_DoArcPart(pPath, corners, angleStartQuadrant, angleEndQuadrant,
 731          start);
 732       start=FALSE;
 733    }  while(!end);
 734
 735    return TRUE;
 736 }
 737
 738 /***********************************************************************
 739  * Internal functions
 740  */
 741
 742 /* PATH_PathToRegion
 743  *
 744  * Creates a region from the specified path using the specified polygon
 745  * filling mode. The path is left unchanged. A handle to the region that
 746  * was created is stored in *pHrgn. If successful, TRUE is returned; if an
 747  * error occurs, SetLastError is called with the appropriate value and
 748  * FALSE is returned.
 749  */
 750 static BOOL32 PATH_PathToRegion(const GdiPath *pPath, INT32 nPolyFillMode,
 751    HRGN32 *pHrgn)
 752 {
 753    int    numStrokes, iStroke, i;
 754    INT32  *pNumPointsInStroke;
 755    HRGN32 hrgn;
 756
 757    assert(pPath!=NULL);
 758    assert(pHrgn!=NULL);
 759
 760    /* FIXME: What happens when number of points is zero? */
 761
 762    /* First pass: Find out how many strokes there are in the path */
 763    /* FIXME: We could eliminate this with some bookkeeping in GdiPath */
 764    numStrokes=0;
 765    for(i=0; i<pPath->numEntriesUsed; i++)
 766       if((pPath->pFlags[i] & ~PT_CLOSEFIGURE) == PT_MOVETO)
 767          numStrokes++;
 768
 769    /* Allocate memory for number-of-points-in-stroke array */
 770    pNumPointsInStroke=(int *)malloc(sizeof(int)*numStrokes);
 771    if(!pNumPointsInStroke)
 772    {
 773       SetLastError(ERROR_NOT_ENOUGH_MEMORY);
 774       return FALSE;
 775    }
 776
 777    /* Second pass: remember number of points in each polygon */
 778    iStroke=-1;  /* Will get incremented to 0 at beginning of first stroke */
 779    for(i=0; i<pPath->numEntriesUsed; i++)
 780    {
 781       /* Is this the beginning of a new stroke? */
 782       if((pPath->pFlags[i] & ~PT_CLOSEFIGURE) == PT_MOVETO)
 783       {
 784          iStroke++;
 785          pNumPointsInStroke[iStroke]=0;
 786       }
 787
 788       pNumPointsInStroke[iStroke]++;
 789    }
 790
 791    /* Create a region from the strokes */
 792    hrgn=CreatePolyPolygonRgn32(pPath->pPoints, pNumPointsInStroke,
 793       numStrokes, nPolyFillMode);
 794    if(hrgn==NULL)
 795    {
 796       SetLastError(ERROR_NOT_ENOUGH_MEMORY);
 797       return FALSE;
 798    }
 799
 800    /* Free memory for number-of-points-in-stroke array */
 801    free(pNumPointsInStroke);
 802
 803    /* Success! */
 804    *pHrgn=hrgn;
 805    return TRUE;
 806 }
 807
 808 /* PATH_EmptyPath
 809  *
 810  * Removes all entries from the path and sets the path state to PATH_Null.
 811  */
 812 static void PATH_EmptyPath(GdiPath *pPath)
 813 {
 814    assert(pPath!=NULL);
 815
 816    pPath->state=PATH_Null;
 817    pPath->numEntriesUsed=0;
 818 }
 819
 820 /* PATH_AddEntry
 821  *
 822  * Adds an entry to the path. For "flags", pass either PT_MOVETO, PT_LINETO
 823  * or PT_BEZIERTO, optionally ORed with PT_CLOSEFIGURE. Returns TRUE if
 824  * successful, FALSE otherwise (e.g. if not enough memory was available).
 825  */
 826 BOOL32 PATH_AddEntry(GdiPath *pPath, POINT32 point, BYTE flags)
 827 {
 828    assert(pPath!=NULL);
 829
 830    /* Check that path is open */
 831    if(pPath->state!=PATH_Open)
 832       return FALSE;
 833
 834    /* Reserve enough memory for an extra path entry */
 835    if(!PATH_ReserveEntries(pPath, pPath->numEntriesUsed+1))
 836       return FALSE;
 837
 838    /* Store information in path entry */
 839    pPath->pPoints[pPath->numEntriesUsed]=point;
 840    pPath->pFlags[pPath->numEntriesUsed]=flags;
 841
 842    /* Increment entry count */
 843    pPath->numEntriesUsed++;
 844
 845    return TRUE;
 846 }
 847
 848 /* PATH_ReserveEntries
 849  *
 850  * Ensures that at least "numEntries" entries (for points and flags) have
 851  * been allocated; allocates larger arrays and copies the existing entries
 852  * to those arrays, if necessary. Returns TRUE if successful, else FALSE.
 853  */
 854 static BOOL32 PATH_ReserveEntries(GdiPath *pPath, INT32 numEntries)
 855 {
 856    INT32   numEntriesToAllocate;
 857    POINT32 *pPointsNew;
 858    BYTE    *pFlagsNew;
 859
 860    assert(pPath!=NULL);
 861    assert(numEntries>=0);
 862
 863    /* Do we have to allocate more memory? */
 864    if(numEntries > pPath->numEntriesAllocated)
 865    {
 866       /* Find number of entries to allocate. We let the size of the array
 867        * grow exponentially, since that will guarantee linear time
 868        * complexity. */
 869       if(pPath->numEntriesAllocated)
 870       {
 871          numEntriesToAllocate=pPath->numEntriesAllocated;
 872          while(numEntriesToAllocate<numEntries)
 873             numEntriesToAllocate=numEntriesToAllocate*GROW_FACTOR_NUMER/
 874                GROW_FACTOR_DENOM;
 875       }
 876       else
 877          numEntriesToAllocate=NUM_ENTRIES_INITIAL;
 878
 879       /* Allocate new arrays */
 880       pPointsNew=(POINT32 *)malloc(numEntriesToAllocate * sizeof(POINT32));
 881       if(!pPointsNew)
 882          return FALSE;
 883       pFlagsNew=(BYTE *)malloc(numEntriesToAllocate * sizeof(BYTE));
 884       if(!pFlagsNew)
 885       {
 886          free(pPointsNew);
 887          return FALSE;
 888       }
 889
 890       /* Copy old arrays to new arrays and discard old arrays */
 891       if(pPath->pPoints)
 892       {
 893          assert(pPath->pFlags);
 894
 895          memcpy(pPointsNew, pPath->pPoints,
 896              sizeof(POINT32)*pPath->numEntriesUsed);
 897          memcpy(pFlagsNew, pPath->pFlags,
 898              sizeof(BYTE)*pPath->numEntriesUsed);
 899
 900          free(pPath->pPoints);
 901          free(pPath->pFlags);
 902       }
 903       pPath->pPoints=pPointsNew;
 904       pPath->pFlags=pFlagsNew;
 905       pPath->numEntriesAllocated=numEntriesToAllocate;
 906    }
 907
 908    return TRUE;
 909 }
 910
 911 /* PATH_GetPathFromHDC
 912  *
 913  * Retrieves a pointer to the GdiPath structure contained in an HDC and
 914  * places it in *ppPath. TRUE is returned if successful, FALSE otherwise.
 915  */
 916 static BOOL32 PATH_GetPathFromHDC(HDC32 hdc, GdiPath **ppPath)
 917 {
 918    DC *pDC;
 919
 920    pDC=DC_GetDCPtr(hdc);
 921    if(pDC)
 922    {
 923       *ppPath=&pDC->w.path;
 924       return TRUE;
 925    }
 926    else
 927       return FALSE;
 928 }
 929
 930 /* PATH_DoArcPart
 931  *
 932  * Creates a Bezier spline that corresponds to part of an arc and appends the
 933  * corresponding points to the path. The start and end angles are passed in
 934  * "angleStart" and "angleEnd"; these angles should span a quarter circle
 935  * at most. If "addMoveTo" is true, a PT_MOVETO entry for the first control
 936  * point is added to the path; otherwise, it is assumed that the current
 937  * position is equal to the first control point.
 938  */
 939 static BOOL32 PATH_DoArcPart(GdiPath *pPath, POINT32 corners[],
 940    double angleStart, double angleEnd, BOOL32 addMoveTo)
 941 {
 942    double  halfAngle, a;
 943    double  xNorm[4], yNorm[4];
 944    POINT32 point;
 945    int     i;
 946
 947    assert(fabs(angleEnd-angleStart)<=M_PI_2);
 948
 949    /* FIXME: Is there an easier way of computing this? */
 950
 951    /* Compute control points */
 952    halfAngle=(angleEnd-angleStart)/2.0;
 953    a=4.0/3.0*(1-cos(halfAngle))/sin(halfAngle);
 954    xNorm[0]=cos(angleStart);
 955    yNorm[0]=sin(angleStart);
 956    xNorm[1]=xNorm[0] - a*yNorm[0];
 957    yNorm[1]=yNorm[0] + a*xNorm[0];
 958    xNorm[3]=cos(angleEnd);
 959    yNorm[3]=sin(angleEnd);
 960    xNorm[2]=xNorm[3] + a*yNorm[3];
 961    yNorm[2]=yNorm[3] - a*xNorm[3];
 962
 963    /* Add starting point to path if desired */
 964    if(addMoveTo)
 965    {
 966       PATH_ScaleNormalizedPoint(corners, xNorm[0], yNorm[0], &point);
 967       if(!PATH_AddEntry(pPath, point, PT_MOVETO))
 968          return FALSE;
 969    }
 970
 971    /* Add remaining control points */
 972    for(i=1; i<4; i++)
 973    {
 974       PATH_ScaleNormalizedPoint(corners, xNorm[i], yNorm[i], &point);
 975       if(!PATH_AddEntry(pPath, point, PT_BEZIERTO))
 976          return FALSE;
 977    }
 978
 979    return TRUE;
 980 }
 981
 982 /* PATH_ScaleNormalizedPoint
 983  *
 984  * Scales a normalized point (x, y) with respect to the box whose corners are
 985  * passed in "corners". The point is stored in "*pPoint". The normalized
 986  * coordinates (-1.0, -1.0) correspond to corners[0], the coordinates
 987  * (1.0, 1.0) correspond to corners[1].
 988  */
 989 static void PATH_ScaleNormalizedPoint(POINT32 corners[], double x, double y,
 990    POINT32 *pPoint)
 991 {
 992    pPoint->x=(INT32)floor( (double)corners[0].x +
 993       (double)(corners[1].x-corners[0].x)*0.5*(x+1.0) );
 994    pPoint->y=(INT32)floor( (double)corners[0].y +
 995       (double)(corners[1].y-corners[0].y)*0.5*(y+1.0) );
 996 }
 997
 998 /* PATH_NormalizePoint
 999  *
1000  * Normalizes a point with respect to the box whose corners are passed in
1001  * "corners". The normalized coordinates are stored in "*pX" and "*pY".
1002  */
1003 static void PATH_NormalizePoint(POINT32 corners[], const POINT32 *pPoint,
1004    double *pX, double *pY)
1005 {
1006    *pX=(double)(pPoint->x-corners[0].x)/(double)(corners[1].x-corners[0].x) *
1007       2.0 - 1.0;
1008    *pY=(double)(pPoint->y-corners[0].y)/(double)(corners[1].y-corners[0].y) *
1009       2.0 - 1.0;
1010 }