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 "debug.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(gdi, "(%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 /***********************************************************************
 304  *           PathToRegion32    (GDI32.261)
 305  *
 306  * FIXME
 307  *   Check that SetLastError is being called correctly
 308  *
 309  * The documentation does not state this explicitly, but a test under Windows
 310  * shows that the region which is returned should be in device coordinates.
 311  */
 312 HRGN WINAPI PathToRegion(HDC hdc)
 313 {
 314    GdiPath *pPath;
 315    HRGN  hrgnRval;
 316
 317    /* Get pointer to path */
 318    if(!PATH_GetPathFromHDC(hdc, &pPath))
 319    {
 320       SetLastError(ERROR_INVALID_PARAMETER);
 321       return 0;
 322    }
 323
 324    /* Check that path is closed */
 325    if(pPath->state!=PATH_Closed)
 326    {
 327       SetLastError(ERROR_CAN_NOT_COMPLETE);
 328       return 0;
 329    }
 330
 331    /* FIXME: Should we empty the path even if conversion failed? */
 332    if(PATH_PathToRegion(pPath, GetPolyFillMode(hdc), &hrgnRval))
 333       PATH_EmptyPath(pPath);
 334    else
 335       hrgnRval=0;
 336
 337    return hrgnRval;
 338 }
 339
 340
 341 /***********************************************************************
 342  *           FillPath32    (GDI32.100)
 343  *
 344  * FIXME
 345  *    Check that SetLastError is being called correctly
 346  */
 347 BOOL WINAPI FillPath(HDC hdc)
 348 {
 349    GdiPath *pPath;
 350    INT   mapMode, graphicsMode;
 351    SIZE  ptViewportExt, ptWindowExt;
 352    POINT ptViewportOrg, ptWindowOrg;
 353    XFORM   xform;
 354    HRGN  hrgn;
 355
 356    /* Get pointer to path */
 357    if(!PATH_GetPathFromHDC(hdc, &pPath))
 358    {
 359       SetLastError(ERROR_INVALID_PARAMETER);
 360       return FALSE;
 361    }
 362
 363    /* Check that path is closed */
 364    if(pPath->state!=PATH_Closed)
 365    {
 366       SetLastError(ERROR_CAN_NOT_COMPLETE);
 367       return FALSE;
 368    }
 369
 370    /* Construct a region from the path and fill it */
 371    if(PATH_PathToRegion(pPath, GetPolyFillMode(hdc), &hrgn))
 372    {
 373       /* Since PaintRgn interprets the region as being in logical coordinates
 374        * but the points we store for the path are already in device
 375        * coordinates, we have to set the mapping mode to MM_TEXT temporarily.
 376        * Using SaveDC to save information about the mapping mode / world
 377        * transform would be easier but would require more overhead, especially
 378        * now that SaveDC saves the current path.
 379        */
 380
 381       /* Save the information about the old mapping mode */
 382       mapMode=GetMapMode(hdc);
 383       GetViewportExtEx(hdc, &ptViewportExt);
 384       GetViewportOrgEx(hdc, &ptViewportOrg);
 385       GetWindowExtEx(hdc, &ptWindowExt);
 386       GetWindowOrgEx(hdc, &ptWindowOrg);
 387
 388       /* Save world transform
 389        * NB: The Windows documentation on world transforms would lead one to
 390        * believe that this has to be done only in GM_ADVANCED; however, my
 391        * tests show that resetting the graphics mode to GM_COMPATIBLE does
 392        * not reset the world transform.
 393        */
 394       GetWorldTransform(hdc, &xform);
 395
 396       /* Set MM_TEXT */
 397       SetMapMode(hdc, MM_TEXT);
 398
 399       /* Paint the region */
 400       PaintRgn(hdc, hrgn);
 401
 402       /* Restore the old mapping mode */
 403       SetMapMode(hdc, mapMode);
 404       SetViewportExtEx(hdc, ptViewportExt.cx, ptViewportExt.cy, NULL);
 405       SetViewportOrgEx(hdc, ptViewportOrg.x, ptViewportOrg.y, NULL);
 406       SetWindowExtEx(hdc, ptWindowExt.cx, ptWindowExt.cy, NULL);
 407       SetWindowOrgEx(hdc, ptWindowOrg.x, ptWindowOrg.y, NULL);
 408
 409       /* Go to GM_ADVANCED temporarily to restore the world transform */
 410       graphicsMode=GetGraphicsMode(hdc);
 411       SetGraphicsMode(hdc, GM_ADVANCED);
 412       SetWorldTransform(hdc, &xform);
 413       SetGraphicsMode(hdc, graphicsMode);
 414
 415       /* Empty the path */
 416       PATH_EmptyPath(pPath);
 417       return TRUE;
 418    }
 419    else
 420    {
 421       /* FIXME: Should the path be emptied even if conversion failed? */
 422       /* PATH_EmptyPath(pPath); */
 423       return FALSE;
 424    }
 425 }
 426
 427
 428 /***********************************************************************
 429  *           SelectClipPath32    (GDI32.296)
 430  * FIXME
 431  *  Check that SetLastError is being called correctly
 432  */
 433 BOOL WINAPI SelectClipPath(HDC hdc, INT iMode)
 434 {
 435    GdiPath *pPath;
 436    HRGN  hrgnPath;
 437    BOOL  success;
 438
 439    /* Get pointer to path */
 440    if(!PATH_GetPathFromHDC(hdc, &pPath))
 441    {
 442       SetLastError(ERROR_INVALID_PARAMETER);
 443       return FALSE;
 444    }
 445
 446    /* Check that path is closed */
 447    if(pPath->state!=PATH_Closed)
 448    {
 449       SetLastError(ERROR_CAN_NOT_COMPLETE);
 450       return FALSE;
 451    }
 452
 453    /* Construct a region from the path */
 454    if(PATH_PathToRegion(pPath, GetPolyFillMode(hdc), &hrgnPath))
 455    {
 456       success = ExtSelectClipRgn( hdc, hrgnPath, iMode ) != ERROR;
 457       DeleteObject(hrgnPath);
 458
 459       /* Empty the path */
 460       if(success)
 461          PATH_EmptyPath(pPath);
 462       /* FIXME: Should this function delete the path even if it failed? */
 463
 464       return success;
 465    }
 466    else
 467       return FALSE;
 468 }
 469
 470
 471 /***********************************************************************
 472  * Exported functions
 473  */
 474
 475 /* PATH_InitGdiPath
 476  *
 477  * Initializes the GdiPath structure.
 478  */
 479 void PATH_InitGdiPath(GdiPath *pPath)
 480 {
 481    assert(pPath!=NULL);
 482
 483    pPath->state=PATH_Null;
 484    pPath->pPoints=NULL;
 485    pPath->pFlags=NULL;
 486    pPath->numEntriesUsed=0;
 487    pPath->numEntriesAllocated=0;
 488 }
 489
 490 /* PATH_DestroyGdiPath
 491  *
 492  * Destroys a GdiPath structure (frees the memory in the arrays).
 493  */
 494 void PATH_DestroyGdiPath(GdiPath *pPath)
 495 {
 496    assert(pPath!=NULL);
 497
 498    free(pPath->pPoints);
 499    free(pPath->pFlags);
 500 }
 501
 502 /* PATH_AssignGdiPath
 503  *
 504  * Copies the GdiPath structure "pPathSrc" to "pPathDest". A deep copy is
 505  * performed, i.e. the contents of the pPoints and pFlags arrays are copied,
 506  * not just the pointers. Since this means that the arrays in pPathDest may
 507  * need to be resized, pPathDest should have been initialized using
 508  * PATH_InitGdiPath (in C++, this function would be an assignment operator,
 509  * not a copy constructor).
 510  * Returns TRUE if successful, else FALSE.
 511  */
 512 BOOL PATH_AssignGdiPath(GdiPath *pPathDest, const GdiPath *pPathSrc)
 513 {
 514    assert(pPathDest!=NULL && pPathSrc!=NULL);
 515
 516    /* Make sure destination arrays are big enough */
 517    if(!PATH_ReserveEntries(pPathDest, pPathSrc->numEntriesUsed))
 518       return FALSE;
 519
 520    /* Perform the copy operation */
 521    memcpy(pPathDest->pPoints, pPathSrc->pPoints,
 522       sizeof(POINT)*pPathSrc->numEntriesUsed);
 523    memcpy(pPathDest->pFlags, pPathSrc->pFlags,
 524       sizeof(INT)*pPathSrc->numEntriesUsed);
 525    pPathDest->state=pPathSrc->state;
 526    pPathDest->numEntriesUsed=pPathSrc->numEntriesUsed;
 527    pPathDest->newStroke=pPathSrc->newStroke;
 528
 529    return TRUE;
 530 }
 531
 532 /* PATH_MoveTo
 533  *
 534  * Should be called when a MoveTo is performed on a DC that has an
 535  * open path. This starts a new stroke. Returns TRUE if successful, else
 536  * FALSE.
 537  */
 538 BOOL PATH_MoveTo(HDC hdc)
 539 {
 540    GdiPath *pPath;
 541
 542    /* Get pointer to path */
 543    if(!PATH_GetPathFromHDC(hdc, &pPath))
 544       return FALSE;
 545
 546    /* Check that path is open */
 547    if(pPath->state!=PATH_Open)
 548       /* FIXME: Do we have to call SetLastError? */
 549       return FALSE;
 550
 551    /* Start a new stroke */
 552    pPath->newStroke=TRUE;
 553
 554    return TRUE;
 555 }
 556
 557 /* PATH_LineTo
 558  *
 559  * Should be called when a LineTo is performed on a DC that has an
 560  * open path. This adds a PT_LINETO entry to the path (and possibly
 561  * a PT_MOVETO entry, if this is the first LineTo in a stroke).
 562  * Returns TRUE if successful, else FALSE.
 563  */
 564 BOOL PATH_LineTo(HDC hdc, INT x, INT y)
 565 {
 566    GdiPath *pPath;
 567    POINT point, pointCurPos;
 568
 569    /* Get pointer to path */
 570    if(!PATH_GetPathFromHDC(hdc, &pPath))
 571       return FALSE;
 572
 573    /* Check that path is open */
 574    if(pPath->state!=PATH_Open)
 575       return FALSE;
 576
 577    /* Convert point to device coordinates */
 578    point.x=x;
 579    point.y=y;
 580    if(!LPtoDP(hdc, &point, 1))
 581       return FALSE;
 582
 583    /* Add a PT_MOVETO if necessary */
 584    if(pPath->newStroke)
 585    {
 586       pPath->newStroke=FALSE;
 587       if(!GetCurrentPositionEx(hdc, &pointCurPos) ||
 588          !LPtoDP(hdc, &pointCurPos, 1))
 589          return FALSE;
 590       if(!PATH_AddEntry(pPath, &pointCurPos, PT_MOVETO))
 591          return FALSE;
 592    }
 593
 594    /* Add a PT_LINETO entry */
 595    return PATH_AddEntry(pPath, &point, PT_LINETO);
 596 }
 597
 598 /* PATH_Rectangle
 599  *
 600  * Should be called when a call to Rectangle is performed on a DC that has
 601  * an open path. Returns TRUE if successful, else FALSE.
 602  */
 603 BOOL PATH_Rectangle(HDC hdc, INT x1, INT y1, INT x2, INT y2)
 604 {
 605    GdiPath *pPath;
 606    POINT corners[2], pointTemp;
 607    INT   temp;
 608
 609    /* Get pointer to path */
 610    if(!PATH_GetPathFromHDC(hdc, &pPath))
 611       return FALSE;
 612
 613    /* Check that path is open */
 614    if(pPath->state!=PATH_Open)
 615       return FALSE;
 616
 617    /* Convert points to device coordinates */
 618    corners[0].x=x1;
 619    corners[0].y=y1;
 620    corners[1].x=x2;
 621    corners[1].y=y2;
 622    if(!LPtoDP(hdc, corners, 2))
 623       return FALSE;
 624
 625    /* Make sure first corner is top left and second corner is bottom right */
 626    if(corners[0].x>corners[1].x)
 627    {
 628       temp=corners[0].x;
 629       corners[0].x=corners[1].x;
 630       corners[1].x=temp;
 631    }
 632    if(corners[0].y>corners[1].y)
 633    {
 634       temp=corners[0].y;
 635       corners[0].y=corners[1].y;
 636       corners[1].y=temp;
 637    }
 638
 639    /* In GM_COMPATIBLE, don't include bottom and right edges */
 640    if(GetGraphicsMode(hdc)==GM_COMPATIBLE)
 641    {
 642       corners[1].x--;
 643       corners[1].y--;
 644    }
 645
 646    /* Close any previous figure */
 647    if(!CloseFigure(hdc))
 648    {
 649       /* The CloseFigure call shouldn't have failed */
 650       assert(FALSE);
 651       return FALSE;
 652    }
 653
 654    /* Add four points to the path */
 655    pointTemp.x=corners[1].x;
 656    pointTemp.y=corners[0].y;
 657    if(!PATH_AddEntry(pPath, &pointTemp, PT_MOVETO))
 658       return FALSE;
 659    if(!PATH_AddEntry(pPath, corners, PT_LINETO))
 660       return FALSE;
 661    pointTemp.x=corners[0].x;
 662    pointTemp.y=corners[1].y;
 663    if(!PATH_AddEntry(pPath, &pointTemp, PT_LINETO))
 664       return FALSE;
 665    if(!PATH_AddEntry(pPath, corners+1, PT_LINETO))
 666       return FALSE;
 667
 668    /* Close the rectangle figure */
 669    if(!CloseFigure(hdc))
 670    {
 671       /* The CloseFigure call shouldn't have failed */
 672       assert(FALSE);
 673       return FALSE;
 674    }
 675
 676    return TRUE;
 677 }
 678
 679 /* PATH_Ellipse
 680  *
 681  * Should be called when a call to Ellipse is performed on a DC that has
 682  * an open path. This adds four Bezier splines representing the ellipse
 683  * to the path. Returns TRUE if successful, else FALSE.
 684  */
 685 BOOL PATH_Ellipse(HDC hdc, INT x1, INT y1, INT x2, INT y2)
 686 {
 687    /* TODO: This should probably be revised to call PATH_AngleArc */
 688    /* (once it exists) */
 689    return PATH_Arc(hdc, x1, y1, x2, y2, x1, (y1+y2)/2, x1, (y1+y2)/2);
 690 }
 691
 692 /* PATH_Arc
 693  *
 694  * Should be called when a call to Arc is performed on a DC that has
 695  * an open path. This adds up to five Bezier splines representing the arc
 696  * to the path. Returns TRUE if successful, else FALSE.
 697  */
 698 BOOL PATH_Arc(HDC hdc, INT x1, INT y1, INT x2, INT y2,
 699    INT xStart, INT yStart, INT xEnd, INT yEnd)
 700 {
 701    GdiPath     *pPath;
 702    DC          *pDC;
 703    double      angleStart, angleEnd, angleStartQuadrant, angleEndQuadrant=0.0;
 704                /* Initialize angleEndQuadrant to silence gcc's warning */
 705    double      x, y;
 706    FLOAT_POINT corners[2], pointStart, pointEnd;
 707    BOOL      start, end;
 708    INT       temp;
 709
 710    /* FIXME: This function should check for all possible error returns */
 711    /* FIXME: Do we have to respect newStroke? */
 712
 713    /* Get pointer to DC */
 714    pDC=DC_GetDCPtr(hdc);
 715    if(pDC==NULL)
 716       return FALSE;
 717
 718    /* Get pointer to path */
 719    if(!PATH_GetPathFromHDC(hdc, &pPath))
 720       return FALSE;
 721
 722    /* Check that path is open */
 723    if(pPath->state!=PATH_Open)
 724       return FALSE;
 725
 726    /* FIXME: Do we have to close the current figure? */
 727
 728    /* Check for zero height / width */
 729    /* FIXME: Only in GM_COMPATIBLE? */
 730    if(x1==x2 || y1==y2)
 731       return TRUE;
 732
 733    /* Convert points to device coordinates */
 734    corners[0].x=(FLOAT)x1;
 735    corners[0].y=(FLOAT)y1;
 736    corners[1].x=(FLOAT)x2;
 737    corners[1].y=(FLOAT)y2;
 738    pointStart.x=(FLOAT)xStart;
 739    pointStart.y=(FLOAT)yStart;
 740    pointEnd.x=(FLOAT)xEnd;
 741    pointEnd.y=(FLOAT)yEnd;
 742    INTERNAL_LPTODP_FLOAT(pDC, corners);
 743    INTERNAL_LPTODP_FLOAT(pDC, corners+1);
 744    INTERNAL_LPTODP_FLOAT(pDC, &pointStart);
 745    INTERNAL_LPTODP_FLOAT(pDC, &pointEnd);
 746
 747    /* Make sure first corner is top left and second corner is bottom right */
 748    if(corners[0].x>corners[1].x)
 749    {
 750       temp=corners[0].x;
 751       corners[0].x=corners[1].x;
 752       corners[1].x=temp;
 753    }
 754    if(corners[0].y>corners[1].y)
 755    {
 756       temp=corners[0].y;
 757       corners[0].y=corners[1].y;
 758       corners[1].y=temp;
 759    }
 760
 761    /* Compute start and end angle */
 762    PATH_NormalizePoint(corners, &pointStart, &x, &y);
 763    angleStart=atan2(y, x);
 764    PATH_NormalizePoint(corners, &pointEnd, &x, &y);
 765    angleEnd=atan2(y, x);
 766
 767    /* Make sure the end angle is "on the right side" of the start angle */
 768    if(GetArcDirection(hdc)==AD_CLOCKWISE)
 769    {
 770       if(angleEnd<=angleStart)
 771       {
 772          angleEnd+=2*M_PI;
 773          assert(angleEnd>=angleStart);
 774       }
 775    }
 776    else
 777    {
 778       if(angleEnd>=angleStart)
 779       {
 780          angleEnd-=2*M_PI;
 781          assert(angleEnd<=angleStart);
 782       }
 783    }
 784
 785    /* In GM_COMPATIBLE, don't include bottom and right edges */
 786    if(GetGraphicsMode(hdc)==GM_COMPATIBLE)
 787    {
 788       corners[1].x--;
 789       corners[1].y--;
 790    }
 791
 792    /* Add the arc to the path with one Bezier spline per quadrant that the
 793     * arc spans */
 794    start=TRUE;
 795    end=FALSE;
 796    do
 797    {
 798       /* Determine the start and end angles for this quadrant */
 799       if(start)
 800       {
 801          angleStartQuadrant=angleStart;
 802          if(GetArcDirection(hdc)==AD_CLOCKWISE)
 803             angleEndQuadrant=(floor(angleStart/M_PI_2)+1.0)*M_PI_2;
 804          else
 805             angleEndQuadrant=(ceil(angleStart/M_PI_2)-1.0)*M_PI_2;
 806       }
 807       else
 808       {
 809          angleStartQuadrant=angleEndQuadrant;
 810          if(GetArcDirection(hdc)==AD_CLOCKWISE)
 811             angleEndQuadrant+=M_PI_2;
 812          else
 813             angleEndQuadrant-=M_PI_2;
 814       }
 815
 816       /* Have we reached the last part of the arc? */
 817       if((GetArcDirection(hdc)==AD_CLOCKWISE &&
 818          angleEnd<angleEndQuadrant) ||
 819          (GetArcDirection(hdc)==AD_COUNTERCLOCKWISE &&
 820          angleEnd>angleEndQuadrant))
 821       {
 822          /* Adjust the end angle for this quadrant */
 823          angleEndQuadrant=angleEnd;
 824          end=TRUE;
 825       }
 826
 827       /* Add the Bezier spline to the path */
 828       PATH_DoArcPart(pPath, corners, angleStartQuadrant, angleEndQuadrant,
 829          start);
 830       start=FALSE;
 831    }  while(!end);
 832
 833    return TRUE;
 834 }
 835
 836 /***********************************************************************
 837  * Internal functions
 838  */
 839
 840 /* PATH_PathToRegion
 841  *
 842  * Creates a region from the specified path using the specified polygon
 843  * filling mode. The path is left unchanged. A handle to the region that
 844  * was created is stored in *pHrgn. If successful, TRUE is returned; if an
 845  * error occurs, SetLastError is called with the appropriate value and
 846  * FALSE is returned.
 847  */
 848 static BOOL PATH_PathToRegion(const GdiPath *pPath, INT nPolyFillMode,
 849    HRGN *pHrgn)
 850 {
 851    int    numStrokes, iStroke, i;
 852    INT  *pNumPointsInStroke;
 853    HRGN hrgn;
 854
 855    assert(pPath!=NULL);
 856    assert(pHrgn!=NULL);
 857
 858    /* FIXME: What happens when number of points is zero? */
 859
 860    /* First pass: Find out how many strokes there are in the path */
 861    /* FIXME: We could eliminate this with some bookkeeping in GdiPath */
 862    numStrokes=0;
 863    for(i=0; i<pPath->numEntriesUsed; i++)
 864       if((pPath->pFlags[i] & ~PT_CLOSEFIGURE) == PT_MOVETO)
 865          numStrokes++;
 866
 867    /* Allocate memory for number-of-points-in-stroke array */
 868    pNumPointsInStroke=(int *)malloc(sizeof(int)*numStrokes);
 869    if(!pNumPointsInStroke)
 870    {
 871       SetLastError(ERROR_NOT_ENOUGH_MEMORY);
 872       return FALSE;
 873    }
 874
 875    /* Second pass: remember number of points in each polygon */
 876    iStroke=-1;  /* Will get incremented to 0 at beginning of first stroke */
 877    for(i=0; i<pPath->numEntriesUsed; i++)
 878    {
 879       /* Is this the beginning of a new stroke? */
 880       if((pPath->pFlags[i] & ~PT_CLOSEFIGURE) == PT_MOVETO)
 881       {
 882          iStroke++;
 883          pNumPointsInStroke[iStroke]=0;
 884       }
 885
 886       pNumPointsInStroke[iStroke]++;
 887    }
 888
 889    /* Create a region from the strokes */
 890    hrgn=CreatePolyPolygonRgn(pPath->pPoints, pNumPointsInStroke,
 891       numStrokes, nPolyFillMode);
 892    if(hrgn==(HRGN)0)
 893    {
 894       SetLastError(ERROR_NOT_ENOUGH_MEMORY);
 895       return FALSE;
 896    }
 897
 898    /* Free memory for number-of-points-in-stroke array */
 899    free(pNumPointsInStroke);
 900
 901    /* Success! */
 902    *pHrgn=hrgn;
 903    return TRUE;
 904 }
 905
 906 /* PATH_EmptyPath
 907  *
 908  * Removes all entries from the path and sets the path state to PATH_Null.
 909  */
 910 static void PATH_EmptyPath(GdiPath *pPath)
 911 {
 912    assert(pPath!=NULL);
 913
 914    pPath->state=PATH_Null;
 915    pPath->numEntriesUsed=0;
 916 }
 917
 918 /* PATH_AddEntry
 919  *
 920  * Adds an entry to the path. For "flags", pass either PT_MOVETO, PT_LINETO
 921  * or PT_BEZIERTO, optionally ORed with PT_CLOSEFIGURE. Returns TRUE if
 922  * successful, FALSE otherwise (e.g. if not enough memory was available).
 923  */
 924 BOOL PATH_AddEntry(GdiPath *pPath, const POINT *pPoint, BYTE flags)
 925 {
 926    assert(pPath!=NULL);
 927
 928    /* FIXME: If newStroke is true, perhaps we want to check that we're
 929     * getting a PT_MOVETO
 930     */
 931
 932    /* Check that path is open */
 933    if(pPath->state!=PATH_Open)
 934       return FALSE;
 935
 936    /* Reserve enough memory for an extra path entry */
 937    if(!PATH_ReserveEntries(pPath, pPath->numEntriesUsed+1))
 938       return FALSE;
 939
 940    /* Store information in path entry */
 941    pPath->pPoints[pPath->numEntriesUsed]=*pPoint;
 942    pPath->pFlags[pPath->numEntriesUsed]=flags;
 943
 944    /* If this is PT_CLOSEFIGURE, we have to start a new stroke next time */
 945    if((flags & PT_CLOSEFIGURE) == PT_CLOSEFIGURE)
 946       pPath->newStroke=TRUE;
 947
 948    /* Increment entry count */
 949    pPath->numEntriesUsed++;
 950
 951    return TRUE;
 952 }
 953
 954 /* PATH_ReserveEntries
 955  *
 956  * Ensures that at least "numEntries" entries (for points and flags) have
 957  * been allocated; allocates larger arrays and copies the existing entries
 958  * to those arrays, if necessary. Returns TRUE if successful, else FALSE.
 959  */
 960 static BOOL PATH_ReserveEntries(GdiPath *pPath, INT numEntries)
 961 {
 962    INT   numEntriesToAllocate;
 963    POINT *pPointsNew;
 964    BYTE    *pFlagsNew;
 965
 966    assert(pPath!=NULL);
 967    assert(numEntries>=0);
 968
 969    /* Do we have to allocate more memory? */
 970    if(numEntries > pPath->numEntriesAllocated)
 971    {
 972       /* Find number of entries to allocate. We let the size of the array
 973        * grow exponentially, since that will guarantee linear time
 974        * complexity. */
 975       if(pPath->numEntriesAllocated)
 976       {
 977          numEntriesToAllocate=pPath->numEntriesAllocated;
 978          while(numEntriesToAllocate<numEntries)
 979             numEntriesToAllocate=numEntriesToAllocate*GROW_FACTOR_NUMER/
 980                GROW_FACTOR_DENOM;
 981       }
 982       else
 983          numEntriesToAllocate=NUM_ENTRIES_INITIAL;
 984
 985       /* Allocate new arrays */
 986       pPointsNew=(POINT *)malloc(numEntriesToAllocate * sizeof(POINT));
 987       if(!pPointsNew)
 988          return FALSE;
 989       pFlagsNew=(BYTE *)malloc(numEntriesToAllocate * sizeof(BYTE));
 990       if(!pFlagsNew)
 991       {
 992          free(pPointsNew);
 993          return FALSE;
 994       }
 995
 996       /* Copy old arrays to new arrays and discard old arrays */
 997       if(pPath->pPoints)
 998       {
 999          assert(pPath->pFlags);
1000
1001          memcpy(pPointsNew, pPath->pPoints,
1002              sizeof(POINT)*pPath->numEntriesUsed);
1003          memcpy(pFlagsNew, pPath->pFlags,
1004              sizeof(BYTE)*pPath->numEntriesUsed);
1005
1006          free(pPath->pPoints);
1007          free(pPath->pFlags);
1008       }
1009       pPath->pPoints=pPointsNew;
1010       pPath->pFlags=pFlagsNew;
1011       pPath->numEntriesAllocated=numEntriesToAllocate;
1012    }
1013
1014    return TRUE;
1015 }
1016
1017 /* PATH_GetPathFromHDC
1018  *
1019  * Retrieves a pointer to the GdiPath structure contained in an HDC and
1020  * places it in *ppPath. TRUE is returned if successful, FALSE otherwise.
1021  */
1022 static BOOL PATH_GetPathFromHDC(HDC hdc, GdiPath **ppPath)
1023 {
1024    DC *pDC;
1025
1026    pDC=DC_GetDCPtr(hdc);
1027    if(pDC)
1028    {
1029       *ppPath=&pDC->w.path;
1030       return TRUE;
1031    }
1032    else
1033       return FALSE;
1034 }
1035
1036 /* PATH_DoArcPart
1037  *
1038  * Creates a Bezier spline that corresponds to part of an arc and appends the
1039  * corresponding points to the path. The start and end angles are passed in
1040  * "angleStart" and "angleEnd"; these angles should span a quarter circle
1041  * at most. If "addMoveTo" is true, a PT_MOVETO entry for the first control
1042  * point is added to the path; otherwise, it is assumed that the current
1043  * position is equal to the first control point.
1044  */
1045 static BOOL PATH_DoArcPart(GdiPath *pPath, FLOAT_POINT corners[],
1046    double angleStart, double angleEnd, BOOL addMoveTo)
1047 {
1048    double  halfAngle, a;
1049    double  xNorm[4], yNorm[4];
1050    POINT point;
1051    int     i;
1052
1053    assert(fabs(angleEnd-angleStart)<=M_PI_2);
1054
1055    /* FIXME: Is there an easier way of computing this? */
1056
1057    /* Compute control points */
1058    halfAngle=(angleEnd-angleStart)/2.0;
1059    if(fabs(halfAngle)>1e-8)
1060    {
1061       a=4.0/3.0*(1-cos(halfAngle))/sin(halfAngle);
1062       xNorm[0]=cos(angleStart);
1063       yNorm[0]=sin(angleStart);
1064       xNorm[1]=xNorm[0] - a*yNorm[0];
1065       yNorm[1]=yNorm[0] + a*xNorm[0];
1066       xNorm[3]=cos(angleEnd);
1067       yNorm[3]=sin(angleEnd);
1068       xNorm[2]=xNorm[3] + a*yNorm[3];
1069       yNorm[2]=yNorm[3] - a*xNorm[3];
1070    }
1071    else
1072       for(i=0; i<4; i++)
1073       {
1074          xNorm[i]=cos(angleStart);
1075          yNorm[i]=sin(angleStart);
1076       }
1077
1078    /* Add starting point to path if desired */
1079    if(addMoveTo)
1080    {
1081       PATH_ScaleNormalizedPoint(corners, xNorm[0], yNorm[0], &point);
1082       if(!PATH_AddEntry(pPath, &point, PT_MOVETO))
1083          return FALSE;
1084    }
1085
1086    /* Add remaining control points */
1087    for(i=1; i<4; i++)
1088    {
1089       PATH_ScaleNormalizedPoint(corners, xNorm[i], yNorm[i], &point);
1090       if(!PATH_AddEntry(pPath, &point, PT_BEZIERTO))
1091          return FALSE;
1092    }
1093
1094    return TRUE;
1095 }
1096
1097 /* PATH_ScaleNormalizedPoint
1098  *
1099  * Scales a normalized point (x, y) with respect to the box whose corners are
1100  * passed in "corners". The point is stored in "*pPoint". The normalized
1101  * coordinates (-1.0, -1.0) correspond to corners[0], the coordinates
1102  * (1.0, 1.0) correspond to corners[1].
1103  */
1104 static void PATH_ScaleNormalizedPoint(FLOAT_POINT corners[], double x,
1105    double y, POINT *pPoint)
1106 {
1107    pPoint->x=GDI_ROUND( (double)corners[0].x +
1108       (double)(corners[1].x-corners[0].x)*0.5*(x+1.0) );
1109    pPoint->y=GDI_ROUND( (double)corners[0].y +
1110       (double)(corners[1].y-corners[0].y)*0.5*(y+1.0) );
1111 }
1112
1113 /* PATH_NormalizePoint
1114  *
1115  * Normalizes a point with respect to the box whose corners are passed in
1116  * "corners". The normalized coordinates are stored in "*pX" and "*pY".
1117  */
1118 static void PATH_NormalizePoint(FLOAT_POINT corners[],
1119    const FLOAT_POINT *pPoint,
1120    double *pX, double *pY)
1121 {
1122    *pX=(double)(pPoint->x-corners[0].x)/(double)(corners[1].x-corners[0].x) *
1123       2.0 - 1.0;
1124    *pY=(double)(pPoint->y-corners[0].y)/(double)(corners[1].y-corners[0].y) *
1125       2.0 - 1.0;
1126 }
1127
1128 /*******************************************************************
1129  *      FlattenPath32 [GDI32.103]
1130  *
1131  *
1132  */
1133 BOOL WINAPI FlattenPath(HDC hdc)
1134 {
1135         FIXME(gdi, "FlattenPath, stub\n");
1136         return 0;
1137 }
1138
1139 /*******************************************************************
1140  *      StrokeAndFillPath [GDI32.352]
1141  *
1142  *
1143  */
1144 BOOL WINAPI StrokeAndFillPath(HDC hdc)
1145 {
1146         FIXME(gdi, "StrokeAndFillPath, stub\n");
1147         return 0;
1148 }
1149
1150 /*******************************************************************
1151  *      StrokePath [GDI32.353]
1152  *
1153  *
1154  */
1155 BOOL WINAPI StrokePath(HDC hdc)
1156 {
1157         FIXME(gdi, "StrokePath, stub\n");
1158         return 0;
1159 }
1160
1161 /*******************************************************************
1162  *      WidenPath [GDI32.360]
1163  *
1164  *
1165  */
1166 BOOL WINAPI WidenPath(HDC hdc)
1167 {
1168         FIXME(gdi, "WidenPath, stub\n");
1169         return 0;
1170 }
1171