Introduction to Computer Graphics Algorithms

    Several algorithms are used in the creation of the computer graphics application. These are already existing algorithms which are used to implement most of the graphic features . The algorithms are:

1. Bresenham’s Line Drawing Algorithm
2. Bresenham’s Circle Drawing Algorithm
3. Midpoint Ellipse Drawing Algorithm
4. Flood Fill Algorithm

Bresenham’s Line Drawing Algorithm

Bresenham's line algorithm is an algorithm that determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics.The line is drawn between two points (x0, y0) and (x1, y1), where these pairs indicate column and row, respectively, increasing in the down and right directions.

Illustration
of the result of Bresenham's line algorithm.

 

ALGORITHM

•     Input the two line endpoints and store the left endpoint in (x0, y0).
•     Load (x0, y0) into the frame buffer; that is plot the first point.
•     Calculate constants ∆x, ∆y, 2∆y, and 2∆y - 2∆x, and obtain the starting value for the decision parameters as               

                   p0 = 2∆y - ∆x

•     At each xk along the line, starting at k=0,perform the following test:
•     If pk <0, the next to plot is (xk + 1,k) and

                         Pk+1 = pk + 2∆y

•     Otherwise, the next point to plot is (xk + 1,yk + 1) and

                         Pk+1 = pk+ 2∆y – 2∆x.

•    . Repeat step 4 ∆x times  

Bresenham’s Circle Drawing Algorithm

 
 


Algorithm

•     Input values of radius r and circle centre ( x0, y0) and obtain the first pt on the circumference of a circle centred on the origin as ( x0, y0)= (0, l)
•     Calculate the initial decision parameter as d= 3-2r
•     For each pixel position (xi, yi),perform:
•     If di < 0, the next point is (xi  + 1 , yi) and di + 1 = di + 4xi +6
•     Otherwise the next point along the circle is (xi+1, yi -1)and  

                            di + 1 = di + 4 (xi - yi) + 10

•     Determine symmetry points on the other 7 octants
•     Move each calculated pixel position (x, y) onto the circular path centred on (xa , y a) and plot the co-ordinate values.

        x = x + xa
        y = y + ya

•     Repeat step 2 to 5 until x>=y

Midpoint Ellipse Drawing Algorithm

This has the following properties.

   <0    if (x, y) is inside the boundary    ellipse (x, y)       =0    if (x, y) is on the boundary
   >0    if (x, y) is outside the boundary

Thus ellipse function serves as the decision parameter for the algorithm.

So we move out region 1 whenever 2ry2x ≥ 2rx2y

Algorithm

1.    Input rx, ry , and ellipse centre (xc,yc) and obtain the first point on an ellipse centred on the origin as (x0, y0) = (0, ry)
2.    Calculate the initial value of the decision parameter in region 1 as
        p10 = r2y - r2xry + 1/4r2x
3.    At each xk position  in region 1, starting at k=0, perform the following test:
       If p1k < 0, the next point along the ellipse centred on (0, 0) is (xk+1, yk) and
       p1k+1 = p1k + 2r2yxk+1 + r2y
       otherwise, the next point along the circle is (xk+1,yk-1) and
      p1k+1 = p1k + 2r2yxk+1 - 2r2xyk+1 + r2y
        with 2r2yxk+1 = 2r2yxk + 2r2y ,  2r2xyk+1 = 2r2xyk - 2r2x
        and continue with until 2r2yx ≥ 2r2xy
4.    Calculate the initial value of the decision parameter in the region 2 using the last point (x0,y0) calculated in region 1 as
       p20 = r2y(x0+1/2)2 + r2x(y0-1)2 – r2xr2y
5.    At each yk position in region 2 starting at k = 0, perform the following test:
       if p2k > 0, the next point along the ellipse centred on (0,0) is (xk,yk-1) and
      p2k+1 = p2k - 2r2xyk+1 + r2x
      Other wise , the next point along the circle is (xk+1,yk-1) and
       p2k+1 = p2k  +  2r2yxk+1- 2r2xyk+1 + r2x
       using the same incremental calculation for x and y as in region 1
6.    Determine symmetry points in the other three quadrants.
7.    Move each calculated pixel position (x, y) on to the elliptical path centred on (xc,yc) and plot the coordinated values:
       x = x + xc, y = y + yc
8.    Repeat the steps for region 1 until 2r2yx ≥ 2r2xy

Flood Fill Algorithm

The purpose of Flood Fill is to color an entire area of connected pixels with the same color. The Flood Fill algorithm is also sometimes called Seed Fill: First a seed id is planted (the pixel where you start), and, recursively, more and more seeds are planted around the original seed if those pixels have the correct colour. Each new seed is responsible for coloring the pixel at its position and testing for new pixels around it that has to be coloured.

Algorithm

        floodfill4 ( x + 1 , y, fillcolor , oldcolor );
        floodfill4 ( x - 1 , y, fillcolor , oldcolor );
        floodfill4 ( x , y + 1, fillcolor , oldcolor );
        floodfill4 ( x , y - 1, fillcolor , oldcolor );

The algorithm uses recursive calls to itself to paint the inside of a region. Since we are using a four point flood fill algorithm it checks the four neighbouring pixel positions of the current mouse location. It is usually used when an area defined with multiple colour boundaries

•     Start at a point inside a region.
•     Replace a specified interior colour (old colour) with fill colour.
• Fill the 4−connected region until all interior points being replaced.

Related Articles

Implementing Computer graphics through C application
Introduction to Basic Principles of Animation