2 Output Primitives–DDA line Drawing procedure

T. Raghuveera

Objectives:

Understand how a line is drawn using DDA line drawing procedure

Basic Building blocks of a picture:

A primitive is a small component of a picture. A picture is an aggregation of basic building blocks as shown here. Some of the basic building blocks under discussion are Points, lines, triangle, plane circle, ellipse, arcs, splines, NURBS, fractals. A picture is some combination of these primitives.

A point is a location in space. It has no dimension theoretically. A point can be easily plotted on a monitor only if its abscissa and ordinate are both integers.

Lines: A line is a collection of points along a particular direction.Given two end points, the line drawing algorithm has to find the intermediate points which could be plotted. A monitor is a device that has got a rectangular arrangement of pixels. A pixel is identified or located using an x-position and a y-position. i.e., a pixel position can be identified as say (25, 40), the reference position being the top left corner as we start counting pixels from top left corner. Moreover we have pixel positions which are integer values only i.e. there is no position like (10.4, 20.7) which can be plotted. We have to either round it off or trim the fractions.

Line drawing algorithms:

The two popular line drawing procedures are given here. DDA is a rudimentary level procedure and is less accurate, while Bresenham’s procedure is more accurate.

• DDA (Digital Differential Analyzer)
• BRESENHAM

An efficient algorithm is one that has less computational complexity and draws accurate lines. Lines can be represented in equations by using slope-point form, slope-intercept form or parametric form.

DDA (Digital Differential Analyzer) LINE DRAWING ALGO:

• Based on slope–point form of line equation
• Simple
• Scan conversion based
• Less efficient

Let’s imagine various line type as shown. The blue color dot represents the starting point of the line and the red dot represents the endpoint. The line types 1 and 3 are more inclined towards X-axis. Line type 2 and 4 are more inclined towards y-axis. Line types 1, 2 and 5 have positive slopes with type 5 having a slope of 1, while line types 3, 4 have negative slopes. We can characterize the line types as shown below. These are the possible lines that we can draw in 2D space. Here ‘m’ is the slope and computed as ratio of dy, dx.

As line types (1) and (3) are more inclined towards X-axis it makes sense to sample them along X-axis at the highest possible sampling frequency which is 1. Line types (2) and (4) are more inclined towards Y-axis it makes sense to sample them along Y-axis at the highest possible sampling frequency which is 1. The line type (5) can be sampled either along x-axis or along y-axis. For simplicity we can sample the line type (5) also along x-axis. We can devise simple procedures that compute points along the line path, given the two end points. The closer we compute the points along the line path, the better is the approximation for the true line path. That is we are concerned about the highest possible sampling frequency, which is one-pixel distance. See figure.

We adopt different procedures, for different line types. When the lines are more inclined towards x-axis (|m|<=1), we will sample the line along x-axis at unit x-intervals, and compute the corresponding y as shown above and below.

When the lines are more inclined towards x-axis (|m|>1), we will sample the line along y-axis at unit y-intervals, and compute the corresponding x as shown below. As can be observed from the figure above, for line type (1), (3), three in-between points (shown in green) need to be computed, while for line type (5) two in-between points need to be computed.

Given two end points P1(x1, y1) and P2(x2, y2)

For any two consecutive points along the line say (xk,yk) and (xk+1,yk+1)

Where k takes integer values from 1 or 0 for the first point and increases by 1 until the final end point is reached. The next x value is indicated as Xk+1 while the next y value is indicated as yk+1. When we are sampling along x-axis next x given xk is xk+1 and when we are sampling along x-axis next x given yk is yk+1.

DDA procedure:

• Input the end points
• Compute slope
• Depending on the magnitude of slope, decide whether to increment along X-axis or Y-axis by unit steps and compute corresponding points on the other axis
• Round the computed values to the nearest integer for plotting

Ex: Problem: Given two end points (2, 2) and (10, 5). Find the intermediate points using DDA line drawing algo.

Sol: Compute Slope m=3/8=0.375 <1

Since m<1 use eq.s of case (i) xk+1=xk+1, yk+1=yk+m

The starting position on the line is at (X0, Y0) = (2, 2), so next x is 3 and next is 4 and so on.

The intermediate points are computed as shown.

Y1=2+0.375

Y2=2.375+0.375

Y3=2.750+0.375

……

……

i.e., for computation we use floating point values and for plotting we will be rounding off the values.

Drawbacks of DDA

• Stair-Step or Jaggy effect
• Floating point calculations
• For longer lines DDA line drifts away from true line

Summary:

• Learnt how to draw a line given two end points using DDA procedure
• Understood the pros and cons of the DDA procedure