Line Drawing Algorithms
* Digital Differential Analyzer (DDA) Algorithm
* Bresenham’s Line Algorithm
* Parallel Line Algorithm
* Digital Differential Analyzer (DDA) Algorithm
* Bresenham’s Line Algorithm
* Parallel Line Algorithm
The Cartesian slope-intercept equation for a straight line is
y = m . x + b (1)
Where m as slope of the line and b as the y intercept
Given that the two endpoints of a line segment are specified at positions (x1, y1) and (x2, y2) as in figure we can determine the values for the slope m and y intercept b with the following calculations
Figure: Line Path between endpoint positions (x1, y1) and (x2, y2)
m = Δy / Δx = y2 - y1 / x2 - x1 (2)
b = y1 - m . x1 (3)
For any given x interval Δx along a line, we can compute the corresponding y interval Δ y
Δy = m Δx (4)
We can obtain the x interval Δx corresponding to a specified Δy as
Δ x = Δ y/m (5)
For lines with slope magnitudes |m| < 1, Δx can be set proportional to a small horizontal deflection voltage and the corresponding vertical deflection is then set proportional to Δy as calculated from Eq (4).
For lines whose slopes have magnitudes |m| > 1 , Δy can be set proportional to a small vertical deflection voltage with the corresponding horizontal deflection voltage set proportional to Δx, calculated from Eq (5) For lines with m = 1, Δx = Δy and the horizontal and vertical deflections voltage are equal.
Figure: Straight line Segment with five sampling positions along the x axis between x1 and x2
y = m . x + b (1)
Where m as slope of the line and b as the y intercept
Given that the two endpoints of a line segment are specified at positions (x1, y1) and (x2, y2) as in figure we can determine the values for the slope m and y intercept b with the following calculations
m = Δy / Δx = y2 - y1 / x2 - x1 (2)
b = y1 - m . x1 (3)
For any given x interval Δx along a line, we can compute the corresponding y interval Δ y
Δy = m Δx (4)
We can obtain the x interval Δx corresponding to a specified Δy as
Δ x = Δ y/m (5)
For lines with slope magnitudes |m| < 1, Δx can be set proportional to a small horizontal deflection voltage and the corresponding vertical deflection is then set proportional to Δy as calculated from Eq (4).
For lines whose slopes have magnitudes |m| > 1 , Δy can be set proportional to a small vertical deflection voltage with the corresponding horizontal deflection voltage set proportional to Δx, calculated from Eq (5) For lines with m = 1, Δx = Δy and the horizontal and vertical deflections voltage are equal.
Digital Differential Analyzer (DDA) Algortihm
The digital differential analyzer (DDA) is a scan-conversion line algorithm based on
calculation either Δy or Δx
The line at unit intervals in one coordinate and determine corresponding integer values nearest the line path for the other coordinate.
A line with positive slop, if the slope is less than or equal to 1, at unit x intervals (Δx = 1) and compute each successive y values as
yk+1 = yk + m (6)
Subscript k takes integer values starting from 1 for the first point and increases by 1 until the final endpoint is reached. m can be any real number between 0 and 1 and, the calculated y values must be rounded to the nearest integer
For lines with a positive slope greater than 1 we reverse the roles of x and y, (Δy = 1) and calculate each succeeding x value as
xk+1 = xk + (1/m) (7)
Equation (6) and (7) are based on the assumption that lines are to be processed from the left endpoint to the right endpoint.
If this processing is reversed, Δx = -1 that the starting endpoint is at the right
yk+1 = yk – m (8)
When the slope is greater than 1 and Δy = -1 with
xk+1 = xk-1(1/m) (9)
If the absolute value of the slope is less than 1 and the start endpoint is at the left, we set Δx = 1 and calculate y values with Eq. (6)
When the start endpoint is at the right (for the same slope), we set Δx = -1 and obtain y positions from Eq. (8). Similarly, when the absolute value of a negative slope is greater than 1, we use Δy = -1 and Eq. (9) or we use Δy = 1 and Eq. (7).
Algorithm#define ROUND(a) ((int)(a+0.5))
void lineDDA (int xa, int ya, int xb, int yb)
{
int dx = xb - xa, dy = yb - ya, steps, k;
float xIncrement, yIncrement, x = xa, y = ya;
if (abs (dx) > abs (dy) steps = abs (dx) ;
else steps = abs dy);
xIncrement = dx / (float) steps;
yIncrement = dy / (float) steps
setpixel (ROUND(x), ROUND(y) ):
for (k = 0; k<steps; k++)
{
x += xIncrement;
y += yIncrement;
setpixel (ROUND(x), ROUND(y));
}
}
Algorithm Description:Step 1: Accept Input as two endpoint pixel positions
Step 2: Horizontal and vertical differences between the endpoint positions are assigned to parameters dx and dy (Calculate dx = xb-xa and dy = yb-ya).
Step 3: The difference with the greater magnitude determines the value of parameter steps.
Step 4: Starting with pixel position (xa, ya), determine the offset needed at each step to generate the next pixel position along the line path.
Step 5: loop the following process for steps number of times
a. Use a unit of increment or decrement in the x and y direction
b. if xa is less than xb the values of increment in the x and y directions are 1 and m
c. if xa is greater than xb then the decrements -1 and – m are used.
Example : Consider the line from (0,0) to (4,6)
1. xa = 0, ya = 0 and xb = 4 yb = 6
2. dx = xb - xa = 4-0 = 4 and dy = yb - ya = 6-0 = 6
3. x = 0 and y = 0
4. 4 > 6 (false) so, steps = 6
5. Calculate xIncrement = dx/steps = 4 / 6 = 0.66 and yIncrement = dy/steps = 6/6 = 1
6. Setpixel(x, y) = Setpixel(0, 0) (Starting Pixel Position)
7. Iterate the calculation for xIncrement and yIncrement for steps(6) number of times
8. Tabulation of the each iteration
1. It is the simplest algorithm
2. It is a is a faster method for calculating pixel positions
Disadvantages of DDA Algorithm
1. Floating point arithmetic in DDA algorithm is still time-consuming
2. End point accuracy is poor
Bresenham’s Line Algorithm
An accurate and efficient raster line generating algorithm developed by Bresenham, that uses only incremental integer calculations.
In addition, Bresenham’s line algorithm can be adapted to display circles and other
curves.
To illustrate Bresenham's approach, we- first consider the scan-conversion process for lines with positive slope less than 1.
Pixel positions along a line path are then determined by sampling at unit x intervals. Starting from the left endpoint (x0, y0) of a given line, we step to each successive column (x position) and plot the pixel whose scan-line y value is closest to the line path.
To determine the pixel (xk, yk) is to be displayed, next to decide which pixel to plot the column xk+1 = xk+1. (xk+1, yk) and (xk+1, yk+1). At sampling position xk+1, we label vertical pixel separations from the mathematical line path as d1 and d2. The y coordinate on the mathematical line at pixel column position xk+1 is calculated as
y = m(xk+1)+b (1)
Then
d1 = y - yk
= m(xk+1)+b - yk
d2 = (yk+1) -y
= yk+1-m(xk+1) -b
To determine which of the two pixel is closest to the line path, efficient test that is based on the difference between the two pixel separations
d1- d2 = 2m(xk+1) - 2yk+ 2b - 1 (2)
A decision parameter Pk for the kth step in the line algorithm can be obtained by rearranging equation (2). By substituting m = Δy/Δx where Δx and Δy are the vertical and horizontal separations of the endpoint positions and defining the decision parameter as
pk = Δx (d1- d2)
= 2Δy xk.- 2Δx. yk + c (3)
The sign of pk is the same as the sign of d1- d2, since Δx > 0
Parameter C is constant and has the value 2Δy + Δx(2b - 1) which is independent of the pixel position and will be eliminated in the recursive calculations for Pk.
If the pixel at yk is “closer” to the line path than the pixel at yk+1 (d1 < d2) than decision parameter Pk is negative. In this case, plot the lower pixel, otherwise plot the upper pixel. Coordinate changes along the line occur in unit steps in either the x or y directions.
To obtain the values of successive decision parameters using incremental integer calculations. At steps k+1, the decision parameter is evaluated from equation (3) as
Pk+1 = 2Δy xk+1 - 2Δx. yk+1 + c
Subtracting the equation (3) from the preceding equation
Pk+1 - Pk = 2Δy (xk+1 - xk) - 2Δx(yk+1 - yk)
But xk+1= xk + 1 so that
Pk+1 = Pk+ 2Δy - 2Δx(yk+1 - yk) (4)
Where the term yk+1 - yk is either 0 or 1 depending on the sign of parameter Pk
This recursive calculation of decision parameter is performed at each integer x position, starting at the left coordinate endpoint of the line.
The first parameter P0 is evaluated from equation at the starting pixel position (x0, y0) and with m evaluated as Δy/Δx
P0 = 2Δy - Δx (5)
Bresenham’s line drawing for a line with a positive slope less than 1 in the following outline of the algorithm.
The constants 2Δy and 2Δy - 2Δx are calculated once for each line to be scan converted.
An accurate and efficient raster line generating algorithm developed by Bresenham, that uses only incremental integer calculations.
In addition, Bresenham’s line algorithm can be adapted to display circles and other
curves.
To illustrate Bresenham's approach, we- first consider the scan-conversion process for lines with positive slope less than 1.
Pixel positions along a line path are then determined by sampling at unit x intervals. Starting from the left endpoint (x0, y0) of a given line, we step to each successive column (x position) and plot the pixel whose scan-line y value is closest to the line path.
To determine the pixel (xk, yk) is to be displayed, next to decide which pixel to plot the column xk+1 = xk+1. (xk+1, yk) and (xk+1, yk+1). At sampling position xk+1, we label vertical pixel separations from the mathematical line path as d1 and d2. The y coordinate on the mathematical line at pixel column position xk+1 is calculated as
y = m(xk+1)+b (1)
Then
d1 = y - yk
= m(xk+1)+b - yk
d2 = (yk+1) -y
= yk+1-m(xk+1) -b
To determine which of the two pixel is closest to the line path, efficient test that is based on the difference between the two pixel separations
d1- d2 = 2m(xk+1) - 2yk+ 2b - 1 (2)
A decision parameter Pk for the kth step in the line algorithm can be obtained by rearranging equation (2). By substituting m = Δy/Δx where Δx and Δy are the vertical and horizontal separations of the endpoint positions and defining the decision parameter as
pk = Δx (d1- d2)
= 2Δy xk.- 2Δx. yk + c (3)
The sign of pk is the same as the sign of d1- d2, since Δx > 0
Parameter C is constant and has the value 2Δy + Δx(2b - 1) which is independent of the pixel position and will be eliminated in the recursive calculations for Pk.
If the pixel at yk is “closer” to the line path than the pixel at yk+1 (d1 < d2) than decision parameter Pk is negative. In this case, plot the lower pixel, otherwise plot the upper pixel. Coordinate changes along the line occur in unit steps in either the x or y directions.
To obtain the values of successive decision parameters using incremental integer calculations. At steps k+1, the decision parameter is evaluated from equation (3) as
Pk+1 = 2Δy xk+1 - 2Δx. yk+1 + c
Subtracting the equation (3) from the preceding equation
Pk+1 - Pk = 2Δy (xk+1 - xk) - 2Δx(yk+1 - yk)
But xk+1= xk + 1 so that
Pk+1 = Pk+ 2Δy - 2Δx(yk+1 - yk) (4)
Where the term yk+1 - yk is either 0 or 1 depending on the sign of parameter Pk
This recursive calculation of decision parameter is performed at each integer x position, starting at the left coordinate endpoint of the line.
The first parameter P0 is evaluated from equation at the starting pixel position (x0, y0) and with m evaluated as Δy/Δx
P0 = 2Δy - Δx (5)
Bresenham’s line drawing for a line with a positive slope less than 1 in the following outline of the algorithm.
The constants 2Δy and 2Δy - 2Δx are calculated once for each line to be scan converted.
Bresenham’s line Drawing Algorithm for |m| < 1
1. Input the two line endpoints and store the left end point in (x0, y0)
2. Load (x0, y0) into frame buffer, ie. Plot the first point.
3. Calculate the constants Δx, Δy, 2Δy and obtain the starting value for the decision parameter as P0 = 2Δy - Δx
4. At each xk along the line, starting at k = 0 perform the following test
If Pk < 0, the next point to plot is (xk+1, yk) and Pk+1 = Pk + 2Δy
Otherwise, the next point to plot is (xk+1, yk+1) and Pk+1 = Pk + 2Δy - 2Δx
5. Perform step4 Δx times.
1. Input the two line endpoints and store the left end point in (x0, y0)
2. Load (x0, y0) into frame buffer, ie. Plot the first point.
3. Calculate the constants Δx, Δy, 2Δy and obtain the starting value for the decision parameter as P0 = 2Δy - Δx
4. At each xk along the line, starting at k = 0 perform the following test
If Pk < 0, the next point to plot is (xk+1, yk) and Pk+1 = Pk + 2Δy
Otherwise, the next point to plot is (xk+1, yk+1) and Pk+1 = Pk + 2Δy - 2Δx
5. Perform step4 Δx times.
Implementation of Bresenham Line drawing Algorithm
void lineBres (int xa, int ya, int xb, int yb)
{
int dx = abs( xa – xb) , dy = abs (ya - yb);
int p = 2 * dy – dx;
int twoDy = 2 * dy, twoDyDx = 2 *(dy - dx);
int x , y, xEnd;
/* Determine which point to use as start, which as end * /
if (xa > x b )
{
x = xb;
y = yb;
xEnd = xa;
}
else
{
x = xa;
y = ya;
xEnd = xb;
}
setPixel(x, y);
while(x < xEnd)
{
x++;
if (p < 0)
p+ = twoDy;
else
{
y++;
p+ = twoDyDx;
}
setPixel(x,y);
}
}
void lineBres (int xa, int ya, int xb, int yb)
{
int dx = abs( xa – xb) , dy = abs (ya - yb);
int p = 2 * dy – dx;
int twoDy = 2 * dy, twoDyDx = 2 *(dy - dx);
int x , y, xEnd;
/* Determine which point to use as start, which as end * /
if (xa > x b )
{
x = xb;
y = yb;
xEnd = xa;
}
else
{
x = xa;
y = ya;
xEnd = xb;
}
setPixel(x, y);
while(x < xEnd)
{
x++;
if (p < 0)
p+ = twoDy;
else
{
y++;
p+ = twoDyDx;
}
setPixel(x,y);
}
}
Example: Consider the line with endpoints (20,10) to (30,18)
The line has the slope m = (18 - 10)/(30 - 20) = 8/10 = 0.8
Δx = 10 Δy = 8
The initial decision parameter has the value
p0 = 2Δy - Δx = 6
and the increments for calculating successive decision parameters are
2Δy = 16 2Δy - 2 Δx = -4
We plot the initial point (x0, y0) = (20, 10) and determine successive pixel positions along the line path from the decision parameter as
Tabulation
* Algorithm is Fast
* Uses only integer calculations
Disadvantages
It is meant only for basic line drawing.
Computer Graphics with DomaiNesia Suman covers the principles, techniques, and applications of visual content creation and rendering on digital platforms.
ReplyDelete