MIDLANDS STATE UNIVERSITY

FACULTY OF COMMERCE
MIDLANDS STATE UNIVERSITY
FACULTY OF BUSINESS SCIENCES
DEPARTMENT OF INFORMATION AND MARKETING SCIENCES
INFO411- COMPUTER GRAPHICS
Lecturer: R. Gumbo
OUTPUT PRIMITVES
Presentation Focus
 Output Primitives

 Points and Lines

 Line drawing algorithms
 Circle drawing algorithms
What is an Output Primitive?
 Primitives are the simple geometric functions that are
used to generate various Computer Graphics required by
the User. The most basic output primitives are point-
position(pixel), and a straight line. However different
Graphic packages offers different output primitives like a
rectangle, conic section, circle, spline curve among others.
Attributes of output primitives
 Any parameter that affects the way a primitive is to be displayed is referred to
as an attribute parameter. Example attribute parameters are color, size etc. A
line drawing function for example could contain parameter to set color, width
and other properties.
 Line Attributes
 Curve Attributes
 Color and Grayscale Levels
 Area Fill Attributes
 Character Attributes
 Bundled Attributes
Points and Lines
 A point function is the most basic Output primitive in the graphic package. It
contains location using x and y coordinates and the user may also pass other
attributes such as its intensity and color. The location is stored as two integer
tuple. The color is defined using hex codes. The size of a pixel is equal to the size
of pixel on display monitor.
 Point plotting is accomplished by converting a single coordinate position
furnished by an application program into appropriate operations for the output
device. With a CRT monitor, for example, the electron beam is turned on to
illuminate the screen phosphor at the selected location
Points and Lines cont’

 A line function is used to generate a straight line between any two

end points. Usually a line function is provided with the location of
two pixel points called the starting point and the end point and it is
up to the computer to decide what pixels fall between these two
points so that a straight line is generated.
 Line drawing is accomplished by calculating intermediate positions
along the line path between two specified endpoints positions. An
output device is then directed to fill in these positions between the
endpoints Digital devices display a straight line segment by plotting
discrete points between the two endpoints. Scan lines are numbered
consecutively from 0, starting at the bottom of the screen; and pixel
columns are numbered from 0, left to right across each scan line
Line Attributes

 The Basic attributes of a straight line segment are its type, its width, and its color. In some
graphics packages, lines can also be displayed using selected pen or brush options
 Line Type
 Line Width
 Pen and Brush Options
 Line Color
Line Drawing Algorithms

What is a line drawing algorithm?

 It is a set of rules followed by a computer to determine the positions of pixels that fall
between two given points to generate a straight line.
Line Drawing algorithms
 Digital Differential Analyser (DDA) Algorithm
 Bresenham’s Line Algorithm
 Parallel Line Algorithm
 Mid point line drawing
DDA Line Drawing Algorithm
 Digital Differential Analyser (DDA) Line Drawing Algorithm is the simplest line drawing
algorithm. It is an incremental method, i.e. it works by incrementing the source coordinate points
according to the values of the slope generated which basically means the algorithm takes the 2
endpoints of a line and then inputs pixel one at a time on the path. Because of its incremental
nature it is used for the rasterization of lines, triangles, and polygons. In this algorithm, the
calculation is performed in a step-by-step manner, and the previous step result is used in the next
step. 
 A line is usually infinite in dimension but a segment of the line can be drawn.
 A line segment will have two confined points (x1, y1) and (x2, y2) which is a starting point and
an ending point.
 The line equation is set as: y=mx+c where
 m is the slope of the line and is calculated as m = (y2 – y1)/ (x2 – x1)
 c is the intersecting point of the y-intercept.
DDA, seeks to establish all the set of points in a line segment.
Finding the slope
To find the slope between the starting point and ending point.
There can be three possible cases:

 If slope (m) is less than 1 (m<1) then increment x as x1+1

and calculate y1 as y1=y1+m
 If slope (m) is greater than 1 (m>1) then increment y as
y1+1 and calculate x1=x1+1/m
 If slope (m) is equal to 1 (m=1) then increment both x and
y. x1=x1+1, y1=y1+1
Steps to DDA
 Step 1: Set starting points of line as (x1, y1) and end
points as (x2, y2)
 Step 2: m=(y2-y1)/(x2-x1)
 Step 3: Find the next point by following one of the
three cases as outlined above
 Step 4: Repeat the steps till the end of the line (x2,
y2) is reached
Example: draw a line from (1,1) to (8,7)
 Answer:

Step 1: (x1=1, y1=1); (x2=8, y2=7)

Step 2: m= (y2-y1)/(x2-x1) which translates to (7-1)/(8-1) which equals 6/7 and definitely a case of m<1

