2 * COPYRIGHT: GNU GPL, See COPYING in the top level directory
3 * PROJECT: ReactOS kernel
4 * PURPOSE: Bezier functions
5 * FILE: subsys/win32k/objects/bezier.c
14 /******************************************************************
16 * *Very* simple bezier drawing code,
18 * It uses a recursive algorithm to divide the curve in a series
19 * of straight line segements. Not ideal but for me sufficient.
20 * If you are in need for something better look for some incremental
23 * 7 July 1998 Rein Klazes
27 * Some macro definitions for bezier drawing.
29 * To avoid trucation errors the coordinates are
30 * shifted upwards. When used in drawing they are
31 * shifted down again, including correct rounding
32 * and avoiding floating point arithmatic
33 * 4 bits should allow 27 bits coordinates which I saw
34 * somewere in the win32 doc's
38 #define BEZIERSHIFTBITS 4
39 #define BEZIERSHIFTUP(x) ((x)<<BEZIERSHIFTBITS)
40 #define BEZIERPIXEL BEZIERSHIFTUP(1)
41 #define BEZIERSHIFTDOWN(x) (((x)+(1<<(BEZIERSHIFTBITS-1)))>>BEZIERSHIFTBITS)
42 /* Maximum depth of recursion */
43 #define BEZIERMAXDEPTH 8
45 /* Size of array to store points on */
46 /* enough for one curve */
47 #define BEZIER_INITBUFSIZE (150)
49 /* Calculate Bezier average, in this case the middle
50 * correctly rounded...
53 #define BEZIERMIDDLE(Mid, P1, P2) \
54 (Mid).x=((P1).x+(P2).x + 1) >> 1;\
55 (Mid).y=((P1).y+(P2).y + 1) >> 1;
57 /**********************************************************
58 * BezierCheck helper function to check
59 * that recursion can be terminated
60 * Points[0] and Points[3] are begin and endpoint
61 * Points[1] and Points[2] are control points
62 * level is the recursion depth
63 * returns true if the recusion can be terminated
65 static BOOL FASTCALL
BezierCheck( int level
, POINT
*Points
)
69 dx
=Points
[3].x
-Points
[0].x
;
70 dy
=Points
[3].y
-Points
[0].y
;
71 if ( abs(dy
) <= abs(dx
) ) /* Shallow line */
73 /* Check that control points are between begin and end */
74 if ( Points
[1].x
< Points
[0].x
)
76 if ( Points
[1].x
< Points
[3].x
)
79 else if ( Points
[1].x
> Points
[3].x
)
81 if ( Points
[2].x
< Points
[0].x
)
83 if ( Points
[2].x
< Points
[3].x
)
86 else if ( Points
[2].x
> Points
[3].x
)
88 dx
= BEZIERSHIFTDOWN(dx
);
91 if ( abs(Points
[1].y
-Points
[0].y
-(dy
/dx
)*
92 BEZIERSHIFTDOWN(Points
[1].x
-Points
[0].x
)) > BEZIERPIXEL
||
93 abs(Points
[2].y
-Points
[0].y
-(dy
/dx
)*
94 BEZIERSHIFTDOWN(Points
[2].x
-Points
[0].x
)) > BEZIERPIXEL
103 /* Check that control points are between begin and end */
104 if(Points
[1].y
< Points
[0].y
)
106 if(Points
[1].y
< Points
[3].y
)
109 else if(Points
[1].y
> Points
[3].y
)
111 if ( Points
[2].y
< Points
[0].y
)
113 if ( Points
[2].y
< Points
[3].y
)
116 else if ( Points
[2].y
> Points
[3].y
)
118 dy
= BEZIERSHIFTDOWN(dy
);
121 if ( abs(Points
[1].x
-Points
[0].x
-(dx
/dy
)*
122 BEZIERSHIFTDOWN(Points
[1].y
-Points
[0].y
)) > BEZIERPIXEL
||
123 abs(Points
[2].x
-Points
[0].x
-(dx
/dy
)*
124 BEZIERSHIFTDOWN(Points
[2].y
-Points
[0].y
)) > BEZIERPIXEL
132 /* Helper for GDI_Bezier.
133 * Just handles one Bezier, so Points should point to four POINTs
135 static void APIENTRY
GDI_InternalBezier( POINT
*Points
, POINT
**PtsOut
, INT
*dwOut
,
136 INT
*nPtsOut
, INT level
)
138 if(*nPtsOut
== *dwOut
) {
140 *PtsOut
= ExAllocatePoolWithTag(PagedPool
, *dwOut
* sizeof(POINT
), TAG_BEZIER
);
143 if(!level
|| BezierCheck(level
, Points
)) {
145 (*PtsOut
)[0].x
= BEZIERSHIFTDOWN(Points
[0].x
);
146 (*PtsOut
)[0].y
= BEZIERSHIFTDOWN(Points
[0].y
);
149 (*PtsOut
)[*nPtsOut
].x
= BEZIERSHIFTDOWN(Points
[3].x
);
150 (*PtsOut
)[*nPtsOut
].y
= BEZIERSHIFTDOWN(Points
[3].y
);
153 POINT Points2
[4]; /* For the second recursive call */
154 Points2
[3]=Points
[3];
155 BEZIERMIDDLE(Points2
[2], Points
[2], Points
[3]);
156 BEZIERMIDDLE(Points2
[0], Points
[1], Points
[2]);
157 BEZIERMIDDLE(Points2
[1],Points2
[0],Points2
[2]);
159 BEZIERMIDDLE(Points
[1], Points
[0], Points
[1]);
160 BEZIERMIDDLE(Points
[2], Points
[1], Points2
[0]);
161 BEZIERMIDDLE(Points
[3], Points
[2], Points2
[1]);
163 Points2
[0]=Points
[3];
165 /* Do the two halves */
166 GDI_InternalBezier(Points
, PtsOut
, dwOut
, nPtsOut
, level
-1);
167 GDI_InternalBezier(Points2
, PtsOut
, dwOut
, nPtsOut
, level
-1);
171 /***********************************************************************
172 * GDI_Bezier [INTERNAL]
173 * Calculate line segments that approximate -what microsoft calls- a bezier
175 * The routine recursively divides the curve in two parts until a straight
180 * Points [I] Ptr to count POINTs which are the end and control points
181 * of the set of Bezier curves to flatten.
182 * count [I] Number of Points. Must be 3n+1.
183 * nPtsOut [O] Will contain no of points that have been produced (i.e. no. of
188 * Ptr to an array of POINTs that contain the lines that approximinate the
189 * Beziers. The array is allocated on the process heap and it is the caller's
190 * responsibility to HeapFree it. [this is not a particularly nice interface
191 * but since we can't know in advance how many points will generate, the
192 * alternative would be to call the function twice, once to determine the size
193 * and a second time to do the work - I decided this was too much of a pain].
195 POINT
* FASTCALL
GDI_Bezier( const POINT
*Points
, INT count
, INT
*nPtsOut
)
198 INT Bezier
, dwOut
= BEZIER_INITBUFSIZE
, i
;
200 if((count
- 1) % 3 != 0) {
205 out
= ExAllocatePoolWithTag(PagedPool
, dwOut
* sizeof(POINT
), TAG_BEZIER
);
210 for(Bezier
= 0; Bezier
< (count
-1)/3; Bezier
++) {
212 memcpy(ptBuf
, Points
+ Bezier
* 3, sizeof(POINT
) * 4);
213 for(i
= 0; i
< 4; i
++) {
214 ptBuf
[i
].x
= BEZIERSHIFTUP(ptBuf
[i
].x
);
215 ptBuf
[i
].y
= BEZIERSHIFTUP(ptBuf
[i
].y
);
217 GDI_InternalBezier( ptBuf
, &out
, &dwOut
, nPtsOut
, BEZIERMAXDEPTH
);