Method for fast generation of parametric curves employing a pre-calculated number of line segments in accordance with a determined error threshold

• US 5,408,598 A
• Filed: 02/25/1994
• Issued: 04/18/1995
• Est. Priority Date: 05/23/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pryor, Duaine W. Jr.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/202,678
• Time in Patent Office: 417 Days
• Field of Search: 395/141-143, 395/119, 395/123, 395/127, 395/133, 395/-140, 395/155, 395/150, 395/151
• US Class Current: 345/442
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A method enables the prediction of the number of subdivisions of a curve that will be required by control polygons to assure that a resulting straight line representation of the curve will not exceed a preset error threshold. The method is applicable to cubics and parametric quadratics including parabolas, ellipses and hyperbolas. In each case, the prediction of the number of subdivisions eliminates the need for a detailed error calculation at each subdivision step, thereby enabling an error calculation to be carried out only once in the process.

Claims

1. A computer graphics method for approximating a curve having beginning and end coordinates by a series of connected straight line segments, said method employing a recursive subdivision of said curve and control polygons, each control polygon having at least a first straight line segment extending between two coordinates on said curve and additional connecting line segments to create a closed plane figure, a maximum distance between said first straight line segment and said curve defined as an error value, said method comprising computer implemented the steps of:

a. establishing an error value threshold Δ

_E between a said first straight line segment of a control polygon and said curve;

b. establishing a control polygon whose first straight line segment has terminal vertices coincident with said curve'"'"'s beginning and end coordinates, calculating an error value for said control polygon and testing said error value to determine if it exceeds Δ

_E and if yes;

c. modifying said calculated error value by a factor and testing said modified error value to determine if it is greater than Δ

_E, and if it is, again modifying said modified error value by said same factor, and repeating said test, said modifying action being repeated on a last modified value until a new modified value is equal to or less than Δ

_E ;

d. establishing 2ⁿ control polygons between said curve'"'"'s beginning and end coordinates, where n equals the number of error values calculated in steps b and c;

e. creating an approximated curve by enabling joinder of said first straight line segments of each said 2ⁿ control polygons; and

f. displaying the approximated curve on a computer display, whereby a display delay time for the step of displaying is related to an execution time for the computer graphics method.

2. The method as recited in claim 1 wherein said curve is a cubic function and said error value in step b is m which is calculated using the expression:

##EQU47## where;

x" and y" are second derivatives of coordinate functions.

3. The method as recited in claim 2, wherein said modifying step includes a division of the calculated value of m by four.

4. The method as recited in claim 1 wherein said curve is a cubic function and said error value in step b is L which is calculated using the expression:

##EQU48## where;

x" and y" are second derivatives of coordinate functions.

5. The method as recited in claim 4 wherein said modifying step includes the subtraction of one from L.

6. The method as recited in claim 1, wherein said curve is a conic function, said method including the additional steps of:

identifying the curve type to be one of the group;

hyperbola, ellipse;

if said curve is determined to be a hyperbola, calculating a said error value for said curve in step (b) as follows;

##EQU49## if said curve is identified as an ellipse, calculating said error value for said curve in step (b) as follows;

##EQU50## where;

w₀, w₁ are curve weight values at curve coordinates 0 and 1, respectively;

t=time; and

a₁, a₂ are either coordinate values x₁, x₂ or y₁, y₂, as the case may be.

7. The method as recited in claim 6 wherein said modifying step includes a division of the calculated value of said error value by four.

8. The method as recited in claim 6 wherein said error value is calculated using the expression L=Log₄ (m).

9. The method as recited in claim 8 wherein said modifying step includes the reduction of the value of L by one.

10. The method of claim 6 wherein said conic curve has beginning and end coordinates x(0), y(0), w(0) and x(1), y(1), w (1), and wherein step (a) identifies the curve type by the expressions

11. A computer graphics incremental method for approximating a cubic curve, having beginning and end coordinates, by a series of connected straight line segments, said method predicting the number of steps required to achieve a desired error threshold Δ

_E between the curve and a series of polygon line segments, wherein Δ

_E is a maximum distance between said curve and a line segment connecting two coordinates on said curve, each said line segment forming a portion of a polygon, said method comprising computer implemented steps of;

a) computing ##EQU51## b) choosing a step size t=2^-L ;

c) computing x(0), x_t (0), x_tt (0), x_ttt (0) to a precision Δ

_E 2^-L ;

d) computing y(0), y_t (0), y_tt (0), y_ttt (0) to a precision Δ

_E 2^-L ; and

e) for (t=Δ

t to 1, by Δ

t increments) computing;

space="preserve" listing-type="equation">x(t)=x(t-Δ

t)+x.sub.t (t-Δ

t),

