The Quadratic Curves, Circles and Ellipses FAQ
==============================================
Version 1.3 17th March 1998
----------------------------
This FAQ is maintained by "hexapod@netcom.com". Any additional suggestions
or related questions are welcome. Just send E-mail to the above address.
Feel free to distribute or copy this FAQ as you please.
Questions
---------
QUADRATIC CURVES
================
Q1. What is a quadratic curve?
Q2. How do I solve a quadratic equation?
Q3. What is the "discriminant" of a quadratic curve?
Q4. How do I calculate the value of X for a know value of Y?
Q5. How do I calculate the coefficients of a rotated quadratic curve?
Q6. How do I determine the gradient of a quadratic curve?
Q7. How do I determine the outward normal of a quadratic curve?
CIRCLES
=======
Q8. What is a circle?
Q9. How do I define a circle mathematically?
Q10. What is the general equation of the circle?
Q11. How do I derive the general equation of the circle?
Q12. How do I determine the limits of a circle?
Q13. How do I determine the gradient at a point on a circle?
Q14. How do I determine the outward normal of a circle?
Q15. How do I determine the octant of a point on a circle?
ELLIPSES
========
Q16. What is an ellipse?
Q17. How do I calculate the Y coordinate if only the X coordinate is known?
Q18. How do I calculate the gradient of a point on a ellipse?
Q19. How do I calculate the outward normal of a point on an ellipse?
Q20. How do I calculate the coefficients of an axis-orientated ellipse?
Q21. How do I calculate the coefficients of an arbitary rotated ellipse?
Q22. How do I determine the limits for an arbitary rotated ellipse?
Q23. How do I render a filled rotated ellipse?
Q24. How do I render the outline of a rotated ellipse?
ANSWERS
=======
QUADRATIC CURVES
================
Q1. What is a quadratic curve?
------------------------------
A quadratic curve is a curve defined by the equation:
2
y = At + Bt + C
x = t
The most common uses for this equation are to calculate the path of a
projectile in a constant gravitational field ie. football being kicked
into the air or an artillery shell being fired from a tank.
The value of x defines the horizontal position of the object. The
value of y defines the vertical position.
The value of t defines the current time. t=0 defines the position of
x and y at the initial position of the projectile.
Q2. How do I solve a quadratic equation?
----------------------------------------
To calculate the values of x that make y equal to zero, use the equation:
____________
/
/ 2
-B +/- \/ B - 4AC provided A != 0
x = -----------------------
2A
The values of x are known as "roots".
Q3. What is the discriminant of a quadratic curve?
--------------------------------------------------
The "discriminant" is defined as the value of
2
B - 4AC
If this value is negative, no roots exist and no value of X can be found.
If this value is zero, only one root exist and one value of X exists.
If this value is positive, then two roots exist, and two value of X exist.
Q4. How do I calculate the value of X for a know value of Y?
------------------------------------------------------------
For a given value of Y, the value X that generates this value can be
determined by the equation:
_____________
/
/ 2
-B +/- \/ B - 4A(C-y) provided A != 0
x = ------------------------
2A
The discriminant in this case is thus:
2
D = B - 4A(C-y)
The values of D determine the number of roots as above.
Q5. How do I calculate the coefficients of a rotated quadratic curve?
---------------------------------------------------------------------
For a quadratic curve with a vertical axis of symmetry:
2
[1] y = Px + Qx + R
2
<=> Px + Qx + R - y = 0
Rotating a pair of X and Y coordinates can be performed by the following
expression:
| M N | | Mx - Ny |
| x y | x | | = | |
| -N M | | Nx + My |
where
M = cos (angle)
N = sin (angle)
Substituting the resulting matrix elements into equation [1] gives:
2
P(Mx - Ny) + Q(Mx - Ny) + R - (Nx + My) = 0
2 2 2 2
<=> P(M x - 2MNxy + N y ) + QMx - QNy + R - Nx - My = 0
2 2 2 2
<=> PM x - 2MNPxy + PN y + QMx - QNy + R - Nx - My = 0
2 2 2 2
<=> PM x + PN y + QMx - Nx - QNy - My - 2MNPxy + R = 0
Expressing in terms of the standard equation of the circle:
2 2
Ax + By + Cx + Dy + Exy + F = 0
Then the values of the coefficients are:
2
A = PM
2
B = PN
C = QM - N
D = -QN - M
E = -2MNP
F = R
Q6. How do I determine the gradient of a quadratic curve?
---------------------------------------------------------
The gradient of a quadratic curve is calculated by calculating the
derivative:
For any polynomial equation term of the form:
n n-1 2 3 2
Ax becomes nAx eg. x becomes 2x, 4x becomes 12x
Constant terms are discarded.
Thus, the gradient of a quadratic curve:
2
Ax + Bx + C = 0
becomes
dy = 2Ax + B
dx = 1
dy
M = -- = 2Ax + B
dx
For a rotated quadratic curve, the values of dx and dy are as follows:
dx = 2Ax + C + Ey
dy = 2By + D + Ex
Then the gradient is calculated from:
dy 2By + D + Ex
M = -- = ------------
dx 2Ax + C + Ey
Q7. How do I determine the outward normal of a quadratic curve?
---------------------------------------------------------------
The outward normal of a quadratic curve is the direction perpendicular
to the tangent vector of the curve at a select point:
The tangent vector can be calculated by converting the gradient into a
rotation angle. Using the C programming language, this can be achieved
using the "atan" function, and then using this angle as input to the
"sine" and "cosine" functions.
---------------------------------
angle = atan( gradient );
tangent.vx = cos( angle );
tangent.vy = sin( angle );
---------------------------------
Since the outward normal is perpendicular to the tangent vector, it can
be considered to be a rotation of 90 degrees ie:
O = M . T
This can be expanded out:
| Ox | | cos A -sin A | | Tx |
| | = | | . | |
| Oy | | sin A cos A | | Ty |
If the gradient is zero, then T = (1,0) and O = (0,1)
| C.Tx - S.Ty | | 1 | | 0 |
O = | | .| | = | |
| S.Tx + C.Ty | | 0 | | 1 |
| 0*1 + -1*0 |
O = | |
| 1*1 + 0*0 |
This can be solved for M:
| 0 -1 |
M = | |
| 1 0 |
This can be simplified down to:
| -sin A |
O = | |
| cos A |
CIRCLES
=======
Q8. What is a circle?
---------------------
A circle is a type of curve such that every point is a constant distance
away from a single fixed centre point eg. the origin
The distance between each point on the circle and the centre point is
known as the "radius".
Q9. How do I define a circle mathematically?
--------------------------------------------
A circle centred at the origin, and with radius r can be represented
as the equation:
2 2
x y
-- + -- - 1 = 0
2 2
r r
where:
(x,y) defines a two-dimensional coordinate and
r is the radius of the circle.
If the circle is not at the origin then the circle will have centre-point
at some coordinate [c,d]. This modifies the equation to be:
2 2
(x-c) (y-d)
------ + ------ - 1 = 0
2 2
r r
Q10. What is the general equation of the circle?
------------------------------------------------
If the previous equation is expanded out and constants assigned to
each power of x and y, then the following equation is derived:
2 2
Ax + By + Cx + Dy + Exy + F = 0
where A, B, C, D, E, F are constant terms.
This is referred to as the general equation of the circle
Each constant has the following effect:
A - Radius of the ellipse in the X-axis
B - Radius of the ellipse in the Y-axis
C - Determines centre point X coordinate
D - Determines centre point Y coordinate
E - Determines rotation of the ellipse (always zero if axis-aligned)
F - Determines average radius of the ellipse
The derivation of this equation is presented below.
Q11. How do I derive the general equation of the circle?
--------------------------------------------------------
The general equation of the circle can be derived by multiplying out
the equation:
2 2
(x-c) (y-d)
------ + ------ - 1 = 0
2 2
r r
Multiplying out the denominator gives:
2 2 2
(x-c) + (y-d) - r = 0
This expands into:
2 2 2 2 2
(x - 2xc + c ) + (y -2yd + d ) - r = 0
Fully expanding into single terms:
2 2 2 2 2
x - 2cx + c + y - 2dy + d - r = 0
Rearranging these parameters to conform to the general equation:
2 2
Ax + By + Cx + Dy + Exy + F = 0
gives:
2 2 2 2 2
x + y -2cx -2dy + c + d - r = 0
Assigning values to each constant term in the general equation gives:
A = 1
B = 1
C = -2c
D = -2d
E = 0
2 2 2
F = c + d - r
For a circle, A and B are always set to one.
If the circle is at the origin then C and D are both set to zero.
For a circle E is always zero.
If F is zero, then the circle defines a single point.
If F is negative, then no point or circle exists.
Q12. How do I determine the limits of a circle?
-----------------------------------------------
These are simply calculated using:
xmin = c-r xmax = c+r
ymin = d-r ymax = d+r
Or if the coefficients of the circle is known, then they can be solved
using the equations:
For the X-axis:
2
2 D 2
Ax + Cx - -- - r = 0
4
For the Y-axis:
2
2 C 2
By + Dy - -- - r = 0
4
Q13. How do I determine the gradient at a point on a circle?
------------------------------------------------------------
The general equation of a circle is:
2 2
x + y + Cx + Dy + Exy + F = 0
The derivative for X is:
dx = 2x + C + Ey
The derivative for Y is:
dy = 2y + D + Ex
Then the gradient M is given by:
dy 2y + D + Ex
M = -- = -----------
dx 2x + C + Ey
But E = 0 for a circle, so:
2y + D
M = ------
2x + C
This can be converted to an angle using the tan function ie.
dx = sin( angle ) = 2x + C
dy = cos( angle ) = 2y + D
Then the angle is determined from
angle = atan2( dy, dx )
or
angle = atan( dy / dx )
Q14. How do I determine the outward normal of a circle?
-------------------------------------------------------
Since the derivatives of the circle are:
dx = 2x + C
dy = 2y + D
and the gradient of the outward normal is perpendicular to the gradient
of the tangent, then:
1 1
N = - - = - ---------
M |dy|
|--|
|dx|
Then
Nx = 2x + C = sin( angle )
Ny = 2y + D = cos( angle )
Q15. How do I determine the octant of a point on a circle?
----------------------------------------------------------
The equation of a circle is:
2 2
Ax + By + Cx + Dy + Exy + F = 0
Plotted in two dimensions, a circle can be divided into eight octants
+-------------------------------------------+
| |
| dy=0 |
| dx=-dy [7] ^ [0] dx=dy |
| |Y |
| \ dx>dy | dx>dy / |
| \ dx>0 | dx>0 / |
| \ dy>0 | dy<0 / |
| \ | / |
| [6] \ >-o->- / [1] |
| \ / | \ / |
| dx < dy x | x dx > dy |
| dx > 0 / \ | / \ dx > 0 |
| dy > 0 | \ | / | dy < 0 |
| ^ \ | / v |
| dx=0 | \|/ | |
| ----------o------+------o--------> dx=0 |
| | /|\ | |
| ^ / | \ v X |
| [5] | / | \ | [2] |
| \ / | \ / |
| dx < dy x | x dx > dy |
| dx < 0 / \ | / \ dx < 0 |
| dy > 0 / -<-o-<- \ dy < 0 |
| / | \ |
| / [4] | [3] \ |
| / | \ |
| / dx < dy | dx < dy \ |
| dx=dy dx < 0 | dx < 0 dx=-dy |
| dy > 0 | dy < 0 |
| dy=0 |
| |
+-------------------------------------------+
Expressing each line has the following equation:
Ax + By + C = 0
generates the following table:
+--------+-------+----+----+-----+
|Equation| | A | B | C |
+--------+-------+----+----+-----+
| dx=dy | X-Y=0 | 1 | -1 | 0 |
| dx=0 | X=0 | 1 | 0 | 0 |
| dx=-dy | X+Y=0 | 1 | 1 | 0 |
| dy=0 | Y=0 | 0 | 1 | 0 |
+--------+-------+----+----+-----+
Each octant has the following attributes:
+----------+------+------+----------+--------+--------+
| Octant # | dx | dy | dx ?? dy | start | end |
+----------+------+------+----------+--------+--------+
| 0 | > 0 | < 0 | dx > dy | dy= 0 | dx= dy |
| 1 | > 0 | < 0 | dx > dy | dx= dy | dx= 0 |
| 2 | < 0 | < 0 | dx > dy | dx= 0 | dx=-dy |
| 3 | < 0 | < 0 | dx < dy | dx=-dy | dy= 0 |
| 4 | < 0 | > 0 | dx < dy | dy= 0 | dx= dy |
| 5 | < 0 | > 0 | dx < dy | dx= dy | dx= 0 |
| 6 | > 0 | > 0 | dx < dy | dx= 0 | dx=-dy |
| 7 | > 0 | > 0 | dx > dy | dx=-dy | dy= 0 |
+----------+------+------+----------+--------+--------+
ELLIPSES
========
Q16. What is an ellipse?
------------------------
An ellipse is a closed curve similar to a circle. However, the radius
varies between a minimum diameter and a maximum diameter.
In effect, an ellipse can be considered to be a squashed or stretched
circle.
An axis-aligned ellipse can be specified as a centre (c,d) and
axis radii (r,s)
These can be combined to give the equation:
2 2
(x-c) (y-d)
----- + ------ - 1 = 0
2 2
r s
Expnding out this expression will generate an equation identical to that
of a circle. However, the values of A and B are not guaranteed to be
equal to one.
The algebraic expression is:
2 2
Ax + By + Cx + Dy + Exy + F = 0
where A,B,C,D,E and F are constant terms.
Q17. How do I calculate the Y coordinate if only the X coordinate is known?
---------------------------------------------------------------------------
Given the equation:
2 2
[1] Ax + By + Cx + Dy + Exy + F = 0
Then the known value of x or y is defined as:
[2] x = X
y = Y
Substituting [2] into [1] gives:
2 2
[3] AX + By + CX + Dy + EXy + F = 0
2 2
Ax + BY + Cx + DY + ExY + F = 0
Moving all constant terms to the end of the equation gives:
2 2
[4] By + Dy + EXy + AX + CX + F = 0
2 2
Ax + Cx + ExY + BY + DY + F = 0
Converting these into quadratic equations gives:
2 2
Ry + Sy + T = 0 Rx + Sx + T = 0
where:
R = B R = A
S = D +Ey S = C + EY
2 2
T = AX + CX + F T = BY + DY + F
These values can be solved using quadratic equations.
Q18. How do I determine the gradient of a point on a ellipse?
-------------------------------------------------------------
The equation of the ellipse is:
2 2
Ax + By + Cx + Dy + Exy + F = 0
The values of dx and dy are calculated from:
dx = 2Ax + C + Ey
dy = 2By + D + Ex
The gradient is calculated from:
dy 2By + D + Ex
M = -- = ------------
dx 2Ax + C + Ey
Q19. How do I determine the outward normal of a point on the ellipse?
---------------------------------------------------------------------
The equation of the ellipse is:
2 2
Ax + By + Cx + Dy + Exy + F = 0
The values of dx and dy are calculated from:
dx = 2Ax + C + Ey
dy = 2By + D + Ex
The outward normal is calculated from:
N = ( dy, -dx )
Q20. How do I calculate the coefficients of an axis-aligned ellipse?
--------------------------------------------------------------------
The algebraic exprssion of an ellipse is:
2 2
Ax + By + Cx + Dy + Exy + F = 0
where A,B,C,D,E and F are constant terms.
Multiplying out the denominators in [1] gives:
2 2 2 2 2 2
s (x-c) + r (y-d) - r s = 0
Multiplying out the numerators in [1] gives:
2 2 2 2 2 2 2 2
s (x - 2cx + c ) + r (y - 2dy + d ) - r s = 0
Converting into single terms produces:
2 2 2 2 2 2 2 2 2 2 2 2
s x - s 2cx + s c + r y - r 2dy + r d - r s = 0
Multiplying every parameter by the denominator gives:
2 2 2 2 2 2 2 2 2 2 2 2
s x - s 2cx + s c + r y - r 2dy + r d - r s = 0
Rearranging into the algebraic expression gives:
2 2 2 2 2 2 2 2 2 2 2 2
s x + r y - s 2cx - r 2dy + r d + s c - r s = 0
The values of the constant terms are then as follows:
2
A = s
2
B = r
2
C = -s 2c
2
D = -r 2d
E = 0
2 2 2 2 2 2
F = r d + s c - r s
For an axis-aligned ellipse, A and B are always positive.
For an axis-aligned ellipse, E is always zero, and F is always negative.
These constants can be used to render the ellipse using an incremental
scan-line algorithm.
Q21. How do I calculate the coefficients of an arbitary rotated ellipse?
------------------------------------------------------------------------
The parameters calculated previously are only correct for an ellipse
which is aligned with the X and Y axii.
The ellipse still has to be rotated by the desired angle. This is done
as follows:
Rotating a pair of X and Y coordinates can be performed by the following
expression:
| M N | | Mx - Ny |
[x y] | | = | |
| -N M | | Nx + My |
where
M = cos( angle )
N = sin( angle )
Substituting the resulting matrix elements into equation [1] gives:
2 2
(Mx-Ny-c ) (Nx+My-d )
---------- + ---------- - 1 = 0
2 2
r s
Multiplying out the denominators gives:
2| | 2| | 2 2
s |(Mx-Ny-c)(Mx-Ny-c)| + r |(Nx+My-d)(Nx+My-d)| - r s = 0
| | | |
Multiplying out the equations within the parenthesis gives:
2| 2 2 2 2 2 |
s |(M x + N y + c - 2MxNy - 2Nyc - 2Mxc)| +
| |
2| 2 2 2 2 2 | 2 2
r |(N x + M y + d + 2NxMy - 2Myd - 2Nxd)| - r s = 0
| |
Then rearranging into the order required by equation [2] gives:
2 2 2 2 2 2 2 2 2 2 2
s M x + s N y - s 2MxNy - s 2Mxc - s 2Nyc + s c +
2 2 2 2 2 2 2 2 2 2 2 2 2
r N x + r M y + r 2MxMy - r 2Myd - r 2Nxd + r d - r s = 0
The values of the constant terms are then as follows:
2 2 2 2
A = s M + r N
2 2 2 2
B = s N + r M
2 2
C = -2 ( s Mc + r Nd )
2 2
D = -2 ( s Nc + r Md )
2 2
E = 2 ( s MN - r MN )
2 2 2 2 2 2
F = s c + r d - r s
These values tend to get quite large, so 64-bit integers will be
required.
Q22. How do I determine the limits for a rotated ellipse?
---------------------------------------------------------
The equation of the ellipse is:
2 2
[1] Ax + By + Cx + Dy + Exy + F = 0
The derivative for the X-axis is:
[2] dx = 2Ax + C + Ey
The derivative for the Y-axis is:
[3] dy = 2By + D + Ex
When dx is zero, then the current location is at the left or right limit
of the ellipse.
When dy is zero, then the current location is at the bottom or top limit
of the ellipse.
Calculating the limits for Y gives:
General equation of the circle:
2 2
[1] Ax + By + Cx + Dy + Exy + F = 0
Derivative of Y:
[2] 2By + D + Ex = 0
Expressing y in terms of x gives:
2By = -Ex - D
-Ex - D
y = ------
2B
Substituting into equation [1] gives:
2
2 | -Ex - D | | -Ex - D | | -Ex - D |
Ax + B| ------- | + Cx + D| ------- | + Ex | ------- | + F = 0
| 2B | | 2B | | 2B |
Multiplying out last two brackets gives:
2 2 2
2 | (-Ex-D)(-Ex-D) | -DEx - D -E x - DEx
Ax + B| -------------- | + Cx + --------- + ----------- + F = 0
| 2 | 2B 2B
4B
Expanding out all brackets produces:
2 2 2 2 2
2 | E x +2DEx + D | 2DE 2D 2E 2 2DE
Ax + B| ---------------- | + Cx - --- x - --- - -- x - --- x + F = 0
| 2 | 4B 4B 4B 4B
4B
Cancelling out terms in first bracket and breaking up last two brackets:
2 2 2 2 2
2 E x + 2DEx + D 2DE 2D 2E 2 2DE
Ax + ----------------- + Cx - ---x - --- - --- x - ---x + F = 0
4B 4B 4B 4B 4B
Breaking up first bracket produces:
2 2 2 2
2 E 2 2DE D 2DE 2D 2E 2 2DE
Ax + --x + ---x + -- + Cx - ---x - --- - --- x - ---x + F = 0
4B 4B 4B 4B 4B 4B 4B
Some rearrangement produces:
2 2 2 2
2 E 2 2E 2 2DE 2DE 2DE D 2D
Ax + --x - --- x + Cx + ---x - ---x - ---x + -- - --- + F = 0
4B 4B 4B 4B 4B 4B 4B
Cancelling out and combining some terms produces:
2 2 2 2
2 E 2 2E 2 2DE - 4DE D - 2D
Ax + --x - -- x + Cx + --------- x + -------- + F = 0
4B 4B 4B 4B
Further reduction produces:
2 2 2
2 E - 2E 2 2DE D
Ax + -------- x + Cx - ---x - -- + F = 0
4B 4B 4B
Final cancellation out produces:
2 2
2 -E 2 DE D
Ax + --- x + Cx - -- x - -- + F = 0
4B 2B 4B
Expressing as a quadratic equation with parameter t produces:
2
Pt + Qt + R = 0
The final equation for the Y-axis:
| 2 | | | | 2 |
| E | 2 | DE | | D |
| A - -- | t + | C - -- | t + | F - -- | = 0
| 4B | | 2A | | 4B |
And for the X-axis:
| 2 | | | | 2 |
| E | 2 | CE | | C |
| B - -- | t + | D - -- | t + | F - -- | = 0
| 4A | | 2B | | 4A |
This produces terms:
Y-axis X-axis
| 2 | | 2 |
| E | | E |
P = | A - -- | P = | B - -- |
| 4B | | 4A |
| | | |
| DE | | CE |
Q = | C - -- | Q = | D - -- |
| 2A | | 2B |
| 2 | | 2 |
| D | | C |
R = | F - -- | R = | F - -- |
| 4B | | 4A |
Multiplying out by the common denominator produces:
The terms for both the X-axis and Y-axis are as follows:
X-axis Y-axis
----------------- -----------------
2 2
P = 4AB - E P = 4AB - E
Q = 4BC - 2DE Q = 4AD - 2CE
2 2
R = 4BF - D R = 4AF - C
----------------- -----------------
Q23. How do I render a filled rotated ellipse?
----------------------------------------------
Given an ellipse specified as a pair of centre point coordinates [c,d]
radii [r,s], and a rotation angle, the steps are as follows:
1. Convert the radii and centre point into an ellipse equation.
This converts [c,d] and [r,s] into [A,B,C,D,E,F]
2. Determine the minimum and maximum X and Y limits for the ellipse.
This generates [xmin,xmax,ymin,ymax] from [A,B,C,D,E,F]
width = xmax - xmin + 1
height = ymax - ymin + 1
3. Determine the starting X and Y coordinates from [xmin,ymin]
This generates [xp,yp] from [A,B,C,D,E,F] and [ymin]
4. Determine the value of the ellipse equation at [xmin,ymin]
and the derivatives for the X and Y axii:
2 2
d = Ax + By + Cx + Dy + Exy + F
dx = 2Ax + C + Ey
ddxx = 2A
dy = 2By + D + Ey
ddyy = 2B
ddxy = 2E
ddyx = 2E
5. Calculate the linear screen address of the first pixel:
ptr = screen_address( xmin, ymin )
dpitch = screen_width
6. Render the ellipse using the algorithm:
while ( height-- ) // For every scan-line
{
td = d; // Temporary copies for horizontal scanning
tdx = dx;
tdy = dy;
twidth = width;
while ( twidth-- ) // For every pixel on scan-line
{
if ( td <= 0 ) // Test pixel value
*ptr = color;
ptr += 1; // Horizontal increment
td += tdx;
tdx += ddxx;
tdy += ddyx;
}
ptr += dpitch; // Vertical increment
dy += ddyy;
dx += ddxy;
d += dy;
}
7. Finish
Note - to avoid overflow errors with 32-bit integers, it may be
convenient to translate the ellipse to the origin and adjust
the initial linear screen address accordingly.
The consequence of this is to set C and D to zero.
Q24. How do I render the outline of a rotated ellipse?
------------------------------------------------------
This algorithm was first developed by Bresenham during the 1960's.
Given an ellipse specified as a pair of centre point coordinates [c,d]
radii [r,s], and a rotation angle, the steps are as follows:
1. Convert the radii and centre point into an ellipse equation.
This converts [c,d] and [r,s] into [A,B,C,D,E,F]
2. Determine the minimum and maximum X and Y limits for the ellipse.
This generates [xmin,xmax,ymin,ymax] from [A,B,C,D,E,F]
3. Determine the starting X coordinate from the minimum Y coordinate
This generates [xp,yp] from [A,B,C,D,E,F] and [ymin]
4. Determine the value of the ellipse equation at [xmin,ymin]
and the derivatives for the X and Y axis:
2 2
d = Ax + By + Cx + Dy + Exy + F
dx = 2Ax + C + Ey
ddxx = 2A
dy = 2By + D + Ey
ddyy = 2B
ddxy = 2E
ddyx = 2E
5. Calculate the linear screen address of the first pixel:
ptr = screen_address( xmin, ymin )
dpitch = screen_width
6. Render the ellipse using the algorithm:
--------------------------------------
#define INCREMENT_X()\
{\
ptr += 1;\
xp += 1,\
d += dx;\
dx += ddxx;\
dy += ddxy;\
}
#define INCREMENT_Y()\
{\
ptr += dpitch;\
yp += 1;\
d += du;\
dx += ddyx;\
dy += ddyy;\
}
#define DECREMENT_X()\
{\
ptr -= 1;\
xp -= 1;\
dx -= ddxx;\
dy -= ddxy;\
d -= dx;\
}
#define DECREMENT_Y()\
{\
ptr -= dpitch;\
yp -= 1;\
dx -= ddyx;\
dy -= ddyy;\
d -= dy;\
}
while ( dx < -dy ) // Octant 0 (12:00 - 01:30)
{
PUTPIXEL( xp, yp, color );
INCREMENT_X();
if ( d > 0 )
INCREMENT_Y();
}
while ( dy < 0 ) // Octant 1 (01:30 - 03:00)
{
PUTPIXEL( xp, yp, color );
INCREMENT_Y();
if ( d < 0 )
INCREMENT_X();
}
while ( dy < dx ) // Octant 2 (03:00 - 04:30)
{
PUTPIXEL( xp, yp, color );
INCREMENT_Y();
if ( d > 0 )
DECREMENT_X();
}
while ( dx > 0 ) // Octant 3 (04:30 - 06:00)
{
PUTPIXEL( xp, yp, color );
DECREMENT_X();
if ( d < 0 )
INCREMENT_Y();
}
while ( -dx < dy ) // Octant 4 (06:00 - 07:30
{
PUTPIXEL( xp, yp, color );
DECREMENT_X();
if ( d > 0 )
DECREMENT_Y();
}
while ( dy > 0 ) // Octant 5 (07:30 - 09:00)
{
PUTPIXEL( xp, yp, color );
DECREMENT_Y();
if ( d < 0 )
DECREMENT_X();
}
while ( dx < dy ) // Octant 6 (09:00 - 10:30)
{
PUTPIXEL( xp, yp, color );
DECREMENT_Y();
if ( d > 0 )
INCREMENT_X();
}
while ( dx < 0 ) // Octant 7 (10:30 - 12:00)
{
PUTPIXEL( xp, yp, color );
INCREMENT_X();
if ( d < 0 )
DECREMENT_Y();
}
}
----------------------------------------
7. Finish
Note - to avoid overflow errors with 32-bit integers, it may be
convenient to translate the ellipse to the origin and recalculate
the initial starting pixel.
Thus the values of C are D are only used to calculate the offset
of the first pixel and are set to zero for all other calculations.