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