Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Pulse repetition rate
Reexamination Certificate
2000-01-12
2003-01-21
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Pulse repetition rate
C708S290000, C382S300000
Reexamination Certificate
active
06510442
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer graphics systems using applications such as line drawing, polygon edge computing, texture mapping, and image scaling. More particularly, the present invention relates to a digital differential analyzer using improved linear interpolation procedures for use in such computer graphics applications.
BACKGROUND OF THE INVENTION
In a computer graphics system, it is desirable to represent an object as efficiently as possible to preserve memory and system bandwidth, and to enhance rendering speed. Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ applications such as line drawing, polygon edge computing, texture mapping, image scaling, and Gouraud shading during rendering images of three-dimensional (3D) objects. Linear interpolation is one of the fundamental procedures in computer graphics applications. Because linear interpolation is often used at the lowest level in a graphics driver, it is desirable to perform the linear interpolation as rapidly as possible.
A digital differential analyzer (DDA) is a mathematical function that is used to linearly interpolate and quantize a mathematical model, such as the rendering of a line or other computer graphics applications. However, conventional DDAs are computation intensive because they use comparisons or divisions.
One such DDA is described in Eker,
Faster Linear Interpolation, Graphics Gems IV,
Edited by Heckbert, Academic Press, Inc., (1994) pp. 526-533. Eker's DDA requires the integer to be extracted from the result. This requirement is expensive in terms of processor time. Moreover, the DDA of Eker is restricted to linear interpolation directed to rounding with respect to the floor over a very small range.
There are a wide range of applications involving computer graphics in which it is necessary or desirable to provide efficient and accurate linear interpolation. Accordingly, the present invention provides an improved DDA that is efficient and accurate and avoids using comparisons.
SUMMARY OF THE INVENTION
This invention addresses the problem of providing improved (faster for a given amount of computer resources) linear interpolation procedures for use in computer graphics applications such as line drawing, computing polygon edges, texture mapping, and image scaling.
The present invention provides a digital differential analyzer (DDA) that avoids using comparisons that occur in the prior art DDAs, and instead uses shifts, multiplies, and adds. Shifts are less costly to use in terms of processor time, and already exist in the hardware of a computer graphics system. The present invention uses shifts to generate an “imposter” DDA having a larger denominator that substantially exactly simulates a DDA for a finite number of terms. The imposter DDA is a fixed point simulator of the original DDA that provides error-free approximations. Preferably, the imposter DDA is stored as a data structure in memory.
Other features of the invention are described below.
REFERENCES:
patent: 3934130 (1976-01-01), Friberg
patent: 4586037 (1986-04-01), Rosener et al.
patent: 5025405 (1991-06-01), Swanson
patent: 6321245 (2001-11-01), Cukier et al.
Eker, Steven, “X.2 Faster Linear Interpolation,” Graphics Gems IV, Paul S. Heckbert, ed., Academic Press, Inc., 1994, pp. 526-533.
Malzahn David H.
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
System and method for improved digital differential analyzer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for improved digital differential analyzer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for improved digital differential analyzer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3036369