KCES’s College of Engineering and Management, Jalgaon.
Unit 2: Raster scan Graphics
Presented By
Mrs. P M Chaudhari
Unit 2: Raster Scan Graphics
Introduction:
Raster scanning is a fundamental concept in
computer graphics and display technology. It is used
to draw an image line by line from top to bottom on a
screen. This method has been widely used in
television, computer monitors, and other digital
displays.
Raster Scan Graphics
2.1 Line Drawing algorithms: Digital
Differential Analyzer algorithm, Bresenham’s
algorithm
1. DDA algorithm:
The Digital Differential Analyzer (DDA) algorithm is
a line drawing algorithm used in computer graphics.
It works by calculating the intermediate pixel
positions along a line, using incremental steps based
on the slope between the two endpoints
DDA algorithm
How it works:
1. Input:
The algorithm takes the coordinates of the two
endpoints of the line (x0, y0) and (x1, y1) as input.
2. Calculate Differences:
It calculates the differences in x and y coordinates: dx
= x1 - x0 and dy = y1 - y0.
DDA algorithm:
3. Determine Steps:
It determines the number of steps needed to draw the line. If the
absolute value of dx is greater than the absolute value of dy, the
number of steps is |dx|; otherwise, it's |dy|.
4. Calculate Increments:
It calculates the increment values for x and y coordinates. If steps is
|dx|, then x-increment is dx / |dx| and y-increment is (dy/|dx|). If
steps is |dy|, then x-increment is (dx/|dy|) and y-increment is dy / |
dy|. These increments are either 1, -1, or 0, depending on the
direction of the line.
DDA algorithm
5. Iterate and Plot:
It iterates through the calculated steps, incrementing
the x and y coordinates by their respective increments
in each step. At each step, it plots a pixel at the
calculated (x, y) coordinates.
2.2 circle generation
Symmetry of circle
Symmetry of circle
Circles possess eight-way symmetry. If you know the
coordinates of points in one octant (e.g., from 45
degrees to 90 degrees), you can obtain the
coordinates for the other seven octants by appropriate
sign changes and swapping x and y.
Points in one octant can be mirrored to other 7.
It reduces computation.
Properties of a Circle
A circle is symmetric about:
◦ X-axis
◦ Y-axis
◦ Origin
◦ 45-degree (diagonal) lines
This symmetry allows generation of only 1/8th of the
circle and reflecting it
Circle Drawing Algorithms Overview
Midpoint Circle Algorithm
Bresenham’s Circle Algorithm
Trigonometric method (inefficient)
Bresenham’s Circle Algorithm – Concept
An extension of Bresenham’s Line Algorithm
Uses integer calculations only (no floating point)
Starts from topmost point (0, r)
Chooses between two pixel positions to stay close to
the circle path
Bresenham’s Circle Algorithm
Decision variable pk_:pkto choose next pixel
Initial decision:
p0=3−2r
Update rules:
If pk<0
xk+1=xk+1
pk+1=pk+4xk+6
Bresenham’s Circle Algorithm
Else:
xk+1=xk+1
yk+1=yk−1
pk+1=pk+4(xk−yk)+10
Algorithm Steps
Input radius r
Initialize: x=0, y=r, p=3−2rx = 0.
Loop until x≤y
Plot 8 symmetric points.
Update decision parameter.
Increment x, possibly decrement y.
End loop
Example
Let's say you want to draw a circle with center (0, 0)
and radius 4.
Initialize: x = 0, y = 4, d = 3 - 2 * 4 = -5.
Iteration 1:
◦ d < 0, so plot (0, 4) and (0, -4), (4, 0) and (-4, 0).
Update d=d+4x+6
d = -5 + 4 * 0 + 6 = 1.
◦ Since d >= 0, plot (1, 3) and (1, -3), (-1, 3) and (-1,
-3), (3, 1) and (3, -1), (-3, 1) and (-3, -1).
◦ Update d = 1 + 4 * (1 - 3) + 10 = 1 - 8 + 10 = 3.
Example
Continue: the process until x >= y.
2.3 Polygon filling:Seed fill algorithm-Flood fill
algorithm,Boundary fill algorithm.
Flood fill algorithm:
The flood fill (or seed fill) algorithm is a method
used in computer graphics for filling connected
regions of a polygon or image with a specified color.
It works by starting at a seed point (an interior pixel)
and recursively replacing the color of neighboring
pixels with the fill color until the boundary of the
region is reached
Flood Fill (Seed Fill) Algorithm:
Select a Seed Point: Choose a pixel within the polygon as
the starting point (the seed).
Check the Color: Determine the color of the seed pixel.
Recursive Filling:
◦ If the seed pixel's color matches the target color (the color
you want to replace), replace it with the fill color.
◦ Then, recursively call the flood fill function on the
neighboring pixels (e.g., up, down, left, right for 4-
connected, and also diagonals for 8-connected).
Boundary Check: The recursion stops when it encounters
a pixel that is not the target color (i.e., the boundary of the
region) or when all reachable pixels have been filled.
Types of Flood Fill:
4-Connected:
Only the four directly adjacent pixels (up, down, left,
right) are considered for filling.
8-Connected:
All eight surrounding pixels, including diagonals, are
considered for filling.
Example
Let's say you have a white polygon on a black
background, and you want to fill the interior with red.
You would select a point inside the polygon as your
seed, and the flood fill algorithm would replace all
the white pixels connected to that seed with red
Boundary Fill Algorithm
Concept: Starts with a seed point inside the polygon
and recursively fills the region until it reaches the
boundary of the polygon (defined by a specific
boundary color).
Process:
◦ Start: Choose a seed pixel inside the polygon.
◦ Check: Examine the neighboring pixels.
◦ Fill: If a neighbor's color is not the boundary color
or the fill color, fill it with the fill color and
recursively apply the same process to that neighbor.
Boundary Fill Algorithm
Boundary: If a neighbor has the boundary color, stop
filling in that direction.
Connectivity: Can use 4-connected or 8-connected
neighbors.
Advantages: Simple to implement and efficient for
filling polygons with a clear boundary color.
Disadvantages: Requires the boundary to be a single,
uniform color.
Key Differences
While both algorithms are used for polygon filling,
boundary fill focuses on finding and stopping at the
boundary color, whereas flood fill replaces interior
colors until the boundary is reached.