subsys/win32k/objects/bezier.c

   1 /*
   2  *  ReactOS W32 Subsystem
   3  *  Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 ReactOS Team
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19 /* $Id$ */
  20 #include <windows.h>
  21 #include <ddk/ntddk.h>
  22 #include <math.h>
  23
  24 /******************************************************************
  25  *
  26  *   *Very* simple bezier drawing code,
  27  *
  28  *   It uses a recursive algorithm to divide the curve in a series
  29  *   of straight line segements. Not ideal but for me sufficient.
  30  *   If you are in need for something better look for some incremental
  31  *   algorithm.
  32  *
  33  *   7 July 1998 Rein Klazes
  34  */
  35
  36  /*
  37   * some macro definitions for bezier drawing
  38   *
  39   * to avoid trucation errors the coordinates are
  40   * shifted upwards. When used in drawing they are
  41   * shifted down again, including correct rounding
  42   * and avoiding floating point arithmatic
  43   * 4 bits should allow 27 bits coordinates which I saw
  44   * somewere in the win32 doc's
  45   *
  46   */
  47
  48 #define BEZIERSHIFTBITS 4
  49 #define BEZIERSHIFTUP(x)    ((x)<<BEZIERSHIFTBITS)
  50 #define BEZIERPIXEL        BEZIERSHIFTUP(1)
  51 #define BEZIERSHIFTDOWN(x)  (((x)+(1<<(BEZIERSHIFTBITS-1)))>>BEZIERSHIFTBITS)
  52 /* maximum depth of recursion */
  53 #define BEZIERMAXDEPTH  8
  54
  55 /* size of array to store points on */
  56 /* enough for one curve */
  57 #define BEZIER_INITBUFSIZE    (150)
  58
  59 /* calculate Bezier average, in this case the middle
  60  * correctly rounded...
  61  * */
  62
  63 #define BEZIERMIDDLE(Mid, P1, P2) \
  64   (Mid).x=((P1).x+(P2).x + 1)/2;\
  65   (Mid).y=((P1).y+(P2).y + 1)/2;
  66
  67 static int abs ( int __x )
  68 {
  69   if ( __x < 0 )
  70     return -__x;
  71   else
  72     return __x;
  73 }
  74
  75 /**********************************************************
  76 * BezierCheck helper function to check
  77 * that recursion can be terminated
  78 *       Points[0] and Points[3] are begin and endpoint
  79 *       Points[1] and Points[2] are control points
  80 *       level is the recursion depth
  81 *       returns true if the recusion can be terminated
  82 */
  83 static BOOL FASTCALL BezierCheck( int level, POINT *Points)
  84 {
  85   INT dx, dy;
  86
  87   dx=Points[3].x-Points[0].x;
  88   dy=Points[3].y-Points[0].y;
  89   if ( abs(dy) <= abs(dx) ) /* shallow line */
  90   {
  91     /* check that control points are between begin and end */
  92     if ( Points[1].x < Points[0].x )
  93     {
  94       if ( Points[1].x < Points[3].x )
  95         return FALSE;
  96     }
  97     else if ( Points[1].x > Points[3].x )
  98       return FALSE;
  99     if ( Points[2].x < Points[0].x)
 100     {
 101       if ( Points[2].x < Points[3].x )
 102         return FALSE;
 103     }
 104     else if ( Points[2].x > Points[3].x )
 105       return FALSE;
 106     dx = BEZIERSHIFTDOWN(dx);
 107     if ( !dx )
 108       return TRUE;
 109     if ( abs(Points[1].y-Points[0].y-(dy/dx)*
 110         BEZIERSHIFTDOWN(Points[1].x-Points[0].x)) > BEZIERPIXEL ||
 111         abs(Points[2].y-Points[0].y-(dy/dx)*
 112         BEZIERSHIFTDOWN(Points[2].x-Points[0].x)) > BEZIERPIXEL
 113         )
 114         return FALSE;
 115       else
 116         return TRUE;
 117   }
 118   else
 119   { /* steep line */
 120       /* check that control points are between begin and end */
 121       if(Points[1].y < Points[0].y)
 122       {
 123         if(Points[1].y < Points[3].y)
 124           return FALSE;
 125       }
 126       else if(Points[1].y > Points[3].y)
 127         return FALSE;
 128       if ( Points[2].y < Points[0].y )
 129       {
 130         if ( Points[2].y < Points[3].y )
 131           return FALSE;
 132       }
 133       else if ( Points[2].y > Points[3].y )
 134         return FALSE;
 135       dy = BEZIERSHIFTDOWN(dy);
 136       if ( !dy )
 137         return TRUE;
 138       if ( abs(Points[1].x-Points[0].x-(dx/dy)*
 139         BEZIERSHIFTDOWN(Points[1].y-Points[0].y)) > BEZIERPIXEL ||
 140         abs(Points[2].x-Points[0].x-(dx/dy)*
 141         BEZIERSHIFTDOWN(Points[2].y-Points[0].y)) > BEZIERPIXEL
 142         )
 143         return FALSE;
 144       else
 145         return TRUE;
 146     }
 147 }
 148
 149 /* Helper for GDI_Bezier.
 150  * Just handles one Bezier, so Points should point to four POINTs
 151  */
 152 static void STDCALL GDI_InternalBezier( POINT *Points, POINT **PtsOut, INT *dwOut,
 153                                 INT *nPtsOut, INT level )
 154 {
 155   if(*nPtsOut == *dwOut) {
 156     *dwOut *= 2;
 157     *PtsOut = ExAllocatePool(NonPagedPool, *dwOut * sizeof(POINT));
 158   }
 159
 160   if(!level || BezierCheck(level, Points)) {
 161     if(*nPtsOut == 0) {
 162       (*PtsOut)[0].x = BEZIERSHIFTDOWN(Points[0].x);
 163       (*PtsOut)[0].y = BEZIERSHIFTDOWN(Points[0].y);
 164        *nPtsOut = 1;
 165     }
 166     (*PtsOut)[*nPtsOut].x = BEZIERSHIFTDOWN(Points[3].x);
 167     (*PtsOut)[*nPtsOut].y = BEZIERSHIFTDOWN(Points[3].y);
 168     (*nPtsOut) ++;
 169   } else {
 170     POINT Points2[4]; /* for the second recursive call */
 171     Points2[3]=Points[3];
 172     BEZIERMIDDLE(Points2[2], Points[2], Points[3]);
 173     BEZIERMIDDLE(Points2[0], Points[1], Points[2]);
 174     BEZIERMIDDLE(Points2[1],Points2[0],Points2[2]);
 175
 176     BEZIERMIDDLE(Points[1], Points[0],  Points[1]);
 177     BEZIERMIDDLE(Points[2], Points[1], Points2[0]);
 178     BEZIERMIDDLE(Points[3], Points[2], Points2[1]);
 179
 180     Points2[0]=Points[3];
 181
 182     /* do the two halves */
 183     GDI_InternalBezier(Points, PtsOut, dwOut, nPtsOut, level-1);
 184     GDI_InternalBezier(Points2, PtsOut, dwOut, nPtsOut, level-1);
 185   }
 186 }
 187
 188 /***********************************************************************
 189  *           GDI_Bezier   [INTERNAL]
 190  *   Calculate line segments that approximate -what microsoft calls- a bezier
 191  *   curve.
 192  *   The routine recursively divides the curve in two parts until a straight
 193  *   line can be drawn
 194  *
 195  *  PARAMS
 196  *
 197  *  Points  [I] Ptr to count POINTs which are the end and control points
 198  *              of the set of Bezier curves to flatten.
 199  *  count   [I] Number of Points.  Must be 3n+1.
 200  *  nPtsOut [O] Will contain no of points that have been produced (i.e. no. of
 201  *              lines+1).
 202  *
 203  *  RETURNS
 204  *
 205  *  Ptr to an array of POINTs that contain the lines that approximinate the
 206  *  Beziers.  The array is allocated on the process heap and it is the caller's
 207  *  responsibility to HeapFree it. [this is not a particularly nice interface
 208  *  but since we can't know in advance how many points will generate, the
 209  *  alternative would be to call the function twice, once to determine the size
 210  *  and a second time to do the work - I decided this was too much of a pain].
 211  */
 212 POINT * FASTCALL GDI_Bezier( const POINT *Points, INT count, INT *nPtsOut )
 213 {
 214   POINT *out;
 215   INT Bezier, dwOut = BEZIER_INITBUFSIZE, i;
 216
 217   if((count - 1) % 3 != 0) {
 218     return NULL;
 219   }
 220   *nPtsOut = 0;
 221   out = ExAllocatePool(NonPagedPool, dwOut * sizeof(POINT));
 222   for(Bezier = 0; Bezier < (count-1)/3; Bezier++) {
 223     POINT ptBuf[4];
 224     memcpy(ptBuf, Points + Bezier * 3, sizeof(POINT) * 4);
 225     for(i = 0; i < 4; i++) {
 226       ptBuf[i].x = BEZIERSHIFTUP(ptBuf[i].x);
 227       ptBuf[i].y = BEZIERSHIFTUP(ptBuf[i].y);
 228     }
 229     GDI_InternalBezier( ptBuf, &out, &dwOut, nPtsOut, BEZIERMAXDEPTH );
 230   }
 231
 232   return out;
 233 }
 234 /* EOF */