Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-08-24
2004-01-06
Razavi, Michael (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S440000, C345S442000, C345S443000, C382S241000, C382S242000
Reexamination Certificate
active
06674435
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The technical field of this invention is conversion of Bezier curves to visually attractive line segment approximations that can be quickly drawn or manipulated as polygons.
BACKGROUND OF THE INVENTION
Bezier curves are mathematically described curves. A Bezier curve of order n is given by the parametric equation in u of:
P
(
u
)
=
∑
i
=
0
n
P
i
n
!
i
!
(
n
-
i
)
!
u
i
(
1
-
u
)
n
-
1
(
1
)
where: u is the parametric variable, u=0 yields the beginning point and u=1 yields the end point; n is the order of the Bezier curve; i is an index variable for the summation; and P
i
are control points for the Bezier curve. The Bezier curve intersects the first and last control points and has a shape determined by the intermediate control points and the order.
Most computer generated Bezier curves are limited to an order of 3. A Bezier curve of order 3 is given by the equation:
P
(
u
)
=P
0
(1
−u
)
3
+P
1
3
u
(1
−u
)
2
+P
2
3
u
2
(1
−u
)+
P
3
u
3
(2)
where: P
0
, P
1
, P
2
and P
3
are the control points expressed in (x,y) coordinates. Bezier curves of order 3 are specified with 4 controlling points. The first point P
0
and the fourth point P
3
define the respective beginning point and end point of the curve. The slope of the curve at the beginning point corresponds to the slope of the line segment joining the first point P
0
and the second point P
1
. The slope at the end point corresponds to the slope of the line segment joining the third point P
2
and the fourth point P
3
.
Many computer programs draw using curves defined via Bezier equations. There are prior art techniques for rendering these curves into a series of points that can be displayed or printed. One known technique uses known mathematics to split the Bezier curve into two halves, each half also being a Bezier curve. This technique is described in the book, Principles of Interactive Computer Graphics, by Newman and Sproull (1979). Following splitting, each half is tested to determine if it is “approximately” straight. The method proceeds recursively splitting the curve into equal halves until the each half is “approximately” straight. These approximately straight sections are rendered as line segments. The approximations produced by this recursive decomposition method are somewhat attractive, in that they are slightly asymmetric. Further, there is a significant amount of computational overhead associated with the recursion process itself and with determining whether or not the curve is “approximately” straight. This technique produces line segments in the order of the binary decomposition. This is a scramble of the order necessary for the later polygon or trapezoid processing often used in graphics applications. Thus the line segments must be re-ordered, requiring additional processing time.
It is possible to directly compute points on the Bezier curve from the definition equations. These calculations generally require floating point numbers due to the dynamic range of the quantities involved. Such direct calculation using floating point numbers can be performed using a floating point unit attached to the data processor. This involves an additional expense for the additional hardware of the floating point unit. It is possible to emulate floating point computations on an integer processor, but this is very time consuming.
There are integer approximation techniques for drawing Bezier curves into a pixel map of the image. These techniques involve comparison of the slope of the curve at a particular point and determination of which of the eight adjacent points is the next point to be plotted. This technique thus provides a raster scan rendered curve. For some applications this advantageously bypasses a step of rendering a line segment. In other cases, the line segments are needed for later polygon or trapezoid processing, thus the line segments must be determined from the pixel by pixel plot. This technique is best suited for rendering for computer monitors rather than printers. Surprisingly, printers typically require faster rendering performance that computer monitors. Computer monitors typically are updated from a pixel map memory. Thus the curve can be rendered into the pixel map memory much slower than the speed of the display. Printers typically do not store entire pixel maps due to the much greater number of pixels on a printed page than on a computer monitor. Typical printers render the page into stripes or bands, thus reducing the storage requirements. However, once started on printing a page many color laser printers cannot be slowed or stopped without spoiling the page. The print driver thus must provide data at the speed of the printer. Thus this pixel by pixel rendering of a Bezier curve typically is too slow for use with color laser printers.
SUMMARY OF THE INVENTION
A major problem using Bezier curves and the known techniques is conversion into a raster scan form that can be printed via a color laser printer. The rendering must be as fast as print engine forming the dots on the page. It is generally better to render Bezier curves into line segments for polygon or trapezoid processing, such as determining polygon clipping and occlusion. Such processes are speeded if the line segments are produced in scan order.
In order to approximate the specified Bezier curve as a sequence of line segments, it is necessary to use 2 parametric equations, X(t) and Y(t) each of which is a third degree polynomial in t whose value ranges from 0.0 to 1.0. 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 gives a predictable execution time and uses line segments to connect the points as a piecewise straight line approximation to 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). Since X(t) can be multi-valued for each scan line, it is necessary to guarantee that the scan line is closed at the inflection points of the Bezier curve. This second method gives a new x value for each scan line. This 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.
REFERENCES:
patent: 4620287 (1986-10-01), Yam
patent: 4855935 (1989-08-01), Lien et al.
patent: 5241654 (1993-08-01), Kai et al.
patent: 5253336 (1993-10-01), Yamada
patent: 5287441 (1994-02-01), Nakamura
patent: 5309521 (1994-05-01), Matsukawa
patent: 5337404 (1994-08-01), Baudelaire et al.
patent: 5363479 (1994-11-01), Olynyk
patent: 5367617 (1994-11-01), Goossen et al.
patent: 5422990 (1995-06-01), Siverbrook et al.
patent: 5471573 (1995-11-01), Kaasila
patent: 5500927 (1996-03-01), Sander-Cederlof et al.
patent: 5638503 (1997-06-01), Hoel
patent: 5694535 (1997-12-01), Broekhuijsen
patent: 5717905 (1998-02-01), Iwamoto et al.
patent: 5731820 (1998-03-01), Broekhuijsen
patent: 5857067 (1999-01-01), Hassett et al.
patent: 5877743 (1999-03-01), Dzik
patent: 6111588 (2000-08-01), Newell
patent: 6137500 (2000-10-01), Silverbrook et al.
Boggs Lowell
Payne Ralph E.
Brady III W. James
Chung Daniel J
Marshall, Jr. Robert D.
Razavi Michael
LandOfFree
Fast, symmetric, integer bezier curve to polygon conversion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast, symmetric, integer bezier curve to polygon conversion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast, symmetric, integer bezier curve to polygon conversion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3217832