Guest User

Derivation of Bresenham's algorithm

a guest
Feb 15th, 2016
398
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