Step 3: As m<1 therefore x is increased and y is calculated. This means we increment x as x1+1 and

calculate y1 as y1=y1+m. The points generated will be x1=x1+1 and y1=1+(6/7) =1.9=> approx. 2 so
x1=2 and y1=~2 as below

Steps X1 Y1 Pixel Plotted

1 2 2 2,2

2 3 2+(6/7)=2.9 3,3

3 4 2.9+0.9=3.8 4,4

4 5 3.8+0.9=4.7 5;5
The algorithm will stop here
5 6 4.7+0.9=5.6 6,6
since the y value has reached 7 6 7 5.6+0.9=6.5 7,7
Advantages and disadvantages of DDA

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.
Disadvantages:
 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 consumes a lot of time.
 It is more suitable for generating line using the software. But it is less suited for hardware implementation.
Bresenham’s Line Drawing Algorithm

 Bresenham Line Algorithm is an optimistic & incremental scan conversion Line Drawing Algorithm that
calculates all intermediate points over the interval between start and endpoints.
 It is implemented entirely with integer numbers and the integer arithmetic. It only uses addition and
subtraction and avoids heavy operations like multiplication and division.
 The idea of Bresenham’s algorithm is to avoid floating-point multiplication and addition to compute mx + c,
and then computing the round value of (mx + c) in every step.
 Bresenham’s Line Drawing Algorithm determines the points of an n-dimensional raster that should be
selected in order to form a close approximation to a straight line between two points.
Bresenham’s Line Drawing Algorithm cont’

• Bresenham's line algorithm uses the principle of selecting

the optimum raster locations to represent a straight line.
• To accomplish this, the algorithm always increments either x
or y by one unit depending on the slope of the line.
• The increment in the other variable is determined by
examining the distance between the actual line location and
the nearest pixel. This distance is called the decision
variable or the error
Steps to Bresenham
 Step 1: Calculate ΔX and ΔY from the given input.
 These parameters are calculated as-
 ΔX = X2 – X1
 ΔY =Y2 – Y1

 Step 2: Calculate the decision parameter Pk.

 calculated as: Pk = 2ΔY – ΔX

 Step 3: Calculation of next point

 Suppose the current point is (Xk, Yk) then then next point is (Xk+1, Yk+1).
 Find the next point depending on the value of decision parameter P k.
 Follow the two cases on the Fig
 Step 4 Keep repeating Step 3 until the end point is reached
Example: Using Bresenham’s line drawing algorithm, calculate
the points between the starting coordinates (9, 18) and ending
coordinates (14, 22).
Pk Pk+1 Xk+1 Yk+1
• Starting coordinates = (X1, Y1) = (9, 18)
• Ending coordinates = (X2, Y2) = (14, 22) 9 18
Step 1: Calculate ΔX and ΔY from the given input.
ΔX = X2 – X1 = 14 – 9 = 5 3 1 10 19
ΔY =Y2 – Y1 = 22 – 18 = 4
Step 2: Calculate the decision parameter. 1 -1 11 20
Pk = 2ΔY – ΔX
= (2 x 4)– 5 -1 7 12 20
=3
7 5 13 21
So, decision parameter Pk = 3
Step 3: As Pk >= 0, so case-02 is satisfied. 5 3 14 22
• Thus Pk+1 = Pk + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
• Xk+1 = Xk + 1 = 9 + 1 = 10
• Yk+1 = Yk + 1 = 18 + 1 = 19
Step 3 is executed until the end point is reached.
Advantages and Disadvantages of
Bresenham’s algorithm
 Advantages:
 It involves only integer arithmetic, so it is simple.
 It avoids the generation of duplicate points.
 It can be implemented using hardware because it does not use multiplication and division.
 It is faster as compared to DDA (Digital Differential Analyzer) because it does not involve
floating point calculations like DDA Algorithm.
 Disadvantages:
 This algorithm is meant for basic line drawing only Initializing is not a part of Bresenham's line
algorithm. So to draw smooth lines, you should want to look into a different algorithm.
Difference between DDA Algorithm and Bresenham's Line Algorithm:

DDA Algorithm Bresenham's Line Algorithm

1. DDA Algorithm use floating point, i.e., Real Arithmetic. 1. Bresenham's Line Algorithm use fixed point, i.e., Integer
Arithmetic

2. DDA Algorithms uses multiplication & division its operation 2.Bresenham's Line Algorithm uses only subtraction and addition its
operation

3. DDA Algorithm is slowly than Bresenham's Line Algorithm in 3. Bresenham's Algorithm is faster than DDA Algorithm in line
line drawing because it uses real arithmetic (Floating Point because it involves only addition & subtraction in its calculation and
operation) uses only integer arithmetic.

