SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Subject Name: GRAPHICS & IMAGE PROCESSING Subject Code: CS T46
Prepared by:
RB.THIYAGARAJAN, AP/CSE
P. VIJAYAKUMAR, AP/CSE
P.SUBHAPRIYA, AP/CSE
Verified by: Approved by:
UNIT II
Geometric Display Primitives and Attributes: Geometric display primitives – Points – Lines and
Polygons – Point display method – Line drawing methods.
2D Transformations and Viewing: Transformations – types – matrix representation – Concatenation –
Scaling – Rotation – Translation – Shearing – Mirroring – Homogeneous coordinates.
Window to view port transformations: Windowing And Clipping: Point – Lines – Polygons -
boundary intersection methods.
DISPLAY PRIMITIVES AND ATTRIBUTES
LINE DRAWING ALGORITHM
Line drawing is our first adventure into the area of scan conversion. The need for scan
conversion, or rasterization, techniques is a direct result of scanning nature of raster displays.
The goal of any line drawing algorithm is to construct the best possible approximation of an ideal
line given the inherent limitations of a raster display. Following is a list of some of line qualities that are
often considered.
Continuous appearance
Uniform thickness and brightness
Are the pixels nearest the ideal line turned on
How fast is the line generated
The Bresenham line algorithm is an algorithm that determines which points in an n-dimensional
raster should be plotted in order to form a close approximation to a straight line between two given
GRAPHICS & IMAGE PROCESSING Page 1
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
points. It is commonly used to draw lines on a computer screen, as it uses only integer addition,
subtraction and bit shifting all of which are very cheap operations in standard computer architectures. It
is one of the earliest algorithms developed in the field of computer graphics.
Through a minor expansion, the original algorithm for lines can also be used to draw circles. Also
this can be done with simple arithmetic operations; quadratic or trigonometric expressions can be
avoided or recursively dissolved into simpler steps.
The common conventions that pixel coordinates increase in the down and right directions and that
pixel centers have integer coordinates will be used. The endpoints of the line are the pixels at (x0, y0)
and (x1, y1), where the first coordinate of the pair is the column and the second is the row.
The algorithm will be initially presented only for the octant in which the segment goes down and to
the right (x0≤x1 and y0≤y1 ) , and its horizontal projection x1 − x0 is longer than the vertical projection y1
− y0 (in other words, the line has a slope less than 1 and greater than 0.) In this octant, for each column x
between x0 and x1, there is exactly one row y (computed by the algorithm) containing a pixel of the line,
while each row between y0 and y1 contains multiple rasterized pixels.
Bresenham's algorithm chooses the integer y corresponding to the pixel center that is closest to the
ideal (fractional) y for the same x; on successive columns y can remain the same or increase by 1. The
general equation of the line through the endpoints is given by:
Since we know the column, x, the pixel's row, y, is given by rounding this quantity to the nearest
integer:
The slope (y1 − y0) / (x1 − x0) depends on the endpoint coordinates only and can be precomputed,
and the ideal y for successive integer values of x can be computed starting from y0 and repeatedly
adding the slope.
In practice, the algorithm can track, instead of possibly large y values, a small error value
between −0.5 and 0.5: the vertical distance between the rounded and the exact y values for the current x.
Each time x is increased, the error is increased by the slope; if it exceeds 0.5, the rasterization y is
GRAPHICS & IMAGE PROCESSING Page 2
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
increased by 1 (the line continues on the next lower row of the raster) and the error is decremented by
1.0.
In the following pseudocode sample plot(x,y) plots a point and abs returns absolute value:
function line(x0, x1, y0, y1)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := deltay / deltax // Assume deltax != 0 (line is not vertical)
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if abs(error) ≥ 0.5 then
y := y + 1
error := error - 1.0
Illustration of the result of Bresenham's line algorithm.
The basic Bresenham algorithm
Consider drawing a line on a raster grid where we restrict the allowable slopes of the line to the
range .
If we further restrict the line-drawing routine so that it always increments x as it plots, it becomes
clear that, having plotted a point at (x,y), the routine has a severely limited range of options as to where
it may put the next point on the line:
GRAPHICS & IMAGE PROCESSING Page 3
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
It may plot the point (x+1,y), or:
It may plot the point (x+1,y+1).
So, working in the first positive octant of the plane, line drawing becomes a matter of deciding
between two possibilities at each step.
We can draw a diagram of the situation which the plotting program finds itself in having plotted (x,y).
In plotting (x,y) the line drawing routine will, in general, be making a compromise between what
it would like to draw and what the resolution of the screen actually allows it to draw. Usually the plotted
point (x,y) will be in error, the actual, mathematical point on the line will not be addressable on the pixel
grid. So we associate an error, , with each y ordinate, the real value of y should be . This
error will range from -0.5 to just under +0.5.
In moving from x to x+1 we increase the value of the true (mathematical) y-ordinate by an
amount equal to the slope of the line, m. We will choose to plot (x+1,y) if the difference between this
new value and y is less than 0.5.
Otherwise we will plot (x+1,y+1). It should be clear that by so doing we minimise the total error
between the mathematical line segment and what actually gets drawn on the display.
The error resulting from this new point can now be written back into , this will allow us to repeat the
whole process for the next point along the line, at x+2.
The new value of error can adopt one of two possible values, depending on what new point is plotted. If
(x+1,y) is chosen, the new value of error is given by:
GRAPHICS & IMAGE PROCESSING Page 4
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
Otherwise it is:
This gives an algorithm for a DDA which avoids rounding operations, instead using the error variable
to control plotting:
This still employs floating point values. Consider, however, what happens if we multiply across both
sides of the plotting test by and then by 2:
All quantities in this inequality are now integral.
Substitute for . The test becomes:
This gives an integer-only test for deciding which point to plot.
The update rules for the error on each step may also be cast into form. Consider the floating-point
versions of the update rules:
GRAPHICS & IMAGE PROCESSING Page 5
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
Multiplying through by yields:
which is in form.
Using this new ``error'' value, , with the new test and update equations gives Bresenham's integer-
only line drawing algorithm:
Integer only - hence efficient (fast).
Multiplication by 2 can be implemented by left-shift.
This version limited to slopes in the first octant, .
ALGORITHM FOR GENERATING CIRCLE
Many incremental methods exist to plot circles and arcs.
1) If the hardware exists for line generation, then circles are generated using short line segments.
2) If the line generation hardware does not exist, then circles are generated using closely spaced dots.
Central Symmetry
A usable fact is that if the center of the circle is at location (0,0) and a point (x,y) lies on the
circumference of the circle, then we know 7 more points on the circle.
GRAPHICS & IMAGE PROCESSING Page 6
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
We can set eight symmetric pixels that correspond to a point (x,y) on the circle using the following
procedure:
procedureset_eight(x,y,xcenter,ycenter:integer);
begin
plot_pixel(x+xcenter,y+ycenter);
plot_pixel(-x+xcenter,y+ycenter);
plot_pixel(x+xcenter,-y+ycenter);
plot_pixel(-x+xcenter,-y+ycenter);
plot_pixel(y+xcenter,x+ycenter);
plot_pixel(-y+xcenter,x+ycenter);
plot_pixel(y+xcenter,-x+ycenter);
plot_pixel(-y+xcenter,-x+ycenter);
end;
Circle Generating Algorithms
Non-DDA Methods
1) Parameter Method - this method consists of calculating values (x,y) on the circle using the following
formulas:
x=rcos(u)
y = rsin(u)
where u increases incrementally by small steps over the interval 0 to 2(pi). We can use symmetry to
improve the execution time so that u is calculated over the interval 0 to pi/4. We also note that if the
incremental value of u is <= 1/r, where r is the length of r expressed in pixels, the circle generator
advances by approximately one pixel each iteration. This algorithm is slow because of the constant
recalulation of sin(u) and cos(u).
are generating a circle from the origin with radius 10. This would imply the following table of values:
GRAPHICS & IMAGE PROCESSING Page 7
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
u X=rcos(u) Y=rsin(u)
0 10 0
.1 9.95 .999
.2 9.8 1.99
.3 9.55 2.96
.4 9.21 3.89
.5 8.78 4.79
.6 8.25 5.65
.7 7.65 6.44
.8 6.97 7.17 (Note: pi/4 = .7854)
....
1.5708 0 10 (Note: pi/2 = 1.5708)
2) Rotation Method - this method consists of using the point (x,y) on the circle and rotating it about the
origin. The following equations will produce the desired result:
a) Clockwise
Xrot=Xcos(u)+Ysin(u)
Yrot = -Xsin(u) + Ycos(u)
b) Counterclockwise
Xrot=Xcos(u)-Ysin(u)
Yrot = Xsin(u) + Ycos(u)
To use the rotation method, we assign (X0,Y0) equal to (r,0). We can then use the following equations
to generate successive points:
Xn+1=Xncos(u)-Ynsin(u)
Yn+1 = Xnsin(u) + Yncos(u)
ELLIPSE GENERATING ALGORITHM
GRAPHICS & IMAGE PROCESSING Page 8
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
• 2a is the length of the major axis along the x axis.
• 2b is the length of the minor axis along the y axis.
• The midpoint can also be applied to ellipses.
• For simplicity, we draw only the arc of the ellipse that lies in the first quadrant, the other three
quadrants can be drawn by symmetry
• Firstly we divide the quadrant into two regions
• Boundary between the two regions is
– the point at which the curve has a slope of -1
– the point at which the gradient vector has the i and j components of equal magnitude
• At the next midpoint, if a2(yp-0.5)<=b2(xp+1), we switch region 1=>2
• In region 1, choices are E and SE
– Initial condition: dinit = b2+a2(-b+0.25)
– For a move to E, dnew = dold+DeltaE with DeltaE = b2(2xp+3)
– For a move to SE, dnew = dold+DeltaSE with
DeltaSE = b2(2xp+3)+a2(-2yp+2)
• In region 2, choices are S and SE
– Initial condition: dinit = b2(xp+0.5)2+a2((y-1)2-b2)
– For a move to S, dnew = dold+Deltas with Deltas = a2(-2yp+3)
– For a move to SE, dnew = dold+DeltaSE with
DeltaSE = b2(2xp+2)+a2(-2yp+3)
• Stop in region 2 when the y value is zero.
GRAPHICS & IMAGE PROCESSING Page 9
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
AREA FILLED ATTRIBUTES
It is an area filled with the foreground color, but it depends on the current interior style. The
SOLID style depends only on the foreground color. The HATCH and STIPPLE style depend on the
foreground color, background color and on the back opacity attribute. The hatch lines drawn with this
style do not depend on the other line attributes. The PATTERN style depends only on global canvas
attributes.
The filled area includes the line at the edge of the area. So if you draw a filled rectangle, sector
or polygon on top of a non filled one using the same coordinates, no style and 1 pixel width, the non
filled primitive should be obscured by the filled primitive. But depending on the driver implementation
some pixels at the edges may be not included. IMPORTANT: In the Postscript and PDF drivers the line
at the edge is not included at all.
If either the background or the foreground color are modified, the hatched and monochromatic
fillings must be modified again in order to be updated.
Note that when a Filling Attribute is modified, the active filling style is now that of the modified
attribute (hatch, stipple or pattern). Notice that this is not true for the clipping area. When the clipping
area is modified, the clipping is only affected if it is active.
Fills the arc of an ellipse aligned with the axis, according to the current interior style, in the
shape of a pie. It is drawn counter-clockwise. The coordinate (xc,yc) defines the center of the ellipse.
Dimensions w and h define the elliptic axes X and Y, respectively.
GRAPHICS & IMAGE PROCESSING Page 10
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
Angles angle1 and angle2, in degrees, define the arc's beginning and end, but they are not the
angle relative to the center, except when w==h and the ellipse is reduced to a circle. The arc starts at the
point (xc+(w/2)*cos(angle1),yc+(h/2)*sin(angle1)) and c+(w/2)*cos(angle2),yc+(h/2)*sin(angle2)).
A complete ellipse can be drawn using 0 and 360 as the angles.
The angles are specified so if the size of the ellipse (w x h) is changed, its shape is preserved. So
the angles relative to the center are dependent from the ellipse size. The actual angle can be obtained
using rangle = atan2((h/2)*sin(angle),(w/2)*cos(angle)).
The angles are given in degrees. To specify the angle in radians, you can use the definition
CD_RAD2DEG to multiply the value in radians before passing the angle to CD. When the interior style
CD_HOLLOW is defined, the function behaves like its equivalent cd Arc, plus two lines connecting to
the center.
LINE ATTRIBUTES
The graph drawing routines may be freely mixed with those described in this section, allowing
the user to control line color, width and styles. The attributes set up by these routines apply modally, i.e,
all subsequent objects (lines, characters and symbols) plotted until the next change in attributes are
affected in the same way. The only exception to this rule is that characters and symbols are not affected
by a change in the line style, but are always drawn using a continuous line.
Line color is set using the routine plcol0. The argument is ignored for devices which can only
plot in one color, although some terminals support line erasure by plotting in color zero.
Line width is set using plwid. This option is not supported by all devices.
Line style is set using the routine plstyl or pllsty. A broken line is specified in terms of a
repeated pattern consisting of marks (pen down) and spaces (pen up). The arguments to this routine are
the number of elements in the line, followed by two pointers to integer arrays specifying the mark and
space lengths in micrometers. Thus a line consisting of long and short dashes of lengths 4 mm and
2 mm, separated by spaces of length 1.5 mm is specified by:
mark[0] = 4000;
mark[1] = 2000;
space[0] = 1500;
space[1] = 1500;
plstyl(2, mark, space);
GRAPHICS & IMAGE PROCESSING Page 11
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
To return to a continuous line, just call plstyl with first argument set to zero. You can use
pllsty to choose between 8 different predefined styles.
Lines and line segments
In mathematics, lines are infinite – that is, they have no ends. It is not often, in the real world,
that we deal with such lines. When people use the word 'line' to talk about the lines of a tennis court, for
example, what they actually mean is 'line segment. A line segment is the set of points on the straight line
between any two points, including the two endpoints themselves.
A section of a line between and including any two points on that line is a line segmentThe region
of a circle bounded by an arc and the chord joining its two end points.
Sutherland line clipping algorithm
Clipping operation
Clipping is a process to extract portion from an object. The extracting portion is called clip
window. The figure given below shows the clipping process.
After Clipping
Clip Window
Before Clipping
Types of clipping
The following are the different types of clipping. They are
i. Point clipping
ii. Line clipping
iii. Clip windows
iv. Text clipping
Line clipping
Line clipping is a process of clipping an object in terms of line segment. The figure given below
shows the concept of line clipping.
GRAPHICS & IMAGE PROCESSING Page 12
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
clip Window
(
( ( (
(
(
(
(
( ( (
(
After Clipping
(
Before clipping
The following steps are used for line clipping.
(a) Let ( be a clip windlow.
(b) For each line segment of an object, check whether
i. it is completely within the window (
ii. it is completely outside the window (
iii. it is crossing the window (both end points are outside the window) (
iv. it is partially inside the window (one end point is inside and other outside). (
(c) If the line segment is completely within the window, store the line segment end points.
(d) If the line segment is completely outside, reject the line segment
(e) If the line segment crosses the window and the end points are outside the window, find the new line
segment with new end points (crossing points) and store it.
(f) If one end point is inside the window and other outside, find the new line segment with one new end
point (crossing point) and store it.
cohen - sutherlend line clipping algorithm
principle
In this clipping algorithm, the line segment is tested by means of the following cohen -
sutherlend code called region code.
1001 1000 1010
0001 0000 0010
0101 0100 0110
Clip window
GRAPHICS & IMAGE PROCESSING Page 13
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
With respect to the clip window, the screen is divided into 9 regions as shown above. Then each region
is numbered by means of a 4 bit binary code. Using the following rules each bit of the code is generated.
The clip window region code is 0000
if the region is left of clip window, the first bit of the code is one. That is 0001.
if the region is right of clip window, the second bit of the code is one. That is 0010
If the region is bottom of clip window, the third bit is one. That is 0100
If the region is top of clip window, the fourth bit is one. that is 1000
Using the above rules, the other region codes are generated. They are
Left top region code is 1001.
Left bottom region code is 0101
Right top region code is 1010
Right bottom region code is 0110
Finding region code for any point (x,y)
The following steps are followed to find the region code.
i. if x < Set first bit to 1 else 0.
ii. if X > set second bit to 1 else 0.
iii. if y < set third bit to 1 else 0.
iv. if y > set fourth bit to 1 else 0.
Algorithm
i. Generate the region code for all the end points of the line segments in an object.
ii. Take any line segment. Find the logical AND operation with the region code for the end points
of the line segment.
iii. If the result is not zero, the line segment is completely outside the window. So reject the line
segment.
iv. If both end points region code of line segments are 0000, then these line segments are completely
within the window. So store the end points.
Else
if both end points region code are not zero, and the result of logical AND operation is zero then
Case (i) : Consider the line segment as shown below.
GRAPHICS & IMAGE PROCESSING Page 14
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
1001
-------------------------------------------
--------------------------------------------------------
0100 )
Here = 0000. Therefore the line segment is crossing the window. So find the crossing points
and
(a) Finding crossing point with respect to .
i. Since the first bit of the area code is 1, the segment cross the line at
=(
The and values are calculated using the formula
Since the fourth bit of the area code is 1, the line segment crosses the line at P1".
=(
The and values are calculated using the formula
Since and are on the window boundary, we got the crossing point with respect to
(b) Finding crossing point with respect to .
i. Since the third bit of the area code is 1, the line segment crosses the line at
=(
GRAPHICS & IMAGE PROCESSING Page 15
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
Since and are on the window boundary, we got the crossing point with respect to
DDA Line Drawing Algorithm
DDA (Digital Differential Analyzer) is a scan conversion line algorithm based on dx/dy. It uses
floating point arithmetic value to find the next nearest pixel in the line.
Algorithm:
Inline int round(const float a)
{
Return int (a+0.5)
}
Void lineDDA(int x0 , int y0, int xend, int yend)
{
Int dx = xend - x0, dy = yend- y0;
Int steps, k;
Float xIncr, yIncr, x= x0, y= y0 ;
If (fabs(dx)>fabs(dy))
Steps = fabs(dx);
Else
Steps=fabs(dy);
xIncr=float(dx)/float(steps);
yIncr=float(dy)/float(steps);
setPixel(round(x), round(y));
for(k=0;k<steps;k++)
{
x= x+xIncr;
y=y+yIncr;
setPixel(round(x), round(y));
}
}
Example: Draw a line segment from (2,3) to (10,8)
Workout the problem.
Disadvantages of DDA algorithm over Bresenham’s :
It is slower than Bresenham’s algorithm
It is not accurate and efficient
It is expensive
Bresenham’s Line Algorithm:
The basic principle of Bresenham’s line algorithm is to select 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
line.
GRAPHICS & IMAGE PROCESSING Page 16
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
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 decision variable or the error.
Algorithm:
1. Read the line end points (x1, y1) and (x2, y2) such that they are not equal.
[ if equal then plot that point and exit]
2. ∆x = │x2 – x1│ and ∆y = │y2 – y1│
3. [Initialize starting point]
x = x1
y = y1
4. e = 2 * ∆y - ∆x
[Initialize value of decision variable or error to compensate for nonzero intercepts]
5. i = 1 [Initialize counter]
6. Plot (x,y)
7. while (e ≥ 0)
{
y=y+1
e = e – 2 * ∆x
}
x=x+1
e = e + 2 * ∆y
8. i = i + 1
9. if (i ≤ ∆x) then go to step 6.
10. Stop
GRAPHICS & IMAGE PROCESSING Page 17
SRI MANAKULA VINAYAGAR ENGINEERING COLLEGE Dept of CSE
PONDICHERRY UNIVERSITY QUESTIONS
GRAPHICS AND IMAGE PROCESSING
1. How to represent the matrix in Two-Dimensional Transformation? Discuss it. (APRIL /
MAY 2012)
2. Write and algorithm in Line Clipping. (APRIL / MAY 2012)
3. Explain DDA line drawing algorithm in detail. (NOVEMBER 2012)
4. Illustrate the procedure for applying Reflect transformations. (NOVEMBER 2012)
5. Illustrate line drawing algorithm (APRIL 2013)
6. Briefly explain Polygon Clipping./ Describe the Sutherland Hodgeman polygon clipping
procedure. (APRIL 2013) (NOV 2014) (APR 2015)
7. Explain DDA Line Drawing Algorithm in detail with and example. Also list down the
disadvantages of DDA algorithm over Bresenham’s algorithm. (NOV 2013)(APR 2015)
8. Describe the general procedure for applying translation, rotation and scaling parameters to
reposition and resize two-dimensional object. (APRIL 2014)
9. Explain Cohen Sutherland Line Clipping algorithm in detail with a suitable example.
(NOVEMBER 2013) (APRIL 2014)
10. Explain in detail about Bresenham’s line algoritm with a suitable example. (NOV 2014)
11. Explain all 2D transformations with suitable examples. (MAY 2015)
12. Write short notes on Shearing and Mirroring (MAY 2015)
13. Discuss in detail about clipping and its types (MAY 2015)
GRAPHICS & IMAGE PROCESSING Page 18
