Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-11-17
2003-06-10
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C345S423000
Reexamination Certificate
active
06577310
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a progressive coding/decoding method and apparatus of three-dimensional (3D) mesh data, characterized by error resilience and incremental build-up, 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 incrementally and error-resiliently 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, progressive restoration allows transmitted data to be partially restored and minimizes the amount of mesh data to be retransmitted. Error-resilient restoration allows transmitted data to be independently restored in units of the transmitted data, irrespective of presence of errors generated in a specific unit of the transmitted data, thereby enhancing-the data restoration efficiency and reducing the standby time of a user. The progressive and error-resilient restoration method which is robust against such communication path errors can be effectively used in wireless communications or low transmission rate communications. The purposes of the present invention are to construct connectivity, geometry and photometry necessary for progressively coding 3D mesh data and providing resilience against data errors, and to propose a coding/decoding method of the same.
In the conventional coding method of 3D mesh data, since the mesh data is wholly 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 a given mesh is the same as a sphere topologically. Then, the mesh is cut along a given cutting-edge to generate a triangle spanning graph having a binary tree structure. Here, the cutting-edge defined for cutting the mesh is configured such that it connects vertices, that is, it is given as a tree structure having a loop. The cutting-edge is 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 basically performed on the unit of one IndexedFaceSet. However, it is allowed to form a single IndexedFaceSet 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 form 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 defined as a strip which is a set of connected triangles generated 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 one of two branching runs in the triangle spanning graph can be 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 is generally formed of 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 triangle spanning graph-vertex spanning graph pairs can be obtained.
The method for restoring the data coded by the above-described topological surgery technology 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, and sets of triangles or polygons having connectivity of a strip shape are generated. Here, the triangles or polygons are formed using a triangle marching bit of the triangle spanning graph.
3. Meshes are restored in accordance with the topological geometry using the mesh data of a tree structure constructed through the steps 1 and 2.
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 mesh data, in any event of a transmission error, all bitstreams must be retransmitted.
2. In the case where the magnitude of compressed data is large, compared to the bandwidth, it takes a long period of time to transmit the data completely and a user must wait during such a period of time. In order to reduce the user's waiting time, meshes must be partially restored and rendered using the transmitted data. However, according to the existing technologies, the number of triangles which can be restored is small, compared to the amount of transmitted bits, in view of the structure of bitstreams.
To overcome the disadvantages of the conventional technology, the following functions must be satisfied.
1. Mesh data must be partitioned by an effective unit size in view of the bandwidth of a transmission path or the characteristic of a decoder, and error resilience must be allowed so that bitstreams having the unit size are restored and rendered by the decoder.
2. Incremental coding/decoding methods must be allowed so that partial restoration and rendering of only a part of the currently received data is possible.
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
FIG. 1F
, points
10
,
14
and
18
are Y-vertices. In order to calculate a Y-vertex, at least one of two branching triangle runs must be processed. In other words, for triangles within a triangle run, the indices of the three vertices of each triangle can be determined using the marching bit pattern and the bounding loop. However, in order to determine 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 trian
Han Mahn-jin
Jang Euee-seon
Jung Seok-yoon
Kim Sung-jin
Seo Yang-seock
Burns Doane , Swecker, Mathis LLP
Sealey Lance W.
Zimmerman Mark
LandOfFree
3D mesh coding/decoding method and apparatus for error... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with 3D mesh coding/decoding method and apparatus for error..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3D mesh coding/decoding method and apparatus for error... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3125930