4. DDA Algorithm is not accurate and efficient as Bresenham's Line 4. Bresenham's Line Algorithm is more accurate and efficient at
Algorithm. DDA Algorithm.

5.DDA Algorithm can draw circle and curves but are not accurate as 5. Bresenham's Line Algorithm can draw circle and curves with more
Bresenham's Line Algorithm accurate than DDA Algorithm.
Circle drawing algorithms

 A Circle is defined as the set of points that are all at a given distance r from a center
position (xc, yc).
Types of circle drawing algorithms
 Bresenham’’s circle algorithm
 Midpoint Circle Algorithm
Bresenham’s circle algorithm

 Bresenham’’s circle algorithm avoids these square root calculations by comparing the
squares of the pixel separation distances. Points are generated from 90° to 45°, moves will
be made only in the +x & -y directions.
 The best approximation of the true circle will be described by those pixels in the raster that
falls the least distance from the true circle.
 In this approach is to test the halfway position between two pixels to determine if this
midpoint is inside or outside the circle boundary.
Steps to Bresenham’s circle algorithm
 Step1: Start Algorithm
 Step2: Declare p, q, x, y, r, d variables
        p, q are coordinates of the center of the circle
        r is the radius of the circle
 Step3: Enter the value of r
 Step4: Calculate d = 3 - 2r
 Step5: Initialize       x=0
          &nbsy= r
 Step6: Check if the whole circle is scan converted
            If x > = y
            Stop
Step7: Plot eight points by using concepts of eight-way symmetry. The center is at (p, q). Current active pixel is (x, y).
                putpixel (x+p, y+q)
                putpixel (y+p, x+q)
                putpixel (-y+p, x+q)
                putpixel (-x+p, y+q)
                putpixel (-x+p, -y+q)
                putpixel (-y+p, -x+q)
                putpixel (y+p, -x+q)
                putpixel (x+p, -y-q)
Steps to Bresenham’s circle algorithm Cont’

 Step8: Find location of next pixels to be scanned

            If d < 0
            then d = d + 4x + 6
            increment x = x + 1
            If d ≥ 0
            then d = d + 4 (x - y) + 10
            increment x = x + 1
            decrement y = y - 1
 Step9: Go to step 6
 Step10: Stop Algorithm
Example: Plot 6 points of circle using Bresenham
Algorithm. When radius of circle is 10 units. The
circle has centre (50, 50).
Solution: 
 Let r = 10 (Given)
 Step1: Take initial point (0, 10)
                d = 3 - 2r
                d = 3 - 2 * 10 = -17
                d < 0 ∴ d = d + 4x + 6
                      = -17 + 4 (0) + 6
                      = -11
 Step2: Plot (1, 10)
          d = d + 4x + 6 (∵ d < 0)
                = -11 + 4 (1) + 6
                = -1
 Step3: Plot (2, 10)
           d = d + 4x + 6 (∵ d < 0)
                = -1 + 4 x 2 + 6
                = 13
Solution Cont’

 Step4: Plot (3, 9) d is > 0 so x = x + 1, y = y - 1

                          d = d + 4 (x-y) + 10 (∵ d > 0)
                = 13 + 4 (3-9) + 10
                = 13 + 4 (-6) + 10
                = 23-24=-1
 Step5: Plot (4, 9)
            d = -1 + 4x + 6
                = -1 + 4 (4) + 6
                = 21
 Step6: Plot (5, 8)
            d = d + 4 (x-y) + 10 (∵ d > 0)
                = 21 + 4 (5-8) + 10
                = 21-12 + 10 = 19
 So P1 (0,0)⟹(50,50)
            P2 (1,10)⟹(51,60)
            P3 (2,10)⟹(52,60)
            P4 (3,9)⟹(53,59)
            P5 (4,9)⟹(54,59)
            P6 (5,8)⟹(55,58)
Midpoint Circle Algorithm

 To apply the midpoint method we define a circle function as

fcircle(x,y) = x2+y2-r2
 Any point (x,y) on the boundary of the circle with radius r satisfies the equation fcircle
(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
 fcircle (x,y) <0, if (x,y) is inside the circle boundary =0,
 if (x,y) is on the circle boundary >0,
 if (x,y) is outside the circle boundary
Steps to midpoint Circle Algorithm
Example : Midpoint Circle Drawing Given a circle radius
r=10 The circle octant in the first quadrant from x=0 to x=y.

The initial value of the decision parameter is P0=1-r = - 9

For the circle centered on the coordinate origin, the initial
point is (x0,y0)=(0,10) and initial increment terms for
calculating the decision parameters are 2x0=0 , 2y0=20
Successive midpoint decision parameter values and the
corresponding coordinate positions along the circle path are
listed in the following table.
Outcome
The
end