The Cartesian intersect equation for a straight line is y = mx +b --------------(1)

Consider two end points of a line segment (x1,y1) and ( x2,y2)

m =( y2-y1)/(x2-x1) --------------(2)

and b = y1-m *x1. --------------(3)

For any x interval dx along line we can compute the corresponding y interval dy

dy = m * dx --------------(4)

similarly we can obtain the x interval dx corresponding to a specified dy as

dx = dy/m--------------(5)

these two equation form the basis for determine deflection voltage in analog devices .

for line with slop magnitude |m| <1, dx can be set proportional to a small horizontal voltage and
corresponding vertical deflection voltage is set proportional to dx with dy = m * dx

Similarly

For |m|>1

We can obtain dx = dy/m

For m =1, dy =dx and horizontal and vertical deflections voltages are equal.
On raster systems, lines are plotted with pixels, and step size in horizontal and vertical directions are
constrained by pixel separations.

DDA algorithm
The Digital Differential Analyzer is a scan conversion line algorithm based on calculation dx or dy
using

dy = m* dx and dx = dy/m

We sample the line at unit interval in coordinate and determine corresponding integer values
nearest the line path for the other coordinate

Consider first line with positive slop

If slop is less than or equal to 1, we sample at unit x interval ( dx =1) and compute each successive y
value as

Yk+1 = yk +m --------------(6)

, where k takes integer values starting from 1 , for the first point, and increases by 1 until final end is
reached.

Since m can be any real number between 0 and 1 , the calculated y values must be rounded to the
nearest integer.

Next

Consider line with a positive slop greater than 1, we reverse role of x and y. That is we sample at
unit y interval (dy =1) and calculate each corresponding x value as

Xk+1 = Xk + 1/m--------------(7)

Both these equations (6) and (7)

Yk+1 = yk +m

Xk+1 = Xk + 1/m

Are based on the assumption that lines are to be processed from left endpoint to right endpoint.

If processing is reversed, so that the starting point is at right , the either we have

dx =-1

that is yk+1 = yk –m --------------(8)

or ( when slope is greater than 1) dy =-1 with Xk+1 = Xk –1/m. --------------(9)

Equation (6) to (9) can be used to calculate pixel positions along a line with negative slop.

If the absolute value of the slop is less than 1( |m| <1) and start end is left , we set dx = 1 and
calculate the y values with the equation (6).

If the absolute value of the slop (|m| <1) and starts end is right , we set dx =-1 and calculate the y
values with the equation (8).

Similarly when the absolute value of the negative slop is greater than 1 (|m|>1) and start end is lt
we set dy =1 and calculate the y values with equation (7).

Similarly when the absolute value of the negative slop is greater than 1 (|m|>1) and start end is
right, we set dy =-1 and calculate the y values with equation (9).

Summarization of DDA Algorithm

1. Accept (input) two endpoint pixel positions.

2. Calculate the horizontal and vertical difference between two endpoint positions and are
assigned to the parameters dx and dy respectively.
3. The difference with greater magnitude determines the value of parameter steps
4. Starting with pixel position (xa,xb).
5. Loop through this process through steps times.
6. If the magnitude of dx is greater than the magnitude of dy ( that is |m| <1), and xa is less
than xb ( left to right) , the values of the increment in the x and y directions are 1 and m
respectively . If greater change in the x direction , but xa is less than xb (right to left ), then
the decrements -1 and -m are used to generate each new point on the line. Otherwise we
use unit increment(or decrement) in the y direction and an x increment ( or decrement of
1/m).

DDA Algorithm

A line connects two points. It is a basic element in graphics. To draw a line, you need two
points between which you can draw a line. In the following three algorithms, we refer the one
point of line as X0,Y0 and the second point of line as X1,Y1.

Digital Differential Analyzer (DDA) algorithm is the simple line generation algorithm which is
explained step by step here.

Step 1 − Get the input of two end points (X0,Y0) and (X1,Y1).

Step 2 − Calculate the difference between two end points.

dx = X1 - X0

dy = Y1 - Y0

Step 3 − Based on the calculated difference in step-2, you need to identify the number of
steps to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y
coordinate.
 if (absolute(dx) > absolute(dy))

Steps = absolute(dx);

else

Steps = absolute(dy);

Step 4 − Calculate the increment in x coordinate and y coordinate.

Xincrement = dx / (float) steps;

Yincrement = dy / (float) steps;

Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and
complete the drawing of the line.

for(int v=0; v < Steps; v++)

