Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-02-24
2002-03-26
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S426000
Reexamination Certificate
active
06362818
ABSTRACT:
BACKGROUND
TECHNICAL FIELD
This invention relates generally to the field of computer graphics display, and more particularly to reducing the amount of time needed to render complex virtual scenes on a computer graphics display.
BACKGROUND OF THE INVENTION
Computers have been used for many years to do image and graphics generation. In recent years these computer-generated graphics have become more and more sophisticated. As the power of computer equipment increases, the users' expectation of what the computer should do also increases. One area that has been accelerating rapidly is computer-generated imagery with increasing scene complexity. Computer users have come to expect more realism that generally means that there are more objects and more lighting and texture processing on those objects.
Complex images and scenes are modeled in three-dimensional space in the computer memory and manipulated accordingly. A complex three-dimensional shape is broken down into basic graphic shapes called primitives. Modeling techniques and tools describe the virtual environment with primitives. Primitives include such things as polygons, meshes, strips and surface patches. Some graphics architectures employ optimized algorithms for handling simple primitives such as dots, lines and triangles. Before a three dimensional scene can be viewed by the user it must be translated from the three dimensional view in the computer to a two dimensional view which can be displayed on a two dimensional screen or monitor.
The process of translating the three-dimensional image to a flat display device is called rendering. The rendering process takes place in the graphics hardware or software and converts primitives into a two-dimensional array of graphical points. These points are known as pixels and are stored in computer memory in a frame buffer before they are drawn on the screen. The frame buffer is a rectangular two-dimensional array and is M by N pixels, where M and N depend on the display system. The computer draws multiple frames consecutively at many frames per second to animate the virtual environment being viewed. Graphics display techniques can also incorporate sub-pixels that are logical sub-divisions of a pixel. The color values of the sub-pixels are later combined or averaged together to form an actual pixel. Generally, techniques that can be applied to pixels can also be applied to sub-pixels.
The number of frame buffer pixels which must be displayed is constant for any given computer screen. However, the number of pixels that must be computed in order to fill the frame buffer is highly dependent on the complexity of the virtual scene. For each actually displayed pixel, a number of pixels may be rendered based on the number of primitives that cover the pixel in the scene. In other words, a calculation is made for each primitive graphic object that is in the line of sight of the pixel. The ratio of the number of rendered pixels relative to the number of displayed pixels is known as the average pixel depth complexity. This indicates the average number of primitives that cover each pixel on the screen. Depth complexity numbers indicate the amount of processing or work it takes to create each image, and these numbers vary greatly depending on the modeled environment and the viewer's current position in that environment.
For example, in a rendering of a region of mountainous terrain covered with trees as viewed from above, the average depth complexity lies somewhere between one and two. The peak depth complexity may be two. Pixels displaying the terrain only need one calculation, while pixels covered by a tree need two calculations, one for the tree and one for the terrain. If the viewer's position is moved down within the trees, with a line of sight toward the horizon, the depth complexity numbers will increase dramatically. If the forest is quite dense, the average depth complexity may go up into the tens while the peak may even approach the hundreds. As the model complexity increases the depth complexity numbers will also increase.
Many pixels rendered in high depth complexity scenes never contribute to the final image. This occurs because the primitives to which they belong are located farther away and behind other primitives in the scene and are therefore not visible to the user. The additional unused calculations increase the amount of hardware or time required to render a given scene.
As the virtual enviromnent's complexity increases, the demand on the rendering process also increases. If the rendering is done in accelerated graphics hardware, it can become quite costly because of the large number of calculations required to be implemented in hardware. For software based rendering systems, the rendering time can become very slow. In either case, if the rendering is too slow, the movement of the display image becomes disjointed or choppy when the image is displayed.
Various techniques have been used to reduce the amount of hardware or computing time needed to render increasingly complex scenes. These techniques attempt to reduce the number of pixels rendered which do not contribute to the final image. Most current systems use a brute-force approach to converting modeled primitives into viewable pixels. Each primitive is taken individually and projected from the three-dimensional model coordinates into a two-dimensional frame buffer space in memory. Then the process calculates which pixels within the frame buffer the primitive touches. Computing which pixels are touched is a process known as scanning. Scanning selects each pixel and computes its color as determined by the modeled attributes of the primitive. Computing the pixel color can be very complex if sophisticated lighting algorithms and textures are being used. Typical factors contributing to the pixel's color include the modeled color, light sources shining on the primitive, texture, anti-aliasing, and visibility conditions.
A mechanism must also be provided to determine which primitive in the scene should be visible for any given pixel (or sub-pixel if anti-aliasing techniques are employed). This process is often referred to as hidden-surface-removal. For example, all the primitives or surfaces which are hidden by other surfaces within the scene are removed. Common hidden-surface-removal techniques include the painter's algorithm, list-priority algorithms, scan-line algorithms, and Z-buffering (or depth buffering).
Each of these hidden-surface-removal techniques has it own advantages or disadvantages.
For a number of reasons, the Z-buffer method has now become a very popular choice. Most of the other approaches require special modeling techniques and support data structures to render the image properly. The Z-buffer approach eliminates most of these constraints and simplifies the modeling process. In the Z-buffer approach, the visible primitive or surface at each pixel is the primitive with the closest Z value. The Z value is basically the depth of the primitive in the viewed scene. As each primitive is rendered, this Z parameter can be computed for each pixel touched. The frame buffer is also expanded to store the Z depth, along with storing the pixel color. As each new primitive is processed, the new Z depth can be compared with one already stored in the frame buffer. The frame buffer only keeps the pixels rendered for the primitive closest to the observer.
A major disadvantage of the Z-buffer is that all of the color shading calculations are performed before the depth test is done. Pixels are only discarded by the frame buffer circuit after the color shading calculation is done. This requires a lot of expensive or time consuming calculations to be performed with no final contribution to the image on the screen.
Other hidden-surface-removal strategies have developed more cost effective architectures. An example is the list-priority approach, where the primitives are rendered in a front-to-back order. By recording which pixels (or pixel arrays) are filled up by primitives as they are rendered, later prim
Gardiner Harold D.
Urry Russell J.
Evans & Sutherland Computer Corporation
Thorpe North & Western LLP
Vo Cliff N.
LandOfFree
System and method for reducing the rendering load for high... 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 reducing the rendering load for high..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for reducing the rendering load for high... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2838102