1

Chapter Four: Geometry and Line

Generation
COMPUTER GRAPHICS
COURSE NUMBER: COSC3072
PREREQUISITE: COMPUTER PROGRAMMING (COSC 1012)

Compiled by: Kidane W.

2
Introduction 3

 Computer graphics is fundamentally about representing

and manipulating shapes in 2D and 3D space. Geometry
provides the mathematical framework to define:
 Points

 Lines

 Polygons (especially triangles)

 Curves

 Surfaces

 Without this foundation, higher-level rendering algorithms

(e.g. for circles, ellipses, Bézier curves) would not have a
context in which to operate.
Introduction 4

A commonly used approach in computer graphics for

the representation of (complex) objects is the modelling
of their surfaces using basic geometric objects.
 Pointplotting is done by converting a single coordinate
position furnished by an application program into
appropriate operations for the output device in use.
 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.
Introduction 5
 Allcomplex shapes can be reduced to combinations of simple
geometric primitives:
A rectangle is made of 4 lines
A triangle is made of 3 lines
 Circles can be approximated using polygons or parametric line segments
 Thus,understanding how to generate and draw lines effectively is a
prerequisite for handling more complex shapes.
 Many graphics APIs and GPUs (e.g., OpenGL, DirectX) are optimized for
drawing lines and triangles, not high-level primitives. So when you
design an algorithm for a circle or curve, you often convert it to a set of
lines or triangles.
Introduction 6

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.
Introduction 7

 Fora raster video display, the line intensity is loaded in

frame buffer at the corresponding pixel positions.
 Reading from the frame buffer, the video controller then
plots the screen pixels.
 Screen locations are referenced with integer values, so
plotted positions may only approximate actual line
positions between two specified endpoints.
Introduction 8

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 stair step shape is noticeable in low
resolution system, and we can improve their
appearance somewhat by displaying them on
high resolution system. More effective
techniques for smoothing raster lines are based
on adjusting pixel intensities along the line
paths.

Pixel position will referenced according to scan-

Stair step effect produced when line is generated as line number and column number which is
a series of pixel positions. illustrated by
following figure.
 Line Drawing Algorithms 9
 The Line drawing algorithm is a graphical algorithm which
is used to represent the line segment on discrete
graphical media, i.e., printer and pixel-based media.
A line contains two points. The point is an important
element of a line.
 Line drawing is fundamental to computer graphics.
 We must have fast and efficient line drawing functions.
…are critical for:
• Drawing outlines of more complex
Lines are the simplest and most
shapes (polygons, circles)
frequently used primitive in
graphics. • Rendering wireframes in 3D
• Edge detection in image processing

• Vector-based drawing systems (e.g.

CAD)
Line Drawing Algorithms 10

 We can define a straight line with the help of the

following equation. y= mx + a Where, (x, y) = axis of the
line. m = Slope of the line. a = Interception point.

There are following algorithms used for drawing a line:

1. DDA (Digital Differential Analyzer) Line Drawing
Algorithm
2. Bresenham’s Line Drawing Algorithm
DDA (Digital Differential Analyser) 11
Line Drawing Algorithm
 The Digital Differential Analyzer (DDA) Line Drawing
Algorithm is a simple and efficient algorithm used to draw
lines in computer graphics.
 It incrementally plots points along the line between two
endpoints, calculating intermediate pixel positions based
on the slope of the line.
 Key Concepts:
 Start Point: (𝑥0,𝑦0)
 End Point: (𝑥1,𝑦1) As we know the general equation of the straight line is:
y = mx + c
 Slope: The slope 𝑚 of the line is calculated as Here, m is the slope of (x1, y1) and (x2, y2).
m = (y2 – y1)/ (x2 – x1)
Now, we consider one point (xk, yk) and (xk+1, yk+1) as the next point.
Then the slope m = (yk+1 – yk)/ (xk+1 – xk)
DDA (Digital Differential Analyser) Line Drawing 12
Algorithm
DDA (Digital Differential Analyser) Line Drawing 13
A line has a starting point (1,7) and ending point (11,17). Apply the
Digital Differential Analyzer algorithm to plot a line.

Solution: We have two coordinates,

