Compression of polygonal models with low latency decompression

Details Compression of polygonal models with low latency decompression Compression of polygonal models with low latency decompression

1999-10-01

2002-09-03

Vo, Cliff N. (Department: 2772)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

06445389

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to the field of computer graphics. More specifically, the invention relates to the representation of polygonal models in compressed form suitable for rendering with low latency.
BACKGROUND OF THE INVENTION
Although the geometric modeling domain is being expanded for mechanical computer aided design (CAD) and for animation modeling systems to include free form surfaces, polygonal models remain the primary three dimensional (3D) representation used in the manufacturing, architectural, geographic information systems, geoscience, and entertainment industries. In particular polygonal models are effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mockup applications involving complex Computer Aided Design models.
Furthermore, 3D models are being used as a video compression mechanism for teleconferencing and future video coding standards, e.g., motion picture experts group four (MPEG-4), which is to be used in the next generation of cellular phones and for home entertainment systems (set-top boxes).
A polygonal model may be defined by what is referred to as the model's geometry. A typical definition includes the position of its vertices which are n-dimensional vectors; what is referred to as the model's connectivity, i.e., the association between each face and its sustaining vertices; and/or, by what is referred to as the model's properties. A model's properties may include its colors, normals, and texture coordinates that do not affect the 3D geometry of the model, but that influence the way it is shaded during rendering.
Methods for efficiently representing single-resolution polygonal models in compressed form are known in the prior art. Such methods are known in the art for easily and efficiently triangulating arbitrary polygonal faces. Many of these methods only consider polygonal models that have been defined by triangular meshes. A triangular mesh is a polygonal model in which all model faces are represented as triangles. Graphs and trees for managing these triangular meshes are generally described by R. E. Tarjan in “Data Structures and Network Algorithms,” SIAM, 1983, which is incorporated herein by reference.
New compression methods and systems for compressing polygonal models are described in detail in U.S. Pat. No. 5,825,369 entitled “Compression of Simple Geometric Models Using Spanning Trees”, to J. Rossignac and G. Taubin, and in U.S. Pat. No. 5,905,507 entitled “Compression of Geometric Models Using Spanning Trees”, to J. Rossignac and G. Taubin, both assigned to the assignee of the present invention, incorporated herein by reference in their entirety and collectively referred to hereinafter as Rossignac et al.
Briefly, as described in Rossignac et al., the connectivity of the triangular mesh is preserved, effectively, without loss of information. The vertices of the triangular mesh are organized into a tree referred to as a “vertex spanning tree” and the triangles of the mesh are organized into a tree referred to as a “triangle spanning tree.” A graph referred to as the graph of the triangular mesh is defined by the vertices and edges of the triangular mesh and includes the vertex spanning tree as a sub-graph. A graph referred to as the dual graph of the triangular mesh is defined by the triangles and edges of the triangular mesh and includes the triangle spanning tree as a sub-graph. What is referred to as the order for the edges of the triangular mesh defines the traversal order of both the vertex spanning tree and the triangle spanning tree. Each shape is represented as a simple polygon formed from triangles, the vertex positions and properties are quantized and what is known as entropy is encoded.
FIG. 1
shows a prior art decoder process
1000
, which receives a compressed geometric data stream
1100
as an input and produces an uncompressed geometric data stream
1200
as an output. The percentage of the compressed data stream
1100
that must be received before the decoder
1000
starts producing output is known as decoder latency. In many instances, the decoder
1000
may not be capable of producing an output before receiving the entire compressed data stream
1100
input. If the decoder
1000
must receive the entire bitstream before producing any triangles, it has 100% decoder latency. Ideally, decoder latency is zero and, as the decoder
1000
receives the compressed data input
1100
, simultaneously, it produces an uncompressed output
1200
.
FIG. 2
is a plot
2000
illustrating decoder latency
2100
. The plot
2000
shows the percentage of uncompressed data stream
2300
as a function of the percentage of the compressed data stream
2200
. Decoder latency
2100
is the x-axis intercept. Rossignac et al. achieves very good compression efficiency, but at a cost of 100% decoder latency.
Thus, there is a need for a polygon model compression/decompression technique for the transmission of geometry with low latency without added redundancy.
SUMMARY OF THE INVENTION
It is therefore a purpose of the present invention to improve geometry compression without added redundancy and with low latency;
It is yet another purpose of the invention to improve compressing, storing, transmitting, decompressing polygonal models;
It is another purpose of the present invention to render polygon models directly from a compressed bitstream without requiring an extra decoding step.
The present invention is a method for modifying and reordering a data bitstream of a geometric model without adding redundancy and with low latency. The bitstream is divided into three parts, two parts much smaller than the third and which are the first part of the datastream. The first two parts are a stitching record defining external edge pairs and a triangle tree record which is a representation of the triangle tree of a simple polygonal model. The third, larger part which includes data records for triangles in the triangle tree. The data records can be received incrementally, and as they are received, triangles are output for display.


REFERENCES:
patent: 5825369 (1998-10-01), Rossignac et al.
patent: 5905507 (1999-05-01), Rossignac et al.

Affiliated with

Also associated with

Rating

Compression of polygonal models with low latency decompression does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Compression of polygonal models with low latency decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of polygonal models with low latency decompression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2874640