Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-08-24
2003-05-13
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S440000, C345S420000
Reexamination Certificate
active
06563500
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This application claims priority under 35 U.S.C. §§119 and/or 365 to 98-35420 filed in Korea on Aug. 29, 1998, and 99-19620 filed in Korea on May 29, 1999; the entire content of which is hereby incorporated by reference.
The present invention relates to coding of three-dimensional (3D) mesh data, and more particularly, to a progressive coding method and apparatus using topological surgery with respect to three-dimensional (3D) mesh data used in the fields of motion picture experts group-4 synthetic and natural hybrid coding (MPEG-4 SNHC), virtual reality modelling language (VRML) and the like.
2. Description of the Related Art
In transmitting 3D objects composed of 3D mesh data, it is very important to progressively restore transmitted data as well as to effectively code the 3D mesh data. In the event that a data error is generated due to a transmission path error, a progressive restoration would allow transmitted data to be partially restored and minimize the amount of mesh data to be retransmitted. The progressive restoration method which is robust against such communication path errors can be effectively used in wireless communications or low transmission rate communications.
In the conventional coding method of 3D mesh data, since the mesh data is continuously coded, it is almost impossible to partially restore data before an entire bitstream is received. Also, due to transmission path errors generated during transmission, even if only a part of the data is damaged, the entire bitstream of data must be received again. For example, ISO/IEC JTC1/SC29/WG11 MPEG98/W2301, “MPEG-4 SNHC Verification Model 9.0” proposed by I.B.M. Corp. is currently being adopted as an MPEG-4 SNHC 3D mesh coding technology.
In MPEG-4 SNHC, mesh coding is designed based on VRML. In the VRML, a mesh is described in a node form referred to as an IndexedFaceSet. One of the main technologies for coding mesh data is a topological surgery proposed by I.B.M. Corp. According to this technology, it is assumed that any given mesh is topologically the same as a sphere. Then, the mesh is cut along given cutting-edges to generate a triangle spanning graph having a binary tree structure. Here, the cutting-edges defined for cutting the mesh are configured such that it connects vertices of the mesh, that is, it is given as a tree structure having a loop. The cutting-edges are referred to as a vertex spanning graph. Thus, two tree structures, that is, the triangle spanning graph and the vertex spanning graph, are coded/decoded, thereby restoring the original mesh without loss.
According to MPEG-4 SNHC, although there may be multiple IndexedFaceSets in a VRML file, compression is generally performed on the unit of one IndexedFaceSet. However, a single IndexedFaceSet can be formed by several connected components. In other words, assuming that a set of polygons capable of connecting vertices is a connected component, IndexedFaceSet can be formed by several connected components.
In general, for fast graphics processing, modeling must be performed in units of triangles. These triangles are not formed randomly but are preferably connected to each other in the form of strips or fans. Also, the more symbols that are repeatedly represented, the better the compressibility is. To this end, a mesh formed by a single long triangular strip is proposed by I.B.M. Corp. in view of fast graphics processing and better compressibility.
FIGS. 1A through 1F
illustrate a conventional procedure for generating a vertex spanning graph and a triangle spanning graph in an example of a triangular mesh.
FIGS. 1A and 1D
illustrate a method for cutting a mesh along cutting-edges drawn by a thick line.
FIG. 1B
illustrates the overall format of the cutting-edges.
FIG. 1E
illustrates the configuration of edges and vertices produced by cutting along the cutting-edges shown in FIG.
1
B.
FIG. 1C
illustrates a vertex spanning graph made by connecting vertices which reference cutting points.
FIG. 1F
illustrates a triangle spanning graph in which a strip which is a set of connected triangles by cutting the mesh along the vertex spanning graph. Also, if the triangle spanning graph is generated by the method shown in
FIGS. 1A through 1F
, the length of a run of two branching runs in the triangle spanning graph becomes considerably shorter than the other.
FIGS. 2A through 2D
illustrate an example of a topological surgery technique applied to actual mesh data. In a vertex spanning graph, a branch can branch off into several branches.
FIG. 3
illustrates an example of a vertex spanning graph having a loop, in which a vertex run returns to a location of one of the previous vertices. Since a mesh can be formed by several connected components, each connected component forming the mesh generates a pair of a vertex spanning graph shown in
FIG. 1F and a
triangle spanning graph shown in FIG.
1
C. Therefore, if a single IndexedFaceSet is coded, several pairs of triangle spanning graphs and vertex spanning graph can be obtained.
The method for restoring the data coded by the above-described method is as follows:
1. A bounding loop is generated using a vertex spanning graph.
2. When the third vertex of a triangle branching off in a triangle spanning tree is referred to as a Y-vertex, the Y-vertex is calculated using bitstreams of the triangle spanning tree.
3. Triangles or polygons are generated using a triangle marching bit of the triangle spanning graph.
Lossless compression using arithmetic coding of the vertex spanning graph and the triangle spanning graph has been proposed by I.B.M. Corp. However, according to this method, in order to reconstruct the original structure, all bitstreams must be input and the following problems arise:
1. Since all bitstreams must be input in order to decode data, in any event of a transmission error, all bitstreams must be retransmitted.
2. In the case when the magnitude of compressed data is large, it takes a long time to transmit the data completely and a user must wait during such a time.
To overcome the disadvantages of the conventional technology, the following functions must be satisfied.
1. Even if a transmission error is generated, only the portion having the transmission error can be retransmitted, thereby reducing the network load and the transmission time.
2. Restoration is allowed in which only a part of the data and triangles or polygons for the restored portion are processed to be displayed on a screen.
Implementation of these two functions while maintaining the basic structure of the conventional method proposed by I.B.M. Corp. depends on effective processing of the bounding loop and Y-vertex, as shown in FIG.
4
. In order to calculate a Y-vertex in a restoration process, at least one of two branching triangle runs must be received. In
FIG. 1F
, points
10
,
14
and
18
are Y-vertices. For triangles within a triangle run, indices for the three vertices of each triangle can be determined using the marching bit pattern and the bounding loop. However, in order to determined the indices of Y-vertices which are the third vertices of branching triangles, all bitstreams for one of two triangle runs next to the branching triangles must be received. Therefore, the triangles next to the branching triangles cannot be restored to be displayed until subsequent bitstreams are received. This problem is not generated in the method proposed by I.B.M. Corp., which is based on the assumption that all bitstreams are received. However, in order to restore and display the triangles in the input order, this problem must be solved.
FIG. 5
is a conceptual block diagram of a three-dimensional (3D) mesh information coding/decoding method adopted in a conventional MPEG4 transmission system. In
FIG. 5
, 3D mesh data
100
is divided into connectivity information and geometry information and coded by a connectivity coder
102
and a geometry coder
103
. Here, vertex structure information
105
is transmitted from the connectivity coder
102
to a geometry coder
103
. The
Han Mahn-jin
Jang Euee-seon
Kim Sung-jin
Seo Yang-seock
Song Mun-sup
Burns Doane , Swecker, Mathis LLP
Jankus Almis R.
Sealey Lance W.
LandOfFree
Progressive 3D mesh coding method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Progressive 3D mesh coding method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Progressive 3D mesh coding method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3078296