WO2014005415A1

WO2014005415A1 - System and method for multi-level repetitive structure based 3d model compression

Info

Publication number: WO2014005415A1
Application number: PCT/CN2012/087939
Authority: WO
Inventors: Kangying Cai; Tao Luo; Wenfei JIANG; Jiang Tian
Original assignee: Thomson Licensing
Priority date: 2012-07-04
Filing date: 2012-12-29
Publication date: 2014-01-09

Abstract

A method for multi-level repetitive structure identification in a 3D model and methods for encoding and decoding 3D model based on such multi-level repetitive structures are described. Repetitive structures in the 3D model are identified to increase the compression ratio by reducing the redundancy among the instance components. Multi-level repetitive structures are extracted from a 3D model by first extracting a first-level repetitive structure, based on which second-level repetitive structures are extracted. "Pattern-instance" representation is used to represent the repetitive structure in an embodiment of the present invention. Connected components are examined in the first-level repetitive structure extraction. Parts of the connected components in the patterns and unique components of the first-level repetitive structures are examined to extract the second-level repetitive structure. Encoding of a 3D model is performed by encoding the multi-level repetitive structure, whereby stitching information is calculated for instance components to avoid misalignment at the boundary of components.

Description

SYSTEM AND METHOD FOR MULTI-LEVEL REPETITIVE STRUCTURE BASED

3D MODEL COMPRESSION

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of priority from International Application No.

PCT/CN2012/078190, entitled "System and Method for Multi-Level Repetitive Structure Based 3D Model Compression," filed on July4, 2012. The teachings of the above-identified PCT application are expressly incorporated herein by reference. TECHNICAL FIELD

The present invention generally relates to three dimensional (3D) models. More particularly, it relates to compression and transmission of 3D models in a 3D program.

BACKGROUND OF THE INVENTION

In practical applications, such as3D games, virtual chatting room, digital museum, and CAD, many 3D models consist of a large number of connected components. These multi-connected 3D models usually contain a non-trivial amount of repetitive structures via various transformations, as shown in Fig. 1. An efficient compression method for this kind of 3D models should be able to explore the repetitive structures and extract the redundancy to achieve a high compression ratio.

In PCT application WO2010149492 filed on June 9, 2010, entitled Efficient Compression Scheme for Large 3D Engineering Models, an efficient compression algorithm for multi-connected 3D models by taking advantage of discovering repetitive structures in the input models is disclosed. It first discovers in a 3D model the structures or components repeating in various positions, orientations and scaling factors. Then the repetitive structures/components in the 3D model are organized using "pattern-instance" representation. A pattern is the representative geometry of the corresponding repetitive structure. The instances of a repetitive structure correspond to the components belonging to the repetitive structure and are represented by their transformations, i.e. the positions, orientations and possible scaling factors, with respect to the corresponding pattern and the pattern identification (Pattern ID). To restore the original model from the "pattern-instance" representation, the instance components are calculated by

Inst Comp = Inst Transf x Pattern, (1) where Inst Transf is the transformation matrix transforming the corresponding pattern to the instance component Inst Comp. The decoder calculates the transformation matrix Inst Transf by deriving it from the decoded position, orientation and scaling information, such as

Inst Transf = Func(Pos_Instra, Ori lnstra, Scal lnstra), (2) where Pos lnstra, Ori lnstra and Scal lnstra are the decoded position, orientation and scaling factor of the instance component to be restored. Thus the instance components can be restored by

Inst Comp = Func(Pos_Instra, Ori lnstra, Scal lnstra) x Pattern. (3) The compression scheme disclosed in WO2010149492 has achieved significant bitrates saving compared to traditional 3D model compression algorithms which do not discover repetitive structures.

In a commonly owned PCT application (PCT/CN2012/070877) filed on February 3, 2012, entitled System and Method for Error Controllable Repetitive Structure Discovery Based Compression, the teachings of which are specifically incorporated herein by reference, a method and apparatus for identifying repetitive structures in 3D models to reduce redundancy among instance components, and thus to improve compression efficiency, are disclosed. The instance components can be expressed in a "pattern-instance" representation and a decision is made as to whether to compress the "pattern-instance" representation for the 3D model. For those instance components that are determined to be encoded in "pattern- instance" representation, a verification process is employed to examine the decoding error of the instance components. If the decoding error is below a threshold value, the instance components are compressed in the "pattern-instance" representation. Otherwise, a different encoding mode is used to compress the instance components.

The present invention further solves the problem of 3D model compression and proposes an algorithm which can discover multi-level repetitive structures and further improve compression efficiency. SUMMARY OF THE INVENTION

This invention directs to methods and apparatuses for multi-level repetitive structure identification in 3D model and 3D model compression based on such repetitive structure.

According to an aspect of the present invention, there is provided a method for extracting repetitive structures from a 3D model, which comprises extracting a first-level repetitive structure in said 3D model; and extracting a second-level repetitive structure from at least one of a) said first-level repetitive structure, and b) a unique part from said 3D model which does not belong to said first-level repetitive structure.

According to another aspect of the present invention, there is provided a method for encoding a 3D model, which comprises encoding a repetitive structure from said 3D model, wherein said repetitive structure comprises a first-level repetitive structure and a second-level repetitive structure.

According to yet another aspect of the present invention, there is provided a method for decoding an encoded 3D model, which comprises decoding a repetitive structure from said encoded 3D model, wherein said repetitive structure comprises a first-level repetitive structure and a second-level repetitive structure.

BRIEF DESCRIPTION OF THE DRAWINGS

The above features of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which:

Figure 1 illustrates 3D models with a large number of connected components and repetitive structures.

Figure 2 shows an exemplary flow chart of extracting multi-level repetitive structures from a 3D model according to the principles of the present invention.

Figure 3 shows relationship among various objects in a multi-level repetitive structure representation of a 3D model according to one embodiment of the current invention.

Figure 4 shows pictorial examples depicting symmetric structures.

Figure 5 shows pictorial examples depicting patterns of symmetric structure, symmetric patterns and symmetric unique parts. Figure 6 shows an exemplary block diagram of a 3D model encoder according to one embodiment of the present invention.

Figure 7 shows an exemplary block diagram of a 3D model decoder according to one embodiment of the present invention.

Figure 8 shows an exemplary flow chart of decoding an encoded 3D model according to one embodiment of the present invention.

Figure 9 depicts an exemplary structure of the encoded bitstream for a 3D model according to one embodiment of the present invention.

Figure 10 shows example of flipped instance with regards to original pattern.

