2160703

Computer Graphics

Unit-2
Graphics Primitives

Prof. Vijay M. Shekhat

9558045778
[Link]@[Link]
 Outline
▪ Points
▪ Line drawing algorithms.
▪ Circle drawing algorithm.
▪ Ellipse drawing algorithm.
▪ Scan-Line polygon filling algorithm.
▪ Inside-Outside test.
▪ Boundary fill algorithm.
▪ Flood fill algorithm.
▪ Character generation.
▪ Line attributes.
▪ Color and grayscale levels
▪ Area fill attributes.
▪ Character attributes.

Unit: 2 Graphics Primitives 2 Darshan Institute of Engineering & Technology

 Point
▪

7
6
5
4
3
2
1
0
0 1 2 3 4 5 6 7

Unit: 2 Graphics Primitives 3 Darshan Institute of Engineering & Technology

 Line
▪ Line drawing is done by calculating intermediate positions along
the line path between two specified endpoint positions.
▪ The output device is then directed to fill in those positions
between the end points with some color.
▪ For some device such as a pen plotter or random scan display, a
straight line can be drawn smoothly from one end point to other.
▪ Digital devices display a straight line segment by plotting discrete
points between the two endpoints.
▪ Discrete coordinate positions along the line path are calculated
from the equation of the line.

Unit: 2 Graphics Primitives 4 Darshan Institute of Engineering & Technology

 Contd.
▪ Screen locations are referenced with integer values.
▪ So plotted positions may only approximate actual line positions
between two specified endpoints. For example line position of
(12.36, 23.87) would be converted to pixel position (12, 24).
▪ This rounding of coordinate values to integers causes lines to be
displayed with a stair step appearance (“the Jaggies”).

Unit: 2 Graphics Primitives 5 Darshan Institute of Engineering & Technology

 Line Drawing Algorithms
▪

Unit: 2 Graphics Primitives 6 Darshan Institute of Engineering & Technology

 Introduction to DDA Algorithm
▪

Unit: 2 Graphics Primitives 7 Darshan Institute of Engineering & Technology

 Unit Step Direction in DDA
Algorithm
▪ Processing from left to right.
✔ Slope is “+ve”, & Magnitude is Less than 1
✔ Slope is “-ve”, & Magnitude is Less than 1
✔ Slope is “+ve”, & Magnitude is greater than 1
✔ Slope is “-ve”, & Magnitude is greater than 1

▪ Processing from right to left.

✔ Slope is “+ve”, & Magnitude is Less than 1
✔ Slope is “-ve”, & Magnitude is Less than 1
✔ Slope is “+ve”, & Magnitude is greater than 1
✔ Slope is “-ve”, & Magnitude is greater than 1

Unit: 2 Graphics Primitives 8 Darshan Institute of Engineering & Technology

 Derivation of DDA Algorithm
▪

Unit: 2 Graphics Primitives 9 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 10 Darshan Institute of Engineering & Technology

Procedure for DDA line algorithm.
Void lineDDA (int xa, int ya, int xb, int yb)
{
int dx = xb – xa, dy = yb – ya, steps, k;
float xincrement, yincrement, x = xa, y = ya;
if (abs(dx)>abs(dy))
{
Steps = abs (dx);
}
else
{
Steps = abs (dy);
}
xincrement = dx/(float) steps;
yincrement = dy/(float) steps;

setpixel (ROUND (x), ROUND (y));

for(k=0;k<steps;k++)
{
x += xincrement;
y += yincrement;
setpixel (ROUND (x), ROUND (y));
}
}
 Example DDA Algorithm
▪
4
3
2
1
0
0 1 2 3 4 5 6 7 8

Unit: 2 Graphics Primitives 12 Darshan Institute of Engineering & Technology

 Introduction to Bresenham’s Line
Algorithm
▪

Unit: 2 Graphics Primitives 13 Darshan Institute of Engineering & Technology

 Line Path & Candidate pixel
▪ Example |ΔX| > |ΔY|, and ΔY is “+ve”. 4
3
Initial point (Xk, Yk)
2
Line path 1
0
Candidate pixels {(Xk+1, Yk), (Xk+1, Yk+1)}
0 1 2 3 4
▪ Now we need to decide which candidate pixel is more closer to
actual line.
▪ For that we use decision parameter (Pk) equation.
▪ Decision parameter can be derived by calculating distance of
actual line from two candidate pixel.

Unit: 2 Graphics Primitives 14 Darshan Institute of Engineering & Technology

 Derivation Bresenham’s Line
Algorithm
▪ 4
3
2
1
0
0 1 2 3 4

Unit: 2 Graphics Primitives 15 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 16 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 17 Darshan Institute of Engineering & Technology

 Initial Decision parameter
▪

Unit: 2 Graphics Primitives 18 Darshan Institute of Engineering & Technology

 Bresenham’s Line Algorithm
▪

Unit: 2 Graphics Primitives 19 Darshan Institute of Engineering & Technology

 Discryption of Bresenham’s Line
Algorithm
▪

Unit: 2 Graphics Primitives 20 Darshan Institute of Engineering & Technology

 Example Bresenham’s Line
Algorithm
▪

4
3
2
1
0
0 1 2 3 4 5 6 7 8

Unit: 2 Graphics Primitives 21 Darshan Institute of Engineering & Technology

 Parallel Execution of Line
Algorithms
▪ The line-generating algorithms we have discussed so far
determine pixel positions sequentially.
▪ With multiple processors we can calculate pixel position along a
line path simultaneously.
▪ One way to use multiple processors is partitioning existing
sequential algorithm into small parts and compute separately.
▪ Alternatively we can setup the processing so that pixel positions
can be calculated efficiently in parallel.
▪ Balance the load among the available processors is also important
in parallel processing.

