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