x = x + Xincrement;

y = y + Yincrement;

putpixel(Round(x), Round(y));

Advantages

*It is faster method for calculating pixel positions than the direction use y=mx+b
*It eliminates the multiplications in y= mx +b so that appropriate increments are applied I the x or y
direction to step to pixel positions along the line path.

Disadvantages

*he accumulation of round off error in successive additions of floating point increment can cause the
calculated pixel positions to drift away from true line path for long line segment.
*Further the rounding operations and floating point arithmetic are still time-consuming.

Bresenham’s Line Generation

The Bresenham algorithm is another incremental scan conversion algorithm. The big advantage of
this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and
at each step choose between two different y coordinates.
For example, as shown in the following illustration, from position (2, 3) you need to choose
between (3, 3) and (3, 4). You would like the point that is closer to the original line.
At sample position xk+1, the vertical separations from the mathematical line are labelled
as dupper and dlower.

From the above illustration, the y coordinate on the mathematical line at xk+1 is y = m(xk+1) + b
So, dupper and dlower are given as follows −
dlower=y−yk
=m(xk+1)+b−yk
and
dupper=(yk+1)−y
=yk+1−m(xk+1)−b
You can use these to make a simple decision about which pixel is closer to the mathematical line.
This simple decision is based on the difference between the two pixel positions.
dlower−dupper=2m(xk+1)−2yk+2b−1
Let us substitute m with dy/dx where dx and dy are the differences between the end-points.
dx .(dlower−dupper)=dx .(2dy/dx(xk+1)−2yk+2b−1)
= dx . (2 . (dy/dx) xk +2.dy/dx -2yk +2b -1)
=2 dy. xk +2 dy – 2yk .dx +2b . dx – 1.dx
=2dy.xk−2dx.yk+2dy+dx(2b−1)
=2dy.xk−2dx.yk+C
So, a decision parameter Pk for the kth step along a line is given by −
Pk=dx(dlower−dupper)
=2dy.xk−2dx.yk+C
The sign of the decision parameter Pk is same as the sign of ( dlower – dupper) since dx >0.
Pk is the same as that of dlower−dupper. C= 2dy + dx (2b-1) which is independent of pixel position.
If Pk is negative, then choose the lower pixel, otherwise choose the upper pixel.
Remember, the coordinate changes occur along the x axis in unit steps, so you can do everything
with integer calculations. At step k+1, the decision parameter is given as −
Pk+1=2dy.xk+1−2dx.yk+1+C
Subtracting Pk from this we get −
Pk+1−Pk=2dy(xk+1−xk)−2dx(yk+1−yk)
But, xk+1is the same as (xk)+1.
So
pk+1=pk+2dy−2dx(yk+1−yk)
Where, yk+1–yk is either 0 or 1 depending on the sign of Pk.
The first decision parameter p0 is evaluated at (x0,y0) is given as −
p0=2dy−dx
( pk = =2dy.xk−2dx.yk+ 2dy + dx (2b-1)

p0 =2dy.x0−2dx.y0+2dy + dx (2b-1)
=0 +0 +2dy +2b.dx-dx
= 2dy +2(y0-( dy/dx).x0).dx –dx
=2dy –dx.)

Now, keeping in mind all the above points and calculations, here is the Bresenham algorithm for
slope m < 1

Step 1 − Input the two end-points of line, storing the left end-point in (x0,y0).
Step 2 − Load (x0,y0) into frame buffer and Plot the point (x0,y0).

Step 3 − Calculate the constants dx, dy, 2dy, and (2dy – 2dx) and get the first value for the decision
parameter as −

p0=2dy−dx

Step 4 − At each Xk along the line, starting at k = 0, perform the following test −

If pk < 0, the next point to plot is (xk+1,yk) and

pk+1=pk+2dy

Otherwise,

Plot the point (xk+1,yk+1),

pk+1=pk+2dy−2dx

Step 5 − Repeat step 4 (dx – 1) times.

For m > 1, find out whether you need to increment x while incrementing y each time.

After solving, the equation for decision parameter Pk will be very similar, just the x and y in the
equation gets interchange.

Circle Generating Algorithms

The circle is defined as the set of points that are all at a given distance r from center position (xc,yc).

So (x-xc)2 + (y-yc)2 =r2 . BY stepping along the x axis in unit steps from xc-r to xc +r and calculating
the corresponding y values at each position as

y = yc +- sqrt(r2 –(x-xc)2)

The limitations of this method are :it involves more computation at each step. Also the space
between plotted pixel positions is not uniform.

