Fast, symmetric, integer bezier curve to polygon conversion
US6674435B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 24, 1999 |
| Grant date | Jan 6, 2004 |
| Priority date | — |
| Expiry date | Aug 24, 2019 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T11/203
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.