win32ss/gdi/ntgdi/bezier.c

   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 */