Figures 11 and 12 show high-level block diagrams of the PB3DMC codec according to one embodiment of the present invention: Figure 11 : PB3DMC encoder and Figure 12: PB3DMC decoder.

DETAILED DESCRIPTION

In the present invention, a solution to extract multi-level repetitive structure from a

3D model and a solution to compress a 3D model using such multi-level repetitive structures are proposed.

Figure 2 shows an exemplary flow chart of extracting multi-level repetitive structures from a 3D model according to the principles of the present invention. The process starts with inputting a 3D model and extracting first-level repetitive structures from the input 3D model 210. The output of the step 210 comprises first-level repetitive structures (RS I) and first level unique parts (UP_1), wherein a first-level unique part is a part of the 3D model that does not belong to any first-level repetitive structure. In step 220, RS I and UP l are further analyzed to identify if there are second-level repetitive structures. If not, step 230 outputs the RS I and UP l and the process ends; otherwise, step 240 further extracts the second-level repetitive structure RS 2 and the part that does not belong to any second-level repetitive structure is identified as second-level unique part UP 2.

In one embodiment, a repetitive structure at a larger scale, such as at the scale of one or more connected components, is extracted as a first-level repetitive structure RS I, whereas a smaller scale repetitive structure, such as a part of a connected component (e.g. at the scale of a surface in a surface-based model), is extracted as a second-level repetitive structure RS 2. In this embodiment, not only repetitive structures among various components are identified, the repetitive structures within a component are also explored. The former is called "gross repetitive structures" and any instance of this kind of repetitive structures does not share boundaries with other parts of the 3D model. The latter is called "fine repetitive structures" or "symmetric structures" and an instance of the symmetric structures may share boundaries with some other parts of the 3D model. The boundary of an instance could be defined as vertices, triangles or other elements, such as edge, of the 3D model. Note that "symmetric structure" covers a wide range of scenarios that include relationships between structures such as reflection, shifting, rotation etc. In other words, a symmetric structure is invariant under certain transformation. Examples of symmetric structure are shown in Fig. 4, wherein A and B in Fig. 4(a), A' and B' in Fig. 4(b), A" and B" in Fig. 4(c) belong to the same symmetric structure.

With the extracted repetitive structures, each instance component belonging to a repetitive structure can be represented using the corresponding repetitive structure, for example, through a transformation between the instance component and a pattern generated for the corresponding repetitive structure. One exemplary transformation is a transformation matrix between the instance component and the corresponding pattern.

One detailed embodiment of extracting the first-level repetitive structure as a gross repetitive structure can be found in a commonly owned PCT application (PCT/CN2012/070877) filed on February 3, 2012, entitled System and Method for Error Controllable Repetitive Structure Discovery Based Compression, the teachings of which are specifically incorporated herein by reference, and in Kangying Cai, Wencheng Wang, Zhibo Chen, Quqing Chen, Jun Teng. "Exploiting repeated patterns for efficient compression of massive models" . Proceedings of 8th International Conference on Virtual Reality Continuum and its Applications in Industry (VRCAI 2009), 145-150, 2009, the teachings of which are specifically incorporated herein by reference.

Specifically, the repetitive structure discovery is performed by a pair-wise comparison of connected components. In a preferred embodiment, in order to increase efficiency of the comparison, all components are first clustered by utilizing each component's vertex normal distribution as its feature vector for clustering, as disclosed in PCT application PCT/CN2011/080382 filed on Sept. 29, 2011, entitled "Robust Similarity Comparison of 3D Models, " the teachings of which are herein incorporated by reference in its entirety. Only the components belonging to the same cluster are compared with each other.

Two components are aligned first before the comparison. Component alignment involves two steps. First align two components by their positions, orientations and scaling factors. Then they are further aligned using iterated closest points (ICP) algorithm, such as, Rusinkiewicz, S., and Levoy, M. Efficient Variants of the ICP Algorithm, in 3DIM, 145-152, 2001, which includes iterative rotation and translation transformation. Two components are determined as belonging to the same repetitive structure if their surface distance is small enough after being aligned with each other. An example method for calculating the surface distance between two components can be found in N. Aspert, D. Santa-Cruz and T. Ebrahimi, MESH: Measuring Error between Surfaces using the Hausdorff distance, in Proceedings of the IEEE International Conference on Multimedia and Expo 2002 (ICME), vol. I, pp. 705-70. The surface distance threshold value can be determined based on a user input QualityParameter (QP) table, an example of which is shown below:

where FLT MAX is the maximum float point number value.

In a preferred embodiment, repetitive structure discovery generates repetitive structures which consist of patterns and instance components (or instances), and unique components which are connected components that do not belong to any repetitive structures. Patterns are the representative geometry of repetitive structures. Instances are "pattern- instance" representation of the corresponding instance components. In one embodiment, a pattern is not selected as one of the components of the input model; rather it is aligned with the world coordinate system. For example, a pattern can be generated by selecting an instance component of the repetitive structure and moving it to the origin of the world coordinate, rotating it so that its eigenvectors are aligned to the world coordinate. In a different embodiment of generating a pattern, only shifting of a selected instance component to the origin is performed, and no rotation is involved. In this case, the selected instance component would have the least transformation to the pattern, i.e. no rotation in its transformation matrix. Typically, the number of bits allocated to the compressed rotation sub-matrix/part is high. Thus, in this embodiment, there are no bits assigned to the rotation sub-matrix/part for the selected instance component, which reduces the encoded bit rate. In a different embodiment, instance components of repetitive structures are clustered and the instance component which is close to the center of the cluster is picked to generate the pattern. This embodiment leads to small values of the rotation information for most of the instance components in the cluster and thus fewer bits for the rotation information in the compressed bitstream. The instances can be represented by

• A repetitive structure ID or a pattern ID; and

• An instance transformation matrix Inst Transf as described in Eqn. (1 ) or Eqn. (4), which may include information on scaling, rotation and translation etc.

The output patterns for the repetitive structure identified through the above- referenced process are the first-level patterns P (320) and the unique components are the first-level unique components U (330) as one embodiment of the first-level unique part (UP l). Instance components I (325) can be represented by a transformation from the corresponding pattern P to the instance component. After the first-level repetitive structures are identified, second-level repetitive structures or symmetric structures are extracted by examining the first-level pattern and the first-level unique components. Specifically, in this embodiment, first-level patterns and first-level unique components are examined altogether to identify symmetric structures. The process of identifying a second-level repetitive structure is similar to the process for a first-level repetitive structure, but at a smaller scale than the connected components. That is, the above mentioned steps, such as clustering operation, pairwise comparison, alignment etc., are applied to a part of the connected component, such as a surface in a surface-based 3D mode representation.

