Abstract:
Two methods are provided for the automated derivation of Voronoi diagrams in 3D. The invention, implementable via various means such as a processing system, method, or data structure in a recording medium such as memory or as a self-contained electronic circuit, has wide ranging applicability to numerous fields such as big data analysis, computer graphics and animation, route planning, collision avoidance, computer vision, robotic vision, and etc. The first method of the invention details steps necessary to segment data according to a set of generators so as to produce a Voronoi partitioning of the data. The second method of the invention includes steps associated with the derivation of the mathematical specification of a 3D Voronoi diagram.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    Voronoi diagrams are a highly studied art due to their wide range of applicability to a diverse set of fields such as, but not limited to, molecular modeling, bio-informatics, robotic route planning, and computer graphics. The traditional Voronoi diagram V is defined as the partitioning of a plane P containing n points, or generators g, into n distinct polygons such that each polygon contains only a single generator g and that every point p inside of a polygon POLY is closer to the generator g for POLY than the generator g′ for some other polygon POLY′.  FIG. 1  shows a Voronoi diagram generated by a set of random points. In  FIG. 1, 1  is a generator for the Voronoi cell  2 . 
         [0002]    Despite the amount of research that has been performed in the art of Voronoi diagram construction, it is still difficult to automatically construct Voronoi diagrams for complex generators and higher dimensional spaces. For example, the automatic construction of a Voronoi diagram for a set of line segments in 3D is still considered an open problem. One of the reasons for this is that the definition of a Voronoi diagram must first be relaxed before generators that are more complicated than a point can be considered. For example, if we extend to concept of a Voronoi diagram in 3D from that which is constructed from a set of points to something that can be constructed for a set of lines then we immediately face the problem that the faces for our Voronoi diagram over lines in 3D are no longer planer, and in fact have a curved nature,  FIG. 2 . 
         [0003]    Various groups have tried to automatically generate Voronoi diagrams for line segments, some even in 3D; however, a casual inspection of the treatment of the line segment endpoints in these diagrams usually invalidates the claim that said generated diagrams are Voronoi diagrams. Similarly, Boada and his group created a method that approximates a Voronoi diagram for a variety of shapes, including line segments; however, a close inspection of the cells computed by Boada et. al.&#39;s method shows that the cells generated by said method in fact does not meet the requirements for a Voronoi cell. 
         [0004]    The deficiency of the methods presented in prior work is largely due to the relaxed treatment that said groups give to the definition of a Voronoi diagram. To some degree this is necessary. For example, while Voronoi diagrams for point sets in high dimensional space can be generalized via the use of polytopes instead of polygons, more complicated generators, such as line segments, do require a further generalization of our definition so as to accommodate curved faces  3 . However, Boada et. al. and Held et. al. generalize the definition of a Voronoi diagram to the extent that they now allow generators to be associated with multiple Voronoi cells, Voronoi cells to be associated with multiple generators, and Voronoi cells that contain points that are closer to an alternative generator g′ than the primary generator g. Clearly, this violates both the definition and spirit of a Voronoi diagram. For the methods presented here, we define a Voronoi diagram V to be a partitioning of a space, or data set, into a set C of cells C i , called Voronoi cells, based upon a set G of generators; such that every point pεC i  is closer to the generator i for C than any other generator j in G. In this definition, “closer” can be according to any distance measure. For example, but not limited to, one embodiment may use Euclidian distance to determine closeness; another embodiment might use the Manhattan distance; yet another method may use the Minkowski distance, and etc. 
         [0005]    It should also be noted that Kim et. al. devised a computationally intensive method for utilizing Voronoi diagrams of spheres and sphero-cylinders for the analysis of biomolecules. However, they do not claim that their novel method includes the methodologies for the construction of a Voronoi diagram; where the method that they presented in their patent includes the description of a method for the construction of a Voronoi diagram of spheres and sphero-cylinders.  FIG. 20  depicts two pairs of such sphero-cylinders. The first pair,  1000  and  1001 , are sphero-cylinders with non-zero radii. The second pair of sphero-cylinders,  1003  and  1004 , are sphero-cylinders with zero-valued radii. 
         [0006]    This construction of Voronoi diagrams of sphero-cylinders is related to the construction of Voronoi diagram for a set of line segments, or sphero-cylinders with zero-value radii,  1003  and  1004 ; however, the methodology developed by Kim et al does not present a method for handling the intersection of two sphero-cylinders, or potentially the intersection of two line segments, at an endpoint,  1005 . In fact, said method does not at all investigate or handle the intersections of complex generators. Since it is the intersection of generators that generally invalidates a proposed Voronoi diagram construction, Kim et. al. neglected to solve the most critical component of Voronoi diagram construction. For example, if a sphero-cylinder  1003  with radius equal to zero intersects another sphero-cylinder  1004  with radius equal to zero in such a way that one of the half-spheres for the first sphero-cylinder perfectly overlaps one of the half-spheres for the other sphero-cylinder  1005  then the method presented by Kim et. al. will not be able to discriminate between points,  1006  and  1007 , near said overlapping half-spheres that belong to the first sphero-cylinder,  1006  to  1003 , from points that belong to the second sphero-cylinder,  1007  to  1004 . 
       SUMMARY OF INVENTION 
       [0007]    This Summary is not intended to limit the scope of the claimed subject matter or identify key or essential features of the claimed subject matter. This Summary is only provides, in an abridged form, a selection of concepts that are further described in the Detailed Description. 
         [0008]    With the previous paragraph in mind, this disclosure details two novel methods for the derivation of Voronoi diagrams for a set of generators of arbitrary dimensionality and arbitrary complexity. The first novel method involves the construction of a Voronoi diagram via an intermediary mathematical game played over the input set of generators along with a finite input set of data values. This initial method is best suited for, but not limited to, applications where it is desirable to compute a mapping of a finite number of input data values to a finite number of input value-generator pairs (d,g); where such a pair would indicate that a given input d is closest to the given generator g. The second novel method involves the construction of a Voronoi diagram over an input set of generators alone. This second method is best suited for, but not limited to, applications where it is desirable to compute a set of equations that define the Voronoi diagram, and each component, or cell/Voronoi polygon, of the Voronoi diagram, so as to be able to arbitrarily select any given cell from the output and obtain a mathematical description for the selected cell. 
         [0009]    The construction of such Voronoi diagrams has a diverse set of applicable uses. Here, we will present one such use. Specifically, we will present the use of Voronoi diagram constructed via the first novel method for the purpose of automatically segmenting, rigging, and then subsequently animating an input model. This automatic-rigging use-case is in itself a novel method for automatic rigging. The embodiment of the use case presented here is in no way meant to limit the potential use, or application, for Voronoi diagrams constructed using the following methods. On the contrary, the vast number of uses is so numerous and diverse that it would be impractical to list all of such uses here. As such, the automatic rigging use case shown here is to be interpreted as a non-limiting, illustrative use case scenario. 
         [0010]    In addition to the novelty of the automatic-rigging method presented here, said method also utilizes a novel method for referencing the closeness of a point that participates in a joint to the remainder of the limb; or conversely, the center of the joint. This novel method for recording, referencing, or otherwise relating, a point in a model to the center of a joint is useful during the animation process for more fine controlled animations at the joints. 
         [0011]    The scope of this claim is not in any way intended to be limited according to the structure or format of the input data, or the medium for implementation of the methods presented here. The methods described here are typically, but not necessarily, implemented on a computational device of some manner that is capable of receiving, or loading, input data in such a manner as to enable the execution of the aforementioned methods. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]    Similarly numbered elements in the attached drawings correspond to one another. 
           [0013]      FIG. 1  depicts an example Voronoi diagram for a set of input point generators. 
           [0014]      FIG. 2  depicts an example curved-face  3  for two, adjoining Voronoi cells in a Voronoi diagram of two lines. The Voronoi Diagram in  FIG. 2  was computed for a unit cube; thereby truncating the lines,  4  and  5 , and face  3  at the boundaries for said unit cube. As such,  3 ,  4 , and  5  are to be interpreted as unbounded, and extending, beyond the unit cube, to an infinite length in a direction that is appropriate for the portions of  3 ,  4 , and  5  shown in  FIG. 2 . 
           [0015]      FIG. 3  depicts an example discrete, discontinuous data set. The data figure shown in  FIG. 3  was taken from the US Census Bureau&#39;s  2002  report on Global Population Growth. 
           [0016]      FIG. 4  depicts a high level perspective of the process for the first novel method,  30 , for creating a Voronoi diagram. 
           [0017]      FIG. 5  depicts a high level perspective of one possible process for generating a Voronoi diagram graphic from the partitioned data generated by the process presented in  FIG. 4 . 
           [0018]      FIG. 6  depicts a non-limiting example of a normal form game  100  and the associated extensive form  101  for  100 . 
           [0019]      FIG. 7  depicts a non-limiting example of a normal form  102  game specification for a Voronoi diagram defined over the finite data set {p} with respect to the set {i, j} of generators. 
           [0020]      FIG. 8  depicts some of the geometrical properties for a set S of generators containing line segments. 
           [0021]      FIG. 9  presents additional geometrical properties for a set S of generators containing line segments that can be used for an alternative generator intersection resolution method. 
           [0022]      FIG. 10  shows an example set S of line segment generators for a Voronoi diagram. 
           [0023]      FIG. 11  shows the Voronoi diagram computed for the set S of line segment generators from  FIG. 10 . 
           [0024]      FIG. 12  shows a Voronoi diagram computed for a set S of 25 random line segment generators using  30 . 
           [0025]      FIG. 13  shows a Voronoi diagram computed for a set S of 100 random line segment generators using  30 . 
           [0026]      FIG. 14  shows a Voronoi diagram computed for a set S of 250 random line segment generators using  30 . 
           [0027]      FIG. 15  details an example process by which a model is automatically rigged to an animation skeleton and then subsequently animated. 
           [0028]      FIG. 16  details a high level perspective of a novel method for the derivation of a Voronoi diagram over a generic set of generators. 
           [0029]      FIG. 17  details a high level perspective of a novel method for the derivation of a Voronoi diagram over a set of line segment generators. 
           [0030]      FIG. 18  shows four potential orientations for two line segments in three-dimensional space. 
           [0031]      FIG. 19  depicts the segmentation of thirteen separate models via the Voronoi induction method from  FIG. 4 . 
           [0032]      FIG. 20  depicts two pairs of overlapping sphero-cylinders, and two data values that are to be partitioned according to one of the pairs. The first pair has an associated non-zero radius for each sphero-cylinder. The second pair has a zero-valued radius for each sphero-cylinder. 
           [0033]      FIG. 21  depicts a method for automatically rigging an animation skeleton to a model. 
       
    
    
     DETAILED DESCRIPTION 
       [0034]    The presented disclosure is directed at the derivation of a Voronoi diagram, Voronoi-like diagram, Voronoi partitioning, and/or Voronoi-like partitioning of an input set of information, mathematical space, or information, which we will from hence forth on refer to as data, for the purpose of analyzing data, or data space, for the purpose of analyzing a space, so as to formulate conclusions, and/or predictions, with regards to the presented data, or data space. An example data space is a unit cube within which the Voronoi diagram was computed in  FIG. 2 . An example data set, or set of discrete information, is shown in  FIG. 3 . The data, data set, presented in  FIG. 2 ,  FIG. 3 , are meant to serve as a non-limiting example of a potential data space, data set. 
         [0035]      FIG. 4  depicts a high level perspective of the first method for the derivation of a Voronoi diagram over a data space or input data set.  30  is the high level method in  FIG. 4 . The method presented in  FIG. 4  is optimally applied to finite, discrete input data sets, but not limited in application to finite, discrete input data sets. If the input data set  10  is finite, then the method presented in  FIG. 4  can be said to induce a Voronoi partitioning of  10  according to the supplied set of generators  11 . If the input data set  10  is non-finite, or infinite, then the embodiment presented in  FIG. 4  can be said to induce a Voronoi partitioning of the data space for  10 , where the subsequent Voronoi diagram graphic, or visualization, can be generated as in the high level method presented in  FIG. 5 . 
         [0036]      10  and  11  in the embodiment shown in  FIG. 4  are the input data/data space/data set D and the input generator set S, respectively. The data in  10  can be any form of information, including the mathematical space over which S itself is defined. S is a set of generators g; where g is any, and not limited to, geometrical, or non-geometrical, object which can be related to D via mathematical means.  13  in  FIG. 4  utilizes a mathematical game to determine which generator g the input data value d is closest to; and therefore should be assigned. Step  14  in  FIG. 4  cycles back to Step  12  until all data values have been evaluated; upon which time the partitioned data is returned in Step  15 . Said partitioned data can then be passed to the method presented in  FIG. 5  to be subsequently converted into a Voronoi diagram. The process outlined in  FIG. 5  sequentially searches the data values partitioned in  13  to determine if two neighboring values are assigned to different generators. If they are, then we know that we have detected a face and pass said face-values to Step  22 . Step  22  collates the face-values and then tessellates, or simply passes the values, as in  FIG. 11 ,  FIG. 12 ,  FIG. 13 , and  FIG. 14 , in step  23  to a subsequent process in a format that is able to be rendered to an output device. The embodiment of the method in  FIG. 4  is not meant to be interpreted as limiting with regard to any reasonable modification of the method that still retains the key concepts presented in the method. For example, and equivalent, yet different embodiment for the method presented in  FIG. 4  would be to retrieve a set d of data values d in  12 , and independently, but concurrently assign each value d Ed to a generator in  13  instead of the sequential approach presented in  FIG. 4 . Another alternative embodiment would be to assign all data values concurrently. Alternatively, another embodiment may be to add values to a queue, and then continue with the data assignment process until the queue is empty. Again, another embodiment may be to just remove values from D for assignment until D is empty. 
         [0037]    The assignment performed in  13  is determined via the use of a mathematical game. Note: while the embodiment presented here utilizes a mathematical game, this is not meant to be limiting, and is to be interpreted as the use of any mathematical equivalent of a mathematical game. For example, another embodiment may be to use the linear programing equivalent of the game that is played during step  13 . We may refer to the mathematical game in  13  of  FIG. 4  henceforth as either mathematical game, normal form game, extensive form game, or just game; where the distinctions between normal form and extensive form games is apparent to anyone familiar to the art.  FIG. 6  demonstrates a non-limiting example of such a mathematical game for  13 . The game  100  in  FIG. 6  is the normal form of the classical prisoner&#39;s dilemma game: which is well known to anyone that is familiar with the art and discipline of game theory.  101  in  FIG. 6  is the extensive form of the same classical prisoner&#39;s dilemma game as in  100 . We can define both  100  and  101  according to the triple &lt;N, A, u&gt;: where N is the set of n players; A=A 1 × . . . ×A n , where A i  is the finite set of actions for player i; and u=(u 1 , . . . , u n ), where u i :A→R is the utility function. Where said mathematical definition of a triple for a mathematical game is common knowledge to those who are familiar with the art of game theory. Additionally, said mathematical definition for  100  and  101  is identical because both  100  and  101  are instances of the prisoner&#39;s dilemma problem; where the prisoner&#39;s dilemma problem is also known to those that are familiar with the art of game theory. 
         [0038]    A non-limiting example for the game played during the decision process of step  13  in  FIG. 5  is presented in  FIG. 7 . The mathematical definition for the game in  FIG. 7  can be regarded as the same as was stated for  100  and  101  with the exception that the actions will be the assignment of the input data point  107  to one of the line segments,  108  or  109 , in  103 , and with the exception that the utilities for said assignment-actions be based upon the utility of the available assignments. The embodiment presented in  FIG. 7  is only to be interpreted as one possible example for the game performed during  13 : and not in any way to be interpreted as limiting or exhaustive. For example, another embodiment could have ten points and one line segment. Another embodiment could have one thousand line segments and a million data points. Yet another embodiment could have one hundred thousand line segments and uncountably infinite data points: or be defined over a data space. 
         [0039]    In  FIGS. 7, 104 and 105  are the players i and j for the game  102 .  113  is the payoff, or utility, to players  104  and  105 .  106  is one possible action that may, but is not necessarily, performed by player  104 ; and where the action  106  is to be read as “assign input data point p to player j.” The action set A 1  for each player i for  102  is defined over the set of all data-value-player pairs; such as the data-value-player pair  106 .  103  is the non-limiting use case scenario over which  102  is defined.  110  is the set of generators S:={i, j}, where  108  is the generator i and  109  is the generator j. In the non-limiting embodiment presented in  FIG. 7 , both  108  and  109  are line segments such that  108  intersects  109  at a common endpoint, or bound.  107  is the input data value p that constitutes the entirety of the input data for the non-limiting embodiment presented in  103  in  FIG. 7 .  112  is the mathematical projection of  107  onto  109 .  111  is the mathematical projection of  107  onto  108 . The utilities,  113 ,  114 ,  115 , and  116 , for the actions for  102  are computed using a distance function d(i p); where i is a player, such as  104  or  105 , and p is an input data value, such as  107 . 
         [0040]    The distance function d(i,p) can be derived using any distance measure, such as, but not limited to, Euclidean distance, Manhattan distance, Minkowski distance, Chebyshev distance, Hamming distance, and Mahalanobis distance. In addition to a generic distance function, d(i,p) may, but does not necessarily, have generator specific logic. d(i,p) may, but does not necessarily, also have a set, or library, of decision process, functional methodologies, or computational process that are chosen from to respond to a varying number of generator types, varieties, or classifications. It is further possible that d(i,p) is itself the payoff for an encapsulated game that is played over a set of potential generators, or generator-generator interactions. Additionally, it is possible that d(i,p) is incorporated into the initial game structure  102  to form a more complicated game; such as, but not limited to, a Markov game or a Bayesian game. Note, the aforementioned description of d(i,p) in the embodiment presented here, as well as the subsequent examples for d(i,p), are in no way meant to be exhaustive or limiting with respect to the specification of d(i,p). 
         [0041]    As a non-limiting example, consider a set S, for example  110 , of line segments as the set of generators for a Voronoi diagram.  FIG. 8  demonstrates some of the relevant geometric properties for sets of generators defined over line segments, such as  110 . In  FIG. 8, 220  shows the relationship between the α-value,  207 , from the projective function for a data value, such as  107  in  FIG. 7 , onto a line segment, such as  108  in  FIG. 7 .  221  in  FIG. 8  shows the geometrical properties associated with a system of line segments that intersect at a common bound. 
         [0042]    In  FIG. 8, 200  is the line over which the line segment  201  is defined.  201  is bound by the endpoints {dot over (p)},  202 , and {umlaut over (p)},  203 .  204 ,  205 , and  206  are potential data values, where the dotted lines in  220  indicate the projection proj 200 { 204 | 205 | 206 } of the data values  204 ,  205 , and  206  onto the line  200 . α in  220  is the α-value associated with said projective function. One embodiment for such a projection can be defined as: 
         [0000]      proj i   p=p +α{dot over (()} {umlaut over (p)}−{dot over (p)} )
 
         [0000]    where α is defined as 
         [0000]    
       
         
           
             α 
             = 
             
               
                 
                   
                     ( 
                     
                       p 
                       - 
                       
                         p 
                         . 
                       
                     
                     ) 
                   
                   · 
                   
                     ( 
                     
                       
                         p 
                         ¨ 
                       
                       - 
                       
                         p 
                         . 
                       
                     
                     ) 
                   
                 
                 
                    
                   
                     
                       p 
                       ¨ 
                     
                     - 
                     
                       p 
                       . 
                     
                   
                    
                 
               
               . 
             
           
         
       
     
         [0000]    The embodiment of the projective function presented here is meant to be non-limiting. For example, an alternative embodiment could be the projection onto a plane. Yet another embodiment could be the projection onto the surface of a sphere, or a cube. An additional embodiment could be the projection onto a polytope. 
         [0043]      221  illustrates one possible, non-limiting method for determining which generator a data value should be assigned, or which generator a data value is “closest to,” for the scenario of two line segments intersecting at a common bound  210 . In  221 , j,  208 , and i,  209 , are the line segments that define the set S of generators for the to-be-derived Voronoi diagram V. Alternatively, we could interpret the line segments shown in the embodiment presented in  221  as a subset of the total set S of generators for V.  210 , {dot over (p)}, and  211 , {umlaut over (p)} are the bounds on the line segment  209 .  210  is also a common bound for  208  and  209 : meaning that  208  and  209  intersect at  210 .  213  is the hyperplane H that bisects the angle between  208  and  209 .  212 , p, is the data value that must be assigned to either  208  or  209  depending on whether  212  is “closer” to  208  or  209 .  214 , θ, is the angle between  209  and  213 .  215  is the angle between (p−{dot over (p)}) and  209 . By “angle between” we are to be understood as referring to the angle between H and the plane defined over the line that passes through the normal to the plane defined by  208  and  209  and the line that passes through  209 , or (p−{dot over (p)}), respectively. 
         [0044]    For the non-limiting example set S={i, j} of generators i and j from  103 , the utility function for  102  can be defined over the action profile a i :=(a i,p1 , . . . , a i,k ), where k=|a i |, for a given player, or generator, i as: 
         [0000]        u   i ( a   i )=Σ a     i,p     εa     i     u   i ( a   i,p )
 
         [0000]    where the sub-function u i (a i,p ) is defined as: 
         [0000]    
       
         
           
             
               
                 u 
                 i 
               
                
               
                 ( 
                 
                   a 
                   
                     i 
                     , 
                     p 
                   
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       1 
                     
                     
                       
                         
                           d 
                            
                           
                             ( 
                             
                               i 
                               , 
                               p 
                             
                             ) 
                           
                         
                         = 
                         
                           min 
                            
                           
                             { 
                             
                               
                                 d 
                                  
                                 
                                   ( 
                                   
                                     j 
                                     , 
                                     p 
                                   
                                   ) 
                                 
                               
                               | 
                               
                                 j 
                                 ∈ 
                                 S 
                               
                             
                             } 
                           
                         
                       
                     
                   
                   
                     
                       0 
                     
                     
                       otherwise 
                     
                   
                 
                 , 
               
             
           
         
       
     
         [0000]    and where d(i,p) is defined as: 
         [0000]    
       
         
           
             
               d 
                
               
                 ( 
                 
                   i 
                   , 
                   p 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                          
                         
                           p 
                           - 
                           
                             
                               proj 
                               i 
                             
                              
                             p 
                           
                         
                          
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           0 
                         
                         &lt; 
                         α 
                         &lt; 
                         1 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             p 
                             . 
                           
                         
                          
                         
                           ( 
                           
                             i 
                             , 
                             p 
                           
                           ) 
                         
                       
                     
                     
                       
                         α 
                         &lt; 
                         0 
                       
                     
                   
                   
                     
                       
                         
                           d 
                           
                             p 
                             ¨ 
                           
                         
                          
                         
                           ( 
                           
                             i 
                             , 
                             p 
                           
                           ) 
                         
                       
                     
                     
                       
                         α 
                         &gt; 
                         1 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0045]    Using the geometric properties presented in  221 , the sub-function d {dot over (p)} (i,p) is defined as: 
         [0000]    
       
         
           
             
               
                 d 
                 
                   p 
                   . 
                 
               
                
               
                 ( 
                 
                   i 
                   , 
                   p 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                          
                         
                           
                             p 
                             . 
                           
                           - 
                           p 
                         
                          
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             deg 
                              
                             
                               ( 
                               
                                 p 
                                 . 
                               
                               ) 
                             
                           
                         
                         = 
                         1 
                       
                     
                   
                   
                     
                       
                          
                         
                           
                             p 
                             . 
                           
                           - 
                           p 
                         
                          
                       
                     
                     
                       
                         
                           
                             deg 
                              
                             
                               ( 
                               
                                 p 
                                 . 
                               
                               ) 
                             
                           
                           &gt; 
                           1 
                         
                          
                         
                           
                             φ 
                              
                             
                               ( 
                               
                                 p 
                                 . 
                               
                               ) 
                             
                           
                           &lt; 
                           
                             θ 
                              
                             
                               ( 
                               
                                 p 
                                 . 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       ∞ 
                     
                     
                       otherwise 
                     
                   
                 
                 , 
               
             
           
         
       
     
         [0000]    where deg({dot over (p)}) is the number of generators that intersect at the point {dot over (p)}. d {umlaut over (p)} (i,p) is defined the same as d {dot over (p)} (i,p), but with respect to {umlaut over (p)} instead of {dot over (p)}, 
         [0000]    
       
         
           
             
               
                 d 
                 
                   p 
                   ¨ 
                 
               
                
               
                 ( 
                 
                   i 
                   , 
                   p 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                          
                         
                           
                             p 
                             ¨ 
                           
                           - 
                           p 
                         
                          
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             deg 
                              
                             
                               ( 
                               
                                 p 
                                 ¨ 
                               
                               ) 
                             
                           
                         
                         = 
                         1 
                       
                     
                   
                   
                     
                       
                          
                         
                           
                             p 
                             ¨ 
                           
                           - 
                           p 
                         
                          
                       
                     
                     
                       
                         
                           
                             deg 
                              
                             
                               ( 
                               
                                 p 
                                 ¨ 
                               
                               ) 
                             
                           
                           &gt; 
                           1 
                         
                          
                         
                           
                             φ 
                              
                             
                               ( 
                               
                                 p 
                                 ¨ 
                               
                               ) 
                             
                           
                           &lt; 
                           
                             θ 
                              
                             
                               ( 
                               
                                 p 
                                 ¨ 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       ∞ 
                     
                     
                       otherwise 
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    The embodiment presented in  221  is not to be interpreted as limiting. The method presented here is to be interpreted as any utilization of the geometrical properties presented in  221  for the purpose of segmentation. 
         [0046]    For example, an alternative embodiment of the sub-functions d {dot over (p)} (i,p) and d {umlaut over (p)} (i,p) can be defined utilizing the alternative interpretation, shown in  FIG. 9 , of the geometrical properties shown in  221 .  222  in  FIG. 9  presents the additional geometrical information which can be used to determine which generator,  231  or  232 , a data value  235  is “closest to” for the scenario where  231  and  232  intersect at a common bound  233 . In  FIG. 9, 237  indicates the projection of  235  onto the hyperplane  236  that bisects the angle between generators  231  and  232 , and  238  indicates the projection of  234  onto  236 . With this geometrical information, we can redefine d {dot over (p)} (i,p) and d {umlaut over (p)} (i,p) as: 
         [0000]    
       
         
           
             
               
                 d 
                 
                   p 
                   . 
                 
               
                
               
                 ( 
                 
                   i 
                   , 
                   p 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                          
                         
                           p 
                           - 
                           
                             p 
                             . 
                           
                         
                          
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             sign 
                              
                             
                               ( 
                               
                                 
                                   proj 
                                   H 
                                 
                                  
                                 p 
                               
                               ) 
                             
                           
                         
                         = 
                         
                           sign 
                            
                           
                             ( 
                             
                               
                                 proj 
                                 H 
                               
                                
                               
                                 p 
                                 ¨ 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       ∞ 
                     
                     
                       otherwise 
                     
                   
                 
                 , 
               
             
           
         
       
     
         [0000]    and d {umlaut over (p)} (i,p) can be defined as: 
         [0000]    
       
         
           
             
               
                 d 
                 
                   p 
                   ¨ 
                 
               
                
               
                 ( 
                 
                   i 
                   , 
                   p 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                          
                         
                           p 
                           - 
                           
                             p 
                             ¨ 
                           
                         
                          
                       
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             sign 
                              
                             
                               ( 
                               
                                 
                                   proj 
                                   H 
                                 
                                  
                                 p 
                               
                               ) 
                             
                           
                         
                         = 
                         
                           sign 
                            
                           
                             ( 
                             
                               
                                 proj 
                                 H 
                               
                                
                               
                                 p 
                                 . 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       ∞ 
                     
                     
                       otherwise 
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    Note that the definitions for d(i,j), d {dot over (p)} (i,p), and d {umlaut over (p)} (i,p) are non-limiting, and are only meant to be an explanatory example of the mathematical properties used during assignment in  13 , and as one particular, non-limiting, form of the functions d(i,j), d {dot over (p)} (i,p), and d {umlaut over (p)} (i,p) that are necessary to compute the Voronoi diagram for a general set of generators. It should also be noted that the example forms for the functions d(i,j), d {dot over (p)} (i,p), and d {umlaut over (p)} (i,p) presented here are use case specific to a set of line segment generators. This said, it should be evident to anyone familiar with the art that a prohibitively large set of varieties for the functions d(i,j), d {dot over (p)} (i,p), and d {umlaut over (p)} (i,p) will be necessary to fully accommodate here all geometric forms that may be used as generators. 
         [0047]      FIG. 11 ,  FIG. 12 ,  FIG. 13 , and  FIG. 14  show examples of Voronoi diagrams computed using a game, such as  102  in  FIG. 7 . The Voronoi diagram shown in  FIG. 11  was computed for the set S of generators { 300 ,  301 ,  302 ,  303 ,  304 ,  305 ,  306 } shown in  FIG. 10 .  FIG. 12  was generated with respect to a random set of 25 random line segments.  FIG. 13  was generated with respect to a random set of 100 random line segments.  FIG. 14  was generated with respect to a random set of 250 random line segments. The lengths of the line segments in  FIG. 12  were unrestricted. The lengths of the line segments in  FIG. 13  and  FIG. 14  were restricted to a maximum length of 2500 units. 
         [0048]    While the method presented in  FIG. 4 , which uses a game such as  102  in  FIG. 7  to compute the Voronoi diagram for an input data set, utilizes a brute force approach, there are applications for Voronoi diagrams that cannot avoid the runtime requirements for such a brute force approach. For example, the automatic rigging of a graphical model, or just model, to an animation skeleton, or skeleton, requires the visitation of each vertex in the model at least once, if for no other reason then, to assign a bone weight to each vertex, see  FIG. 15 .  FIG. 15  shows the process by which a Voronoi partitioning of an input model,  400 , can be utilized for the process of automatically rigging  400  to an input animation skeleton,  401 .  402  in  FIG. 15  shows the Voronoi partitioning of  401  based upon  400 ; where each bone in  400  is viewed as a separate generator for  402 .  403  is the final rigged model, where the joints for  400  are centered in the planes of separation between the two, or more, neighboring Voronoi cells in  402 .  404 ,  405 , and  406  represent three separate animations that are then subsequently applied to  403  via  400  using standard animation methods. Since a bone weight must be assigned to each vertex in  401  in order for  401  to be animated via  400  the brute force approach of the method presented in  FIG. 4  is only marginally more costly than the process of assigning a known set of bone weights to  401 . 
         [0049]    Note, the embodiment of the automatic rigging example presented in  FIG. 15  is a non-limiting example of an application for the method presented in  FIG. 4 .  FIG. 15  is to be understood as being presented for illustrative purposes only, and not as a totality of potential uses for the method presented in  FIG. 4 . The method for the automated rigging procedure demonstrated in  FIG. 15  is discussed in  FIG. 21 . 
         [0050]      FIG. 16  details a high level perspective of a novel method for the derivation of a Voronoi diagram over a set of generators, of any form, via the direct derivation of equations for the facial specification of the Voronoi diagram: where a Voronoi diagram is composed of a finite set of Voronoi cells, which are in turn composed of a finite set of faces. Note: the high level perspective, or embodiment, presented in  FIG. 16  is not intended to be interpreted as exclusive, strict, or rigid. Any practitioner in the art of algorithm design is familiar with the observation that most algorithms can be altered in many ways while still maintaining the functionality of the embodiment or implemented method. For example, another embodiment would be where  501  in  FIG. 16  is moved after  503  without affecting the intent, purpose, methodology, or outcome of the method presented in  FIG. 16 . As such, the method presented in  FIG. 16  is only to be presented as an outline of one possible implementation, or embodiment, for the method discussed. 
         [0051]    The input to the embodiment of the method presented in  FIG. 16  is a set S of generators for the to-be-generated Voronoi diagram. In  501 , the minimum distance between each pair (i,j) of generators if i,jεS is computed. It should be noted that any of a number of distance measures could be used in  501 ; including, but not limited to, Euclidean distance, Manhattan distance, or Hamming distance. This minimum distance can be derived utilizing any number of ways known to anyone familiar with the art. In Step  502  the generators in S are sorted so as to find a generator with an extreme value: such as, but not limited to, the generator i that has one of its endpoints being the farthest point in the +x direction. The generator i with an extrema from  502  is then selected in  503  and removed from S. In  504  the remaining generators in S are sorted according to their distance from i, as was computed in  501 . The nearest neighbor j from  501  is then removed from S in  505  and added to a neighbor buffer B. The plane of separation between i and j is then computed in  506  and added to a set V, that will eventually become the Voronoi diagram for S, as a face for V. 
         [0052]    In Step  507  the next closest neighbor k to i in S is checked to see if the plane p of separation between i and k contains a point closer to i than any of the points that participate in the current specification for the Voronoi cell c i  for i. If there does exist such a point then p is added to V as a new face for c i , and the current set of faces for c i  are updated to reflect any bounds that are introduced by the inclusion of p in c i . Next, k is removed from S and added to B. 
         [0053]    In Step  508 , the sorted list created in  504  is check to see if all generators lεS have been visited. If an unvisited generator k remains then we return to  507  and process k. If all neighbors have been visited, then we check to see if B is empty in  509 . If B is empty then we return the derived Voronoi diagram for S in  510 . If B is not empty then in  511  the nearest neighbor i is removed from the top of B and S is set to the union of S and B. i is then subsequently processed as before in Step  504 . 
         [0054]      FIG. 17  details a high level perspective of an application of the embodiment of the method in  FIG. 16  for the derivation of a Voronoi diagram over a set of line segment generators via the direct derivation of equations for the facial specification of the Voronoi diagram. Neither the embodiment in  FIG. 16  nor the embodiment in  FIG. 17  are intended to be limiting. Many minor modifications can be made to the method presented in  FIG. 16  and  FIG. 17  while still retaining the spirit and intent of said method. For example, the embodiment in  FIG. 17  is just a modification of the embodiment presented in  FIG. 16 . Similarly, and alternative embodiment could be constructed for spheres, or cylinders, or mixed generator sets of points, line segments, spheres, and etc. As such, the high level perspective presented in  FIG. 17  is not intended to be interpreted as exclusive, strict, or rigid. Any practitioner in the art of algorithm design is familiar with the observation that most algorithms can be altered in many ways while still maintaining the functionality of the implemented method. As such, the method presented in  FIG. 17  is only to be presented as an outline of one possible implementation for the method discussed. 
         [0055]    The input to the embodiment of the method presented in  FIG. 17  is a set S of line segments. In  601 , the minimum distance between each pair (i,j) of line segments i,jεS is computed. It should be noted that any of a number of distance measures could be used in  601 ; including, but not limited to, Euclidean distance, Manhattan distance, or Hamming distance. This minimum distance can be derived utilizing any number of ways known to anyone familiar with the art. In Step  602  the line segments in S are sorted so as to find a line segment with an extreme endpoint: such as, but not limited to, the line segment i that has one of its endpoints being the farthest point in the +x direction. The line segment i with an extreme endpoint from  602  is then selected in  603  and removed from S. In  604  the remaining line segments in S are sorted according to their distance from i, as was computed in  601 . The nearest neighbor j from  601  is then removed from S in  605  and added to a neighbor buffer B. The plane of separation between i and j is then computed in  606  and added to a set V, that will eventually become the Voronoi diagram for S, as a face for V. 
         [0056]    In Step  607  the next closest neighbor k to i in S is checked to see if the plane p of separation between i and k contains a point closer to i than any of the points that participate in the current specification for the Voronoi cell c i  for i. If there does exist such a point then p is added to V as a new face for c i , and the current set of faces for c i  are update to reflect any bounds that are introduced by the inclusion of p in c i . Next, k is removed from S and added to B. 
         [0057]    In Step  608  the sorted list created in  604  is check to see if all line segments lεS have been visited. If an unvisited line segment k remains then we return to  607  and process k. If all neighbors have been visited, then we check to see if B is empty in  609 . If B is empty then we return the derived Voronoi diagram for S in  610 . If B is not empty then in  611  the nearest neighbor i is removed from the top of B and S is set to the union of S and B. i is then subsequently processed as before in Step  604 . 
         [0058]    Note: the method presented in  FIG. 17  is to be interpreted as a non-limiting example of how the method presented in  FIG. 16  can be used to construct a Voronoi diagram. The line segment generators discussed in  FIG. 17  are only one of an infinite number of possible generator classes. As such, the line segment application in  FIG. 17  is to be viewed as only one possible version of the method presented in  FIG. 16 . 
         [0059]    The Voronoi face computed in the embodiment presented in  606  is based upon one of the four scenarios in  FIG. 18 . The first scenario,  740 , involves two line segments L 1  and L 2  such that no point pεL 1  is closer to all points in L 2  than any other point p′εî no point qεL 2  is closer to all points in L 1  than some other point q′εL 2 . The second scenario,  741 , involves two line segments L 1  and L 2  such that endpoint p 3  for L 2  is closer to all points pεL 1  than any other point p′εL 2 . The third scenario,  742 , involves two line segments L 1  and L 2  that intersect at a common bound  723 . The fourth, and final, scenario,  743 , involves two line segments such that endpoint p 2 εL 1  is closer to all off the points in L 2  than any other points pεL 1 ̂ endpoint p 3 εL 2  than all points L 1  than any other point p″εL 2 . 
         [0060]    For  740 ,  700  and  701  are the lines L 1  and L 2 .  702  and  703  are the endpoints p 1  and p 2  for L 1 .  704  and  705  are the endpoints p 3  and p 4  for L 2 .  706  is a point s that is equidistant to L 1  and L 2 .  707  is the perpendicular distance d 1  of  706  to  700 .  708  is the perpendicular distance d 2  of  706  to  701 . d 1 =d 2 . The equation for the plane of separation between  700  and  701  can be defined as: 
         [0000]        f   F ( s )=( s −proj L     1     s )·( s −proj L     1     s )−( s −proj L     2     s )·( s −proj L     2     s )=0.
 
         [0061]    For  741 ,  710  and  711  are the lines L 1  and L 2 .  712  and  713  are the endpoints p 1  and p 2  for L 1 .  714  and  715  are the endpoints p 3  and p 4  for L 2 .  716  is a point s that is equidistant to L 1  and L 2 .  717  is the perpendicular distance d 1  of  716  to  710 .  718  is the distance d 2  of  716  to  714 . d 1 =d 2 . The equation for the plane of separation between  710  and  711  can be defined as: 
         [0000]        f   F ( s )=( s −proj L     1     s )·( s −proj L     1     s )−( s−p   2 )·( s−p   2 )=0.
 
         [0062]    For  742 ,  720  and  721  are the lines L 1  and L 2 .  722  and  723  are the endpoints p 1  and p 2  for L 1 .  723  and  724  are the endpoints p 2  and p 3  for L 2 : where L 1  and L 2  intersect at, or share, the common endpoint  723 .  725  is a point s that is equidistant to L 1  and L 2 .  726  is the bisecting hyperplane H that separates the points p′ that belong to L 1  from the points p″ that belong to L 2 . The equation for the plane of separation between  720  and  721  can be defined as: 
         [0000]        f   F ( s )=(({right arrow over ( L   2 )}×{right arrow over ( L   1 )})×({right arrow over ( L   2 )}+{right arrow over ( L   1 )}))·( s−p   2 )=0,
 
         [0000]    where {right arrow over (L l )} the direction of the line segment L i  away from the point of intersection  723 . 
         [0063]    For  743 ,  730  and  731  are the lines L 1  and L 2 .  732  and  733  are the endpoints p 1  and p 2  for L 1 .  734  and  735  are the endpoints p 3  and p 4  for L 2 .  736  is a point s that is equidistant to L 1  and L 2 . The equation for the plane of separation between  730  and  731  can be defined as: 
         [0000]        f   F ( s )=( s·p   2 )·( s−p   2 )−( s−p   3 )·( s−p   3 )=0.
 
         [0064]    As a non-limiting example of the application of the four scenarios  740 ,  741 ,  742 , and  743 , the Voronoi diagram V in  FIG. 11  for the set S of generators in  FIG. 10  can be define using the equations for the four scenarios  740 ,  741 ,  742 , and  743  in  FIG. 18  as follows. Looking at the Voronoi cell for  300 , the back face for the Voronoi cell for  300  can be defined according to the equation: 
         [0000]        f   F     1   ( s )=( s −proj L     300     s )·( s −proj L     300     s )−( s −proj L     306     s )·( s −proj L     306     s )=0,
 
         [0000]    where 
         [0000]        f   F     1   ( s )≦( s −proj L     300     s )·( s −proj L     300     s )−( s−p   802 )−( s−p   802 ),
 
         [0000]        f   F     1   ( s )≧({right arrow over ( L   301 )}×{right arrow over ( L   300 )})×(({right arrow over ( L   301 )}×{right arrow over ( L   300 )})− p   800 )−(proj H   s−p   800 ),
 
         [0000]        f   F     1   ( s )≦( s−p   801 )·( s−p   801 )−( s−p   803 )·( s−p   803 ),
 
         [0000]        f   F     1   ( s )≧( s −proj L     300     s )·( s −proj L     300     s )−( s −proj L     304     s )·( s −proj L     304     s ).
 
         [0065]    The remainder of the faces for V can be defined similarly to F 1 . As a non-limiting example, the Voronoi cell for  300  can be defined as: 
         [0000]        C   300   =U   w   F     300     f   F     w   ( s ), 
         [0000]    or more generally; 
         [0000]        C   i   =U   w   F     i     f   F     w   ( s ), 
         [0000]    where F w εF i , and F i  is the set of faces for the generator i. The remainder of the cells for V can be defined similarly to C 300 . 
         [0066]    With the cells for V defined, V itself can be defined as: 
         [0000]        V=U   x   C   C   x , 
         [0000]    where C is the set of cells for V. 
         [0067]    The interior of a Voronoi cell C i,interior  can be defined as Ax=0, where A is the augmented matrix for the system of equations that define C i,interior . For example, we can define the interior of the Voronoi cell for  300  can be defined as: 
         [0000]        f   cell,i ( s )= s,    
         [0000]    where: 
         [0000]        f   cell,i ( s )&lt;( s −proj L     300     s )·( s −proj L     300     s )−( s −proj L     306     s )·( s −proj L     306     s )
 
         [0000]        f   cell,i ( s )&lt;( s −proj L     300     s )·( s −proj L     300     s )−( s−p   802 )·( s−p   802 ),
 
         [0000]        f   cell,i ( s )&lt;({right arrow over ( L   301 )}×{right arrow over ( L   300 )})×(({right arrow over ( L   301 )}×{right arrow over ( L   300 )})− p   800 )·(proj H   s−p   800 ),
 
         [0000]        f   cell,i ( s )&gt;( s−p   801 )·( s−p   801 )−( s−p   803 )·( s−p   803 ),
 
         [0000]        f   cell,i ( s )&gt;( s −proj L     300     s )·( s −proj L     300     s )−( s −proj L     304     s )·( s −proj L     304     s ).
 
         [0068]      FIG. 19  shows, as example of use, the results of using the method in  FIG. 4  to induce a Voronoi-base segmentation of a set { 900 ,  901 ,  902 ,  903 ,  904 ,  905 ,  906 ,  907 ,  908 ,  909 ,  910 ,  911 ,  912 } of thirteen models. After using the method presented in  FIG. 4  to segment the thirteen models in  FIG. 19 , all thirteen models were independently rig to the input skeleton S that was utilized as the set of generators for  11 . As discussed previously in this disclosure, the automatic rigging process utilized for the models in  FIG. 19  centered the joints for the input animation skeleton, used as the set of generators, in the Voronoi faces for neighboring Voronoi cells. 
         [0069]      FIG. 21  is a non-limiting example of an embodiment for a method for automatically rigging an animation skeleton to a model. It should be sufficiently clear to anyone familiar with the art that there are many modifications to the embodiment shown in  FIG. 21  that are still covered by the intent of the depiction shown in  FIG. 21 . For example, an alternative embodiment would be to simultaneously import multiple animation skeletons S α , from multiple sources, and autonomously rig them, in concurrent fashion, to multiple models. Another, potential embodiment would be to import a scene containing multiple models, and an animation library containing multiple animation skeletons, and then to use the method depicted in  FIG. 21  to autonomously rig each model in the scene based upon the most appropriate animation skeleton from the library. Yet another possible embodiment would be to use the method depicted in  FIG. 21  to autonomously rig an animation skeleton from an animation library to streaming data; potentially for the purpose of tracking and/or monitoring the behavior off an object in an observed real-world-scene. 
         [0070]    For the particular embodiment depicted in  FIG. 21, 1010  designates the application of an input animation skeleton; where said animation skeleton is to be understood as a potential set of generators for the subsequent Voronoi induction on the input model passed in  1011 .  1012  uses the animation skeleton from  1010  to induce a Voronoi partition of the model from  1011  via  30 . For the sake of relating the method in  FIG. 21  to the current state-of-the-art in the field of computer animation, but without limiting the scope or applicability of  1012  or intent behind the embodiment shown in  FIG. 21, 1012  can be viewed as skinning M from  1011  according to S from  1010 . In  1013 , the animation skeleton S from  1010  is then embedded in the newly partitioned model M. This embedding is done by centering the joints, which are equivalent to that depicted in  221  and  222 , in S in the faces associated with each joint for the pair of Voronoi cells associated with the bones that intersect at said joints. These faces can be regarded as the bounded regions of space defined over the hyperplane Hα,  213  and  236 , that bisect the intersecting endpoints, or joints α. This centering can be performed utilizing any number of methods. For example, the most natural method would be the average of all points pεM that lie in H α , for a joint p α . However, another embodiment might use the harmonic mean of all such points. Yet another embodiment could use the geometric mean. As such, the description of the joint-centering method presented here is not meant to be limiting in any way. The presented embodiment is only meant to serve as an example of one such possible embodiment for the proposed method. Lastly, the rigged model is returned in  1014 .