Efficiently rendering line segments on a computer display

Details Efficiently rendering line segments on a computer display Efficiently rendering line segments on a computer display

2000-06-06

2003-06-24

Bella, Matthew C. (Department: 2676)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

C345S418000, C345S467000, C345S468000, C345S586000

Reexamination Certificate

active

06583788

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer displays. More specifically, the present invention relates to the efficient rendering of line segments on a computer display.
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.
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. 1
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
10
and pixel
12
.
A common method for determining which pixels to illuminate to best represent a line segment is Bresenhan'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
14
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. 2
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
+1).
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
−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=&Dgr;y/&Dgr;x, where &Dgr;y and &Dgr;x are the vertical and horizontal separations of the endpoint positions, and defining:
p
k
=&Dgr;x
(
d
1
−d
2
)
 
p
k
=2
&Dgr;y·x
k
−2
/&Dgr;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 &Dgr;x >0. Parameter c is constant and has the value 2&Dgr;y+&Dgr;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
&Dgr;y·X
k+1
−2
&Dgr;x·y
k+1
+C
Subtracting p
k
=2&Dgr;y·x
k
−2/&Dgr;x·y
k
+C from the preceding equation, we have
P
k+1
−p
k
=2
&Dgr;y
(
x
k+1
−x
k
)−2
&Dgr;x
(
y
k+1
+Y
k
)
But x
k+1
=x
k
+1, so that
P
k+1
=p
k
+2
&Dgr;y
−2
&Dgr;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 recursive calculation of decision parameters is performed at each integer x position, starting at the left coordinate endpoint of the line. The first parameter, p
0
, is evaluated at the starting pixel position (x
0
, y
0
) and with m evaluated as &Dgr;y/&Dgr;x:
p
0
+2
&Dgr;y−&Dgr;x
Bresenham's method may be summarized as follows (for slope value between −1 and 1):
1. Begin with starting point (x
0
, y
0
)
2. calculate the following constants:
&Dgr;x−the change in x over the entire line segment
&Dgr;y−the change in y over the entire line segment
2&Dgr;y
2&Dgr;y−2&Dgr;x
3. Calculate the starting value for the decision parameter (p) as
p
0
2
&Dgr;y−&Dgr;x
4. At each x
k
along the line segment, starting at k=0, perform the following test: if p
k
<0, the next point to plot is (x
k
+1, Y
k
) and
p
k+1
=p
k
+2
&Dgr;y
 Otherwise, the next point to plot is (x
k
+1, y
k
+1) and
p
k +1
=p
k
+2
&Dgr;y
−2
&Dgr;x
5. Repeat step 4 for each column until the ending point is reached.
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. The computation of constants requires a lot of computing power lest the speed of the line drawing suffer. The problem, therefore, with using Bresenham's method for drawing lines is that it requires the calculation of four different constants. What is needed is a solution for approximating line segments which can be performed with less calculations yet would yield similar results.
SUMMARY OF THE INVENTION
A method for rendering a line segment extending in the positive-x direction and positively direction on a computer display given a starting point and an ending point, the starting point having the form (x
s
, y
s
) and the ending point having the form (x
e
, y
e
). In this method, &Dgr;x and &Dgr;y are computed using the formula &Dgr;x=|x
e
−x
s
| and &Dgr;y=|y
e
−y
s
|, respectively. Then dt(0)=(y
f
*&Dgr;x)−(x
f
*&Dgr;y) is computed, where x
f
is the fractional portion of x
s
and y
f
is the fractional portion of y
s
, which allows for more precision. If the line segment extends in the postive-x and positive-y directions, then for each column n containing a portion of said line segment the process: plots said current pixel if dt(n)<=0.5*&Dgr;x and plotting the pixel above said current pixel if dt(n)>0.5*&Dgr;x; moves said current pixel to the right one pixel if dt(n)<=0.5*&Dgr;x and moves said pixel to the right and up one pixel if dt(n)>0.5*&Dgr;x; and corrects dt(n) by computing dt(n)=dt(n)−&Dgr;x if dt(n)>0.5*&Dgr;x. After all of these computations have been performed, the process may iterate to the next column by computing dt(n+1)=dt(n)+&Dgr;y. This method greatly reduces the number of calculations required by the prior art methods, thus producing a faster and more efficient process by which to draw line segments on a computer display.


REFERENCES:
patent: 4808988 (1989-02-01), Burke et al.
patent: 5333250 (1994-07-01), Staley et al.
patent: 5519822 (1996-05-01), Barkans et al.
patent: 5581680 (1996-12-01), Sfarti et al.
patent: 5646691 (1997-07-01), Yokoyama
patent: 5790126 (1998-08-01), Ballard et al.
patent: 6088041 (2000-07-01), Ballard et al.
patent: 6175372 (2001-01-01), Ballard et al.

Affiliated with

Also associated with

Rating

Efficiently rendering 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 Efficiently rendering line segments on a computer display, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiently rendering line segments on a computer display will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3113501