Based on the results, first-level patterns P can be classified into two categories: symmetric patterns P_s(335), which contain symmetric structures, and regular patterns P_R(340), which do not contain symmetric structures. Similarly, first-level unique components U can also be classified into two categories: symmetric unique components U_s(345), which contain symmetric structures, and regular unique components U_R (350), which do not contain symmetric structures. For P_s and Us, a pattern of each identified symmetric structure, P_Ss (360), is generated. Instances of symmetric structure I_Ss(365), which may include first-level symmetric patterns and/or first-level symmetric unique components depending on where symmetric structures are identified, are represented by transformation between the I_Ss and the corresponding P_ss. The remaining part of the symmetric pattern that does not contain symmetric structures is denoted as the unique part of the symmetric pattern U_Sp (355); and the remaining part of the symmetric unique component that does not contain symmetric structures is denoted as the unique part of the symmetric unique component U_Su (370). As a result, a P_Ss is a second-level pattern; an I_ss is a second-level instance, and a U_Sp or a U_Su is a second-level unique part/component. Fig.3 illustrates the relationship among various patterns, instances and unique components.

Fig. 5 depicts an example for P_ss, P_s and U_s. In this example, the pattern P_s consists of A", B" and C". The unique component U_s consists of B" and C". As can be seen from Fig. 5, the pattern and the unique component share two connected repetitive structures or symmetric structures: B" and C". One example pattern P_ss for each of the symmetric structures is shown in Fig. 5. Then A' ' would be the unique part of the symmetric pattern U_Sp.

In the following, an "instance" or an "instance component" without specifying its corresponding repetitive structure may refer to an instance component of a first-level repetitive structure, I, or an instance of a second-level repetitive structure, I_Ss.

Because of the unavoidable vertex position coding error introduced by most 3D model compression algorithms such as quantization error, using the same method to represent and compress gross repetitive structures and symmetric structures might cause cracks or misalignment on the boundaries of the decoded symmetric instances I_Ss- In order to mitigate the problem, stitching information should be recorded in the compressed bitstream for stitching the decoded instances of symmetric structure and their adjacent parts in the 3D model. For example, the stitching information can be the difference between the vertex positions recovered from different instances which correspond to the same vertex in the original 3D model. For one gross repetitive structure whose pattern consists of symmetric structures, i.e. Ps, there are two options to represent its instances I:

Option A: I is represented as one instance of Ps. That is, I is transformed from P_s.

Option B: I is represented as instances of Pss. That is, I is decomposed into Iss and Usp, and I_Ss is transformed from P_ss.

Using instances to represent symmetric structures might decrease the quality of the decoded 3D model due to the imperfect encoding/decoding of the pattern and the transformation information. In addition, extra stitching information is needed for those instances from the symmetric structures. For these reasons, option A is preferred to limit the number of instances of the symmetric structures.

As a result of the multi-level repetitive structure discovery, the entire original 3D model can be represented and compressed by the following types of objects/elements/data:

• Patterns, which comprise the patterns of gross repetitive structures which do not include any symmetric structures, P_R, the patterns of symmetric structures, P_ss, the unique parts of those gross-repetitive-structure patterns including symmetric structures, U_Sp, and the unique parts of those unique components which do not belong to any gross repetitive structures but have symmetric structures, U_Su- All of these four types of patterns are shaded in Fig. 3. In the encoded bitstream, all the objects that belong to these four types are indexed according to their actual positions in the bitstream so that the decoder can identify the corresponding pattern to decode a certain part of 3D model.

• Instances, which comprise instances of gross repetitive structures, I, and instances of symmetric structures, I_Ss, which are represented by the pattern IDs and transformations from the symmetric patterns P_Ss to the corresponding instance I_Ss-

• Stitching information, which is used to stitch the decoded symmetric instances and their adjacent parts in the decoded 3D model. The adjacent parts can be other decoded symmetric instances or the two types of unique parts defined in the pattern type of objects/data, i.e. U_Sp and U_Su- • Unique components (U_R), which do not belong to any gross repetitive structures and do not include any symmetric structures.

The encoding of a 3D model is thus performed based on the encoding of the repetitive structure from the 3D model and the unique components that do not belong to any repetitive structure. Specifically, the encoding of the repetitive structure is performed by encoding the above mentioned types of objects/data. In general, the encoding of these objects can be done in any order, while in some applications, a specific order is preferred. For example, in applications with on-the-fly decoding, encoding patterns before instance components is preferred so that once instance data are received, the pattern data is already available so that the instance can be decoded immediately. On the other hand, if the instances are encoded before patterns, the decoder has to wait until the pattern data are received to decode a component even though the instance data have been already received. In a different application, unique components are encoded first so that once decoded they can be displayed immediately. As discussed earlier, an instance component I or I_ss is represented by transformation information between the instance component and the corresponding pattern in one embodiment of the present invention. One example of such transformation information is a transformation matrix. According to one embodiment in a commonly owned PCT application PCT/CN2011/082942, filed on November 25, 201 1 , entitled Repetitive Structure Discovery based 3D Model Compression, the teachings of which are herein incorporated by reference in its entirety, the instance transformation matrix Inst Transf is decomposed into four parts, a reflection part (Refle), a rotation part (Rotatl or Rotat2), a translation part (Transl), and a possible scaling part, as shown below:

Inst_Transf = sl x Scaling (4)

where, Rotat Refle can be decomposed into

Rotat_Refle = Refle x Rotatl or

Rotat_Refle = Rotatl x Re fie.

The reflection part Refle which represents a generic reflection transformation about a generic normalized axis (n_x, n_y, n_z) can be expressed as follows:

- 2n_x 2n_xn_y -2n_xn_z

Refle = -2n_xn_y -2n_yn_z (5)

-2n_xn_z -2n_yn_z 1 - 2n^

An efficient way to compress the generic reflection transformation, as shown in Eqn. (5), is to quantize and then compress n_x, n_y and n_z. In a different embodiment of processing the reflection transformation about the generic axis, the method of calculating patterns is adjusted as follows to make coding error of the entire decoded 3D model more controllable: if there exists a reflection part in the transformation for an instance, its corresponding pattern is further aligned with the coordinate axes. By this means, the reflection axes in accordance with transformations from the pattern to its instances can be replaced by the coordinate axes, which is more convenient for compression than some specific axes in view of reconstruction errors.

