Line DDA Algorithm (Digital Differential Analyer)

Explanation

This C program demonstrates the Digital Differential Analyzer (DDA) algorithm, a fundamental method for drawing lines on a raster graphics display. The core idea behind DDA is to calculate points along a line by incrementally adding small fractional values to the current x and y coordinates, then rounding these to integer pixel positions.

Here's how the code works step-by-step:

1. Includes and Macro:

   • #include<graphics.h>: This header provides functions for graphics operations, such as initializing the graphics mode, drawing pixels, and closing the graphics window. It's part of the Borland Graphics Interface (BGI).
   • #include<conio.h>: This header provides console input/output functions, specifically getch() which is used here to pause the program until a key is pressed.
   • #define ROUND(a) ((int)(a+0.5)): This macro is defined to perform rounding to the nearest integer. For any floating-point number a, adding 0.5 to it and then type-casting to int effectively rounds it. For example, 3.2 + 0.5 = 3.7 -> (int)3.7 = 3, and 3.7 + 0.5 = 4.2 -> (int)4.2 = 4.

2. lineDDA Function:

   • This function takes four integer arguments: (xa, ya) representing the starting coordinates of the line and (xb, yb) representing the ending coordinates.
   • int dx = xb - xa; and int dy = yb - ya;: It calculates the total change in x (dx) and y (dy) required to draw the line.
   • int steps;: This variable will store the number of pixels to be drawn along the line.
   • if(abs(dx) > abs(dy)) steps = abs(dx); else steps = abs(dy);: The algorithm determines the number of steps based on the larger absolute difference between dx and dy. This ensures that the line is drawn smoothly, incrementing by at least one pixel along the major axis (the one with the larger change).
   • float xInc = dx / (float) steps; and float yInc = dy / (float) steps;: These calculate the incremental values for x and y for each step. For instance, if dx is 100 and steps is 100, xInc will be 1. If dy is 50 and steps is 100, yInc will be 0.5. This means for every step, x will increase by 1 and y will increase by 0.5.
   • float x = xa, y = ya;: Initializes the current x and y coordinates to the starting point. These are float to allow for fractional increments.
   • putpixel(ROUND(x), ROUND(y), WHITE);: The first pixel (the starting point) is drawn using the putpixel function, rounding its coordinates to the nearest integer.
   • for(k=0; k<steps; k++){ ... }: A loop iterates steps times to draw the rest of the line.
     • x += xInc; and y += yInc;: In each iteration, the current x and y coordinates are updated by adding their respective increments.
     • putpixel(ROUND(x), ROUND(y), WHITE);: The new pixel position, after rounding, is drawn in WHITE color.

3. main Function:

   • int gd = DETECT, gm;: gd (graphics driver) is initialized to DETECT, which tells initgraph to automatically detect the best graphics driver for the system. gm (graphics mode) will be set by initgraph.
   • initgraph(&gd, &gd, "C:\\TC\\BGI");: This crucial function initializes the graphics system. It loads the graphics driver and sets the graphics mode. The third argument "C:\\TC\\BGI" specifies the directory where the BGI driver files (like .BGI files) are located.
   • lineDDA(100, 200, 330, 400);: The lineDDA function is called to draw a line starting at pixel (100, 200) and ending at (330, 400).
   • getch();: This function waits for the user to press any key before the program continues. This keeps the graphics window open so the user can see the drawn line.
   • closegraph();: This function unloads the graphics driver and restores the screen to its original text mode, effectively closing the graphics window.

In essence, the program initializes a graphics environment, uses the DDA algorithm to calculate and draw a line pixel by pixel from a specified start to end point, waits for user input, and then closes the graphics display.

Algorithm

The DDA Line Drawing Algorithm implemented in the code follows these steps:

1. Input Coordinates: Get the starting coordinates (xa, ya) and ending coordinates (xb, yb) of the line.
2. Calculate Differences: Determine the total change in x (dx = xb - xa) and total change in y (dy = yb - ya).
3. Determine Number of Steps:
   • Compare the absolute values of dx and dy.
   • If |dx| > |dy|, the number of steps (steps) is set to |dx|.
   • Otherwise, steps is set to |dy|. This ensures that the line is sampled at a rate that covers all pixels along the longer axis.
4. Calculate Increments:
   • Calculate the x-increment per step: xInc = dx / (float)steps.
   • Calculate the y-increment per step: yInc = dy / (float)steps.
5. Initialize Current Position: Set the current floating-point coordinates (x, y) to the starting point (xa, ya).
6. Draw Initial Pixel: Draw the first pixel at (ROUND(x), ROUND(y)) in WHITE color.
7. Iterate and Draw:
   • Loop steps times (from k=0 to k < steps).
   • In each iteration:
     • Update x by adding xInc: x = x + xInc.
     • Update y by adding yInc: y = y + yInc.
     • Draw a pixel at the rounded current coordinates: putpixel(ROUND(x), ROUND(y), WHITE).
8. Graphics Cleanup: After drawing, wait for user input (getch()) and then close the graphics mode (closegraph()).