More info

Tuesday, 18 February 2014

Computer Graphics Notes - Lab 13 - Ellipse Generating Algorithms Cont

MIDPOINT ELLIPSE ALGORITHM

1.     Read rx and ry.
2.     Initialise starting point
x = 0
y = ry
3.     Calculate the initial value of decision parameter in region I as
d1 = ry2 - rx2ry + 1/4 rx2
4.     Initialize dx and dy as
dx = 2ry2 x
dy = 2rx2y
5.     do
        {
plot(x,y)
if(d1 < 0)
{
x = x+ 1
y = y
dx = dx + 2ry2
d1 = d1 + dx+ ry2
}
else
x = x + 1
y = y - l
dx = dx + 2ry2
dy = dy - 2rx2
d1 = d1 + dx - dy + ry2
 } while (dx < dy)

6.     Calculate the initial value of decision parameter in region II as
        d2 = ry2 (x + 1/2) 2 + rx2 (y - 1) 2 - rx2 ry2

7.     do
{
plot(x,y)
if (d2 > 0)
{
x = x
y = y – 1
dy = dy - 2r x2
d2 = d2 - dy + rx2
}
Else
{
x = x+ 1
y = y – 1
dx = dx + 2ry2
dy = dy - 2rx2
d2 = d2 + dx - dy + rx2
 } while (y > 0)

8.     Determine symmetrical points in other three quadrants.

9.     Stop.

Example
Given ellipse parameters rx = 8 and ry = 6. Determine raster positions.

For region I
d1 = ry– rx2 ry + ¼ rx2
= 36 – 64 *6 + ¼ *64
= 36 - 384 + 16
= 52 - 384
= - 332
k
d1
(xk+1, yk+1)
2ry2 xk+1
2rx2 yk+1
0
     -332
(1,6)
72
768
1
     -224
(2,6)
144
768
2
      -44
(3,6)
216
768
3
208
(4,5)
288
640
4
    -108
(5,5)
360
640
5
288
(6,4)
432
512
6
244
(7,3)
504
384


For region II

The initial point is (7, 3)
Our initial decision parameter is
d2 = 36 (7 + l/2)2 + 64 (3 - 1)2 - 36 *64
= 36*225/4 + 64*4 - 2304
= 2025 + 256 - 2304
= - 23
k
d1
(xk+1, yk+1)
2ry2 xk+1
2rx2 yk+1
0
     -23
(8,2)
576
256
1
     361
(8,1)
576
128
2
      297
(8,0)
-
-



Computer Graphics Notes - Lab 13 - Ellipse Generating Algorithms Cont.

MIDPOINT ELLIPSE DRAWING ALGORITHM
Midpoint ellipse algorithm is a method for drawing ellipse in computer graphics. This method is modified from Bresenham's algorithm. The advantage of this method is that only addition operations are required in the program loops. This leads to simple and fast implementation in all processors.

An ellipse centered at the origin of an x-y coordinate system with its major axis along the jc-axis is defined by the equation
x2/rx2 + y2/ry2 = 1
i.e. ry2 x2 + rx2 y2 - rx2 ry2 = 0
The midpoint ellipse method is applied throughout the first quadrant in two parts .Let us consider one quarter of an ellipse. The curve is divided into two regions. In region I, the slope on the curve is greater than -1 while in region II less than-1.



Regions I and II can be processed in various ways. We can start at position (0, ry) and step clock wise along the elliptical path in the first quadrant shifting from unit steps in x to unit steps in y when the slope becomes less than -1. Alternatively, we could start at (rx, 0) and select points in a counterclockwise order, shifting from unit steps in y to unit steps in x when the slope becomes greater than -l. As an example of a sequential implementation of the midpoint algorithm, we take the start position at (0, ry) and step along the ellipse path in clockwise order throughout the first quadrant.

Consider the general equation of an ellipse
fellipse(x, y) = ry2 x2 +rx2 y2 - rx2 ry2
which has the following properties:
fellipse(x, y)   < 0, if (x, y) is inside the ellipse boundary
                   = 0, if (x, y) is on the ellipse boundary
                   > 0, if (x, y) is outside the ellipse boundary

Thus, the ellipse function fellipse(x, y) serves as the decision parameter in the midpoint algorithm. At each sampling position, we select the next pixel along the ellipse path according to the sign of the ellipse function evaluated at the midpoint between the two candidate pixels.

Starting at (0, ry), we take unit steps in the x direction until we reach the boundary between region I and region II. Then we switch to unit steps in the y direction over the reminder of the curve in the first quadrant. At each step, we need to test the value of the slope of the curve. The ellipse slope is calculated as
2x/rx2 dx + 2y/ry2 dy = 0
Dy/dx = -2ry2 x/2rx2 y

At the boundary between region I and region II, dy/dx = -1 and 2 ry2 x = 2 rx2 y.

Therefore, we move out of region I whenever 2 ry2 x 2 rx2 y.







x is always incremented in each step i.e. xk+i = xk + 1
yk +1 = yk if E is selected or yk+1 = yk -1 if SE is selected.

In order to make decision between S and SE, a decision (xk + 1, yk – ½ ) is set at the middle between the two candidate pixels. A decision function plk can be defined as follows:
Plk= fellipse (Xk + 1, yk - ½ )
= ry2 (xk + 1)2 + rx2 (yk – ½ )2 - rx2 ry2
= ry2 (xk2 + 2 xk + 1) + rx2 (yk2 – ¼ ) - rx2 ry2

If p1< 0 select E i.e. xk+1 = yk+1 = yk
p1k+1 = rx2 (xk+1 + 1)+ rx2 (yk – ½ )2 - rx2 ry2

= ry2 (xk + 2)2 + rx2 (yk - ½ )2 - rx2 ry2
= ry2 (xk2 + 4xk + 4) + rx2 (yk2 - yk + ¼ ) - rx2 ry2

pl k+1-pl k = 2ry2 xk + 3ry2
 = ry2(2xk + 3)
= ry2(2xk + l) + l)
= ry2 (2x k+1 + 1)
= 2 ry2 xk+1  + ry2
If plk 0, select SE i.e xk+1 = xk + 1 and yk+1 = yk - 1
plk+1 = ry2 (xk+1 + 1)2 + rx2 (yk+1 – ½ )2 - rx2 ry2
= ry2(xk + 2)2 + rx2(yk - 3/2 )2 - rx2ry2
= ry2 (xk2 + 4xk + 4) + rx2 (yk2 - 3yk + 9/4) - rx2 ry2