Fig. 6 shows an exemplary block diagram of a 3D model encoder 600. The encoder comprises an element encoder 620 to encode various types of elements/objects that have been discussed. In an embodiment, the element encoder further comprises a pattern encoding module 622 for encoding the pattern type of objects/elements, an instance encoding module 624 for encoding instance type of objects/elements and a unique part encoding module for encoding unique part type of objects/elements. If the 3D model comprises further information, such as stitching information, the element encoder 620 could further include an extra information encoding module 628 to encode those information. In one embodiment, the encoding modules 622-628 are implemented as separate modules. In a different embodiment, they may be implemented to share some common sub-modules, or even be implemented as one module. The output of the 3D model encoder is an encoded bitstream.

The encoder can take repetitive structure representation of a 3D model as an input to perform the encoding in each module. It can also take a 3D model as an input, and further comprise a repetitive structure extractor 610 to extract the repetitive structure from the 3D model for later encoding. The repetitive structure extractor further comprises a first-level extractor (not shown) for extracting a first-level repetitive structure in the input 3D model and a second-level extractor (not shown) for extracting a second-level repetitive structure. According to one embodiment of the present invention, the second-level repetitive structure is extracted from the first-level repetitive structure, and a unique part from the 3D model which does not belong to the first-level repetitive structure.

The decoding of a 3D model encoded according to the present invention comprises decoding the repetitive structure of a 3D model. Fig. 7 shows an exemplary block diagram of a 3D model encoder 700. The decoder comprises an element decoder 710 to decode various elements/objects of an encoded 3D model and a 3D model reconstruct module 720. In one embodiment, the element decoder 710 comprises a pattern decoding module 712 for decoding the pattern type of objects/elements of the encoded 3D model, an instance decoding module 714 for decoding the instance type of objects/elements of the encoded 3D model and a unique part decoding module 716 for decoding the unique part of the 3D model. An optional extra information decoding module can be included if extra information such as stitching information has been encoded. The encoding modules 712-718 can be implemented as separate modules or they may be implemented to share some common sub-modules, or even be implemented as one module. The decoded various elements are then input to the 3D model reconstruction module to obtain the decoded 3D model.

Note that when the repetitive structure comprises first-level repetitive structures and second-level repetitive structures, the decoding would involve the decoding of two level repetitive structures. Figure 8 shows an exemplary flow chart of decoding an encoded 3D model according to one embodiment of the present invention. The process starts with accessing an input encoded 3D model. Step 810 decodes the pattern type of data/object as described above, such as symmetric structures P_R, the patterns of symmetric structures P_Ss, the unique parts on those gross-repetitive-structure patterns including symmetric structures, Usp, and the unique parts of those unique components which do not belong to any gross repetitive structures but have symmetric structures, U_Su- Step 820 decodes symmetric instances I_Ss- In step 830, stitching information is decoded, and gross-repetitive-structure patterns and unique components including symmetric structures Ps and Us, are decoded in step 840 using the recovered patterns, symmetric instances and stitching information. In step 850, the gross-repetitive-structure instances, I, and unique components which do not belong to any gross repetitive structures and do not include any symmetric structures, U_R, are decoded. The decoder does not necessarily follow the above order during decoding. Any order of decoding, as long as the required information is available at decoding, is possible. Decoding of some objects/data wherein there is no dependency between objects/data, e.g. decoding of U_R and I, can be implemented in parallel.

Fig. 9 depicts an exemplary structure of the encoded bitstream for a 3D model according to one embodiment of the present application, called Pattern Based 3D Model Compression (PB3DMC). The bitstream starts with the header buffer (PB3DMC_stream_header), which contains all the necessary information for decoding the compressed stream: information of whether or not there are unique parts in the original model, information of whether or not there is at least one repetitive structure in the original model, information of whether or not the "grouped instance transformation mode" or "elementary instance transformation mode" is used in this bitstream, information of the original 3D model, information of the type of attributes that instances may have, the 3D model compression method used for compressing geometry, connectivity and properties of all 3D objects (patterns and other parts if necessary), etc. The "grouped instance transformation mode" ("group mode" in short) or "elementary instance transformation mode" ("elementary mode" in short) are detailed in a commonly owned PCT application (PCT/CN2012/070877) filed on February 3, 2012, entitled System and Method for Error Controllable Repetitive Structure Discovery Based Compression, and are briefly explained herein. Recall that each instance has two parts of data: Pattern ID and a transformation matrix. There are two packing modes for the instance data: an elementary mode and a group mode. In the elementary mode, the entire instance data for the instance components are encoded sequentially, i.e. (PID 1, trans 1) (PID 2, trans 2), (PID n, trans n), wherein PID x and trans x are the pattern ID and the transformation matrix for component x, respectively and x =1 , ... , n. In the group mode, PIDs for a group of instances are encoded together followed by the encoding of the transformation matrices for that group of instances, i.e. (PID 1 , PID 2, PID n)(reflection 1 , reflection 2, reflection n), (translation 1 , translation 2, ... translation n), (rotation 1 , rotation 2, ... , rotation n), (scaling 1 , scaling 2, scaling n). In the bitstream, if there is no unique part and repetitive structure in the original model (uni_part_bit == 0 &&repeat_struc_bit = 0), the remaining part of the bitstream is the compressed input 3D model using the 3D model compression method indicated in PB3DMC_stream_header. Otherwise, the next part in the bitstream is the compressed result of all unique components, if there is any. If there is at least one repetitive structure, the next data field is the compressed result of all patterns, which consist of the patterns of gross repetitive structures not including any symmetric structures, the patterns of symmetric structures, the unique parts on those gross-repetitive-structure patterns including symmetric structures, and the unique parts of those unique components which do not belong to any gross repetitive structures but have symmetric structures. If there is at least one symmetric structure, the next data field is the compressed transformation of all instances of symmetric structures. Depending on which instance transformation packing mode is chosen in this bitstream, either compr insta grouped data or compr insta elementary data is the next part in the bitstream, which contains the compressed transformation of all instances of gross repetitive structures.

In the following, the bistream syntax and semantics is described in detail according to one embodiment of the present invention.

The mathematical operators used to describe this specification for repeated structure discovery based compression algorithm are similar to those used in the C programming language. However, integer divisions with truncation and rounding are specifically defined. Numbering and counting loops generally begin from zero.

In addition to the syntax functions, categories and descriptors already used in Scalable 3D model compression (SC3DMC) specification, the following are also used:

f(n): fixed-length coded bit string using n bits (written from left to right) for each symbol, n depends on the code length for each symbol; and

ec(v): entropy-coded (e.g., arithmetic coded) syntax element, including possibly configuration symbols.

PB3DMC stream class

Syntax

class PB D C stream ! | Num. of Bits | Descriptor

