Computer graphics part 3

[aayush_005]

Breshenham’s Line Algorithm:

An accurate and efficient raster line-generating algorithm, developed by Bresenham, scan converts lines using only incremental integer calculations that can be adapted to display circles and other curves. The vertical axes show scan-line positions, and the horizontal axes identify pixel columns. To illustrate Bresenham’s approach, we first consider the scan-conversion process for lines with positive slope less than 1. Pixel positions along a line path are then determined by sampling at unit x intervals. Starting from the left end-point(x0,y0) of a given line, we step to each successive column(x position) and plot the pixel whose scan-line y value is closest to the line path.
< FIGURE >

The above figure demonstrates the kth step in this process.
Assuming we have determined that the pixel at (xk,yk) is to be displayed, we next need to decide which pixel to plot in column xk+1. Our choices are the pixels at positions (xk+1, yk) and (xk+1,yk+1).

At sampling position xk+1, we label vertical pixel separations from
the mathematical line path as d1 and d2 (fig.3-8). The y coordinate on the mathematical line at pixel column position xk+1 is calculated as

y = m(xk+1)+b
then
d1 = y-yk
=m(xk+1)+b-yk
and
d2 = (yk+1)-y
=yk+1-m(xk+1)-b
The difference between these two separations is

d1-d2 = 2m(xk+1)-2yk+2b-1
A decision parameter pk for the kth step in the line algorithm can be obtained by rearranging above equation so that it involves only integer calculations. We accomplish this by substituting m=y/x, where ∆y and ∆x are the vertical and horizontal separations of the endpoint positions, and defining:

pk=∆x(d1-d2)
= 2∆y. xk - 2∆x . yk + c  (1)
the sign of pk is the same as the sign of d1-d2, since ∆x>0 for our example. Parameter c is constant and has the value 2∆y + ∆x(2b-1), which is independent pixel at yk is closer to the line path than the pixel at yk+1, then decision parameter pk is negative. In that case, we plot the lower pixel; otherwise, we plot the upper pixel.

Co-ordinate changes along the line occur in unit steps in either the x or y directions. Therefore, we can obtain the values of successive decision parameters using incremental integer calculations. At step k+1, the decision parameter is evaluated from equation (1) as

pk+1= 2∆y. xk+1 - 2∆x . yk+1 + c

Subtracting the equation (1) from the above equation, we have
pk+1-pk= 2∆y( xk+1 – xk) - 2∆x(yk+1 – yk)
But xk+1=xk + 1, so that pk+1=pk+2∆y-∆x(yk+1-yk)
Where the term yk+1 – yk is either 0 or 1, depending on the sign of parameter pk. This recursive calculation of decision parameters is performed at each integer x position, starting at the left co-ordinate end point of the line. The first parameter, p0 is evaluated from the equation (1) at the starting pixel position (x0, y0) and with m evaluated as ∆y/∆x.

p0=2y-∆x
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 parameter as p0=2∆y-∆x.
 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.
 Repeat step 4 ∆x times.





Circle Generators:

In certain classes of application, particularly those involving the display of mechanical engineering parts, circles and circular arcs are frequently displayed. A number of incremental methods have been invented to plot circles and arcs. These methods are valuable because most displays have none for circle drawing. Where line generation hardware exists, incremental circle generators can be used to compute the endpoints of consecutive short lines segments. Circle generators are capable of generating closely spaced dots.

The following algorithm is used for circle generation. Circle generating algorithm is a variant of DDA methods.

Circle-Generating DDA:

The principle of the DDA can be extended to other curves as one such curve is the circular arc. The differential equation of a circle with center at the origin can be written as below.

dy / dx = - x / y;

This suggests that we can implement a circle-plotting DDA by using - x and y as incrementing values.

X n+1 = x n + y n.
Y n+1 = y n + x n.

This involves computing the incrementing values afresh at each step, but the computation can be reduced to a pair of shifts and a complement operation if  is chosen to be a negative power of 2. To prevent the spacing of consecutive points from exceeding one screen unit,  should equal to 2 –n, where

2 n-1 <= r < 2 n

and r being the radius of the circle.

