Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1996-12-26
2002-09-24
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S441000
Reexamination Certificate
active
06456283
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and system for generating an image in computer graphics, and more specifically to an image generating method and system capable of speedily executing a hidden surface removal.
2. Description of the Related Art
It is known to use a Z-buffer method as an image generating method for generating a hidden surface removed image of a three-dimensional object in computer graphics (for example, Japanese Patent Application Pre-examination Publication No. JP-A-62-222379). The Z buffer method uses a Z buffer storing a depth value of each pixel, indicative of the distance from a viewpoint to each pixel, in the amount of one frame. The Z-buffer also stores a frame buffer storing a brightness value of each pixel, indicative of the brightness of each pixel, in the amount of one frame. For each pixel, the depth value stored in the Z buffer is compared with the depth value of a newly calculated three-dimensional object. The depth value nearer to the viewpoint and the corresponding brightness value are left in the Z buffer and the frame buffer, so that a hidden surface removed image is finally generated in the frame buffer. In this method, it is necessary to read, modify and write to the frame buffer for each of pixels included in a projected image formed by projecting the three-dimensional object onto a picture plane. Therefore, in order to speedily execute the image generation, it is necessary to speedily perform a random access to a large capacity memory which constitutes the frame buffer.
A high speed memory, called SRAM (static random accesses memory) is used in a method for speedily performing a random access to the memory, in order to increase the bus band width of the memory. Alternatively, memories have been operated in a parallel.
In the above mentioned conventional image generation method, in order to speedily perform the random access to the frame buffer, an expensive memory has been used, or alternatively, in order to operate memories in parallel, it has been necessary to use a large number of memories and to increase the number of signal lines in accordance with the degree of parallelism. Therefore, there was a problem in that the apparatus became large scale and expensive.
On the other hand, a large-capacity, low-cost, high-speed-accessible memory such as a high speed DRAM (dynamic random access memory) has recently started to be manufactured. However, since there is a restriction that the random access cannot be freely performed, there occurs a problem in which the performance of the memory cannot be sufficiently utilized in the conventional Z-buffer method.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide image generating method and system in computer graphics, which have overcome the above mentioned problems of the prior art.
Another object of the present invention is to provide image generating method and system capable of speedily generating an image even with a low-cost memory such as a high speed DRAM, by dividing a picture frame into a plurality of rectangular blocks (hereinafter, “block”) and repeating generation of a hidden surface removed block image.
One example of a prior art using a procedure for dividing picture data into a plurality of block areas is disclosed by Japanese Patent Application Pre-examination Publication No. JP-A-01-112377 entitled “Picture Information Processor”. However, this apparatus is configured to encode in units of blocks, and is completely different in object and in construction from the present invention.
In an image generation method for generating a hidden surface removed image, an object located in a three-dimensional space being defined as a collection of primitives which are fundamental shapes, and a hidden surface removal being conducted on the basis of a depth value indicating a distance from a viewpoint to each of pixels in a picture frame composed of pixels arranged in the form of matrix, the method in accordance with the present invention is characterized by including dividing the picture frame into a plurality of rectangular blocks, preparing a cache memory for storing a brightness value and a depth value of each pixel, in the amount of at least one block, and repeating a processing including to segment the primitive into a collection of in-block spans which are completely included in one block, and to generate on the basis of the collection of in-block spans a hidden surface removed block image in the cache memory, whereby an image of one picture frame is generated.
Alternatively, in an image generation method for generating a hidden surface removed image, an object located in a three-dimensional space being defined as a collection of primitives which are fundamental shapes, and a hidden surface removal being conducted by using a Z buffer and a frame buffer, which correspond to position of pixels in a picture frame composed of pixels arranged in the form of matrix, and which respectively store a depth value indicating a distance from a viewpoint to each pixel and a brightness value indicating a brightness of each pixel, on the basis of the depth value, the method in accordance with the present invention is characterized by including:
a cache initializing step for initializing into an empty condition a cache memory capable of storing pixel values in the amount of at least one rectangular block of a plurality of rectangular blocks obtained when the picture frame is divided into the plurality of rectangular blocks;
a step for discriminating whether or not a primitive exists, in which if in all the primitives constituting the object there exists a primitive which has not yet been extracted, the primitive is extracted, and if there is no primitive which has not yet been extracted, the processing goes into an ending processing;
a projected block extracting step for extracting all blocks including a projected image of the primitives projected onto the picture frame;
a step for discriminating whether or not a block exists, in which if in all the blocks including the projected image of the primitives projected onto the picture frame, there exists a block which has not yet been extracted, the block is extracted, and if there is no block which has not yet been extracted, the processing returns into the step for discriminating whether or not the primitive exists;
a cache replacement step in which if the pixel values of the extracted block are not stored in the cache memory, the pixel values of the extracted block are written into the cache memory, and when the cache memory stores the pixel values of another block and therefore the pixel values of the extracted block are overwritten into the cache memory, the pixel values of the another block are written into the Z buffer and the frame buffer;
an in-block span generating step for seeking in-block span information obtained when the primitive is segmented into a collection of in-block spans so that a projected image of the primitive completely falls in the extracted block;
a block image generating step for obtaining the pixel values of the pixels included in the in-block spans from the in-block span information, comparing the depth values of the pixel values with the depth values of the extracted block stored in the cache memory, and preserving, in the cache memory, the pixel values of the in-block spans which can be viewed from the viewpoint, and then, returning to the step for discriminating whether or not the block exists; and
a cache exhausting step for writing the brightness values stored in the cache memory into the frame buffer, as the ending processing in the step for discriminating whether or not the primitive exists.
Furthermore, the image generation method in accordance with the present invention is also characterized in that, in the cache replacement step, if the pixel values of the extracted block are not stored in the cache memory, the pixel values of the extracted block are written into the cache memory, and when the cache memory stores the pixel values of a
Brier Jeffery
Fouladi-Semnani Faranak
NEC Corporation
LandOfFree
Method and system for generating image in computer graphics does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for generating image in computer graphics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for generating image in computer graphics will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2856210