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.

Discuss this article in the forums


Date this article was posted to GameDev.net: 7/29/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!