Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-09-18
2003-01-28
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06512515
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the fields of data compression, and more particularly, to compressing 3D multimedia transfers over a network connection.
BACKGROUND
3D multimedia includes video conferencing, interactive games, web-page content, audio/visual (A/V)recordings, to name but a few (hereafter collectively “A/V data”). A/V data requires significant storage space, as well as substantial bandwidth to transmit the data over a network. Since most data recipients do not have sufficient bandwidth to receive the A/V data in its original form, A/V data has traditionally been retrieved over a local high-speed bus or specialized high-speed data link.
For example, consider computerized games. Games include simple single-user simulators for pinball, cards, gambling, fighting, etc., or more complex multiple-player turn-taking games where each player competed against the game and ultimately compared scores. Well-known high-tech gaming systems include the Nintendo® and Sony PlayStation® gaming systems. These and other games use geometry to describe two and three-dimensional objects within gaming models. In particular, complex object surfaces are usually represented by a combination of one or more basic object shapes, such as splines, non-uniform rational splines (NURBs), texture maps, and (monohedral) triangle tesselation. Typically, an arbitrary object is defined by triangle tesselation, each triangle having associated spatial coordinate tuples X, Y (and perhaps Z), color, normal, and other attributes. This information, when multiplied by hundreds or thousands of polygons in moderately complex objects, amounts data that must be retrieved from dedicated graphics systems and local storage of graphics data. The data transfer requirements prohibit play against remote players. Although some games have been designed to use a modem to directly call a remote player and establish a game, this solution was often clumsy, slow, and inconsistent; rich content transfer was infeasible.
Or, consider video conferencing applications. As with games, these applications concern transferring large volumes of data. However, these applications must transfer the data to remote locations (e.g., conference participants). Therefore, they have required high-speed data links, e.g., at a minimum, a 128K-bit bonded ISDN connection to the remote participant, or more preferably, a T1 or faster frame-relay connection. Unfortunately, these speedy connection backbones are not generally available to users, and require complex technical support to maintain an active link. Conferencing also shares the modem-game limitation of requiring direct user-to-user connections.
With the recent advent of ubiquitous low-cost Internet connections, it has become a relatively straightforward matter to form a network communication link between multiple remote participants. This has spurred interest in using these generally available links to transfer A/V data. Unfortunately, due to the cost and technical complexity of maintaining ISDN, Frame Relay, and other high-speed links, Internet connections are commonly relatively slow modem-based connections. Since modem connections only generally realize an average modem bit rate of 14-40 KBits per second, these connections are not able to transfer, in reasonable time, rich game content, conferencing data, or other A/V data. This problem is exacerbated with each additional remote participant, since A/V data must now be distributed to multiple recipients—further consuming bandwidth resources.
In an effort to reduce bandwidth constraints, and take advantage of the easily-available slow networking connections, there have been efforts to compress A/V data. For example, data and geometry compression has previously been used to reduce information content in 2D and 3D models. Previous compression attempts include image compression (e.g., JPEG), defining objects with shared features (e.g., shared edges), small texture maps for large areas, etc. examples of some of these and other techniques can be found in U.S. Pat. No. 5,740,409 which teaches a 3D graphics accelerator for compressed geometry, and U.S. Pat. Nos. 5,793,371, 5,867,167, and 5,870,094 which teach various methods for more-efficiently encoding 3D models. These compression techniques are readily applicable to A/V game data (which use models), as well as other A/V data representing data in a compatible compressible format, such as Moving Picture Experts Group (MPEG) digital video encoding.
In addition to geometry compression, general purpose data compression procedures has also been applied to A/V data. Such techniques include Huffman encoding (See Huffman, “A Method For Construction Of Minimum Redundancy Codes”, Proceedings IRE, 40, 10 pages 1098-1100 (September 1952)), Tunstall encoding (See Tunstall Doctoral thesis, “Synthesis of Noiseless Compression Codes”, Georgia Institute of Technology (September 1967)), and Lempel-Ziv encoding (See “A Universal Algorithm For Sequential Data Compression”, IEEE Transactions on Information Theory, IT-23, 3, pages 337-343 (May, 1977)), and run-length encoding of model data (see, e.g., U.S. Pat. No. 3,656,178). These general purpose compression techniques are applicable to all data formats.
Unfortunately, even after application of general purpose and geometric compression, there still remains a significant amount of information that needs to be transferred before games, conferencing, viewers of 3D multimedia, interactive 3D chat rooms, and other applications of A/V data appear to operate as if they are retrieving their data from local storage or high-speed links. Thus, some further data reduction is needed.
SUMMARY
A computing-device implemented method for compressing a data model, defined by plural data points, that is transferred from a provider to a recipient. Typically the provider and recipient are in communication over a network. For a first and a second data point defined in the model, first offsets are determined from the first data point for the second data point. The second data point can then be re-coded in terms of the determined first offsets. The first offsets are coded to require less data storage than required for the first data point, thus allowing them to be transferred more quickly. Second offsets can be cascaded off the first offsets for a third data point defined within the model.
Other compression methods and apparatus are disclosed.
REFERENCES:
patent: 3656178 (1972-04-01), De Maine et al.
patent: 5155772 (1992-10-01), Brandman et al.
patent: 5388209 (1995-02-01), Akagiri
patent: 5740409 (1998-04-01), Deering
patent: 5793371 (1998-08-01), Deering
patent: 5867167 (1999-02-01), Deering
patent: 5870094 (1999-02-01), Deering
Rosenfeld et al. “Digital Picture Processing” Academic Press, 1976, pp. 148-151.*
Huang et al., “Picture Processing and Digital Filtering,” Topics in Applied Physics, Apr. 1975, pp. 43-45, vol. 6, Springer-Verlag, Germany.
Naphatali Rishe, “Interval-based aproach to lexicographic representation and compression of numeric data”, Data and Knowledge Engineering, 8, 4(1992), pp. 339-351., Copyright 1992.
Kenyon Jeremy A.
Smith Peter D.
Columbia IP Law Group, PC
Nguyen Phu K.
WildTangent
LandOfFree
Data compression through motion and geometric relation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression through motion and geometric relation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression through motion and geometric relation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3062266