reactos/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: bezier.c,v 1.3 2003/05/18 17:16:17 ea Exp $ */
  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 /**********************************************************
  68 * BezierCheck helper function to check
  69 * that recursion can be terminated
  70 *       Points[0] and Points[3] are begin and endpoint
  71 *       Points[1] and Points[2] are control points
  72 *       level is the recursion depth
  73 *       returns true if the recusion can be terminated
  74 */
  75 static BOOL FASTCALL BezierCheck( int level, POINT *Points)
  76 {
  77   INT dx, dy;
  78
  79   dx=Points[3].x-Points[0].x;
  80   dy=Points[3].y-Points[0].y;
  81   if(abs(dy)<=abs(dx)) {/* shallow line */
  82     /* check that control points are between begin and end */
  83     if(Points[1].x < Points[0].x){
  84       if(Points[1].x < Points[3].x) return FALSE;
  85     }else
  86     if(Points[1].x > Points[3].x) return FALSE;
  87     if(Points[2].x < Points[0].x) {
  88       if(Points[2].x < Points[3].x) return FALSE;
  89     } else
  90       if(Points[2].x > Points[3].x) return FALSE;
  91       dx=BEZIERSHIFTDOWN(dx);
  92       if(!dx) return TRUE;
  93       if(abs(Points[1].y-Points[0].y-(dy/dx)*
  94         BEZIERSHIFTDOWN(Points[1].x-Points[0].x)) > BEZIERPIXEL ||
  95         abs(Points[2].y-Points[0].y-(dy/dx)*
  96         BEZIERSHIFTDOWN(Points[2].x-Points[0].x)) > BEZIERPIXEL) return FALSE;
  97       else
  98         return TRUE;
  99     } else{ /* steep line */
 100       /* check that control points are between begin and end */
 101       if(Points[1].y < Points[0].y){
 102         if(Points[1].y < Points[3].y) return FALSE;
 103       } else
 104         if(Points[1].y > Points[3].y) return FALSE;
 105       if(Points[2].y < Points[0].y){
 106         if(Points[2].y < Points[3].y) return FALSE;
 107       } else
 108         if(Points[2].y > Points[3].y) return FALSE;
 109       dy=BEZIERSHIFTDOWN(dy);
 110       if(!dy) return TRUE;
 111       if(abs(Points[1].x-Points[0].x-(dx/dy)*
 112         BEZIERSHIFTDOWN(Points[1].y-Points[0].y)) > BEZIERPIXEL ||
 113         abs(Points[2].x-Points[0].x-(dx/dy)*
 114         BEZIERSHIFTDOWN(Points[2].y-Points[0].y)) > BEZIERPIXEL ) return FALSE;
 115       else
 116         return TRUE;
 117     }
 118 }
 119
 120 /* Helper for GDI_Bezier.
 121  * Just handles one Bezier, so Points should point to four POINTs
 122  */
 123 static void STDCALL GDI_InternalBezier( POINT *Points, POINT **PtsOut, INT *dwOut,
 124                                 INT *nPtsOut, INT level )
 125 {
 126   if(*nPtsOut == *dwOut) {
 127     *dwOut *= 2;
 128     *PtsOut = ExAllocatePool(NonPagedPool, *dwOut * sizeof(POINT));
 129   }
 130
 131   if(!level || BezierCheck(level, Points)) {
 132     if(*nPtsOut == 0) {
 133       (*PtsOut)[0].x = BEZIERSHIFTDOWN(Points[0].x);
 134       (*PtsOut)[0].y = BEZIERSHIFTDOWN(Points[0].y);
 135        *nPtsOut = 1;
 136     }
 137     (*PtsOut)[*nPtsOut].x = BEZIERSHIFTDOWN(Points[3].x);
 138     (*PtsOut)[*nPtsOut].y = BEZIERSHIFTDOWN(Points[3].y);
 139     (*nPtsOut) ++;
 140   } else {
 141     POINT Points2[4]; /* for the second recursive call */
 142     Points2[3]=Points[3];
 143     BEZIERMIDDLE(Points2[2], Points[2], Points[3]);
 144     BEZIERMIDDLE(Points2[0], Points[1], Points[2]);
 145     BEZIERMIDDLE(Points2[1],Points2[0],Points2[2]);
 146
 147     BEZIERMIDDLE(Points[1], Points[0],  Points[1]);
 148     BEZIERMIDDLE(Points[2], Points[1], Points2[0]);
 149     BEZIERMIDDLE(Points[3], Points[2], Points2[1]);
 150
 151     Points2[0]=Points[3];
 152
 153     /* do the two halves */
 154     GDI_InternalBezier(Points, PtsOut, dwOut, nPtsOut, level-1);
 155     GDI_InternalBezier(Points2, PtsOut, dwOut, nPtsOut, level-1);
 156   }
 157 }
 158
 159 /***********************************************************************
 160  *           GDI_Bezier   [INTERNAL]
 161  *   Calculate line segments that approximate -what microsoft calls- a bezier
 162  *   curve.
 163  *   The routine recursively divides the curve in two parts until a straight
 164  *   line can be drawn
 165  *
 166  *  PARAMS
 167  *
 168  *  Points  [I] Ptr to count POINTs which are the end and control points
 169  *              of the set of Bezier curves to flatten.
 170  *  count   [I] Number of Points.  Must be 3n+1.
 171  *  nPtsOut [O] Will contain no of points that have been produced (i.e. no. of
 172  *              lines+1).
 173  *
 174  *  RETURNS
 175  *
 176  *  Ptr to an array of POINTs that contain the lines that approximinate the
 177  *  Beziers.  The array is allocated on the process heap and it is the caller's
 178  *  responsibility to HeapFree it. [this is not a particularly nice interface
 179  *  but since we can't know in advance how many points will generate, the
 180  *  alternative would be to call the function twice, once to determine the size
 181  *  and a second time to do the work - I decided this was too much of a pain].
 182  */
 183 POINT * FASTCALL GDI_Bezier( const POINT *Points, INT count, INT *nPtsOut )
 184 {
 185   POINT *out;
 186   INT Bezier, dwOut = BEZIER_INITBUFSIZE, i;
 187
 188   if((count - 1) % 3 != 0) {
 189     return NULL;
 190   }
 191   *nPtsOut = 0;
 192   out = ExAllocatePool(NonPagedPool, dwOut * sizeof(POINT));
 193   for(Bezier = 0; Bezier < (count-1)/3; Bezier++) {
 194     POINT ptBuf[4];
 195     memcpy(ptBuf, Points + Bezier * 3, sizeof(POINT) * 4);
 196     for(i = 0; i < 4; i++) {
 197       ptBuf[i].x = BEZIERSHIFTUP(ptBuf[i].x);
 198       ptBuf[i].y = BEZIERSHIFTUP(ptBuf[i].y);
 199     }
 200     GDI_InternalBezier( ptBuf, &out, &dwOut, nPtsOut, BEZIERMAXDEPTH );
 201   }
 202
 203   return out;
 204 }
 205 /* EOF */