Unit: 2 Graphics Primitives 22 Darshan Institute of Engineering & Technology

 Parallel Bresenham Line
Algorithms
▪

Unit: 2 Graphics Primitives 23 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 24 Darshan Institute of Engineering & Technology

 IDP for Parallel Bresenham Line
Algorithms
▪

Unit: 2 Graphics Primitives 25 Darshan Institute of Engineering & Technology

 Other Ways for Parallel Execution of Line
Algorithms
▪

Unit: 2 Graphics Primitives 26 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 27 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 28 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 29 Darshan Institute of Engineering & Technology

 Circle
▪

r
Radius

Unit: 2 Graphics Primitives 30 Darshan Institute of Engineering & Technology

 Properties of Circle- Cartesion
Coordinate
▪

Unit: 2 Graphics Primitives 31 Darshan Institute of Engineering & Technology

 Contd.
▪ But this is not best method as it requires more number of
calculations which take more time to execute.
▪ And also spacing between the plotted pixel positions is not
uniform.

▪ We can adjust spacing by stepping through y values and

calculating x values whenever the absolute value of the slop of the
circle is greater than 1.
▪ But it will increases computation time.

Unit: 2 Graphics Primitives 32 Darshan Institute of Engineering & Technology

 Properties of Circle- Polar
Coordinate
▪

Unit: 2 Graphics Primitives 33 Darshan Institute of Engineering & Technology

 Properties of Circle- Symmetry
▪ Computation can be reduced by considering symmetry city
property of circles.
▪ The shape of circle is similar in each octant.

(-3, 4) (3, 4)
(-Y, X) (Y, X)
(-4, 3) (4, 3)
(-X, Y) (X, Y)

(-4, -3) (4, -3)

(-X, -Y) (X, -Y)

(-Y, -X) (Y, -X)

(-3, -4) (3, -4)

Unit: 2 Graphics Primitives 34 Darshan Institute of Engineering & Technology

 Circle Algorithm
▪

Unit: 2 Graphics Primitives 35 Darshan Institute of Engineering & Technology

 Contd.
▪ A method for direct distance comparison to test the midpoint
between two pixels to determine if this midpoint is inside or
outside the circle boundary.
▪ This method is easily applied to other conics also.
▪ Midpoint approach generates same pixel position as generated by
bresenham’s circle algorithm.
▪ The error involve in locating pixel positions along any conic section
using midpoint test is limited to one-half the pixel separation.

Unit: 2 Graphics Primitives 36 Darshan Institute of Engineering & Technology

 Introduction to Midpoint Circle
Algorithm
▪

Unit: 2 Graphics Primitives 37 Darshan Institute of Engineering & Technology

 Decision Parameter Midpoint Circle
Algorithm
▪

Unit: 2 Graphics Primitives 38 Darshan Institute of Engineering & Technology

 Midpoint between Candidate
pixel
▪

yk Midpoint
Candidate
y k+1 Pixel

x k x k+1 x k+2

Unit: 2 Graphics Primitives 39 Darshan Institute of Engineering & Technology

 Derivation Midpoint Circle
Algorithm
▪

Unit: 2 Graphics Primitives 40 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 41 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 42 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 43 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 44 Darshan Institute of Engineering & Technology

 IDP Midpoint Circle Algorithm
▪

Unit: 2 Graphics Primitives 45 Darshan Institute of Engineering & Technology

 Example Midpoint Circle
Algorithm
▪

0 -9 (1, 10)
1 -6 (2, 10)
2 -1 (3, 10)
3 6 (4, 9)
4 -3 (5, 9)
5 8 (6, 8)
6 5 (7, 7)

Unit: 2 Graphics Primitives 47 Darshan Institute of Engineering & Technology

 Contd.
▪
0 -9 (1, 10)
1 -6 (2, 10)
2 -1 (3, 10)
3 6 (4, 9)
4 -3 (5, 9)
5 8 (6, 8)
6 5 (7, 7)

Unit: 2 Graphics Primitives 48 Darshan Institute of Engineering & Technology

 Contd.
▪
0 -9 (1, 10)
1 -6 (2, 10)
2 -1 (3, 10)
3 6 (4, 9)
4 -3 (5, 9)
5 8 (6, 8)
6 5 (7, 7)

Unit: 2 Graphics Primitives 49 Darshan Institute of Engineering & Technology

 Contd.
▪

Center (0, 0) Center (1, 1)

(1, 10) (2, 11)
(2, 10) (3, 11)
(3, 10) (4, 11)
(4, 9) (5, 10)
(5, 9) (6, 10)
(6, 8) (7, 9)
(7, 7) (8, 8)

Unit: 2 Graphics Primitives 50 Darshan Institute of Engineering & Technology

 Contd.
▪ Plot the pixel.
12
▪ First plot initial point. 11
(1, 11) 10
9
Center (1, 1)
8
(2, 11) 7
6
(3, 11)
5
(4, 11) 4
(5, 10) 3
(6, 10) 2
Center
1
(7, 9) (1, 1)
0
(8, 8)
0 1 2 3 4 5 6 7 8 9 10 11
Unit: 2 Graphics Primitives 51 Darshan Institute of Engineering & Technology
 Ellipse
▪ AN ellipse is defined as the set of points such that the sum of the
distances from two fixed positions (foci) is same for all points.

Unit: 2 Graphics Primitives 52 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 53 Darshan Institute of Engineering & Technology

 Properties of Ellipse-Specifying
Equations
▪

Unit: 2 Graphics Primitives 54 Darshan Institute of Engineering & Technology

 Contd.
▪

X-axis

Y-axis

