Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1996-07-01
2001-01-09
Jankus, Almis R. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S441000
Reexamination Certificate
active
06172678
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to a three-dimensional (simply referred to as 3D, hereinafter) image processing apparatus and method, and particularly relates to a 3D image processing apparatus and method which display on a two-dimensional (simply referred to as 2D, herein after) screen a projection image of a 3D polyhedral object.
2. Description of the Related Art
When displaying a 3D object on a 2D screen such as a CRT display by applying a perspective transformation and the like, there is a need to carry out hidden surface removal processing which makes objects hide other objects which are distanced further from the perspective view point. Methods of hidden surface removal processing include the Z-sort method, the Z-buffer method and the scan-line method.
The Z-sort method has an advantage over other methods in that it can be carried out at a high speed, but has a disadvantage in that it cannot draw objects correctly when some objects overlap other objects. The Z-buffer method eliminates this disadvantage of the Z-sort method by comparing one polygon with another polygon with regard to their distances from the perspective view point at each pixel of the image. In the Z-buffer method, the color and the depth, i.e., the Z value (the distance from the perspective view point), of a polygon are stored in a memory for each pixel of the image. When a new polygon needs to be displayed, the Z value of the new polygon is compared for each pixel with the Z value stored in the memory. only when the new Z value is smaller than the old Z value, will the Z value of the a pixel be updated. At the same time, the color of the new polygon for that pixel is stored in the memory. Thus, objects distanced further from the perspective view point are overwritten by nearer objects, which results in an appropriate image with hidden surfaces removed.
The problem is that the Z-buffer method needs a Z-buffer memory for storing a Z value of objects for each pixel, and, thus, requires a large amount of memory volume for the entire image. Further, in order to improve image drawing speed, a method may be considered in which the Z-buffer memory is connected with a image drawing processing device in dot parallel and thereby Z values of a plurality of dots are read and written in parallel. However, this method needs a plurality of memories serving as the Z-buffer memory.
The scan-line method is suitable for a serial processing, since it utilizes a strong correlation existing between adjacent pixels within one scan-line or adjacent pixels across scan-lines when displaying the color of each pixel for consecutive scan-lines. However, this method requires a large amount of computation and a complex control logic.
A method for hidden surface removal processing with a hybrid nature between the Z-buffer method and the scan-line method is disclosed in the Japanese Laid-Open Patent Application No. 62-100878, which utilizes a correlation across scan-lines and uses the Z-buffer method within one scan-line. This Laid-Open Patent Application discloses a hidden surface removal processing apparatus comprising a depth register for storing a depth (Z value), a luminance register for storing luminance data (with color), an adder for demarcating a plane segment, adding a displacement of depth, comparing depth data with each other by using a time division, an input/output device for outputting information about an input plane segment token through one pipeline register while updating that information, and a luminance data bus for outputting data stored in the luminance register. However, in the above-described apparatus, because the above-described hardware is needed for each dot on a scan-line, the size of the entire hardware may be considerably large.
An image processing apparatus which places patterns on each polygon to be displayed and thus performs mapping is disclosed in Japanese Laid-Open Patent Application No. 5-120449.
According to this image processing apparatus, patterns are placed inside a polygon and the patterns placed inside a polygon vary as a configuration of the polygon varies.
However, in the image processing apparatus which performs mapping, although mapping on polygons can be easily performed, the Z-sort method is used as the hidden surface removal for polygons. Therefore, an object may not be correctly drawn when polygons overlap other polygons.
In order to solve this problem, an image processing apparatus which performs mapping and uses the Z-buffer method as the hidden surface removal method for polygons is disclosed in Japanese Laid-Open Patent Application No. 7-105404 (corresponding to the U.S. patent application Ser. No. 08/317,116 filed on Oct. 3, 1994). This Laid-Open Patent Application discloses a method in which each polygon vertex has mapping X, Y addresses and a Z value of the polygon, the mapping X, Y addresses and polygon Z value is caused to vary along an outline of the polygon and thus an interpolation calculation is performed. Then, through the hidden surface removal using the Z-buffer method, a polygon which is located nearest to the perspective view point for a pixel position is obtained. Based on the X address of at least one end of a scan-line between two opposite sides of the obtained polygon, mapping pattern information and displacement of the mapping pattern information, a mapping pattern address is calculated. According to the calculated mapping pattern address, a mapping pattern memory is accessed, thereby R, G, B or a luminance value of each dot is read out, the read R, G, B or luminance value is transferred to a CRT, and thus an image having mapping performed thereon is displayed.
However, in the Z-buffer method in the related art used in the above-described apparatus, because a dot at the same address is updated many times in a frame memory, overall processing speed depends on the frame memory access speed capability.
Further, in a case where access in the frame memory is performed in dot parallel in order to achieve a high-speed Z-buffer hidden surface removal, because interface of the frame memory should be of a multi-bit interface, it is necessary to use as the frame memory a plurality of memories, each having a small capacity, thus data processing efficiency may not be high and high costs may be required.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a 3D image processing apparatus by which the above-described problems occurring in the related art can be solved and high-speed mapping can be performed even using the Z-buffer method.
According to the present invention, mapping pattern X, Y addresses and a polygon Z value are provided for each polygon vertex, the addresses and Z values are used for interpolating mapping pattern addresses and Z values for each side of the polygon through a digital differential analysis (abbreviated ‘DDA’), thus interpolated data is used for interpolating mapping pattern addresses and Z values for the interior of the polygon on a scan-line also through the DDA, a Z-buffer hidden surface removal operation is performed for a plurality of consecutive dots on the scan-line in parallel, and mapping pattern addresses of the plurality of consecutive dots on the scan line are written in a first one of two memory divisions of a color line memory when it is allowed according to the result of the hidden surface removal operation.
Thus, all the polygons on the scan-line are processed. Thereby, all the processing to be performed for the scan-line has been completed and therefore the dots of this scan-line are written in a frame memory sequentially. While the sequential writing in the frame memory is being performed as writing data is being read out from the first memory division of the color line memory, the other memory division of the color line memory is used for writing mapping memory addresses for the subsequent scan-line.
Thus, 3D image data processing including hidden surface removal is completed for each scan-line one by one sequentially. In this system, necessary
Cooper & Dunham LLP
Jankus Almis R.
Ricoh & Company, Ltd.
LandOfFree
Image processing method and apparatus including hidden... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing method and apparatus including hidden..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing method and apparatus including hidden... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2497310