1 /* 2 * COPYRIGHT: GNU LGPL 3 * PURPOSE: Bezier functions 4 */ 5 6 #include <win32k.h> 7 8 #define NDEBUG 9 #include <debug.h> 10 11 /* Based on Wine Staging 1.7.37 - dlls/gdi32/painting.c */ 12 13 /****************************************************************** 14 * 15 * *Very* simple bezier drawing code, 16 * 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 20 * algorithm. 21 * 22 * 7 July 1998 Rein Klazes 23 */ 24 25 /* 26 * some macro definitions for bezier drawing 27 * 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 34 * 35 */ 36 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 43 44 /* size of array to store points on */ 45 /* enough for one curve */ 46 #define BEZIER_INITBUFSIZE (150) 47 48 /* calculate Bezier average, in this case the middle 49 * correctly rounded... 50 * */ 51 52 #define BEZIERMIDDLE(Mid, P1, P2) \ 53 (Mid).x=((P1).x+(P2).x + 1)/2;\ 54 (Mid).y=((P1).y+(P2).y + 1)/2; 55 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 63 */ 64 static BOOL BezierCheck( int level, POINT *Points) 65 { 66 INT dx, dy; 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) 73 return FALSE; 74 }else 75 if(Points[1].x > Points[3].x) 76 return FALSE; 77 if(Points[2].x < Points[0].x){ 78 if(Points[2].x < Points[3].x) 79 return FALSE; 80 }else 81 if(Points[2].x > Points[3].x) 82 return FALSE; 83 dx=BEZIERSHIFTDOWN(dx); 84 if(!dx) return TRUE; 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 ) 89 return FALSE; 90 else 91 return TRUE; 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) 96 return FALSE; 97 }else 98 if(Points[1].y > Points[3].y) 99 return FALSE; 100 if(Points[2].y < Points[0].y){ 101 if(Points[2].y < Points[3].y) 102 return FALSE; 103 }else 104 if(Points[2].y > Points[3].y) 105 return FALSE; 106 dy=BEZIERSHIFTDOWN(dy); 107 if(!dy) return TRUE; 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 ) 112 return FALSE; 113 else 114 return TRUE; 115 } 116 } 117 118 /* Helper for GDI_Bezier. 119 * Just handles one Bezier, so Points should point to four POINTs 120 */ 121 static void GDI_InternalBezier( POINT *Points, POINT **PtsOut, INT *dwOut, 122 INT *nPtsOut, INT level ) 123 { 124 if(*nPtsOut == *dwOut) { 125 *dwOut *= 2; 126 *PtsOut = ExAllocatePoolWithTag(PagedPool, *dwOut * sizeof(POINT), TAG_BEZIER); 127 if (*PtsOut == NULL) 128 { 129 /// \todo FIXME! 130 NT_ASSERT(FALSE); 131 return; 132 } 133 } 134 135 if(!level || BezierCheck(level, Points)) { 136 if(*nPtsOut == 0) { 137 (*PtsOut)[0].x = BEZIERSHIFTDOWN(Points[0].x); 138 (*PtsOut)[0].y = BEZIERSHIFTDOWN(Points[0].y); 139 *nPtsOut = 1; 140 } 141 (*PtsOut)[*nPtsOut].x = BEZIERSHIFTDOWN(Points[3].x); 142 (*PtsOut)[*nPtsOut].y = BEZIERSHIFTDOWN(Points[3].y); 143 (*nPtsOut) ++; 144 } else { 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]); 150 151 BEZIERMIDDLE(Points[1], Points[0], Points[1]); 152 BEZIERMIDDLE(Points[2], Points[1], Points2[0]); 153 BEZIERMIDDLE(Points[3], Points[2], Points2[1]); 154 155 Points2[0]=Points[3]; 156 157 /* do the two halves */ 158 GDI_InternalBezier(Points, PtsOut, dwOut, nPtsOut, level-1); 159 GDI_InternalBezier(Points2, PtsOut, dwOut, nPtsOut, level-1); 160 } 161 } 162 163 164 165 /*********************************************************************** 166 * GDI_Bezier [INTERNAL] 167 * Calculate line segments that approximate -what microsoft calls- a bezier 168 * curve. 169 * The routine recursively divides the curve in two parts until a straight 170 * line can be drawn 171 * 172 * PARAMS 173 * 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 178 * lines+1). 179 * 180 * RETURNS 181 * 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]. 188 */ 189 POINT *GDI_Bezier( const POINT *Points, INT count, INT *nPtsOut ) 190 { 191 POINT *out; 192 INT Bezier, dwOut = BEZIER_INITBUFSIZE, i; 193 194 if (count == 1 || (count - 1) % 3 != 0) { 195 DPRINT1("Invalid no. of points %d\n", count); 196 return NULL; 197 } 198 *nPtsOut = 0; 199 200 out = ExAllocatePoolWithTag(PagedPool, dwOut * sizeof(POINT), TAG_BEZIER); 201 if (!out) return NULL; 202 203 for(Bezier = 0; Bezier < (count-1)/3; Bezier++) { 204 POINT ptBuf[4]; 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); 209 } 210 GDI_InternalBezier( ptBuf, &out, &dwOut, nPtsOut, BEZIERMAXDEPTH ); 211 } 212 DPRINT("Produced %d points\n", *nPtsOut); 213 return out; 214 } 215 /* EOF */ 216