Unit-2

• What are Line Drawing Algorithms?
• “The Line drawing algorithm is a graphical algorithm that is used to represent the line segment on discrete graphical media, i.e., printer and pixel-based media.” A line contains two points The point is an important element of a line. A line algorithm is a method for estimating a line segment on discrete graphical media such as pixel-based screens and printers in graphics.
• Lines are rasterized in one color using basic methods. Spatial anti-aliasing is a sophisticated approach that allows for a better representation of
• numerous color gradations.
• To draw a line on a continuous medium, however, no algorithm is required. Cathode-ray
• oscilloscopes, for example, use analog phenomena to create lines and curves.
• The formula for a slope line interception is:
• Y = mx + b
• In this formula, m is the slope line and b is the line’s intercept of y.
• Two endpoints for the line segment are supplied in coordinates (x1, y1) and (x2, y2).
• In this formula, m is the slope line and b is the line’s intercept of y.
• Two endpoints for the line segment are supplied in coordinates (x1, y1) and (x2, y2).

• Properties of a Line Drawing Algorithm: Input: At least one or more inputs must be accepted a good algorithm. Output: At least one output must produce an algorithm. An algorithm should be precise:
• The algorithm’s each step must well-define.
• Finiteness: Finiteness is required in an algorithm. It signifies that the algorithm will come to a halt once all of the steps have been completed.
• Correctness: An algorithm must implement correctly.
• Uniqueness: The result of an algorithm should be based on the given input and all steps of the algorithm should be clearly and uniquely defined.
• Effectiveness: An algorithm’s steps must be correct and efficient.
• Easy to understand: Learners must be able to understand the solution in a more natural way thanks to an algorithm.
• Characteristics of Line Drawing Algorithm:
• The line should appear Straight:
• We must appropriate the line by choosing addressable points close to it.
• If we choose well, the line will appear straight, if not, we shall produce crossed lines.

• The lines must be generated parallel or at 45° to the x and y-axes.
• Other lines cause a problem: a line segment through it starts and finishes at addressable points, may happen to pass through no other addressable point in between.

• Lines should have constant density:
• Line density is proportional to the no. of dots displayed divided by the length of the line.
• To maintain constant density, dots should be equally spaced.
• Line density should be independent of line length and angle:
• This can be done by computing an approximating line-length estimate and using a line generation algorithm that keeps line density constant to within the accuracy of this estimate.
• The line should be drawn rapidly: This computation should be performed by special-purpose hardware.

DDA algorithm

DDA stands for Digital Differential Analyzer.
 It is an incremental method of scan conversion of line. In this method calculation is
performed at each step but by using results of previous steps.
 We sample the line at unit intervals in one coordinate and find corresponding integer values
nearest the line path for the other coordinate.
 Consider first a line with positive slope and slope is less than or equal to We sample at unit x
interval (Ax= 1) and calculate each successive y value as follow:
The line of equation for step i
Yi = mxi+b………………….equation 1
Next value will be
yi+1=mxi+1+b……………..equation 2
m = DDA Algorithm

yi+1-yi = ∆y…………………..equation 3 yi+1-xi = ∆x………………….equation 4 yi+1 = yi+∆y ∆y = m∆x yi+1 = yi+m∆x ∆x = ∆y/m Case1: When |M|<1 then (assume that x12) x = x1, y = y1 set ∆x = 1 yi+1 = y1+m, x = +1 Until x = x2 Case2: When |M|<1 then (assume that y12) x = x1, y = y1 set ∆y = 1 xi+1 = DDA Algorithm, y=y+1 Until y → y2 DDA Algorithm:

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));
}
Steps of Algorithms
Step1: Start Algorithm
Step2: Declare x1, y1, x2, y2, dx, dy, x, y as integer variables.
Step3: Enter value of x1, y1, x2, y2.
Step4: Calculate dx = x2-x1
Step5: Calculate dy = y2-y1
Step6: If ABS (dx) > ABS (dy)
Then step = abs (dx) Else
Step7: xinc = dx/step
yinc = dy/step
assign x = x1
assign y = y1
Step8: Set pixel (x, y)
Step9: x = x + xinc
y = y + yinc
Set pixels (Round (x), Round (y))
Step10: Repeat step 9 until x = x2
Step11: End Algorithm

• Advantage:
• It is a faster method than method of using direct use of line equation.
• This method does not use multiplication theorem.
• It allows us to detect the change in the value of x and y, so plotting of same point twice is
• not possible.
• This method gives overflow indication when a point is repositioned. It is an easy method because each step involves just two additions.
• Disadvantage:
• It involves floating point additions rounding off is done. Accumulations of round-off error cause accumulation of error.
• Rounding-off operations and floating point operations consume a lot of time.
• It is more suitable for generating lines using the software. But it is less suited for hardware implementation.