1 /*
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
6 * PROGRAMER: Unknown
7 */
9 #include <win32k.h>
11 #define NDEBUG
12 #include <debug.h>
14 /******************************************************************
15 *
16 * *Very* simple bezier drawing code,
17 *
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
21 * algorithm.
22 *
23 * 7 July 1998 Rein Klazes
24 */
26 /*
27 * Some macro definitions for bezier drawing.
28 *
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
35 *
36 */
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...
51 * */
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
64 */
65 static BOOL FASTCALL BezierCheck( int level, POINT *Points)
66 {
67 INT dx, dy;
69 dx=Points[3].x-Points[0].x;
70 dy=Points[3].y-Points[0].y;
71 if ( abs(dy) <= abs(dx) ) /* Shallow line */
72 {
73 /* Check that control points are between begin and end */
74 if ( Points[1].x < Points[0].x )
75 {
76 if ( Points[1].x < Points[3].x )
77 return FALSE;
78 }
79 else if ( Points[1].x > Points[3].x )
80 return FALSE;
81 if ( Points[2].x < Points[0].x)
82 {
83 if ( Points[2].x < Points[3].x )
84 return FALSE;
85 }
86 else if ( Points[2].x > Points[3].x )
87 return FALSE;
88 dx = BEZIERSHIFTDOWN(dx);
89 if ( !dx )
90 return TRUE;
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
95 )
96 return FALSE;
97 else
98 return TRUE;
99 }
100 else
101 {
102 /* Steep line */
103 /* Check that control points are between begin and end */
104 if(Points[1].y < Points[0].y)
105 {
106 if(Points[1].y < Points[3].y)
107 return FALSE;
108 }
109 else if(Points[1].y > Points[3].y)
110 return FALSE;
111 if ( Points[2].y < Points[0].y )
112 {
113 if ( Points[2].y < Points[3].y )
114 return FALSE;
115 }
116 else if ( Points[2].y > Points[3].y )
117 return FALSE;
118 dy = BEZIERSHIFTDOWN(dy);
119 if ( !dy )
120 return TRUE;
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
125 )
126 return FALSE;
127 else
128 return TRUE;
129 }
130 }
132 /* Helper for GDI_Bezier.
133 * Just handles one Bezier, so Points should point to four POINTs
134 */
135 static void APIENTRY GDI_InternalBezier( POINT *Points, POINT **PtsOut, INT *dwOut,
136 INT *nPtsOut, INT level )
137 {
138 if(*nPtsOut == *dwOut) {
139 *dwOut *= 2;
140 *PtsOut = ExAllocatePoolWithTag(PagedPool, *dwOut * sizeof(POINT), TAG_BEZIER);
141 }
143 if(!level || BezierCheck(level, Points)) {
144 if(*nPtsOut == 0) {
145 (*PtsOut)[0].x = BEZIERSHIFTDOWN(Points[0].x);
146 (*PtsOut)[0].y = BEZIERSHIFTDOWN(Points[0].y);
147 *nPtsOut = 1;
148 }
149 (*PtsOut)[*nPtsOut].x = BEZIERSHIFTDOWN(Points[3].x);
150 (*PtsOut)[*nPtsOut].y = BEZIERSHIFTDOWN(Points[3].y);
151 (*nPtsOut) ++;
152 } else {
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);
168 }
169 }
171 /***********************************************************************
172 * GDI_Bezier [INTERNAL]
173 * Calculate line segments that approximate -what microsoft calls- a bezier
174 * curve.
175 * The routine recursively divides the curve in two parts until a straight
176 * line can be drawn
177 *
178 * PARAMS
179 *
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
184 * lines+1).
185 *
186 * RETURNS
187 *
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].
194 */
195 POINT * FASTCALL GDI_Bezier( const POINT *Points, INT count, INT *nPtsOut )
196 {
197 POINT *out;
198 INT Bezier, dwOut = BEZIER_INITBUFSIZE, i;
200 if((count - 1) % 3 != 0) {
201 return NULL;
202 }
203 *nPtsOut = 0;
205 out = ExAllocatePoolWithTag(PagedPool, dwOut * sizeof(POINT), TAG_BEZIER);
206 if(!out) {
207 return NULL;
208 }
210 for(Bezier = 0; Bezier < (count-1)/3; Bezier++) {
211 POINT ptBuf[4];
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);
216 }
217 GDI_InternalBezier( ptBuf, &out, &dwOut, nPtsOut, BEZIERMAXDEPTH );
218 }
220 return out;
221 }
222 /* EOF */