Patent Publication Number: US-10311635-B2

Title: Method and apparatus for detecting repetitive structures in 3D mesh models

Description:
This application claims the benefit, under 35 U.S.C. § 365 of International Application PCT/CN2010/000984, filed Jun. 30, 2010, which was published in accordance with PCT Article 21(2) on Jan. 5, 2012 in English. 
     FIELD OF THE INVENTION 
     This invention relates to a method for detecting repetitive structures in 3D mesh models. 
     BACKGROUND 
     Repetitive structures are ubiquitous not only in nature, e.g. in biology and physics, but also in other fields, such as engineering and art. Repetitive structures are very common in man-made objects, and fundamental e.g. in almost all design styles in architecture. Therefore, all common types of 3D mesh models generally comprise repetitive structures. Due to increasing complexity of such models, it is desirable to minimize the amount of data required for coding them. It has been found that symmetry, including repetitive structures, is a kind of redundancy that may be used to reduce complexity: Repetitive structures need to be encoded only once, and can be called or “instantiated” several times. In order to benefit from this redundancy, it is necessary to detect repetitive structures in existing 3D mesh models. Traditional methods use a technique for segmenting periodic structures that relies on a user to manually identify repetitive elements. Obviously such user assistance is unwanted. 
     Each instance of a repetitive structure can be individually modified by transformations, such as rotations, translations, reflections and uniform scaling. A known method 1  for (partial) symmetry detection, even at different scales, uses an approach that is called “transformation voting”: it comprises constructing a transformation space, clustering possible transformations and deciding symmetry by transformation clusters. E.g. Mitra 1  calculates in a first step local shape descriptors, which are then used to pair up points that could be mapped to each other under a candidate symmetry action. A set of possible candidate transformations is called transformation space. Pairs with similar transformations form clusters in the transformation space, which provide evidence for the corresponding symmetry relation. In a second step, point pairs whose transformation falls into a cluster are checked for spatial consistency. A stochastic clustering provides surface correspondences, so that only a small set of candidates samples needs to be considered when detecting and extracting symmetric surface patches. Curvature descriptors are used to pair sample points; candidate point pairs are discarded if their curvature descriptors differ too much. Similarly, it is known 2  to group sample points into “similarity sets” according to curvature descriptors. Curvature is generally the amount by which a geometric object deviates from being flat. 
     One reason for the usage of clustering is that the amount of data to be compared is very high. The number of sampling points, and thus the data amount, highly depends on the sampling step size: smaller sampling steps result in more data, which makes the clustering steps less efficient. However, larger sampling steps result in the omission of small-scale structures. 
     SUMMARY OF THE INVENTION 
     The present invention provides an improvement to known 3D compression methods, and in particular to transformation voting methods. The latter have usually steps of finding candidates for symmetries by transformation clustering and then comparing the candidates. They may be employed in 3D compression or other applications. 
     The improvement provided by the present invention concerns at least the sampling step size. In particular, the present invention uses an iterative uniform sampling method with a decreasing sampling step size. A given 3D mesh model is uniformly sampled with an initial sampling step size, which is relatively large. Then, the sampling points are clustered according to their curvature, and then transformations are determined between sampling points that belong to the same cluster. These are so-called candidate transformations. Thus, the candidate transformations need to be determined only for those sampling point pairs where both points have similar curvature. Such clustering step not only improves the algorithm efficiency, but also increases the algorithm accuracy. The transformation space, which is constructed by all the transformations calculated before, contains less noise elements than it would if the sampling step size was smaller. Thus, a subsequent clustering step will be more likely to discover all the repetitive structures. If the model comprises repetitive structures, the usual result of such clustering is that one or more distinct clusters will emerge. In the next step, the (most relevant) clusters are selected, and the corresponding transformations and sampling point pairs are assumed to indicate a repetitive structure. The most relevant clusters are those which are most significant and apparent. Other transformations that don&#39;t belong to a cluster are discarded. 
     This procedure is iteratively executed with a decreasing sampling step. Each iteration skips repetitions, and only processes remaining parts of the model and representatives of the representative structures that were detected in the previous iteration. Thus, also multi-scale repetitive structures on the 3D model can be discovered. The iterative process stops when the number of repetitive structures is stable, or when a pre-defined minimum sampling step size is reached. It is also possible to define a time-out, measure the runtime of the process, and terminate the process when the runtime exceeds the time-out. 
     The additional clustering and iteration steps reduce the amount of possible transformations to be investigated, and thus the required processing capacity. 
     According to one embodiment of the invention, a method for detecting repetitive structures in 3D mesh models comprises steps of sampling the 3D mesh model using a current (uniform) sampling step size, 
     detecting within the 3D mesh model one or more repetitive structures and remaining portions of the model, and determining a representative for each of the one or more repetitive structures, 
     as long as the detecting step yields one or more repetitive structures using the current sampling step size,
         reducing the current sampling step size to obtain a reduced sampling step size, and   repeating the steps of sampling and detecting for each detected representative of a detected repetitive structure and for the remaining portions of the model, wherein the reduced sampling step size is used as the current sampling step size. The detected multi-scale repetitive structure is recorded in a tree structure. If the detecting step yields no more repetitive structures, or if a pre-defined minimum sampling step size or time-out is reached, the method for detecting repetitive structures is terminated.       

     In one embodiment, each detecting step comprises steps of calculating a curvature descriptor for each sampling point, based on the respective current sampling step size, clustering the sampling points according to their curvature descriptor, wherein one or more sampling point clusters are obtained, calculating transformations between pairs of sampling points that belong to a common sampling point cluster, clustering the calculated transformations in a transformation space, wherein one or more transformation clusters are obtained, and determining, according to each of the one or more transformation clusters in the transformation space, a repetitive structure and its representative, wherein pairs of sampling points whose transformation belongs to a common cluster in the transformation space are defined as two instances of a repetitive structure. 
     According to one embodiment of the invention, a device for detecting repetitive structures in 3D mesh models comprises sampling means for sampling the 3D mesh model using a current (uniform) sampling step size, 
     detection means for detecting within the 3D mesh model one or more repetitive structures and remaining portions of the model, determining means for determining a representative for each of the one or more repetitive structures, reducing means for reducing the current sampling step size to obtain a reduced sampling step size, and control means for controlling, as long as the detection means detects one or more repetitive structures using the current sampling step size, the repeated operation of the reducing means, the sampling means and the detecting means for each detected representative of a detected repetitive structure and for the remaining portions of the model, wherein the reduced sampling step size is used as the current sampling step size. 
     If the detecting means does not detect any more repetitive structures, or if a pre-defined minimum sampling step size or time-out is reached, the device for detecting repetitive structures is stopped. 
     Advantageous embodiments of the invention are disclosed in the dependent claims, the following description and the figures. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Exemplary embodiments of the invention are described with reference to the accompanying drawings, which show in 
         FIG. 1  a block diagram of the method for discovering repetitive structures in 3D models; 
         FIG. 2  the principle of symmetry detection; and 
         FIG. 3  a tree structure for recording the detected multi-scale repetitive structure; 
         FIG. 4  a block diagram of a device for discovering repetitive structures; 
         FIG. 5  a block diagram of a detecting means for detecting repetitive structures; 
         FIG. 6  an exemplary 3D mesh model and its corresponding data set; and 
         FIG. 7  a transformation between points of a point pair. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 1  shows a block diagram of a method for discovering repetitive structures in 3D models. For an input model, sampling points are calculated  100 , wherein a relatively large initial sampling step size is used. In the next step  200 , a curvature descriptor is calculated for each sampling point. The sampling points are clustered  300  according to their curvature descriptors, i.e. sampling points with similar curvature descriptors are put into the same cluster. Among the sampling points within a cluster, repetitive structures are detected (i.e. calculated)  400  and verified  500 . From the detected repetitive structures, a tree is constructed where each repetitive structure is represented by a sub-branch. Finally, it is checked  700  whether the number of repetitions has increased in the previous steps. For input models that contain repetitive structures (like most models), this will initially always be the case. In this case, the sampling step size is decreased, and sampling points are re-calculated for sub-structures of a cluster. 
     An efficient method for detecting repetitive structures on 3D models is disclosed, which can automatically discover repetitive structures of any small scale and multi-scale repetitive structures. The key ideas include clustering all sampling points based on their curvature and iteratively processing the model with a decreasing sampling step. A block diagram of this method is shown in  FIG. 1 . In this algorithm, the input data set in can be a point set or a mesh-based model. 
     For recording the multi-scale repetitive structures detected by the method, a tree structure is used. Each node of the tree records one repetitive structure. In the beginning, the tree only has the root corresponding to the input model. The sampling step H is initially a relatively large number. 
     Sampling block  100  uniformly samples the surface. In this diagram, the current sampling step is denoted as H. 
     Curvature descriptor computing block  200  computes the curvature descriptor of each sampling point. For a sampling point p i , we calculate its mean curvature H(p i ), Gaussian curvature K(p i ), principal curvatures K i1 , K i2  and principal direction C i1 , C i2 . Any method can be used to calculate the curvature descriptor, e.g. the method described in section 3-5 of [Meyer et al. 2002] 3 . The curvature descriptor of p i  is
 
 cd ( p   i )= H ( p   i ) 2   /K ( p   i )  (1)
 
     K i1 , K i2 , C i1  and C i2  are useful in the next calculations described below. More details about the curvature descriptor are given below. 
     Block  300  clusters sampling points according to their curvature descriptors. We use mean-shift algorithm (as commonly known, and described e.g. in [Comaniciu et al.] 4 ) as our cluster operator. The density function is defined as:
 
