Chapter-2

Output Primitives Algorithm

PREPARED BY: SUSHANT BHATTARAI

​

www.notedinsights.com

​

Scan Conversion Algorithm

▶ Line

▶ DDA(Digital Differential Analyzer)

▶ Bresenham’s Line Algorithm

▶ Circle Generating Algorithm

▶ Ellipse Generating Algrithm

2

Line Drawing Algorithm

▶ The Cartesian slope-intercept equation for a straight line is

y=mx+b……….[i]

with m representing the slope of the line and b as they intercept.

▶ Given that the two endpoints of the segment are specified at positions (x₁, y₁) and (x₂, y₂) , as shown in Fig., we can determine values for the slope m and y intercept b with the following calculations:

​

……..[ii]

​

……..[iii]

3

Line Drawing Algorithm

▶ Algorithms for displaying straight h e s are based on the line equation [i] and the calculations given in Eqs. [ii] and [iii].

▶ For any given x interval Δx along a line, we can compute the corresponding y interval Δy from eqn. [ii] as

Δy =m Δx

▶ Similarly, we can obtain the x interval Δx corresponding to a specified Δy as

Δx = ^Δy

m

▶ These equations form the basis for determining deflection voltages in analog devices.

▶ On raster systems, lines are plotted with pixels, and step sizes in the horizontal and vertical directions are constrained by pixel separations

4

DDA(Digital Differential Analyzer)

▶ The digital differential analyzer (DDA) is a scan-conversion line algorithm based on calculating either Δy or Δx

▶ We sample the line at unit intervals in one coordinate and determine corresponding integer values nearest the line path for the other coordinate.

▶ Consider first a line with positive slope, as shown in Fig. If the slope is less than or equal to 1, we sample at unit x intervals (Δx = 1) and compute each successive y value as

y_k+1 = y_k + m…………[iv]

▶ Subscript k takes integer values starting from 1, for the first point, and increases by 1 until the final endpoint is reached. Since m can be any real number between 0 and 1, the calculated y values must be rounded to the nearest integer.

5

DDA(Digital Differential Analyzer)

▶ For lines with a positive slope greater than 1, we reverse the roles of x and y.

That is, we sample at unit y intervals (Δy = 1) and calculate each

succeeding x value as

k+1 k

m

x = x + ¹ …….[v]

▶ Equations (iv) and (v) are based on the assumption that lines are to be processed from the left endpoint to the right endpoint. If this processing is reversed, so that the starting endpoint is at the right, then either we have Δx

= -1 and

y_k+1 = y_k − m

or (when the slope is greater than I) we have Δy = -1 with

x = x

k+1 k

₋ 1

m

6

Algorithm

▶ Step1: Start

▶ Step2: Declare x₁,y₁,x₂,y₂,dx,dy,x,y as integer variables.

▶ Step3: Enter value of x₁,y₁,x₂,y₂.

▶ Step4: Calculate dx = x₂-x₁

▶ Step5: Calculate dy = y₂-y₁

▶ Step6: If ABS (dx) > ABS (dy)

Then step = abs (dx)

Else step = abs (dy)

▶ Step7: x_inc=dx/step

y_inc=dy/step assign x = x₁ assign y = y₁

▶ Step8: Set pixel (x, y)

▶

Step9: x = x + x_inc

y = y + y_inc

Set pixels (Round (x), Round (y))

▶ Step10: Repeat step 9 until x = x₂

▶ Step11: End

7

Advantages

▶ 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.

8

Disadvantages

▶ It involves floating point additions rounding off is done.

Accumulations of round off error can use accumulation of error.

▶ Rounding off operations and floating point operations consumes a lot of time.

▶ It is more suitable for generating line using the software. But it is less

suited for hardware implementation.

9

Numerical

1. Calculate the points between the starting point (5, 6) and ending point (8, 12).

▶ Solution: Given,

Starting coordinates = (X₀, Y₀) = (5, 6)

Ending coordinates = (X_n, Y_n) = (8, 12) Step-01:

Calculate ΔX, ΔY and M from the given input.

ΔX = X_n – X₀ = 8 – 5 = 3

ΔY =Y_n – Y₀ = 12 – 6 = 6

M = ΔY / ΔX = 6 / 3 = 2

Step-02:

Calculate the number of steps.

As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6

10

Numerical

Step-03:

As M > 1, so y is increased by 1 and x is to be calculated using the

formulae

^xk+1 ^{= x}k

₊ 1

m

The step must be repeated until the value of y= y_n

11

Numerical

12

Numerical

2. Calculate the points between the starting point (5, 6) and ending point (13, 10).

​

Solution: Given-

Starting coordinates = (X₀, Y₀) = (5, 6) Ending coordinates = (X_n, Y_n) = (13, 10)

Step-01:

Calculate ΔX, ΔY and M from the given input.

ΔX = X_n – X₀ = 13 – 5 = 8