Semantics

PB3DMC_stream_header: This data field contains the header buffer.

PB3DMC_stream_data: This data field contains the data buffer.

In the following definition, "symmetric instance" refers to the instance of symmetric structures and "instance" refers to the instance of gross repetitive structures. Patterns consist of the patterns of gross repetitive structures not including any symmetric structures, the patterns of symmetric structures, the unique parts on those gross-repetitive-structure patterns including symmetric structures, and the unique parts of those unique components which do not belong to any gross repetitive structures but have symmetric structures. PB3DMC stream header class

Syntax

Semantics

uni_part_bit: This 1-bit unsigned integer indicates whether there is a unique part, which does not belong to any gross repetitive structures and does not include any symmetric structures, in the 3D model. 0 means there is no unique part and 1 means there is a unique part. Note that for those multi -connected 3D model without any repetitive structure, the entire input 3D model is regarded as a unique part.

repeat_struc_bit: This 1 -bit unsigned integer indicates whether or not there is at least one repetitive structure in the 3D model, 0 for no repetitive structure and 1 for repetitive structure. uni_part_bit = 0 && repeat struc bit = 0 means the 3D model contains only one connected component and will be compressed using its raw representation, i.e. the input representation. pattern_num: This8-bit unsigned integer indicates the number of all patterns if it is less than 255. The minimum value of pattern num is 1. When pattern num = 255, it means that the next data field is pattern_num_2.

pattern_num_2: Thisl 6-bit unsigned integer indicates the number of all patterns if it is not less than255. In this case, the total pattern number is (pattern_num_2 + 255)

sym_instance_num: This 16-bit unsigned integer indicates the number of all symmetric instances.

instance_num: This 16-bit unsigned integer indicates the number of all instances if it is less than 65535. The minimum value of instance num is 1. When instance num = 65535, it means that the next data field is pattern_num_2

instance_num_2: This32-bit unsigned integer indicates the number of all instances if it is not less than 65535. In this case, the total instance number is (instance_num_2 + 65535) insta_trans_elem_bit: This 1-bit unsigned integer indicates whether "grouped instance transformation mode" or "elementary instance transformation mode" is used in this bitstream: 0 for "grouped instance transformation mode" and 1 for "elementary instance transformation mode".

use_scaling_bit: This 1-bit unsigned integer indicates whether instance transformation includes scaling factors: 1 for scaling factors being included in instance transformation and 0 if not. When the scaling factors of most instances equal 1.0, the instance transformation doesn't include scaling factor. That means all instances must have the same size with the corresponding patterns. 3d_model_compr_mode: This 2-bit unsigned integer indicates the 3d model compression method used to compress patterns, unique part and the original 3D model itself if it includes no repetitive structures.

3d_model_header: This data field contains the 3D model header buffer.

QP_translation: This 5-bit unsigned integer indicates the quality parameter of instance translation. In one embodiment, the quantization bit number is used as the quality parameter. The minimum value of QP Translation is 3 and the maximum value is 31.

QP_rotation: This 5 -bit unsigned integer indicates the quality parameter of instance rotation. In one embodiment, the quantization bit number is used as the quality parameter. The minimum value of QP Rotation is 3 and the maximum value is 31.

error_compen_enable_bit: This 1 -bit unsigned integer indicates whether or not there are data fields of compressed coding error compensation data for some instances in the bitstream. 0 means there is no data field of compressed coding error compensation data of instances in the bitstream and 1 means there are data fields of compressed coding error compensation data of some instances in the bitstream.

3d model header class

Syntax

Semantics

ver_num: This 32-bit unsigned integer contains the number of vertices of the entire 3D model. This value can be used to verify the decoded 3D model.

tri_num: This 32-bit unsigned integer contains the number of triangles of the entire 3D model. This value can be used to verify the decoded 3D model.

default_coord_bbox: This 1-bit unsigned integer indicates whether a default bounding box is used for the entire 3D model's geometry: 0 means using another bounding box and 1 means using the default bounding box. The default bounding box is defined as x_mi_n=0.0, y_min=0.0, z_min=0.0, x_max=l .0, y_max=l .0, and z_max=l .0.

coordj box: This data field contains the bounding box of the entire 3D model's geometry. The geometry bounding box is defined by (x_min, y_min, z_min, x_max, y_max, z_max). QP_coord: This 5-bit unsigned integer indicates the quality parameter of the 3D model geometry. The minimum value of QP coord is 3 and the maximum value is 31. If there is at least one repetitive structure, QP coord is used as the number of quantization bits for the geometry of patterns.

normalj inding: This 2-bit unsigned integer indicates the binding of normals to the 3D model. The admissible values are described in the following table.

default_normal_bbox: This 1 -bit unsigned integer should always be Ό', which indicating a default bounding box is used for the normal of the entire 3D model. The default bounding box of normal is defined as nx_min=0.0, ny_min=0.0, nz_min=0.0, nx_max=1.0, ny_max=1.0, and nz_max=1.0.

QP_normal: This 5-bit unsigned integer indicates the quality parameter of the 3D model normal. The minimum value of QP normal is 3 and the maximum value is 31. If there is at least one repetitive structure, QP normal is used as the number of quantization bits for the normal of patterns.

colorj inding: This 2-bit unsigned integer indicates the binding of colors to the 3D model. The following table shows the admissible values.

default_color_bbox: This 1-bit unsigned integer indicates whether a default bounding box is used for the color of the entire 3D model: 0 means using another bounding box and 1 means using the default bounding box. The default bounding box is defined as r_min=0.0, g_min=0.0, b_min=0.0, r_max=1.0, g_max=1.0, and b_max=1.0. colorj box: This data field contains the bounding box of the color of the entire 3D model. The color bounding box is defined by (r_mi„, g_min, b_min, r_max, g_max, b_max).

QP_color: This 5-bit unsigned integer indicates the quality parameter of the color. The minimum value of QP color is 3 and the maximum value is 31. If there is at least one repetitive structure, QP color is used as the number of quantization bits for the color of patterns.

multi_texCoord_num: This 5-bit unsigned integer gives the number of texture coordinates per vertex/corner.

texCoord_binding: This 2-bit unsigned integer indicates the binding of texture coordinates to the 3D model. The following table shows the admissible values.

default_texCoord_bbox: This 1-bit unsigned integer indicates whether a default bounding box is used for the texture coordinates: 0 means using another bounding box and 1 means using the default bounding box. The default bounding box is defined as u_min=0.0, v_min=0.0, Umax=1.0, and v_max=1.0.

