Computer graphics processing and selective visual display system – Computer graphic processing system – Plural graphics processors
Reexamination Certificate
2002-03-14
2004-07-06
Chauhan, Ulka J. (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphic processing system
Plural graphics processors
C345S582000, C345S601000, C345S552000, C345S522000, C345S556000
Reexamination Certificate
active
06760032
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer graphics, and more particularly to cellular automata application programs in the context of computer graphics.
BACKGROUND OF THE INVENTION
A cellular automata program, or simply a “cellular automata,” is a program in which a set of rules is applied to a discreet array or grid of values in order to create a new value at each point in the grid. Each grid value is a “cell” and the state of the grid constitutes one “generation” of the field of cells. In applying the rules to a generation, a new generation of cells is created. The rules are then applied to the new generation to create yet another, and so forth.
Typically, the rules are local to each cell of the grid, meaning they involve only the cells surrounding each individual cell. One example of such a rule includes: “turn a cell on if it has exactly three neighbors that are also turned on” and “turn a cell off if it has more than three neighbors turned on.” This simplifies the creation of each new generation, as only a small area of the previous generation determines the state of each new cell.
Cellular automata programs are typically run on a 2-dimensional (2D) grid, but can also be specified in n-dimensions. The programs produce useful and interesting patterns as they evolve over time. In the context of computer graphics, the patterns are useful in rendering animated effects and for generating features procedurally.
An example of the foregoing principles will now be set forth in the context of computer graphics. Such example involves combining neighbor sampling and dependent lookups to run Conway's popular “Game of Life” cellular automata programming in a graphics pipeline. For more information on such program reference may be made to: Gardner, Martin, “Mathematical Games,” Scientific
American
, vol. 223, no. 4, Octobre 1970, pp. 120-123; which is incorporated herein by reference in its entirety. While the present example involves Conway'scellular automata formulation, modifications may be applied to run significantly more complex cellular automata programs.
In Conway's“Game of Life,” each cell begins as either “on” or “off” which is represented by a grid of white or black texels, respectively. The rules for creating the next generation for every cell on the map are shown in Table #1.
TABLE 1
1) If a cell is on and has two or three neighbors on, the
cell remains on in the next generation.
2) If a cell is on and has fewer than two or greater than
three neighbors on, the cell is turned off in the next
generation.
3) If a cell is off and has three neighbors on, the cell is
turned on in the next generation.
The game requires that for each cell, the eight cell neighbors and the cell itself be sampled, and logic be applied to the result of the sampling. More information on an exemplary technique for running the game using a hardware stencil buffer may be found with reference to: Neider, Jackie, et. al.,
OpenGL Programming Guide
, Addison-Wesley Publishing Co., 1993.
Prior Art
FIG. 1
illustrates an exemplary rule table
100
that may be used by a cellular automata program. As shown, the rule table
100
embodies the rules of Table #1, and may be used to carry out the foregoing logic necessary for creation of the next generation of cells. The rule table
100
is accessed for each cell at a horizontal coordinate according to the number from zero to eight of neighbors which are “on” and in the vertical coordinate according to whether the cell is “on” or “off.” The table yields an “X” for all cells conditions that should result in an “on” cell in the next generation and is blank for all cell conditions that should result in a “off” cell.
Prior Art
FIG. 2
illustrates an example of how a first cell state
200
may be translated into a second cell state
202
based on the logic embodied in the rule map
100
of FIG.
1
. Prior Art
FIG. 3
shows a more intricate example
300
of how a cellular automata program may operate based on the logic embodied in the rule map
100
of FIG.
1
and yield various patterns over six generations of cells. Application of the rules to each numbered generation results in the subsequent numbered generation.
As mentioned earlier, the foregoing patterns are useful in the context of computer graphics rendering. Traditionally, such cellular automata programs have been implemented on general central processing unit (CPU) architectures utilizing software and a system-to-video card bus or in a limited and inflexible manner using a hardware stencil buffer. Such systems are typically limited in speed and bandwidth. There is thus a need for the ability to run such programs efficiently on a hardware graphics pipeline, avoid a transfer of data across a system-to-graphics pipeline bus, and establish a technique by which the rules that govern the cellular automata may be easily changed.
DISCLOSURE OF THE INVENTION
A system and method are provided for executing a cellular automata program in a hardware graphics pipeline. Initially, cell values are received in a hardware graphics pipeline. Next, the cell values are rendered to generate a condition value utilizing the hardware graphics pipeline. A cell value result for the subsequent generation is read from a rule map according to the condition value utilizing the hardware graphics pipeline. Still yet, additional cell values are stored based on the rule map value.
In one embodiment, the cell values may be referenced by geometry. As an option, the cell values may be referenced as an array of textures.
In another embodiment, a plurality of the cell values may be combined. Further, the combined cell values may be rendered to generate the condition value. Optionally, at least one of the combined cell values may include a cell value from a previous iteration of the receiving, rendering, and reading operations.
In still another embodiment, the condition value may be represented by a color value. In use, a plurality of the condition values may be combined. Moreover, the rule map value may be read from the rule map with the combined condition values.
In still yet another embodiment, the rule map may be 1-dimensional, 2-dimensional, 3-dimensional, 4-dimensional, etc. Further, the rule map may be a look-up table. In use, the rule map value may be read from the rule map utilizing the condition value as an index into the rule map. Optionally, the rule map value may be programmably read from the rule map.
As an option, a plurality of rule map values may be read from a plurality of rule maps. Further, the receiving, rendering, and reading operations may be repeated in multiple iterations utilizing the rule map value from a previous iteration.
In still another embodiment, the receiving, rendering, and reading operations may be repeated in multiple iterations. Such operations may further be programmably repeated. Such programmability may be applied to any desired aspect of the present embodiment.
In another embodiment, the geometry referencing the cell values may be bound to the rule map. Further, the geometry may be bound to information indicating how to access a plurality of the cell values as a texture lookup. While any desired architecture may be used in the context of the present embodiment, the various operations may be executed in a multi-texture engine of the hardware graphics pipeline.
Optionally, the cell values may be written to the rule map itself in the hardware graphics pipeline, thereby creating a self-modifying cellular automata program.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.
REFERENCES:
patent: 6456744 (2002-09-01), Lafe
patent: 6654021 (2003-11-01), Wasserman et al.
patent: 2003/0115021 (2003-06-01), Mates
Iwasaki, K., Dobashi, Y., Nishita, T. Efficient Rendering of Optical Effects within Water Using Graphics Hardware. Ninth Pacific Conference on Computer Graphics and Applications, pp 374-383 (2001).*
Nishita, T., Dobashi, Y. Modeling and renderin
Chauhan Ulka J.
Nvidia Corporation
Silicon Valley IP Group PC
Zilka Kevin J.
LandOfFree
Hardware-implemented cellular automata system and 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 Hardware-implemented cellular automata system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-implemented cellular automata system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3191536