Patent Number:
6,674,435
Title:
Fast, symmetric, integer bezier curve to polygon conversion
Abstract:
A printer forms an approximate of a Bezier curve as a sequence of line segments. Two parametric equations, X(t) and Y(t), are employed. Two methods can be used to evaluate the parametric equations. Both use fixed point integer arithmetic to directly calculate points along the curve which are the values of the X(t) and Y(t) equations. The first method sets the number of steps of the parametric variable are equal to an integral power of 2. This gives a predictable execution time and uses line segments to connect the points as a piecewise straight line approximation to the curve. The number of steps is set as the next higher power of 2 than an estimated length of the curve. The second method allows Y(t), the scan line variable, to change only in predetermined integer steps. The value of X(t) is evaluated for each t corresponding to the integer step in Y(t). This second method has a natural advantage, if a closed path is being decomposed as a run array rather than a collection of trapezoids. Both methods create the lines segments in natural scan line order. This is advantageous for polygon fill algorithms because it eliminates the need for edge sorting.
Inventors:
Payne; Ralph E. (Dallas, TX), Boggs; Lowell (Lewisville, TX)
Assignee:
Texas Instruments Incorporated
International Classification:
G06F 17/17 (20060101); G06T 11/20 (20060101); G06T 011/00 ()
Expiration Date:
01/06/2021