texCoord_bbox: This data field contains the bounding box of the texture coordinate of the entire 3D model. The texture coordinate bounding box is defined by (u_min, v_min, u_max, v_max). QP_texCoord: This 5 -bit unsigned integer indicates the quality parameter of texture coordinates. The minimum value of QP texCoord is 3 and the maximum value is 31. If there is at least one repetitive structure, QP texCoord is used as the number of quantization bits for the texture coordinates of patterns.

multi_attribute_num: This 5 -bit unsigned integer gives the number of attributes per vertex/face/corner.

attribute_binding: This 2-bit unsigned integer indicates the binding of attributes to the 3D model. The following table shows the admissible values.

2 bound_per_face

3 bound per comer

default_attribute_bbox: This 1-bit unsigned integer indicates whether a default bounding box is used for the attributes: 0 means using another bounding box and 1 means using the default bounding box. The default bounding box is defined as attribute_min[l ..attribute_dim]=0.0, attribute_max[l ..attribute_dim]=l .0.

attribute_bbox: This data field contains the bounding box of the attribute. The attribute bounding box is defined by (attribute_min[l ..attribute_dim], attribute_max[l ..attribute_dim]). QP_attribute: This 5-bit unsigned integer indicates the quality parameter of the attribute. The minimum value of QP attribute is 3 and the maximum value is 31. If there is at least one repetitive structure, QP attribute is used as the number of quantization bits for the attribute of patterns.

PB3DMC stream data class

Syntax

Semantics

compr_3d_model_data: This data field contains the compressed 3d model, which has only one connected component and is encoded by the compression method indicated by 3 d model compr mode.

compr_uni_part_data: This data field contains the compressed unique part data, which is defined as those components not belonging to any gross repetitive structures and not including any symmetric structures. compr_repeat_struc_data: This data field contains the compressed repetitive structure data.

compr uni part data

Syntax

Semantics

compr_uni_comp_data: This data field contains the compressed geometry, connectivity and properties of all unique components, which is encoded by the compression method indicated by 3d_model_compr_mode. All unique components are translated to the origin before compression.

compr_uni_comp_transl: This data field contains the compressed translation vectors for all unique components. The unique component translation vectors are compressed by first quantization and then entropy coding. This data field uses the same order of unique component with compr uni comp data.

bit_num_uni_comp_transl(): This function computes the number of bits used for quantizing each unique component translation vector based on QP coord.

compr repeat struc data class

Syntax

Semantics

compr_pattern_data: This data field contains the compressed geometry, connectivity and properties of all patterns, which is encoded by the compression method indicated by 3d_model_compr_mode. Here patterns consist of the patterns of gross repetitive structures not including any symmetric structures, the patterns of symmetric structures, the unique parts on those gross-repetitive-structure patterns including symmetric structures, and the unique parts of those unique components which do not belong to any gross repetitive structures but have symmetric structures.

compr_sym_insta_data: This data field contains the compressed information of the symmetric instances.

compr_stitch_data: This data field contains the compressed data for stitching symmetric instances and their adjacent parts on the decoded 3D model.

compr_pattern_transl: This data field contains the compressed translation vectors for those components corresponding to the patterns of gross repetitive structures. The pattern translation vectors are compressed by first quantization and then entropy coding. This data field uses the same order of patterns as compr_pattern_data.

compr_insta_elementary_data: This data field contains the compressed transformation data for all instances using the "elementary instance transformation mode". It is compressed in a manner that is byte aligned.

compr_insta_grouped_data: This data field contains the compressed transformation data for all instances using the "grouped instance transformation mode". It is compressed in a manner that is byte aligned.

bit_num_pattern_transl(): This function computes the number of bits used for quantizing translation vector of each pattern component based on QP coord. compr sym insta data class

Syntax