plk+1 - plk = 2ry2 xk + 3 ry2 - 2rx2 yk + 2rx2
= 2ry2 xk + 3 ry2 - 2 rx2 yk + 2rx2
= r y2(2xk+3) - 2rx2 (yk-l)
= ry2(2(xk+l)+l) - 2rx2 (yk - l)
= ry2(2xk+1 + l) - 2rx2yk+1
= 2ry2 xk+1 + ry2 - 2rx2 yk+1

At the initial position (0, ry)
P10 = fellipse (1, ry - ½ )
= ry2 l2 + rx2 (ry - ½ )2 – rx2 ry2
= ry2 + rx2 (r2y - ry + l/4) -rx2 ry2
 = ry2 - rx2ry +1/4 rx2

In region II (dy/dx < -1)

All calculations are similar to that in region I except that y is decremented in each step.

y is always incremented in each step i.e. yk+1 = yk - 1
xk+1 = xk if S is selected or xk+1 = xk +1 if SE is selected.





In order to make decision between E and SE, a decision (xk + 1/2, yk - 1) is set at the middle between the two candidate pixels. A decision function p2k can be defined as follows:
p2k = fellipse(xk + 1/2, yk - 1)
= r y2(xk + 1/2)2 + rx2 (yk - 1)2 - rx2 ry2
= ry2 (xk2 + xk + 1/4) + rx2 (yk2 - 2yk + 1) - rx2 ry2

If p2k > 0, select S i.e xk+1 = xk and yk+1 = yk - 1
P2k+1 = ry2 (xk+1 + 1/2)2 + rx2 (yk+1 - 1)2 - rx2 ry2
= ry2 (xk + 1/2)2 + rx2 (yk - 2)2 - rx2 ry2
= ry2 (xk2 + xk + 1/4) + rx2 (yk2 - 4yk + 4) - rx2 ry2
p2k+1 - p2k = -2rx2 yk + 3 rx2
= -rx2(2yk - 3)
= -rx2(2(yk-l)-l)
= -rx2(2yk+1 - 1)
= -2rx2yk+1 + rx2

If p2k 0, select SE i.e xk+1 = xk + 1 and yk+i = yk- 1

P2k+1 = ry2 (xk+1 + 1/2)2 + rx2 (yk+1 - I)2 - rx2 ry2
= ry2(xk + 3/2)2 + rx2(yk - 2)2 - rx2ry2
= ry2 (xk2 + 3xk + 9/4) + rx2 (yk2 - 4yk+ 4) - rx2 ry2

p2k+1 - p2k = ry2 (xk2 + 3xk + 9/4) + rx2 (yk2 - 4yk + 4) - rx2 ry2- ry2 (xk2 + xk + l/4) -rx2(yk2 - 2yk + l) + rx2ry2
= 2rv2 xk + 2 rv2 - 2 rx2 yk + 3rx2
= 2ry2(xk + l) - 2rx2 (yk - l) + rx2
= 2ry2xk+1 - 2rx2yk+1 + rx2

When we enter the region II, the initial position (x0, yo) is taken as the last position selected in region I and the initial decision parameter in region II is then

P20 = fellipse (Xo+ 1/2, y0 - 1)
= ry2 (xk + ½ )2 + rx2 (y0 - l)2 -rx2 ry2