space="preserve" listing-type="equation">x.sub.t (t)=x.sub.t (t-Δ

t)+x.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">x.sub.tt (t)=x.sub.tt (t-Δ

t)+x.sub.ttt (t-Δ

t),

space="preserve" listing-type="equation">y(t)=y(t-Δ

t)+y.sub.t (t-Δ

t),

space="preserve" listing-type="equation">y.sub.t (t)=y.sub.t (t-Δ

t)+y.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">y.sub.tt (t)=y.sub.tt (t-Δ

t)+y.sub.ttt (t-Δ

t), and

drawing a line from x(t-Δ

t), y(t-Δ

t) to x(t), y(t) for each Δ

t increment to create an approximated curve

where;

L=number of curve subdivisions;

t=time;

x(0), y(0) are x and y coordinate functions at curve point t=0, etc.

space="preserve" listing-type="equation">x(0)=x coordinate function at t=0,

space="preserve" listing-type="equation">x.sub.t (0)=x.sub.t (t.sub.0 -Δ

t)-x(t.sub.0),

space="preserve" listing-type="equation">x.sub.tt (0)=x.sub.t (t.sub.0 +Δ

t)-x.sub.t (t.sub.0),

space="preserve" listing-type="equation">x.sub.ttt (0)=x.sub.tt (t.sub.0 +Δ

t) -x.sub.tt (t.sub.0),

space="preserve" listing-type="equation">y(0)=y coordinate function at t=0,

space="preserve" listing-type="equation">y.sub.t (0)=y.sub.t (t.sub.0 -Δ

t)-y(t.sub.0),

space="preserve" listing-type="equation">y.sub.tt (0)=y.sub.t (t.sub.0 +Δ

t)-y.sub.t (t.sub.0),

space="preserve" listing-type="equation">y.sub.ttt (0)=y.sub.tt (t.sub.0 +Δ

t) -y.sub.tt (t.sub.0), and

displaying the approximated curve on a computer display, whereby a display delay time for the step of displaying is related to an execution time for the computer graphics method.

12. A computer graphics incremental method for approximating an ellipse, having beginning and end coordinates, by a series of connected straight line segments, said method predicting the number of steps required to achieve a desired error threshold Δ

_E between an ellipse and a series of line segments, wherein Δ

_E is a maximum distance between said ellipse and a line segment connecting two coordinates on said ellipse, said method comprising computer implemented steps of;

a) computing L=log₄ (m_ellipse) where ##EQU52## b) choosing a step size Δ

t=2^-L c) computing X(

     0), X_t (0), X_tt (0) to a precision Δ

_E 2^-L ;

d) computing Y(0), Y_t (0), Y_tt (0) to a precision Δ

_E 2^-L ;

e) computing w(0), w_t (0), w_tt (0) to a precision Δ

_E 2^-L ; and

f) for (t=Δ

t to 1, by Δ

t increments) computing

space="preserve" listing-type="equation">X(t)=X(t-Δ

t)+X.sub.t (t-Δ

t),

space="preserve" listing-type="equation">X.sub.t (t)=X.sub.t (t-Δ

t)+X.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">Y(t)=Y(t-Δ

t)+Y.sub.t (t-Δ

t),

space="preserve" listing-type="equation">Y.sub.t (t)=Y.sub.t (t-Δ

t)+Y.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">w(t)-w(t-Δ

t)+w.sub.t (t-Δ

t),

space="preserve" listing-type="equation">w.sub.t (t)=w.sub.t (t-Δ

t)+w.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">x(t)=X(t)/w(t),

space="preserve" listing-type="equation">y(t)=y(t)/w(t), and

drawing a line from x(t-Δ

t), y(t-Δ

t) to x(t), y(t) for each Δ

t increment to create an approximated curve

where;

L=number of curve subdivisions;

w₀, w₁ are curve weight and values at curve coordinates 0 and 1, respectively;

t=time;

a₁, a₂ are either coordinate values x₁, x₂ or y₁, y₂, as the case may be;

space="preserve" listing-type="equation">X(0)=X(0)w(0)(at t=0);

space="preserve" listing-type="equation">X.sub.t (0)=X0)(t.sub.0 +Δ

t)-X(0)(t.sub.0);

space="preserve" listing-type="equation">X.sub.tt (0)=X.sub.t (0)(t.sub.0 +Δ

t)-X.sub.t (0)(t.sub.0);

space="preserve" listing-type="equation">X.sub.tt (0)=X.sub.tt (0)(t.sub.0 +Δ

t)-X.sub.t (0)(t.sub.0);

space="preserve" listing-type="equation">w(0)=weight of curve at t=0;

