Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-02-08
2001-11-27
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S441000, C345S621000
Reexamination Certificate
active
06323874
ABSTRACT:
FIELD OF THE INVENTION
The field of the invention is computer graphics, and particularly relates to recursively subdividing a frame buffer in an order determined by a space-filling curve to render a graphic object such as a primitive.
BACKGROUND OF THE INVENTION
In the field of computer graphics, an image is represented as a rectangular grid of picture elements. Each picture element is called a pixel. A pixel is a piece of information (data) that represents one solid color, and is stored in a part of a computer's memory called the frame buffer.
An image is displayed on a screen. An example of a screen is a cathode ray tube (CRT), which is commonly used as the display for a computer. An image is displayed on a screen by mapping the pixels stored in the frame buffer onto the screen.
An image stored as pixels in a frame buffer can be generated mathematically, i.e., as the result of mathematical calculations performed by a computer processor. An example of such a processor is an Application Specific Integrated Circuit (ASIC), which is specifically designed to efficiently and rapidly perform computer graphics functions.
The processor sends drawing instructions to an apparatus called a display controller. An example of some drawing instructions is as follows:
(1) set the fill color to red
(2) start at location
74
,
19
on the screen
(3) draw a square that is 15 pixels wide
These drawing instructions tell the display controller to make every pixel inside the image red (1), start at a location 74 pixels from the left of the screen and 19 pixels down from the top of the screen, and then draw a square 15 pixels wide. The display controller uses these drawing instructions to set the right values for the correct pixels in the frame buffer which, when they are mapped to the screen, will produce the red square described in the drawing instructions.
A primitive is an image that can be drawn directly from drawing instructions to the frame buffer by the display controller. Primitives are typically simple shapes such as a triangle, a square, a line, a circle, a point, a regular polygon, etc. The use of primitives can facilitate the drawing of complex images to the frame buffer. Together, these primitives produce the image when the frame buffer is mapped to the screen.
The process of translating drawing instructions to pixels in a frame buffer is called rendering. In one known rendering system, the value of all of the pixels in an image are computed once for each object in the image. After the effect of a single object on all of the pixels is computed, the effect of the next object on the value of the pixels is determined. Thus, a pixel can be revisited and its value adjusted numerous times. This rendering method becomes slower as the number of objects in an image increases. An example of this type of rendering is called Z-buffering, which renders one object at a time onto the frame buffer, and thus a single pixel can be revisited many times.
Certain techniques render pixels without regard to the certain efficiencies that can be realized from the fact that they are part of the same object, or simply near each other within the same object. For example, in
FIG. 1
, pixels labeled
1
,
2
and
5
are part of the same object, but the rendering technique ignores this fact, and shifts computations from pixels in this group to pixels outside the group (e.g., pixels
3
and
8
), before returning to the pixels inside the object. This makes inefficient use of caches in rendering the object.
The values of pixels that are nearby to each other in the same object can be more efficiently computed when considered together, rather than in some arbitrary fashion that ignores the fact that they are part of the same object. Certain space-filling curves (such as the Peano curve 901 and Hilbert curve 902 shown in
FIG. 2
) can exploit coherence in two dimensions because they are self-similar at multiple resolutions. If a space-filling curve visits all of the pixels corresponding to a particular object area at one level of resolution, then it can be presumed to have the same property for larger and smaller object areas. This suggests that space filling curves can be used recursively in a rendering scheme. A space-filling curve is topologically continuous, so the areas it visits are always adjacent to each other.
The space-filling curve is used to determine the order in which regions or pixels are checked. As shown in
FIG. 3
, this order is specified by a Hilbert Curve. Pixels in an 4×4 grid are checked in the order shown by the numbers on the Hilbert Curve shown in FIG.
3
.
The recursive use of space-filling curves as a traversal sequence in rendering objects is described in
Space-Filling Curves and a Measure of Coherence
, by Douglas Voorhies, Hewlett Packard Co., Chelmsford, Mass., 1991, published in
Graphics Gems II
, edited by James Arvo, Program of Computer Graphics, Cornell University, Ithaca, N.Y., Academic Press, Inc., 1991, pp. 26-30, 485-486. However, this article does not disclose how to efficiently use a recursive space-filling curve traversal sequence to render a primitive on a screen. Further, the article does not disclose any specific computational techniques at the Boolean level that can make the use of recursive space-filling curve especially efficient.
REFERENCES:
patent: 5543935 (1996-08-01), Harrington
patent: 5602943 (1997-02-01), Velho et al.
patent: 5867166 (1999-02-01), Myhrvold et al.
patent: 5903270 (1999-05-01), Gentry et al.
patent: 5963956 (1999-10-01), Smartt
patent: 5999189 (1999-12-01), Kajiya et al.
patent: 6021406 (2000-02-01), Kuznetsov
patent: 6058211 (2000-05-01), Bormans et al.
patent: 6084595 (2000-07-01), Bach et al.
Voorhies, Douglas,Graphics Gems II, “Space-Filling Curves and a Measure of Coherence,” 1991, pp. 485-486.
Havan Thu-Thao
Luu Matthew
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
System and method for rendering an image 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 rendering an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for rendering an image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2604171