Unit: 2 Graphics Primitives 55 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 56 Darshan Institute of Engineering & Technology

 Properties of Ellipse-Symmetry
▪ Symmetry property further reduced computations.
▪ An ellipse in standard position is symmetric between quadrant.

Unit: 2 Graphics Primitives 57 Darshan Institute of Engineering & Technology

 Introduction to Midpoint Ellipse
Algorithm
▪

Unit: 2 Graphics Primitives 58 Darshan Institute of Engineering & Technology

 Regions in Midpoint Ellipse
Algorithm
▪ In this method we divide first quadrant into two parts according to
the slope of an ellipse
▪ Boundary divides region at
Region 1
• slope = -1.
▪ We take unit step in X direction
• If magnitude of ellipse slope < 1 (Region 1).
Region 2
▪ We take unit step in Y direction
• If magnitude of ellipse slope > 1 (Region 2).

Unit: 2 Graphics Primitives 59 Darshan Institute of Engineering & Technology

 Ways of Processing Midpoint Ellipse
Algorithm
▪

Unit: 2 Graphics Primitives 60 Darshan Institute of Engineering & Technology

 Decision Parameter Midpoint Ellipse
Algorithm
▪

Unit: 2 Graphics Primitives 61 Darshan Institute of Engineering & Technology

 Processing Steps of Midpoint Ellipse
Algorithm
▪

Region 1
▪ At each step we need to test the value
of the slope of the curve for deciding
the end point of the region-1.
Region 2

Unit: 2 Graphics Primitives 62 Darshan Institute of Engineering & Technology

 Decide Boundary between Region
1 and 2
▪

Unit: 2 Graphics Primitives 63 Darshan Institute of Engineering & Technology

 Midpoint between Candidate pixel in
Region 1
▪

r y2x 2+r x2y 2-r x2r y2=0

yk Midpoint
y k-1 Candidate
Pixel
x k x k+1 x k+2

Unit: 2 Graphics Primitives 64 Darshan Institute of Engineering & Technology

 Derivation for Region 1
▪

Unit: 2 Graphics Primitives 65 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 66 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 67 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 68 Darshan Institute of Engineering & Technology

 IDP for Region 1
▪

Unit: 2 Graphics Primitives 69 Darshan Institute of Engineering & Technology

 Midpoint between Candidate pixel in
Region 2
▪

r y2x 2+r x2y 2-r x2r y2=0

yk Midpoint
y k-1
Candidate
Pixel
xk x k+1 x k+2

Unit: 2 Graphics Primitives 70 Darshan Institute of Engineering & Technology

 Derivation for Region 2
▪

Unit: 2 Graphics Primitives 71 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 72 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 73 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 74 Darshan Institute of Engineering & Technology

 IDP for Region 2
▪

Unit: 2 Graphics Primitives 75 Darshan Institute of Engineering & Technology

 Example Midpoint Ellipse
Algorithm
▪

Unit: 2 Graphics Primitives 78 Darshan Institute of Engineering & Technology

 Contd.
K p1k (xk+1, yk+1)
0 -332 (1, 6)
1 -224 (2, 6)
2 -44 (3, 6)
3 208 (4, 5)
4 -108 (5, 5)
5 288 (6, 4)
6 244 (7, 3)

Unit: 2 Graphics Primitives 79 Darshan Institute of Engineering & Technology

 Contd.
K p1k (xk+1, yk+1)
0 -332 (1, 6)
1 -224 (2, 6)
2 -44 (3, 6)
3 208 (4, 5)
4 -108 (5, 5)
5 288 (6, 4)
6 244 (7, 3)

Unit: 2 Graphics Primitives 80 Darshan Institute of Engineering & Technology

 Contd.
K p1k (xk+1, yk+1)
0 -332 (1, 6)
1 -224 (2, 6)
2 -44 (3, 6)
3 208 (4, 5)
4 -108 (5, 5)
5 288 (6, 4)
6 244 (7, 3)

Unit: 2 Graphics Primitives 81 Darshan Institute of Engineering & Technology

 Contd.
K p1k (xk+1, yk+1)
0 -332 (1, 6)
1 -224 (2, 6)
2 -44 (3, 6)
3 208 (4, 5)
4 -108 (5, 5)
5 288 (6, 4)
6 244 (7, 3)

Unit: 2 Graphics Primitives 82 Darshan Institute of Engineering & Technology

 Contd.
K p1k (xk+1, yk+1)
0 -332 (1, 6)
1 -224 (2, 6)
2 -44 (3, 6)
3 208 (4, 5)
4 -108 (5, 5)
5 288 (6, 4)
6 244 (7, 3)

Unit: 2 Graphics Primitives 83 Darshan Institute of Engineering & Technology

 Contd.
K p1k (xk+1, yk+1)
0 -332 (1, 6)
1 -224 (2, 6)
2 -44 (3, 6)
3 208 (4, 5)
4 -108 (5, 5)
5 288 (6, 4)
6 244 (7, 3)

Unit: 2 Graphics Primitives 84 Darshan Institute of Engineering & Technology

 Contd.
K p2k (xk+1, yk+1)
0 -23 (8, 2)
1 361 (8, 1)
2 297 (8, 0)

Unit: 2 Graphics Primitives 85 Darshan Institute of Engineering & Technology

 Contd.
K p2k (xk+1, yk+1)
0 -23 (8, 2)
1 361 (8, 1)
2 297 (8, 0)

Unit: 2 Graphics Primitives 86 Darshan Institute of Engineering & Technology

 Contd.
K p2k (xk+1, yk+1)
0 -23 (8, 2)
1 361 (8, 1)
2 297 (8, 0)

Unit: 2 Graphics Primitives 87 Darshan Institute of Engineering & Technology

 Contd.
