src/freenet/captcha/easybmp/EasyBMP_Geometry.cpp

   1 /*************************************************\r
   2 *                                                *\r
   3 *  EasyBMP Cross-Platform Windows Bitmap Library * \r
   4 *                                                *\r
   5 *  Author: Paul Macklin                          *\r
   6 *   email: pmacklin@math.uci.edu                 *\r
   7 *                                                *\r
   8 *    file: EasyBMP_Geometry.h                    *\r
   9 *    date: 2-21-2005                             *\r
  10 * version: 1.05.00                               *\r
  11 *                                                *\r
  12 *   License: BSD (revised)                       *\r
  13 * Copyright: 2005-2006 by the EasyBMP Project    * \r
  14 *                                                *\r
  15 * description: draw simple geometric objects     *\r
  16 *                                                *\r
  17 *************************************************/\r
  18 \r
  19 #include "../../../../include/freenet/captcha/easybmp/EasyBMP_Geometry.h"\r
  20 \r
  21 int ebmpRound( double input )\r
  22 {\r
  23  double output = floor( input );\r
  24  if( output - input >= 0.50 )\r
  25  { return (int) ( output+1 ); }\r
  26  return (int) output;\r
  27 }\r
  28 \r
  29 double InverseAngle( double Xdir, double Ydir )\r
  30 {\r
  31  double pi = 3.14159265358979;\r
  32  double Norm = sqrt( Xdir*Xdir + Ydir*Ydir );\r
  33  if( Norm <= 0.25 )\r
  34  { return 0.0; }\r
  35  Xdir /= Norm; \r
  36  Ydir /= Norm;\r
  37 \r
  38  double Xabs = fabs( Xdir );\r
  39  double Yabs = fabs( Ydir );\r
  40  double theta = 0.5*( acos( Xabs ) + asin( Yabs ) );\r
  41 \r
  42  if( Xdir >= 0.0 && Ydir >= 0.0 )\r
  43  { return theta; }\r
  44  if( Xdir < 0.0 && Ydir >= 0.0 )\r
  45  { return pi - theta; }\r
  46  if( Xdir < 0.0 && Ydir < 0.0 )\r
  47  { return pi + theta; }\r
  48  return 2*pi - theta; \r
  49 }\r
  50 \r
  51 double LineFunction( double SlopeX , double SlopeY, int StartX, int StartY, double TestX, double TestY )\r
  52 {\r
  53  return fabs( SlopeX*(TestY-StartY) - SlopeY*(TestX-StartX) );\r
  54 }\r
  55 \r
  56 void DrawAALine( BMP &Image , int FromX, int FromY, int ToX, int ToY , RGBApixel Color )\r
  57 {\r
  58  double SlopeX = ToX-FromX;\r
  59  double SlopeY = ToY-FromY;\r
  60 \r
  61  if( fabs( SlopeX ) <= 0.8 && fabs( SlopeY ) <= 0.8 ) // nothing to do; don't bother\r
  62  {\r
  63   return;\r
  64  }\r
  65  double Norm = sqrt( Square( SlopeX ) + Square( SlopeY ) );\r
  66  SlopeX /= Norm; \r
  67  SlopeY /= Norm;\r
  68 \r
  69  // bounds checking\r
  70 \r
  71  if( FromX >= Image.TellWidth() )\r
  72  { FromX = Image.TellWidth()-1; }\r
  73  if( FromX < 0 )\r
  74  { FromX = 0; }\r
  75  if( ToX >= Image.TellWidth() )\r
  76  { ToX = Image.TellWidth()-1; }\r
  77  if( ToX < 0 )\r
  78  { ToX = 0; }\r
  79 \r
  80  if( FromY >= Image.TellHeight() )\r
  81  { FromY = Image.TellHeight()-1; }\r
  82  if( FromY < 0 )\r
  83  { FromY = 0; }\r
  84  if( ToY >= Image.TellHeight() )\r
  85  { ToY = Image.TellHeight()-1; }\r
  86  if( ToY < 0 )\r
  87  { ToY = 0; }\r
  88 \r
  89  int LeftI = FromX;\r
  90  int RightI = ToX;\r
  91  if( RightI < LeftI ){ int temp = LeftI; LeftI = RightI; RightI = temp; }\r
  92  int LeftJ = FromY;\r
  93  int RightJ = ToY;\r
  94  if( RightJ < LeftJ ){ int temp = LeftJ; LeftJ = RightJ; RightJ = temp; }\r
  95  \r
  96  int i,j;\r
  97  for( i=LeftI ; i <= RightI ; i++ )\r
  98  {\r
  99   for( j=LeftJ ; j <= RightJ ; j++ )\r
 100   {\r
 101    double ii=0;\r
 102    double jj=0;\r
 103    double dx = 0.25;\r
 104    double dy = 0.25;\r
 105    double x = i-1.5*dx;\r
 106    double y = j-1.5*dx;\r
 107    \r
 108    double Temp = 0.0;\r
 109    \r
 110    for( ii=-2; ii<=1 ; ii++)\r
 111    {\r
 112     for( jj=-2 ; jj<=1 ; jj++)\r
 113     {\r
 114      x = i+ii*dx+0.5*dx;\r
 115      y = j+jj*dy+0.5*dy;\r
 116      double Temp1 = LineFunction( SlopeX, SlopeY , FromX, FromY, x,y ); \r
 117      if( Temp1 <= 0.5 ){ Temp1 = 1.0; }else{ Temp1 = 0.0; }\r
 118      Temp+=Temp1;\r
 119     }   \r
 120    }\r
 121    \r
 122    Temp /= 16.0;\r
 123    double MinValue = 0.03125; // 1.0/32.0\r
 124    \r
 125    if( Temp > MinValue )\r
 126    {\r
 127     Image(i,j)->Red = (ebmpBYTE) (unsigned int) (  (1.0-Temp)*( (double) Image(i,j)->Red )\r
 128                                                         +Temp*( (double) Color.Red ) );\r
 129     Image(i,j)->Green = (ebmpBYTE) (unsigned int) (  (1.0-Temp)*( (double) Image(i,j)->Green )\r
 130                                                         +Temp*( (double) Color.Green ) );\r
 131     Image(i,j)->Blue = (ebmpBYTE) (unsigned int) (  (1.0-Temp)*( (double) Image(i,j)->Blue )\r
 132                                                           +Temp*( (double) Color.Blue ) );\r
 133    }\r
 134    \r
 135   }\r
 136  }\r
 137  \r
 138  return; \r
 139 }\r
 140 \r
 141 void DrawFastLine( BMP &Image , int FromX, int FromY, int ToX, int ToY , RGBApixel Color )\r
 142 {\r
 143  // bounds checking\r
 144 \r
 145  if( FromX >= Image.TellWidth() )\r
 146  { FromX = Image.TellWidth()-1; }\r
 147  if( FromX < 0 )\r
 148  { FromX = 0; }\r
 149  if( ToX >= Image.TellWidth() )\r
 150  { ToX = Image.TellWidth()-1; }\r
 151  if( ToX < 0 )\r
 152  { ToX = 0; }\r
 153 \r
 154  if( FromY >= Image.TellHeight() )\r
 155  { FromY = Image.TellHeight()-1; }\r
 156  if( FromY < 0 )\r
 157  { FromY = 0; }\r
 158  if( ToY >= Image.TellHeight() )\r
 159  { ToY = Image.TellHeight()-1; }\r
 160  if( ToY < 0 )\r
 161  { ToY = 0; }\r
 162 \r
 163  // source: http://www.gamedev.net/reference/articles/article1275.asp\r
 164 \r
 165  int dX = ToX - FromX;\r
 166  int dY = ToY - FromY;\r
 167  \r
 168  if( dX == 0 && dY == 0 ) // nothing to do; don't bother\r
 169  {\r
 170   return;\r
 171  }\r
 172  \r
 173  int Xinc1 = 1;\r
 174  if( dX < 0 )\r
 175  { Xinc1 = -1; dX = -dX; } \r
 176  int Yinc1 = 1;\r
 177  if( dY < 0 )\r
 178  { Yinc1 = -1; dY = -dY; }\r
 179  \r
 180  int x = FromX;               // Start x off at the first pixel\r
 181  int y = FromY;               // Start y off at the first pixel\r
 182  \r
 183  int Xinc2 = Xinc1;\r
 184  int Yinc2 = Yinc1;\r
 185  \r
 186  double Denominator;\r
 187  double Numerator;\r
 188  int NumberToAdd;\r
 189  int NumberOfPixels;\r
 190 \r
 191  if ( dX >= dY )         // There is at least one x-value for every y-value\r
 192  {\r
 193   Xinc1 = 0;                  // Don't change the x when numerator >= denominator\r
 194   Yinc2 = 0;                  // Don't change the y for every iteration\r
 195   Denominator = dX+0.0;\r
 196   Numerator = 0.5*dX;\r
 197   NumberToAdd = dY;\r
 198   NumberOfPixels = dX;         // There are more x-values than y-values\r
 199  }\r
 200  else                          // There is at least one y-value for every x-value\r
 201  {\r
 202   Xinc2 = 0;                  // Don't change the x for every iteration\r
 203   Yinc1 = 0;                  // Don't change the y when numerator >= denominator\r
 204   Denominator = dY+0.0;\r
 205   Numerator = 0.5*dY;\r
 206   NumberToAdd = dX;\r
 207   NumberOfPixels = dY;         // There are more y-values than x-values\r
 208  }\r
 209  \r
 210  int CurrentPixel;\r
 211 \r
 212  for (CurrentPixel = 0; CurrentPixel <= NumberOfPixels; CurrentPixel++ )\r
 213  {\r
 214   Image(x,y)->Red = Color.Red;\r
 215   Image(x,y)->Green = Color.Green;\r
 216   Image(x,y)->Blue = Color.Blue;\r
 217   \r
 218   Numerator += NumberToAdd;   // Increase the numerator by the top of the fraction\r
 219   if( Numerator >= Denominator ) // Check if numerator >= denominator\r
 220   {\r
 221     Numerator -= Denominator; // Calculate the new numerator value\r
 222     x += Xinc1;               // Change the x as appropriate\r
 223     y += Yinc1;               // Change the y as appropriate\r
 224   }\r
 225   x += Xinc2;                 // Change the x as appropriate\r
 226   y += Yinc2;                 // Change the y as appropriate\r
 227  }\r
 228  \r
 229  return; \r
 230 }\r
 231 \r
 232 void DrawArc( BMP &Image , double CenterX, double CenterY , double Radius, \r
 233               double FromTheta, double ToTheta , RGBApixel Color )\r
 234 {\r
 235  double pi = 3.14159265358979;\r
 236 \r
 237  while( ToTheta < FromTheta )\r
 238  { ToTheta += 2*pi; }\r
 239 \r
 240  double Arclength = (ToTheta-FromTheta)*Radius;\r
 241  if( fabs( Arclength ) <= 1e-5 ) // if it's short, don't bother\r
 242  { return; }\r
 243  \r
 244  // set up the final circle first\r
 245  \r
 246  BMP Downsampled;\r
 247  int FinalWidth = (int) floor( 2.0*Radius + 1.0); // was ceil ,also tried Round\r
 248  \r
 249  // new for testing\r
 250  Radius = 0.5*(FinalWidth-1.0);\r
 251  // end new for testing \r
 252  \r
 253  int FinalHeight = FinalWidth;\r
 254  Downsampled.SetSize( FinalWidth , FinalHeight );\r
 255  \r
 256  // make a temporary circle of double resolution\r
 257 \r
 258  BMP Temp;\r
 259  double TempRadius = 2.0*Radius; \r
 260  \r
 261  Temp.SetSize( 2*FinalWidth, 2*FinalHeight );\r
 262  double dTheta = 1.0/TempRadius;\r
 263  \r
 264  double CenterXtemp = FinalWidth - 0.5; // was TempRadius + .5\r
 265  double CenterYtemp = FinalHeight - 0.5; // was TempRadius + 0.5;\r
 266 \r
 267  int x,y;\r
 268  \r
 269  double OuterRadiusSquared = TempRadius+1.0;\r
 270  OuterRadiusSquared *= OuterRadiusSquared;\r
 271  double InnerRadiusSquared = TempRadius-1.0;\r
 272  InnerRadiusSquared *= InnerRadiusSquared;\r
 273  \r
 274  for( x=0 ; x < Temp.TellWidth() ;x++)\r
 275  {\r
 276   for( y=0 ; y < Temp.TellHeight() ; y++)\r
 277   {\r
 278    double X = x-CenterXtemp;\r
 279    double Y = y-CenterYtemp;\r
 280    double TempRadiusSquared = X*X + Y*Y;\r
 281    \r
 282    if( InnerRadiusSquared <= TempRadiusSquared && \r
 283        TempRadiusSquared <= OuterRadiusSquared )\r
 284    {\r
 285     double Angle = InverseAngle( X, Y );\r
 286     bool PlotIt = false;\r
 287     if( FromTheta <= Angle && Angle <= ToTheta )\r
 288     { PlotIt = true; }\r
 289     Angle += 2*pi;\r
 290     if( FromTheta <= Angle && Angle <= ToTheta )\r
 291     { PlotIt = true; }\r
 292     Angle -= 4*pi;\r
 293     if( FromTheta <= Angle && Angle <= ToTheta )\r
 294     { PlotIt = true; }\r
 295     \r
 296     if( PlotIt )\r
 297     { Temp(x,y)->Red = 0; }\r
 298    }\r
 299   }\r
 300  }\r
 301  \r
 302  // downsample to anti-alias\r
 303  \r
 304  int i,j;\r
 305  for( i=0 ; i < Downsampled.TellWidth() ; i++ )\r
 306  {\r
 307   for( j=0 ; j < Downsampled.TellHeight() ; j++ )\r
 308   {\r
 309    double TempRed = 0.0;\r
 310   \r
 311    int k,ell;\r
 312    for( k=0 ; k <= 1 ; k++ )\r
 313    {\r
 314     for( ell=0 ; ell <= 1 ; ell++ )\r
 315     {\r
 316      int I = 2*i+k;\r
 317      int J = 2*j+ell;\r
 318      TempRed += (double) Temp(I,J)->Red;\r
 319     }\r
 320    }\r
 321    TempRed /= 4.0;\r
 322    \r
 323    Downsampled(i,j)->Red = (ebmpBYTE) TempRed;\r
 324   }\r
 325  }\r
 326  \r
 327  // paste with alpha blending \r
 328  \r
 329  int DestinationTopLeft = ebmpRound( CenterX - Radius );\r
 330  int DestinationTopRight = ebmpRound( CenterY - Radius );\r
 331  \r
 332  for( i=0 ; i < Downsampled.TellWidth() ; i++) \r
 333  {\r
 334   for( j=0 ; j < Downsampled.TellHeight() ; j++)\r
 335   {\r
 336    int DestinationI = DestinationTopLeft+i;\r
 337    int DestinationJ = DestinationTopRight+j;\r
 338    if( DestinationI >= 0 && DestinationI < Image.TellWidth() &&\r
 339        DestinationJ >= 0 && DestinationJ < Image.TellHeight() )\r
 340    {\r
 341     double alpha = (255.0 - Downsampled(i,j)->Red )/255.0;\r
 342     Image(DestinationI,DestinationJ)->Red = (ebmpBYTE) ( \r
 343       (1.0-alpha)*Image(DestinationI,DestinationJ)->Red \r
 344     + (alpha)*Color.Red );\r
 345     Image(DestinationI,DestinationJ)->Green = (ebmpBYTE) ( \r
 346       (1.0-alpha)*Image(DestinationI,DestinationJ)->Green \r
 347     + (alpha)*Color.Green );\r
 348     Image(DestinationI,DestinationJ)->Blue = (ebmpBYTE) ( \r
 349       (1.0-alpha)*Image(DestinationI,DestinationJ)->Blue \r
 350     + (alpha)*Color.Blue );\r
 351    }\r
 352   \r
 353   }\r
 354  }\r
 355  \r
 356  return;\r
 357 }\r
 358 \r
 359 void DrawLine( BMP &Image , int FromX , int FromY, int ToX, int ToY, RGBApixel Color )\r
 360 {\r
 361  if( FromX != ToX && FromY != ToY )\r
 362  {\r
 363   DrawAALine( Image, FromX, FromY, ToX, ToY, Color);\r
 364  } \r
 365  DrawFastLine( Image, FromX, FromY, ToX, ToY, Color); \r
 366  return;\r
 367 }\r