Generation and use of compressed image data

Details Generation and use of compressed image data Generation and use of compressed image data

1998-09-29

2001-10-09

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S420000

Reexamination Certificate

active

06300952

ABSTRACT:

This invention relates to the generation and use of compressed image data. In particular, it relates to a method and computer system for generating compressed image data, and to a method and image rendering device for rendering pixel data using the compressed image data.
The invention is particularly concerned with graphics data which is intended for display on a monitor associated with a computer system or some other control means including a processor means. For instance, the display may be the monitor of a computer system, the graphics data generated being stored on the memory of the computer system or on, for instance, a CD-ROM and being retrieved for rendering to the monitor of the computer system. Alternatively, the compressed image data for rendering to the monitor may be retrieved from a remote source. It is a characteristic of such systems that the image rendering device which displays the compressed image data has associated therewith a user interface which enables user interaction.
One objective for the local image rendering device is to allow pixel data to be rendered for display with the minimum amount of time.
An objective for forming the compressed image data from the image source is to represent the original image in a useful format which allows rendering time to be kept to a minimum yet results in a flexible and useful system. A particularly useful feature of flexibility is to allow the display system to receive compressed image data from a number of different image sources without significantly altering the rendering time for display of the pixel data on the local display. Another desirable feature is to reduce the amount of unnecessary pixel data which is generated, particularly in respect of objects which are invisible in the final display.
One known data structure according to which compressed image data is transmitted is a Binary Space Partition (BSP) tree according to which polygons defined in the image to be rendered are held in an index in which each polygon is identified as a list of a number of identifiers. According to convention, each polygon is identified by three identifiers such that they are mapped onto triangles, but this is not essential. The data structure includes a list which maps each identifer onto a point defined in Cartesian coordinates (X,Y,Z). Using this basic format, a BSP tree is established for an image by a process of allocating subdividing polygons. The BSP tree is a useful format for compressed image data, although it does have some limitations.
One of these is that, in rendering an image from compressed image data stored as a BSP tree, pixel data may be generated for polygons that are not in fact visible in the final display. This thus is a waste of processing time.
Moreover, some polygons are required to be split up during formation of the BSP tree so that effectively two polygons have to be created for a single polygon in the image.
According to one aspect of the present invention there is provided a method of generating compressed image data defining a 3-D image to be rendered in 2-D comprising:
defining in the image a plurality of hulls, each hull being defined as a set of polygons in a designated coordinate system;
defining for each of at least some of said hulls a portal, each portal being defined as a set of points in the designated coordinate system for that hull and a viewing transform for mapping the portal to another, target hull; and
storing a data structure which holds the defined hulls and portals in a manner describing their physical relationship in the image, the data structure representing the compressed image data.
By defining hulls and portals, a number of different advantages can be obtained.
The viewing transform for each portal that allows one hull to be matched to another allows hulls to be generated on independent coordinate systems which can be related by the viewing transform. Thus, it is possible to provide compressed image data from a number of different image sources each providing their own hulls and portals, provided that the viewing transforms allow for this mapping.
Another advantage is that there is much more flexibility about the arrangement of hulls within the image. The physical relationship of hulls can be changed relative to one another by altering the viewing transforms of the portals. Importantly, this allows for an easy technique for coping with moving objects within an image.
The use of portals also allows clipping to be effected when an image is rendered, for example by frustrum culling so that only that part of a hull which can be seen through the portal from the defined user viewpoint is rendered.
A portal maps the coordinate set of one hull into another, and a transformation is provided to achieve this. Thus, a transformation may map a target hull to a source hull. The definition of each portal may also include an inverse viewing transform. The inverse viewing transform maps the source hull to the target hull. The provision of such inverse transforms allows a viewpoint to move through a portal from a source hull into a target hull.
In the preferred embodiment the data structure comprises an index in which each polygon is stored as a group of identifiers, and a list in which each identifier denotes a point in the designated coordinate system. Typically, a Cartesian coordinate system could be used. A suitable form of data structure is a BSP tree. The data structure can also hold for each polygon, polygon properties such as colour, texture and normals.
In the described embodiment, each portal is defined as a convex quadrilateral by four points. This renders clipping techniques such as frustum culling particularly simple. However, portals of other shapes can be defined.
The method of the invention is particularly useful when applied to an image in which objects are moving. Moving objects are defined in the data structure as respective sub-hulls, each with an associated moving portal in the hull containing the sub-hull. Thus a nomad is a moving portal within a hull, the moving portal mapping into that hull a sub-hull.
The invention also provides a method of operating a computer system to generate compressed image data defining a 3-D image to be rendered in 2-D, comprising:
displaying a representation of the 3-D image on a display;
operating a user interface to define in the representation of the image a plurality of hulls and, for each of at least the sum of said hulls, a portal,
wherein the computer system defines each hull as a set of polygons in a designated coordinate system, and defines each portal as a set of points in the designated coordinate system for that hull and a viewing transform for mapping the portal to another, target hull; and
storing in a memory of the computer system a data structure which holds the defined hulls and portals in a manner describing their physical relationship in the image, the data structure representing the compressed image data.
The invention also provides a computer system for generating compressed image data defining a 3-D image to be rendered in 2-D, the data server comprising:
an interface for allowing a user to define in a representation of the 3-D image a plurality of hulls and, for each of at least some of said hulls, a portal;
a processor for defining each hull as a set of polygons in a designated coordinate system, and each portal has a set of points in the designated coordinate system for the hull with which it is associated and a viewing transform for mapping the portal to another, target hull; and
a memory holding a data structure which holds the defined hulls and portals in a manner describing their physical relationship in the image, the data structure representing the compressed image data.
According to another aspect of the present invention there is provided a method of rendering an image from compressed image data which is in the form of a data structure which holds data defining hulls and portals in a manner describing their physical relationship in the image, wherein each hull is defined as a set of polygons in a designated co

Affiliated with

Also associated with

Rating

Generation and use of compressed image data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Generation and use of compressed image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generation and use of compressed image data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2600941