The Quadratic Curves, Circles and Ellipses FAQ ============================================== Version 1.4 28th December 2001 ------------------------------- This FAQ is now maintained by "andreas@(no-spam)cs.ualberta.ca". Any additional suggestions or related questions are welcome. Just send E-mail to the above address. The latest copy of this FAQ can be found at the following web page: http://www.cs.ualberta.ca/~andreas/math/curvfaq_latest.html Feel free to distribute or copy this FAQ as you please. Contributions ------------- Appearance: Cleaned out some of the empty lines, made the header like the matrfaq: Andreas Junghanns History ------- I (Andreas) received this FAQ from "Sylvain Carette" by email. I tried to find "hexapod@(no-spam)netcom.com" who seemed to have maintained this (as others) for a while, but the site at netcom.com doesn't exist anymore, emails bounce. Since I (and colleques) wasted quite some time figuring out what was wrong with some of the algorithms given in the earlier versions of this document, I decided to correct it and put it back on the web. The formerly given sites for the location of these documents do not exist anymore: ftp://ftp.netcom.com/pub/he/hexapod/index.html http://www.glue.umd.edu/~rsrodger Versions, dates and links to local copies (so you can compare): curvfaq_1.03.html: Version 1.3 17th March 1998 curvfaq_1.04.html: Version 1.4 28th December 2001 Please refrain from asking me math questions. I am only maintaining this FAQ and have very little knowledge about the subject. But, if you have a question that is not answered by this FAQ and later happen to find the answer and believe it to be relevant for this FAQ (or its readers), please send all relevant information, hopefully in a pre-digested form, to me to be included here. Thanks! If you prefer to appear as "anonymous" in the contributions list, let me know, otherwise I'll just put you down with whatever name I can gather from your email header. 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.