COMPUTER GRAPHICS (XCS 354) UNIT II

1. Explain in detail about the DDA scan conversion algorithm? 
The digital differential analyzer is a scan conversion algorithm based on calculation either y or x using the following equations
y= m x
x = y / m
Sample the line at unit intervals in one coordinate and determine corresponding integer values nearest the line path for the coordinates Sample at X intervals ( x = 1) and compute each successive Y value as
Yk+1 = Yk + m
For lines with positive slope greater than 1, reverse the roles of X and Y. Sample at unit Y intervals ( y = 1)and calculate each successive X value as Xk+1 = Xk+ 1/m
Algorithm 
Step 1: Input the line endpoints and store the left endpoint in (x1, y1) and right endpoint in (x2, y2)
Step 2: Calculate the values of x and y using x =xb – xa, y= yb – ya
Step 3: if the values of x > y assign values of steps as x otherwise the values of steps as y
Step 4: Calculate the values of X increment and Y increment and assign the value x= xa and y = ya
Step 5: for k=1 to steps do
X = X + X increment
Y= Y + Y increment
Putpixel(ceil(x), ceil(y),15)
Step 6: End

2. Explain Bresenhams line drawing algorithm? 
In Bresenham’s approach the pixel position along a line path are determined by sampling unit X intervals. Starting from the left end point(X0, Y0)of a given line we step to each successive columns and plot the pixel whose scan line Y-value is closest to the line path.Assuming the Kth step in process, determined that the pixel at (Xk, Yk)decide which pixel to plot in column Xk+1.The choices are (Xk+1, Yk) and (Xk+1, k+1)

Algorithm 
Step 1: Input the line endpoints and store the left endpoint in (X0, Y0)
Step 2: Load (X0, Y0) in to the frame buffer
Step 3: Calculate constants x, y, 2 y, -2 x, and obtain the decision parameters as P0 = 2 y – x
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+2 y
Otherwise, the next point to plot is (Xk+1, Yk+1) and
Pk+1 = Pk+2 y - 2 x
Step 5: Repeat step 4 x times


3. Explain Midpoint Circle algorithm? 
Algorithm 
Step 1:Input radius r and circle center(Xc, Yc)and obtain the first point on the circumference of a circle centered on the origin as (X0, Y0) = (0, r)
Step 2: Calculate the initial values of the decision parameter as P0 = 5/4 – r
Step 3: At each position starting at k perform the following test:
If Pk < 0, the next point to plot is (Xk+1, Yk) and
Pk+1 = Pk+2 Xk+1 + 1
Otherwise the next point is (Xk+1, Yk+1) and Pk+1 = Pk+2 Xk+1 + 1- 2 Yk-1
Step 4: Determine symmetry points in the other seven octants
Step 5: Move each pixel position(X, Y) onto the circular path centred on (Xc, Yc) and plot the coordinate values as X = X + Xc Y = Y + Yc
Step 6: Repeat steps 3 through until X>=Y Pk + 1= Pk + 2 Y
Other wise, the next point is (Xk+1, Yk+1) and Pk + 1= Pk + 2 Y - 2 X
Step 5: Repeat steps 4 X times

4. Explain Ellipse generating Algorithm? 
Algorithm 
Step 1:Input radius rx, ry and ellipse center(Xc, Yc)and obtain the first point on the circumference of a circle centered on the origin as (X0, Y0) = (0, ry)
Step 2: Calculate the initial values of the decision parameter in region 1 as
P10 =ry2 - rx2 ry+1/4 rx2
Step 3: At each position starting at Xk position in region 1,starting at k = 0, perform the following test:
If Pk < 0, the next point to plot is (Xk+1, Yk) and 22 P1k+1 = P1k+2 ry Xk+1 + ry
Otherwise the next point is (Xk+1, Yk-1) and 222P1k+1 = P1k+2 ry Xk+1 - 2ry Yk+1 + ry
Step 4: Calculate the initial values of the decision parameter in region 2 as 222222 P20 =ry (X0+1/2)+ rx (Y0 – 1)-rx ry
Step 5: At each position starting at Yk position in region 2,starting at k = 0,
perform the following test:
If Pk > 0, the next point to plot is (Xk, Yk-1) and 22 P2k+1 = P2k- 2 ry Yk+1 +rx
Otherwise the next point is (Xk+1, Yk-1) and 222 P2k+1 = P2k- 2 ryYk+1 -2rx Yk+1 +rx
Step 6: Determine symmetry points in the other three octants
Step 7: Move each pixel position(X, Y) onto the circular path centred on (Xc, Yc) and plot the coordinate values as X = X + Xc Y = Y + Yc 22
Step 8: Repeat steps for region 1 until 2 ry X>=2 ry Y

5.Explain Boundary fill Algorithm? 

• If the boundary is specified in a single color, the fill algorithm proceeds outward pixel-by-pixel until the boundary color is encountered. This is called boundary fill algorithm 
• The boundary fill procedure accepts as input the coordinates of an interior point (x, y), a fill color, and a boundary color. 
• Starting from (x, y), the procedure tests the neighboring positions to determine whether they are boundary color. 
• If not, they are painted with the fill color, and the neighbors are tested. 
• This process continues until all pixels up to the boundary color for the area have been tested 

Two methods 
4- connected 
• 4 neighbouring points are connected
8-connected 
• correctly fill the interior of the area defined program
void boundaryfill( int x, int y, int fill, int boundary)
{
int current;
current = getpixel (x, y);
if ((current != boundary) &&(current != nil)
{
setColor ( fill);
setPixel ( x, y);
boundaryfill (x+1, y, fill, boundary);
boundaryfill (x-1, y, fill, boundary);
boundaryfill (x, y+1, fill, boundary);
boundaryfill (x, y-1, fill, boundary);
}
}