Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reissue Patent
1999-01-21
2003-04-15
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S504000, C345S519000, C345S519000, C345S519000
Reissue Patent
active
RE038078
ABSTRACT:
FIELD OF THE INVENTION
The field of this invention is twofold: 1) three-dimensional computer graphics, and more specifically, hidden surface removal in three-dimensional rendering; and 2) computer memories, and more specifically, Content Addressable Memories (CAM).
BACKGROUND OF THE INVENTION
Three-dimensional Computer Graphics
Computer graphics is the art and science of generating pictures with a computer. Generation of pictures is commonly called rendering. Generally, in three-dimensional computer graphics, geometry that represents surfaces (or volumes) of objects in a scene is translated into pixels stored in a frame buffer, and then displayed on a display device, such as a CRT.
Pixels may have a direct one-to-one correspondence with physical display device hardware, but this is not always the case. Some three-dimensional graphics systems reduce aliasing with a frame buffer that has multiple pixels per physical display picture element. Other 3D graphics systems, in order to reduce the rendering task, have multiple physical display picture elements per pixel. In this document, “pixel” refers to the smallest individually controllable element in the frame buffer, independent of the physical display device. The display screen
100
is defined as the two-dimensional array of pixels which makes a picture. Display screens
100
can be almost any size. This document uses, as a numerical example for various pixel organizations, a very small display screen
100
of 120×80 pixels.
When a piece of 3D geometry is projected onto a display screen
100
, it affects a set of pixels in the Frame Buffer
1012
. In the context of a particular piece of geometry, the term “pixel” is used to describe one small portion of the projected piece of geometry which has a one-to-one correspondence with a pixel in the display screen
100
.
A summary of the rendering process can be found in: “Fundamentals of Three-dimensional Computer Graphics”, by Watt, Chapter 5: The Rendering Process, pages 97 to 113, published by Addison-Wesley Publishing Company, Reading, Mass., 1989, reprinted 1991, ISBN 0-201-15442-0 (hereinafter referred to as the Watt Reference).
An example of a hardware renderer is incorporated herein by reference: “Leo: A System for Cost Effective 3D Shaded Graphics”, by Deering and Nelson, pages 101 to 108 of SIGGRAPH 93 Proceedings, 1-6 Aug. 1993, Computer Graphics Proceedings, Annual Conference Series, published by ACM SIGGRAPH, New York, 1993, Softcover ISBN 0-201-58889-7 and CD-ROM ISBN 0-201-56997-3 (hereinafter referred to as the Deering Reference). The Deering Reference describes a generic 3D graphics pipeline (i.e., a renderer, or a rendering system) as “truly generic, as at the top level nearly every commercial 3D graphics accelerator fits this abstraction”, and this pipeline diagram is reproduced here as FIG.
1
. Such pipeline diagrams convey the process of rendering, but do not describe any particular hardware. The Generic 3D Graphics Pipeline
1000
has two sections highlighted, the floating-point intensive functions
1020
and the drawing intensive functions performed by a Pixel Drawing Pipeline
4000
. In this document, the term “pixel drawing pipeline” refers to a subset of a 3D graphics pipeline, and it includes everything after the screen space conversion
1003
step up to and including the Z-buffered blend
1010
step. The Pixel Drawing Pipeline
4000
method is shown in a flow diagram in FIG.
4
.
The Pixel Drawing Pipeline
4000
in
FIG. 1
is implemented in hardware by a Pixel Drawing Subsystem
2002
, and a simple block diagram is shown in FIG.
2
. The Pixel Drawing Subsystem
2002
includes a conventional, prior art, Z-buffer
2008
and a Prior Art Rasterize Processor
2010
. As defined here, the Prior Art Rasterize Processor
2010
performs: 1) set up for incremental render
1004
; 2) edge walking
1006
; 3) span interpolation
1008
; and 4) Z-buffered blend
1010
. Some manufacturers do not include the set up for incremental render
1004
as part of the Prior Art Rasterize Processor
2010
. But, it
1004
is included here because the present invention adds a new step before the set up for incremental render
1004
step, and both steps are included in the novel pixel drawing pipelines presented here. The Prior Art Rasterize Processor
2010
performs the Z-buffered blend
1010
by accessing the Z-buffer
2008
over a bus, labelled ZValues
2006
in FIG.
2
. As the Prior Art Rasterize Processor
2010
generates new pixel color values, they are written into the frame buffer
1012
by utilizing the busses PixelColor
2012
and PixelAddr
2016
.
In computer graphics, each renderable object generally has its own local object coordinate system, and therefore needs to be translated from object coordinates to pixel display coordinates. Conceptually, this is a 4-step process: 1) translation (including scaling for size enlargement or shrink) from object coordinates to world coordinates, which is 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, where perspective scaling (farther objects appear smaller) has been performed; and 4)translation from perspective translated eye coordinates to pixel coordinates, also called screen coordinates. These translation steps can be compressed into one or two steps by precomputing appropriate translation matrices before any translation occurs.
FIG. 3
shows a three-dimensional object, a tetrahedron, with its own coordinate axes (x
obj
, y
obj
, z
obj
). The three-dimensional object
3010
is translated, scaled, and placed in the viewing point's
3030
coordinate system based (x
eye
, y
eye
, z
eye
). The object
3020
is projected onto the viewing plane, thereby correcting for perspective. At this point, the object appears to have become two-dimensional; however, the object's z-coordinates are preserved so they can be used later for hidden surface removal techniques. 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 within the display screen and their z coordinates in a scaled version of distance from the viewing point.
Once the geometry is in screen coordinates, it is rasterized, which is the process of generating actual pixel color values. Many techniques are used for generating pixel color values, including Gouraud shading, Phong shading, and texture mapping. In some systems, the Frame Buffer
1012
is augmented with an A-buffer which is used to reduce aliasing. The A-buffer reduces aliasing by keeping track of the percentage coverage of a pixel by a rendered object, which is relevant for edges of projected objects. Hereinafter, the A-buffer will not be explicitly discussed, but is assumed to be optionally included in any rendering system described herein.
Because many different portions of geometry can affect the same pixel, the geometry representing the surfaces closest to the scene viewing point must be determined. Thus, for each pixel, the closest surface to the viewing point determines the pixel color value, and the other more distant surfaces which could affect the pixel are hidden and are prevented from affecting the pixel. An exception to this rule occurs when non-opaque surfaces are rendered, in which case all non-opaque surfaces closer to the viewing point than the closest opaque surface affect the pixel color value, while all other non-opaque surfaces are discarded. In this document, the term “occulted” is used to describe geometry which is 100% hidden by other non-opaque geometry.
As a rendering process proceeds, the renderer must often recompute the color value of a given screen pixel multiple times, because there may be many surfaces that intersect the volume subtended by the pixel. The average number of times a pixel needs to be rendered, for a particular
Apple Computer Inc.
Flehr Hohbach Test Albritton & Herbert LLP
Padmanabhan Mano
Zimmerman Mark
LandOfFree
Graphical rendering system using simultaneous parallel query... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graphical rendering system using simultaneous parallel query..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphical rendering system using simultaneous parallel query... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3019191