Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
1999-07-15
2002-04-23
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S612000, C345S614000, C345S606000, C345S581000
Reexamination Certificate
active
06377274
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer image generation (CIG) systems, and, more particularly, to a novel color determination means for use in a display processor and to novel methods for processing image data describing object faces, for display of two-dimensional representations of those objects in a real-time imaging system.
BACKGROUND OF THE INVENTION
Real-time computer image systems are being designed to provide realistic image reproduction for a variety of video graphic systems, such as video games and video training and simulation devices. In these systems, it is very advantageous to provide the user with video display realism.
In a typical real-time computer image generation system, such as a video game, image generation is done in three sequential stages: Controller, Geometry Processor, and Display Processor. Each of these three processing stages or sections each work independently on data representating of or corresponding to one of three consecutive scenes to be displayed. Each of these processing stages or sections processes data on a scene or image for a fixed time, which may be either a field time of 16.67 milliseconds or a frame time of 33.3 milliseconds, usually the former. These particular field and frame times corresponds to those of a typical television format display, i.e., two interlaced fields per frame with thirty frames per second.
For each time interval, all three processors are kept busy so that, at any given time, the processors are working on three separate scenes. Each section processes inputs and generates outputs during the interval, so data flows through the three stages in a sequential manner from the controller, to the Geometry Processor, and then to the Display Processor. The computational load is spread out among the specialized processor sections, new scenes can be displayed each field or frame time, even though the results are delayed three field or frame times.
For example, in a video game that simulates a flight system, user, or player, inputs are received by the Controller; and after being processed sequentially by the Controller, the Geometry Processor and Display Processor, the output is sent as a color scene to video displays observed by the player. The data seen by the player starts out as simple control inputs applied to an environment definition and is converted to pixel video display information. In the controller, the player inputs are used to calculate the new position and orientation of the simulated aircraft, and from this, a mathematical rotation matrix is calculated that is used to rotate objects from a reference coordinate system to a display coordinate system. Other information dealing with the aircraft, with the position of targets and with other aircraft is also calculated in the Controller. In some applications, the Controller is a general purpose computer.
The Geometry Processor reads, from a database, descriptions of objects that are potentially visible in the stored three-dimensional digital representation of the scene, and the objects that are read are rotated into display coordinates using the rotation matrices calculated in the Controller. The Geometry Processor mathematically projects the three-dimensional data onto the two-dimensional display window. In addition, the Geometry Processor calculates (as by use of a depth-buffer or the like) which objects are in front or behind other objects and stores this information in a priority list.
Each object processed is comprised of individual faces, where each face is in the form of a polygon bounded by straight edges. The priority list contains the order of all faces in the scene, with the first face in the list as the highest priority face, and the last face in the list as the lowest priority face. Whenever two faces overlap on the display, the higher priority face will be visible, and the lower priority face will be obscured. Lastly, the Geometry Processor calculates the display end points for the edges that bound the two-dimensional faces, and also calculates the coefficients of the line equations that describe these bounding edges.
The Display Processor receives the two-dimensional face descriptions, along with additional face related data and uses this information to output data describing to a color display each pixel in the scene. Each color display in the system is typically made up of 1024 lines of video information, with each line having 1024 individual color dots or pixels. The Display Processor has to resolve, for each pixel, what the color of the pixel should be, given that many faces can be present in a pixel, and that certain portions of faces may be covered by other faces. Since values for all of these pixels need to be calculated in {fraction (1/60)}th of a second, the processing load in the Display Processor is very high. To calculate video for a multi-display system (a single system has contained as many as 14 displays), the Display Processor must perform in excess of 10 billion computations per second.
One persistent problem has been to process pixel color intensity information in an anti-aliasing manner, which allows for suitable high-definition edge effects to be visible while preventing undesirable video data components (“distortion”) from taking on the identity of a desired component, so as to appear as the wrong color, or degree of translucency, in that pixel.
SUMMARY OF THE INVENTION
An object of this invention is to provide an improved anti-aliasing procedure for computer image generation systems.
Another object of the present invention is to provide an improved process for encoding edge intersection data for use in an anti-aliasing procedure in a computer image generation system.
These and other objectives are attained with a method and apparatus, for use in a computer image generation system wherein polygons are displayed on an array of pixels, for encoding data representing intersections of the polygons and the pixels. The method comprises the steps of receiving input data signals characterizing a set of coordinates of each of at least three vertices of each polygon to be displayed, each different pair of the vertices of each polygon defining a different edge of the polygon; and generating, responsive to the received vertex data signals, edge data signals describing the intersection, if any, of the polygon edges with each pixel to be displayed.
The generating step includes, for each pixel to be displayed, i) identifying in a first field of one of the edge data signals, and for each side of the pixel, whether or not the edges of a selected one of the polygons intersect said side of the pixel, and ii) if the edges of the selected polygon intersects any side of the pixel, storing, in a second field of said one of the edge data signals, an estimate of the location along the side or sides of the pixel at which the polygon edges intersect the pixel side.
Further benefits and advantages of the invention will become apparent from a consideration of the following detailed description, given with reference to the accompanying drawings, which specify and show preferred embodiments of the invention.
REFERENCES:
patent: 4714428 (1987-12-01), Bunker et al.
patent: 4727365 (1988-02-01), Bunker
patent: 4825391 (1989-04-01), Merz
patent: 5528738 (1996-06-01), Sfarti et al.
patent: 5555360 (1996-09-01), Kumazaki et al.
patent: 5668940 (1997-09-01), Steiner et al.
patent: 5684939 (1997-11-01), Foran et al.
patent: 5872902 (1999-02-01), Kuchkuda et al.
patent: 6005580 (1999-12-01), Donovan
patent: 6057855 (2000-05-01), Barkans
patent: 6226005 (2001-05-01), Laferriere
Chung Daniel J
Intel Corporation
Luu Matthew
Scully Scott Murphy & Presser
LandOfFree
S-buffer anti-aliasing 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 S-buffer anti-aliasing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and S-buffer anti-aliasing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2856154