▪ Plot the pixel.
12
▪ Plot initial point(0, 6) 11
Center (0, 0) Center (0, 0) 10
9
(1, 6) (8, 2) 8
(2, 6) (8, 1) 7
(3, 6) 6
(8, 0)
5
(4, 5) 4
(5, 5) 3
(6, 4) 2
(7, 3) 1
Center 0
(0, 0) 0 1 2 3 4 5 6 7 8 9 10 11
Unit: 2 Graphics Primitives 88 Darshan Institute of Engineering & Technology
 Filled-Area Primitives
▪ In practical we often use polygon which are filled with some
colour or pattern inside it.
▪ There are two basic approaches to area filling on raster systems.
• One way to fill an area is to determine the overlap intervals for scan line
that cross the area.
• Another method is to start from a given interior position and paint outward
from this point until we encounter boundary.

Unit: 2 Graphics Primitives 89 Darshan Institute of Engineering & Technology

 Scan-Line Polygon Fill
Algorithm
▪ For each scan-line crossing a polygon, the algorithm locates the
intersection points are of scan line with the polygon edges.
▪ This intersection points are stored from left to right.
▪ Frame buffer positions between each pair of intersection point are
set to specified fill color.

Scan line

Unit: 2 Graphics Primitives 90 Darshan Institute of Engineering & Technology

 Contd.
▪ Scan line intersects at vertex are required special handling.
▪ For vertex we must look at the other endpoints of the two line
segments which meet at this vertex.
• If these points lie on the same (up or down) side of the scan line, then that
point is counts as two intersection points.
• If they lie on opposite sides of the scan line, then the point is counted as
single intersection.

Scan line
Scan line

Scan line

Unit: 2 Graphics Primitives 91 Darshan Institute of Engineering & Technology

 Edge Intersection Calculation with
Scan-Line
▪

Unit: 2 Graphics Primitives 92 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 93 Darshan Institute of Engineering & Technology

 Edge Intersection Calculation with Scan-Line for parallel
execution
▪

Unit: 2 Graphics Primitives 94 Darshan Institute of Engineering & Technology

 Simplified Method for Edge Intersection Calculation with
Scan-Line
▪

Counter=2
Counter=3
Counter=4
Counter=5
Counter=6
Counter=1
Counter=0

Unit: 2 Graphics Primitives 95 Darshan Institute of Engineering & Technology

 Use of Sorted Edge table in Scan-Line Polygon Fill
Algorithm
▪

Unit: 2 Graphics Primitives 96 Darshan Institute of Engineering & Technology

 Contd.
Scan Line
Number

B .
.
.

.
C .
.
C E

D .
.
A .
1
0

Unit: 2 Graphics Primitives 97 Darshan Institute of Engineering & Technology

 Inside-Outside Tests
▪ In area filling and other graphics operation often required to find
particular point is inside or outside the polygon.
▪ For finding which region is inside or which region is outside most
graphics package use either
1. Odd even rule OR
2. Nonzero winding number rule

Unit: 2 Graphics Primitives 98 Darshan Institute of Engineering & Technology

 Odd Even/ Odd Parity/ Even
Odd
▪
Rule

Boundary of Screen

1 2

Unit: 2 Graphics Primitives 99 Darshan Institute of Engineering & Technology

 Nonzero Winding Number Rule
▪

Boundary of Screen

Winding number=0

Unit: 2 Graphics Primitives 100 Darshan Institute of Engineering & Technology

 Contd.
▪ The line we choose must not pass through vertices.
▪ Then we move along that line we find number of intersecting
edges.
1. If edge cross our line from right to left We add 1 to winding number
2. Otherwise subtract 1 from winding number
▪ IF the final value of winding number is nonzero then the point is
interior otherwise point is exterior. Boundary of Screen

-1 -1
Winding number=+1-1=0
number=0
number=-1

+1

Unit: 2 Graphics Primitives 101 Darshan Institute of Engineering & Technology

 Comparison between Odd Even Rule and Nonzero
Winding Rule
▪ For standard polygons and simple object both rule gives same
result but for more complicated shape both rule gives different
result.

Odd Even Rule Nonzero Winding Rule

Unit: 2 Graphics Primitives 102 Darshan Institute of Engineering & Technology

 Scan-Line Fill of Curved
Boundary Areas
▪ Scan-line fill of region with curved boundary is more time
consuming as intersection calculation now involves nonlinear
boundaries.
▪ For simple curve such as circle or ellipse scan line fill process is
straight forward process.
▪ We calculate the two scan line intersection on opposite side of the
curve.
▪ This is same as generating pixel position along the curve boundary
using standard equation of curve.
▪ Then we fill the color between two boundary intersections.
▪ Symmetry property is used to reduce the calculation.

Unit: 2 Graphics Primitives 103 Darshan Institute of Engineering & Technology

 Introduction to Boundary / Edge Fill
Algorithm
▪ In this method, edges of the polygons are drawn.
▪ Then starting with some seed (any point inside the polygon) we
examine the neighbouring pixels to check whether the boundary
pixel is reached.
▪ If boundary pixels are not reached, pixels are highlighted and the
process is continued until boundary pixels are reached.
▪ Selection of neighbour pixel is either 4-cormected or 8-connected.

4-Cormected Region 8-Cormected Region

Unit: 2 Graphics Primitives 104 Darshan Institute of Engineering & Technology
 Contd.
▪ In some cases, an 8-connected algorithm is more accurate than
the 4-connected algorithm.
▪ Some times 4-connected algorithm produces the partial fill.

Seed

Unit: 2 Graphics Primitives 105 Darshan Institute of Engineering & Technology

 Boundary / Edge Fill Algorithm
