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
x^{2}/r_{x}^{2} + y^{2}/r_{y}^{2}
= 1
i.e. r_{y}^{2} x^{2} + r_{x}^{2}
y^{2} - r_{x}^{2} r_{y}^{2} = 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, r_{y}) 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 (r_{x,}
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, r_{y}) and step along the ellipse path in clockwise order
throughout the first quadrant.
Consider the general equation of an ellipse
f_{ellipse}(x, y) = r_{y}^{2} x^{2}
+r_{x}^{2} y^{2} - r_{x}^{2} r_{y}^{2}_{
}
which
has the following properties:
f_{ellipse}(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 f_{ellipse}(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, r_{y}), 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/r_{x}^{2 }dx + 2y/r_{y}^{2 }dy
= 0
Dy/dx = -2r_{y}^{2 }x/2r_{x}^{2
}y
At the boundary between region I and region II, dy/dx =
-1 and 2 r_{y}^{2} x = 2 r_{x}^{2} y.
Therefore, we move out of region I whenever 2 r_{y}^{2}
x ≥ 2 r_{x}^{2}
y.
x is always incremented in each step i.e. x_{k+}i
= x_{k} + 1
y_{k} +1 = y_{k} if E is selected or y_{k+1}
= y_{k} -1 if SE is selected.
In order to make decision between S and SE, a decision (x_{k}
+ 1, y_{k} – ½ ) is set
at the middle between the two candidate pixels. A decision function pl_{k }can
be defined as follows:
Pl_{k}= f_{ellipse }(X_{k} + 1, y_{k}
- ½ )
= r_{y}^{2} (x_{k} + 1)^{2}
+ r_{x}^{2} (y_{k} – ½ )^{2} - r_{x}^{2} r_{y}^{2}
= r_{y}^{2 }(x_{k}^{2 }+ 2
x_{k} + 1) + r_{x}^{2 }(y_{k}^{2 }– ¼ ) - r_{x}^{2} r_{y}^{2}
If p1_{k }< 0 select E i.e. x_{k+1 }= y_{k+1 }= y_{k}
p1_{k+1 }= r_{x}^{2
}(x_{k+1 }+ 1)^{2
}+ r_{x}^{2} (y_{k} – ½ )^{2} - r_{x}^{2}
r_{y}^{2}
= r_{y}^{2}
(x_{k} + 2)^{2} + r_{x}^{2} (y_{k} - ^{½} )^{2} - r_{x}^{2} r_{y}^{2 }
= r_{y}^{2} (x_{k}^{2} +
4x_{k} + 4) + r_{x}^{2} (y_{k}^{2} - y_{k}
+ ¼ ) - r_{x}^{2} r_{y}^{2}
pl_{ k+1}-pl_{ k} = 2r_{y}^{2}
x_{k} + 3r_{y}^{2}
_{ }= r_{y}^{2}(2x_{k}
+ 3)
= r_{y}^{2}(2x_{k }+ l) +
l)
= r_{y}^{2} (2x_{ k+1 }+ 1)
= 2 r_{y}^{2 }x_{k+1 } + r_{y}^{2}
If pl_{k }≥ 0, select SE i.e x_{k+1}
= x_{k} + 1 and y_{k+1} = y_{k }- 1
pl_{k+1} = r_{y}^{2} (x_{k+1}
+ 1)^{2} + r_{x}^{2} (y_{k+1} – ½ )^{2} - r_{x}^{2}
r_{y}^{2 }
= r_{y}^{2}(x_{k} + 2)^{2 }+
r_{x}^{2}(y_{k }- 3/2 )^{2 }- r_{x}^{2}r_{y}^{2
}
= r_{y}^{2} (x_{k}^{2} +
4x_{k} + 4) + r_{x}^{2} (y_{k}^{2} - 3y_{k}
+ 9/4) - r_{x}^{2} r_{y}^{2}
pl_{k+1} - pl_{k} = 2r_{y}^{2}
x_{k} + 3 r_{y}^{2 }- 2r_{x}^{2} y_{k}
+ 2r_{x}^{2}
= 2r_{y}^{2} x_{k} + 3 r_{y}^{2}
- 2 r_{x}^{2} y_{k} + 2r_{x}^{2}
= r_{ y}^{2}(2x_{k}+3) - 2r_{x}^{2
}(y_{k}-l)
= r_{y}^{2}(2(x_{k}+l)+l) - 2r_{x}^{2
}(y_{k }- l)
= r_{y}^{2}(2x_{k+1} + l) - 2r_{x}^{2}y_{k+1
}
= 2r_{y}^{2} x_{k+1} + r_{y}^{2}
- 2r_{x}^{2} y_{k+1}
At the initial position (0, r_{y})
P1_{0 }=
f_{ellipse }(1, r_{y }- ½ )
= r_{y}^{2 }l^{2 }+ r_{x}^{2
}(r_{y }- ½ )^{2 }– r_{x}^{2 }r_{y}^{2
}
= r_{y}^{2 }+ r_{x}^{2 }(r^{2}_{y
}- r_{y }+ l/4) -r_{x}^{2 }r_{y}^{2}
^{ }= r_{y}^{2}
- r_{x}^{2}r_{y} +1/4 r_{x}^{2}
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. y_{k+1}
= y_{k} - 1
x_{k+1} = x_{k} if S is selected or x_{k+1}
= x_{k} +1 if SE is selected.
In order to make decision between E and SE, a decision (x_{k}
+ 1/2, y_{k} - 1) is set at the middle between the two candidate
pixels. A decision function p2_{k }can be defined as follows:
p2_{k} = f_{ellipse}(x_{k} + 1/2,
y_{k} - 1)
= r_{ y}^{2}(x_{k} + 1/2)^{2}
+ r_{x}^{2} (y_{k} - 1)^{2 }- r_{x}^{2}
r_{y}^{2}
= r_{y}^{2} (x_{k}^{2} +
x_{k} + 1/4) + r_{x}^{2} (y_{k}^{2} -
2y_{k} + 1) - r_{x}^{2} r_{y}^{2}
If p2_{k }> 0, select S i.e x_{k+1} =
x_{k} and y_{k+1} = y_{k }- 1
P2_{k+1} = r_{y}^{2} (x_{k+1}
+ 1/2)^{2} + r_{x}^{2} (y_{k+1} - 1)^{2}
- r_{x}^{2} r_{y}^{2 }
= r_{y}^{2} (x_{k} + 1/2)^{2}
+ r_{x}^{2} (y_{k} - 2)^{2} - r_{x}^{2}
r_{y}^{2 }
= r_{y}^{2} (x_{k}^{2} +
x_{k} + 1/4) + r_{x}^{2} (y_{k}^{2} -
4y_{k} + 4) - r_{x}^{2} r_{y}^{2}
p2_{k+1} - p2_{k} = -2r_{x}^{2}
y_{k} + 3 r_{x}^{2 }
= -r_{x}^{2}(2y_{k} - 3)
= -r_{x}^{2}(2(y_{k}-l)-l)
= -r_{x}^{2}(2y_{k+1} - 1)
= -2r_{x}^{2}y_{k+1} + r_{x}^{2}
If p2_{k }≤ 0, select SE i.e x_{k+1}
= x_{k} + 1 and y_{k+}i = y_{k}- 1
P2_{k+1} = r_{y}^{2} (x_{k+1}
+ 1/2)^{2} + r_{x}^{2} (y_{k+1} - I)^{2}
- r_{x}^{2} r_{y}^{2 }
= r_{y}^{2}(x_{k} + 3/2)^{2 }+
r_{x}^{2}(y_{k }- 2)^{2 }- r_{x}^{2}r_{y}^{2
}
= r_{y}^{2} (x_{k}^{2} +
3x_{k} + 9/4) + r_{x}^{2} (y_{k}^{2} -
4y_{k}+ 4) - r_{x}^{2} r_{y}^{2}
p2_{k+1} - p2_{k} = r_{y}^{2}
(x_{k}^{2} + 3x_{k} + 9/4) + r_{x}^{2}
(y_{k}^{2} - 4y_{k} + 4) - r_{x}^{2} r_{y}^{2}-
r_{y}^{2} (x_{k}^{2} + x_{k} + l/4) -r_{x}^{2}(y_{k}^{2
}- 2y_{k }+ l) + r_{x}^{2}r_{y}^{2 }
= 2r_{v}^{2} x_{k} + 2 r_{v}^{2}
- 2 r_{x}^{2} y_{k} + 3r_{x}^{2}
= 2r_{y}^{2}(x_{k }+ l) - 2r_{x}^{2
}(y_{k }- l) + r_{x}^{2}
= 2r_{y}^{2}x_{k+1 }- 2r_{x}^{2}y_{k+1
}+ r_{x}^{2}
When we enter the region II, the initial position (x_{0},
yo) is taken as the last position selected in region I and the initial decision
parameter in region II is then
P2_{0 }=
f_{ellipse} (Xo+ 1/2, y_{0} - 1)
= r_{y}^{2 }(x_{k }+ ½ )^{2 }+
r_{x}^{2 }(y_{0 }- l)^{2 }-r_{x}^{2 }r_{y}^{2}