Bresenham's Line algorithm

Explanation

This C code implements Bresenham's Line Algorithm, a fundamental algorithm in computer graphics for drawing lines on a digital display. The program uses the graphics.h library, which is a legacy library primarily associated with DOS-based C compilers like Turbo C/C++.

The core functionality resides in the lineBres function, which takes two points (xa, ya and xb, yb) as input and draws a line between them using white pixels. The algorithm's main advantage is that it uses only integer arithmetic, making it very efficient and fast compared to algorithms that rely on floating-point calculations (like DDA).

The lineBres function first determines the absolute differences in x and y coordinates (dx and dy). It then divides the problem into two main cases based on the slope of the line:

1. Slope magnitude <= 1 (i.e., dx >= dy): In this case, the line is "more horizontal." The algorithm iterates along the x-axis, incrementing x by 1 in each step. It then decides whether to keep y the same or increment/decrement y by 1, based on a decision parameter p. The step variable ensures y moves in the correct direction (up or down).
2. Slope magnitude > 1 (i.e., dx < dy): Here, the line is "more vertical." The algorithm iterates along the y-axis, incrementing y by 1 in each step. It decides whether to keep x the same or increment/decrement x by 1, again using the decision parameter p. The step variable ensures x moves in the correct direction (left or right).

The main function initializes the graphics environment using initgraph, then makes multiple calls to lineBres with different coordinate pairs. These calls collectively draw a specific shape, which appears to be an outline of a house with a window and a door. Finally, getch() waits for user input, and closegraph() shuts down the graphics system.

Algorithm

Bresenham's Line Algorithm works by incrementally determining the next pixel to plot based on a decision parameter that minimizes the error between the true line and the plotted pixel. Here are the steps:

1. Initialization:

   • Read the two endpoints of the line: (xa, ya) and (xb, yb).
   • Calculate the absolute differences: dx = |xa - xb| and dy = |ya - yb|.
   • Determine the starting pixel (x, y) and the ending coordinate (xEnd or yEnd) for iteration. This is done to ensure the line is drawn from left to right (for dx >= dy) or bottom to top (for dx < dy).
   • Calculate a step variable to determine the direction of change for the non-dominant axis (e.g., if y should increase or decrease).

2. Case 1: Slope magnitude <= 1 (dx >= dy):

   • If xa > xb, swap (xa, ya) and (xb, yb) to always draw from left to right. Set x = xa, y = ya, xEnd = xb. Adjust step based on ya vs yb.
   • Initialize the decision parameter: p = 2 * dy - dx.
   • Plot the initial pixel (x, y).
   • Loop: While x < xEnd:
     • Increment x.
     • If p < 0 (the midpoint is below the line):
       • Update p = p + 2 * dy. (y remains the same)
     • Else (the midpoint is above or on the line):
       • Update y = y + step.
       • Update p = p + 2 * (dy - dx).
     • Plot the new pixel (x, y).

3. Case 2: Slope magnitude > 1 (dx < dy):

   • If ya > yb, swap (xa, ya) and (xb, yb) to always draw from bottom to top. Set y = ya, x = xa, yEnd = yb. Adjust step based on xa vs xb.
   • Initialize the decision parameter: p = 2 * dx - dy.
   • Plot the initial pixel (x, y).
   • Loop: While y < yEnd:
     • Increment y.
     • If p < 0 (the midpoint is to the left of the line):
       • Update p = p + 2 * dx. (x remains the same)
     • Else (the midpoint is to the right of or on the line):
       • Update x = x + step.
       • Update p = p + 2 * (dx - dy).
     • Plot the new pixel (x, y).