Procedure:
boundary-fill4(x, y, f-colour, b-colour)
{
if(getpixel (x,y) ! = b-colour && gepixel (x, y) ! = f-colour)
{
putpixel (x, y, f-colour)
boundary-fill4(x + 1, y, f-colour, b-colour);
boundary-fill4(x, y + 1, f-colour, b-colour);
boundary-fill4(x - 1, y, f-colour, b-colour);
boundary-fill4(x, y - l, f-colour, b-colour);
}
}

Unit: 2 Graphics Primitives 106 Darshan Institute of Engineering & Technology

 Problem of Staking and Efficient
Method
▪ Same procedure can be modified according to 8 connected region
algorithm by including four additional statements to test diagonal
positions.
▪ This procedure requires considerable stacking of neighbouring
points more, efficient methods are generally employed.
▪ Efficient method fill horizontal pixel spans across scan lines,
instead of proceeding to 4 connected or 8 connected neighbouring
points.
▪ Then we need only stack a beginning position for each horizontal
pixel span, instead of stacking all unprocessed neighbouring
positions around the current position.
▪ Starting from the initial interior point with this method, we first fill
in the contiguous span of pixels on this starting scan line.

Unit: 2 Graphics Primitives 107 Darshan Institute of Engineering & Technology

 Contd.
▪ Then we locate and stack starting positions for spans on the
adjacent scan lines.
▪ Spans are defined as the contiguous horizontal string of positions
bounded by pixels displayed in the area border colour.
▪ At each subsequent step, we unstack the next start position and
repeat the process.
▪ For e.g.

Unit: 2 Graphics Primitives 108 Darshan Institute of Engineering & Technology

 Contd.

3
2
(a) (b)
1 2 1 3
1 1

5 6 5
6
(c) 4 5 (d) 4 5
1 4 1 4
1 1

Unit: 2 Graphics Primitives 109 Darshan Institute of Engineering & Technology

 Introduction to Flood-Fill
Algorithm
▪ Sometimes it is required to fill in an area that is not defined within
a single colour boundary.
▪ In such cases we can fill areas by replacing a specified interior
colour instead of searching for a boundary colour.
▪ This approach is called a flood-fill algorithm. Like boundary fill
algorithm, here we start with some seed and examine the
neighbouring pixels.
▪ However, here pixels are checked for a specified interior colour
instead of boundary colour and they are replaced by new colour.
▪ Using either a 4-connected or 8-connected approach, we can step
through pixel positions until all interior point have been filled.

Unit: 2 Graphics Primitives 110 Darshan Institute of Engineering & Technology

 Flood-Fill Algorithm
Procedure :
flood-fill4(x, y, new-colour, old-colour)
{
if(getpixel (x,y) = = old-colour)
{
putpixel (x, y, new-colour)
flood-fill4 (x + 1, y, new-colour, old -colour);
flood-fill4 (x, y + 1, new -colour, old -colour);
flood-fill4 (x - 1, y, new -colour, old -colour);
flood-fill4 (x, y - l, new -colour, old-colour);
}
}

Unit: 2 Graphics Primitives 111 Darshan Institute of Engineering & Technology

 Character Generation
▪ We can display letters and numbers in variety of size and style.
▪ The overall design style for the set of character is called typeface.
▪ Today large numbers of typefaces are available for computer
application for example Helvetica, Arial etc.
▪ Originally, the term font referred to a set of cast metal character
forms in a particular size and format.
▪ Example: 10-point Courier Italic or 12- point Palatino Bold.

Unit: 2 Graphics Primitives 112 Darshan Institute of Engineering & Technology

 Contd.
▪ Now, the terms font and typeface are often used interchangeably,
since printing is no longer done with cast metal forms.
▪ Methods of character generation are:
Bitmap Font/ Bitmapped Font
Outline Font
Stroke Method
Starbust Method

Unit: 2 Graphics Primitives 113 Darshan Institute of Engineering & Technology

 Bitmap Font/ Bitmapped Font
▪ A simple method for representing the 0 0 1 1 1 1 0 0
character shapes in a particular typeface is to 0 1 1 1 1 1 1 0
1 1 0 0 0 0 1 1
use rectangular grid patterns. 1 1 0 0 0 0 1 1
1 1 1 1 1 1 1 1
▪ In frame buffer, the 1 bits designate which 1 1 1 1 1 1 1 1
pixel positions are to be displayed on the 1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
monitor.
▪ Bitmap fonts are the simplest to define and display.
▪ Bitmap fonts require more space.
▪ It is possible to generate different size and other variation from
one set but this usually does not produce good result.

Unit: 2 Graphics Primitives 114 Darshan Institute of Engineering & Technology

 Outline Font
▪ In this method character is generated using curve
section and straight line as combine assembly.
▪ To display the character we need to fill interior

B
region of the character.
▪ This method requires less storage since each
variation does not required a distinct font cache.
▪ We can produce boldface, italic, or different sizes
by manipulating the curve definitions for the
character outlines.
▪ But this will take more time to process the outline
fonts, because they must be scan converted into
the frame buffer.

Unit: 2 Graphics Primitives 115 Darshan Institute of Engineering & Technology

 Stroke Method
• It uses small line segments to generate
a character.
• The small series of line segments are
drawn like a stroke of a pen to form a
character.
• We can generate our own stroke method by calling line
drawing algorithm.
• Here it is necessary to decide which line segments are
needs for each character and then draw that line to
display character.
• It support scaling by changing length of line segment.

Unit: 2 Graphics Primitives 116 Darshan Institute of Engineering & Technology

 Starbust Method
▪ In this method a fix pattern of lines (24 line) segments are used to
generate characters. 03 04
13 14
02 23 05
17 18
01 06
21
12 22 07
20
24 19
11 08
16 15
10 09