Computation can be reduced by symmetry of circles. The shape of circle is similar in each quadrant .
So the circle sections 3 and 4 quadrants can be obtained from the sections in the first and second by
symmetry of x-axis.

Taking the advantage of symmetry in this way, we can generate all pixel positions around a circle by
calculating only the points within the sector from x=0 to x=y.

Midpoint Circle Algorithm

As in the raster line algorithm, we sample at unit intervals and determine the closest position to the
specified circle path at each step. For a given radius r and screen center positon (xc,yc), calculate the
pixel positions around a circle path centered at origin (0,0). Then each calculated position (x,y) is
moved to its proper screen position by adding xc to x and yc to y.

Along the circle section from x = 0 to x=y in the first quadrant the slop of curve varies from 0 to -1.

Therefore, we can take unit steps in positive x direction over this octant and use a decision
parameter to determine which of the two possible y positions is closer to the circle path at each
step. Positions in the other seven octant are then obtained by symmetry.

To apply the midpoint method , we define a circle function

fcircle(x,y) = x2 +y2 –r2

Figure shows the midpoint between the two candidate pixels at sampling position xk+ 1.

Assuming we have just plotted the pixel at (xk , yk), we next need to determine whether the pixel at
positon (xk+1,yk) or one at position (xk+1, yk -1) is closer to the circle.

Our decision parameter is the circle function , fcircle(x,y) = x2 +y2 –r2 , evaluated at the midpoint
between these two pixels:

pk = fcircle(xk +1,yk - ½)

pk = (xk+1)2 + (yk-½)2 –r2

pk =(xk+1)2 + (yk)2 -.yk –(1/4) –r2

If pk <0 , this midpoint is inside the circle and the pixel on the scan line yk is closer to the circle
boundary .

Otherwise midpoint is outside or the circle boundary, we select the pixel on scanline yk-1.
The circle function at sampling position xk+1 +1 =xk +2

Pk+1 = fcircle(xk +1 +1,yk+1 -½)

= [ (xk+1) +1]2 +( yk+1 – ½)2 – r2

= (xk+1)2 + 2(xk +1) +1+ (yk+1)2 – 2.1/2 . (yk+1) –(1/4) –r2

Pk+1 – pk = (xk+1)2 + 2(xk +1) +1+ (yk+1)2 – (yk+1) –(1/4) –r2 - ((xk+1)2 + (yk)2 -.yk –(1/4) –r2 )

=(xk+1)2 + 2(xk +1) +1+ (yk+1)2 – (yk+1) –(1/4) –r2 - (xk+1)2 - (yk)2 +yk +(1/4) +r2

= 2(xk +1) + (yk+1)2 - (yk)2 –( (yk+1) - .yk ) +1

= pk + 2xk +1 + (yk+1)2 - (yk)2 –( (yk+1) - .yk ) +1 since (2.xk +1 = 2(xk +1) = 2xk +2)

yk+1 is either yk or yk-1 depending on the sign of pk

If pk is negative (pk <0) , yk+1 = yk and increments for pk+1 is 2xk +1 +1

If pk is positive (pk>0) , yk+1 = yk-1 and increments for pk+1 is 2xk +1 +1 – 2yk+1

( since 2yk+1 = 2* ( yk -1) =2yk – 2 )

At start position (0,r) these two terms have the values 0 and 2r respectively. Each successive value is
obtained by adding 2 to the previous value of 2x and subtracting 2 from the previous value of 2y.

At start position (x0,y0) = (0,r)

pk = fcircle(xk +1,yk - ½)

p0 = fcircle(0 +1,r - ½)

p0 = (0+1)2 + (r-½)2 –r2

=(5/4) –r

= 1-r

Mid Point Algorithm

Step 1 − Input radius r and circle center (xc,yc)and obtain the first point on the circumference of the
circle centered on the origin as
(x0, y0) = (0, r)
Step 2 − Calculate the initial value of decision parameter as
P0= 5/4 – r
Step 3 − At each xk position starting at k=0, perform the following test −

If PK < 0 then next point on circle centered on (0,0) is (XK+1,YK) and

PK+1 = PK + 2XK+1 + 1
Else
PK+1 = PK + 2XK+1 + 1 – 2YK+1

Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2.

Step 4 − Determine the symmetry points in other seven octants.

Step 5 − Move each calculate pixel position (X, Y) onto the circular path centered on (xc,yc)and plot
the coordinate values.
X = X + X C, Y = Y + Y C
Step 6 − Repeat step-3 through 5 until X >= Y.

