subsys/win32k/objects/bezier.c

   1 #include <windows.h>
   2 #include <ddk/ntddk.h>
   3
   4 /******************************************************************
   5  *
   6  *   *Very* simple bezier drawing code,
   7  *
   8  *   It uses a recursive algorithm to divide the curve in a series
   9  *   of straight line segements. Not ideal but for me sufficient.
  10  *   If you are in need for something better look for some incremental
  11  *   algorithm.
  12  *
  13  *   7 July 1998 Rein Klazes
  14  */
  15
  16  /*
  17   * some macro definitions for bezier drawing
  18   *
  19   * to avoid trucation errors the coordinates are
  20   * shifted upwards. When used in drawing they are
  21   * shifted down again, including correct rounding
  22   * and avoiding floating point arithmatic
  23   * 4 bits should allow 27 bits coordinates which I saw
  24   * somewere in the win32 doc's
  25   *
  26   */
  27
  28 #define BEZIERSHIFTBITS 4
  29 #define BEZIERSHIFTUP(x)    ((x)<<BEZIERSHIFTBITS)
  30 #define BEZIERPIXEL        BEZIERSHIFTUP(1)
  31 #define BEZIERSHIFTDOWN(x)  (((x)+(1<<(BEZIERSHIFTBITS-1)))>>BEZIERSHIFTBITS)
  32 /* maximum depth of recursion */
  33 #define BEZIERMAXDEPTH  8
  34
  35 /* size of array to store points on */
  36 /* enough for one curve */
  37 #define BEZIER_INITBUFSIZE    (150)
  38
  39 /* calculate Bezier average, in this case the middle
  40  * correctly rounded...
  41  * */
  42
  43 #define BEZIERMIDDLE(Mid, P1, P2) \
  44   (Mid).x=((P1).x+(P2).x + 1)/2;\
  45   (Mid).y=((P1).y+(P2).y + 1)/2;
  46
  47 /**********************************************************
  48 * BezierCheck helper function to check
  49 * that recursion can be terminated
  50 *       Points[0] and Points[3] are begin and endpoint
  51 *       Points[1] and Points[2] are control points
  52 *       level is the recursion depth
  53 *       returns true if the recusion can be terminated
  54 */
  55 static BOOL BezierCheck( int level, POINT *Points)
  56 {
  57   INT dx, dy;
  58
  59   dx=Points[3].x-Points[0].x;
  60   dy=Points[3].y-Points[0].y;
  61   if(abs(dy)<=abs(dx)) {/* shallow line */
  62     /* check that control points are between begin and end */
  63     if(Points[1].x < Points[0].x){
  64       if(Points[1].x < Points[3].x) return FALSE;
  65     }else
  66     if(Points[1].x > Points[3].x) return FALSE;
  67     if(Points[2].x < Points[0].x) {
  68       if(Points[2].x < Points[3].x) return FALSE;
  69     } else
  70       if(Points[2].x > Points[3].x) return FALSE;
  71       dx=BEZIERSHIFTDOWN(dx);
  72       if(!dx) return TRUE;
  73       if(abs(Points[1].y-Points[0].y-(dy/dx)*
  74         BEZIERSHIFTDOWN(Points[1].x-Points[0].x)) > BEZIERPIXEL ||
  75         abs(Points[2].y-Points[0].y-(dy/dx)*
  76         BEZIERSHIFTDOWN(Points[2].x-Points[0].x)) > BEZIERPIXEL) return FALSE;
  77       else
  78         return TRUE;
  79     } else{ /* steep line */
  80       /* check that control points are between begin and end */
  81       if(Points[1].y < Points[0].y){
  82         if(Points[1].y < Points[3].y) return FALSE;
  83       } else
  84         if(Points[1].y > Points[3].y) return FALSE;
  85       if(Points[2].y < Points[0].y){
  86         if(Points[2].y < Points[3].y) return FALSE;
  87       } else
  88         if(Points[2].y > Points[3].y) return FALSE;
  89       dy=BEZIERSHIFTDOWN(dy);
  90       if(!dy) return TRUE;
  91       if(abs(Points[1].x-Points[0].x-(dx/dy)*
  92         BEZIERSHIFTDOWN(Points[1].y-Points[0].y)) > BEZIERPIXEL ||
  93         abs(Points[2].x-Points[0].x-(dx/dy)*
  94         BEZIERSHIFTDOWN(Points[2].y-Points[0].y)) > BEZIERPIXEL ) return FALSE;
  95       else
  96         return TRUE;
  97     }
  98 }
  99
 100 /* Helper for GDI_Bezier.
 101  * Just handles one Bezier, so Points should point to four POINTs
 102  */
 103 static void GDI_InternalBezier( POINT *Points, POINT **PtsOut, INT *dwOut,
 104                                 INT *nPtsOut, INT level )
 105 {
 106   if(*nPtsOut == *dwOut) {
 107     *dwOut *= 2;
 108     *PtsOut = ExAllocatePool(NonPagedPool, *dwOut * sizeof(POINT));
 109   }
 110
 111   if(!level || BezierCheck(level, Points)) {
 112     if(*nPtsOut == 0) {
 113       (*PtsOut)[0].x = BEZIERSHIFTDOWN(Points[0].x);
 114       (*PtsOut)[0].y = BEZIERSHIFTDOWN(Points[0].y);
 115        *nPtsOut = 1;
 116     }
 117     (*PtsOut)[*nPtsOut].x = BEZIERSHIFTDOWN(Points[3].x);
 118     (*PtsOut)[*nPtsOut].y = BEZIERSHIFTDOWN(Points[3].y);
 119     (*nPtsOut) ++;
 120   } else {
 121     POINT Points2[4]; /* for the second recursive call */
 122     Points2[3]=Points[3];
 123     BEZIERMIDDLE(Points2[2], Points[2], Points[3]);
 124     BEZIERMIDDLE(Points2[0], Points[1], Points[2]);
 125     BEZIERMIDDLE(Points2[1],Points2[0],Points2[2]);
 126
 127     BEZIERMIDDLE(Points[1], Points[0],  Points[1]);
 128     BEZIERMIDDLE(Points[2], Points[1], Points2[0]);
 129     BEZIERMIDDLE(Points[3], Points[2], Points2[1]);
 130
 131     Points2[0]=Points[3];
 132
 133     /* do the two halves */
 134     GDI_InternalBezier(Points, PtsOut, dwOut, nPtsOut, level-1);
 135     GDI_InternalBezier(Points2, PtsOut, dwOut, nPtsOut, level-1);
 136   }
 137 }
 138
 139 /***********************************************************************
 140  *           GDI_Bezier   [INTERNAL]
 141  *   Calculate line segments that approximate -what microsoft calls- a bezier
 142  *   curve.
 143  *   The routine recursively divides the curve in two parts until a straight
 144  *   line can be drawn
 145  *
 146  *  PARAMS
 147  *
 148  *  Points  [I] Ptr to count POINTs which are the end and control points
 149  *              of the set of Bezier curves to flatten.
 150  *  count   [I] Number of Points.  Must be 3n+1.
 151  *  nPtsOut [O] Will contain no of points that have been produced (i.e. no. of
 152  *              lines+1).
 153  *
 154  *  RETURNS
 155  *
 156  *  Ptr to an array of POINTs that contain the lines that approximinate the
 157  *  Beziers.  The array is allocated on the process heap and it is the caller's
 158  *  responsibility to HeapFree it. [this is not a particularly nice interface
 159  *  but since we can't know in advance how many points will generate, the
 160  *  alternative would be to call the function twice, once to determine the size
 161  *  and a second time to do the work - I decided this was too much of a pain].
 162  */
 163 POINT *GDI_Bezier( const POINT *Points, INT count, INT *nPtsOut )
 164 {
 165   POINT *out;
 166   INT Bezier, dwOut = BEZIER_INITBUFSIZE, i;
 167
 168   if((count - 1) % 3 != 0) {
 169     return NULL;
 170   }
 171   *nPtsOut = 0;
 172   out = ExAllocatePool(NonPagedPool, dwOut * sizeof(POINT));
 173   for(Bezier = 0; Bezier < (count-1)/3; Bezier++) {
 174     POINT ptBuf[4];
 175     memcpy(ptBuf, Points + Bezier * 3, sizeof(POINT) * 4);
 176     for(i = 0; i < 4; i++) {
 177       ptBuf[i].x = BEZIERSHIFTUP(ptBuf[i].x);
 178       ptBuf[i].y = BEZIERSHIFTUP(ptBuf[i].y);
 179     }
 180     GDI_InternalBezier( ptBuf, &out, &dwOut, nPtsOut, BEZIERMAXDEPTH );
 181   }
 182
 183   return out;
 184 }