Data compression through adaptive data size reduction

• US 6,577,769 B1
• Filed: 09/18/1999
• Issued: 06/10/2003
• Est. Priority Date: 09/18/1999
• Status: Expired due to Term

• Current Assignee: Gamigo Inc.
• Original Assignee: WildTangent Incorporated (Samarion SE)
• Inventors: Smith, Peter D., Kenyon, Jeremy A.
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US09/399,062
• Time in Patent Office: 1,361 Days
• Field of Search: 382/239, 382/232, 382/243, 358/426, 358/1.15
• US Class Current: 382/239
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A computing-device implemented method for compressing data, where such devices include a computer, personal digital assistant (PDA), home appliance, and the like. The data includes bandwidth intensive information such as that used in video conferencing, MPEG and equivalent types of digital video encoding, multi-media data transfers, and interactive gaming. In one implementation, a 3D model has objects defined therein. Each object is defined according to a data collection, each element within the collection having a first data size. A distance is determined between a reference point in the model, and a bounding box for an object. A data reduction factor is selected based, at least in part, on the distance. The data collection is compressed according to the distance by mapping each data of the first data size to data having a second data size smaller than the first data size. Other compression methods and apparatus are disclosed.

Claims

1. A computing-device implemented method for compressing and transferring model data from a content provider to a recipient, comprising:

determining a zoom range for a model object defined according to a data collection of data elements, each data element within the data collection having a spatial location defined at least in part with a standard-format floating point number having a first data size;

selecting a data reduction factor based at least in part on the zoom range; and

compressing the data collection according to the zoom range by mapping each standard-format floating point number of the first data size to data having a second data size smaller than the first data size.

2. A method according to claim 1, further comprising:

determining a length n based at least in part on the zoom range; and

converting each standard-format floating point number into a nonstandard-format floating point number comprising an n-bit length mantissa and an optional sign-bit.

3. A method according to claim 2, further comprising:

constructing a transmission packet comprising plural nonstandard-format floating point numbers of equal bit-length followed by a stop word; and

providing the transmission packet to the recipient.

4. A method according to claim 1, further comprising:

for each standard-format floating point number, determining a truncation factor based at least in part on the zoom range;

converting each such standard-format floating point number into a nonstandard-format floating point number truncated according to the truncation factor; and

constructing a transmission packet comprising at least one pairing of an indicator field followed by a following nonstandard-format floating point number;

wherein the indicator field identifies a bit length for each following nonstandard-format floating point number.

5. A method according to claim 1, further comprising:

for each standard-format floating point number, determining a truncation factor based at least in part on the zoom range;

converting each such standard-format floating point number into a nonstandard-format floating point number truncated according to the truncation factor; and

constructing a transmission packet comprising groupings of plural indicator fields having fixed length followed by corresponding nonstandard-format floating point numbers, such indicators indicating the bit length for such corresponding numbers; and

packing the transmission packet into a first data word, wherein packing includes determining whether the transmission packet is larger than the first data word, and if so, packing a remaining portion of the transmission packet into at least one subsequent data word.

6. A method according to claim 1, further comprising:

providing a directed graph, such graph comprising a start node, interior nodes, and leaf nodes, each interior and leaf node storing a binary value, such that a recording of a graph traversal from the start node to a particular leaf node corresponds to a particular floating point bit sequence; and

truncating each standard-format floating point number by traversing the directed graph according to the bit values within such standard-format floating point number, and replacing such standard-format floating point number with a record of such traversal;

wherein different traversals of the graph can yield records of differing lengths.

7. A method according to claim 6, the method further comprising:

constructing a transmission packet by packing truncated floating-point numbers into a first data word;

wherein packing includes determining whether the transmission packet is larger than the first data word, and if so, packing a remaining portion of the transmission packet into at least one subsequent data word.

8. A method according to claim 7, for receiving a first floating point number, comprising:

providing the directed graph to the recipient;

