Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-01-28
2002-07-30
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06426748
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a data compression method and apparatus and in particular to a loss-less data compression technique suitable for use in transmitting and storing interactive three-dimensional graphics such as may be transmitted over the Internet.
Three-dimensional graphics providing, for example, three-dimensionally defined surfaces that may be viewed from a variety of angles or manipulated in three dimensions can be extremely useful in conveying complex ideas.
Such models can be prepared on standard computer systems by assembling the model from a predefined library of standard three-dimensional “shape primitives” such as spheres, cones and cylinders manipulated by “shape operators” such as copying, scaling or rotation according to author commands entered in three-dimensional editor.
A polygon generator receives the model and based on input from a user indicating viewpoint or animation commands, produces a list of polygons having vertices defined in three dimensions. The polygons are selected according to well-known algorithms to fit together to approximate the surfaces of the model. The polygons may be read by a renderer producing a two-dimensional projection of the three-dimensional surface (an image) that can be displayed on a standard computer monitor and viewed by the user. Together the polygon generator and renderer provide an image player, which may be part of the editor.
The two-dimensional image may be stored in a variety of well-known image formats and be transmitted to other users for viewing. This latter approach, however, of transmitting the static image, destroys an advantage of three-dimensional model in that it may be manipulated to be viewed from varying angles to provide a greater understanding of the model's dimensions.
This problem may be avoided by sending repeated images to the remote user manipulating the model-based commands received from the user. This approach is not possible when the image is to be viewed on an off-line electronic book. Alternatively, the polygons themselves may be sent in a file to the user who is also supplied with a copy of the renderer so as to manipulate the model directly.
Both approaches are hampered by the significant time that it takes with current phone technology to transmit the underlying data.
BRIEF SUMMARY OF THE INVENTION
The present inventor has recognized that the processing of generating three-dimensional graphic of(1) designating a set of shaped primitives, (2) modifying the shape parameters of the shape primitives with shape operators, (3) in a series of defined steps so as to produce a polygon file, results in an effective expansion of data by many thousands to one. It follows that by truncating this process at the instruction level (e.g. shape primitives, shape operators and flow instructions), one can create an effective data compression of equal amount.
Accordingly, in the invention, a remote user is provided with only the high level instructions used by the polygon generator to produce the polygons and a “virtual machine” image player for processing those high level instructions. As a first matter, therefore, the present invention provides a loss-less, high ratio data compression technique for transmitting three-dimensional graphics to remote users rapidly for real- time interactivity at the user site.
The inventor has overcome what might be expected to be one limitation of such an approach, that of a limited and static set of shape primitives implicit in a system where the image player is distributed to a large number of users some having limited memory resources, by allowing composite shapes to be defined from the shape primitives. The composite shapes have their own specially defined shape parameters to be easily manipulated just like the shape primitives. The definitions of the composite shapes are by their nature are extremely compact and can be readily stored or transmitted remotely.
Specifically then, the present invention provides a system for simplifying the distribution of three-dimensional graphics. The apparatus includes an editor executable on a first electronic computer having a first graphics display and a first user input device, the editor accepting author commands from the first user input device to produce a shape instruction file. The shape instruction file is composed in turn of: (i) at least one shape primitive identifying a predefined three-dimensional shape having associated shape parameters, and (ii) at least one shape operator operating on the shape primitive according to an operation argument to change ones of the shape parameters associated with the shape primitive. The system further includes a distribution medium for distributing the shape instruction file to a user and an image player at the user's site executable on a second electronic computer having a second graphics display. The image player receives the shape instruction file via the distribution medium to generate on the second graphics display a two-dimensional representation of the three-dimensional graphic by modifying the shape parameters of the shape primitive according to the operation argument of the shape operator.
Thus it is one object of the invention to provide for an extremely compact transmission of three-dimensional graphic that allows full interactivity and manipulation at the user's end. By sending the high level instructions used to create the model, both a high degree of compression and complete interactivity are preserved.
It is another object of the invention to minimize the amount of writeable memory that is occupied by software needed to produce three-dimensional graphics. Because the image player deals with predefined shape primitives, shape operators and flow commands, it may be held in the second computer in read-only memory and the writeable memory saves the fairly compact shape instruction file and necessary image buffers. Writeable memory is generally more expensive and requires greater power consumption than read-only memory.
The editor may include a second image player reading the shape instruction file to generate on the first graphics display, a two-dimensional representation of the three- dimensional graphic by modifying the shape parameters of the shape primitives according to the operation argument of the shape operator.
Thus it is another object of the invention to reproduce the virtual machine producing three-dimensional graphics from high-level instructions for use both by the model programmers and model users.
The distribution medium may be the Internet and the image player may be a plugin to an Internet browser.
Thus it is another object of the invention to allow three-dimensional graphics to be transmitted easily over the Internet.
The shape primitives may include sphere, rectangular prisms, cones, cylinder and plane and the shape parameters may include location, rotation, dimension and color.
Thus it is another object of the invention to select shape primitives that can provide highly compressed forms of the shapes they represent. Thus, for example, a sphere shape primitive defined by a few bytes of data may produce thousands of bytes of polygon data in the resulting three-dimensional graphic.
The editor may further accept author commands to produce flow commands defining flow and execution of the shape operators operating on the shape primitives.
Thus it is another object of the invention to realize the compression inherent in flow commands such as looping and branching. For example, a single looping command may create an arbitrarily large number of shapes in the model.
The editor may further accept author commands from the first user input device to produce at least one composite shape associating multiple author-selected shape primitives, the composite shape having an associated composite shape parameter and including an author-defined mapping section relating the composite shape parameter to ones of the shape parameters associated with the shape primitives of the composite shape primitive. The shape instruction file ma
Hypercosm, Inc.
Nguyen Phu K.
Quarles & Brady LLP
LandOfFree
Method and apparatus for data compression for... 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 apparatus for data compression for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for data compression for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2816865