Unit-2
Drawing and Clipping Primitives
Topic – Points, Lines, DDA Algorithm, Bresenham’s Algorithm
Points and Lines in Computer Graphics
• Points and lines are the fundamental
building blocks of all graphics.
• From lines, we can construct polygons,
curves, and 3D objects.
• On raster displays, lines must be
approximated using pixels.
Why is it Important?
• Every shape (circle, polygon, text) is made of lines - line drawing is
the foundation.
• Used in:
• CAD tools (engineering design)
• Gaming graphics
• GUI frameworks (window borders, icons)
• Graph plotting
• Without efficient algorithms - graphics would be slow, blurry, and
inconsistent.
Scan Conversion
• What is Scan Conversion?
• Conversion of geometric primitives (lines,
circles, polygons) into discrete pixels on
raster display.
• Required because display devices are raster-
based - made of finite pixels.
• Ideal line = Infinitely thin + continuous.
• Raster line = Finite, jagged.
• Goal: Map mathematics -> pixels efficiently &
accurately.
Representation of a Point
• A point is the smallest addressable element on
the screen (a pixel).
• Defined by coordinates (x, y) in 2D space.
• In raster systems:
• Coordinates are integers - corresponds to pixel grid.
• Example: (3, 5) means the pixel at row 5, column 3.
• In vector systems: points can be continuous,
not limited to pixel grid.
Representation of a Line
• Mathematical line equation:
• General form:
where b is the y-intercept
• Slope:
Types of slopes
• m = 0 → horizontal line
• m = ∞ → vertical line
• 0 < m < 1 → shallow line
• m > 1 → steep line
Challenges in Line Drawing
• Problem: Mapping continuous geometry
onto discrete pixel grid.
• Issues:
• Aliasing: stair-step effect in diagonal
lines.
• Accuracy: pixel positions may deviate ?
from true line. ? ?
?
• Efficiency: must be drawn quickly for
real-time applications.
• Therefore - Need line-drawing algorithms.
Properties of a Good Algorithm
• Line must be straight and close to ideal.
• Exactly 1 pixel per column/row (depending on slope).
• Uniform brightness and constant thickness.
• Algorithm should be fast (no heavy floating-point math if
possible).
• Support for thick lines, styles (dashed, dotted), and anti-aliasing.
Line Drawing Algorithms
• Two main incremental algorithms:
• Digital Differential Analyzer (DDA)
• Uses floating-point arithmetic
• Simple, easy to implement
• Bresenham’s Algorithm
• Uses integer arithmetic
• Faster and more accurate
• Both are used to decide which pixels best approximate a line.
DDA Line Drawing Algorithm
DDA Line Drawing Algorithm
• DDA - Digital Differential Analyzer
• Line drawing algorithm used to generate a line segment between
two specified endpoints.
• One of the earliest line drawing algorithms.
• Idea:
• Works by moving in small equal steps along one axis (x or y)
and
• Calculating the corresponding value on the other axis, ensuring
the plotted pixels follow the ideal line closely.
Drawing a horizontal line on pixel grid
• Draw a line between (2,2) & (9,2)
• Approach:
• dx = 9-2 = 7 x y
• dy = 2-2 = 0 2 2
• Slope, m = dy/dx 3 2
= 0/7 = 0 4 2
• steps = 7 5 2
• x_inc = dx/steps 6 2
= 7/7 = 1 7 2
• y_inc = dy/steps 8 2
9 2
= 0/7 = 0
Drawing a vertical line on pixel grid
• Draw a line between (2,5) & (2,12)
• Approach:
• dx = 2-2 = 0
• dy = 12-5 = 7 x y
• Slope, m = dy/dx 2 5
2 6
= 7/0
2 7
= undefined
2 8
• steps = 7 2 9
• x_inc = dx/steps 2 10
= 0/7 = 0 2 11
• y_inc = dy/steps 2 12
= 7/7 = 1
Drawing a sloped line on pixel grid (m<1)
• Draw a line between (5,4) & (12,7)
• Approach:
• dx = 12-5 = 7 x y
round
(y)
• dy = 7-4 = 3
5 4 4
• Slope, m = dy/dx
6 4.4 4
= 3/7 7 4.8 5
= 0.4 8 5.2 5
• steps = 7 9 5.6 6
• x_inc = dx/steps 10 6 6
= 7/7 = 1 11 6.4 6
• y_inc = dy/steps 12 6.8 7
= 3/7 = 0.4
Drawing a sloped line on pixel grid (m>1)
• Draw a line between (5,7) & (10,14)
• Approach:
• dx = 10-5 = 5 x y
round
(x)
• dy = 14-7 = 7 5 7 5
• Slope, m = dy/dx 5.7 8 6
= 7/5 6.4 9 6
= 1.4 7.1 10 7
• steps = 7 7.8 11 8
• x_inc = dx/steps 8.5 12 9
9.2 13 9
= 5/7 = 0.7
9.9 14 10
• y_inc = dy/steps
= 7/7 = 1
Drawing a sloped line on pixel grid (m=1)
• Draw a line between (7,3) & (13,9)
• Approach:
• dx = 13-7 = 6
• dy = 9-3 = 6 x y
• Slope, m = dy/dx 7 3
= 6/6 8 4
=1 9 5
• steps = 6 10 6
• x_inc = dx/steps 11 7
12 8
= 6/6 = 1
13 9
• y_inc = dy/steps
= 6/6 = 1
Mathematical Representation of DDA
• Equation of line: y = mx + c
• Given two endpoints: (x1, y1) and (x2, y2)
• Calculate slope: m = (y2 – y1) / (x2 – x1)
• Two cases:
• If |m| <= 1 → x increases in unit steps, y is
calculated.
• xk+1 = xk + 1
• yk+1 = yk + m
• If |m| > 1 → y increases in unit steps, x is calculated.
• yk+1 = yk + 1
• xk+1 = xk + (1/m)
DDA Algorithm (Pseudo-code)
function DDA(x1, y1, x2, y2):
dx = x2 – x1
dy = y2 – y1
steps = max(|dx|, |dy|)
Xinc = dx / steps
Yinc = dy / steps
x = x1, y = y1
for k = 0 to steps:
plot(round(x), round(y))
x = x + Xinc
y = y + Yinc
DDA Algorithm (Generalized Form)
• Steps: • Initialize:
• Input two endpoints (x1, y1) and • x = x1, y = y1
(x2, y2). • Repeat for “steps” times:
• Compute: • Plot (round(x), round(y))
• dx = x2 – x1 • x = x + x_inc
• dy = y2 – y1 • y = y + y_inc
• Calculate steps = max(|dx|, |dy|)
• Compute increments:
• x_inc = dx / steps
• y_inc = dy / steps
Example:
• Problem: Draw line from (2, 3) to Pixel
(10, 8) using DDA Algorithm Step x y Plotted
(round)
• Solution: 0 2.0 3.0 (2, 3)
• dx = 10-2 = 8 1 3.0 3.625 (3, 4)
2 4.0 4.25 (4, 4)
• dy = 8-3 = 5 3 5.0 4.875 (5, 5)
• steps = max(8,5) = 8 4 6.0 5.5 (6, 6)
• x_inc = 8/8 = 1 5 7.0 6.125 (7, 6)
6 8.0 6.75 (8, 7)
• y_inc = 5/8 = 0.625 7 9.0 7.375 (9, 7)
8 10.0 8.0 (10, 8)
Advantages & Disadvantages of DDA
• Advantages:
• Conceptually simple, easy to implement.
• Works for all slopes (generalized form).
• Disadvantages:
• Uses floating-point arithmetic - slower.
• Rounding may cause accumulated error.
• Lines produced are not smooth.
• Not as efficient as integer-based methods.
Applications of DDA
• Used in early raster graphics systems.
• Useful for educational purposes - demonstrates rasterization.
• Still used in software rendering for small line-drawing tasks.
• Forms the base for Bresenham’s Algorithm (improved version).
References
• Foley, J. D., Dam, A.V, Feiner, S. K., & Hughes, J. F. Computer
Graphics: Principles and Practice in C, 2nd edition, Pearson
education, 1999.
Thank You
