Computer graphics processing and selective visual display system – Computer graphic processing system – Plural graphics processors
Reexamination Certificate
1999-08-20
2003-06-10
Bella, Matthew C. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphic processing system
Plural graphics processors
C345S502000, C345S505000, C345S419000
Reexamination Certificate
active
06577317
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to high-performance 3-D graphics imaging. More particularly, the invention relates to geometry operations in a 3D-graphics pipeline, operations such as transformations, clippings, decompositions and lighting calculations.
BACKGROUND
Three-Dimensional Computer Graphics
Computer graphics is the art and science of generating pictures with a computer. Generation of pictures, or images, is commonly called rendering. Generally, in three-dimensional (3D) computer graphics, geometry that represents surfaces (or volumes) of objects in a scene is translated into pixels stored in a framebuffer and then displayed on a display device.
In a 3D animation, a sequence of still images is displayed, giving the illusion of motion in three-dimensional space. Interactive 3D computer graphics allows a user to change his viewpoint or change the geometry in real-time, thereby requiring the rendering system to create new images on the fly in real time.
In 3D computer graphics, each renderable object generally has its own local object coordinate system and, therefore, needs to be translated (or transformed) from object coordinates to pixel-display coordinates. Conceptually, this translation is a four-step process: 1) translation from object coordinates to world coordinates, the coordinate system for the entire scene, 2) translation from world coordinates to eye coordinates, based on the viewing point of the scene, 3) translation from eye coordinates to perspective-translated eye coordinates and 4) translation from perspective-translated eye coordinates to pixel (screen) coordinates. These translation steps can be compressed into one or two steps by pre-computing appropriate translation matrices before any translation occurs.
(Translation from object coordinates includes scaling for size enlargement or shrink. Perspective scaling makes farther objects appear smaller. Pixel coordinates are points in three-dimensional space in either screen precision (that is to say, pixels) or object precision (that is to say, high-precision numbers, usually floating-point).
Once the geometry is in screen coordinates, it is broken into a set of pixel-color values (that is, “rasterized”) that are stored into the framebuffer.
A summary of the prior-art rendering process can be found in Watt,
Fundamentals of Three-dimensional Computer Graphics
(Addison-Wesley Publishing Company, 1989, reprinted 1991, ISBN 0-201-15442-0, herein “Watt” and incorporated by reference), particularly Chapter 5, “The Rendering Process,” pages 97 to 113, and Foley et al.,
Computer Graphics: Principles and Practice,
2nd edition (Addison-Wesley Publishing Company, 1990, reprinted with corrections 1991, ISBN 0-201-12110-7, herein “Foley et al.” and incorporated by reference).
FIG. 1
shows a three-dimensional object, a tetrahedron, with its own coordinate axes (x
object
, y
object
, z
object
). The three-dimensional object is translated, scaled and placed in the viewing point's coordinate system based on (x
eye
, y
eye
, z
eye
). The object is projected onto the viewing plane, thereby correcting for perspective. At this point, the object appears to have become two-dimensional. The object's z-coordinates, however, are preserved for later use in hidden-surface removal. The object is finally translated to screen coordinates, based on (x
screen
, y
screen
, z
screen
), where z
screen
is going perpendicularly into the page. Points on the object now have their x and y coordinates described by pixel location (and fractions thereof) within the display screen and their z coordinates in a scaled version of distance from the viewing point.
Generic 3D-Graphics Pipeline
Many hardware renderers have been developed. See, for example, Deering et al., “Leo: A System for Cost Effective 3D Shaded Graphics,” SIGGRAPH93 Proceedings, Aug. 1-6, 1993, Computer Graphics Proceedings, Annual Conference Series (ACM SIGGRAPH, 1993, Soft-cover ISBN 0-201-58889-7 and CD-ROM ISBN 0-201-56997-3, herein “Deering et al.” and incorporated by reference), particularly at pages 101 to 108. Deering et al. includes a diagram of a generic 3D-graphics pipeline (that is to say, a renderer, or a rendering system) that it describes as “truly generic, as at the top level nearly every commercial 3D graphics accelerator fits this abstraction.” This pipeline diagram is reproduced here as FIG.
6
. (In this figure, the blocks with rounded corners typically represent functions or process operations, while sharp-cornered rectangles typically represent stored data or memory.)
Such pipeline diagrams convey the process of rendering but do not describe any particular hardware. This document presents a new graphics pipeline that shares some of the steps of the generic 3D-graphics pipeline. Each of the steps in the generic 3D-graphics pipeline is briefly explained here. (Processing of polygons is assumed throughout this document, but other methods for describing 3D geometry could be substituted. For simplicity of explanation, triangles are used as the type of polygon in the described methods.)
As seen in
FIG. 6
, the first step within the floating point-intensive functions of the generic 3D-graphics pipeline after the data input (step
612
) is the transformation step (step
614
), described above. The transformation step also includes “get next polygon.”
The second step, the clip test, checks the polygon to see if it is at least partially contained in the view volume (sometimes shaped as a frustum) (step
616
). If the polygon is not in the view volume, it is discarded. Otherwise, processing continues.
The third step is face determination, where polygons facing away from the viewing point are discarded (step
618
). Generally, face determination is applied only to objects that are closed volumes.
The fourth step, lighting computation, generally includes the set up for Gouraud shading and/or texture mapping with multiple light sources of various types but could also be set up for Phong shading or one of many other choices (step
622
).
The fifth step, clipping, deletes any portion of the polygon that is outside of the view volume because that portion would not project within the rectangular area of the viewing plane (step
624
). Conventionally, coordinates including color texture coordinates must be created for each new primative. Polygon clipping is computationally expensive.
The sixth step, perspective divide, does perspective correction for the projection of objects onto the viewing plane (step
626
). At this point, the points representing vertices of polygons are converted to pixel-space coordinates by step seven, the screen space conversion step (step
628
).
The eighth step (step
632
), set up for an incremental render, computes the various begin, end and increment values needed for edge walking and span interpolation (e.g.: x, y and z coordinates, RGB color, texture map space, u and v coordinates and the like).
Within the drawing-intensive functions, edge walking (step
634
) incrementally generates horizontal spans for each raster line of the display device by incrementing values from the previously generated span (in the same polygon), thereby “walking” vertically along opposite edges of the polygon. Similarly, span interpolation (step
636
) “walks” horizontally along a span to generate pixel values, including a z-coordinate value indicating the pixel's distance from the viewing point. Finally, the z-test and/or alpha blending (also referred to as Testing and Blending) (step
638
) generates a final pixel-color value. The pixel values also include color values, which can be generated by simple Gouraud shading (that is to say, interpolation of vertex-color values) or by more computationally expensive techniques such as texture mapping (possibly using multiple texture maps blended together), Phong shading (that is to say, per-fragment lighting) and/or bump mapping (perturbing the interpolated surface normal).
After drawing-intensive functions are completed, a double-buffered MUX output look-up table operation is performed (step
644
Arnold Vaughn T.
Benkual Jack
Dodgen Stephen L.
Duluk, Jr. Jerome F.
Go Shun Wai
Ananian R. Michael
Apple Computer Inc.
Bella Matthew C.
Dorsey & Whitney LLP
Monestime Mackly
LandOfFree
Apparatus and method for geometry operations in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for geometry operations in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for geometry operations in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124211