libctgraphics/bresenham.cpp

   1 /*****************************************************************************
   2 **  This is part of the CTSim program
   3 **  Copyright (c) 1983-2009 Kevin Rosenberg
   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 (version 2) as
   7 **  published by the Free Software Foundation.
   8 **
   9 **  This program is distributed in the hope that it will be useful,
  10 **  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 **  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 **  GNU General Public License for more details.
  13 **
  14 **  You should have received a copy of the GNU General Public License
  15 **  along with this program; if not, write to the Free Software
  16 **  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17 ******************************************************************************/
  18
  19 // REFERENCES FOR BRESENHAM'S ALGORITHM
  20 // Newman & Sproll, "Principals of Interactive Computer Graphics",  page 25.
  21 // Foley & van Dam, "Fundementals of Interactive Computer Graphics", page 433
  22
  23
  24 static void
  25 bresx (int x, int y, int major_inc, int minor_inc, int count, int d,
  26        int dinc1, int dinc2, void(*fn)(const int, const int))
  27 {
  28   do {
  29     (*fn)(x,y);
  30     x += major_inc;
  31
  32     if (d < 0)
  33       d += dinc2;
  34     else {
  35       d += dinc1;
  36       y += minor_inc;
  37     }
  38   } while (--count > 0);
  39 }
  40
  41
  42 static void
  43 bresy (int x, int y, int major_inc, int minor_inc, int count, int d,
  44        int dinc1, int dinc2, void(*fn)(const int, const int))
  45 {
  46   do {
  47     (*fn)(x,y);
  48     y += major_inc;
  49
  50     if (d < 0)
  51       d += dinc2;
  52     else {
  53       d += dinc1;
  54       x += minor_inc;
  55     }
  56   } while (--count > 0);
  57 }
  58
  59 void
  60 bresenham (int x1, int y1, int x2, int y2, void(*fn)(const int, const int))
  61 {0000
  62   int delta_x = x2 - x1;
  63   int dx_abs = (delta_x >= 0 ? delta_x : -delta_x);
  64
  65   int delta_y = y2 - y1;
  66   int dy_abs = (delta_y >= 0 ? delta_y : -delta_y);
  67
  68   // draws a line when abs(dx) >= abs(dy)
  69   if (dx_abs > dy_abs) {
  70     int count = dx_abs + 1;
  71     int major_inc = (x1 <= x2 ? 1 : -1);
  72     int minor_inc = (delta_y >= 0 ? 1 : -1);     // determine direction of minor axis
  73
  74     int d = dy_abs * 2 - dx_abs;      // Put decision variable in d
  75     int dinc1 = (dy_abs - dx_abs) * 2;
  76     int dinc2 = 2 * dy_abs;
  77
  78     bresx (x1, y1, major_inc, minor_inc, count, d, dinc1, dinc2, fn);
  79   } else {    //For plotting lines with abs(dy) > abs(sx)
  80     int count = dy_abs + 1;
  81
  82     int major_inc = (y1 <= y2 ? 1 : -1);
  83     int minor_inc = (delta_x >= 0 ? 1 : -1);      // check direction of minor axis
  84
  85     int d = dx_abs * 2 - dy_abs;
  86     int dinc1 = (dx_abs - dy_abs) * 2;
  87     int dinc2 = 2 * dx_abs;
  88
  89     bresy (x1, y1, major_inc, minor_inc, count, d, dinc1, dinc2, fn);
  90   }
  91 }