Computer Graphics Notes - Lab 13 - Ellipse Generating Algorithms Cont

MIDPOINT ELLIPSE ALGORITHM

1.     Read r_x and r_y.

2.     Initialise starting point

x = 0

y = r_y

3.     Calculate the initial value of decision parameter in region I as

d₁ = r_y² - r_x²r_y + 1/4 r_x²

4.     Initialize dx and dy as

dx = 2r_y² x

dy = 2r_x²y

5.     do

        {

plot(x,y)

if(d₁ < 0)

{

x = x+ 1

y = y

dx = dx + 2r_y²

d₁ = d₁ + dx+ r_y²

}

else

x = x + 1

y = y - l

dx = dx + 2r_y²

dy = dy - 2r_x²

d₁ = d₁ + dx - dy + r_y²

 } while (dx < dy)

6.     Calculate the initial value of decision parameter in region II as

        d₂ = r_y² (x + 1/2) ² + r_x² (y - 1) ² - r_x² r_y²

7.     do

{

plot(x,y)

if (d₂ > 0)

{

x = x

y = y – 1

dy = dy - 2r _x²

d_{2 =} d₂ - dy + r_x²

}

Else

{

x = x+ 1

y = y – 1

dx = dx + 2r_y²

dy = dy - 2r_x²

d_{2 =} d₂ + dx - dy + r_x²

 } while (y > 0)

8.     Determine symmetrical points in other three quadrants.

9.     Stop.

Example

Given ellipse parameters r_x = 8 and r_y = 6. Determine raster positions.

For region I

d₁ = r_y²  – r_x² r_y + ¼ r_x²

= 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

d₂ = 36 (7 + ^l/2)² + 64 (3 - 1)² - 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)	-	-