Smoothing of line segments on a computer display

Details Smoothing of line segments on a computer display Smoothing of line segments on a computer display

2000-10-03

2003-11-25

Bella, Matthew C. (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

C345S610000, C345S611000

Reexamination Certificate

active

06654017

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 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
100
is sampled and then displayed using a group of shaded pixels
102
. One can see by viewing the shaded pixels
120
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. In these displays, each pixel is actually made up of many subpixels, which can be turned on or off in certain patterns to give the pixel a specific intensity.
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
200
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
202
would have to be completely shaded. However, by selectively turning on or off certain subpixels within pixel
202
, it give the viewer the impression that only a region of pixel
202
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, also known 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
300
is known, and therefore the length of segment c can be determined fairly easily. However, the area of the entire shaded region
302
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).
Similar computations must be made to determine the “middle” of the line, or the segment portion. Thus, repeated complex calculations must be made, which can create problems with limited processing power.
Line segments are represented as mathematical equations. Each segment will have a starting point, and ending point, and a slope. While some line segments may be relatively easy to draw on a computer display, such as precisely horizontal or vertical lines, most lines require some degree of approximation in choosing which pixels to illuminate in order to best represent the line segment to a viewer.
FIG. 4
is a diagram illustrating a line segment overlaid on a group of pixels. As can be seen, decisions must be made as to which pixels should be illuminated. For example, in column
2
, a decision must be made between pixel
400
and pixel
402
.
A common method for determining which pixels to illuminate to best represent a line segment is Bresenham's line algorithm. In Bresenham's approach, for lines with slopes between 0 and 1, pixel positions along a line segment are determined by sampling the line in one-pixel increments. Therefore, the process starts at the starting point
404
and steps to each successive column. At each column, the pixel is chosen whose y value is closest to the line segment.
Starting from the left end-point (x
0
,y
0
) of a given line, the process steps to each successive column (x position) and illuminates the pixel whose scan-line y value is closest to the line segment.
FIG. 5
is a diagram illustrating the kth step in this process. Assuming that the pixel at (x
k
,y
k
) is to be displayed, the process needs to determine which pixel to plot in column x
k+1
. The choices are the pixels at positions (x
k
+1,y
k
) and (x
k
+1,y
k
).
At sampling position x
k
+1, the vertical pixel separations from the mathematical line path may be termed d
1
and d
2
. The y coordinate on the mathematical line segment at pixel column position x
k
+1 is calculated as
y=m
(
x
k
+1)+
b
where m=dy/dx
Then
d
1
=y−y
k
d
1
=m
(
x
k
+1)+
b−y
k
d
2
=(
y
k
+1)−
y
d
2
=y
k
+1
31
m
(
x
k
+1)−
b
The difference between these two separations is
d
1
−d
2
=2
m
(
x
k
+1)−2
y
k
+2
b
−1
The decision parameter p
k
for the kth step in the line process may be determined by rearranging the equations so that they only involve integer calculations. This may be accomplished by substituting m=·y/·x, where ·y and ·x are the vertical and horizontal separations of the endpoint positions, and defining:
p
k
=·x
(
d
1
−d
2
)
p
k
=2
·y·x
k
−2
/·x·y
k
+c
The sign of p
k
is the same as the sign of d
1
−d
2
, since in the present case ·x>0. Parameter c is constant and has the value 2·y+·x(2b−1), which is independent of pixel position and will be eliminated in the recursive calculations for p
k
. If the pixel at y
k
is closer to the line path than the pixel at y
k
+1 (that is, d
1
<d
2
), then decision parameter p
k
is negative. In that case, the lower pixel is illuminated, otherwise the upper pixel is illuminated.
Coordinate changes along the line occur in unit steps in either the x or y directions. Therefore, the values of successive decision parameters can be obtained using incremental integer calculations. At step k+1, the decision parameter is evaluated as
P
k+1
=p
k
+2
·y·x
k+1
−2
·x·y
k+1
+c
Subtracting p
k
=2·y·x
k
−2/·x·y
k
+c from the preceding equation, we have
P
k+1
p
k
=2
·y
(
x
k+1
−x
k
)−2
·x
(
y
k+1
+y
k
)
But x
k+1
=x
k
+1, so that
P
k+1
=p
k
+2
·y
−2
·x
(
y
k+1
+y
k
)
where the term y
k+1
+y
k
is either 0 or 1, depending on the sign of parameter p
k
.
This iterative calculation of decision parameters is performed at each integer x position, starting at the left coordinate endpoint of the line. The first para

Affiliated with

Also associated with

Rating

Smoothing of line segments on a computer display does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Smoothing of line segments on a computer display, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Smoothing of line segments on a computer display will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3150104