3 * PURPOSE: Bezier functions
11 /* Based on Wine Staging 1.7.37 - dlls/gdi32/painting.c */
13 /******************************************************************
15 * *Very* simple bezier drawing code,
17 * It uses a recursive algorithm to divide the curve in a series
18 * of straight line segments. Not ideal but sufficient for me.
19 * If you are in need for something better look for some incremental
22 * 7 July 1998 Rein Klazes
26 * some macro definitions for bezier drawing
28 * to avoid truncation errors the coordinates are
29 * shifted upwards. When used in drawing they are
30 * shifted down again, including correct rounding
31 * and avoiding floating point arithmetic
32 * 4 bits should allow 27 bits coordinates which I saw
33 * somewhere in the win32 doc's
37 #define BEZIERSHIFTBITS 4
38 #define BEZIERSHIFTUP(x) ((x)<<BEZIERSHIFTBITS)
39 #define BEZIERPIXEL BEZIERSHIFTUP(1)
40 #define BEZIERSHIFTDOWN(x) (((x)+(1<<(BEZIERSHIFTBITS-1)))>>BEZIERSHIFTBITS)
41 /* maximum depth of recursion */
42 #define BEZIERMAXDEPTH 8
44 /* size of array to store points on */
45 /* enough for one curve */
46 #define BEZIER_INITBUFSIZE (150)
48 /* calculate Bezier average, in this case the middle
49 * correctly rounded...
52 #define BEZIERMIDDLE(Mid, P1, P2) \
53 (Mid).x=((P1).x+(P2).x + 1)/2;\
54 (Mid).y=((P1).y+(P2).y + 1)/2;
56 /**********************************************************
57 * BezierCheck helper function to check
58 * that recursion can be terminated
59 * Points[0] and Points[3] are begin and endpoint
60 * Points[1] and Points[2] are control points
61 * level is the recursion depth
62 * returns true if the recursion can be terminated
64 static BOOL
BezierCheck( int level
, POINT
*Points
)
67 dx
=Points
[3].x
-Points
[0].x
;
68 dy
=Points
[3].y
-Points
[0].y
;
69 if(abs(dy
)<=abs(dx
)){/* shallow line */
70 /* check that control points are between begin and end */
71 if(Points
[1].x
< Points
[0].x
){
72 if(Points
[1].x
< Points
[3].x
)
75 if(Points
[1].x
> Points
[3].x
)
77 if(Points
[2].x
< Points
[0].x
){
78 if(Points
[2].x
< Points
[3].x
)
81 if(Points
[2].x
> Points
[3].x
)
83 dx
=BEZIERSHIFTDOWN(dx
);
85 if(abs(Points
[1].y
-Points
[0].y
-(dy
/dx
)*
86 BEZIERSHIFTDOWN(Points
[1].x
-Points
[0].x
)) > BEZIERPIXEL
||
87 abs(Points
[2].y
-Points
[0].y
-(dy
/dx
)*
88 BEZIERSHIFTDOWN(Points
[2].x
-Points
[0].x
)) > BEZIERPIXEL
)
92 }else{ /* steep line */
93 /* check that control points are between begin and end */
94 if(Points
[1].y
< Points
[0].y
){
95 if(Points
[1].y
< Points
[3].y
)
98 if(Points
[1].y
> Points
[3].y
)
100 if(Points
[2].y
< Points
[0].y
){
101 if(Points
[2].y
< Points
[3].y
)
104 if(Points
[2].y
> Points
[3].y
)
106 dy
=BEZIERSHIFTDOWN(dy
);
108 if(abs(Points
[1].x
-Points
[0].x
-(dx
/dy
)*
109 BEZIERSHIFTDOWN(Points
[1].y
-Points
[0].y
)) > BEZIERPIXEL
||
110 abs(Points
[2].x
-Points
[0].x
-(dx
/dy
)*
111 BEZIERSHIFTDOWN(Points
[2].y
-Points
[0].y
)) > BEZIERPIXEL
)
118 /* Helper for GDI_Bezier.
119 * Just handles one Bezier, so Points should point to four POINTs
121 static void GDI_InternalBezier( POINT
*Points
, POINT
**PtsOut
, INT
*dwOut
,
122 INT
*nPtsOut
, INT level
)
124 if(*nPtsOut
== *dwOut
) {
126 *PtsOut
= ExAllocatePoolWithTag(PagedPool
, *dwOut
* sizeof(POINT
), TAG_BEZIER
);
135 if(!level
|| BezierCheck(level
, Points
)) {
137 (*PtsOut
)[0].x
= BEZIERSHIFTDOWN(Points
[0].x
);
138 (*PtsOut
)[0].y
= BEZIERSHIFTDOWN(Points
[0].y
);
141 (*PtsOut
)[*nPtsOut
].x
= BEZIERSHIFTDOWN(Points
[3].x
);
142 (*PtsOut
)[*nPtsOut
].y
= BEZIERSHIFTDOWN(Points
[3].y
);
145 POINT Points2
[4]; /* for the second recursive call */
146 Points2
[3]=Points
[3];
147 BEZIERMIDDLE(Points2
[2], Points
[2], Points
[3]);
148 BEZIERMIDDLE(Points2
[0], Points
[1], Points
[2]);
149 BEZIERMIDDLE(Points2
[1],Points2
[0],Points2
[2]);
151 BEZIERMIDDLE(Points
[1], Points
[0], Points
[1]);
152 BEZIERMIDDLE(Points
[2], Points
[1], Points2
[0]);
153 BEZIERMIDDLE(Points
[3], Points
[2], Points2
[1]);
155 Points2
[0]=Points
[3];
157 /* do the two halves */
158 GDI_InternalBezier(Points
, PtsOut
, dwOut
, nPtsOut
, level
-1);
159 GDI_InternalBezier(Points2
, PtsOut
, dwOut
, nPtsOut
, level
-1);
165 /***********************************************************************
166 * GDI_Bezier [INTERNAL]
167 * Calculate line segments that approximate -what microsoft calls- a bezier
169 * The routine recursively divides the curve in two parts until a straight
174 * Points [I] Ptr to count POINTs which are the end and control points
175 * of the set of Bezier curves to flatten.
176 * count [I] Number of Points. Must be 3n+1.
177 * nPtsOut [O] Will contain no of points that have been produced (i.e. no. of
182 * Ptr to an array of POINTs that contain the lines that approximate the
183 * Beziers. The array is allocated on the process heap and it is the caller's
184 * responsibility to HeapFree it. [this is not a particularly nice interface
185 * but since we can't know in advance how many points we will generate, the
186 * alternative would be to call the function twice, once to determine the size
187 * and a second time to do the work - I decided this was too much of a pain].
189 POINT
*GDI_Bezier( const POINT
*Points
, INT count
, INT
*nPtsOut
)
192 INT Bezier
, dwOut
= BEZIER_INITBUFSIZE
, i
;
194 if (count
== 1 || (count
- 1) % 3 != 0) {
195 DPRINT1("Invalid no. of points %d\n", count
);
200 out
= ExAllocatePoolWithTag(PagedPool
, dwOut
* sizeof(POINT
), TAG_BEZIER
);
201 if (!out
) return NULL
;
203 for(Bezier
= 0; Bezier
< (count
-1)/3; Bezier
++) {
205 memcpy(ptBuf
, Points
+ Bezier
* 3, sizeof(POINT
) * 4);
206 for(i
= 0; i
< 4; i
++) {
207 ptBuf
[i
].x
= BEZIERSHIFTUP(ptBuf
[i
].x
);
208 ptBuf
[i
].y
= BEZIERSHIFTUP(ptBuf
[i
].y
);
210 GDI_InternalBezier( ptBuf
, &out
, &dwOut
, nPtsOut
, BEZIERMAXDEPTH
);
212 DPRINT("Produced %d points\n", *nPtsOut
);