Scan Converting Lines, Circles and Ellipses Video Lecture - Computer Science Engineering (CSE)

Oh No - aha youngja y de does mean he
was the love each other
[Music]
hello and welcome to the lecture on
computer graphics today we are going to
learn about algorithms by which lines
circles and ellipses are drawn in
computer graphics so the title of the
lecture is scan converting lines circles
and ellipses and the word scan
converting itself gives you a meaning as
to that you have to basically scan and
convert the lines from the frame buffer
onto the screen okay
so basically how to fill up the pixels
in the frame buffer and automatically
the lines or the curves will be drawn on
this screen now if you remember the
there are basically almost 44 different
attributes of drawing in computer
graphics one are lines second arcs
curves and ellipses they fall under one
category in fact circle is a special
type of an ellipse and arc is also a
special type it's a part of a circle
ellipse so arc circles an ellipse fall
under one category state lines fall
under one category and then polygon
drawing and it's filling is the third
type which we will see later on in due
course of time and of course those form
a combination of line drawings using
line drawings we basically draw polygons
on the screen and also fill them with
different types of patterns so that is
the third category and of course the
fourth category is it drawing text on
the screen so out of these four
different attributes of drawing lines
are circles ellipses or polygons filled
or empty on text we are going to study
the first one first the method of
drawing a straight line on this screen
okay and of course that seems to be the
most easiest one out of these four
different attributes basic minimal
attributes necessary for any graphics
drawing packet software or standard
which you whatever you mean and we will
see why drawing lines are fun for for
drawing lines you need an algorithm to
draw a line because the state line is
probably the easiest thing which a baby
even can draw in is
cool in the primary section you give him
a piece of paper and a pencil or a pen
and give him a scale and it just draws a
line puts the scale and draws a line and
the equation of line is also very
straightforward the most simplest one
when you read the equations and read
geometry the equation of the line comes
on first the x linear expression and
there should not be any problem so why
do we talk of an algorithm for scan
converting lines we will see that and
before going into it of course I will
give you a hint why new geniune
algorithm because when we draw a line
when you think of a line in a graph
paper on a plain paper or whatever the
case may be we are probably in fact why
probably drawing a line in a analog
environment where all points are defined
all for X Y different coordinates but
but in the case of a computer graphics
in the case of computer graphics you
have a digitized
raster environment so X Y are defined as
integer coordinates and you need to
actually find out what are those
coordinates which fall on the line
before you draw it so that is the
problem the digitized space we do not
have continuous values of x and y like
the analog world and so I and hence the
case we need a method or an algorithm by
which you draw a line okay so what are
the main points what is basically a line
what are the key issues of drawing a
line well the problem now can be posed
as that given the specification for a
straight line given the specification
for a straight line find the collection
of addressable pixels which most closely
approximates this line now you can
almost start to visualize you remember
the lectures on display devices raster
and all that you can visualize yourself
the digitized space or the raster space
as a matrix or an array of pixels and
definitely if you draw an arbitrary line
not all of these square pixel blocks or
raster positions will fall in a line so
we are talking of approximately
representing land in that sense truly of
course in an analog environment you can
see there are basically almost infinite
points which lie on a line that is not
the case we have a finite set of pixels
which fall on a line and you
find out which are those finite pixels
when I define a line you can talk think
of an equation of a line or the starting
point x1y1 and the finishing point x2y2
of a line and you need to you can simply
draw a line by a scale that is fine but
in the case of a graphic screen which
you are leaving now in a TV or a CRT
monitor you have to find out what are
those pixels starting from X naught Y
naught and so on up to and n points x
and y in our x1 y1 okay so what are
those points or addressable pixels is
the term used here in the problem
definition which falls in this line so
that is the problem pause now that I
read it again given the specification of
a straight line either in the form of an
equation or the starting point at the
endpoint if that is given to you find
the collection of addressable pixels
which most closely approximates this
line so that was the definition which
was given and so the goals of the if you
look into the next line the goals of
this solve a solvent the problem and of
course I must say here that at a given
point of time not all of them may be
achievable with the discrete space of a
raster device so that is the
discretization of the raster device is
the one which is causing the problem we
will see a lot of examples what is this
illustrative examples are there in the
next 1 hour or more where we will see
why what is meant by the problem of
approximating this line and drawing a
line in a discretized space of a raster
device ok let's find out the goals of
drawing straight line should appear
straight now again you have to start
thinking in the rasterized scenario or
you can wait till I bring up the
illustration of drawing a line in a
discretized environment because for L
straight line is a straight line ok if
you think from a mathematical
perspective or from a child as you say
we give a scale and you can draw a line
L straight line is a straight line ok
unless the scale shift or paper shapes
as long as a rigid environment you draw
a line it always appears straight so
what is the issue here and when we talk
about straight line should appear
straight yes this is because the
rasterize environment which we will see
that it it makes the line appears not
crooked but something else which you
will see so our motivation or the goal
here for the problem is to find out
those addressable pixels from the
starting point to the end
point in this discrete array of pixels
we're in such a manner and the state
line should appear as straight as
possible as linear as possible from the
starting point to the finishing point so
that is the first goal a straight line
should appear straight and you can hold
on until the examples come to find out
what this goal basically mean we will
have a lot of examples today and the
second goal as appears on the screen now
is that the line should start and end
accurately that is very very important
actually you can start on the a point
and reach the other point or draw the
line in the reverse fashion whatever the
case may be you should draw the line
accurately and and should not expect to
come up with an algorithm where you
start at this at a starting point all
right and finish somewhere near or close
to the ending point that will not solve
the purpose that does is not the goal of
computer graphics it should start at
their starting point and end at the
finishing point that should be the case
and matching end points with connecting
lines okay so that is the case which is
very important two main goals are it
should appear straight and it should be
accurate the lines should have constant
brightness that is also the case and the
question comes is when you probably take
a pencil and draw the line typically
appears constant in a in a paper but
what is the issue here when you talk of
a line having constant brightness well
we will see that the addressable pixels
which you are drawing may not be
uniformly spaced along the line in terms
of the distance between corresponding
our respective I am sorry the
corresponding pixels as they come from
the starting to the finishing point and
if the addressable pixels the distance
between them start varying from small to
large from the starting point to the
ending point the pixels which are there
their gaps are non-uniform what will
happen the the line may appear slightly
more darker at certain small small
sections and lighter in certain other so
we will try to also see that how to make
a line with a constant rightness and the
last and most important point as far as
computer science is concerned for any
algorithm is it should be as fast as
possible the complexity should be made
as minimal the cost of computation the
because you have to calculate certain
values and it should be known as rapidly
as possible such that the line is drawn
very fast
so what are the problems associated with
drawing a line okay the main goal of the
algorithm is to basically the problem is
to determine which pixels to eliminate
to satisfy the ever above goals you know
all the pixels are dark if you want to
just draw line one line on the screen
you have to eliminate a set of pixels
and which are those pixels from the
starting to the finishing point are
these pixels you have to eliminate up
fill up the raster such that the
straight line appear straight accurate
and uniform whiteness now this problem
of the line appearing not very uniform
the in terms of brightness and straight
doesn't happen in all cases of line out
of all possible lines which you can draw
on the screen the lines which are
vertical on the screen exactly vertical
horizontal it means typically we are
talking about along the x axis of the
screen and Y axis of the screen and
lines with slope plus and minus 1 that
is its substance and that is the angle
between the line and X or Y axis is 45
degrees or PI by 4 radians these are the
3 or 4 special cases where you actually
get a straight line and they are the
easiest to draw you will see that as
well well all other cases for all other
lines it creates problems that means you
have what is an effect called as a stair
casing effect it is also called jaggies
or also called aliasing these three
terms will be used in the changeable
throughout the course and we will soon
see what do I mean by the effect of
stair casing of a line in general
remember the second point which we
discussed this before this effect of
stair casing jaggies or aliasing do not
occur in a line if the line is
absolutely vertical horizontal or up to
the slope of plus or minus 1 okay so
these lines appear absolutely straight
there is absolutely no problem in of
course in these cases also we have to
find out using the same same algorithm
what are the points in between the
addressable points which was be
illuminated all right but the problem of
this stair casing effect or the jaggies
or aliasing the other two terms which
are used in the chain
we made some time call it there is an
aliasing the stair casing effect these
problems will not be there for these
three or four special cases whereas for
every other line you will have this
effect in the line and the quality of
the line drawn depends on the location
of the pixels and they are brightness so
that is also very important that the
location of the pixels on the line
determine the local brightness in the
line and that local brightness should be
uniformly uniform from the starting to
the finishing point okay so these are
the various problems this is an example
of an effect of the stair casing jaggies
or aliasing which you are talking about
and the problem comes therefore because
it is difficult to find out which are
the addressable pixels which must be
eliminated in this case I am trying to
draw a line from the left hand corner
here at the bottom left of the line to
the top right so the starting and the
ending pixels are given and the question
comes is which are the pixels in the
line you can almost visualize that the
line does not actually pass the center
of any pixel so you have to eliminate a
set of pixels to make it appear very
straight and you can see here in the
middle there are two options for you you
can eliminate the top white portion
which is either left or the bottom blue
one in both cases it is the same because
the line passes through in the center of
these two pixels and you can actually
have two different lines drawn for the
same straight line same specification of
the starting point or ending point or
slope and intercept of the line we will
see the equations of the line but in
this case you can see the effect of
stair casing as you move from left to
right left the bottom to top right it
appears as a staircase that is why it is
called a stair casing effect or the line
appears jaggies have you move through
the analog line when a log line means
the state and exactly as you would have
drawn in a graph paper the line appears
very crooked and jagged from left to
right it oscillates and that is the
effect which is predominant in almost
any lines except special lines and then
again it is the and then now you can
almost visualize you basically need a
very fast algorithm to find out which
are these lines from the bottom left to
the top right of the screen to be drawn
here
illuminated just that you have a uniform
straight line so that is that is the
problem with this example which shows of
course we will take numerical examples
to find out how do you calculate and get
those pixels but this is an example we
which illustrates two facts the one fact
is that the there is an effect of stair
casing or jaggies as you move that the
line dances up and then again there are
two options in certain cases you have
two options of choosing this or that
pixel and it is sometimes difficult to
find out which pixel you will draw to
actually have uniform illumination and
that is the main problem as far as the
third and the last goal of the algorithm
is concerned is now the question comes
is you how fast can you draw how fast
can you draw because the algorithm will
be so fast that you must be able to draw
a line instantaneous scheme the
algorithm is slow you are eliminating
one pixel after another nobody will
purchase your graphic software because
the big why because the you are not
going to roll in a single line you are
going to draw an entire picture which
consists of lines arcs texture polygons
shading textures and all that and if you
to draw a line itself could be a very
slow process where a user basically sees
one line being drawn here then another
line and so on to compete one structure
itself if you take a second or more and
the entire picture a few minutes then
nobody in fact will draw a line in fact
you should draw a line as fast as
possible so that the user cannot
perceive that the line is being drawn
the algorithm must be very fast so you
need to do some computations very fast
and in the integer space in the
discretized raster space such that the
algorithm is draw fast I again repeat
that for analog case as far as
mathematics is concerned given the
specification of a line you can always
drawn a line in a graph paper there is
absolutely no problem but that is not a
simple transformation from the analog
graph paper or a white paper in fact to
the discretized skin where we have an
array of pixels discretized environment
and we have to select certain pixels
certain certain addressable pixels in
the raster map which should be drawn so
these are the two problems which hamper
us and of course there are good
algorithms which we will see we will see
a slightly more
simple algorithm to start with and then
we will come up which may not be that
fast and then we will see our fast
algorithm can be designed okay so let us
look at a solution for trying to draw a
line the way we know we draw a line in a
graph paper we look at the equation of
this of the line in a screen where we
say that the direct solution say the
simple expression of a line which gives
you try to solve the equation y equals
MX plus B where m is the slope of the
line and 0 comma B is the y-intercept of
the line we all know this M is the slope
B is the y-intercept and you can pick up
values of any values of X substitute on
the right-hand side of the expression M
X equal to plus B and compute the value
of y which you will get on the left hand
side okay so that is very simple you can
substitute any value of x but
unfortunately X values are discrete set
of values integer discrete set of values
and let us say my X naught comma Y
naught is the starting point and x1
comma y1 is the finishing point or end
point of the line so what your care must
keep doing is substitute values from X
naught X naught plus 1 and so on up to
x1 and substitute in the equation MX
plus B here and get the value of y if
the values of even if X is an integer
value of the problem which comes here is
the value of M and B B could be an
integer location but the value of M is
definitely in general a floating point
number and a is a floating point number
and even in spite of the fact that X and
B I can put a constraint that X and B
are integer values because I am drawing
it on a graph paper with integer
coordinates let us say and or in screen
with integer coordinates pixel values so
if X and B could be integers and M is a
floating point that's enough to give us
a value of y which is a floating point
number so you have to round off the
value of y why round off you can easily
guess we will see that if you do not
whine round up the value of Y or take
the next highest or the next low as the
the line does not appear well so you
need to round off the value of Y from
the above equation MX plus B or the
value of MX plus B which is a floating
point number must be rounded off to get
the actual integer value of y
okay take an example we'll take an
example and compute certain values of
integer coordinates let us say I take a
simple value of B is equal to one so my
starting point is zero comma one for the
line and the slope is a fractional
number say three by five which could be
0.6 which is in fact point six I
represent it as three by five or you can
write it as point six and try to
calculate that if I start to obtain the
value of successive values starting from
the location 0 comma 1 and next
successive five values you see here they
are given in this table on the bottom
where if I substitute X equal to 1 in
the expression M X equal to B where m is
equal to 3 plus 5 and the value of B is
equal to 1 you get a Y which is round of
3 by 5 plus 1 which is 8 by 5 so round
of 8 by 5 will be equal to 2 okay so you
round it off and get a integer value of
2 you can keep on substituting next take
the value of x equal to 2 what you will
get is under MX plus B you will get 6 by
5 plus 1 which gives you round off 11 by
5 round of 11 by 5 is 2 for X equal to 3
you get round off 14 by 5 y 3 into 3 by
5 9 by 5 plus 5 so it gives you 14 by 5
X equal to 4 gives you 12 by 5 plus 1
which is 17 by 5 and X equal to 5 gives
15 by 5 divided plus 1 divided by 5 so
it is 20 by 5 so round of 20 by 5 is
exactly 4 and so the ending point is
fine but if you see the other ones
around 17 by 5 is will give you 3 round
14 but I will use so these are now the
integer coordinates obtained by using
the calculation MX plus B where B is
equal to 1 M is equal to 3 by 5 starting
point is 0 comma 1 of the line finishing
point is 5 comma 4 and these are the
integer coordinates 1 comma 2 2 comma 2
3 comma 3 & 4 comma 3 these are the
addressable pixels or integer
coordinates of the line which we have
obtained by this calculation so let us
look at the result actually if you had
given the starting point 0 comma 1 and
finishing point 5 comma 4 you can
calculate yourself the equation of the
line and say that my slope is I am sorry
the intercept P is equal to 1 and the
slope is 3 by 5 because it starts at 0
comma 1 and ends at 5 comma 4 or it
starts at 1 comma 2 and ends at 5 comma
4 and you can draw the line in this form
okay so 0 comma 1 s so there it is
basically 1 2 3 so at 1 2 3 so 3 by 5 is
the slope of the line because the
vertical disparity is exactly 3 and the
horizontal disparity is 5 so the slope
of the line is basically 3 by 5 4 minus
1 is the numerator 5 minus 0 so it is 3
by 5 as you can see and if you have
given the graph paper near to a boy in a
school or a child in a school he would
have drawn this line from the starting
point 0 comma 1 to the finishing point 5
comma 4 so that I will so this is an
example of not the picture of the roster
line drawn on the graphic screen this is
an ideal case of a line drawn on a graph
paper you just you just have to worry
about 0 comma 1 and 5 comma 4 or vice
versa
you can start from 5 comma 4 and end at
0 comma 1 also
nobody starting and ending point could
be swapped but still you get the same
line and you draw the line on the graph
paper but this will not suffix in a
raster screen why as you can see the
integer position the pixels the
horizontal grids those intersection
points are the points where the pixels
lie of course the starting point 0 comma
1 at the bottom left and 5 comma 4 on
the top right are the starting and
finishing points so those pixels of
course have to be switched on that is
fine but what about the rest in the
middle as you can see if the
intersection intersecting gridlines are
the locations of the pixels which
includes of course they're starting on
the finishing point also where is the
starting point here 0 comma 1 finishing
point 5 comma 4 fine but if you stick
the other integer coordinates which are
the intersection points of the grids the
line does not pass through any of the
intersection points it is bound to
happen in general for almost all
except the lines which are vertical
auras on ttle and of course barring a
slope of plus and minus one those are
special cases otherwise in general a
line is almost like it is not guaranteed
but in general what will happen is it
will not pass through an intersection
point this is what we see in this
example that this line does not pass the
intersection point and now the question
comes is which of these intersection
points which you see on so on that
screen just now have to be illuminated
they may not exactly lie on the line but
you have to actually find out the
closest closest of those integer pixels
or addressable pixels or points on this
screen which has to be switched on to
give you a feeling that you are
basically drawing a line which is almost
straight now you will ask a question
when I see a straight line on a screen I
usually see it straight I do agree with
you I do agree with you in fact the
screen which you have just seen now I
had drawn a line which is shown on a
graphic screen why does it appear
straight enough well I must admit you
that you are seeing a line on a very
high-resolution graphics monitor and
that monitor typically may have thousand
pixels by about a few hundred to almost
thousand by thousand grain and you have
seen that line that line will not
consist of only three or pixels which
have been eliminated on the screen that
line the red line which you have just
seen now as an example of that
continuous line may consist of several
hundred pixels and the several hundred
addressable points when they are so very
close and densed they tint and lie
almost very close to the line you have a
feeling that it you are basically
drawing a straight line so that is the
advantage of perception of the eye which
you try to bypass or Teeter it will be
to give you an impression that all the
pixels are not exactly lying on the line
it's so dense and so close and if you
are drawing a line which is of length
several hundred pixels let us say at
least 100 or more it will appear to be a
straight line but you can find the
effect of stair casing and jag is by two
methods two methods are the following
when a watching through a TV monitor or
a computer screen take a lens and try to
observe a line very closely a very thin
line or even it could be a thick line we
will see the problems of thick lines
later on in this screen let us worry
about a line but the width is just one
pixel if you zoom on to that screen
either using a line
or or through some Photoshop or pen
brush type of software's you will find
that the pixels start to blow up as
square blocks you will see with an
example I have got an example where I
will show when you zoom close to a line
how the pixels start appearing and you
will start to see the effect of jaggies
from the starting point to the ending of
the line so and when you blow out
instead of blowing in and the line
appears dense and condensed it appears
in a straight line so please do not have
a feeling in mind that I am just saying
that the line which appears straight why
do am I saying that the line will appear
it has to appear the stair casing effect
has to appear because you are working in
a rasterized digitized environment the
pixel attribute addressable points when
the very close will appear almost a
straight line but still we should try to
make an attempt to draw a straight line
as possible by selecting the addressable
points which are very close that is the
problem which I have just shown now and
of course the second problem is how fast
we can draw the line that is the most
important part where we need the the
computer scientists and computer science
based students will be very happy to
come up with an algorithm where we are
in need of processing things very fast
come up with an optimal algorithm before
to solve that but we are still in the
environment where we substitute the
value of M into MX plus B okay M is a
floating point number X and B could be
integers so the resultant value is a
floating point number you use around
operation to calculate the Y and X comma
y integer values you select them okay so
let us see with this example which you
have just solved now this was the
example which we just saw now the
starting point was obtained as 1 comma 2
the finishing point of the line was 5
comma 4 the rest of the values in
between were obtained using round
functions so these are the examples
which we just solved about one or two
slides back and is and why the round
function is important I did say that
that is probably the closest integer
pixel which you get if you do not use
round function then what will you use of
course you cannot get a pixel at the
fractional numbers which are put on the
right hand side that is at 8 by 5 11 by
14 by 5 17 by these are floating-point
numbers there is no addressable pixels
available at any arbitrary floating
point numbers so you will say instead of
rounding I will
choose the next highest number on the
next lowest number okay if you choose
the next highest number let us see what
it happens if you choose the next
highest number with starting from 0
comma 1 and then 1 comma 2 that is the
next highest instead of 11 by 5 the next
comma next highest number will be 2
comma 3 3 comma 3 of course is the next
highest then you get 4 comma 4 and 5 you
can see these are the next size instead
of using the round function what has
been done here is you have chosen the
next highest integers with respect to
the values given on the right hand side
next highest of 8 by 5 which is 2 so you
have 1 comma 2 next highest of 11 comma
5 is 3 so you have 2 comma 3 instead of
2 comma 2 14 by 5 next is gives you 3
that is fine but is 17 by 5 the next
highest is 4 so these are the pixels
which you will get if you choose the
next highest you can visualize yourself
that if you choose the next lowest
instead you just almost get the mirror
image of what are the pixels which we
have just seen on the screen and as you
can see on the screen the pixels which
you have seen they are all one one side
of the line and that is not the line we
were looking for the line will appear to
be little bit shifted away only the
starting and the ending point will be
the same all the pixels will appear to
be lopsided if you use the round
function what happens this is now the
figure which we see here instead of the
next ties if when you use the round
functions and we have already used it
and obtained the integer coordinates of
x and y as 1 comma 2 2 comma 2 3 comma 3
4 comma 3 and 5 comma 4 and they have
been drawn on this screen starting from
0 comma 1 the starting point to 5 comma
4 1 comma 2 of course is the next
addressable point then 2 comma 2 here 3
comma 3 here 4 comma 3 here 5 comma 4 is
the last finishing point now you can see
there is a lot of balance there are a
few pixels on the top of the line some
on and some at the bottom of the line ok
so this is what is going to happen and
you will have a uniform split of a few
points on both sides of the line and
typically this is scenario which will
get you numerical computing exercises of
what is called as least square
regulation of a line where these points
are given and you need to find the
equation of a line but that is a
different problem altogether in this
case of computer graphics you are
expected to find out
points which are distributed over the
line and the most closest that is what
is most important that you need to find
out the points which are most closest
and these are the points which are most
closest by using the round function so
what we have done in the calculation so
far we know the starting point and the
finishing point of the line from that we
compute the slope of the line which is
the M get sucks and of course we know
the y-intercept B that is fine and we
know the starting point so from the
starting point to the finishing point x
coordinates we take keep on taking the
next successive integer value that means
keep incrementing by one and for each
such step of after incrementing one what
you have to do you have substitute in
the equation MX plus B get a floating
point number rounded off get a Y value
which is an integer and that is how you
compute this so this is not an algorithm
but a method by which you get the
nearest addressable points why well I
say that this is not an algorithm it
works fine okay in this case it will
give you the correct addressable lines
you can guarantee that is absolutely no
problem but there are two issues here in
fact almost in fact one issue the
problem comes because that means I say
the method D Y this is undesired or not
wanted for I do not want to use
operators like multiplication and
divisions which are expensive and also
the round function is all at each step I
have to multiply M by X and then adapt
to be ad is fine and this it is an all
in floating point space floating point
based operations multiplication division
addition subtraction are more costly
than integer operations this we know
from basics of computer science of
arithmetic the floating point arithmetic
is much more cross scale many many times
than the integer arithmetic because the
the hardware is suited there are very
fast algorithms and hardware available
to do integer computations in terms of
addition subtraction and multiplication
and the floating point it takes about
more than double the time could be even
4 times the amount you need to do an
addition or multiplication using integer
arithmetic so all these floating-point
operations multiplication addition and
division are expensive operations and
most over that and each
at each step you need to have a round
function at each step you need to have a
round function plus an integer method so
that is going to be the word you lose
time you cannot generate the points very
fast to draw the line and you know that
when you cannot generate points very
fast
you cannot fill up the raster space with
addressable points and the line drawing
process will be very slow
you need a very fast algorithm were
given the starting point and the
finishing point of a line okay or the
starting point could be here the
finishing point could be there whatever
the case may be you need to actually get
this addressable integer locations very
fast so the line is drawn almost
instantaneously not like a pixel then
the second pixel then the third pixel
and so on and if you have an algorithm
by which each of this computation
produces a significant amount of delay
in generating all these integer pixels
one after another from the starting to
the integer point nobody will purchase
your software nobody you will use your
computer graphics program the and it
will not be approved by software
specialists and and and specialists in
the field of computer graphics and that
they will say we are sorry it is a to a
slope program it works fine it gives you
the exact positions of addressable
points those addressable points are the
closest to the line drawn that is all
fine but it is too slow this is too slow
because of these mathematical operations
which take time multiplication addition
division and the round operation each
loop there n number of loops depending
upon number of points which you need to
draw and for each loop you have a
multiplication operation floating point
a floating point addition in a round
function three floating point operations
out of them round is the most cost least
one and of course multiplication as well
and they are the ones which is consuming
time okay and the other fact which you
see now is that if you use this round
function you can get gaps in the line if
the slope is more than one okay let us
take this example as you see on this
screen ok you can get gaps in the line
if the slope is much much more more than
one let us take an example the slope is
very high let us take an example where M
the slope of a line is equal to 10 and
the slope B is equal to 2 now the
equation of the line y equals MX plus B
y equals MX
as beak is written as y equals 10x plus
2 okay
substitute X equal to 1 what do you get
it is given already y is equal to 12
substitute the next integer point x
equal to 2 what do you get 20 plus 2 22
now you can see you have to address next
addressable points differ by a wide
margin at X equal to 1 you have y equal
to 12 at X equal to 2 you have y equal
22 this do you cannot draw a line like
this you cannot draw a line like this so
there are methods by which this sort of
problems are to be also handled and
addressed while drawing a line so we
move towards the first algorithm which
which is incremental in nature it it
tries to reduce the computational burden
and tries to increase the speed of
computing the integer addressable pixels
locations and the first of the most
primitive algorithm you will find them
in some old books most than the current
books is called the digital differential
analyzer or digital difference analyzer
algorithm or it is popularly called the
DD a for computing the integer locations
of a line is based on in incremental
mething incremental algorithm and what
is basically done is the same equation
of the line y equals MX plus B is used
right and the M is obtained by the ratio
of the Y coordinates of the starting and
finishing point and also the x
coordinates starting finishing one that
ratio can be taken and we have
substituted that in place of M the
starting and finishing point x and y
coordinate to give you the M so that is
the equation of the line so based on
this equation we assume for the time
being that the value of x 1 is more than
X naught that means you start from the
left hand side of the screen and moving
towards the right the starting point is
less than the finishing point that is
that that is why X naught is less than X
1 or X 1 is more than X naught and DX by
dy which are nothing but the Y 1 minus y
naught as given in the expression of M
as Y 1 minus y naught assume that to be
dy and DX is nothing but X 1 minus X 2
we assume that DX is more than DUI
in absolute it basically means what the
value of M will be if DX is more than dy
and M is dy by DX this value of the
slope of the line is less than one we
assume this constraints now you need to
draw a line from anywhere to anywhere on
this screen that is true but what may
happen is it is not always the case that
you start from the leftmost point and go
to the right and the slope is less than
one and all that but there are other
case you mean you draw a line from here
to there from there all sorts of
positions are bound to happen but we
will tackle all the situation's later on
right now let us assume that from your
leftmost point to the right top point is
what you are drawing a line you are
selecting the addressable pixels from
left bottom to top right you need a good
Calgary them to get this into your
locations number one and the slope is
less than one it is not three zero two
okay so these are the two conditions we
will worry about the rest in a couple of
slides as we go ahead so come back to
the slide so we assume that X 1 is more
than X naught DX is greater than D Y
that means slope is less than 1 and we
will see that we can easily modify the
other situations to handle all the other
possible cases of drawing the line what
is the DDA algorithm ok as I said before
the DX is defined to the first four
statements of this algorithm here on the
right bottom of the screen gives the
initialization condition that is not the
loop DX is what I would I just said
sometime back X 1 minus X naught dy is y
1 minus y naught the slope of the line M
is given as dy by DX now since X 1 X
naught Y 1 y naught are integer
coordinates DX and dy will be also
integers but the ratio of two integers
is not guaranteed to be an integer
quantity in general it will be a
floating point
so just remember here that the value of
M or the slope of a line is going to be
my floating point number
Y is equal to Y naught that is starting
point we know it starts at X naught Y
naught and so what we do basically is
the you actually first draw the first
point X naught Y naught and then start
from you keep make an iterative
where you actually I have written this
in pseudocode not follow any syntax of
languages like C it could be Pascal like
or algo like so you make a loop from X
naught to X 1 okay so you start from the
x coordinates of the first point or
starting point and wind up and finish at
the finishing end point of the x
coordinates and at each point you draw
the lines the first point of course will
be Y is equal to Y not so you draw the
first point which is X not and round off
y naught which is nothing but the Y
naught itself then what you do is this
is incremental algorithm that is why it
is called you increment Y by the value n
you increment Y by the value M remember
Y is an integer but adding a floating
point number will actually return a
floating point value on the Y so what in
the next clip what will happen is in the
draw point command you need to you have
a you the round function will return
integer point is integer value of y and
that is what the drop point comment
basically illuminates let us assume that
this draw point is a very low level
library function we are given two
integer points X comma Y it draws a
point on the screen one addressable
point given by integer coordinates X
comma Y both are assumed to be integers
in the next calculation in each loop Y
becomes a floating point alright by the
round Y will return a integer so that is
what the N for loop so you see the for
loop now you have a floating point
addition and a round function ok we have
actually abolished the the incremental
algorithm has abolished the
multiplicative point multiplication that
is the small advantage so it will become
a little bit faster but not that much
because there are still two costly
functions within your for loop that for
loop has n number of steps n number of
steps depending upon the number of
points you have to draw on the screen X
naught takes one that the integer
difference and the too costly functions
one is the round operation another is
the floating point addition if we can
eliminate these two of course you cannot
eliminate both then you cannot draw a
line how to eliminate if you can
eliminate the round function which is
the cost list and still exist in the DDA
or an incremental algorithm and replace
the floating point arithmetic of
addition by an integer arithmetic which
will be several times faster and then
eliminate some of the round operation
you can almost imagine that for a line
to be drawn with several hundred points
on the screen the speed-up will be
tremendous many many times more then you
would like to spend then you would like
to have for a DDA type of an algorithm
which has floating point addition and
the round function so DDA is an entry
incremental algorithm it has speeded up
the algorithm a little bit but it is not
the most efficient one the most
efficient one which is going to discuss
now in the next few minutes left in this
class and then we will carry over it
over also to the next class because it
is a very important concept which you
must know is the method of the midpoint
criteria of drawing a line and it is
based on the idea of the concept
developed by bresenham's it is also
called the bresenham's line algorithm
which is integer based fully on integer
calculations integer based arithmetic is
what you use and is based on a criteria
of midpoint criteria for drawing right
so that is the net so the problems which
we had with DDA we will just define that
again that it uses a floating point and
around inside the loop so DDA in spite
of being incremental has this problem it
is still slower because of these true
drawbacks the drawbacks are the floating
point and the round function inside the
loop and we have to get rid of this of
course you can have to get up grid of
the round function the addition floating
point can be made integer you have to
add anyway you cannot escape that but
once you make the floating point
operation integer and throw of the round
operation the speed-up will be huge in
nature the other part is which we talked
in the DD algorithm is the octants
covering the 2d space we assume that you
are drawing a line from the left hand
side of the screen to the right hand
side the slope is less than 1 so if you
see all possible lines in the 2d space
and there are eight octants
each with an angle subtended of pi by 4
that means you are dividing the 2d space
into eight different octants we are
basically solving the algorithm for the
first octant only that means the slope
is less than 1 from 0 to 1 and if the
line lies in any of the other octants
that mean the slope is more than 1 or
the starting point is to the right and
the finishing point is the left that
means the the line could be in the
vii of tandoori mean third or fourth
then we will see what to do because
those are simple manipulations of
certain numbers which you have to
manipulate and get the environment done
solve it in the first octant space and
then draw the line back so we are
assuming that the line to be drawn for
the time being is drawn in the first
octant only that is one and we will see
how the other octants are also handled
okay so so we move on to the last few
minutes of this lecture on what is
called the bresenham's algorithm or I
will use the technical term of midpoint
line algorithm it is also an incremental
algorithm like the DDA algorithm but it
is based on integer arithmetic and we
assume that we are working only in the
first octant that means we are drawing a
line from the left hand side left bottom
to top right and the slope is less than
1 okay so that the first octant we had
seen the picture of eight octants
covering the entire 2d space so only the
first octant is what we are looking
through and once you are able to solve
that all the other seven octants also
will be handled so if we look back into
the slide and given the constraint that
we are drawing a line only in the first
octant given the current choice of a
pixel which could be the starting point
or any other point integer point at any
given point of iteration we will see
that the choice of the next pixel based
on the assumption the constraint of
first octant is only between two pixels
which we will be labeling as the east
pixel or the nos North East pixel so the
line states that given the choice of a
current pixel which one do we choose
next East or not east we will see what
do you mean by this East and North East
pixels as we go and look into the figure
well let us look into the couple of
equations today at least visualize this
configuration of East and North East and
understand the midpoint criteria at
least today the equation of a line is
given in this form parametric form is y
equals dy by DX multiplied by X plus B
where dy by DX is nothing but this slope
of the line dy by DX you know is given
by Y 1 minus y naught X 1 I think you
have noted down those equations by now
otherwise please note down dy is y 1
minus y naught the difference in Y
coordinates of the starting and
finishing points and the
is X 1 minus X not the difference in
x-coordinate of the starting and
finishing point of the line and so this
is the equation of the line we know that
okay now we rewrite the equation of this
line y equals dy by DX multiplied by X
this plus B as as a function of FX y
equal to zero it is possible to
manipulate and put all the terms on one
side and write the equation in the form
as X plus B y plus C equal to zero this
is also an equation of a line you can
actually find out the slope of this line
is going to be minus a by B okay so you
can visualize this this is another you
can easily manipulate this and this is
given in the bottom if you rewrite the
equation number one and try to put that
in the form of equation number 2 you
will rewrite as FX y as dy multiplied by
X minus DX multiplies by y plus BD x
equal to 0 do you please verify that
yourself right now that you can rewrite
equation number one and you are trying
to write it as in the form of equation
number two and in the process of doing
so you get this F XY equals d YX minus
DX y plus BX equal to 0 and this
equation is in the form of equation
number two now as FX y equal to zero
where the parameters of the line now
instead of being M and B only are a now
capital B of course you must be careful
but in small B and capital B in this
case which are different with two
different forms a is you can just simply
substitute this equation number two and
the one given at the bottom a is your D
Y which is given here B is minus D X
this is also given here remember this is
B is minus D X and small C will be
capital B multiplied by DX so these are
the three parameters of the line these
are the three parameters of the line
which is now we will use to and what is
the advantage of using this equation
well you can use this equation to find
out what is the mid where is the
midpoint of the next choice of the line
with respect to the equation of the line
so you can see that this is where I
describe what I mean by East or not east
pixel the two possible choices the two
possible choices
left to me let us assume from this
figure if you look that the black pixel
on the bottom left of this screen the
black pixel is the current pixel or it
could be the starting pixel also of
course if it is the starting pixel the
line will start from here so I have
taken a general case where the line you
have used this midpoint criteria to
iterate and got a few points already and
at a given given point of time
at any given stage of iteration this is
the current point which you have already
selected the next choice will be between
these two pixels not the east level as
red and East labeled as blue why this
has to be because of the constraint that
you are working on the first first
octant and the slope of the line is less
than one if the slope of the line is
more than what it would have been a
different case but since we do not
consider the situation right now the
choice is between east and northeast
only M is a midpoint between East and
naught is a bisector if you draw a line
from Eastern is to not least a vertical
line the midpoint is the bisector of the
line so what you try to do basically
with this equation of F X y equal to 0
is you evaluate the midpoint M with
respect to the equation of the line so
that is the criteria which is resisted
by bresenham's midpoint line algorithm
here and the M is between North East and
North East and you need to find out
whether this M is above the line or
below the line because that gives you
justification as you see in this figure
now if M is below the line the line is
closer to Northeast you will be choosing
the Northeast if this line was below M
which we will see another figure
similarly then of course you will choose
no East so the choice is now clear which
we just talked some time back that you
have to choose between two pixels
northeast or east this is if this is the
current pixel at any given point of time
the next choice is between North East
and East and you evaluate the midpoint
with respect to the equation of the line
and find out where is this midpoint
located and based on this criteria
choose East or North East so how do you
use the equation to find out whether the
midpoint is pillow or on the top of the
line what is the equation of the line
this was the equation of the line as
given in this form because we started
with y equals MA
plus B and then rewrote it in the form
FX y equal to 0 as in ax plus B y plus C
C is B times DX B is minus DX and a is
dy so this this form we got in the
previous slide you have written this
equation ordinary now what does this
meaning of this FX y equal to zero means
if you take a point which lie exactly on
this line if you take a point which lies
exactly on the line that means I select
an integer coordinate or any fractional
number in fact X comma Y and substitute
in this expression those coordinates of
a point which lie on the line are
exactly on the line anywhere any way
anywhere on the line but on the line is
important then if you substitute
assuming you know the other parameters
of the line like dy/dx capital B and so
on the value of FX Y will be equal to 0
that means the the points satisfy the
criteria that it is on the line and and
the value of the function is exactly
equal to 0 on the line whereas if you
substitute the values for a point which
is on top of the line you are on the
bottom you will get the value of the
function not equal to 0 on the line
function is equal to 0 on the top around
the bottom not equal to 0 but is not
equal to 0 gives you two different
conditions you can almost visualize from
the equation of the line that the value
of the F value of the function f if the
point is above the line assuming this to
be a line if the point is above the line
in 2d space then you will get a positive
or negative value and completely the
reverse will happen if the point is
below the line what let us look at this
figure and try to see this is the basic
concept here that if you substitute a
point which is below the line in this
case take the value of the coordinates
of M M is below the line if you
substitute the XY coordinates of this
point in and substitute in the equation
of F what basically will happen is this
term minus DX multiplied by Y will start
dropping from the case when the point if
the point M would have been exactly on
the line if the point M is below the
line this negative quantity will start
reducing and force the value of F to
grow positive so the value of F will be
positive you just have to remember that
the value of f becomes positive if the
point is below the line
if the point is above the line assume a
scenario of M goes above the line or
take the value of of the XY coordinates
from the naughty substitute on the value
of M what will happen is this DX
multiplied by Y term will grow more
forcing the value of F to be negative so
this is the main criteria that the value
of F becomes positive for a point below
the line and a fund poppin above the
line the value will be negative negative
on top of the end positive y on the
below the line this is a this you can
visualize that the function is equal to
0 exactly on the line it is negative and
positive the entire two dimensions based
on this screen is split into two offs
where exactly on the line you have all 0
values anything on top you have negative
anything on the bottom we have positive
positive below the line negative on top
of the line exactly in the middle so you
are dividing the space equally into two
different halves positive of a negative
half and that is where and that is the
concept which is used to evaluate the
midpoint now you can visualize that if M
is below the line you will get F
function to be positive if M is on top
of the line you have the value to be
negative I love the line and so just
looking at the sign of F itself will
tell you whether M is on top or B the
line and that sufficient for you to tell
whether you choose East or not T so that
is the criteria which we say and we stop
here saying that this is the Metron
criteria we will start from here in the
next hour and move towards forming the
algorithm but the midpoint criteria is
the following I repeat again if you look
into the slide the criteria for
bresenham's mid point and algorithm is
evaluate the midpoint M with respect to
the equation of the line so all points
on the line will give you a function
value zero points below the line as this
figure shows for the M will give
positive values points on top of the
line will give negative values look into
the sign of F and decide decide whether
the point is below or top of the line so
in this figure as you see here since M
is below the line if you substitute M
into the equation f you will get a
positive sign and that guarantee the
sign of the the sign of the function f
is itself a sufficient clue to tell you
whether the point is closed the point is
below or above the line or in other
words the line is closer to Northeast or
east
in this case since M is below the line
the line will be closer to Northeast so
you will select the North East pixel as
your next iteration and the case is
there where the point is below the line
f is positive the reverse would have
happened if M we have gone on top of the
line M is above the line F would have
been negative and the point would have
the line would have passed between m and
E or it is closer to these pixel in in
this case you would have considered the
East pixel okay so this is the criteria
the sort of a boolean logic look into
the sign of F positive negative positive
take one tation of choosing Eastern
North East and negative you choose the
other one sort of a bipolar logic or a
boolean logic and that gives you a very
good algorithm to select the line that
part is done but of course we have not
seen where the integer arithmetic is
coming from where the integer arithmetic
is coming out probably round function
will go away the choice criteria once it
is clear we will start from here in the
next class and see start exactly from
this midpoint criteria and move forward
and see how the integer algorithm is
brought on with the help of this
midpoint criteria the choice becomes
very easy between East and North East
how the other octants also are taken
into account and that completes the
entire line drawing algorithm we will
move to the next lecture and see and of
course then we move ahead with curves
equations of curves circles and ellipses
thank you very much
[Music]
Oh