ρ( H ( v ) 2   /K ( v ))=Σ i ( H ( v ) 2   /K ( v )− H ( v   i ) 2   /K ( v   i )) /h   (1a)
 
where h is as suggested by [Comaniciu et al.] 4 .
 
     Block  300  improves the efficiency and robustness of the subsequent analysis steps by pruning the unnecessary sample pairs, since the same repetitive structure consists of points with similar curvature. 
     Block  400  calculates the repetitive structures of a current level. It deals with every sampling point cluster separately. Let Φ k  denote the cluster currently being processed. 
     Block  410  calculates the transformation space Γ k  of Φ k , e.g. by the method described in [Mitra et al. 2006] 1 . A transform T i,j ∈Γ k  transforms point p i  ∈Φ k , to another point p j  ∈Φ k . Block  200  has already calculated the principal curvatures K i1 , K i2  and principal direction C i1 , C i2  of one sampling point p i . 
     C i1  and C i2  define the local frame (C i1 , C i2 , n i ) of p i  where n i =C i1 ×C i2 . There are two sequential rotation operations, R 1ij  and R 2ij . R 1ij  first makes n i  parallel with n j . Then R 2ij  makes C i1  parallel with C j1 . The scaling factor s i,j  is calculated by
 
 s   i,j =( K   i1   /K   j1   +K   i2   /K   j2 )/2  (2)
 
     The translation t i,j  is calculated by
 
 t   i,j   =p   j   −s   i,j   R   i,j   p   i   (3)
 
     Thus, we obtain the 7-dimensional
 
 T   i,j =( s   i,j   ,Rx   i,j   ,Ry   i,j   ,Rz   i,j   ,t   xi,j   ,t   yi,j   ,t   zi,j )  (4)
 
