SHARE
TWEET

Derivation of Bresenham's algorithm

a guest Feb 15th, 2016 364 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Floating point line drawing algorithm. We will assume that x1 < x2, y1 < y2, and that (x2 - x1) >= (y2 - y1) for simplicity:
  2.  
  3. void
  4. draw_line(int x1, int y1, int x2, int y2)
  5. {
  6.     float y = y1 + 0.5f;
  7.     float dy = (float)(y2 - y1) / (x2 - x1); // NOTE: dy <= 1.0f
  8.     for (int x = x1; x <= x2; ++x) {
  9.         plot(x, (int)y);
  10.         y += dy;
  11.     }
  12. }
  13.  
  14. Now separate the integer and floating-point parts of y:
  15.  
  16. void
  17. draw_line(int x1, int y1, int x2, int y2)
  18. {
  19.     int yi = y1;
  20.     float yf = 0.5f;
  21.     float dy = (float)(y2 - y1) / (x2 - x1);
  22.     for (int x = x1; x <= x2; ++x) {
  23.         plot(x, yi);
  24.         yf += dy;
  25.         if (yf >= 1.0f) {
  26.             yf -= 1.0f;
  27.             ++yi;
  28.         }
  29.     }
  30. }
  31.  
  32. Now multiply dy and yf by 2*(x2 - x1) everywhere to make them integers:
  33.  
  34.  
  35. void
  36. draw_line(int x1, int y1, int x2, int y2)
  37. {
  38.     int yi = y1;
  39.     int yf = x2 - x1;
  40.     int dy = 2 * (y2 - y1);
  41.     for (int x = x1; x <= x2; ++x) {
  42.         plot(x, yi);
  43.         yf += dy;
  44.         if (yf >= 2 * (x2 - x1)) {
  45.             yf -= 2 * (x2 - x1);
  46.             ++yi;
  47.         }
  48.     }
  49. }
  50.  
  51. We now have integer line drawing!
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top