Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-06-29
2004-05-11
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S613000
Reexamination Certificate
active
06734870
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to information processing systems, and more specifically to an improved method for scan-converting a line for use with a graphical output in an information processing system.
BACKGROUND OF THE INVENTION
A scan-conversion procedure for lines computes the coordinates of the pixels that lie on or near an ideal, thin straight line imposed on a two-dimensional grid (Foley, J. D. et al, Computer Graphics, 2d ed., 1996, Addison-Wesley, pp. 72-81).
The simplest procedure for the scan-conversion of a line computes the slope of the line and predicts the y-intercepts of the ideal line as the x-coordinate is repeatedly incremented by 1. A pixel is then intensified nearest the predicted y-intercept at the equally spaced x-increments.
The drawbacks of this simple procedure are that it involves floating point arithmetic and rounding and floor functions. Bresenham (Bresenham, J. E., “Algorithm for Computer Control of a Digital Plotter,” IBM Systems Journal, 4(1), 1965, pp. 25-30) developed an algorithm that uses only integer arithmetic. Bresenham showed that his procedure provides a best-fit approximation to an ideal line by minimizing the error to the line. A floating point version of the Bresenham procedure can be applied to lines having arbitrary real-valued endpoint coordinates (Foley, supra, at p. 75).
Current graphical outputs in information processing systems demand the use of floating point arithmetic including multiply and divide operations to obtain needed accuracy. What is needed is a line scan-conversion procedure for application to lines having arbitrary real-valued endpoint coordinates in which floating point arithmetic is not required and in which many integer multiply and divide operations can be implemented using simple, fast left and right shift operations.
SUMMARY OF THE INVENTION
The present invention meets those needs, and others that will become apparent below, by providing a procedure for scan-converting a line, with an arbitrary precision, using integer arithmetic only. The procedure subdivides an integer grid into a new grid in which each original grid element is subdivided by a predetermined positive integer in both an X-direction and a Y-direction, where X and Y are orthogonal, rectangular coordinates. The original grid is referred to as an integer ‘coarse’ grid, while the subdivided grid is referred to as an integer ‘fine’ grid. A line having arbitrary real-valued endpoint coordinates is defined in the fine grid system by providing a pair of integer vertices defining the opposite ends of the line. When the coarse grid granularity approximately equals an output pixel size, and when the fine grid granularity is approximately one-sixteenth that of the coarse grid, the method is able to accurately scan-convert lines having arbitrary real-valued endpoint coordinates without apparent loss of resolution.
Though the same result can be obtained using floating point arithmetic, the present invention uses only integer arithmetic and therefore does not need access to a floating point arithmetic unit. The Bresenham method (supra) can be implemented using only integer arithmetic, but it does not allow for arbitrary precision and is considered to be too slow for advanced graphic applications. The present procedure, on the other hand, is fast enough, and precise enough to meet the needs of the most demanding graphic display requirements.
The line scan-conversion procedure continues by ordering the two line-defining vertices such that the vertex having the larger integer Y-coordinate is referred to as the ‘large’ vertex, while the other vertex is the ‘small’ vertex. The ordering will place the line into one of the first or the second quadrant depending on whether the slope of the line is negative or positive, respectively.
Having ordered the two vertices, the procedure will determine an integer approximation to a slope for an ideal line connecting the two vertices. The procedure will then increment in the Y-direction by one coarse grid unit and determine a best-fit X-coordinate in the fine grid system. The result will be a series of points defined relative to the fine grid and having Y-coordinates that coincide with coarse grid coordinates. The use of the fine grid coordinates in the X-direction produces the same results that can be obtained using floating point arithmetic while using [only] integer arithmetic only.
The results of the line scan-conversion procedure are used to adjust color and brightness attributes of display pixels. The resulting adjusted display pixels are output to a display device for creating an image of the scanned line segment.
REFERENCES:
patent: 5479590 (1995-12-01), Lin
Foley et al., “Computer Graphics: Principles and Practice” 2ndedition in C, 1996, pp. 664, 693.*
Foley, J.D., et al., Computer Graphics, 2d ed., 1996, Addison-Wesley, pp. 72-81, 884.
Buckley Robert
Cardio Logic, Inc.
Luu Matthew
LandOfFree
Line scan-conversion 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 Line scan-conversion method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Line scan-conversion method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254429