class compr_sym_insta_data{ | Num. of bits | Descriptor

Semantics

compr_sym_insta_elementary_data: This data field contains the compressed transformation data for all symmetric instances using the "elementary instance transformation mode". It is compressed in a manner that is byte aligned. The detail definition of compr sym insta elementary data is the same with compr insta elementary data.

compr_sym_insta_grouped_data: This data field contains the compressed transformation data for all symmetric instances using the "grouped instance transformation mode". It is compressed in a manner that is byte aligned. The detail definition of compr sym insta grouped data is the same with compr insta grouped data.

compr insta elementary data class

Syntax

Semantics

insta_transl_bbox: contains the bounding box of all translation vectors so that quantization can be used when compressing instance translation info. The bounding box is defined by insta_transl_x_min, insta_transl_y_mi_n, insta_transl_z_min, insta_transl_x_max, insta_transl_y_max, insta_transl_z_max

elem_insta_QP_translation_flag: This 1-bit unsigned integer indicates whether or not the ith instance has its own quality parameter for translation.

elem_insta_QP_rotation_flag: This 1-bit unsigned integer indicates whether or not the ith instance has its own quality parameter for rotation.

elem_insta_QP_translation: This 5 -bit unsigned integer indicates the quality parameter of the translation vector of ith instance. The minimum value of elem insta QP translationis 3 and the maximum value is 31.

elem_insta_QP_rotation: This 5-bit unsigned integer indicates the quality parameter of the rotation angles of ith instance. The minimum value of elem insta QP rotationis 3 and the maximum value is 31.

compr_elem_insta_patternID: This data field contains the compressed pattern ID of i^thinstance.

elem_insta_filp_flag: This 1-bit unsigned integer indicateswhether or not the ithinstance is flipped compared with the corresponding pattern. A flipped instance means the instance triangle normals are in the opposite diection of the correspoonding pattern triangles. 0 means ith instance is not flipped and 1 ith instance is flipped. Figure 10 shows an example of flipped instance with regards to the original pattern.

elem_insta_reflection_flag: This 3 -bit unsigned integer indicates whether the transformation of i^thinstance includes reflection transformation along the coordinate axes. From left to right, the 3 bits correspond to x, y and z axis respectively. 0 means the transformation of i instance doesn't include the corresponding reflection and 1 means the transformation of i^th instance includes the corresponding reflection.

elem_insta_attribute_header: This data field contains the attribute header of i^th instance. compr_elem_insta_transl: This data field contains the compressed translation vector of i^th instance.

compr_elem_insta_rotat_spherical: This data field contains the compressed rotation transformation of i^th instance in spherical mode.

compr_elem_insta_scaling: This data field contains the compressed scaling factor of i^th instance.

elem_insta_error_compensate_flag:This 1-bit unsigned integer indicates whetheror not the next part of the bitstream is the compressed coding error compensation data of i^th instance. 0 means the next part of the bitstream is not the compressed coding error compensation data of i^th instance and 1 means the next part of the bitstream is the compressed coding error compensation data of i^th instance

compr_elem_insta_error_compen_data: This data field contains the compressed coding errorcompensation data of i^thinstance.

compr_elem_insta_attribute_data: This data field contains the compressed attribute data of i^th instance.

bit_num_insta_transl(): This function computes the number of bits used for quantizing instance translation vectors based on QP coord.

bit_num_vertex_coding_error(): This function adaptively computes the number of bits used for quantizing the coding error of each vertex of i^th instance based on QP coord. elem insta attribute header class Syntax

Semantics

elem_insta_share_pattern_attribute_bit: This 1-bit unsigned integer indicates whether or not the instance share all attributes with the corresponding pattern. 0 means the instance doesn't share all attributes with the corresponding pattern and all or parts of its attributes needs to be compressed. 1 means the instance shares all attributes with the corresponding pattern.

elem_insta_normal_compr_mode: This 2-bit unsigned integer indicates the compression mode of normal data of the instance. The following table shows its admissible values.

elem_insta_color_compr_mode: This 2-bit unsigned integer indicates the compression mode of color data of the instance. The following table shows its admissible values.

elem_insta_texCoord_compr_mode: This 2-bit unsigned integer indicates the compression mode of texture coordinates of the instance. The following table shows its admissible values.

elem_insta_attribute_compr_mode: This 2-bit unsigned integer indicates the compression mode of attribute data of the instance. The following table shows its admissible values.

has_available_attribute()function

Syntax

boolhas available attribute(){

if(normal_binding != 'not_found' || color_binding != 'not_found || multi_texCoord_num != 0 ||

multi_attribute_num != 0

return true;

else

return false;

Semantics

This function decides whether or not there is some attribute data needs to be compressed. compr elem insta rotat spherical class

Syntax

Semantics

The rotation of i^th instance in spherical mode is represented by 3 angles, alpha, beta & gamma.

compr_elem_insta_rotat_alpha: This data field contains the compressed alpha of i^th instance's rotation.

compr_elem_insta_rotat_beta: This data field contains the compressed beta of i^th instance's rotation.

compr_elem_insta_rotat_gamma: This data field contains the compressed gamma of i^th instance's rotation.

bit_num_rotat_alpha(): This function adaptive ly computes the number of bits for the alpha value of i^th instance's rotation based on QP coord and the scale of the corresponding pattern. bit_num_rotat_beta(): This function computes the number of bits for the beta value of i^th instance's rotation based on QP coord and the scale of the corresponding pattern.

bit_num_rotat_gamma(): This function computes the number of bits for the gamma value of i^th instance's rotation based on QP coord and the scale of the corresponding pattern.

compr elem insta attribute data class

Syntax

Semantics

compr_elem_insta_normal_data: This data field contains the compressed normal of i instance.

compr_elem_insta_color_data: This data field contains the compressed color of i^th instance. compr_elem_insta_texCoord_data: This data field contains the compressed texture coordinates of i^th instance.

compr_elem_insta_attribute_data: This data field contains the compressed attribute data of i^th instance. compr insta grouped data class

Syntax

Semantics

All the following data fields use the same instance order.

compr_insta_patternID_header: A 16-bit header for the compressed pattern IDs of all instances. This data field is unused when using fixed-length codec or entropy codec which can determine compressed bitstream length automatically for coding patternlD data.

compr_insta_patternID_data: This data field contains the compressed pattern IDs of all instances.

insta_flip_flag_data: This data field contains the flip flags of all instances. It is compressed in a manner that is byte aligned.

insta_reflection_flag_data: This data field containsthe reflection flags of all instances. It is compressed in a manner that is byte aligned.

compr_insta_transl_header: a 16-bit header for the compressed translation vectors of all instances. This data field is unused when using fixed-length codec or entropy codec which can determine compressed bitstream length automatically for coding transl data. compr_insta_transl_data: contain the compressed translation vectors of all instances.

compr_insta_rotat_header: a 16-bit header for the compressed rotation transformation parts of all instances. This data field is unused when using fixed-length codec or entropy codec which can determine compressed bitstream length automatically for coding rotat data. compr_insta_rotat_data: This data field contains the compressed rotation transformation parts of all instances. It is compressed in a manner that is byte aligned.

compr_insta_scaling_header: a 16-bit header for the compressed scaling factors of all instances. This data field is unused when using entropy codec which can determine compressed bitstream length automatically for coding scaling data.

compr_insta_scaling_data: This data field contains the compressed scaling factors of all instances.

compr_insta_attribute_header: This data field contains the compressed elem insta attribute header data of all instances.

compr_insta_attribute_data: This data field contains the compressed attribute data of all instances. compr insta transl data class

Syntax

Semantics

grouped_insta_transl_bbox: contains the center (3 floats) and the length (1 float) of the longest dimension of the translation vector data's bounding box

num_node: al 6-bit unsigned integer indicating the number of octree nodes.

num_dupli_leaf: contain the number of duplicate leaf nodes (octree leaf nodes containing duplicate instance translation vectors).

dupli leaf id: contain the index of the i^th duplicate leaf node in the breadth first traversal sequence of the octree.

dupli_insta_transl_num_flag: a 1-bit unsigned integer whether or not there are at least 3 duplicate instance translation vectors in the corresponding leaf node. 0 means there are only

2 duplicate instance translation vectors in the corresponding leaf node and 1 means there are more than 2 duplicate instance translation vectors in the corresponding leaf node.

num_dupli_insta_transl: a4-bit unsigned integer indicating the number of duplicate instance translation vectors that fall into the i^th duplicate octree leaf node.

num_interval_bound: an8-bit unsigned integer indicating the number of interval boundaries of the entire octree occupancy code sequence.

interval_bound_id: contain index of the i^th interval boundary.

reservedj its: contain some ISO reserved bits for the purpose of byte alignment

occup_pO_symbols : contain occupancy codes of octree nodes that are compressed with universal set of alphabet.

occup_pl_symbols : contain occupancy codes of octree nodes that are compressed with sub set of alphabet. compr insta rotat data class

Syntax

compr insta attribute data class

Syntax

Fig. 11 and Fig. 12 show the high-level block diagram for the PB3DMC encoder and PB3DMC decoder, respectively. During encoding, a 3D model first goes through the repetitive structure discovery process, which outputs the 3D model in terms of patterns, instances and unique components. A pattern encoder is employed to compress the patterns and a unique component encoder is employed for encoding the unique components. For the instances, the instance component information and properties are encoded based on a user- selected mode. If instance information group mode is selected, the instance information and properties are encoded using a grouped instance information encoder and a grouped instance properties encoder, respectively; otherwise, it is encoded using an elementary instance information encoder and an elementary instance properties encoder, respectively. The encoded components are further verified in the repetitive structure verification stage before being sent to the compressed bitstream. During the decoding, the patterns in the compressed bitstream of the 3D model are decoded by a pattern decoder and the unique components are decoded by a unique component decoder. The decoding of the instance information also depends on the user-selected mode. If instance information group mode is selected, the instance information and properties are decoded using a grouped instance information decoder and a grouped instance properties decoder, respectively; otherwise, they are decoded using an elementary instance information decoder and an elementary instance properties decoder. The decoded patterns, instance information and unique components are reconstructed to generate the output decoded 3D model.

It is to be understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. Preferably, the present invention is implemented as a combination of hardware and software. Moreover, the software is preferably implemented as an application program tangibly embodied on a program storage device. The application program may be uploaded to, and executed by, a machine comprising any suitable architecture. Preferably, the machine is implemented on a computer platform having hardware such as one or more central processing units (CPU), a random access memory (RAM), and input/output (I/O) interface(s). The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein may either be part of the microinstruction code or part of the application program (or a combination thereof), which is executed via the operating system. In addition, various other peripheral devices may be connected to the computer platform such as an additional data storage device and a printing device.

Although preferred embodiments of the present invention have been described in detail herein, it is to be understood that this invention is not limited to these embodiments, and that other modifications and variations may be effected by one skilled in the art without departing from the scope of the invention as defined by the appended claims.

Claims

1. A method for extracting a multi-level repetitive structure from a 3D model, comprising: extracting a first-level repetitive structure in said 3D model; and

extracting a second-level repetitive structure from at least one of a) said first-level repetitive structure, and b) a unique part from said 3D model which does not belong to said first-level repetitive structure.

2. The method of claim 1, wherein said first-level repetitive structure is a gross repetitive structure and said second-level repetitive structure is a symmetric structure.

3. The method of claim 1, further comprising generating a first-level pattern for said first-level repetitive structure, wherein each instance component of said first-level repetitive structure is represented by first-level instance component information generated by comparing said each instance component with said first-level pattern.

4. The method of claim 3, further comprising generating a second-level pattern for said second-level repetitive structure, wherein each instance component of said second-level repetitive structure is represented by second-level instance component information generated by comparing said each instance component of said second-level repetitive structure with said second-level pattern, wherein said each instance component of said second-level repetitive structure is one of a) said first-level pattern, and b) said unique part from said 3D model.