Starting Point = (x1, y1) = (1,7)
Ending Point = (x2, y2) = (11,17)

Step 1: First, we calculate ▲x, ▲y and m.

▲x = x2 – x1 = 11-1 = 10
▲y = y2 – y1 = 17-7 = 10
m = ▲y/▲x = 10/10 = 1

Step 2: Now, we calculate the number of steps.

▲x = ▲y = 10
Then, the number of steps = 10
Step 3: We will repeat step 3 until we get the
Xinc = 1 endpoints of the line.
Yinc = 1
Step 4: Stop
Start Point: (𝑥0,𝑦0)=(2,3 14
End Point: (𝑥1,𝑦1)=(10,8)
15
Bresenham’s Line Drawing 16
Algorithm
 Thisalgorithm was introduced by “Jack Elton
Bresenham” in 1962.
 It is a powerful, useful, and accurate method.
 We use incremental integer calculations to
draw a line.
 The integer calculations include addition,
subtraction, and multiplication.
 Unlike the DDA algorithm, which uses floating-
point arithmetic, Bresenham's algorithm uses
only integer arithmetic, making it much faster
and suitable for real-time graphics applications.
Bresenham’s Line Drawing 17
Algorithm
Step 1: Start. Case 1: If
Step 2: Now, we consider Starting point as (x1, y1) pk < 0
and ending point (x2, y2). Then
pk+1 =pk +2▲y
Step 3: Now, we have to calculate ▲x and ▲y.
xk+1 = xk +1
▲x = x2-x1 yk+1 = yk
▲y = y2-y1 Case 2: If
m = ▲y/▲x pk >= 0
Step 4: Now, we will calculate the decision Then
parameter p0 with following formula. pk+1 =pk +2(▲y-▲x)
p0 = 2▲y-▲x xk+1 =xk +1
Step 5: The initial coordinates of the line are (xk, yk), yk+1 =yk +1
and the next coordinates are (xk+1, yk+1).
Step 6: We will repeat step 5 until we found the
ending point of the line and the total number of
Now, we are going to calculate two cases for iterations =▲x-1.
decision parameter pk
Step 7: Stop.
18
19
Bresenham's Line Drawing from 20
point (2,3) to (10,8).
Bresenham’s Line Drawing 21
Algorithm (Advantages)
Advantages
It is simple to implement because it only contains
integers.
 It is quick and incremental
 Itis fast to apply but not faster than the Digital Differential Analyzer
(DDA) algorithm.
 The pointing accuracy is higher than the DDA algorithm.
Disadvantages
 The Bresenham’s Line drawing algorithm only helps to draw the
basic line.
 The resulted draw line is not smooth.
 Discussion: How to handle 22
downward lines
Ifthe ending y (y2) is greater than the starting y
(y1), then the line moves upward, so sy = +1.

If y2 < y1, the line moves downward, so sy = -1

sx = 1 if x2 > x1 else -1
sy = 1 if y2 > y1 else -1
Shallow and Steep Lines 23

Property Shallow Line Steep Line

Condition dx > dy dy ≥ dx

Driving axis x (step x each loop) y (step y each loop)

Adjusting coordinate Change y when needed Change x when needed

Slope Closer to horizontal Closer to vertical

Line Thickness and Line Style 24

 In computer graphics, line thickness and line style

algorithms are essential for enhancing the visual quality
and representation of lines.
 These algorithms determine how lines are drawn with
varying widths and patterns (such as dashed or dotted
lines) on raster displays.
 The thickness is defined by the number of pixels around
this axis.
Midpoint Line Thickening 25
Algorithm
 This algorithm generalizes Bresenham’s line drawing
algorithm by plotting multiple adjacent pixels to create
thickness.
 It works by displacing pixels orthogonally (relates to a 90-
degree angle) from the line's original path to fill in extra
thickness.
1. Draw the Core Line: Use Bresenham’s or any other line algorithm to plot the central line.
2. For each point on the central line, plot additional pixels above and below or to the left and right.
3. For steep lines, the displacement is vertical (above/below): left and right plotting; for shallow lines, the
displacement is horizontal (left/right): above and below plotting.

If the line is steep (i.e., vertical change |Δy| > horizontal change |Δx|):The main direction is vertical, so thickness should be
applied horizontally — plot additional pixels to the left and right of each core point. If the line is shallow (i.e., |Δx| > |Δy|):The
main direction is horizontal, so thickness should be applied vertically — plot additional pixels above and below each core point.
Parallel Line Algorithm 26

Instead of thickening the line by plotting extra

pixels around a core line, this algorithm draws
multiple parallel lines to simulate thickness.

1. Compute the Perpendicular Direction: Determine the direction perpendicular

to the original line using the slope.
2. Draw Parallel Lines: Shift the line by incremental distances (depending on
thickness) along the perpendicular direction and draw additional lines.
Line Style Algorithms 27

Line style algorithms modify the appearance of

lines by applying different patterns such as
dashed, dotted, or combinations of both.
Dashed Line Algorithm

1. Determine Dash Length and Gap: Decide on the length of each dash
and the gap between dashes.
2. Draw the Line in Segments: Use a line drawing algorithm to draw a
segment (dash), then skip a corresponding gap before drawing the next
segment. function DashedLine(x1, y1, x2, y2, dashLength, gapLength):
currentLength = 0
while currentLength < totalLength(x1, y1, x2, y2):
drawLineSegment(x1, y1, x2, y2, dashLength)
skipLineSegment(x1, y1, x2, y2, gapLength)
currentLength += dashLength + gapLength
Dotted Line Algorithm 28

A dotted line consists of individual points (or very

short line segments) spaced at regular intervals.
1. Set Dot Spacing: Define the distance between dots (e.g., every few pixels).
2. Plot Dots: Plot individual points or very short line segments at regular intervals
along the line.

The dotSpacing parameter defines how frequently the points are plotted. For
example, if dotSpacing = 3, every third point will be plotted.

function DottedLine(x1, y1, x2, y2, dotSpacing):

for each pixel along the line: //pindex =0
if (pixelIndex % (dotSpacing+1) == 0): //# Plot only if pixelIndex is a multiple of
dotSpacing
plot(x, y)
Plotting General Curves 29

 Plotting a general curve involves representing a

mathematical function or equation visually on a
coordinate plane. This function can be of various forms,
including polynomials, trigonometric functions,
exponential functions, and more.
1. Define the Function
2. Identify the range of x-values (domain) for which the function is defined.
3. Calculate the corresponding range of y-values (range)
4. Generate Points
5. Connect Points
Example: (Plotting a Parabola): 30

1. Function: y = x^2
2. Domain: All real numbers
3. Range: y ≥ 0
4. Select a set of x-values, such as: -3, -2, -1, 0, 1, 2, 3.
5. Calculate the corresponding y-values: 9, 4, 1, 0, 1, 4, 9.
6. Connect the points using a smooth curve.
31
Example2 Polyline 32
Circle Drawing Algorithms 33
A circle is a closed two-dimensional figure in which the set of all the
points in the plane is equidistant from a given point called “centre”.

The circle formula in the plane is given as:

( x  xc ) 2  ( y  yc ) 2  r 2
 where (xc, yc) is the centre of the circle.

Alternatively, in polar coordinates we can write:

Circle Formulas 34

Circumference (C) = πd = 2 π r
Area of a circle = πr2 We know that Area is the
space occupied by the circle.
Circle Drawing Algorithms 35

 Forexample, suppose we want to draw a circle with (xc,

yc) = (5,5) and r = 10. We start with θ = 0 degree and
compute x and y as:
x = 5 + 10 cos 0 degree = 15
y = 5 + 10 sin 0 degree = 5
 Therefore we plot (15,5). Next, we increase θ to 5 degree:
x = 5 + 10 cos 5o = 14.96
y = 5 + 10 sin 5o = 5.87 Therefore we plot (15,6)
 Thisprocess would continue until we had plotted the
entire circle (i.e. θ = 360 degree).
Bresenham - Circle Generating 36
Algorithm
 Drawing a circle on the screen is a little
complex than drawing a line.
 Thereare two popular algorithms for generating
a circle − Bresenham’s Algorithm and Midpoint
Circle Algorithm.
 Thesealgorithms are based on the idea of
determining the subsequent points required to
draw the circle.
 The algorithm uses symmetry (8-way symmetry
of the circle) to reduce the number of points
calculated.
Bresenham - Circle Generating 37
Algorithm
Step 1 − Get the coordinates of the center of the circle and radius, and store
them in x, y, and R respectively. (x,y) = (0,r)
1. Set 𝑥=0, 𝑦=r (starting at the top of the circle).
2. Set decision parameter d = 3 – 2r.
3. Plot the first point and its symmetric points in all 8 octants.
Step 2 − Iterate Over Points:
1. For each point, check the value of 𝑑 (the decision parameter).
2. If 𝑑 < 0, the next point is horizontally to the right: (𝑥+1,𝑦). Update the
decision parameter: d=d+4x+6
3. If 𝑑 ≥ 0, the next point is diagonally down and to the right: (𝑥+1,𝑦−1).
Update the decision parameter: d=d+4(x−y)+10.
4. Continue plotting symmetric points in all 8 octants.
Step 2 − Termination: The algorithm stops when 𝑥 exceeds 𝑦, as the circle is
complete. Repeat until x > y
function BresenhamCircle(x_centre, y_centre, radius):
x=0
y = radius
d = 3 - 2 * radius // Initial decision parameter
38
// Plot the first set of points in all octants
PlotCirclePoints(x_centre, y_centre, x, y)

// Loop until x >= y

while x <= y:
x=x+1

// Check the decision parameter and update accordingly

if d < 0:
function PlotCirclePoints(x_centre, y_centre, x, y):
d = d + 4 * x + 6 // Move to (x + 1, y)
// Using symmetry to plot in 8 octants
else:
plot(x_centre + x, y_centre + y)
y=y-1
plot(x_centre - x, y_centre + y)
d = d + 4 * (x - y) + 10 // Move to (x + 1, y - 1)
plot(x_centre + x, y_centre - y)
plot(x_centre - x, y_centre - y)
// Plot points for all 8 octants
plot(x_centre + y, y_centre + x)
PlotCirclePoints(x_centre, y_centre, x, y)
plot(x_centre - y, y_centre + x)
plot(x_centre + y, y_centre - x)
plot(x_centre - y, y_centre - x)
Midpoint Algorithm 39

The midpoint algorithm takes advantage of the

symmetry property of circles to produce a more
efficient algorithm for drawing circles. The
algorithm works in a similar way to Bresenham’s
line-drawing algorithm, in that it formulates a
decision variable that can be computed using
integer operations only.
The Midpoint Circle Drawing Algorithm is an
efficient algorithm used to plot the points of a
circle in computer graphics.
Midpoint Algorithm 40

1. Initialization: The algorithm starts at the circle's radius (i.e., (0, r)) and
iteratively steps along the perimeter of the circle.
2. Decision Parameter: determine whether the next point should move
horizontally or diagonally.

# Update the decision parameter

if p < 0:
p next = p + 2 * x + 1
else:
p next = p + 2 * x + 1 - 2 * y

3. Since circles are symmetric, the algorithm only calculates points for
one-eighth of the circle and reflects these points across all octants.
4. The process continues until the point reaches the x > y diagonal.
Midpoint Circle Drawing Algorithm 41

void circleMidpoint (int xCenter, int yCenter, int radius)

{
circlePlotPoints(xCenter, yCenter, x, y);
int x = 0; while (x < y) {
Int y = radius; x++;
if (f < 0)
int f = 1 – radius; f += 2*x+1;
else {
y--;
f += 2*(x-y)+1;
}
}
circlePlotPoints(xCenter, yCenter, x, y);
}
Midpoint Circle Drawing Algorithm 42

void circlePlotPoints (int xCenter, int yCenter, int x, int y)

{
setPixel (xCenter + x, yCenter + y);
setPixel (xCenter – x, yCenter + y);
setPixel (xCenter + x, yCenter – y);
setPixel (xCenter – x, yCenter – y);
setPixel (xCenter + y, yCenter + x);
setPixel (xCenter – y, yCenter + x);
setPixel (xCenter + y, yCenter – x);
setPixel (xCenter – y, yCenter – x);
}
For example, given a circle of radius 43
r=10, centered at the origin, the steps are:

First,compute the initial decision variable:

Plot (x0,y0) = (0,r) = (0,10) p0  1  r  9
Iteration 0:
p0 < 0, so
Plot (x1,y1) = (x0+1,y0) = (1,10)

p1  p0  2 x1  1  9  3  6
OpenGL Circle Example 44
45
Polygon Plotting 46

A polygon algorithm generally refers to methods

used to draw, analyze, or manipulate polygons.
This includes basic algorithms for plotting
polygons, calculating their properties (e.g., area,
perimeter), determining if a point lies inside a
polygon, and performing geometric operations.
Convex Polygon Vs. Concave 47
Polygon
Feature Convex Polygon Concave Polygon

Interior Angles All less than 180 degrees At least one greater than 180 degrees (reflex angle)
Any segment between two internal points At least one segment between two internal points
Line Segment stays inside goes outside

Diagonals All diagonals lie inside the polygon At least one diagonal lies outside the polygon
Line A line intersects the boundary at most
Intersection twice A line can intersect the boundary more than twice
Shape No dents or indentations Has at least one dent or indentation
Algorithm 48

Input: A set of vertices [(x1, y1), (x2, y2), ..., (xn, yn)]
defining the polygon.
1. Start with the first vertex (x1, y1).
2. For i = 1 to n-1: - Draw a line from (xi, yi) to (xi+1, yi+1).
3. Connect the last vertex (xn, yn) back to the first vertex
(x1, y1) to close the polygon.
4. Optionally fill the polygon if needed.
Polygon Filling 49
Polygon filling is a core operation in raster graphics used to color the interior of a
polygon, rather than just its outline.

 Fillinga polygon means determining and coloring all the

pixels inside a polygon. One of the most common
algorithms used for this is the Scan-line Fill Algorithm,
which is efficient and widely used in computer graphics.
 The Scanline Fill Algorithm works by drawing horizontal
lines (scanlines) across the polygon and determining the
range of pixels that are inside the polygon on each
scanline.
 Ituses the edges of the polygon to compute where the
scanlines intersect the polygon's boundaries, and then fills
in between those intersections.
 Algorithm 50

Input: A polygon defined by vertices [(x1, y1), (x2, y2), ...,

(xn, yn)].
1. Sort the vertices of the polygon by their y-coordinates.
2. Initialize the Edge Table and fill it with the polygon’s
edges. Concept:
3. For each scanline from the bottom y-coordinate to the • Process the image row by row (i.e.,
top y-coordinate: scanlines).
• Find intersection points of the
Find the intersection points of the scanline with the
scanline with polygon edges.
polygon edges.
• Sort them by x-coordinate.
Sort the intersection points by their x-coordinates. • Fill between pairs of intersections.
Fill the pixels between each pair of intersection points.
4. Repeat for all scanlines to fill the polygon.
Polygon Examples 51
Text and Characters in Computer 52
Graphics
The characters are rendered directly from a pixel
grid instead of vector graphics, making them
useful for applications that require fixed-size fonts
or low-resolution displays a significant role in
computer graphics, especially in user interfaces,
digital art, games, and other visual media.
They provide essential information and enhance
the visual experience.
Text Representation 53

Bitmap Fonts:

Bitmap fonts are stored as an array of pixels for

each character.
Advantages: Simple and efficient for displaying
text at fixed sizes.
Disadvantages: Lack scalability; resizing can lead
to pixelation.
Text Representation 54

Vector Fonts:

Vector fonts are defined by mathematical

equations and curves (e.g., Bezier curves).
Advantages: Scalable to any size without loss of
quality; smooth rendering.
Examples: TrueType, OpenType.
Text Representation 55

Unicode:

A character encoding standard that represents

characters from most of the world's writing
systems.
Advantages: Supports multiple languages and
symbols, enabling internationalization of
software.
Text Rendering Techniques 56

Rasterization Process:
Converting vector text into a bitmap image suitable for display
on a raster device.
Techniques: Font Smoothing:
Techniques like anti-aliasing to improve the appearance of text
edges.
TextShading: Adding shadows or gradients to enhance
readability.
Texture Mapping:
 Applying a bitmap font as a texture to a surface in 3D
OpenGL Text Rendering 57
 58

End of Chapter 4