ΔY =Y_n – Y₀ = 10 – 6 = 4

M = ΔY / ΔX = 4 / 8 = 0.50

Step-02:

Calculate the number of steps.

As |ΔX| > |ΔY| = 8 > 4, so number of steps = ΔX = 8

13

Numerical

Step-03:

As M < 1, so value of x is increased by 1 and the value of y is calculated using the formula.

y_k+1 = y_k − m

14

Assignment(DDA Algorithm)

▶ Calculate the points between the starting point (1,1) and ending point (8,7).

▶ Calculate the points between the starting point (0,0) and ending point (4,6).

▶ Calculate the points between the starting point (0,0) and ending

point (7,7).

15

Bresenham Line Algorithm

▶ An accurate and efficient raster line-generating algorithm, developed by Bresenham, scan converts lines using only incrementa1 integer calculations that can be adapted to display circles and other curves

▶ Figures given, illustrate sections of a display screen where straight line segments are to be drawn

▶ The vertical axes show-scan-line positions, and the horizontal axes identify pixel columns. Sampling at unit x intervals in these examples, we need to decide which of two possible pixel positions is closer to the line path at each sample step.

16

Bresenham Line Algorithm

17

▶ 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 (x₀, y₀) 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

▶ Figure below demonstrates the kth step in this process. Assuming we have determined that the pixel at (x_k, y_k) is to be displayed, we next need to decide which pixel to plot in column x_k+1,. Our choices are the pixels at positions (x_k + 1, y_k) and (x_k + 1, y_k + 1).

▶ At sampling position x_k + 1, we label vertical pixel separations from the

mathematical line path as, d₁ and d2 (shown in figure). The y coordinate on the

mathematical line at pixel column position x_k + 1 is calculated as y=m(x_k + 1)+b…….(1)

d₁ =y- y_k

= m(x_k + 1)+b- y_k….(2)

Bresenham Line Algorithm

▶ Similarly,

𝑑₂ =𝑦_𝑘 + 1-y

= 𝑦_𝑘 + 1-m(𝑥_𝑘 + 1)+b…….(3)

▶ Then

𝑑₁ − 𝑑₂=2m(𝑥_𝑘 + 1)-2𝑦_𝑘+2b-1…..(4)

▶ A decision parameter 𝑝_𝑘 for the kth step in the line algorithm can be obtained by rearranging Eq. 4 so that it involves only integer calculations. We accomplish this by

substituting m = ^Δ𝑦, where 𝛥y and 𝛥𝑥 are the vertical and horizontal separations of the

𝛥𝑥

endpoint positions, and defining:

……..(5)

18

Bresenham Line Algorithm

▶ The sign of 𝑝_𝑘, is the same as the sign of 𝑑₁ − 𝑑₂ , since 𝛥𝑥 > 0 for our example. Parameter c is constant and has the value 2 𝛥y + 𝛥𝑥(2b - 1)

▶ If the pixel at y_k is closer to the line path than the pixel at y_k+1 (that is, d₁ < d₂), then decision parameter p_k is negative. In that case, we plot the lower pixel; otherwise, we plot the upper pixel.

▶ Coordinate changes along the line occur in unit steps in either the x or y directions. Therefore, we can obtain the values of successive decision parameters using incremental integer calculations. At step k + 1, the decision parameter is evaluated from Eq(5)

Subtracting Eq. (5) from the preceding equation, we have

19

Bresenham Line Algorithm

▶ But 𝑥_𝑘+1, = 𝑥_𝑘 + 1, so that

…….(6)

​

where the term y_k+1-𝑦_𝑘 is either 0 or 1, depending on the sign of parameter p_𝑘 .

▶ This recursive calculation of decision parameters is performed at each integer x position, starting at the left coordinate endpoint of the line. The first parameter p_𝑘 , is evaluated from Eq. (5) at the starting pixel position (𝑥₀, 𝑦₀)

𝛥𝑥

and with m evaluated as ^𝛥𝑦 :

20

Bresenham Line Algorithm

21

Numerical

22

Numerical

Q)Calculate the points between the starting coordinates (9, 18) and ending coordinates (14, 22).

Solution- Given- Starting coordinates = (X₀, Y₀) = (9, 18) Ending coordinates = (X_n, Y_n) = (14,

22)

Calculate ΔX and ΔY from the given input.

ΔX = X_n – X₀ = 14 – 9 = 5 ΔY =Y_n – Y₀ = 22 – 18 = 4

Calculate the decision parameter.

P_k = 2ΔY – ΔX = 2 x 4 – 5 = 3

So, decision parameter P_k = 3 As P_k >= 0, Thus,

P_k+1 = P_k + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1

X_k+1 = X_k + 1 = 9 + 1 = 10

Y_k+1 = Y_k + 1 = 18 + 1 = 19

(Number of iterations = ΔX – 1 = 5 – 1 = 4)

23

Numerical

24

