Abstract:
The present invention comprises a method for global parameterization and quadrangulation on point cloud. The method comprises: (a) computing and smoothing principal direction field over the point cloud; (b) performing a global parameterization of the point cloud; (c) constructing a quad mesh from the resultant parameterization. The present method is fully automatic, and can be used to all point models with any genus values. This approach can be used to many applications, such as texture mapping, surface fitting and shape analysis.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention generally relates to point cloud data obtained by laser scan device in the area of computer graphics and computer vision, especially relates to methods of global parameterization and quad meshing on point cloud. 
       BACKGROUND OF THE INVENTION 
       [0002]    Point cloud has been widely used in CAD and computer graphics communities due to the development of fast and accurate laser scan devices. Usually, there is no topological information in the raw scan points, and an amount of research work focus on meshing the point cloud while exhibiting the original surface well. Although most of the previous work produce high quality triangle meshes, there is little consideration about how to control the shape and orientation of triangles. A quad dominant mesh is preferred rather than a triangle mesh in many applications due to their tensor-product nature, such as in texturing, simulation with finite elements and B-spline fitting. And the quad mesh following principle directions is particularly useful in modeling as they capture the symmetries of natural geometry. 
         [0003]    Global parameterization is a useful tool to design quadrangulation. Ray et al. propose periodic global parameterization guided by principle directions to parameterize the input model (Ray, N., Li, W. C., Levy, B., Sheffer, A., Alliez, P. 2006; Periodic global parameterization;  ACM Trans. Graph.  25, 4, 1460-1485). Thus a quadrilateral mesh can be got by tracking the iso-lines in the parameterize domain. This method can generate a high quality quad mesh without any user&#39;s interaction. However, this method is limited to a triangle mesh; for a point cloud without connection information, it is difficult to use the method in the art directly to processing point cloud data. 
       SUMMARY OF THE INVENTION 
       [0004]    The subject of the invention is to provide a method of global parameterization and quad meshing on a point cloud, comprising: 
         [0005]    1) Calculating and smoothing principal direction field; 
         [0006]    2) Performing Global parameterization of point cloud; 
         [0007]    3) Constructing a Quad mesh from the resultant parameterization. 
         [0008]    The present invention provides a robust and automatic global parameterization for unorganized point cloud data obtained from laser scan devices, and then extracting a feature-aligned quad mesh from the resultant parameterization. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]      FIG. 1  is a schematic diagram of the whole algorithm. 
           [0010]      FIG. 2  is a flow chart of the calculation of principal directions. 
           [0011]      FIG. 3  is a flow chart of the global parameterization. 
           [0012]      FIG. 4  is a flow chart of the quadrangulation. 
           [0013]      FIG. 5  illustrates the processing of the iso-segments. 
           [0014]      FIG. 6  is an example of quadrangulation on point data rock-arm. 
           [0015]      FIG. 7  is an example of quadrangulation on noisy point data chair. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0016]    Embodiments of the invention are explained in greater detail by way of the drawings. However the description itself is not intended to limit the scope of the invention. 
         [0017]    As illustrated in  FIG. 1 , the present method comprises three steps: the calculation of principal direction; performing global parameterization of point cloud; constructing a quad mesh from the resultant parameterization. Detailed description of each step is as follows. 
         [0018]    As illustrated in  FIG. 2 , the calculation of principal direction requires the normal at each point since there is only coordinate information in the 3D point cloud data. It is necessary to compute the normal vector for each point before calculating the principal direction and performing local Delaunay triangulation. First, a kd tree is constructed. In computing geometry, the kd tree has proven to be one of most efficient data structure for nearest neighbor query. Based on the point positions in 3D space, the kd tree divides the 3D space into two parts iteratively to achieve optimized data structure. The time complexity of k nearest neighbor query in a kd tree is O (log2n), where n is the number of points in the point cloud. 
         [0019]    For estimating the normal of a point, 15 or 30 neighboring points are selected; if these points are almost in the same plane, the tangent plane at this point can be obtained by fitting a weighted sum of the distances of the neighboring points to the fitting plane. The weight for each neighboring point is defined as the reciprocal of the Euclidean distance to this point. A plane is obtained by least square fitting and then the normal vector of this plane is defined as the normal at this point. 
         [0020]    A smooth and accurate principal direction field is necessary since the global parameterization is constrained by the principal direction field. The construction of a principal direction field comprises two steps as in the last two steps of  FIG. 2 : estimation of curvature tensor and a global smoothing. 
         [0021]    To calculate the curvature tensor, local coordinates are first constructed for each point. Let {right arrow over (N)} denote the normal vector of point p, then p is the original point of the local coordinates. Let {right arrow over (u)}, {right arrow over (v)}, {right arrow over (w)} represent the three directions of local coordinates, {right arrow over (N)} i  is the normal of p&#39;s neighboring point p i  , then the curvature tensor at p satisfy the following constraints: 
         [0000]    
       
         
           
             
               
                 [ 
                 
                   
                     
                       
                         
                           
                             ∇ 
                             
                               u 
                               → 
                             
                           
                            
                           
                             N 
                             → 
                           
                         
                         · 
                         
                           u 
                           → 
                         
                       
                     
                     
                       
                         
                           
                             ∇ 
                             
                               v 
                               → 
                             
                           
                            
                           
                             N 
                             → 
                           
                         
                         · 
                         
                           u 
                           → 
                         
                       
                     
                     
                       
                         
                           N 
                           → 
                         
                         · 
                         
                           u 
                           → 
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             ∇ 
                             
                               u 
                               → 
                             
                           
                            
                           
                             N 
                             → 
                           
                         
                         · 
                         
                           v 
                           → 
                         
                       
                     
                     
                       
                         
                           
                             ∇ 
                             
                               v 
                               → 
                             
                           
                            
                           
                             N 
                             → 
                           
                         
                         · 
                         
                           v 
                           → 
                         
                       
                     
                     
                       
                         
                           N 
                           → 
                         
                         · 
                         
                           v 
                           → 
                         
                       
                     
                   
                   
                     
                       
                         
                           
                             ∇ 
                             
                               u 
                               → 
                             
                           
                            
                           
                             N 
                             → 
                           
                         
                         · 
                         
                           w 
                           → 
                         
                       
                     
                     
                       
                         
                           
                             ∇ 
                             
                               v 
                               → 
                             
                           
                            
                           
                             N 
                             → 
                           
                         
                         · 
                         
                           w 
                           → 
                         
                       
                     
                     
                       
                         
                           N 
                           → 
                         
                         · 
                         
                           w 
                           → 
                         
                       
                     
                   
                 
                 ] 
               
               · 
               
                 [ 
                 
                   
                     
                       
                         
                           ∇ 
                           
                             p 
                             → 
                           
                         
                          
                         
                           · 
                           
                             u 
                             → 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           ∇ 
                           
                             p 
                             → 
                           
                         
                          
                         
                           · 
                           
                             v 
                             → 
                           
                         
                       
                     
                   
                   
                     
                       1 
                     
                   
                 
                 ] 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       
                         
                           N 
                           i 
                         
                         → 
                       
                       · 
                       
                         u 
                         → 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           N 
                           i 
                         
                         → 
                       
                       · 
                       
                         v 
                         → 
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           N 
                           i 
                         
                         → 
                       
                       · 
                       
                         w 
                         → 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
         [0022]    15 neighboring points are chosen to provide a set of linear constraints on the elements of the curvature tensor, which may be determined using least squares, and then the principal directions at p are calculated. 
         [0023]    Local triangulation is to construct topological connections in a small area of each point p in the point cloud. For each point p of point cloud, the 15 neighboring points are projected to the tangent plane and then a local Delaunay triangulation is performed in the tangent plane. A local triangulation near point p is derived from this 2D local Delaunay triangulation in the tangent plane by keeping topological connections. The edges and triangulations used in the following sections are based on this local Delaunay triangulation. 
         [0024]    The global smoothing of principal direction field makes the principal direction more consistent. The present invention defines an energy function to measure the difference between the principal directions of neighboring points, and then the principal direction is smoothed through minimizing this energy function. 
         [0025]    The energy function is defined as follows: 
         [0000]    
       
         
           
             
               E 
                
               
                 ( 
                 
                   α 
                   i 
                 
                 ) 
               
             
             = 
             
               
                 
                   ( 
                   
                     1 
                     - 
                     ρ 
                   
                   ) 
                 
                  
                 
                   
                     ∑ 
                     i 
                   
                    
                   
                       
                   
                    
                   
                     
                       sin 
                       2 
                     
                      
                     
                       ( 
                       
                         
                           α 
                           i 
                         
                         - 
                         
                           α 
                           i 
                           0 
                         
                       
                       ) 
                     
                   
                 
               
               - 
               
                 E 
                 smoothing 
               
             
           
         
       
       
         
           where 
         
       
       
         
           
             
               E 
               smoothing 
             
             = 
             
               ρ 
                
               
                 
                   ∑ 
                   
                     i 
                     , 
                     j 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     cos 
                     2 
                   
                    
                   
                     ( 
                     
                       
                         ( 
                         
                           
                             α 
                             i 
                           
                           - 
                           
                             β 
                             ij 
                           
                         
                         ) 
                       
                       - 
                       
                         ( 
                         
                           
                             α 
                             j 
                           
                           - 
                           
                             β 
                             ij 
                           
                         
                         ) 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0026]    here α i  are the unknown angles between the principle directions and a reference direction in the tangent plane, and β ij  represents the angle between the projection of edge i, j into the tangent plane and the reference direction. The user-defined parameter ρ indicates the smooth intensity. The function can be solved as an optimization problem using Newton&#39;s method, and then a smooth direction field is achieved. 
         [0027]    The goal of global parameterization is to find two scalar functions θ and φ, whose gradients align with the principal directions as much as possible. Global parameterization comprises three steps as illustrated in 
         [0028]      FIG. 3 : local Delaunay triangulation, calculating energy function, optimizing energy function. Local triangulation is defined as the same as in the smoothing of principal direction field. The energy function that measures the difference between the gradients and principal direction field is defined as follows: 
         [0000]        F=∫   S (∥∇θ T −ω{right arrow over (K)}∥ 2 +∥∇φ T −ω {right arrow over (K)}   ⊥ ∥ 2 ) dS  
 
         [0029]    The gradient of a scalar function at a point is defined as the sum of the gradients of its adjacent triangles, and the gradient in each triangle is defined as the sum of the gradient of each edge. In practice, the above equation is calculated as: 
         [0000]    
       
         
           
             F 
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     , 
                     j 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     
                       
                         θ 
                         i 
                       
                       - 
                       
                         θ 
                         j 
                       
                       - 
                       
                         wK 
                         · 
                         
                           e 
                           ij 
                         
                       
                     
                     ) 
                   
                   2 
                 
               
               + 
               
                 
                   ∑ 
                   
                     i 
                     , 
                     j 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     
                       
                         ϕ 
                         i 
                       
                       - 
                       
                         ϕ 
                         j 
                       
                       - 
                       
                         
                           wK 
                           ⊥ 
                         
                         · 
                         
                           e 
                           ij 
                         
                       
                     
                     ) 
                   
                   2 
                 
               
             
           
         
       
     
         [0030]    here, θ i  and φ i  denote the two scalar functions at point i, and K and K ⊥  denote the principal directions, e ij  denote the vector between and w is a user-defined parameter to control the density of parameterization. 
         [0031]    The function can be solved as a quadratic optimization problem using Newton&#39;s method, and then a global parameterization of the point cloud is achieved. 
         [0032]    Since the iso-lines of the resultant parameterization align the principal directions, the curve nets of iso-lines are a good start for quadrangulation. The intersection points of iso-lines are the vertices of final quad mesh, and the connection relationship among these vertices are determined by their connection relationship in the iso-lines. 
         [0033]    To remesh the point cloud, as illustrated in  FIG. 4 , the iso-segments in each triangle are first extracted, then the redundant segments are processed according to some rules and finally a quad mesh is constructed. 
         [0034]    Here the iso-lines comprise iso-segments in each triangle. Let the scalar value of the three points of a triangle is θ i , θ j , and θ k , and the iso-value is θ iso , for each edge e ij  of the triangle, if min (θ i , θ j )&lt;θ iso &lt;max ( θ i , θ j ), the intersection vertex of iso-line and this edge is 
         [0000]    
       
         
           
             p 
             = 
             
               
                 p 
                 i 
               
               + 
               
                 
                   
                      
                     
                       
                         θ 
                         i 
                       
                       - 
                       
                         θ 
                         iso 
                       
                     
                      
                   
                   
                      
                     
                       
                         θ 
                         i 
                       
                       - 
                       
                         θ 
                         j 
                       
                     
                      
                   
                 
                 · 
                 
                   
                     ( 
                     
                       
                         p 
                         j 
                       
                       - 
                       
                         p 
                         i 
                       
                     
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
         [0035]    Here, p i , p j  are the end points of e ij . For each triangle, if min (θ i , θ j , θ k )&lt;θ iso &lt;max (θ i , θ j , θ k ), two intersection points are produced, the iso-segments are obtained by connecting these two points. For a triangle, if the iso-segments corresponding to θ and φ exist simultaneously, then the intersection vertex of these two iso-segments is calculated, which is the intersection of iso-lines. 
         [0036]    Redundant triangles exist due to the overlapping triangles produced by local Delaunay triangulation. To handle the irregular points in the iso-lines, three rules are adopted to clean the iso-lines: 
         [0037]    1. In the first case, a triangle does not overlay any adjacent triangles as shown in  FIG. 5(   a ), then calculate the iso-segments with end points i, k and l. If the segments in the adjacent triangle have the same end point k , then they can be merged as i, k, l. 
         [0038]    2. In the second case, a triangle overlays one of its adjacent triangles as shown in  FIG. 5(   b ), then for the iso-segments with common vertex in this overlapping triangle, only the longer iso-segment is kept while the shorter is abandoned; i.e. point j is deleted and the index pair of i and k and the pair of k and l are merged as i, j. 
         [0039]    3. In the third case, a triangle overlaps its one adjacent triangle and two intersection points of iso-segments appear in both of them as shown in  FIG. 5(   c ), the two intersection points are merged by their average point. 
         [0040]    After the processing of iso-lines, each intersection point in the iso-lines is connected with its neighboring intersection points according to the iso-segment connections, and thus a quad mesh is constructed. 
         [0041]    The algorithm described in this invention is implemented in C++ programming language and tested on several models on a PC with Intel® Core™2 Quad CPU Q6600 and 4GB memory. OpenGL is used for the visualization. Table 1 gives the size of some models (number of points) and the time cost of the main steps (Curvature Estimation, Local triangulation, Global Parameterization) of our algorithm. 
         [0000]    
       
         
               
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
               
               
                   
                   
                 Curvature 
                 Local 
                 Global 
               
               
                   
                 Point 
                 Estimation 
                 Triangulation 
                 Parameterization 
               
               
                 Model 
                 Number 
                 (Sec) 
                 (Sec) 
                 (Sec) 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Saddle 
                 4860 
                 1.89 
                 1.72 
                 8.28 
               
               
                 Rock-arm 
                 14413 
                 4.48 
                 4.56 
                 11.23 
               
               
                 Cup 
                 57826 
                 15.14 
                 12.67 
                 42.36 
               
               
                 Soldier 
                 68740 
                 20.78 
                 15.84 
                 47.03 
               
               
                 Chair 
                 209499 
                 60.77 
                 47.13 
                 156 
               
               
                   
               
             
          
         
       
     
         [0042]      FIG. 6  gives the result on a noise model, in which 1% Gaussian noise is added.  FIG. 6(   a ) shows the smoothed principal direction field;  FIG. 6(   b ) shows the two iso-lines in blue and red,  FIG. 6(   c ) is the quad mesh. The resultant quads distribute across the surface evenly and capture the geometry feature. The results are obtained from point cloud, and for better visualization they are rendered on triangle surfaces. 
         [0043]    In  FIG. 7 , we apply our algorithm directly to the point cloud of the rock-arm model, and compare with the results produced by periodic global parameterization method (PGP) on a triangular mesh [Ray et al. 2006].  FIG. 7(   a ) and  FIG. 7(   b ) are our iso-lines and quad mesh, and  FIG. 7(   c ) and  FIG. 7(   d ) are Ray&#39;s results. We can see that although our method uses only the position information without connectivity information, our approach has no less quality than that of PGP. 
         [0044]    The innovation of this invention is a direct quad meshing method on point cloud without a mesh reconstruction step. And this method is fully automatic; the density of quad mesh can be controlled easily by adjusting the parameter. 
         [0045]    The present invention can be applied to point cloud data for both global parameterization and quad meshing. The present invention may be used in other computer graphics applications and is of high practical value. 
         [0046]    Although the present invention has been specifically described on the basis of a preferred embodiment and a preferred method, the invention is not to be construed as being limited thereto. Various changes or modifications may be made to said embodiment and method without departing from the scope and spirit of the invention.