▪ We highlight those lines which are necessary to draw a particular

character.
▪ Pattern for particular character is stored in the form of 24 bit code.
▪ In which each bit represents corresponding line having that number.
▪ We put bit value 1 for highlighted line and 0 for other line.

Unit: 2 Graphics Primitives 117 Darshan Institute of Engineering & Technology

 Contd.
▪ Example letter V
03 04
13 14
02 23 05
17 18
01 06
21
12 22 07
20
24 19
11 08
16 15
10 09

▪ Code for letter V = 1 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0

▪ This technique is not used now a days because:
• It requires more memory to store 24 bit code for single character.
• It requires conversion from code to character.
• It doesn’t provide curve shapes.

Unit: 2 Graphics Primitives 118 Darshan Institute of Engineering & Technology

 Line Attributes
▪ Basic attributes of a straight line segment are:
• Type
• Dimension
• color
• pen or brush option.

Unit: 2 Graphics Primitives 119 Darshan Institute of Engineering & Technology

 Line Type
▪ Possible selection for the line-type attribute includes solid lines, dashed
lines, and dotted lines etc.
1 Solid

2 Dashed

3 Dotted
4 Dotdash
▪ We modify a line –drawing algorithm to generate such lines by setting
the length and spacing of displayed solid sections along the line path.
▪ To set line type attributes in a PHIGS application program, a user
invokes the function: setLinetype(It)
▪ Where parameter lt is assigned a positive integer value of 1, 2, 3, 4…
etc. to generate lines that are, respectively solid, dashed, dotted, or
dotdash etc.

Unit: 2 Graphics Primitives 120 Darshan Institute of Engineering & Technology

 Line Width
▪ Implementation of line-width options depends on the capabilities
of the output device.
▪ A heavy line on a video monitor could be displayed as adjacent
parallel lines, while a pen plotter might require pen changes.
▪ To set line width attributes in a PHIGS application program, a user
invokes the function: setLinewidthScalFactor (lw)
▪ Line-width parameter lw is assigned a positive number to indicate
the relative width of the line to be displayed.
▪ Values greater than 1 produce lines thicker than the standard line
width and values less than the 1 produce line thinner than the
standard line width.

Unit: 2 Graphics Primitives 121 Darshan Institute of Engineering & Technology

 Contd.
▪ In raster graphics we generate thick line by plotting
• above and below pixel of line path when slope |m|<1. &
• left and right pixel of line path when slope |m|>1.

Unit: 2 Graphics Primitives 122 Darshan Institute of Engineering & Technology

 Line Width at Endpoints and
Join
▪ As we change width of the line we can also change line end and
join of two lines which are shown below

Butt caps Miter join

Projecting square caps Round join

Round caps Bevel join

Unit: 2 Graphics Primitives 123 Darshan Institute of Engineering & Technology

 Line color
▪ The name itself suggests that it is defining color of line displayed
on the screen.

▪ By default system produce line with current color but we can

change this color by following function in PHIGS package as
follows: setPolylinecolorIndex (lc)
▪ In this lc is constant specifying particular color to be set.

Unit: 2 Graphics Primitives 124 Darshan Institute of Engineering & Technology

 Pen and Brush Options
• In some graphics packages line is
displayed with pen and brush
selections.
• Options in this category include
shape, size, and pattern.
• These shapes can be stored in a
pixel mask that identifies the
array of pixel positions that are
to be set along the line path.
• Also, lines can be displayed with
selected patterns by
superimposing the pattern values
onto the pen or brush mask.

Unit: 2 Graphics Primitives 125 Darshan Institute of Engineering & Technology

 Color and Grayscale Levels
▪ Various colors and intensity-level options can be made available to
a user, depending on the capabilities and design objectives of a
particular system.
▪ General purpose raster-scan systems, for example, usually provide
a wide range of colors, while random-scan monitors typically offer
only a few color choices, if any.
▪ In a color raster system, the number of color choices available
depends on the amount of storage provided per pixel in the frame
buffer

Unit: 2 Graphics Primitives 126 Darshan Institute of Engineering & Technology

 Contd.
▪ Also, color-information can be stored in the frame buffer in two
ways:
• We can store color codes directly in the frame buffer OR
• We can put the color codes in a separate table and use pixel values as an
index into this table
▪ With direct storage scheme we required large memory for frame
buffer when we display more color.
▪ While in case of table it is reduced and we call it color table or
color lookup table.

Unit: 2 Graphics Primitives 127 Darshan Institute of Engineering & Technology

 Color Lookup Table
▪ Color values of 24 bit is stored in lookup table and in frame buffer
we store only 8 bit index of required color.
▪ So that size of frame buffer is reduced and we can display more
color. Color
Lookup
Frame Buffer Table
0 To Red Gun
To Green Gun
To Blue Gun

2081 00000000 00001000 00100001

196 196

255

Unit: 2 Graphics Primitives 128 Darshan Institute of Engineering & Technology

 Greyscale
▪ With monitors that have no color capability, color function can be
used in an application program to set the shades of grey
(greyscale) for display primitives.
▪ Numeric values between 0-to-1 can be used to specify greyscale
levels.
▪ This numeric values is converted in binary code for store in raster
system. Example: frame buffer with 2 bits per pixel.
Intensity Code Stored Intensity Values In The Displayed Greyscale
Frame Buffer Binary Code
0.0 0 00 Black
0.33 1 01 Dark grey
0.67 2 10 Light grey
1.0 3 11 White

Unit: 2 Graphics Primitives 129 Darshan Institute of Engineering & Technology

 Area-Fill Attributes
▪ For filling any area we have choice between solid colors or pattern
to fill all these are include in area fill attributes. Which are:
• Fill Styles
• Pattern Fill
• Soft Fill

