Browse Prior Art Database

Drawing Approximate Ellipses When Overflow Interferes With Exact Computation

IP.com Disclosure Number: IPCOM000060377D
Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Makowka, CD: AUTHOR

Abstract

A technique is described whereby the ability to print or display ellipses, from computer computations, is enhanced through an iterative method of arriving at arc parameters for a related ellipse that will approximate the original ellipse. Drawing or displaying part or all of an ellipse using finite precision integer arithmetic produced by a microprocessor is difficult because the quadratic equation describing the ellipse leads to a computer overflow, thereby producing errors during the printing or displaying of the ellipse. The technique described herein provides a reasonable approximation of the ellipse that can be drawn without the errors resulting from an overflow condition.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

Drawing Approximate Ellipses When Overflow Interferes With Exact Computation

A technique is described whereby the ability to print or display ellipses, from computer computations, is enhanced through an iterative method of arriving at arc parameters for a related ellipse that will approximate the original ellipse. Drawing or displaying part or all of an ellipse using finite precision integer arithmetic produced by a microprocessor is difficult because the quadratic equation describing the ellipse leads to a computer overflow, thereby producing errors during the printing or displaying of the ellipse. The technique described herein provides a reasonable approximation of the ellipse that can be drawn without the errors resulting from an overflow condition. Assuming the ellipse is centered at the origin, the equation for the ellipse is written: a x2 + b y2 + 2c xy = d When the shape of the ellipse, with the circle as a special case, is specified by four arc parameters P, Q, R, and S that specify the transformation of a unit circle to the ellipse, then a = Q2 + S2 b = P2 + R2 c = -(RQ + SP) d - represents a constant to reflect the size of the ellipse. Since each of the x, y, and arc parameters can be sixteen bit integers, sixty-four bits of precision are needed to represent the equation without the risk of overflow. However, microprocessors used in peripherals that print or display the ellipse will use thirty-two bit integers that may overflow. Therefore, the following steps are implemented to present a recursive approach in responding to an overflow: 1. Attempt to draw the ellipse or arc with the current arc parameters. 2. If an overflow occurs, divide all arc parameters by four. P = P/4; Q = Q/4; R=R/4; S=S/4. 3. If the arc parameters are not degenerate (the area of the ellipse, proportional to PQ - RS, is not zero), then go back to step 1. 4. Otherwise, use a suitable line approximation (parallelogram for ellipse, lines between defining points for an arc) in place of drawing the arc. Straight lines represent the minimum approximations of the curve....