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