Computer systems are highly useful for compiling and assimilating large amounts of data. Computer systems frequently include graphic displays capable of displaying curves. FIG. 1 illustrates a curve 2 that may be displayed on a typical graphics display system.
Graphics display systems generally include a memory for storing a digital representation of the curve to be displayed. In a primitive system this might include an extremely large memory that stores a digital value which represents the curve to be displayed. A high-resolution display system using this method would require an extremely large memory. Such a primitive system would be too slow when initially generating the digital values which represent the curve, and would also be slow when manipulating the curve, such as when the curve is rotated or relocated on the display. Because of these problems, many computer display systems utilize the Bezier spline method of modeling curves.
A Bezier spline, often referred to as a Bezier curve, is a mathematical construct for curves and curved surfaces. The most frequently used Bezier curve for two-dimensional graphic systems is the cubic Bezier curve. A cubic Bezier curve requires four control points which define the curve. Once the four points are specified, the curve is defined. However, as is well known to those skilled in the art, higher order Bezier curves may be used to create highly complex curves in two, three or higher dimensions.
To use cubic Bezier curves to construct an arbitrary curve such as curve 2 of FIG. 1, the curve may be partitioned into a number of individual arcs. This is illustrated in FIG. 1 wherein the curve 2 is divided into three arcs. Between points 4 and 6 curve 2 is divided into an arc 8, between points 6 and 10 curve 2 is divided into an arc 12, and between points 10 and 14 curve 2 is divided into an arc 16. To construct the arc 8 using a cubic Bezier curve, the arc end points 4 and 6 plus two additional points, control points 18 and 20, are selected. By properly selecting the control points 18 and 20 and the end points 4 and 6, the arc 8 can be generated using a well known reiterative process. This process is repeated for arcs 12 and 16 and their selected control points. Thus, the curve 2 can be defined by ten Bezier control points. In a similar manner, almost any desired curve can be generated from a set of selected control points using the Bezier curve technique.
While Bezier curves permit a curve to be described by a small set of data points, when the Bezier curve itself is to be displayed on a display screen the data values for the sequence of points on the display screen, called pixels, that trace out the curve must be specified. Since determining each and every data point on an arc of a curve is a slow, computationally inefficient process, it has been found highly beneficial to approximate the Bezier curve. An advantage of doing this is that the Bezier curve can be approximated very closely by a finite set of line segments. The number of line segments required depends upon several factors including the rate of curvature of the desired curve and the resolution of the display screen. Approximating an arc by a finite set of straight lines segments is particularly advantageous because determining the set of points comprising a line segment can be done very efficiently. The reduction of a Bezier curve into a set of straight line segments that approximates the curve, or at least an arc of the curve, is called "rendering" the curve.
Note that the above discussion is equally applicable to printers as well as display screens. The pixel size on a typical laser printer is different from the pixel size on a typical video display screen. However, the same problems encountered in rendering a Bezier curve on a display screen are present when rendering a curve on a laser printer or any other type of graphics printer.
A typical prior art method of rendering the Bezier curve is illustrated in FIG. 2 wherein an arc 22 is to be closely approximated by a set of line segments. Two control points referred to as end points 24 and 26 of the arc 22 together with control points 28 and 30 define the arc 22 via a cubic Bezier curve. These four control points are determined in a well known manner. The initial step in rendering the curve is to determine whether the line segment 38 extending between points 24 and 26 is a "close enough" approximation to the arc 22 that the line segment can be displayed as an approximation of the arc 22. If the line segments are within the resolution of the display screen (i.e., within a pixel of where the actual arc should be located on the screen), then further computations will yield no improvement in the display. The actual resolution depends on the display device. For example, on a typical video display terminal, there are 72 pixels per inch, while a laser printer has 300 or even 600 pixels per inch. Thus, the degree of accuracy of calculations depends on the display device.
A typical prior an method of determining the amount of error is to form a line segment 38 extending between points 24 and 26. Then the magnitude of a line segment 40, perpendicular to line segment 38 and extending through control point 28, and the magnitude of a line segment 42, also perpendicular to line segment 38 but extending through point 30, are determined. The magnitudes of the line segments 40 and 42 are then checked as to whether they are both smaller than a predetermined test magnitude, such as the dimension of one pixel. If line segments 40 and 42 are both smaller than the test magnitude, the line segment 38 is deemed to be a close enough approximation of the arc 22 that it can be displayed as the arc.
However, if the magnitude of either of the line segments 40 or 42 is greater than the test magnitude, the line segment 38 is not a sufficiently accurate representation of the arc 22 and is an unsuitable approximation of the arc for display purposes. In that event, the arc 22 is subdivided into two parts, each defined by four control points. The four control points for each part are determined as follows. First, the midpoint of each of line segments 32, 34, and 36 is determined, specifically points 44, 46, and 48, respectively. Next the midpoints of line segments extending between points 44 and 46 and between points 46 and 48 are determined, specifically points 50 and 52, respectively. Finally, the midpoint of a line segment 54 drawn between the points 50 and 52 is determined, that point being point 56. The arc 22 passes through point 56. At point 56, the arc 22 is tangent to the line segment 54 connecting points 50 and 52. The two portions of the arc 22 can now be defined.
The first portion 22a of arc 22 is defined using points 24, 44, 50, and 56 as Bezier control points and the second portion 22b of arc 22 is defined by using points 56, 52, 48, and 26 as Bezier control points. After the two portions 22a and 22b of arc 22 are found, the line segments between the Bezier end points 24 and 56 for curve portion 22a and 56 and 26 for curve portion 22b, respectively are then tested using the procedure described above to determine whether they are a sufficiently accurate approximation of their respective are portions 22a and 22b that they can be used to display that portion of the arc 22. If one or more of the arc portions are not defined closely enough by a line segment drawn through the respective control points, the Bezier curve for that arc portion is subdivided using the above procedure. The procedure is reiterated until each portion of the arc 22 is deemed to be closely enough approximated for display purposes by a resulting set of line segments.
By continuing the above process it is possible to approximate the arc 22 to any desired degree of accuracy. It is very important to stop the rendering of the Bezier curve when a given set of line segments approximate the arc with sufficient accuracy that a more accurate set of line segments is not required. This is because of the very large number of mathematical operations required to render a highly accurate curve, because most computer graphics systems, whether display screens or printers, are typically low resolution devices, because the amount of memory required to store the resulting set of line segments grows quickly as the accuracy of the approximation increases, and because of the finite speed of computer graphic systems.
The above prior an technique of determining when a set of line segments closely approximates a Bezier curve is computationally inefficient. The prior art technique requires the determination of the lengths of the line segments 40 and 42. It requires in each reiteration finding of the shortest distance between two Bezier control points and a line segment, such as control points 28 and 30 and the line segment 38. To do this, the location of points 57 and 58 must be determined so that the magnitudes of the line segments 40 and 42 can be calculated. Calculating the location of points 57 and 58 is computationally inefficient; this inefficiency becomes highly pronounced when performed the large number of times required by some computer graphic displays when rendering the curve.
Another prior art method of rendering a Bezier curve is to repeatedly subdivide a curve, without performing a closeness test, until the individual line segments between control points are only one pixel long. This method results in a curve that is as accurate as the resolution of the display device and does not require a calculation and comparison of the line segment lengths described above. However, this technique often results in many more iterations of subdivision being performed than are truly necessary to satisfactorily approximate the curve. Thus, this technique also has the disadvantage of being slow.
Therefore, it would be useful to have a computationally efficient method of determining the accuracy with which a set of line segments approximate a Bezier curve.