Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
2000-03-24
2004-03-02
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06700576
ABSTRACT:
FIELD OF THE INVENTION
The invention generally relates to computer systems and, more particularly, the invention relates to the rendering of a circle by approximating the circle using the vertices of a polygon.
BACKGROUND OF THE INVENTION
Some computer graphics systems have hardware dedicated to rendering circles precisely using differentials. Alternatively, computer graphics systems that do not have dedicated hardware for rendering circles typically improve performance by approximating circles using a polygon whose vertices lie along the circumference of the circle. The approximation of a circle by using a polygon with multiple vertices is shown in
FIG. 1. A
four sided polygon
10
may be used to approximate circle
11
. Also shown are an eight sided polygon
12
, a twelve sided polygon
14
and a circle
16
approximated by using an infinite number of vertices. The number of vertices required to render a circle is dependent upon the desired accuracy and the radius of the circle itself. The number of vertices is also directly related to the amount of time it takes to render the circle, and therefore, inversely proportional to the performance of the computer graphics system.
In a computer graphics system which approximates a circle using a polygon, typically, sine and cosine functions are used to compute each vertex of the polygon used to approximate the circle. Alternatively, a table of precomputed sine and cosine coordinate values may be used to eliminate the sine and cosine computations on a per-vertex basis. The size of the table of sine and cosine values will determine the number of vertices which are used to approximate a circle. For example, if the computer graphics system has a table with six entries, six vertices will be used to approximate the circle. Since a large number of vertices is required to represent a large circle, then, a large table of sine and cosine values must be created. This same table when used to render a smaller circle, however, will be far more accurate than necessary, and will result in slower performance of the computer graphics system.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, an apparatus and method for rendering a circle on a display device, the circle having a radius and a circumference, (a) provides a set of vertex points, (b) selects a subset of vertex points from the set of vertex points based on the radius of the circle, (c) scales each vertex point in the subset of vertex points to produce scaled vertex points, and then (d) connects each scaled vertex point in the subset of vertex points to approximate the circle. In a preferred embodiment, the act of scaling comprises multiplying each vertex point by the radius of the circle. The set of vertex points may be stored in a table in a computer memory. In another embodiment, the subset of vertex points is used to determine scaled vertex points for all four quadrants of the circle. In a further preferred embodiment, the members of the subset of vertex points are evenly distributed about the circumference of the circle.
In one embodiment, the aforementioned step (b) may further determine the number of vertex points required to render the circle with an error less than a predetermined error threshold and then select the subset of vertex points such that the number of members in the subset of vertex points is equivalent to the number of vertex points required to render the circle with an error less than the predetermined error threshold. The number of vertex points required to render the circle with an error less than the predetermined error threshold may be determined using the following relationship:
n
=
π
4
cos
-
1
(
r
-
ϵ
r
)
where n=number of vertex points; r=radius of the circle; and, &egr;=the predetermined error threshold.
In an alternative embodiment, the aforementioned step (b) may further identify all possible vertex point counts, determine the maximum circle radius which may be rendered using each of the possible vertex point counts such that an error is less than a predetermined error threshold and then select the subset of vertex points by comparing the radius of the circle to each maximum circle radius. The maximum circle radius may be determined using the following relationship:
r
=
ϵ
1
-
cos
(
π
4
n
)
where r=maximum circle radius; &egr;=the predetermined error threshold; and, n=vertex point count.
In accordance with another aspect of the invention, an apparatus and method for rendering a circle on a display device, the circle having a radius and four quadrants, (a) provides a set of vertex points for one quadrant of the circle, (b) identifies the vertex points for the remaining three quadrants using the set of vertex points, and (c) connects the vertex points of all four quadrants to approximate the circle. In a preferred embodiment, the apparatus and method further comprises multiplying each vertex point in each quadrant by the radius of the circle. The set of vertex points may be stored in a table in a computer memory. In another embodiment, step (b) may further select a subset of vertex points based on the radius of the circle and identify the vertex points for the remaining three quadrants using the members of the subset of vertex points.
Preferred embodiments of the invention are implemented as a computer program product having a computer usable medium with computer readable program code thereon. The computer readable code may be read and utilized by the computer system in accordance with conventional processes.
REFERENCES:
patent: 4530156 (1985-07-01), Kettlestrings
patent: 4591843 (1986-05-01), Pratt
patent: 4692887 (1987-09-01), Hashidate
patent: 4835722 (1989-05-01), Clarke et al.
patent: 5237649 (1993-08-01), Yamada
patent: 5874968 (1999-02-01), Hama
patent: 6289831 (2001-09-01), Hanai et al.
patent: 6600485 (2003-07-01), Yoshida et al.
Hobby; Rasterizing Curves of Constant Width; Apr. 1989, ACM vol. 36, No. 2, pp. 209-229.*
IBM Technical Disclosure; Optimized Drawing of Filled and Unfilled Circles in a Two-Dimensional Graphics System; Nov. 1990 NB9011291, pp. 291-295, vol. 33, issue 6B.*
Wright; Parallelization of Bresenham's Line and Circle Algorithms; IEEE, 0272-17-16/90/0900-0060, 1990, pp. 60-67.*
Aken et al., Curve-Drawing Algorithms for Raster Displays, 1985 ACM 0730-0301/85/0400-0147, Vol 4, No. 2, pp. 147-169.*
An Improved Parallel Circle Drawing ALgorithm, Huang and Banissi, 1997, IEEE.*
J.A. Harrison, “A powerful display driver for real time systems”, International Conference on Displays for Man-Machine Syatem Apr. 1977, pp. 6-9.
Heinrich Steven J.
Kirkland Dale
Lazenby, Jr. William R.
3Dlabs Inc. Ltd.
Arnall Golden & Gregory LLP
Wallace Scott
Zimmerman Mark
LandOfFree
Variable stride circle rendering apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Variable stride circle rendering apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variable stride circle rendering apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3284611