 # 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