Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-07-19
2002-10-22
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S473000
Reexamination Certificate
active
06469701
ABSTRACT:
Triangle meshes have become the most common representation for complex surfaces. Most three dimensional objects available on the internet are supplied in a format which is based on triangle meshes or polygonal meshes, which can easily transformed into triangle meshes. Especially, in the domain of the internet storage space efficient representations of triangle meshes are important. Therefore a wide variety of compression algorithms are available.
3D-hardware support is primarily based on the rendering of triangles. Each triangle is specified by its three vertices, where each vertex contains three coordinates, possibly the surface normal, material attributes and/or texture coordinates. The coordinates and normals are specified with floating point values, such that a vertex may contain data of up to 36 bytes. Thus the transmission of a vertex is expensive and the simple approach of specifying each triangle by the data of its three vertices is wasteful as for an average triangle mesh each vertex must be transmitted six times.
The introduction of triangle strips helped to save unnecessary transmission of vertices. Two successive triangles in a triangle strip join an edge. Therefore, from the second triangle on, the vertices of the previous triangle can be combined with only one new vertex to form the next triangle. As with each triangle at least one vertex is transmitted and as an average triangle mesh has twice as many triangles as vertices, the maximal gain is that each vertex has to be transmitted only about two times. Two kinds of triangle strips are commonly used—the sequential and the generalized triangle strips. In generalized triangle strips an additional bit is sent with each vertex to specify to which of the free edges of the previous triangle the new vertex is attached. Sequential strips even drop this bit and impose that the triangles are attached alternating.
It is an object of this invention to propose a method for compressing and decompressing large geometric data sets which is fast and simple.
SUMMARY OF THE INVENTION
The method of the invention compresses triangle meshes which consist of a list of vertices and a list of triangles, each triangle containing the three vertex indices and the indices of the three edge-adjacent triangles. If the latter adjacency information is not known it can be easily computed through hashing.
The invention is based on a region growing traversal of the triangle mesh starting for each edge-connected component with an arbitrary triangle of this component. The border of the growing region is called the cut-border. It divides the mesh into the inner and the outer part, which contain the already compressed and the remaining triangles respectively.
Triangles are added to the inner part at a distinguished current cut-border edge which will be called the gate. After each addition of a triangle the gate moves on to another cut-border edge, until all triangles of an edge-connected component of the triangle mesh have been compressed. This is done for each edge-connected component.
The compressed representation contains for each triangle a bit code of an operation identifier which tells how the triangle was formed upon the gate. There are three cases: the gate is an edge of the mesh border, the gate forms a triangle with a vertex on the cut-border or the triangle is formed with a new vertex. The different operations are called “border”, “new vertex” and “connect”. The “connect” operations take one parameter which specifies the offset of the third vertex relative to the gate. The “connect” operations with offset one and minus one are also called “connect forward” and “connect backward”. All other “connect” operations split the cut-border into two loops. As the triangle meshes describe two dimensional surfaces in three dimensional space, two cut border loops can grow together again, actually once for each handle of the triangle mesh. The operation which unifies two loops is called “union” and takes two parameters, the index of the second loop and the offset of the third triangle vertex within this loop.
The cut-border data structure basically consists of a stack of doubly linked lists containing the vertices—or their indices—, which are adjacent to triangles of the inner and the outer part at the same time.
Data at the faces, edges or vertices such as their coordinates are included in the compressed representation each time a new mesh element is added to the cut-border—for example the vertex coordinates of vertex v[i] are encoded after the “new vertex” operation which introduces v[i] into the cut-border.
The decompression algorithm builds the mesh in the same order as the compression algorithm traverses the original mesh. With the help of the indices attached to the “connect” operations the original connectivity can be reconstructed with permuted vertices and triangles. During decompression the edge adjacency information can be reconstructed with no additional cost.
REFERENCES:
Esther M. Arkin, Martin Held, Joseph S. B. Mitchell, Steven S. Skiena, Hamiltonian Triangulations for Fast Rendering.
Reuven Bar-Yehuda and Craig Gotsman, Time/Space Tradeoffs for Polygon Mesh Rendering, ACM Transactions on Graphics, vol. 15, No. 2, Apr. 1996, pp. 141-152.
Michael Deering, Geometry Compression, Computer Graphics Proceedings, Annual Conference Series, 1995.
Francine Evans, Steven Skiena, Amitabh Varshney, Optimizing Triangle Strips for Fast Rendering.
Gabriel Taubin and Jarek Rossignac, Geometric Compression Through Topological Surgery, ACM Transactions on Graphics, vol. 17, No. 2, Apr. 1998.
Daniel Cohen-Or, David Levin, Offir Remez, Progressive Compression of Arbitrary Triangular Meshes.
J. Rossignac, Edgebreaker: Compressing the Incidence Graph of Triangle Meshes, Technical Report GIT-GVU-98-17, May 22, 1998 (Revised Jun. 16, 1998).
Costa Touma, Craig Gotsman, Triangle Mesh Compression.
Quarles & Brady LLP
Vo Cliff N.
LandOfFree
Method for compressing graphical information 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 for compressing graphical information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for compressing graphical information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2997478