Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-09-03
2002-11-12
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06480195
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to, a method and apparatus for generating a straight line, and more particularly, to a method and apparatus that generates a straight line by parallel processing multiple segments corresponding to that straight line, thereby enhancing efficiency.
2. Description of the Related Art
As shown in
FIG. 1
, conventional display devices are formed by an array of display units, generally pixels, that are arranged of horizontal rows and vertical columns. Many devices perform scan-conversion and reproduction of straight lines including but not limited to horizontal and vertical lines, such as line
11
of FIG.
1
. To enable this scan-conversion and reproduction, various approaches have been proposed, two of which are described hereinafter.
A first approach involves scan-converting a straight line by storing each pixel's address and intensity used to represent that line in memory, and reproducing those pixels as needed in another memory (e.g., a frame buffer). This approach requires very little processor time. However, because this approach relies on the storage and retrieval of a large amount of pixel data (e.g., addresses and intensities) in memory, it is memory intensive.
The second approach involves scan-converting straight lines by using only the endpoints of the straight lines, and reproducing the pixels therebetween using an algorithm that is based on those endpoints. Specifically, as shown in
FIG. 2
, an algorithm may be iteratively performed to identify a series of pixels sequentially along a desired straight line. An incremental technique developed by Bresenham has been used in this fashion. In
FIG. 2
, the iterations are performed to sequentially identify a series of pixels beginning with a leftmost pixel (x
i
, Round (y
i
)) followed by the identification of a next pixel (x
i+1
, Round (y
i+m
)), and thereafter each subsequent pixel along the line. In this manner, Bresenham's incremental technique is iteratively repeated until all pixels within the line are reproduced, one computation per pixel.
The second approach is less memory intensive. However, this approach requires increased processor time since a separate computation must be iteratively performed to identify each pixel between the stored endpoints.
Regardless of the method used for scan-converting and reproducing a straight line, a certain amount of error is unavoidable for most straight lines because they are not generally aligned with rows or columns of the pixel array that forms the display.
FIG. 3A
shows how this error results in an effect known as “aliasing” of the line ultimately reproduced on the display. To avoid aliasing, conventional systems have applied anti-aliasing techniques. Most of these techniques involve emphasizing and de-emphasizing pixels used to represent a desired line based on their relative distance from the desired line. Using these anti-aliasing techniques, errors in the produced line become less noticeable, as illustrated by
FIG. 3B
which shows the effects of anti-aliasing techniques on the line of FIG.
3
A.
Generally, anti-aliasing techniques require complex and taxing computations that must be repeated for each pixel to be displayed. For instance, proceeding along the line, a separate computation must be performed for each pixel sequentially to determine the error between that pixel and the desired line to be displayed. Then, before beginning computations for a next pixel, the intensity of the pixel is adjusted based on the error determined. As such, like the computations performed in Bresenhams's incremental technique, the anti-aliasing computations are performed sequentially, and the number of separate computations increase proportional to increases in the length of, and therefore the number of pixels, within the line being reproduced. When employed in combination with conventional algorithms that are performed sequentially for all pixels, such as Bresenham's incremental technique described above, conventional anti-aliasing techniques increase the amount of processing time needed by approximately ninety (90) times.
SUMMARY OF THE INVENTION
The present invention is directed to a method and apparatus that substantially obviate one or more of the problems experienced due to the above and other limitations and disadvantages of the related art.
Objects, features and advantages of the present invention will be set forth in the description that follows, and in part will become apparent from the detailed description, or may be learned by practice of the invention.
To achieve these and other advantages and in accordance with the purposes of the present invention, as embodied and broadly described herein, the present invention includes a method for generating a line corresponding to a desired straight line, the method identifying a plurality of segments between two endpoints of the desired straight line to be generated, and generating the line corresponding to the desired straight line comprising identifying, in parallel, pixels in each of more than one of the segments.
The multiple segments may be identified by identifying a segment of a display pixel array located between pixels that correspond to two points in the straight line to be generated.
To generate the line, pixels within one segment of the multiple segments are identified, and then pixels within other of the multiple segments are identified in parallel based on the pixels identified within the one segment. The process of identifying pixels within the one segment may involve identifying a series of all pixels within the one segment before identifying pixels in any of the other segments, and the process of identifying pixels may involve identifying a series of all pixels within each of the other segments in parallel based on the series of all pixels identified within the one segment. Alternatively, the process of identifying pixels within the one segment may involve identifying less than all pixels within the one segment before identifying corresponding pixels in any of the other segments, and identifying a corresponding group of less than all pixels within each of the other segments in parallel based on the pixels identified within the one segment. In this manner, it is possible to generate the line by simultaneously identifying at least one pixel within each of the multiple segments, e.g., by simultaneously identifying a single corresponding pixel within each of the multiple segments.
Alternatively, the generating may involve identifying a group of at least one (but less than all) corresponding pixels within each of the multiple segments, and identifying a next group of at least one (but less than all) corresponding pixels within each of the multiple segments, where the groups include a single pixel from within each of the multiple segments. The generating also involving controlling an intensity of pixels used to generate the straight line based on an error in position between each pixel and the straight line being generated, respectively.
In addition to the above, the method may include determining the intensity of pixels in a first of the segments, and determining the intensity of pixels in other of the segments based on the intensity determined for the first of the segments.
The multiple segments may be identified based on its slope, the slope being determined based on two endpoints of the straight line. The multiple segments may be identified along the desired straight line or along a line that approximates the desired straight line. To identify the segments, a specified slope interval may be identified based on the determined slope, the specified slope interval being identified from within a stored slope table in which lines are categorized based on ranges of slope such that lines within any particular range of slope are approximated using a same approximate line. Furthermore, the process of identifying multiple line segments may include applying an iterative algorithm that is selected based on the slope to i
Brier Jeffery
Cunningham G. F.
George Mason University
Grossman David
LandOfFree
Method and apparatus for generating a straight line does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating a straight line, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating a straight line will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2953092