Image analysis – Image compression or coding
Reexamination Certificate
1999-10-05
2003-09-30
Do, Anh Hong (Department: 2724)
Image analysis
Image compression or coding
C345S501000, C345S506000, C345S440000
Reexamination Certificate
active
06628836
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to the field of computer graphics and pertains more particularly to sort middle, screen space, graphics geometry compression through redundancy elimination.
2. Discussion of the Prior Art
Modern computer systems have become increasingly graphics intensive. Dedicated special purpose memories and hardware have been developed to meet this need. The majority of graphics systems are built to accelerate the standard graphics pipeline. As an example
FIG. 1
shows a block diagram of a graphics pipeline
10
having geometry processing
12
and rasterization
14
. The pipeline
10
processes a three dimensional (3D) database
16
having geometric objects
18
and textures
20
into a display image
22
which may be shown to the user on a display monitor (not shown). The geometric objects
18
are typically polygons but may also be triangles, lines, and points. These are also known as primitives. For a particular primitive, its vertices or geometrical point locations (p
x
, p
y
, p
z
) are typically IEEE floating point values. Also, attributes such as colors, normals, and texture coordinates may be specified at each point or for an entire primitive. In binary, the floating point value is made up of one bit for the sign (S), eight bits for the exponent (E or exp), and twenty-three bits for the significand for a total of thirty-two bits. In the case of a triangle, there are three vertices generally having horizontal (x), vertical (y), and depth (z) coordinates in the form of (v
0x
, v
0y
, v
0z
), (v
1x
, v
1y
, v
1z
), and (v
2x
, v
2y
, v
2z
). These primitive vertex data of the geometric objects are sent for geometry processing
12
.
During geometry processing
12
, this primitive vertex data undergoes modeling transforms, viewing transforms, and viewpoint transforms. The resulting screen space primitives are specified by a number of setup variables. Now one has (v
0x
, v
0y
, v
0z
) in screen space. Setup variables include the starting values and slope of all of the parameters of the primitive. The number, precision, and type of setup variables will vary from application to application. Geometry processing output may include the screen space locations (x and y) of the triangle vertices, the shaded color values (red, green, blue, alpha), the depths (z), the slope of the edges, colors, opacities, and depths across scanlines, triangles, or both. Calculation of the setup variables may be done at the geometry processing stage or at the rasterization stage. This geometry information varies by the rasterization process used and the techniques disclosed below can work with many varieties of rasterization.
Turning now to
FIG. 2
, a diagram of scan conversion of two triangle types is shown.
FIG. 2
is for illustration purposes only as there exist many equivalent methods to rasterize triangles. For both triangle types, edge
1
, the longest side, is the primary vertical edge on which scan conversion starts. All scan conversion proceeds in horizontal lines across the triangle as shown. Textures
20
from
FIG. 1
may be used as an auxiliary method for looking up a color of a pixel during the scan conversion process. The texture is literally painted onto the polygon by performing an inverse transform lookup from the pixel coordinate, to the polygon coordinate, into the texture space. Finally, the resulting rasterized data is displayed as the display image
22
.
In general, the efficient utilization of the special purpose memories and hardware of the graphics system has not been fully considered. As graphics technologies and products become more prevalent in consumer areas, slim profit margins are demanding the utmost efficiencies. Images rendered from a large number of triangles can create a fundamental bottleneck in the system. Approaches to relieve this situation are to either modify the geometry to create fewer triangles or to compress the triangles that are given. While compression has been used to make many technologies possible, such as communications and video technologies, compression has not been used in conventional graphics systems. Compression is necessary to achieve efficiency in database representation to conserve disk storage, system memory, cache memory, and special purpose memories. Additional savings can be achieved by conserving system bus bandwidths, which becomes more critical with unified computer architectures where graphics and system memory are one and the same.
A definite need exists for a system having an ability to meet the efficiency requirements of graphics intensive computer systems. In particular, a need exists for a system which is capable of compressing geometric data in a skillful manner. Ideally, such a system would have a lower cost and a higher productivity than conventional systems. With a system of this type, system performance can be enhanced. A primary purpose of the present invention is to solve this need and provide further, related advantages.
SUMMARY OF THE INVENTION
A geometry compression method is disclosed for sort middle, screen space, graphics of the standard graphics pipeline. The pipeline processes a 3D database having geometric objects such as triangles and textures into a display image which may be shown to the user on a display monitor. Lossless compression is achieved through redundancy elimination. Triangles are processed following their transformation to screen space, so that the vertex world 3D locations are determined in their projection to the screen 2D locations. Triangles may also be processed by back projecting the screen space scanlines to test locations against the world space triangles. The general technique is to identify the portions of the data that have little or no effect on the rendered output and remove them during compression. Specific examples disclosed include full packing, constant color, delta coding, edge sharing, slope coding, and color quantization.
REFERENCES:
patent: 4967375 (1990-10-01), Pelham et al.
patent: 5408605 (1995-04-01), Deering
patent: 5793371 (1998-08-01), Deering
patent: 6043824 (2000-03-01), Bier
patent: 6229553 (2001-05-01), Duluk, Jr. et al.
patent: 6268875 (2001-07-01), Duluk, Jr. et al.
patent: 0364243 (1990-04-01), None
M.M. Chow, “Optimized Geometry Compression for Real-Time Rendering,” IEEE Visualization, pp. 347-354 (1997).
M. Deering, “Geometry Compression,” Proceedings of SIGGRAPH '95, pp. 13-20 (1995).
J. Li et al., “Progressive Coding of 3-D Graphic Models,” Proceedings of IEEE, vol. 86, No. 6, pp. 1052-1063 (1998).
G. Taubin et al., “Geometric Compression Through Topological Surgery,” Technical Report RC-20340 (89924), IBM T.J. Watson Resarch Center (1996).
G. Taubin et al., “Geometry Coding and VRML,” Proceedings of the IEEE, vol. 86, No. 6, pp. 1228-1243 (1998).
C. Touma et al., “Triangle Mesh Compression,” Proceedings of Graphics Interface '98, pp. 26-34 (1998).
Ordentlich Erik
Wittenbrink Craig M.
LandOfFree
Sort middle, screen space, graphics geometry compression... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Sort middle, screen space, graphics geometry compression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sort middle, screen space, graphics geometry compression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102372