Complete RGPV exam-oriented notes on scan conversion, image representation,
DDA and Bresenham algorithms, circle generation, Bezier curves and B-spline curves.
1. Introduction to Scan Conversion and Drawing Algorithms
Computer graphics drawing algorithms convert mathematical descriptions of
lines, circles and curves into discrete pixels that can be displayed on a raster screen.
A graphics application usually describes an object using coordinates and equations.
However, a raster display can illuminate only individual pixels. Therefore, an algorithm
must decide which pixels best represent the required geometric object.
Need for Drawing Algorithms
To convert continuous mathematical shapes into discrete pixels.
To draw lines, circles and curves accurately.
To reduce computation time.
To minimize gaps and irregular edges.
To provide smooth visual output.
Mathematical Object
|
v
Drawing Algorithm
|
v
Selected Pixel Coordinates
|
v
Raster Display
2. Scan Conversion
Scan conversion is the process of converting the geometric description of an object
into a set of pixels for display on a raster screen.
A line is mathematically continuous, but a raster screen contains separate square pixels.
Scan conversion selects the pixels that lie closest to the ideal line or curve.
Objects Requiring Scan Conversion
Points
Lines
Circles
Ellipses
Polygons
Curves
Text characters
Properties of a Good Scan Conversion Algorithm
High speed
Minimum arithmetic operations
Accurate pixel selection
Uniform brightness
Continuous output without gaps
Use of integer calculations wherever possible
3. Image Representation
A digital image is represented as a two-dimensional array of pixels. Each pixel stores
an intensity or colour value.
Image = f(x, y)
Here, x and y represent pixel coordinates and
f(x,y) represents the intensity or colour of the pixel.
Binary Image
Each pixel contains only one bit. A pixel is either black or white.
Grayscale Image
Each pixel stores a brightness value. An 8-bit grayscale image generally provides
256 intensity levels from 0 to 255.
Colour Image
Each pixel contains multiple colour components. In the RGB model, a pixel stores red,
green and blue intensity values.
Image Type
Pixel Information
Example
Binary
1 bit per pixel
Black and white document
Grayscale
Intensity value
X-ray image
Colour
RGB components
Digital photograph
4. Line Generation
A straight line between two points can be represented using the slope-intercept equation:
y = mx + c
Here, m is the slope and c is the y-intercept.
For endpoints (x₁,y₁) and (x₂,y₂):
m = (y₂ - y₁) / (x₂ - x₁)
Directly using this equation requires multiplication, division and rounding for each pixel.
Therefore, incremental algorithms such as DDA and Bresenham are used.
5. Digital Differential Analyzer (DDA) Line Algorithm
DDA is an incremental line drawing algorithm that calculates each new point by adding
small fixed increments to the previous point.
Basic Idea
The larger difference between x and y coordinates determines the number of steps.
The x and y increments are then calculated and repeatedly added.
Bresenham line algorithm selects the nearest pixel using a decision parameter
and mainly performs integer addition and subtraction.
Consider a line with slope between 0 and 1. Starting from the left endpoint, the next pixel
is selected from the east pixel E or north-east pixel NE.
NE (x+1, y+1)
•
/
Current • ---- • E (x+1, y)
Initial Decision Parameter
p₀ = 2dy - dx
Decision Rules
If p < 0, select E and update p = p + 2dy.
If p ≥ 0, select NE and update p = p + 2dy - 2dx.
Algorithm
Step 1: Read (x1,y1) and (x2,y2)
Step 2: dx = x2 - x1
Step 3: dy = y2 - y1
Step 4: p = 2dy - dx
Step 5: x = x1, y = y1
Step 6: Plot (x,y)
Step 7: While x < x2:
x = x + 1
If p < 0:
p = p + 2dy
Else:
y = y + 1
p = p + 2dy - 2dx
Plot (x,y)
Advantages
Uses integer arithmetic.
Faster than DDA.
No floating-point rounding is required.
Produces accurate and continuous lines.
Disadvantages
Basic derivation is commonly shown only for 0 ≤ slope ≤ 1.
Different cases are needed for other slopes and directions.
More difficult to understand than DDA.
Exam Tip: For a complete answer, draw the E and NE candidate pixel diagram,
write the initial decision parameter and explain both update cases.
DDA vs Bresenham Line Algorithm
Basis
DDA Algorithm
Bresenham Algorithm
Arithmetic
Floating-point calculations
Integer calculations
Rounding
Required
Normally not required
Speed
Slower
Faster
Accuracy
May accumulate error
More accurate
Implementation
Simple
Moderately complex
7. Circle Generation
A circle with center (xc, yc) and radius r is represented by:
(x - xc)² + (y - yc)² = r²
Circle drawing algorithms use symmetry to reduce calculations. A circle has eight-way symmetry.
If one point (x,y) is known, seven other symmetric points can be generated.
Starting from x = -r to x = r, corresponding y values can be calculated.
However, this method requires square root calculations and may generate uneven pixel spacing.
Advantages
Directly based on the circle equation.
Easy to understand mathematically.
Disadvantages
Uses square root operations.
Computationally expensive.
May produce gaps near steep regions.
Not suitable for efficient raster graphics.
9. Symmetric DDA Circle Algorithm
Symmetric DDA generates a circle by using incremental rotation and symmetry.
For a small angular increment ε:
xnew = x - εy
ynew = y + εx
The algorithm starts from a point such as (r,0). New points are calculated repeatedly,
and symmetry is used to display the remaining sections of the circle.
Advantages
Incremental method
Uses circle symmetry
More efficient than direct equation method
Disadvantages
May use floating-point calculations.
Approximation errors may accumulate.
Less efficient than Bresenham circle algorithm.
10. Bresenham Circle Drawing Algorithm
Bresenham circle algorithm uses an integer decision parameter and eight-way symmetry
to generate a circle efficiently.
Starting Point
x = 0, y = r
p₀ = 3 - 2r
Decision Rules
If p < 0, choose the east pixel and update p = p + 4x + 6.
If p ≥ 0, choose the south-east pixel, decrease y and update p = p + 4(x-y) + 10.
Algorithm
Step 1: Input center (xc,yc) and radius r
Step 2: x = 0, y = r
Step 3: p = 3 - 2r
Step 4: Plot eight symmetric points
Step 5: While x <= y:
If p < 0:
p = p + 4x + 6
Else:
p = p + 4(x - y) + 10
y = y - 1
x = x + 1
Plot eight symmetric points
A curve is a smooth path generated using mathematical equations and control points.
Curves are used to model shapes that cannot be represented accurately using only straight lines.
They are important in CAD, animation, industrial design, fonts and three-dimensional modeling.
Types of Curves
Explicit curves
Implicit curves
Parametric curves
Bezier curves
B-spline curves
12. Parametric Functions
In parametric representation, x and y coordinates are expressed as functions of a third
parameter, usually t.
x = x(t)
y = y(t)
0 ≤ t ≤ 1
Example: Line Segment
P(t) = (1-t)P₀ + tP₁
Advantages
Can represent multi-valued curves.
Easy to generate points in sequence.
Suitable for transformations.
Works well for Bezier and B-spline curves.
13. Bezier Curve
A Bezier curve is a parametric curve defined by control points and Bernstein polynomial
blending functions.
If there are n+1 control points P₀, P₁, ..., Pₙ, the Bezier curve is:
P(t) = Σ PiBi,n(t), 0 ≤ t ≤ 1
where the Bernstein polynomial is:
Bi,n(t) = C(n,i)ti(1-t)n-i
Cubic Bezier Curve
A cubic Bezier curve uses four control points P₀, P₁, P₂ and P₃.
The first and last control points lie on the curve.
The curve lies inside the convex hull of control points.
The degree is one less than the number of control points.
The starting tangent follows P₀P₁.
The ending tangent follows Pₙ₋₁Pₙ.
Moving one control point can affect the entire curve.
Advantages
Simple mathematical representation.
Easy to design smooth curves.
Widely used in fonts and vector graphics.
Disadvantages
No local control.
Degree increases with the number of control points.
Complex shapes may require joining multiple Bezier segments.
14. B-Spline Curve
A B-spline curve is a piecewise polynomial curve controlled by control points,
basis functions and a knot vector.
P(t) = Σ PiNi,k(t)
Here, Pi are control points and Ni,k(t) are B-spline basis functions
of order k.
Main Features
Provides local control.
Degree is independent of the number of control points.
Uses piecewise polynomial segments.
Can represent complex shapes smoothly.
Usually does not pass through all control points.
Knot Vector
A knot vector is a sequence of parameter values that determines where and how the curve segments
are joined.
Advantages
Local control of shape.
Stable for a large number of control points.
Supports smooth complex curves.
Degree can remain fixed.
Disadvantages
More complex than Bezier curves.
Requires selection of knot vector and degree.
Mathematical evaluation is harder for beginners.
15. Bezier Curve vs B-Spline Curve
Basis
Bezier Curve
B-Spline Curve
Control
Global control
Local control
Degree
Depends on number of control points
Independent of number of control points
Control point modification
Affects entire curve
Affects only nearby portion
Mathematical complexity
Simple
More complex
Knot vector
Not required
Required
Complex shapes
May need multiple joined segments
Handled efficiently
Algorithm Selection Summary
Requirement
Suitable Method
Reason
Simple line implementation
DDA
Easy to understand
Fast line generation
Bresenham Line
Integer operations
Fast circle generation
Bresenham Circle
Integer decision parameter and symmetry
Simple smooth curve
Bezier Curve
Easy control-point model
Complex curve with local editing
B-Spline Curve
Local control
Complete Unit Summary
Scan conversion converts geometric objects into raster pixels.
Digital images are stored as matrices of pixel intensity or colour values.
DDA generates line points using floating-point increments.
Bresenham line algorithm uses an integer decision parameter.
Circle algorithms use eight-way symmetry.
The general circle method uses square roots and is computationally expensive.
Bresenham circle algorithm is efficient because it uses integer calculations.
Parametric equations represent coordinates using a parameter t.
Bezier curves offer simple global control.
B-spline curves provide local control and fixed degree.
Important RGPV Exam Questions
Long Answer Questions
Explain the DDA line drawing algorithm with steps, example, advantages and disadvantages.
Derive and explain the Bresenham line drawing algorithm with a suitable example.
Compare DDA and Bresenham line drawing algorithms.
Explain the general circle drawing method and symmetric DDA circle algorithm.
Explain Bresenham circle drawing algorithm using eight-way symmetry.
What is a Bezier curve? Explain its equation, properties and applications.
Explain B-spline curves and compare them with Bezier curves.
Explain scan conversion and image representation in computer graphics.
Short Answer Questions
Define scan conversion.
What is image representation?
Write the initial decision parameter of Bresenham line algorithm.
What is eight-way symmetry?
Define a parametric curve.
What is a control point?
What is a knot vector?
State two properties of Bezier curves.
Common Exam Mistake: In numerical algorithms, do not write only the formula.
Show dx, dy, steps or decision parameter, iteration table and final plotted pixels.
Exam Writing Strategy
For Algorithm Questions: Write definition, basic idea, formula,
complete steps, one solved example, advantages and disadvantages.
For Curve Questions: Draw the control polygon, write the curve equation,
explain properties and add Bezier vs B-spline comparison.