Unit: 2 Graphics Primitives 130 Darshan Institute of Engineering & Technology

 Fill Styles
▪ Area are generally displayed with three basic style.
1. hollow with color border
2. filled with solid color
3. filled with some design
▪ In PHIGS package fill style is selected by following function:
setInteriorStyle (fs)
▪ Value of fs include hollow ,solid, pattern etc.

Unit: 2 Graphics Primitives 131 Darshan Institute of Engineering & Technology

 Contd.
▪ Another values for fill style is hatch, which is patterns of line like
parallel line or crossed line.

Hollow Solid Pattern Diagonal Diagonal

Hatch Fill Cross-Hatch Fill

▪ For setting interior color in PHIGS package we use:

setInteriorColorIndex (fc)
▪ Where fc specify the fill color.

Unit: 2 Graphics Primitives 132 Darshan Institute of Engineering & Technology

 Pattern Fill
• We select the pattern with Pattern Table
setInteriorStyleIndex (pi) Index(pi) Pattern(cp)
• Where pattern index parameter pi 1
specifies position in pattern table
2
entry.
• For example:
– SetInteriorStyle( pattern ) ;
– setInteriorStyleIndex ( 2 ) ;
– fillArea (n, points);

Unit: 2 Graphics Primitives 133 Darshan Institute of Engineering & Technology

 Contd.
▪ We can also maintain separate table for hatch pattern.
▪ We can also generate our own table with required pattern.
▪ Other function used for setting other style as follows:
setpatternsize (dx, dy)
▪ setPaternReferencePoint (position)
▪ We can create our own pattern by setting and resetting group of
pixel and then map it into the color matrix.

Unit: 2 Graphics Primitives 134 Darshan Institute of Engineering & Technology

 Soft Fill
▪

Unit: 2 Graphics Primitives 135 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 136 Darshan Institute of Engineering & Technology

 Character Attributes
▪ The appearance of displayed characters is controlled by attributes
such as:
• Font
• Size
• Color
• Orientation.
▪ Attributes can be set for entire string or may be individually.

Unit: 2 Graphics Primitives 137 Darshan Institute of Engineering & Technology

 Text Attributes
▪ In text we are having so many style and design like italic fonts,
bold fonts etc.
▪ For setting the font style in PHIGS package we have function:
setTextFont (tf)
▪ Where tf is used to specify text font.
▪ For setting color of character in PHIGS we have function:
setTextColorIndex (tc)
▪ Where text color parameter tc specifies an allowable color code.
▪ For setting the size of the text we use function:
setCharacterheight (ch)
▪ Where ch is used to specify character height.

Unit: 2 Graphics Primitives 138 Darshan Institute of Engineering & Technology

 Contd.
▪ For scaling the character we use function:
setCharacterExpansionFacter (cw)
▪ Where character width parameter cw is set to a positive real
number that scale the character body width.
▪ Spacing between character is controlled by function:
▪ setCharacterSpacing (cs)
▪ Where character spacing parameter cs can be assigned any real
value.

Unit: 2 Graphics Primitives 139 Darshan Institute of Engineering & Technology

 Contd.
▪ The orientation for a displayed character string is set according to
the direction of the character up vector:
setCharacterUpVector (upvect)
▪ Parameter upvect in this function is assigned two values that
specify the x and y vector components.
▪ Text is then displayed so that the orientation of characters from
baseline to cap line is in the direction of the up vector.
▪ For setting the path of the character we use function:
setTextPath (tp)
▪ Where the text path parameter tp can be assigned the value: right,
left, up, or down.

Unit: 2 Graphics Primitives 140 Darshan Institute of Engineering & Technology

 Contd.
▪ For setting the alignment we use function:
setTextAlignment (h, v)
▪ Where parameter h and v control horizontal and vertical
alignment respectively.
▪ For specifying precision for text display is given with function:
setTextPrecision (tpr)
▪ Where text precision parameter tpr is assigned one of the values:
string, char, or stroke.
▪ The highest-quality text is produced when the parameter is set to
the value stroke.

Unit: 2 Graphics Primitives 141 Darshan Institute of Engineering & Technology

 Marker Attributes
▪ A marker symbol display single character in different color and in
different sizes.
▪ For marker attributes implementation by procedure that load the
chosen character into the raster at defined position with the
specified color and size.
▪ We select marker type using function: setMarkerType (mt)
▪ Where marker type parameter mt is set to an integer code.

Unit: 2 Graphics Primitives 142 Darshan Institute of Engineering & Technology

 Contd.
▪ Typical codes for marker type are the integers 1 through 5,
specifying, respectively:
1. a dot (.)
2. a vertical cross (+)
3. an asterisk (*)
4. a circle (o)
5. a diagonal cross (x).
▪ Displayed marker types are centred on the marker coordinates.

Unit: 2 Graphics Primitives 143 Darshan Institute of Engineering & Technology

 Contd.
▪ We set the marker size with function:
SetMarkerSizeScaleFactor (ms)
▪ Where parameter marker size ms assigned a positive number
according to need for scaling.
▪ For setting marker color we use function:
setPolymarkerColorIndex (mc)
▪ Where parameter mc specify the color of the marker symbol.

Unit: 2 Graphics Primitives 144 Darshan Institute of Engineering & Technology

 Aliasing
▪ Primitives generated in raster graphics by various algorithms have
stair step shape or jagged appearance.
▪ Jagged appearance is due to integer calculation by rounding actual
values.
▪ This distortion of actual information due to low frequency
sampling is called aliasing.

Unit: 2 Graphics Primitives 145 Darshan Institute of Engineering & Technology

 Antialiasing
▪

