Circles, Ellipses, and General Implicit Functions

Circles

Ellipse


Circles

A brute force algorithm would be to use the circle equation:
r2 = (x - xc)2 + (y - yc)2 or y = yc (r2 - (x - xc)2)1/2

But this is very expensive and gives nonuniform pixel spacing.
Second try: use Polar Coordinates:

x = xc + r cos q    step q
y = yc + r sin q
>

Could set step size yr and get uniform density about 1 pixel apart. But this is still computationally expensive ( computing sin, cos ). Use the Decision Variable Method (Bresenham). We can compute in one octant then use symmetry. So can compute 1 point then plot 8 points as below:

Assume xc = yc = 0 (simple offset) so x2 + y2 = R2
use the 2nd octant and go from x = 0 to x = y = (R / 2)1/2.
so will step x by 1 and choose y. In general have

Can discard points 1, 4, 6 since x increases. Also, discard 1, 2, 3 since y decreases, so we need to choose between 5, 7, 8. The slope of the circle must lie between the slope of the lines defined as pi -> x with x = 5, 7, 8. The slope of pi -> 5 = 0, pi -> 8 = -1, pi -> 7 = undefined. The slope of a circle in the second octant: dy / dx = -x / y so at x = 0, slope = 0 and at x = y, slope = -1. Hence use points. 5, 8 and reject 7.

so have:

y2 = r2 - (xi + 1)2
d1 = y i2 - y2 = yi2 - r2 + (xi + 1)2
d2 = y2 - (y i - 1)2 = r2 - (xi + 1)2 - (yi - 1)2


(1) pi = d1 - d2 = 2(xi + 1) 2 + yi2 + (yi - 1)2 - 2r2
if pi < 0 choose yi {d2> d1}
else choose yi - 1  {d2 < d1, pi> 0}
Now, as before (with the line equation), we can derive

Pi+1 = Pi  + 4x i + 6 + 2(yi+12 - yi2) - 2(yi+1 - yi)

so if Pi < 0, {choose yi} {yi+1="yi}" pi+1="Pi" + 4xi + 6

 else {pi > 0, choose yi-1} {yi+1="yi-1}" pi+1="P" i + 4(xi yi) + 10 
now compute p1 from (1): at x1, y1 x1="0," y1="r" so p 1="3" 2r 

Circle Algorithm:

  1. Plot initial pts (0,R) 8 pts
  2. P1 = 3 - 2r
  3. if P1 0 then next pt. is (x1 + 1, y1) else next pt. is (x1 + 1, y 1 1)
  4. if P1 0 p2="P1" + 4x1 + 6 else p2="P1" + 4(x1 y1) + 10
  5. Repeat 3,4 until x = y

Note integer Addition/Subtraction, multiplication by power of 2. The aspect ratio for monitors is usually 4/3 = 1.33. If the pixels are not "square" then a correction must be made, else the circle will look like an ellipse. For example, in the CGA Mode 6, the pixel resolution is 640/200 = 3.2, so the correction = 3.2/1.33= 2.40.

Return to menu


Ellipses

Look at ellipse - use same method but equation is ay^2 + bx^2 - ab = 0. Ellipse has 4 fold symmetry so use 1st quadrant so x1 = 0 , xf = a

>Must determine pixel choices from slope:

So initially choice is between 5 & 8 and then between 7 & 8.

Find change over point.
Slope = dy / dx = -bx/ay (x, y both positive in 1st quadrant)
so when ay < bx then slope < 1 and choose between 7, 8
{Note: complete derivation for ellipse in Dr. Dobb's Journal, May 1985 p.40-48}
We can use the Decision variable method to display any function of form y = f(x). (Remember: changes in slope) Generally easier to use Line segments but not as pretty or fast.

>May want to plot ARCS or part of curve. Can do as above just compute initial, final pts. Example: Start at x1 and only use 1st and 2nd octant symmetry.

Return to menu

 

Output Primitives menu
HyperGraph Table of Contents.
HyperGraph Home page.

Last changed May 13, 1998, G. Scott Owen, owen@siggraph.org