Circle Drawing Algorithm(Simple Algorithm)

▶ A circle is defined as the set of points that are all at a given distance r from a center position (x_c, y_c)

▶ This distance relationship is expressed by the Pythagorean theorem in Cartesian coordinates as

(𝑥 − 𝑥_𝑐)² + (𝑦 − 𝑦_𝑐)²= 𝑟²……….(1)

▶ We could use this equation to calculate the position of points on a circle circumference by stepping along the x axis in unit steps from 𝑥_𝑐 - r to 𝑥_𝑐+ r and calculating the corresponding y values at each position as

…………(2)

25

Circle Drawing Algorithm (Simple Algorithm)

▶ This is not the best method for generating a circle. One problem with this approach is that it involves considerable computation at each step

▶ The spacing between plotted pixel positions is not uniform, as demonstrated in Fig

26

Circle Drawing Algorithm(Polar Equations)

▶ If (x,y) be any point on the circle boundary with center (0,0) and radius r,then

x=rcos𝜃

y=rsin 𝜃

▶ To draw circle using these co-ordinates approach,just increase angle starting from 0 to 360.

▶ Compute (x,y) position according to increment angle. Which draws circle centered at origin, that is not visible completely on the screen as (0,0) is the initial position of the screen.

▶ If the center of the circle is given by 𝑥_𝑐, 𝑦_𝑐 then the pixel position (x,y) on

the circle path will be computed as:

27

Symmetry in Circle scan conversion

▶ Computation can be reduced by considering the symmetry of circles. The shape of the circle is similar in each quadrant.

▶ There are two ways i.e. 4-way and 8-way symmetry.

▶ We only need to generate the points for one quadrant or octant and then use the symmetry to determine all the other points.

28

Midpoint Circle Algorithm

▶ we sample at unit intervals and determine the closest pixel position to the specified circle path at each step.

▶ For a given radius r and screen center position x_c, y_c , we can first set up our algorithm to calculate pixel positions around a circle path centered at the coordinate origin (0,0)

▶ Then each calculated position (x, y) is moved to its proper screen position

by adding x_c to x and y_c to y.

▶ we can take unit steps in the positive x direction over this octant and use a decision parameter to determine which of the two possible y positions is closer to the circle path at each step.

▶ To apply the midpoint method, we define a circle function:

……………(1)

29

Midpoint Circle Algorithm

▶ Any point ( x , y) on the boundary of the circle with radius r satisfies the equation f_circle (x, y) = 0. If the point is in the interior of the circle, the circle function is negative. And if the point is outside the circle, the circle function is positive.

​

…….(2)

▶ The circle-function tests are performed for the mid positions between pixels near the circle path at each sampling step. Thus, the circle function is the decision parameter in the midpoint algorithm

▶ Figure below shows the midpoint between the two candidate pixels at Sampling position x_k + 1.

Assuming we have just plotted the pixel at (x_k, y_k), we next to determine whether the pixel at position (x_k + 1, y_k) or the one at position (x_k + 1, y_k - 1) is closer to the circle. Our decision parameter is the circle function equation(1) evaluated at the midpoint between these two pixels:

30

Midpoint Circle Algorithm

31

▶ If p_k < 0, this midpoint is inside the circle and the pixel on scan line 𝑦_𝑘 is closer to the circle boundary. Otherwise, the mid position is outside or on the circle boundary, and we select the pixel on scanline y_k - 1.

▶ We obtain a recursive expression for the next decision parameter by evaluating the circle function at sampling position x_k+1 + 1 = 𝑥_𝑘 + 2

▶ where y_k+1, is either y_k or y_k−1, depending on the sign of p_k

Midpoint Circle Algorithm

▶ The value of p_k+1 , are either 2 x_k+1 + 1 (if p_k is negative) or 2 x_k+1 + 1 - 2 y_k+1.

where ,

​

▶ The initial decision parameter is obtained by evaluating the circle function at the start position (x₀ , y₀ ) = (0, r)

32

Midpoint Circle Algorithm

33

Numerical

34

Numerical

Q) Given the centre point coordinates (4, 4) and radius as 10, generate all the points to form a circle.

Solution: Centre Coordinates of Circle (X₀, Y₀) = (4, 4) Radius of Circle = 10

▶ As stated in the algorithm,

▶ We first calculate the points assuming the centre coordinates is (0, 0).

▶ At the end, we translate the circle.

Assign the starting point coordinates (X₀, Y₀) as- X₀ = 0

Y₀ = R = 10

35

Numerical

Now, calculate the value of 𝑝₀

p₀ = 1 – R

p₀ = 1 – 10

p₀ = -9

As P_initial < 0, so

X_k+1 = X_k + 1 = 0 + 1 = 1 Y_k+1 = Y_k = 10

P_k+1 = P_k + 2 x X_k+1 + 1 = -9 + (2 x 1) + 1 = -6

36

Numerical

37