5. The method of claim 3, wherein said first-level instance component information comprises an identification to said first-level pattern and a transformation between said instance component and said first-level pattern.

6. The method of claim 5, wherein said second-level instance component information comprises an identification to said second-level pattern and a transformation between said second-level instance component and said second-level pattern.

7. The method of claim 5, wherein said transformation comprises a transformation matrix.

8. The method of claim 7, wherein said transformation matrix comprises a rotation part, a translation part and a reflection part.

9. A method for encoding a 3D model, comprising:

encoding a repetitive structure from said 3D model, wherein said repetitive structure comprises a first-level repetitive structure and a second-level repetitive structure.

10. The method of claim 9, further comprising:

encoding a part of said 3D model which does not belong to said repetitive structure.

11. The method of claim 9, wherein said second-level repetitive structure is extracted from at least one of a) said first-level repetitive structure, and b) a unique part from said 3D model which does not belong to said first-level repetitive structure.

12. The method of claim 9, wherein said first-level repetitive structure is a gross repetitive structure and said second-level repetitive structure is a symmetric structure.

13. The method of claim 9, wherein said encoding step comprises encoding a first-level pattern for said first-level repetitive structure, wherein each instance component of said first- level repetitive structure is represented by first-level instance component information generated by comparing said each instance component with said first-level pattern.

14. The method of claim 13, further comprising generating a second-level pattern for said second-level repetitive structure, wherein each instance component of said second-level repetitive structure is represented by second-level instance component information generated by comparing said each instance component of said second-level repetitive structure with said second-level pattern, and wherein said each instance component of said second-level repetitive structure is one of a) said first-level pattern, and b) said unique part from said 3D model.

15. The method of claim 14, further comprising generating stitching information for said instance components of said second-level repetitive structure.

16. The method of claim 14, wherein said first-level instance component information comprises an identification to said first-level pattern and a transformation between said instance component and said first-level pattern.

17. The method of claim 14, wherein said second-level instance component information comprises an identification to said second-level pattern and a transformation between said second-level instance component and said second-level pattern.

18. The method of claim 16, wherein said transformation comprises a transformation matrix.

19. The method of claim 18, wherein said transformation matrix comprises a rotation part, a translation part and a reflection part.

20. The method of claim 19, wherein said first-level pattern is aligned with coordinate axes.

21. A method for decoding an encoded 3D model, comprising:

decoding a repetitive structure from said encoded 3D model, wherein said repetitive structure comprises a first-level repetitive structure and a second-level repetitive structure.

22. The method of claim 21, further comprising:

decoding a part of said 3D model which does not belong to said repetitive structure.

23. The method of claim 21, wherein said first-level repetitive structure is a gross repetitive structure and said second-level repetitive structure is a symmetric structure.

24. The method of claim 23, wherein decoding said repetitive structure comprising

decoding pattern type of data for said second-level repetitive structure from said encoded 3D model;

decoding instances of said second-level repetitive structure from said encoded 3D model;

restoring first-level repetitive structure patterns using said decoded pattern type of data and said decoded instances of said second-level repetitive structure; and

restoring instance components of said first-level repetitive structure using said restored first-level repetitive structure patterns.

25. The method of claim 24, wherein decoding said repetitive structure further comprises: decoding stitching information from said encoded 3D model.

26. An apparatus for extracting a multi-level repetitive structure from a 3D model, comprising:

a first-level extractor for extracting a first-level repetitive structure in said 3D model; and

a second-level extractor for extracting a second-level repetitive structure from at least one of a) said first-level repetitive structure, and b) a unique part from said 3D model which does not belong to said first-level repetitive structure.

27. An apparatus for encoding a 3D model, comprising:

an element encoder for encoding a repetitive structure from said 3D model, wherein said repetitive structure comprises a first-level repetitive structure and a second-level repetitive structure.

28. An apparatus for decoding an encoded 3D model, comprising:

an element decoder for decoding a repetitive structure from said encoded 3D model, wherein said repetitive structure comprises a first-level repetitive structure and a second-level repetitive structure.