Unit: 2 Graphics Primitives 146 Darshan Institute of Engineering & Technology

 Contd.
▪

Unit: 2 Graphics Primitives 147 Darshan Institute of Engineering & Technology

 Antialiasing Methods
1. Supersampling Straight Line Segments
2. Pixel-Weighting Masks
3. Area Sampling Straight Line Segments
4. Filtering Techniques
5. Pixel Phasing
6. Compensating For Line Intensity Differences
7. Antialiasing Area Boundaries

Unit: 2 Graphics Primitives 148 Darshan Institute of Engineering & Technology

 Supersampling Straight Line
Segments
▪ For the greyscale display of a straight-line segment, we can divide
each pixel into a number of sub pixels and determine the number
of sub pixel along the line path.
▪ Then we set intensity level of each pixel proportional to number of
sub pixel along the line path.
▪ E.g. in figure area of each pixel is
divided into nine sub pixel and then we
determine how many number of sub
pixel are along the line ( it can be 3 or 2
or 1 as we divide into 9 sub pixel).
▪ Based on number 3 or 2 or 1 we assign
intensity value to that pixel.

Unit: 2 Graphics Primitives 149 Darshan Institute of Engineering & Technology

 Contd.
▪ We can achieve four intensity levels by dividing pixel into 16 sub
pixels and five intensity levels by dividing into 25 sub pixels etc.
▪ Lower intensity gives blurred effect and hence performs
antialiasing.
▪ Other way is we considered pixel areas of finite size, but we
treated the line as a mathematical entity with zero width.
▪ Actually, displayed lines have a width approximately equal to that
of a pixel.
▪ If we take finite width of the line into account, we can perform
supersampling by setting each pixel intensity proportional to the
number of sub pixels inside the polygon representing the line
area.

Unit: 2 Graphics Primitives 150 Darshan Institute of Engineering & Technology

 Contd.
▪ A sub pixel can be considered to be
inside the line if its lower left corner is
inside the polygon boundaries.
▪ Advantage of this is that it having
number of intensity equals to number of
sub pixel.
▪ Another advantage of this is that it will distribute total intensity
over more pixels.
▪ E.g. in figure pixel below and left to (10, 20) is also assigned some
intensity levels so that aliasing will reduce.
▪ For color display we can modify levels of color by mixing
background color and line color.
Unit: 2 Graphics Primitives 151 Darshan Institute of Engineering & Technology
 Pixel-Weighting Masks
▪ Supersampling method are often implemented by giving more
weight to sub pixel near the center of pixel area.
▪ As we expect centre sub pixel to be more important in
determining the overall intensity of a pixel.
▪ For the 3 by 3 pixel subdivisions we have considered so far, a
weighting scheme as in fig. could be used.
▪ The center sub pixel here is weighted four times that of the corner
sub pixels and twice that of the remaining sub pixels.
▪ By averaging the weight of sub pixel which are
along the line and assign intensity proportional to
average weight will reduce aliasing effect.

Unit: 2 Graphics Primitives 152 Darshan Institute of Engineering & Technology

 Area Sampling Straight Line
Segments
▪ In this scheme we treat line as finite width rectangle, and the
section of the line area between two adjacent vertical or two
adjacent horizontal screen grid lines is then a trapezoids.
▪ Overlap areas for pixels are calculated by determining how much
of the trapezoid overlaps each pixel in that vertical column (or
horizontal row).
▪ E.g. pixel with screen grid coordinates
(10, 20) is about 90 percent covered by
the line area, so its intensity would be
set to 90 percent of the maximum
intensity.

Unit: 2 Graphics Primitives 153 Darshan Institute of Engineering & Technology

 Contd.
▪ Similarly, the pixel at (10 21) would be set to an intensity of about
15-percent of maximum.
▪ With color displays, the areas of pixel overlap with different color
regions is calculated and the final pixel color is taken as the
average color of the various overlap areas.

Unit: 2 Graphics Primitives 154 Darshan Institute of Engineering & Technology

 Filtering Techniques
▪ It is more accurate method for antialiasing.
▪ Common example of filter is rectangular, conical and Gaussian
filters.
▪ Methods for applying the filter function are similar to applying a
weighting mask, but now we integrate over the pixel surface to
obtain the weighted average intensity.
▪ For reduce computation we often use table look up.

Unit: 2 Graphics Primitives 155 Darshan Institute of Engineering & Technology

 Pixel Phasing
▪ On raster system if we pass the electron beam from the closer sub
pixel so that overall pixel is shifted by factor ¼, ½, or ¾ to pixel
diameter.
▪ Where beam strike at that part of pixel get more intensity then
other parts of the pixel and gives antialiasing effect.
▪ Some systems also allow the size of individual pixels to be
adjusted as an additional means for distributing intensities.

Unit: 2 Graphics Primitives 156 Darshan Institute of Engineering & Technology

 Compensating For Line Intensity
Differences
▪

▪ In general we set intensity according to slope of

the line.

Unit: 2 Graphics Primitives 157 Darshan Institute of Engineering & Technology

 Antialiasing Area Boundaries
▪ Methods we discuss for antialiasing line can also be applied for
area boundary.
▪ If system capabilities permit the repositioning of pixels, area
boundaries can be smoothen by adjusting boundary pixel
positions.
▪ Other method is to adjust each pixel intensity at boundary
position according to percent of area inside the boundary.

Unit: 2 Graphics Primitives 158 Darshan Institute of Engineering & Technology

 Contd.
▪ In fig. pixel at (x, y) is assigned half the intensity as its ½ area is
inside the area boundary.
▪ Similar adjustments based on percent of area of pixel inside are
applied to other pixel.

Unit: 2 Graphics Primitives 159 Darshan Institute of Engineering & Technology

Thank You