where Rx i,j , Ry i,j , Rz i,j  are the Euler angles, standing for a rotation R 2 , and t i,j =[t xi,j , t yi,j , t zi,j ] T  stands for a translation.
 
     Block  420  clusters all the transformations in Γ k . Like the existing algorithms, we choose mean-shift as clustering operator of this step. The transformations in the same cluster usually represent the same repetitive structure. 
     Block  430  calculates surface patches corresponding to repetitive structures. We deal with clusters calculated in Block  420  in the decreasing order of their size. Let C k  denote the transformation cluster being processed. Like [Mitra et al. 2006] 1 , we calculate surface patches by an incremental patch growing process, which starts from a random point T i,j  in C k . T i,j  corresponds to a pair of sampling points (p i , p j ). Suppose p i1  is one surface vertex of the one-ring neighbors of p i  and p′ i1 =T ij S ij R 2ij R 1ij p i1 . Dis_Sur is the distance between p′ i1  and the surface around p j  and Dis_Pt is the distance between p′ i1  and p j :
 
Dis= u   1 *Dis_Sur+ u   2 *Dis_Pt,  u   1   +u   2 =1  (5)
 
where u 1  and u 2  are some constants (we set u 1 =0.8, u 2 =0.2). If Dis is below a threshold, p i1  is added to the surface patch which starts from p i . The surface patch is kept growing from its current boundary until no more points can be added in. After the surface patch starting from p i  is finished, we calculate the surface patch starting from p j . Such two surface patches will be added to two patch sets, {Pat i } and {Pat j }, respectively. During the patch growing process, we mark all the visited sampling points and the transformations involving them. New patches will be built if there is any un-marked transformation in C k . At last, for each cluster, two patch sets are calculated and are instances of the same repetitive structures. One patch set is chosen as the representative and the other one is regarded as the instance of the corresponding repetitive structures.
 
     Block  500  uses an Iterated Closest Points (ICP) algorithm, e.g. as known from [RUSINKIEWICZ et al 2001] 5 , to verify the repetitive structures discovered in Block  400 . At first, we check whether the instance structures can exactly match their corresponding representatives by ICP. Those repetitive structures cannot pass this test are discarded. Then, we try to match each pair of the left representatives by ICP. For those two representatives exactly matched, the corresponding repetitive structures are combined. 
     Block  600  updates the tree structure which records the detected multi-scale repetitive structure, as shown in  FIG. 3 . The repetitive structures just detected are added as leafs of the corresponding node. A special leaf node is added, which corresponds to the part of surface that does not contain any repetitive structure. There may be smaller scale repetitive structures, which will be detected in the next iteration of the algorithm. 
     In the next iteration, the sampling step will be the half of the original size. The algorithm deals with all the leaf nodes separately. In one embodiment, the algorithm is stopped when the sampling step is smaller than a threshold. 
     In one embodiment, the sampling step threshold for stopping the algorithm depends on the input model, and in particular on the diameter of the bounding-box of the input model. That is, a bounding-box (e.g. in a Cartesian coordinate system along the x,y,z-axes) is constructed around the complete model, the length of a diagonal from (x min , y min , z min ) to (x max , y max , z max ) is calculated, and then the sampling step size threshold is set to be a fraction thereof, e.g. 0.5% (diagonal_length/200) or similar. 
       FIG. 2  shows an example of a 3D model. While in a) the sampling points referring to any particular step size are shown, b) shows possible transformations that are constructed in the prior art: For each sampling point, a transformation to each other sampling point is calculated. However, for the present invention such transformations are calculated only for point pairs that have similar curvature, such as  201 , 210 , 220 . After clustering, those transformations that relate to a real symmetry can be identified, since they are so similar that they end up in a common transformation cluster. In  FIG. 2 c   ), the determined symmetry of this exemplary model is shown: a reflection on a symmetry axis  230 . 
     It is noted here that the prior art ([Mitra 2006] 1 ) only deals with those sampling point pairs whose two sampling points have similar signatures. The method is as follows: Suppose p i  is one sampling point and P is the sampling points set. k i1 /k i2  is the signature of p i  where k i1  and k i2  are the principal curvatures of p i . All sample points are mapped to a signature space Ω. Only point pairs that are close in Ω are considered as suitable candidates for a later analyzing process. Prior art first selects a random subset P*⊂P. The candidate point pairs for later analyzing are (p*, p), where p*∈P* and p∈P. For a given sample point p i ∈P*, prior art determines all suitable partners in P by performing a range query in Ω. Prior art uses standard spatial proximity data structures kd-tree to find all suitable partners of p i . By this method, prior art can avoid an exhaustive computation of a quadratic number of point pairs. In the present invention, we achieve the same purpose by clustering all the sampling points according to their curvature descriptor. Compared with the method of randomly choosing a subset of sampling points as used by prior art, the invention is more precise and can guarantee detecting all repetitive structures in any scales, while prior art cannot. 
     Since symmetry is an important concept for the invention, it is clarified here that symmetry means invariance under a set of transformations, such as rotations, translations, reflections and uniform scaling. 
     Further, curvature and the curvature descriptor is a well-defined mathematical concept, and its construction is known in the prior art (e.g. Pauly 2 ). Mean curvature H(v i ) of v i  is independent of the employed coordinate system. Gaussian curvature K(v i ) is dependent on the 3D coordinate system, and defined by 
     
       
         
           
             
               
                 
                   
                     K 
                     ⁡ 
                     
                       ( 
                       
                         v 
                         i 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         A 
                         ⁡ 
                         
                           ( 
                           
                             v 
                             i 
                           
                           ) 
                         
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           2 
                           ⁢ 
                           π 
                         
                         - 
                         
                           
                             ∑ 
                             
                               
                                 v 
                                 j 
                               
                               ∈ 
                               
                                 
                                   N 
                                   1 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     v 
                                     i 
                                   
                                   ) 
                                 
                               
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             θ 
                             j 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     k i1  and k i2  are two principle curvatures of v i . According to Differential Geometry, Gaussian curvature K(v i ) and mean curvature H(v i ) can be expressed by the two principle curvatures as:
 
 K ( v   i )= k   i1   *k   i2   (7)
 
 H ( v   i )= k   i1   +k   i2   (8)
 
     Therefore we can define the principal curvatures as: 
     
       
         
           
             
               
                 
                   
                     k 
                     
                       i 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       1 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           H 
                           ⁡ 
                           
                             ( 
                             
                               v 
                               i 
                             
                             ) 
                           
                         
                         + 
                         
                           
                             
                               
                                 H 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     v 
                                     i 
                                   
                                   ) 
                                 
                               
                               2 
                             
                             - 
                             
                               4 
                               * 
                               
                                 K 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     v 
                                     i 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                     k 
                     
                       i 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       2 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           H 
                           ⁡ 
                           
                             ( 
                             
                               v 
                               i 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             
                               
                                 H 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     v 
                                     i 
                                   
                                   ) 
                                 
                               
                               2 
                             
                             - 
                             
                               4 
                               * 
                               
                                 K 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     v 
                                     i 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     From eq. (9) and (10), we can get the curvature descriptor as 
     
       
         
           
             
               
                 
                   
                     
                       
                         H 
                         ⁡ 
                         
                           ( 
                           
                             v 
                             i 
                           
                           ) 
                         
                       
                       2 
                     
                     / 
                     
                       K 
                       ⁡ 
                       
                         ( 
                         
                           v 
                           i 
                         
                         ) 
                       
                     
                   
                   = 
                   
                     
                       
                         
                           ( 
                           
                             
                               k 
                               
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 1 
                               
                             
                             + 
                             
                               k 
                               
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                               
                             
                           
                           ) 
                         
                         2 
                       
                       / 
                       
                         ( 
                         
                           
                             k 
                             
                               i 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               1 
                             
                           
                           * 
                           
                             k 
                             
                               i 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               2 
                             
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           k 
                           
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                         
                         
                           k 
                           
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             2 
                           
                         
                       
                       + 
                       
                         
                           k 
                           
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             2 
                           
                         
                         
                           k 
                           
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             1 
                           
                         
                       
                       + 
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     Thus, H(v i ) 2 /K(v i ) is invariant under scaling, rotation and translation transformation. Thus we use H(v i ) 2 /K(v i ) as the shape descriptor, and cluster sample points according to H(v i ) 2 /K(v i ). The same curvature descriptor has been used by in [Pauly et al. 2008] 2 , but for a different purpose. 
       FIG. 4  shows a device for detecting repetitive structures in 3D mesh models according to one embodiment of the invention. It comprises sampling means SM, i.e. a sampling unit, for sampling the 3D mesh model provided at the input in. It uses a current uniform sampling step size sss that it receives from another unit, as described below. 
     The sampling unit SM provides sampled data to a detection means DM 1 , which detects within the sampled 3D mesh model one or more repetitive structures and identifies remaining portions of the model that are no repetitive structures. Each repetitive structure rs is provided to a determining means DM 2 , which determines a representative rep for each of the one or more repetitive structures. The representative (i.e. its data) is provided back to the detecting means DM 1 , which uses it for identifying (further) repetitions thereof. 
     Sampling and control data of repetitive structures and the above-mentioned remaining data portions rsrd are provided as output, e.g. to an encoder E. These data rsrd comprise sampling data of a representative for each repetitive structure and of each remaining portion, having the sampling step size in which they were sampled. The data rsrd also comprise data defining the repetitions of the repetitive structures. An example is given below. 
     Further, the device has control means CM for controlling, as long as the detection means detects one or more repetitive structures using the current sampling step size, a repeated operation of the device. That is, if the detecting means DM 1  signals to the control means CM that it has finished its operation on a model and that it has identified at least one repetitive structure, then the control means CM controls a sampling step size reducing means SRM to reduce the sampling step size. Further, the control means CM controls the sampling means SM, the detecting means DM 1  and the determining means DM 2  to repeat their operation for each detected representative of a detected repetitive structure and for the remaining portions of the model, using the reduced sampling step size. 
     The sampling step size is initially a pre-defined value isss, and is successively reduced by a given factor f. In one embodiment, this factor is a constant integer. In one embodiment, this factor is “2”. That is, while in a first iteration the sampling step size is the pre-defined value isss, it will be isss/2 in a second iteration, isss/4 in a third iteration etc. Note that second and further iterations are only performed for representatives of a repetitive structure and for remainders. 
     If the detecting means DM 1  does not detect any more repetitive structures, or if a pre-defined minimum sampling step size smin or a time-out is reached, the device for detecting repetitive structures is stopped. For this purpose, the device comprises, in one embodiment, a time-out measurement unit TMU, and in one embodiment a sampling step size comparison unit CMP. 
     In one embodiment, the detected multi-scale repetitive structure is recorded as a tree structure in a memory device. 
       FIG. 5  shows details of one embodiment of the detecting means DM 1 . It comprises curvature calculating means CUCM for calculating a curvature descriptor for each sampling point, based on the respective current sampling step size. Curvature descriptors are described above. A sampling point clustering means SPCM clusters the sampling points according to their curvature descriptor, wherein one or more sampling point clusters are provided. Transformation calculating means TCAM is used for calculating transformations between pairs of sampling points that belong to a common sampling point cluster, and transformation clustering means TCLM is used for clustering the calculated transformations. This is done in a transformation space, and results in one or more transformation clusters tc being provided. Finally, the detecting means DM 1 , comprises repetitive structure determining means RSDM for determining, according to each of the one or more transformation clusters in the transformation space, a repetitive structure rs, wherein pairs of sampling points whose transformation belongs to a common cluster in the transformation space are defined as two instances of a repetitive structure. The repetitive structure rs is provided to the above-mentioned determining means DM 2 , which determines (i.e. identifies) a representative rep for the repetitive structure. This may happen in any arbitrary manner, e.g. the first determined instance of a repetitive structure is selected as representative, and all further instances are selected as repetitions. The repetitive structure determining means RSDM outputs first data rsrd defining the whole model, as described below, and second data rsd indicating whether or not at least one repetitive structure has been found. The latter data rsd is provided to the control block CM, which may decide to initiate another iteration. 
       FIG. 6  shows an example of the data defining the repetitive structures and the remaining data portions of an exemplary 3D mesh model. It is pointed out here that this is a simplified example for explaining a basic principle of one embodiment. 
       FIG. 6  shows a 3D mesh model comprising one repetitive structure that is used several times and a remainder that is no repetitive structure. In this example, the repetitive structure is a triangle and the remainder rm is a circle. As also shown in  FIG. 6 , the above-mentioned data rsrd comprise sampling data rrd 1  of a representative rr of the repetitive structure, and repetition data r 1 , r 2 , . . . indicating individual repetitions thereof and their respective transformations tr 1 (rrd 1 ), tr 2 (rrd 1 ), . . . for defining the position, scale etc. of each repetition. Further, the data rsrd comprise sampling data rmd 1  defining the remainder. While in this example the remainder is only one single structure, it may also be two or more individual sub-structures. 
       FIG. 7  shows a transformation between points of a point pair. (p i ,p j ) is a point pair of C k , and T i,j  is the transformation between them. p′ i  is a one-ring neighbour of p i . Transforming p′ i  by T i,j  can obtain p′ j . That is: if the p′ i  after transformation is close to the actual p′ j  (e.g. within a threshold circle), the transform T i,j  is a good candidate. If the transform T i,j  is a good candidate for several points, it is used for determining a symmetry. 
     Discovering repetitive structures in 3D models is a challenging task, but the result is very useful in many aspects. The described method and device can e.g. be used for 3D model compression, 3D model repairing, geometry synthesis etc. 
     A compact representation of a 3D model can be generated, based on the result of detecting repetitive structures. Such representation will include:
         some bits to indicate the number of repetitive structures;   for each representatives of repetitive structures, some bits to show the compressed geometry pattern;   some bits to indicate the number of instances of repetitive structures; and   for each instance, some bits to show its transformation and some bits to show the representative ID.       

     The invention has at least the following advantages over known algorithms for repetitive structure detection. 
     First, for all types of models, repetitive structures can be detected more quickly, as first all sampling points are clustered according to their curvature and then each cluster of sampling points is handled separately. 
     Second, the invention is suitable for detecting all repetitive structures in a model, while known methods are not. E.g. when processing models that contain small scale structures, known methods need a large number of sampling points in order to detect all repetitive structures, and e.g. the clustering would fail when the number of sampling points becomes too high. 
     Third, for models with multi-scale repetitive structures, the invention can detect all levels of repetitive structures while the current methods cannot, as we iteratively detect the repetitive structures using a decreasing sampling step. 
     While there has been shown, described, and pointed out fundamental novel features of the present invention as applied to preferred embodiments thereof, it will be understood that various omissions and substitutions and changes in the apparatus and method described, in the form and details of the devices disclosed, and in their operation, may be made by those skilled in the art without departing from the spirit of the present invention. It is expressly intended that all combinations of those elements that perform substantially the same function in substantially the same way to achieve the same results are within the scope of the invention. Substitutions of elements from one described embodiment to another are also fully intended and contemplated. 
     It will be understood that the present invention has been described purely by way of example, and modifications of detail can be made without departing from the scope of the invention. Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features may, where appropriate be implemented in hardware, software, or a combination of the two. Reference numerals appearing in the claims are by way of illustration only and shall have no limiting effect on the scope of the claims. 
     NOTES 
     
         
           1  “Partial and Approximate Symmetry Detection for 3D Geometry”, 2006 by N. Mitra, L. Guibas, M. Pauly, ACM Trans. Gr. 25, 3, 560.568 
           2  “Discovering Structural Regularity in 3D Geometry”, M. Pauly, N. Mitra, J. Wallner, H. Pottmann, L. Guibas, 2008, ACM Trans. Gr. 27, 3 
           3  “Discrete differential geometry operators for triangulated 2-manifolds”, Meyer M, Desbrun M, Schröder P, Barr A, in: Visualization and Mathematics, Berlin, 2002, 52-58 
           4  “Mean shift: A robust approach toward feature space analysis”, Comaniciu D., Meer P.; 2002 IEEE Trans. PAMI 24, 5, 603-619 
           5  “Efficient variants of the ICP algorithm”, RUSINKIEWICZ, S. and LEVOY, M., 2001, in 3 DIM,  145-152