reactos/subsystems/win32/win32k/objects/bezier.c

   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  */
   8
   9 #include <win32k.h>
  10
  11 #define NDEBUG
  12 #include <debug.h>
  13
  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  */
  25
  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   */
  37
  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
  44
  45 /* Size of array to store points on */
  46 /* enough for one curve */
  47 #define BEZIER_INITBUFSIZE    (150)
  48
  49 /* Calculate Bezier average, in this case the middle
  50  * correctly rounded...
  51  * */
  52
  53 #define BEZIERMIDDLE(Mid, P1, P2) \
  54   (Mid).x=((P1).x+(P2).x + 1) >> 1;\
  55   (Mid).y=((P1).y+(P2).y + 1) >> 1;
  56
  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;
  68
  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 }
 131
 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   }
 142
 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]);
 158
 159     BEZIERMIDDLE(Points[1], Points[0],  Points[1]);
 160     BEZIERMIDDLE(Points[2], Points[1], Points2[0]);
 161     BEZIERMIDDLE(Points[3], Points[2], Points2[1]);
 162
 163     Points2[0]=Points[3];
 164
 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 }
 170
 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;
 199
 200   if((count - 1) % 3 != 0) {
 201     return NULL;
 202   }
 203   *nPtsOut = 0;
 204
 205   out = ExAllocatePoolWithTag(PagedPool, dwOut * sizeof(POINT), TAG_BEZIER);
 206   if(!out) {
 207     return NULL;
 208   }
 209
 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   }
 219
 220   return out;
 221 }
 222 /* EOF */