space="preserve" listing-type="equation">w.sub.t (0)=w(0)(t.sub.0 +Δ

t)-w(0)(t.sub.0);

space="preserve" listing-type="equation">w.sub.tt (0)=w.sub.t (0)(t.sub.0 +Δ

t)-w.sub.t (0)(t.sub.0); and

displaying the approximated curve on a computer display, whereby a display delay time for the step of displaying is related to an execution time for the computer graphics method.

13. A computer graphics incremental method for approximating a hyperbola, having beginning and end coordinates, by a series of connected straight line segments, said method predicting the number of steps L required to achieve a desired error threshold Δ

_E between an hyperbola and a series of line segments, wherein Δ

_E is a maximum distance between said hyperbola and a line segment connecting two coordinates on said hyperbola, said method comprising computer implemented steps of;

a) computing L=log₄ (m_hyperbola) where m_hyperbola = ##EQU53## b) choosing a step size Δ

t=2^-L c) computing X(

     0), X_t (0), X_tt (0) to a precision Δ

_E 2^-L ;

d) computing Y(0), Y_t (0), Y_tt (0) to a precision Δ

_E 2^-L ;

e) computing w(0), w_t (0), w_tt (0) to a precision Δ

_E 2^-L ; and

f) for (t=Δ

t to 1, by Δ

t increments) computing

space="preserve" listing-type="equation">X(t)=X(t-Δ

t)+X.sub.t (t-Δ

t),

space="preserve" listing-type="equation">x.sub.t (t)=X.sub.t (t-Δ

t)+X.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">Y(t)=Y(t-Δ

t)+y.sub.t (t-Δ

t),

space="preserve" listing-type="equation">y.sub.t (t)=y.sub.t (t-Δ

t)+y.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">w(t)=w(t-Δ

t)+w.sub.t (t-Δ

t),

space="preserve" listing-type="equation">w.sub.t (t)=w.sub.t (t-Δ

t)+w.sub.tt (t-Δ

t),

space="preserve" listing-type="equation">x(t)=X(t)/w(t),

space="preserve" listing-type="equation">y(t)=Y(t)/w(t), and

drawing a line from x(t-Δ

t), y(t-Δ

t) to x(t), y(t) for each Δ

t increment to create an approximated curve

where;

L=number of curve subdivisions;

w₀, w₁ are curve weight and values at curve coordinates 0 and 1, respectively;

t=time;

a₁, a₂ are either coordinate values x₁, x₂ or y₁, y₂, as the case may be;

space="preserve" listing-type="equation">X(0)=X(0) w(0)(at t=0);

space="preserve" listing-type="equation">X.sub.t (0)=X(0)(t+Δ

t)-X(0)(t.sub.0);

space="preserve" listing-type="equation">X.sub.tt (0)=x.sub.t (0)(t.sub.0 +Δ

t)-X.sub.t (0)(t.sub.0);

space="preserve" listing-type="equation">X.sub.ttt (0)=X.sub.tt (0)(t.sub.0 +Δ

t)-X.sub.tt (0)(t.sub.0);

space="preserve" listing-type="equation">w(0)=weight of curve at t=0;

space="preserve" listing-type="equation">w.sub.t (0)=w(0)(t.sub.0 +Δ

t)-w(0)(t.sub.0);

space="preserve" listing-type="equation">w.sub.tt (0)=w.sub.t (0)(t.sub.0 +Δ

t)-w.sub.t (0)(t.sub.0); and

displaying the approximated curve on a computer display, whereby a display delay time for the step of displaying is related to an execution time for the computer graphics method.

14. A computer graphics system for approximating a curve having beginning and end coordinates by a series of connected straight line segments, said system employing a recursive subdivision procedure for said curve and control polygons to accomplish subdivision of said curve, each control polygon having at least a first straight line segment extending between two coordinates on said curve and additional connecting line segments to create a closed plane figure, a maximum distance between said first straight line segment and said curve defined as an error value, said system including a stored error value threshold Δ

_E, said system comprising;

means for establishing a control polygon whose first straight line segment has terminal vertices coincident with beginning and end coordinates of said curve;

means for calculating an error value for said control polygon and testing said error value to determine if it exceeds Δ

_E and if yes, modifying said error value that was calculated by a factor and testing said modified error value to determine if said modified error value is greater than Δ

_E, and if yes, again modifying said modified error value by said same factor and repeating said testing, said modifying being repeated on a last modified value by said means for calculating until a new modified value is equal to or less than Δ

_E ;

means for establishing 2ⁿ control polygons between said beginning and end coordinates of said curve, where n equals a number of error values calculated by said means for calculating; and

means for creating an approximated curve by joining said first straight line segments of each of said 2ⁿ control polygons and displaying the approximated curve.