Chapter 3
Scan Conversion
Dr. S.M. Mohidul Islam
Associate Professor
CSE Discipline, KU
Chapter 3 Contents
Introduction
3.1 Scan-Converting a Point
3.2 Scan-Converting a Line
3.3 Scan-Converting a Circle
3.4 Scan-Converting an Ellipse
3.5 Scan-Converting Arcs and Sectors
3.6 Scan-Converting a Rectangle
3.7 Region Filling
3.8 Scan-Converting a Character
3.9 Anti-Aliasing (Partial)
3.10 Example: Recursively Defined Drawings
Solved & Supplementary Problems
Introduction
The conversion task of the picture components/primitives (such as
points, lines, circles, and filled polygons) from the continuous
space to the discrete image space is generally referred to as
scan conversion or rasterization.
A ystematic approach to mapping objects from continuous space to
their discrete approximation
3.1 Scan-Converting a Point
First approach: x / = Floor ( x) Another approach: x / = Floor( x + 0.5)
y = Floor ( y )
/
y / = Floor( y + 0.5)
3.2 Scan-Converting a Line
A note of caution: this slope-intercept equation is not suitable for vertical lines.
Horizontal, Vertical, and Diagonal lines can, and often should be handled as special cases
without going through the following scan-conversion algorithms.
Direct Use of the Line Equation
Steps
Scan Convert P1 and P2
Set m = ∆y/∆x = (y2/ - y1/)/(x2/-x1/), b = y1/-mx1/
If 𝑚 <=1: for every x find y. Scan convert
Else: for every y find x. Scan convert
Advantage: Mathematically sound
Disadvantage: Floating-point computation (multiplication and
addition) in every step (m and b)
DDA Algorithm (Digital Differential Analyzer)
Incremental scan conversion method: Perform calculations at each step
using results from the preceding step
Current point (xi, yi), next point (xi+1, yi+1) satisfy m =∆y/∆x, where ∆y = yi+1-yi
and ∆x = xi+1-xi .
We have, yi+1= yi + ∆y = yi + 𝐦∆𝒙 and xi+1= xi + ∆x = xi + ∆𝒚/m
Steps
Scan covert (x1, y1) and (x2, y2)
Set m = ∆y/∆x = (y2/ - y1/)/(x2/-x1/)
if 𝑚 <= 1: start with x = x1/ , y = y1/ and set ∆x = 1. Find yi+1= yi + m.
Scan convert. Continue until x reaches x2/
Else: start with x = x1/ , y = y1/ and set ∆y = 1. Find xi+1= xi + 1/m. Scan
convert. Continue until y reaches y2/
Advantage: Faster than direct use of line equation
Disadvantage: A floating point addition is still needed
Bresenham's Line Algorithm
Scan covert P1(x1, y1) and P2(x2, y2)
Set m = ∆y/∆x = (y2/ - y1/)/(x2/-x1/)
Method for the line having 0 < m < 1:
The coordinates of the last chosen pixel upon entering step i are (xi, yi)
Choose the next one between the bottom pixel S and the top pixelT.
If S is chosen, we have xi+1 = xi + 1 and yi+1 =yi. S(xi + 1, yi)
If T is chosen, we have xi+1 = xi + 1 and yi+1 =yi+ 1. T(xi + 1, yi+1)
The distance from S to the actual line in the y direction is s = y -yi
The distance from T to the actual line in the y direction is t = (yi + 1) – y
❑ Actual y coordinate of the line at x = xi+1 is y = mxi+l + b = m(xi + 1) + b.
When s - t is less than zero, we
have s < t and the closest pixel
is S.
Conversely, when s - t is
greater than zero, we have s >
t and the closest pixel is T.
We also choose T when s - t is
equal to zero.
This difference is,
s-t = (y-yi)-[(yi+1)-y]
= 2y- 2yi - 1
= 2m(Xi +l) + 2b- 2yi - 1
Substituting m by ∆y/∆x and introducing a decision variable di = ∆x(s - t), which
has the same sign as (s - t) since ∆x is positive in our case, we have
di = 2∆y*xi - 2∆x*yi + C where C = 2∆y + ∆x(2b - 1)
Similarly, we can write the decision variable di+1 for the next step as
di+l = 2∆y*xi+l - 2∆x*yi+l + C
Then di+1 - di = 2∆y(xi+l - xi) - 2∆x(yi+l - yi)
Since xi+l = xi + 1, we have di+l = di + 2∆y - 2∆x(yi+l - yi)
If the chosen pixel is the top pixel T (meaning that di >= 0) then yi+l = yi + 1 and so di+l = di
+ 2(∆y - ∆x)
On the other hand, if the chosen pixel is the bottom pixel S (meaning that di < 0) then yi+l = yi and
so di+1 = di + 2∆y
Hence we have
Finally, we calculate d1, the base case value for this recursive formula, from the original
definition of the decision variable di:
d1 = ∆x[2m(xl + l) + 2b- 2y1 - 1]
= ∆x[2(mxl +b -yl) + 2m- I]
Since mxl +b - yl = 0, we have d1 = 2∆y - ∆x
❑ In summary:
For line with -1 < m < 0
negate the y coordinate at the end of each iteration to set the right pixel for the line.
For a line whose slope is in the 45° to 90° range.
exchange x and y in the call to setPixel.
Advantages: Bresenham's line algorithm is a highly efficient incremental
method for scan-converting lines.
It produces mathematically accurate results using only integer addition,
subtraction, and multiplication by 2, which can be accomplished by a simple
arithmetic shift operation.
3.3 Scan-Converting a Circle
A circle is a symmetrical figure.
Eight-way symmetry is used by reflecting each calculated point around each 45°
axis.
Defining a Circle
Two standard methods of mathematically defining a circle centered at the
origin: Second-order polynomial equation, trigonometric functions
If a circle is to be plotted efficiently, the use of trigonometric and power functions must be avoided.
Bresenham's Circle Algorithm
Points are generated from 90° to 45°.
Centered at the origin
Assume that (xi, yi) are the coordinates of
the last scan-converted pixel upon entering
step i.
Next pixel will be either T(xi+1, yi) or
S(xi+1, yi-1)
Let the distance from the origin to pixel T
squared minus the distance to the true
circle squared = D(T). Similarly D(s)
D(T) = (xi+1)2 + yi2 - r2
D(S) = (xi+1)2 +(yi-1)2- r2
Since D(T) will always be positive (T is
outside the true circle) and D(S)…..; a When di < 0, we have |D(T)| <
decision variable di may be defined as: |D(S)| and pixel T is chosen.
di = D(T)+D(S)
When di > 0, we have |D(T)| >
= 2(xi+1)2 + yi2 + (yi-1)2 - 2r2 |D(S)|and pixel S is selected.
di = 2(xi+1)2 + yi2 + (yi-1)2 - 2r2
di+1 = 2(xi+1+1)2 + yi+12 + (yi+1-1)2 -
2r2
di+1 – di = 2(xi+1+1)2 + yi+12 + (yi+1-
1)2 - 2(xi+1)2 - yi2 - (yi-1)2
Since xi+1 = xi +1, we have
di+1 = di + 4xi + 2(yi+12 - yi2) -2(yi+1-yi)
+6
If T is the chosen pixel (meaning
that di < 0) then yi+l = yi and so
di+1 = di + 4xi + 6 Finally, we set (0, r) to be the starting pixel
coordinates and compute the base case value d1
Otherwise, di+1 = di + 4(xi- - yi) + 10 for this recursive formula from the original
definition of di.
Hence, we have d1 = 2(0 + 1)2 + r2 + (r - 1)2 - 2r2
= 3 - 2r
The Bresenham’s Circle algorithm for
yi+l = yi
generating all the pixel coordinates in the
90° to 45° octant that are needed when yi+l = yi - 1
scan-converting a circle of radius r: d1 = 3 - 2r At (0, r)
Midpoint Circle Algorithm
Another incremental circle algorithm, very similar to Bresenham's approach
based on the following function for testing the spatial relationship
between an arbitrary point (x, y) and a circle of radius r centered
at the origin:
• Consider the coordinates of the point halfway
between pixel T and pixel S: (xi + 1, yi - 12). This
is called the midpoint and we use it to define a
decision parameter
• pi = f(xi+1, yi- 12) = (xi+1)2 + (yi- 12)2 - r2
❑ If pi is negative, the midpoint is inside the
circle, and we choose pixel T.
❑ If pi is positive (or equal to zero), the
midpoint is outside the circle (or on the
circle), and we choose pixel S.
pi= (xi+1)2 + (yi- 12)2 - r2
1
pi+1 = (xi+1+1)2 + (yi+1- )2 - r2
2
1
pi+1 – pi = (xi+1+1)2 - (xi+1)2 + (yi+1- 2)2 - (yi- 12)2
Since xi+1 = xi +1, we have
pi+1 = pi + (xi+1+1)2 - (xi+1)2 + (yi+1- 12)2 - (yi- 12)2
If T is the chosen pixel (pi < 0) then yi+l = yi and so pi+1 = pi + 2xi + 3
Otherwise, S is the chosen pixel (pi >= 0) then yi+l = yi -1 & so pi+1 = pi + 2(xi- - yi) + 5
Hence, we have
Finally, we compute the initial value for the decision parameter using the
original definition of pi and starting pixel coordinate(0, r):
1
p1 = (0 + 1)2 + (r - 2)2 - r2
= 54 - r = 1 - r
The Midpoint Circle algorithm for
yi+l = yi
generating all the pixel coordinates in the
90° to 45° octant that are needed when yi+l = yi - 1
scan-converting a circle of radius r: p1 = 1 - r At (0, r)
Arbitrarily Centered Circles
To scan-convert a circle centered at (xc, yc), we can simply replace
the setPixel(x, y) statement in the algorithm description with
setPixel(x + xc, y +yc).
3.5 Scan-Converting Arcs and Sectors
Arcs: Generated using either the trigonometric method or the
polynomial method
❑x = r cos𝜃 y = r s𝑖𝑛𝜃
Trigonometric method
The starting value of 𝜃 is set equal to 𝜃1 and the ending value is set equal to 𝜃 2 and the
values of x and y are found by evaluating the expressions x = r cos𝜃 and y = r s𝑖𝑛𝜃
(Similar to circle but symmetry is not used); (Center at the origin).
x2 + y2 = r2
Polynomial method
The starting value of x is set equal to 𝑥1 and the ending value is
set equal to 𝑥 2 and the values of y are found by evaluating the
expression y = r − x
2 2
(Similar to circle but symmetry is not used); (Center at the origin)
Why Bresenham’s circle algorithm is not a good method
From the graphics programmer's point of view, arcs would appear to be
nothing more than portions of circles. However, problems occur if
algorithms such as Bresenham's circle algorithm are used in drawing an
arc. In the case of Bresenham's algorithm, the endpoints of an arc must be
specified in terms of the x,y coordinates. The general formulation becomes
inefficient when endpoints must be found (see Fig. 3-15).
• This occurs because the endpoints for each 45° increment of
the arc must be found. Each of the eight points found by
reflection must be tested to see if the point is between the
specified endpoints of the arc. As a result, a routine to draw an
arc based on Bresenham's algorithm must take the time to
calculate and test every point on the circle's perimeter. There
is always the danger that the endpoints will be missed when a
method like this is used. If the endpoints are missed, the
routine can become caught in an infinite loop.
Sectors
A sector is scan-converted by using any of the methods of scan-converting an
arc and
then scan-converting two lines from the center of the arc to the endpoints of the
arc.
For example, assume that a sector whose center is at point (h, k) is to be
scan-converted.
First, scan-convert an arc from 𝜃 1 to 𝜃2
Next, a line would be scan-converted from (h,k) to (r cos (𝜃1)+h, r sin (𝜃1) + k). A
second line would be scan-converted from (h, k) to (r cos(𝜃2) + h, r sin(𝜃2) + k)
3.6 Scan-Converting a Rectangle
A rectangle whose sides are parallel to the coordinate axes may be
constructed if the locations of two vertices are known [Fig. 3-16(a)].
The remaining corner points are then derived [Fig. 3-16(6)].
Once the vertices are known, the four sets of coordinates are sent to
the line routine and the rectangle is scan-converted.
In the case of the rectangle shown in Figs., lines would be drawn as follows:
line (x1, y1) to (xl, y2)
line (xl,y2) to (x2,y2)
line (x2,y2) to (x2,y1), and
line (x2,y1) to (x1,y1).
3.9 Anti-Aliasing
❑ The various forms of distortion that result from scan-
conversion are collectively referred to as the aliasing effects of
scan conversion.
Staircase
see when scan-converting a primitive such as a line or a circle.
also see along the border of a filled region.
Unequal Brightness
The Picket Fence Problem
Global aliasing
Local aliasing
3.10 Example: Recursively Defined Drawings
C Curve
A line by itself is a first-order C curve (denoted by Co).
The modification rule for constructing successive generations of the C
curve is to
replace a line by two shorter, equal-length lines joining each other at a 90°
angle,
with the original line and the two new lines forming a right-angled triangle.
❑ The Koch Curve
a line by itself is a first-order Koch curve (denoted by Ko).
The modification rule for constructing successive generations of the Koch
curve is to
divide a line into three equal segments and replace the middle segment with two lines
of the same length (the replaced segment and the two added lines form an equilateral
triangle).
❑ The Sierpinski Gasket
a filled triangle by itself is a first-order Sierpinski gasket (denoted by So).
The modification rule for constructing successive generations of the
Sierpinski gasket is to
take out the area defined by the lines connecting the midpoint of the edges of a filled
triangle, resulting in three smaller ones that are similar to the original.
Problems
Solved Problems: 3.1–3.14, 3.16-3.19, 3.24-3.26, 3.31
Supplementary Problems: 3.35-3.37, 3.40, 3.42, 3.44
Bresenham’s circle algorithm is **excellent for drawing a full circle**.
But an **arc is only a part of a circle** — not the whole thing.
That is where problems start.
For a full circle:
* We just keep generating points until one octant is complete.
* No need to worry about where to stop — symmetry handles everything.
For an arc:
* We must start and stop at specific points.
* These endpoints must be given in **(x, y)** coordinates.
* That means extra calculation is needed to find those points.
This makes it more complicated.
Problem: 8-way Symmetry Creates Extra Work
bresenham uses **8-way symmetry**.
For every calculated point, it reflects it into 8 positions.
For an arc:
* Not all 8 reflected points belong to the arc.
* So every reflected point must be **tested**:
Chapter 3 End
“Is this point inside the required angle range?”
That means:
* Extra checking
* Extra computation
* Reduced efficiency
Problem: Inefficiency
To draw a small arc:* The algorithm may still compute **almost the whole circle*** Because it keeps generating perimeter points* And testing
whether each belongs to the arc. So it wastes time calculating unnecessary points.
Risk: Missing Endpoints - Because Bresenham works in integer steps:
* The exact endpoint might not match a generated pixel
* So the arc might:
* Stop too early
* Or never exactly hit the endpoint .In worst cases:* If the stopping condition is wrong, The loop might never terminate* It can go into an
**infinite oop**Bresenham’s circle algorithm is not good for arcs because:
1. Endpoints must be calculated separately.
2. Every reflected point must be tested.
3. It computes many unnecessary points.
4. It may miss endpoints.
5. It can even cause infinite loops.