Character Generation

A typeface is a design that defines the overall look of characters. Arial and Times New Roman are
examples of typeface.

a typeface (also known as font family) is a set of one or more fonts each composed of glyphs that
share common design features. Each font of a typeface has a specific weight, style, condensation,
width, slant, italicization, ornamentation, and designer or foundry (and formerly size, in metal fonts).

Typeface or font can be divided into two family serif and sans-serif.

Serif type has small lines or accents at the ends of the main character strokes, while sans-serif type
does not have accents

Serif type is more readable, that is, it is easier to read in longer blocks of text. But individual
characters in sans-serif type are easier to recognize and so sans-serif is more legible, good for
labelling and short heading.

A Serif font has “feet” or added extensions like the top and bottom of the Times New Roman, which
is serif font example in the illustration.

The word “sans” (in French) means without. So sans serif would be without the serifs or “feet”. A
classic example of a sans serif font would be Arial.

Serif: a small line, structural detail or flourish at the extremities of a type character.

A simple method for representing the character shapes in a particular typeface(font) is to use
rectangular grid patterns., which is known as bitmap font or bitmapped font. Bit map fonts are the
simplest to define and display. The character grid only mapped to a frame buffer position and
require more space , because each variation like size and format must be stored in a font cache.
Outline fonts require less storage since each variation does not require a distinct font cache. But it
take more time to process the outline fonts, because they must be scan converted into frame buffer.

A scalable font is one in which the outlines of each character are geometrically defined. . An outline
font is scalable because, given a geometrical description of a typeface, a printer or other display
device can generate the characters at any size (scale).Sans-serif: a type character without the above.

A bitmap font is a font with jagged edges when enlarged,

instead of a scalable font where no matter what the size will
look the same. Bitmap fonts are comprised of several dots that
make up a single character.

The picture above is an example of scalable font vs. a bitmap

font. As you zoom in on Computer Hope, there is no
degradation in quality with a scalable font. However, it's the
complete opposite when we zoom into a bitmap font.

Difference between outline font and bitmapped font.

There are basically two types of graphics being used by designers - One is the bitmap which consists
of pixels which are also called raster and the other is the vector graphic which consists of paths. The
vector images base its operation and usability on mathematical formulas to calculate the paths and
points which translate into a visible image while the bitmap image is based on grid. These grids
constitute of pixel of different shade and different color
Bitmap fonts are faster and easier to use in computer code, but non-scalable, requiring a separate
font for each size. ... Although all types are still in use, most fonts seen and used on computers are
outline fonts. Fonts are designed and created using font editors.

Bitmap images are most used for creating non-printable designs. This implies any design that you
don't intend printing such as web pictures, a computer graphic, a banner or flyer that won't be
printed.

What are Vector images used for?

Vector designs are usually used to create images which you intend printing out. This includes logos,
package design, designs on t-shirts etc.

What are Vector graphics or images?

Vector graphics are graphic design which makes used of mathematical formulas in analysing a series
of points which forms an image, this image is composed of lines and shapes connected along a path.
Vector images use geometric formulas in representing images. Vector graphics are often seen in
fonts, logos, line art. A vector image has constant mathematical statements which enables it to
appear smooth at any given size. It does not get blurry when stretched. Programs which can be
used to create and manipulate a vector image are called draw programs. Drawing programs such as
Adobe Illustrator, Macromedia Freehand, CorelDraw, CAD systems, Quark, InDesign and other page
layout applications including animation software's all utilize and manipulate vector graphics.
Applications such as Adobe Photoshop and CorelDraw can give out both vector and bitmap graphics.
Vector images look better when displayed on monitors or high-resolution printers. Logos and types
are typical examples of images that are well suited for the vector image format.

What are Bitmap graphics or images?

Bitmap graphics is a way of representing graphical images which are made up of pattern of dots.
Bitmap images are often called raster images. Bitmap graphics are made up of grid of individual
pixels having different colors. The quality of the pixel count determines the quality of the image, if
the pixel count happens to be high that means that the image will be of high photographic quality,
with an excellent shading and radiation. A bitmap image should not be over expanded or enlarged to
avoid making the edges blurry.Bitmap graphics are best for images which require a wide range of
color composition while vector images are better for images that require a few areas of solid color.
You can use vector to create a nice t-shirt design, you can do that using vector so that it won't be
jagged, you can still use bitmap but ensure its resolution is not less than 300.