ME411: CAD

Mechanical Engineering

Module II: Representation of lines and curves

 Introduction

We need (smooth) curves and surfaces in many applications, such as:

• To model real world objects
• In computer-aided design (CAD)
• In high quality fonts
• In data plots
• In artist’s sketches
 Generation of the lines

A line is a basic element in graphics and connects (at least) two points.

The following criteria have been stipulated for line drawing displays :
➢Lines should appear straight
➢Lines should terminate accurately
➢Lines should have constant density
➢Line density should be independent of length and angle
➢Line should be drawn rapidly
It is known that the screen is divided into pixels that are rectangular in
shape. The process of turning on the pixels for a line segment is called
vector generation. If the end points of the line segment are known, there
are several schemes for selecting the pixels between the end pixels.

However, a large amount of computational effort is required to directly

compute the position of pixels. Hence, a relatively simple procedure to
calculate the position of individual pixel is needed.

Two approaches of generating a line segment are:

➢Digital differential analyzer (DDA) algorithm
➢Bresenham’s line drawing algorithm
Equation of straight line:
y=mx + c
Where, m = slope of the line, and c = intercept
The vertical and horizontal lines can be drawn exactly straight. We need two
endpoints, P and Q, to draw a line on a raster screen. We are starting, say, from
the P coordinate and find the next pixels until we reach, say, the endpoint Q.

Case 1: A horizontal line [m = 0 (i.e., θ = 0°)]

Here, we only need to consider X coordinate value changes. We
first draw pixel P and provide increment only in the X direction
by 1 to get the next pixel.

Case 2: A vertical line [m is undefined (i.e., θ = 90°)]

In this case, we first draw the initial pixel (P), and this time we
increment Y coordinate values by 1 to get the next pixel until
we reach endpoint Q.
Case 3: An inclined line [m = 1 (i.e., θ = 45°)]
The final special scenario is to draw a diagonal line, where
the slope equals 1. To get the next pixel in diagonal line, we
need to increment both X and Y coordinate values by 1.
The scenarios we discussed up to now are special cases.
In general, we may need to draw lines where the slope is greater than / less
than 1. In that cases, we can use the DDA algorithm to draw lines.

DDA line drawing algorithm

This algorithm has 2 cases based on slope value, viz. m>1 and m<1.
For this, let us take (X1, Y1), and (X2, Y2) as our start and end points, respectively.
Case 1: When m < 1

Let us assume that X1 < X2, and we start with X = X1, Y = Y1.
𝑌𝑖+1 −𝑌𝑖
w.k.t. the slope of the line: 𝑚 = (1)
𝑋𝑖+1 −𝑋𝑖

In this case, we always keep the difference in X coordinate values to 1.

𝑋𝑖+1 − 𝑋𝑖 = 1 (2)

Now, by substituting eq. (2) in eq. (1), we can simply calculate the next Y
coordinate value by adding slope to the current Y coordinate as:
𝑌𝑖+1 = 𝑌𝑖 + 𝑚
& 𝑋 =𝑋 +1 (3)
𝑖+1 𝑖
Continue until X = X2.
Case 2: When m > 1

As earlier, let us start with X = X1, Y = Y1.

However, in this case, instead of X, we increment the Y value by one.

𝑌𝑖+1 − 𝑌𝑖 = 1 (4)

So, when we assign this to the slope equation, we get the current X value:
1
𝑚= (5)
𝑋𝑖+1 − 𝑋𝑖

Now we can simply calculate the next Y coordinate value by adding slope to
the current y coordinate.
𝑋𝑖+1 = 𝑋𝑖 + 1/𝑚 (6)
Continue until Y = Y2.
 Bresenham's line drawing algorithm

DDA requires some amount of floating-point arithmetic for each of the pixel
positions, and hence, expensive in terms of the total computation time since
several points need to be calculated for each of the line segments.

Bresenham’s method is an improvement over DDA since it eliminates the

floating-point arithmetic except for the initial computations. All other
computations are fully integer arithmetic and thus is more efficient for raster
conversion.

As for the DDA algorithm, start from the same line equation and the same
parameters. The basic argument for positioning the pixel here is the amount
of deviation the calculated position is from the actual position obtained by
the line equation in terms of d1 and d2 shown in Fig. on the next page.
Let the current position be (Xi, Yi) at the ith position
as shown in Fig. (each of the circles represents
the pixels in the successive positions).
Then,
Xi+1 = Xi + 1 & Yi+1 = Yi + 1 (7)
Yi = m‧Xi + c (8)
Y = m‧(Xi + 1) + c (9)
Let d1 and d2 be two parameters, which indicate where the next pixel is to be
located. If d1 is greater than d2 then the y pixel is to be located at the +1
position, else it remains at the same position as in the previous location.
d1 = Y – Yi = m‧(Xi + 1) + c – Yi (10)
d2 = Yi+1 – Y = (Yi + 1) – m‧(Xi + 1) – c (11)
Therefore,
d1 – d2 = 2m‧(Xi + 1) – 2Yi + 2c – 1 (12)
Where, m=ΔY/ΔX (13)
Equation 12 still contains more computations and hence we would now define
another parameter P which would define the relative position in terms of d1–d2.
Pi = (d1 – d2)‧ΔX (14)
Now, using eq. 13 in eq. 12, and finally substituting in eq. 14, we get:
Pi = 2ΔY‧Xi – 2ΔX‧Yi + 2ΔY + 2c‧ΔX – ΔX = 2ΔY‧Xi – 2ΔX‧Yi + b (15)
Where, b = 2ΔY + 2c‧Δ X – ΔX (16)
Similarly, we can write
Pi+1 = 2ΔY‧(Xi + 1) – 2ΔX‧Yi + 1 + b (17)
Taking the difference of two successive parameters, we can eliminate the
constant terms from eq. 17.
Pi+1– Pi = 2ΔY – 2ΔX‧(Yi+1– Yi) (18)
∴ Pi+1 = Pi + 2ΔY – 2ΔX‧(Yi+1– Yi) (19)
Case 1: When Yi+1= Yi, then, Pi+1 = Pi + 2ΔY, (20)
Case 2: When Yi+1= Yi + 1, then, Pi+1 = Pi + 2ΔY – 2ΔX (21)

From the start point (x1, y1), y1 = m x1 + c (22)

Or c = y1 – (ΔY/ΔX)‧x1 (23)
With this start point, Eq. 15 can be expressed as:
P1 = 2ΔY‧X1 – 2ΔX‧Y1 + 2ΔY + 2c‧Δ X – ΔX (24)
Putting the value of c from eq. 23 into eq. 24, we get:
P1 = 2ΔY‧x1 – 2ΔX‧y1 + 2ΔY + 2[y1 – (ΔY/ΔX)‧x1]‧ΔX – ΔX
= 2ΔY‧x1 – 2ΔX‧y1 + 2ΔY + 2y1‧ΔX – 2ΔY‧x1 – ΔX
∴ P1 = 2ΔY – ΔX (25)
From Eq. 18, it becomes apparent that when Pi is negative then the next pixel
location remains the same as the previous one and eq. 20 becomes valid.
Otherwise, eq. 21 becomes valid. The procedure just described is for the case
when m > 1. The procedure can be repeated for the case of m < 1 by
interchanging X and Y similar to the DDA algorithm.