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