receiving a first transmission packet having n bits;

preparing a first traversal record by traversing the directed graph according to the n-bit sequence within the first transmission packet; and

if a leaf node is reached during such traversal, identifying the first floating point number as the first traversal record.

9. A method according to claim 8, further comprising:

receiving a second transmission packet having m bits; and

if a leaf node is not reached after the n-bit traversal, then continuing traversing the directed graph according to the m-bit sequence within the second transmission packet; and

if a leaf node is reached during such traversal, identifying the first floating point number as the combined bit sequences traversed from the first and second transmission packets.

10. A computing-device implemented method for data decompression, such data having been compressed by determining a zoom range for a model object defined according to a data collection having elements of a first data size, selecting a data reduction factor based at least in part on the zoom range, and compressing the data collection according to the zoom range by mapping each data of the first data size to data having a second data size smaller than the first data size, the method comprising:

receiving a compressed data collection corresponding to a model object; and

expanding the data collection according to a predetermined expansion factor by mapping each data of the second data size back to data having the first data size.

11. An article of manufacture comprising:

a machine readable medium; and

a plurality of instructions stored on the machine readable medium to implement a method for compressing and transferring model data from a content provider to a recipient, such that, when executed, the plurality of instructions cause a processor to;

determine a zoom range for a model object defined according to a data collection of data elements, each data element within the data collection having a spatial location defined at least in part with a standard-format floating point number having a first data size;

select a data reduction factor based at least in part on the zoom range;

compress the data collection according to the zoom range by mapping each standard-format floating point number of the first data size to data having a second data size smaller than the first data size;

determine a length n based at least in part on the zoom range;

convert each standard format floating point number into a nonstandard-format floating point number comprising an n-bit length mantissa and an optional sign-bit;

construct a transmission packet comprising plural nonstandard-format floating point numbers of equal bit-length followed by a stop word; and

provide the transmission packet to the recipient.

12. An article of manufacture comprising:

a machine readable medium; and

a plurality of instructions stored on the machine readable medium to implement a method for compressing and transferring model data from a content provider to a recipient, such that, when executed, the plurality of instructions cause a processor to;

determine a zoom range for a model object defined according to a data collection of data elements, each data element within the data collection having a spatial location defined at least in part with a standard-format floating point number having a first data size;

select a data reduction factor based at least in part on the zoom range;

compress the data collection according to the zoom range by mapping each standard-format floating point number of the first data size to data having a second data size smaller than the first data size;

provide a directed graph, such graph comprising a start node, interior nodes, and leaf nodes, each interior and leaf node storing a binary value, such that a recording of a graph traversal from the start node to a particular leaf node corresponds to a particular floating point bit sequence; and

truncate each standard-form at floating point number by traversing the directed graph according to the bit values within such standard-format floating point number, and replacing such standard-format floating point number with a record of such traversal;

wherein different traversals of the graph can yield records of differing lengths.

13. An apparatus comprising:

a processor; and

a machine readable medium, coupled to said processor, having stored thereon a plurality of programming instructions to implement a method for compressing and transferring model data from a content provider to a recipient, such that when executed by the processor the instructions operate to;

determine a zoom range for a model object defined according to a data collection of data elements, each data element within the data collection having a spatial location defined at least in part with a standard-format floating point number having a first data size;

select a data reduction factor based at least in part on the zoom range;

compress the data collection according to the zoom range by mapping each standard-format floating point number of the first data size to data having a second data size smaller than the first data size;

provide a directed graph, such graph comprising a start node, interior nodes, and leaf nodes, each interior and leaf node storing a binary value, such that a recording of a graph traversal from the start node to a particular leaf node corresponds to a particular floating point bit sequence; and

truncate each standard-format floating point number by traversing the directed graph according to the bit values within such standard-format floating point number, and replacing such standard-format floating point number with a record of such traversal;

wherein different traversals of the graph can yield records of differing lengths.