In computerized video graphics systems, it is often desired to fill a sizeable area on the screen with a random texture pattern. For example, a large grassy field or a macadam roadway may be displayed this way. The texturing may be easily accomplished by using a randomly generated number to create each picture element (pixel) in the area. For the moment, assume that the graphic object having the random texture is drawn so that it lies entirely within the display screen. Successive random numbers can be used to generate the object by displaying the pixels in some predetermined order, for example, in raster scan order. By way of an example, FIG. 1 shows a square object 10 sixty-four pixels wide by sixty-four pixels high for a total of 4096 pixels, which can be displayed by scanning each row of sixty-four pixels in succession. If the square 10 is to have a random texture pattern when it is displayed, the value for each pixel may be selected from a sequence of 4096 random numbers. Each random number is sent to a video display processor where it selects the color and luminance for the corresponding pixel.
Most random number generators used in computers generate numbers by synthesizing the equation y=AX+B. This equation is easily implemented in hardware using a shift register with feedback. The values for A and B are chosen based on the digital word size of the computer. Initially X is the value of a "seed number" that is loaded into the shift register. Thereafter the value of X is the previously generated random number. These generators produce one number of the random sequence each time they are accessed. Being serial in nature, the random number generators always present the next number in the sequence and cannot skip around in the sequence. The numbers generated by this method are known as congruential numbers and give a uniform distribution with favorable overall statistics. Since by using the same seed numbers for the random number generator the same sequence of numbers can be produced, there is no need to store the pixels for the square. Each time the display is to be refreshed the random number generator can be accessed to create the same texture pattern.
There are several problems with conventional random generators. Because the shift register employs the previous number to generate the next number in the sequence, there is a high correlation between consecutive random numbers. If these random numbers are used to generate a texture display pattern, the correlation between the numbers in the sequence will appear as an obvious visible pattern in the picture.
A second more serious problem arises when the square 10 moves to a position where it is only partially on the display screen (i.e., it is clipped). Then in order to properly display the partial square with the same texture pattern as when it was entirely on the screen, the whole object including those portions that are off the screen must be regenerated. This is because in order for the random number generator properly to create the same texture pattern it must step through the same 4096 number sequence as when the entire square 10 was within the display screen. This is very inefficient and time-consuming.
A related problem occurs if the textured object is rotated on the screen. In this case the rows of the object's pixels no longer coincide with the video scan lines. To display the object in video raster scan order, the random numbers must be obtained in a non-sequential fashion, i.e., step through the random number sequence in increments other than one. For example, if the square 10 in FIG. 1 was rotated 45 degrees so as to appear as a diamond, the raster scan sequence of its pixels would no longer be a row at a time, but rather would be diagonally across the square. In this case, the first pixel 12 in the last row of the object is scanned before last pixel 14 in the first row. The sequence of 4096 random numbers is no longer being used in the order they are generated to create the square 10. The pixel values are obtained by random access to the number sequence, according to the new diagonal scan pattern. However, with congruential psuedo random number generators the numbers may be read out only in a serial fashion, i.e., stepping through the sequence in increments of only one. These devices cannot randomly access the numbers in the sequence.
USPTO Backgrounds
USPTO Backgrounds