Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2000-04-07
2003-10-21
Mancuso, Joseph (Department: 2697)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S443000, C345S589000, C382S269000
Reexamination Certificate
active
06636231
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer displays. More specifically, the present invention relates to a method for the approximation of caps of smooth line segments on computer displays.
2. The Background
A computer display is made up of rows and columns of pixels. Each pixel may be very small. However, computer display technology has not yet advanced to the point where the pixels are small enough to avoid several limitations encountered when graphics are viewed by the human eye.
Sampling of images to be displayed on a computer, or of equations representing lines, results in a somewhat jagged appearance, also called the “staircase” effect. This is due to the fact that the sampling process digitizes coordinate points on an object or line to discrete integer pixel positions, resulting in an image having staggered edges. This distortion is also called “aliasing”.
FIG. 1
is a diagram illustrating the staircase effect. Line
10
is sampled and then displayed using a group of shaded pixels
12
. One can see by viewing the shaded pixels
12
that they appear jagged and suffer from the staircase effect.
Techniques used to decrease the aliasing suffered in computer graphics are known collectively as antialiasing techniques. The most obvious antialiasing technique is to simply increase the resolution of the display, so that each pixel is smaller. However, as discussed earlier, computer monitor technology as of yet does not provide for a display with such small pixels that aliasing is not viewable to the human eye.
A common antialiasing method is to increase the sampling rate by treating the display as if it were covered by a finer grid than it really is. This is known as supersampling. Supersampling works best on displays which are capable of displaying pixels at different intensities.
Typical supersampling techniques attempt to smooth the staircase effect by using the surrounding pixels.
FIG. 2
is a diagram illustrating a supersampling technique applied to the aliased line of FIG.
1
. The group of shaded pixels
50
is now much wider than in
FIG. 1
, and there is less of a staircase effect simply because they are wider. However, this technique also utilizes the ability to vary intensity of each pixel to smooth the edges of the line. For example, without the ability to vary intensities, pixel
52
would have to be completely shaded. However, by varying the intensity of pixel
52
, it gives the viewer the impression that only a region of pixel
52
is filled, and thus makes the line appear much smoother.
One drawback to supersampling is that identifying subpixels to be selectively turned on and off requires a larger number of calculations than simply determining which pixels are along a line path. These calculations are further complicated by the fact that the position of the line path within each pixel varies depending on the slope of the line. In a 45-degree line, the line path cuts each pixel in half diagonally, but a 30-degree line path does not.
Endpoints of a line, which are referred to in this application as caps, require very complex calculations, such as inverse squares.
FIG. 3
is a diagram illustrating a single pixel containing an end-point of a line. The mathematical line
100
is known, and therefore the length of segment c can be determined fairly easily. However, the area of the entire shaded region
102
must be determined in order to determine the intensity of the pixel and the orientation of the subpixels. This involves numerous computations using the Pythagorean theorem, beginning with determining a from b and c (according to the Pythagorean theorem, a
2
+b
2
=c
2
, so in order to determine a, a square root, or in computer terms inverse root must be computed).
An inverse root is one of the most complicated computations a processor can make. In recent years, there has been movement away from powerful mainframe computers to smaller, cheaper, less powerful processors, such as those that may be contained in set-top boxes and hand-held devices.
While in a large computer, antialiasing techniques may be applied using hardware, such as graphics cards, the space is not available for such hardware in these smaller, less powerful processors. Additionally, the cost of implementing the techniques in hardware may be prohibitive. Therefore, it would be preferable to perform such techniques using software.
However, performing the traditional antialiasing in software would take too much processing power due to all the inverse squares that would have to be calculated, which would slow down the processor to intolerable levels. What is needed is a solution which allows for an antialiasing technique to be applied which could be performed by software but which does not use as much processing power as traditional antialiasing techniques.
SUMMARY OF THE INVENTION
Starting and ending caps of smooth line segments may be drawn on a computer display without complicated calculations and avoiding the use of inverse square root calculations by drawing the caps using rectangles. The direction of the line segment may be determined, and using the direction certain pixels in a four-pixel grouping may be selectively illuminated. The normalized intensity values of the illuminated pixels may be determined by computing an x-fraction and a y-fraction, representing the distance in the x-direction and y-direction between a sample origin point in a corner of the four-pixel grouping and the closest corner of a region covered by the mathematical origin or endpoint corrected for the thickness of the line segment. It is generally preferable for only two pixels to be illuminated for each cap, the pixels chosen according to a formula ensuring that there are no perception problems when two smooth line segments share a common mathematical origin or endpoint.
REFERENCES:
patent: 4352100 (1982-09-01), O'Connell
patent: 6329977 (2001-12-01), McNamara et al.
Mohammed, Osama and Garcia, Luis, IEEE: An Optimum Finite Element Grid Generator for Triangulating Rotating and Fixed Objects in Electromagnetics (1989), Session 11D2, pp. 804-808.
Hanish Marc S.
Luedke Scott L.
Mancuso Joseph
Sun Microsystems Inc.
Thelen Reid & Priest LLP
LandOfFree
Apparatus for approximation of caps of smooth line segments does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for approximation of caps of smooth line segments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for approximation of caps of smooth line segments will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3167441