2D Ellipse Technique Examined

last updated: 4-17-97

Frith on Usenet posted his fast method for drawing a circle that they had obtained from modifying Bresenham's circle algorithm ( that's what he said anyway ), which is what made me interested in drawing spheres and ellipsoids. Because I was trying to fit the method to ellipses, I learned more about the algorithm and have decided that the basic working idea behind it might work an any shape based on a 2nd order equation (this would be an equation where the highest power that any variable is raised to in the equation is 2). My conclusions also lead to my ability to convert it to drawing 3D objects (but drawing 3D objects has shown that this algorithm has some draw backs which I'm currently working on).

Drawing the ellipse is fairly straight forward because it follows a simple formula ((x^2) / (h^2)) + ((y^2) / (k^2)) = 1. Like the life formula, I'm going to do some algebraic manipulations on the equation to make it look like the line balance equation. I choose to show the ellipse drawing technique because the circle is just a special case condition that supports more optimization than the general ellipse algorithm.

Notice how all the fractions dissappeared! Fractions can get messy in algorithms and especially arithmetic that you are trying to reduce and remove division from.

Now I'll take the derivative with respect to x like I did with the line algorithm and we'll see what we get.

Now we are keen to notice that we still have some variables which haven't dissappeared yet. Let's take another derivative with respect to x.

This shows that a balance between the slope of the ellipse must be kept depending on where x and y are. This is basically the same as the line algorithm except it involves the slope of the ellipse instead of the points of a line being drawn. From this we can see our algorithm will have some simularities with the line drawing program. Now let's look at the slope of the ellipse:

Notice how it forms a balance equation similar to that of the line equation, but x and y are controlled by its own derivative. Let's now put a program together to represent this algorithm (again in C++ because that is the language I program in).


// x and y can be negative or positive, but h and k are presupposed to
// be positive values.
//
void DrawEllipse(int x, int y, int h, int k)
   {
   int slope_mn, slope_md;          //
   int position_mn, position_md;//  // Variables for slope calculation
   int x_position, y_position;  // Variables for position calculation
   int balance;                 //

   slope_md = k * k;  // Find md for the slope of the ellipse.
                      //    Notice it has to be positive.

   slope_mn = h * h;  // Find mn for the slope of the ellipse.
                      //    Notice this has to be positive too.

   // These positions for the ellipse's md and mn start it at the top.
   position_md = 0;  // The minimum value of md for the ellipse.
   position_mn = h * h * k;    // The maximum value of mn for the ellipse.

   x_position = 0;      // Start at the middle x of the ellipse.
   y_position = k;      // Start at the top y of the ellipse.

   balance = 0;              // Let's start at zero.

   // While not at the last x and y positions, go...
   while ((y_position > 0) || (x_position < h))
      {
      // Since an ellipse is refective in 4 quadrants, we can draw 4 points
      //    at a time.  With a circle you can draw 8 points at a time if you
      //    update the algorithm for that special case.
      DrawPointAt(x + x_position, y + y_position);
      DrawPointAt(x - x_position, y + y_position);
      DrawPointAt(x + x_position, y - y_position);
      DrawPointAt(x - x_position, y - y_position);

      if (balance < 0)    // If the balance leans toward x...
	 {
	 balance = balance + position_mn;  // Balance x with y.
         position_mn = position_mn - slope_mn;  // Move position slope mn down.
	 y_position = y_position - 1;      // Move y in the correct direction.
         }

      if (balance >= 0)   // If the balance leans toward y...
	 {
         position_md = position_md + slope_md;  // Move position slope md up.
         balance = balance - position_md;  // Balance y with x.
         x_position = x_position + 1;      // Move x in the correct direction.
         }
      }
   // The y position is zero, so we only need to draw two points.
   DrawPointAt(x + x_position, y);
   DrawPointAt(x - x_position, y);
   }

All of my algorithms presuppose that you won't make your shapes so that the numbers get too big. In the age of 32 bit computers, long signed integers can be about +/- 2,147,483,648. Because I'd like to think everyone would keep their k's, h's, x's, and y's limited, I think this algorithm should work if these never get larger than 1000 (if some are small, others can be bigger).

Now let's get down to how the code works. The first two statements define the slope of the slope of the ellipse. Those are the equivalent of the line equation since the second derivative of the ellipse matched the first derivative of the line. Since each one is the square of a number and we defined k and h as positive, both slopes are garanteed to be positive.

The next group of statements defines the slope values for the ellipse (first derivative) at the very beginning. In the beginning we are at the top of the ellipse, so mn, the y component, would be zero and md, the x component, would be its value when x is at its maximum distance, h. The next group is similar and defines the positions for x and y to start at with x in the middle equal to zero, and y at the top equal to k.

This time I use a zero balance and because I'm still considering what a good balancing factor would be. This means we'll find a point at the top and bottom of our ellipse that looks out of place (this should only be slight).

Now we have to deal with the loop. By looking at the line algorithm, you can see that there are only two conditionals that control everything using the balancing the equations we have. Because of this, I think that 3rd order shapes may be the same except take another set of conditionals.

I've tested this algorithm and saw that it worked. If you have any questions or problems, please contact me so that I can either fix or clarify something.


joshuacantrell@yahoo.com

(My Home Page) - (My Personal Page) - (My Computer Science Page) - (My Resume)