Each step is made in a direction perpendicular to a radius of the circle. Each point is therefore slightly farther from the center than the one before. This problem is easily solved by using x n+1 rather than x n to compute
y n+1.


X n+1 = x n +y n.
Y n+1 = y n - x n+1.

This solution is based on the following reasoning.

The equations,
X n+1 = x n + y n
Y n+1 = y n + x n can be written in matrix form as below.

[x n+1 y n+1] = [x n y n] [1 -   1].
The determinant of the matrix on the right does not equal unity by 1 + 2. This implies that the curve will spiral out. If the determinant can be reduced to unity, the curve will close. We achieve this effect by modifying the matrix as following:

[x n+1 y n+1] = [x n y n] [1 -   1-].

Circles drawn by the DDA need not be centered on the origin. Instead the displacements in x and y from the circle’s center of the point (xm, ym) are used in determining (xn+1, yn+1). This algorithm is well suited to hardware implementations.

If is feasible to construct a DDA that draws an exact circle, using below equations.

X n+1 = x n cos θ + y n sin θ,
Y n+1 = y n cos θ - x n sin θ.

Since θ is generally small, values of cos θ and sin θ are relatively easy to compute and are then constant for any particular circle radius. This pair of equations can therefore be used to advantage if multiplications can be performed inexpensively.

Several other circle-generating methods have been extended to plot wider class of curves. These methods may be useful in specific cases, but they lack the generality and the power of some of the more recently developed curve generation methods.





Midpoint circle Algorithm:

In this algorithm the user has to give the radius r and screen center position (xc, yc). First we have to calculate pixel positions around a circle path centered at the coordinate 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. Then calculate the value of the decision parameter and determine the symmetry points in the other seven octants. To apply the midpoint method we define a circle function:

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

Any point (x, y) on the boundary of the circle with radius r satisfies the equation fcircle (x, y)=0. If the point is in the interior of the circle, the circle function is negative. And if the point is outside of the circle, the circle function is positive. Then the mid positions between pixels near the circle path at each sampling step are obtained from the above circle function tests. Thus, the circle function is the decision parameter in the midpoint algorithm and we can setup incremental calculations for this function.

Our decision parameter is the circle function fcircle (x, y) = x2+y2-r2
evaluated at the midpoint between the two pixels:
pk = fcircle(xk+1, yk-1/2)
= (xk+1)2 + (yk-1/2)2 – r2

If pk<0, this midpoint is inside the circle and the pixel on scan line yk is closer to the circle boundary. Otherwise, the mid position is outside or on the circle boundary and we select the pixel on scan line yk-1. Successive decision parameters are obtained using incremental calculations. Here the next sampling position is xk+1+1 = xk+2.

pk = fcircle(xk+1+1, yk+1-1/2)
= [(xk+1)+1]2 + (yk+1-1/2)2 – r2
OR
pk+1=pk+2(xk+1)+(yk+12-yk2)-(yk+1-yk)+1
Where yk+1 is either yk or yk-1 depending upon the sign of pk.

Evaluation of the terms 2xk+1 and 2yk+1 can also be done incrementally as 2xk+1=2xk+2 and 2yk+1=2yk-2. The initial decision parameter is obtained by evaluating the circle function at the start position (x0, y0)=(0, r)

p0=fcircle (1, r-1/2) = 1+(r-1/2)2-r2 = 5/4-r
If the radius r is specified as an integer, we can simply round p0=1-r.

The mid point method calculates pixel positions along the circumference of a circle using integer additions and subtractions assuming that the circle parameters are specified in integer screen coordinates.

Algorithm:

 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).
 Calculate the initial value of the decision parameter as p0=5/4-r.
 At each xk position, starting at k=0 perform the following test: if pk<0, the next point along the circle centered on (0, 0) is (xk+1, yk) & pk+1=pk + 2xk+1 + 1. Otherwise, the next point along the circle is (xk+1, yk-1) and
pk+1 = pk+2xk+1+1-2yk+1 where 2xk+1=2xk+2 and 2yk+1=2yk-2.
 Determine symmetry points in the other seven octants.
 Move each calculated pixel position (x, y) onto the circular path centered on (xc, yc) and plot the coordinate values:
x=x+xc y=y+yc
 Repeat steps 3 through 5 until x>=y.