Abstract:
Method for processing data defining an element in a space E or:
   a/ we define a set of n points in F;   b/ determined is the intersection between said element and a cell Voroni determined from the point that associates him x, implementing an iterative process that has no current iteration k, it selects an additional point x of the game distinct from x points and the intersection between calculi is half of the space bounded by the hyperplane E mediator of the segment that contains x, and resulting intersection calculi in no previous iteration, the selection of X is function of a comparison between x and x and twice the maximum distance between a bridge and a result of intersection when iterative processing.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention: 
         [0002]    The present invention relates to methods for processing data defining an element in a space E of dimensions d, comprising the following steps:
   a/ a set of n points in the space E is defined;   b/ the intersection between said element and Voronoi cells each determined from an associated point among said n defined points is computed.   
 
         [0005]    Such techniques are used, inter alia, for generating a mesh of an element such as a surface or a volume. 
         [0006]    Surface meshes are used in many technical applications, for example in digital flow simulation for aeronautical design or for oil exploration, in structural mechanics for the design of frames, bridges and other civil engineering structures, in the mechanics of deformations for simulating automotive impact tests, etc. 
         [0007]    Meshing consists in dividing the element under consideration into a set of base cells. Each base cell and the set of base cells as a whole must satisfy predefined validity conditions relating, for example, to the geometric shape of the base cells (square, triangle, tetrahedron, hexahedron, cube, etc.) or to apex angle values (compliance with minimum/maximum angle values). These predefined conditions are dependent, to a large extent, on the intended application of the mesh. 
         [0008]    There are several methods for generating a mesh of a domain. 
         [0009]    Some methods are known which are based on the optimisation of an “objective” function dependent on the coordinates at the vertices of the cells. Such methods are sometimes referred to as “variational methods”. 
         [0010]    Some methods use centroidal Voronoi tessellation (CVT) and optimal Delaunay triangulation (ODT). 
         [0011]    They allow isotropic meshes to be generated effectively and robustly. These methods are found to be particularly effective especially when an isotropic mesh is to be generated from triangular base cells (mesh of a surface) or tetrahedral base cells (mesh of a volume). 
         [0012]    In addition, some applications can require the generation of an anisotropic mesh, that is to say a mesh which has elements which differ from one another in terms of size and/or orientation, in predefined zones of the element. An anisotropic matrix is defined for each base cell specifying those constraints of orientation and size. 
       DESCRIPTION OF RELATED ART 
       [0013]    Document FR 2962582 describes a technique for generating an anisotropic mesh. 
         [0014]    Some techniques have appeared in which the anisotropy is replaced by additional dimensions of the space: an anisotropic element of dimension d0, for example 3D, is represented by a corresponding isotropic element of larger dimension d, for example 6D. This is referred to as embedding of the element of dimension d0 in a corresponding element of dimension d. 
         [0015]    By way of illustration, with reference to  FIGS. 1 and 2 , in order to generate an anisotropic 2D mesh governed by the anisotropic 2D metrics represented in part A of  FIG. 1 , a corresponding isotropic 3D surface is generated (see part A of  FIG. 2 ). 
         [0016]    In part A of  FIG. 1 , each deformed circle represents the points which are equidistant from the centre of the deformed circle in terms of anisotropic distance defined by the anisotropic metrics under consideration. 
         [0017]    According to these techniques, an isotropic Voronoi diagram is then generated for this 3D surface, shown in part B of  FIG. 2 . An isotropic mesh by Delaunay triangulation, shown in part C of  FIG. 2 , is then derived from the Voronoi diagram. 
         [0018]    The isotropic 3D surfaces shown in parts A, B, C of  FIG. 2  are projected onto the plane (xOy) in order to generate the corresponding anisotropic 2D surfaces of parts A, B, C of  FIG. 1 . 
         [0019]    Some of these techniques are explained especially in the following documents, called references — 1:
       J. F. Nash, The imbedding problem for riemannian manifolds. Annals of Mathematics, 63:20-63, 1956;   F. Labelle and J.-R. Shewchuk, Anisotropic Voronoi diagrams and guaranteed-quality anistropic mesh generation, In SCG &#39;03: Proceedings of the nineteenth annual symposium on Computational geometry, pages 191-200, 2003.       
 
         [0022]    These techniques give good results for the consideration of anisotropy, but embedding in larger dimensions d gives rise to a very considerable increase in the necessary computation volume. 
         [0023]    In fact, the computation of a Delaunay triangulation has a complexity proportional to d!, where d is the dimension of the computation space. In general, the embedding space is of dimension 6D, or even 10D, which renders the computation volume prohibitive. 
       BRIEF SUMMARY OF THE INVENTION 
       [0024]    The present invention aims to propose a solution for reducing the computation load in a space of dimension d. 
         [0025]    To that end, according to a first aspect, the invention proposes a method for processing data of the type mentioned above, characterised in that in step b/, the result of the intersection between said element and a Voronoi cell determined from the point x i  associated therewith is determined by carrying out an iterative processing in which at a current iteration step k, there is selected an additional point x jk  of the set of points other than the point x i , and there is computed an updated intersection result equal to the intersection between, on the one hand, the half of the space E delimited by the hyperplane bisecting the segment (x i , x jk ) and which contains x i  and, on the other hand, the intersection result computed at the preceding iteration step,
   and in which the selection of at least one additional point during the iteration steps is a function of a comparison between the distance between the associated point x i  and said additional point and double the maximum distance between the associated point x i  and a point of an intersection result computed during the iterative processing.   
 
         [0027]    The invention makes it possible to reduce the volume of computations necessary for computing the intersections of the Voronoi cells with the element under consideration, by using a test which allows unnecessary computations to be avoided. It further allows the processing operations for separate Voronoi cells to be parallelised. 
         [0028]    In embodiments, the method according to the invention further comprises one or more of the following features:
       in step b/, the n−1 other points of the set classified in order of increasing distance relative to the point x i  are denoted x j1 , . . . x jn−1 , and the iterative processing is carried out by selecting at the current iteration step k the point x jk  of the set of points which follows, in said order of increasing distance, the point x jk−1  selected at iteration step k−1;   said iterative processing is stopped as a function of a comparison between the distance between the associated point x i  and the point x j+1  and double the maximum distance between the associated point x i  and a point of the intersection result computed at iteration step k;   in an initialisation step, the index k is fixed at 1 and the intersection result is fixed to be equal to the element;   steps a/ and b/ are repeated in their entirety, a set of n points taken from at least the preceding set being defined in each new step at;   steps a/ and b/ are repeated in their entirety;   during the step of computing an updated intersection result equal to the intersection between, on the one hand, the half of the space E delimited by a hyperplane bisecting a segment (x i , x jk ) and which contains x i  and, on the other hand, the intersection result computed at the preceding iteration step, the following steps are carried out:
           it is determined whether a vertex q of the updated intersection result is the intersection between the hyperplane bisecting [x i , x p ] and an edge [q 1 , q 2 ] between two vertices q1, q2 of the element, where x p  is a point of the set of n points;   and if said vertex q is determined as being the intersection between the hyperplane bisecting [x i , x p ] and an edge [q 1 , q 2 ] between two vertices q1, q2 of the element, the coordinates of q are determined by means of the following formulae:   
               
 
         [0000]        q=λ   1   q   1 +λ 2   q   2 , where λ 1 =Δ −1 (−∥ x   p ∥ 2 +2&lt; q   2   , x   p &gt;)
 
         [0000]      λ 2 =Δ −1 (−∥ x   p ∥ 2 −2&lt; q   1   , x   p &gt;)
 
         [0000]      where Δ=−2&lt; q   1   , x   p &gt;+2&lt; q   2   , x   p &gt;, and
 
         [0000]      &lt;.,.&gt; represents the function scalar product;
       during the step of computing an updated intersection result equal to the intersection between, on the one hand, the half of the space E delimited by a hyperplane bisecting a segment (x i , x jk ) and which contains x i  and, on the other hand, the intersection result computed at the preceding iteration step, the following steps are carried out:
           it is determined whether a vertex q of the updated intersection result is the intersection between the hyperplane bisecting [x i , x p ], the hyperplane bisecting [x i , x l ], and a triangle of vertices q 1 , q 2 , q 3  of the element, where x p  and x l  are two points of the set of n points;   and if q is determined as being the intersection between the hyperplane bisecting [x i , x p ], the hyperplane bisecting [x i , x l ], and a triangle of vertices q 1 , q 2 , q 3  of the element, the coordinates of q are determined by means of the following formulae:   
               
 
         [0000]        q=λ   1   q   1 +λ 2   q   2 +λ 3   q   3 , where
 
         [0000]      λ 1 =Δ −1 [( a   23   −a   22 )∥ x   p ∥ 2 +( a   12   −a   13 )∥ x   l ∥ 2   +c   31 ];
 
         [0000]      λ 2 =Δ −1 [( a   21   −a   23 )∥ x   p ∥ 2 +( a   13   −a   11 )∥ x   l ∥ 2   +c   32 ];
 
         [0000]      λ 3 =Δ −1 [( a   22   −a   21 )∥ x   p ∥ 2 +( a   11   −a   12 )∥ x   l ∥ 2   +c   33 ];
 
         [0000]      where  a   11 =−2&lt; q   1   , x   p   &gt;; a   12 =−2&lt; q   2   , x   p   &gt;; a   13 =−2&lt; q   3   , x   p &gt;
 
         [0000]        a   21 =−2&lt; q   1   , x   l   &gt;; a   22 =−2&lt; q   2   , x   l   &gt;; a   23 =−2&lt; q   3   , x   l &gt;
 
         [0000]    
       
      
       c 
       31 
       =a 
       23 
       a 
       12 
       −a 
       22 
       a 
       13 
       ; c 
       32 
       =a 
       21 
       a 
       13 
       −a 
       23 
       a 
       11 
       ; c 
       33 
       =a 
       22 
       a 
       11 
       −a 
       21 
       a 
       12  
      
     
         [0000]      Δ= c   31   +c   32   +c   33 , and
 
         [0000]      &lt;.,.&gt; represents the function scalar product;
       during the step of computing an updated intersection result equal to the intersection between, on the one hand, the half of the space E delimited by a hyperplane bisecting a segment (x i , x jk ) and which contains x i  and, on the other hand, the intersection result computed at the preceding iteration step, comprising the following steps:
           it is determined whether a vertex q of the updated intersection result is a vertex of the element;   if said vertex q is determined as being a vertex of the element, the presence of said vertex q in the half of the space E delimited by the hyperplane bisecting the segment (x i , x jk ) and which contains x i  is determined as a function of the sign of the function orient (Π + (i, j k ),q) defined by:   
               
 
         [0000]      orient (Π + ( i, j   k ), q )=sign(∥ x   jk ∥ 2 −2 &lt;q, x   jk &gt;), where
       &lt;.,.&gt; represents the function scalar product and sign (x) is the function providing the sign of the variable x;   during the step of computing an updated intersection result equal to the intersection between, on the one hand, the half of the space E delimited by a hyperplane bisecting a segment (x i , x jk ) and which contains x i  and, on the other hand, the intersection result computed at the preceding iteration step:
           it is determined whether a vertex q of the updated intersection result is the intersection between the hyperplane bisecting [x i , x p ] and an edge [q 1 , q 2 ] between two vertices q1, q2 of the element, where x p  is a point of the set of n points;   if q is determined as being the intersection between the hyperplane bisecting [x i , x k ] and an edge [q 1 , q 2 ] between two vertices q1, q2 of the element, the presence of said vertex q in the half of the space E delimited by the hyperplane bisecting the segment (x i ,x jk ) and which contains x i  is determined as a function of the sign of the function orient (Π + (i, j k ),q) defined by:   
               
 
         [0000]      orient (Π + ( i, j   k ), q )=sign (Δ∥ x   jk ∥ 2 −2&lt;Δ q, x   jk &lt;).sign (Δ),
 
         [0000]    where Δ=−2&lt;q 1 , x p &gt;+2&lt;q 2 , x p &gt; and where &lt;.,.&gt; represents the function scalar product and sign (x) is the function providing the sign of the variable x;
       during the step of computing an updated intersection result equal to the intersection between, on the one hand, the half of the space E delimited by a hyperplane bisecting a segment (x i , x jk ) and which contains x i  and, on the other hand, the intersection result computed at the preceding iteration step:
           it is determined whether a vertex q of the updated intersection result is the intersection between the hyperplane bisecting [x i , x p ], the hyperplane bisecting [x i , x l ], and a triangle of vertices q 1 , q 2 , q 3  of the element, where x p  and x l  are two points of the set of n points;   if said vertex q of the updated intersection result is determined as being the intersection between the hyperplane bisecting [x i , x p ], the hyperplane bisecting [x i , x l ], and a triangle of vertices q 1 , q 2 , q 3  of the element, the presence of said vertex q in the half of the space E delimited by the hyperplane bisecting the segment (x i , x jk ) and which contains x i  is determined as a function of the sign of the function orient (Π + (i, j k ),q) defined by: orient (Π + (i, j k ),q)=sign (Δ∥x jk ∥ 2 −2&lt;Δq, x jk &gt;).sign (Δ), where   
               
 
         [0000]      Δ= c   31   +c   32   +c   33 ;
 
         [0000]        c   31   =a   23   a   12   −a   22   a   13   ; c   32   =a   21   a   13   −a   23   a   11   ; c   33   =a   22   a   11   −a   21   a   12 ; 
         [0000]        a   11 =−2&lt; q   1   , x   p   &gt;; a   12 =−2&lt; q   2   , x   p   &gt;; a   13 =−2&lt; q   3   , x   p &gt;
 
         [0000]        a   21 =−2&lt; q   1   , x   l   &gt;; a   22 =−2&lt; q   2   , x   l   &gt;; a   23 =−2&lt; q   3   , x   l &gt; and where
 
         [0000]      &lt;.,.&gt; represents the function scalar product and sign (x) is the function providing the sign of the variable x.
 
         [0050]    According to a second aspect, the present invention proposes a computer program for processing data defining an element in a space E of dimensions d, said program including instructions for carrying out the steps of a method according to the first aspect of the invention during execution of the program by processing means. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0051]    These features and advantages of the invention will become apparent upon reading the following description, which is given solely by way of example and with reference to the accompanying drawings, in which: 
           [0052]      FIG. 1  shows in part A an anisotropic field prescribed on a 2D surface, in part B a resulting Voronoi diagram and in part C the result of the corresponding Delaunay triangulation; 
           [0053]      FIG. 2  shows in part A an isotropic D surface, in part B a resulting Voronoi diagram and in part C the result of the corresponding Delaunay triangulation; 
           [0054]      FIG. 3  shows in part A a Voronoi diagram of a set of points, in part B the configuration obtained after one iteration of Lloyd&#39;s relaxation algorithm, in part C the configuration obtained after 100 iterations of Lloyd&#39;s relaxation algorithm and in part D the result of the Delaunay triangulation resulting from the configuration shown in part C; 
           [0055]      FIG. 4  is a view of a data processing device in one embodiment of the invention; 
           [0056]      FIG. 5  shows steps of a method in one embodiment of the invention; 
           [0057]      FIG. 6  shows steps of a method in one embodiment of the invention; 
           [0058]      FIG. 7  shows steps of a method in one embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Voronoi Diagram and Delaunay Triangulation: 
       [0059]    The definitions of a Voronoi diagram and of Delaunay triangulation will first be recalled. 
         [0060]    Given a set X of points such that X={x 1 , x 2 , . . . , x n } with x i ∈R d , where R is the real numbers space and d is the dimension under consideration, the Voronoi diagram Vor(X) is the collection of the Voronoi cells Vor(x i ), i=1 to n. 
         [0061]    The Voronoi cell Vor(x i ) associated with the point x i  is defined by: 
         [0000]      Vor(x i )={ x∈R   d   /d ( x,x   i )≦ d ( x,x   j ), ∀ j= 1 to  n} 
 
         [0000]    where d(.,.) indicates the Euclidean distance R d . 
         [0062]    The dual of the Voronoi diagram Vor(X), that is to say the abstract simplicial complex derived from the combinatorics of Vor(X), is called the Delaunay triangulation. 
         [0063]    Each pair of Voronoi cells Vor(x i ), Vor(x j ) which has a non-zero intersection defines a side (x i , x j ) in the Delaunay triangulation, and each triplet of Voronoi cells Vor(x i ), Vor(x j ), Vor(x k ) which has a non-zero intersection defines a triangle (x i , x j , x k ). 
         [0064]    The Delaunay triangulation has several interesting geometric properties and is used in many applications, for example, but not only, mesh generation processing (see Jean-Daniel Boissonnat and Mariette Yvinec. Algorithmic Geometry. Cambridge University Press, 1998). 
         [0065]    The centroidal Voronoi tessellation or CVT is a Voronoi diagram in which the point x i , for i=1 to n, is the centre of the Voronoi cell associated with x i . 
         [0066]    A CVT can be produced by an algorithm, called Lloyd&#39;s relaxation algorithm, which iteratively displaces each point x i  to the centre of Vor(x i ) and provides isotropic triangles (see Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2): 129-137, 1982). 
         [0067]    With reference to  FIG. 3 , a 2D Voronoi diagram associated with the points x i  (corresponding to the points which are not in bold) is shown in part A. The centres of the Voronoi cells are shown by bold points. In part B of  FIG. 3 , the configuration obtained after one iteration of Lloyd&#39;s relaxation algorithm is shown. In part C of  FIG. 3 , the configuration obtained after 100 iterations of Lloyd&#39;s relaxation algorithm is shown. In part D of  FIG. 3 , the Delaunay triangulation derived from the configuration of part C of  FIG. 3  is shown. 
         [0068]    Now, the notions of restricted Voronoi diagram and restricted Delaunay triangulation have been defined. 
         [0069]    Let S be a domain included in R d . 
         [0070]    For example, S is a surface or a volume, or any other domain. 
         [0071]    The Voronoi diagram of the set X restricted to S, denoted Vor(X)| s , is the set of Voronoi cells Vor(x i ), i=1 to n, restricted to S, denoted Vor(x i )| s . 
         [0072]    The Voronoi cell restricted to S, Vor(x i )| s , is equal to Vor(x i )| s =Vor(x i )∩S. 
         [0073]    The dual of the Voronoi diagram Vor(X), that is to say the abstract simplicial complex derived from the combinatorics of Vor(X)| s , is called the restricted Delaunay triangulation. Each triangle of a restricted Delaunay triangulation corresponds to three restricted Voronoi cells having a non-empty intersection. 
         [0074]    As a direct consequence of their definition, restricted Voronoi cells can also be defined by 
         [0000]    
       
         
           
             
               
                 
                   Vor 
                    
                   
                     ( 
                     
                       x 
                       i 
                     
                     ) 
                   
                 
                  
                 
                   | 
                   s 
                 
               
               = 
               
                 S 
                  
                 
                   ⋂ 
                   
                     
                       j 
                       = 
                       
                         1 
                          
                         
                             
                         
                          
                         to 
                          
                         
                             
                         
                          
                         n 
                       
                     
                     , 
                     
                       j 
                       ≠ 
                       i 
                     
                   
                 
                  
                 
                   
                     Π 
                     + 
                   
                    
                   
                     ( 
                     
                       i 
                       , 
                       j 
                     
                     ) 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where Π + (i, j)={x|d(x, x i )≦d(x, x j )} is the half-space in R d  which is limited by the hyperplane bisecting the segment [x i , x j ] and which contains x i . 
         [0075]    It is thus seen that a restricted Voronoi cell Vor(x i )| s  can be obtained by starting from the space R d  and iteratively carrying out divisions by means of the hyperplanes Π + (i, j) for j=1 to n and j≠i. 
         [0076]    Applying such an iteration in practice is of no value because the algorithm which would result therefrom would have superquadratic complexity. For that reason, existing algorithms are based on different considerations. There are known, for example, the methods for computing Voronoi diagrams based on the properties of the Delaunay triangulation which are described in the following reference work: “Algorithmic Geometry”, Boissonnat and Yvinec, ISBN-13: 978-0521565295. These conventional algorithms compute the Delaunay triangulation directly by inserting the points one by one and correcting the mesh iteratively in order to verify the property called the “empty sphere” property. 
       Principle of the Safety Radius: 
       [0077]    One of the aspects of the invention is to make it possible to determine effectively which of the bisecting hyperplanes defined by the segments [x i , x j ] contribute to the determination of Voronoi cell Vor(x i ) and which do not, that is to say Vor(x i )⊂Π + (i, j). 
         [0078]    Let us consider x j1 , . . . x jn−1  to be the n−1 points of the set X other than x i , classified by order of increasing distance from x i . 
         [0079]    Let V k (x i ) be the intersection of the first k bisecting hyperplanes situated between x i  and each of these first k points, and R k  its radius centred on x i , namely: 
         [0000]    
       
         
           
             
               
                 V 
                 k 
               
                
               
                 ( 
                 
                   x 
                   i 
                 
                 ) 
               
             
             = 
             
               
                 
                   
                     ⋂ 
                     
                       i 
                       = 
                       1 
                     
                   
                   k 
                 
                  
                 
                   
                     
                       Π 
                       + 
                     
                      
                     
                       ( 
                       
                         i 
                         , 
                         
                           j 
                           i 
                         
                       
                       ) 
                     
                   
                    
                   
                       
                   
                    
                   and 
                    
                   
                       
                   
                    
                   
                     R 
                     k 
                   
                 
               
               = 
               
                 max 
                  
                 
                   
                     { 
                     
                       
                         
                           d 
                            
                           
                             ( 
                             
                               
                                 x 
                                 i 
                               
                               , 
                               x 
                             
                             ) 
                           
                         
                         / 
                       
                        
                       
                         
                           V 
                           k 
                         
                          
                         
                           ( 
                           
                             x 
                             i 
                           
                           ) 
                         
                       
                     
                     } 
                   
                   . 
                 
               
             
           
         
       
     
         [0080]    The safety radius theorem according to the invention is as follows:
   For any j such that (d(x i ,x j )&gt;2·R k , the bisecting hyperplane Π + (i, j) does not contribute to the construction of the Voronoi cell Vor(x i ), i.e. V k (x i )⊂Π + (i, j).   
 
         [0082]    Proof: considering x∈V k (x i ) and x j  such that d(x i ,x j )&gt;2 R k ,
   by definition of R k , d(x,x i )&lt;R k .   d(x i ,x)+d(x,x j )&gt;d(x i ,x j ) (triangular inequality)   and d(x i ,x i )&gt;2 R k ,   consequently d(x,x j )&gt;R k &gt;d(x,x i ) and x∈Π + (i, j).   
 
         [0087]    It will be noted that this theorem has advantageous practical applications when it is applied to bounded Voronoi cells, and consequently to restricted Voronoi cells. 
         [0088]    Direct consequence of the safety radius theorem: 
         [0000]      if  d ( x   i   ,x   jk+1 )&gt;2· R   k  then  V   k ( x   i )=Vor( x   i ).
 
         [0089]    The safety radius is the first value of Rk (i.e. the greatest) which is encountered when running through the x j1 , . . . x jn−1  in that order which satisfies that condition “d(x i ,x jk+1 )&gt;2·Rk”. 
         [0090]    Example of the Application of the Principle of the Safety Radius 
         [0091]    In the following, an example of the application of the safety radius theorem to a device and a method for processing data, those data defining a domain S0, is explained. 
         [0092]    In the case under consideration, S0 is a surface extending in a space of dimension d0, for example d0=3. 
         [0093]    In other cases, S0 may be a volume delimited by a surface, or any other type of domain. 
         [0094]    In the case under consideration, the aim of the processing which is carried out is to generate an anisotropic mesh of the domain S0 in accordance with a prescribed an isotropic field. 
         [0095]    To that end, let us consider a device  10  for processing data shown in  FIG. 4 . 
         [0096]    Such a processing device  10  comprises a memory  11 , a microcomputer  12  and a man-machine interface  13 , which comprises especially a screen for displaying a mesh generated for the domain S0. 
         [0097]    The memory  10  contains especially digital data defining the domain S0, and a computer program P. 
         [0098]    The program P includes software instructions which, when executed by the microcomputer  12 , carry out the steps indicated below with reference to  FIGS. 5-7 . 
         [0099]    Let the domain of dimension d0 for which an anisotropic mesh governed by a given anistropic metrics is to be generated be S0. 
         [0100]    In a step  100 , there is made to correspond to the domain S0 of dimension d0 a domain S of dimensions d&gt;d0 in accordance with the documents called references_ 1  above. For example, d=6 or 10. 
         [0101]    For d0=3 and d=6, for any point [x,y,z] of S0, for example, a point [x,y,z,s.N x , s.N y , sN z ] of S is made to correspond to point [x,y,z], where the factor s indicates the desired degree of anisotropy (a small value of s generates an isotropic mesh and a large value of s generates an anisotropic mesh). N x , N y , N z  are the unit vectors normal to the surface S0 at the point [x,y,z]. 
         [0102]    An iterative processing  101  is then carried out in order to determine an isotropic mesh of the domain S. 
         [0103]    Accordingly, in a step  102 , the value n of the number of Voronoi cells being fixed, a set X of n points of the space R d , {x 1 , x 2 , . . . , x n } with x 1 ∈R d , is determined for the current iteration. 
         [0104]    During the first iteration, the set X of points is, for example, chosen randomly. 
         [0105]    Then, during the following iterations, the set X is determined as a function of the results of the last iteration carried out for the processing  101 . 
         [0106]    In a step  103 , a step of determining the Voronoi diagram restricted to S, that is to say Vor(x i )| s , is carried out. 
         [0107]    In a step  104 , a loop exit condition is tested. This loop exit condition comprises, for example:
       a comparison between the current iteration value k and a fixed maximum threshold; and/or   the normal of the gradient of an “objective” function is below a certain threshold. For example, the “objective” function represents the quantisation noise power, that is to say the sum of the moments of inertia of the Voronoi cells.       
 
         [0110]    If the loop exit condition  105  is not satisfied, the value of k is increased by 1 and an additional iteration of the processing  101  is carried out. 
         [0111]    If the loop exit condition  104  is satisfied, the iterative processing  101  is stopped. A step  105  of restricted Delaunay triangulation is then carried out in order to determine the dual of the Voronoi diagram provided at the end of the iterative processing  101  by direct deduction from the combinatorics of the restricted Voronoi diagram, that is to say for each vertex of the restricted Voronoi diagram, the corresponding Delaunay triangle is generated. 
         [0112]    Various operations can then be carried out, especially the projection onto the initial space of dimension d0 of the result of the Delaunay triangulation obtained in the space of dimension d at the end of the iterative treatment  101 , so as to obtain the desired anisotropic mesh of the domain S0. 
         [0113]    In the embodiment under consideration, the step  103  of determining Vor(x)| s  is carried out in the manner indicated below with reference to  FIG. 6 :
   In a step  103 _ 1 , for each x i , where i=1 to n, the other points x i , j=1 to n and j≠i, are sorted by order of increasing distance from x i , which results in an ordered list x j1 , . . . x jn−1 . To that end, the ANN tool, for example, is used (David M. Mount and Sunil Arya, ANN: A library for approximate nearest neighbor searching. In Proceedings CGC Workshop on Computational Geometry, pages 33-40, 1997).   
 
         [0115]    In an initialisation step  103 _ 2 , the variable m i  and each of the coordinates of points g i  of R d , i=1 to n, are initialised with the value 0. 
         [0116]    In a step  103 _ 3 , the domain S is divided into subdomains in order to allow the steps carried out on separate subdomains (triangles, tetrahedrons, etc.) to be parallelised. 
         [0117]    In the case under consideration, the subdomains f of the surface S are triangles. 
         [0118]    In a step  103 _ 4 , for each point x i , where i=1 to n, and for each subdomain f such that the intersection between the subdomain f and the Voronoi cell associated with x i  is not empty, Vor(x i )| f , the Voronoi cell associated with x i  and restricted to the subdomain f i  is determined in the manner indicated below with reference to  FIG. 7 . 
         [0119]    The value of the “mass” of Vor(x i )| f  is then allocated to a variable m i  the value of m is added to the current value of m i , and the value of the coordinates of the point g i  is updated according to the formula: g i =g i +m.centre Vor(x i )| f , where centre Vor(x i )| f  is the centre of gravity of Vor(x i )| f . 
         [0120]    The “mass” of Vor(x i )| f  is equal to 
         [0000]    
       
         
           
             . 
             
               
                 ∫ 
                 
                   
                     x 
                     ∈ 
                     
                       Vor 
                        
                       
                         ( 
                         
                           x 
                           i 
                         
                         ) 
                       
                     
                   
                    
                   
                     | 
                     f 
                   
                 
               
                
               
                   
               
                
               
                 
                    
                   x 
                 
                 . 
               
             
           
         
       
     
         [0000]    Accordingly, the “mass” of Vor(x i )| f  is the area of Vor(x i )| f  if Vor(x i )| f  is a surface, the volume of Vor(x i )| f  if Vor(x i )| f  is a volume, the hyper-volume of Vor(x i )| f  if Vor(x i )| f  has a dimension greater than or equal to 4. 
         [0121]    The centre of gravity of Vor(x i )| f  is 
         [0000]    
       
         
           
             
               1 
               
                 
                   mass 
                    
                   
                       
                   
                    
                   of 
                    
                   
                       
                   
                    
                   
                     Vor 
                      
                     
                       ( 
                       
                         x 
                         i 
                       
                       ) 
                     
                   
                 
                  
                 
                   | 
                   f 
                 
               
             
              
             
               
                 ∫ 
                 
                   
                     Vor 
                      
                     
                       ( 
                       
                         x 
                         i 
                       
                       ) 
                     
                   
                    
                   
                     | 
                     f 
                   
                 
               
                
               
                   
               
                
               
                 x 
                 . 
                 
                    
                   x 
                 
                 . 
               
             
           
         
       
     
         [0122]    In one embodiment, the determination of the set of points X in a step  102  for iteration k+1 of the processing  101  is, for example, such that the point x i =g i .1/m i , where i=1 to n and g i  is the point obtained at the end of step  103 _ 4  carried out for iteration k of the processing  101 . 
         [0123]    According to the invention, step  103 _ 4  of determining the Voronoi cell Vor(x i )| f  associated with x i  and restricted to the subdomain f is carried out using the safety radius theorem, and considering the points x j1 , . . . x jn−1  in order of increasing distance from x i . 
         [0124]    In an exemplary embodiment, with reference to  FIG. 7 , step  103 _ 4  thus comprises the following operations. 
         [0125]    In an initialisation step  103 _ 41  a domain V equal to the subdomain f under consideration, a value t equal to 1 and a value R equal to max{d(x i , x)/x∈V} are considered. 
         [0126]    In a step  103 _ 42 , the following steps are iterated as long as d(x i , x jt )&lt;2R and t&lt;n: 
         [0000]        V=V∩Π   + ( i, j   t ); 
         [0000]        R =max{ d ( x   i   , x )/ x∈V};    
         [0000]        t=t+ 1. 
         [0000]    When d(x i , x jj )≧2R or t=n, step  103 _ 42  is stopped. 
         [0127]    And the current value of V is then equal to the Voronoi cell Vor(x i )| f  associated with x i  and restricted to the subdomain f (continuing the iterations of step  103 _ 42  is no further use since the bisecting hyperplanes which have not yet been taken into account do not contribute). 
         [0128]    For the effective computation of the intersection V∩Π + (i, j t ), Sutherland &amp; Hodgman&#39;s reentrant polygon clipping algorithm may be used, for example (Ivan Sutherland and Gary W. Hodgman, Reentrant polygon clipping. Communications of the ACM, 17:32-42, 1974). 
         [0129]    The use of the safety radius theorem makes it possible to determine only the sections of the Voronoi cell which are of use for computing the intersection between that cell and the subdomain f under consideration, thus greatly reducing the necessary computation volume, which is very considerable especially when the value of the dimension d of the space under consideration increases. 
         [0130]    In addition, it allows the intersections for respective Voronoi cells to be computed in parallel and independently. 
         [0131]    In one embodiment, a method according to the invention carries out the steps indicated below in order to define the intersection between a subdomain f and a Voronoi cell in a space of dimensions d, using the scalar products and the linear combination of vectors, the computation volume carried out being independent of the dimension d. 
         [0132]    It will be noted that these steps can be carried out independently of the use of the so-called safety radius test. 
         [0133]    In the step of computing V∩Π + (i, j t ) by means of Sutherland &amp; Hodgman&#39;s reentrant polygon clipping algorithm, it is necessary to determine the coordinates of the new vertices of the domain resulting from this intersection, and also to determine the side on which a vertex is situated relative to a half-space Π + (i, j). 
         [0134]    The function which makes it possible to determine the side on which a vertex q is situated relative to the half-space Π + (i, j) is called orient (Π + (i, j),q). If the result of orient (Π + (i, j),q) is positive, the vertex q is situated in the half-space Π + (i, j). 
         [0135]    Otherwise, the vertex q is outside the half-space Π + (i, j). 
         [0136]    Vertices q of the resulting domain in some cases have already been determined during preceding iteration(s) or only appear in the current iteration. 
         [0137]    Three different configurations exist for a vertex q:
   a- q is a vertex of the subdomain f under consideration;   b- q is the intersection between the hyperplane bisecting [x i , x k ] and an edge [q 1 , q 2 ] between two vertices q 1 , q 2  of the subdomain f;   c- q is the intersection between two bisecting hyperplanes (for example the hyperplane bisecting [x i , x k ] and the hyperplane bisecting [x i , x l ]) and the subdomain f; in the present case, the subdomain is the triangle of vertices q 1 , q 2 , q 3 .   
 
         [0141]    Without loss of generality, x i  is assumed to be at the origin of the space under consideration. Return thereto is achieved by applying a translation. 
         [0142]    In case a/, the coordinates of q are known and orient (Π + (i, j), q)=sign (∥x j ∥ 2 −2&lt;q, x j &gt;), where &lt;,&gt; represents the function scalar product. 
         [0143]    In case b/, the barycentric coordinates (λ 1 , λ 2 ) of q relative to q 1 , q 2  are determined: q=λ 1 q 1 +λ 2 q 2 . 
         [0000]    
       
         
           
             
               [ 
               
                 
                   
                     
                       λ 
                       1 
                     
                   
                 
                 
                   
                     
                       λ 
                       2 
                     
                   
                 
               
               ] 
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 1 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 2 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                     
                     
                       
                         1 
                       
                       
                         1 
                       
                     
                   
                   ] 
                 
                 
                   - 
                   1 
                 
               
                
               
                 [ 
                 
                   
                     
                       
                         
                           
                              
                             
                               x 
                               i 
                             
                              
                           
                           2 
                         
                         - 
                         
                           
                              
                             
                               x 
                               k 
                             
                              
                           
                           2 
                         
                       
                     
                   
                   
                     
                       1 
                     
                   
                 
                 ] 
               
             
           
         
       
     
         [0144]    By calling Δ the determinant of the 2×2 matrix above: 
         [0000]      Δ=−2&lt; q   1   , x   k &gt;+2&lt; q   2   , x   k &gt;
 
         [0000]      λ 1 =Δ −1 (−∥ x   k ∥ 2 +2&lt; q   2   , x   k &gt;) and λ 2 =Δ −1 (∥ x   k ∥ 2 +2&lt; q   1   , x   k &gt;)
 
         [0000]    and orient (Π + (i, j), q)=sign (Δ∥x j ∥ 2 −2&lt;Δq, x j &gt;). sign (Δ). 
         [0145]    In case c/, the barycentric coordinates (λ 1 , λ 2 , λ 3 ) of q relative to q 1 , q 2 , q 3  are determined: q=λ 1 q 1 +λ 2 q 2 +λ 3 q 3 . 
         [0000]    
       
         
           
             
               [ 
               
                 
                   
                     
                       λ 
                       1 
                     
                   
                 
                 
                   
                     
                       λ 
                       2 
                     
                   
                 
                 
                   
                     
                       λ 
                       3 
                     
                   
                 
               
               ] 
             
             = 
             
               
                 
                   [ 
                   
                     
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 1 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 2 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 3 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                     
                     
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 1 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     l 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 2 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     l 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                       
                         
                           2 
                            
                           
                             〈 
                             
                               
                                 q 
                                 3 
                               
                               , 
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     x 
                                     l 
                                   
                                 
                                 ) 
                               
                             
                             〉 
                           
                         
                       
                     
                     
                       
                         1 
                       
                       
                         1 
                       
                       
                         1 
                       
                     
                   
                   ] 
                 
                 
                   - 
                   1 
                 
               
                
               
                 [ 
                 
                   
                     
                       
                         
                           
                              
                             
                               x 
                               i 
                             
                              
                           
                           2 
                         
                         - 
                         
                           
                              
                             
                               x 
                               k 
                             
                              
                           
                           2 
                         
                       
                     
                   
                   
                     
                       
                         
                           
                              
                             
                               x 
                               i 
                             
                              
                           
                           2 
                         
                         - 
                         
                           
                              
                             
                               x 
                               l 
                             
                              
                           
                           2 
                         
                       
                     
                   
                   
                     
                       1 
                     
                   
                 
                 ] 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   a 
                   11 
                 
                 = 
                 
                   
                     - 
                     2 
                   
                    
                   
                     〈 
                     
                       
                         q 
                         1 
                       
                       , 
                       
                         x 
                         k 
                       
                     
                     〉 
                   
                 
               
               ; 
               
                 
                   a 
                   12 
                 
                 = 
                 
                   
                     - 
                     2 
                   
                    
                   
                     〈 
                     
                       
                         q 
                         2 
                       
                       , 
                       
                         x 
                         k 
                       
                     
                     〉 
                   
                 
               
               ; 
               
                 
                   a 
                   13 
                 
                 = 
                 
                   
                     - 
                     2 
                   
                    
                   
                     〈 
                     
                       
                         q 
                         3 
                       
                       , 
                       
                         x 
                         k 
                       
                     
                     〉 
                   
                 
               
             
           
         
       
       
         
           
             
                 
             
              
             
               
                 
                   a 
                   21 
                 
                 = 
                 
                   
                     - 
                     2 
                   
                    
                   
                     〈 
                     
                       
                         q 
                         1 
                       
                       , 
                       
                         x 
                         l 
                       
                     
                     〉 
                   
                 
               
               ; 
               
                 
                   a 
                   22 
                 
                 = 
                 
                   
                     - 
                     2 
                   
                    
                   
                     〈 
                     
                       
                         q 
                         2 
                       
                       , 
                       
                         x 
                         l 
                       
                     
                     〉 
                   
                 
               
               ; 
               
                 
                   a 
                   23 
                 
                 = 
                 
                   
                     - 
                     2 
                   
                    
                   
                     
                       〈 
                       
                         
                           q 
                           3 
                         
                         , 
                         
                           x 
                           1 
                         
                       
                       〉 
                     
                     . 
                   
                 
               
             
           
         
       
     
         [0146]    The following cofactors are computed: 
         [0000]    
       
      
       c 
       31 
       =a 
       23 
       a 
       12 
       −a 
       22 
       a 
       13 
       ; c 
       32 
       =a 
       21 
       a 
       13 
       −a 
       23 
       a 
       11 
       ; c 
       33 
       =a 
       22 
       a 
       11 
       −a 
       21 
       a 
       12  
      
     
         [0000]    Δ being the development of the determinant relative to the last line of the 3×3 matrix: Δ=c 21 +c 32 +c 33 . 
         [0147]    It follows therefrom: 
         [0000]      λ 1 =Δ −1 [( a   23   −a   22 )∥ x   k ∥ 2 +( a   12   −a   13 )∥ x   l ∥ 2   +c   31 ];
 
         [0000]      λ 2 =Δ −1 [( a   21   −a   23 )∥ x   k ∥ 2 +( a   13   −a   11 )∥ x   l ∥ 2   +c   32 ];
 
         [0000]      λ 3 =Δ −1 [( a   22   −a   21 )∥ x   k ∥ 2 +( a   11   −a   12 )∥ x   l ∥ 2   +c   33 ];
 
         [0000]    and orient (Π + (i, j), q)=sign (Δ∥x j ∥ 2 −2&lt;Δq, x j &gt;). sign (Δ). 
         [0148]    The formulation of q and of the function orient is therefore independent of the dimension d, in that only the scalar product &lt;.,.&gt; and linear combinations are involved, and where the dimension of the linear systems is independent of d. 
         [0149]    Furthermore, it lends itself well to an implementation in arbitrary-precision arithmetic and arithmetic with filtering (by interval arithmetic or quasi-static filters). 
         [0150]    The recentring (translation of x, to the origin) improves the filtering performances. 
         [0151]    The algorithm implementing these steps of computation of the coordinates of q and of the function orient is parameterised by a geometric nucleus defining the types of points and vectors, the scalar product and the linear combinations of vectors. This makes it possible to have an implementation which works whatever the dimension d. 
         [0152]    In the example described above, the subdomain f has been considered to be a triangle. However, the formulae given above are equally valid for any subdomain f i  for example an arbitrary polygon or any object of larger dimension, for example a tetrahedron (these formulae are therefore applicable in the case of a volume mesh). 
         [0153]    The use of the safety radius theorem for reducing the computations of a restricted Voronoi diagram or a restricted Delaunay triangulation has been described above within the context of an application to the mesh of an element. Of course, it can be involved in other fields which employ such computations, and can provide the same advantages. 
         [0154]    The same is true of the principles of computation of the vertices resulting from the intersections independently of the dimension d, and of the function orient. 
         [0155]    These features are very advantageous, for values of d equal to 2, 3 or greater than or equal to 4. 
         [0156]    The applications of a technique according to the invention other than meshing include, for example:
       applications in 3D reconstruction, especially the steps of passing from a scatter plot to a surface;   applications in robotics: for example in the representation of configuration spaces, or the management of fleets of autonomous robots or the planning of trajectories;   applications in astrophysics: for example computations in phase spaces;   applications in artificial intelligence, such as document searches (“google” type, which also uses spaces of large dimensions).