Abstract:
A method for searching for neighboring particles includes: setting neighbor target particles of a current particle to calculate mutual influences between the neighbor target particles and the current particle; selecting neighboring particles depending on a calculation result of the mutual influences to store indexes of the neighboring particles in the current particle; updating locations and information of the current particle based on power of the mutual influences and proceeding to a next time step; determining the neighboring particles selected at a previous time step as the neighbor target particles; and repeating above steps starting from said calculating mutual influences regarding the newly determined neighbor target particles.

Description:
CROSS-REFERENCE(S) TO RELATED APPLICATION(S) 
       [0001]    The present invention claims priority of Korean Patent Application No. 10-2010-0130303, filed on Dec. 17, 2010, which is incorporated herein by reference. 
       FIELD OF THE INVENTION 
       [0002]    The present invention relates to searching for a neighboring particle by using temporal continuity, and more particularly, to a method and apparatus for searching for neighboring particles by using temporal continuity, which are capable of quickly searching for neighboring particles in a particle-based physical simulation such as a fluid, a rigid body, a deformed body, or the like. 
       BACKGROUND OF THE INVENTION 
       [0003]    Recently, a method using a particle is frequently used in a computer simulation for reproducing a physical phenomenon such as a fluid, a rigid body, a deformed body, or the like. 
         [0004]    In the particle-based physical simulation, an object desired to be simulated is made into particles and movements of the particles are calculated while performing simulation by a very small period of time. The very small period of time is referred to as a time step. 
         [0005]    Further, in the particle-based physical simulation, mutual influences between freely moving particles are calculated, and for this, a scheme is necessary for quickly searching for neighboring particles located around a current particle. 
         [0006]    The scheme in the conventional art, which is shown in  FIG. 1 , is performed as follows: a space where a simulation is made is divided in advance; particles included in each area are searched at every time step to update information; and mutual influences between a current particle being calculated and particles included in an area adjacent to an area to which the current particle belongs are calculated in the simulation. 
         [0007]    Thus, it is required at every time step to search the entire particles and update information, and this leads to degradation of simulation performance. Such a scheme of updating information of particles included in each area at every time step has such a common problem, even if there is a difference in performance depending on a manner dividing a simulation space. 
       SUMMARY OF THE INVENTION 
       [0008]    In view of the above, the present invention provides a method and an apparatus for searching for neighboring particles, which enable quick search of neighboring particles by searching for particles located nearby in consideration of temporal continuity of movements of particles while a physical simulation is ongoing. 
         [0009]    In accordance with a first aspect of the present invention, there is provided a method for searching for neighboring particles, the method including: 
         [0010]    setting first neighbor target particles of a current particle to calculate first mutual influences between the first neighbor target particles and the current particle; 
         [0011]    selecting first neighboring particles among the first neighbor target particles depending on a result of the calculation of the first mutual influences to store indexes of the first neighboring particles in the current particle; 
         [0012]    updating locations and information of the current particle and the first neighbor target particles based on power of the first mutual influences and proceeding to a next time step; 
         [0013]    determining the first neighboring particles selected at a previous time step as second neighbor target particles to calculate second mutual influences between the second neighbor target particles and the current particle; 
         [0014]    selecting second neighboring particles among the second neighbor target particles depending on a result of the calculation of the second mutual influences to store indexes of the second neighboring particles in the current particle; and 
         [0015]    updating locations and information of the current particle and the second neighbor target particles based on power of the second mutual influences. 
         [0016]    In accordance with a second aspect of the present invention, there is provided a method for searching for a neighboring particle, the method including: 
         [0017]    setting first neighbor target particles of a current particle to calculate first mutual influences between the first neighbor target particles and the current particle; 
         [0018]    selecting first neighboring particles among the first neighbor target particles depending on a result of the calculation of the first mutual influences to store indexes of the first neighboring particles in the current particle; 
         [0019]    updating locations and information of the current particle and the first neighbor target particles based on power of the first mutual influences and proceeding to a next time step; and 
         [0020]    checking a neighbor searching setting condition indicating an expansion range of neighbor searching targets, 
         [0021]    wherein if a current neighbor searching corresponds to a primary setting within the neighbor searching setting condition, the method further comprises: 
         [0022]    determining, the first neighboring particles selected at a previous time step as second neighbor target particles to calculate second mutual influences between the second neighbor target particles and the current particle; 
         [0023]    selecting second neighboring particles among the second neighbor target particles depending on a result of the calculation of the second mutual influences to store indexes of the second neighboring particles in the current particle; and 
         [0024]    updating locations and information of the current particle and the second neighbor target particles based on power of the second mutual influences. 
         [0025]    In accordance with a third aspect of the present invention, there is provided an apparatus for searching for neighboring particles, the apparatus including: 
         [0026]    a neighbor searching unit for determining neighbor target particles of a current particle; 
         [0027]    a neighbor setting unit for setting neighboring particles based on a calculation result of mutual influences between the current particle and the neighbor target particles; 
         [0028]    a neighbor information storage unit for storing indexes of the set neighboring particles in current particles; and 
         [0029]    a particle location updating unit for updating locations and information of the current particle and the neighbor target particles based on power of the mutual influences. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0030]    The objects and features of the present invention will become apparent from the following description of embodiments, given in conjunction with the accompanying drawings, in which: 
           [0031]      FIG. 1  is a view showing an example of a method for searching for neighboring particles according to the prior art; 
           [0032]      FIG. 2  is a view showing an example of a method for searching for neighboring particles by using temporal continuity in accordance with an embodiment of the present invention; 
           [0033]      FIG. 3  illustrates a block diagram of an apparatus for searching for neighboring particles by using temporal continuity in accordance with the embodiment of the present invention; 
           [0034]      FIG. 4  illustrates a flow chart for explaining a first example of a method for searching for neighboring particles by using temporal continuity in accordance with the embodiment of the present invention; and 
           [0035]      FIG. 5  illustrates a flow chart for explaining a second example of a method for searching for neighboring particles by using temporal continuity in accordance with the embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
       [0036]    Hereinafter, embodiments of the present invention will be described in detail with the accompanying drawings. 
         [0037]      FIG. 2  is a view showing an example of a method for searching for neighboring particles by using temporal continuity in accordance with an embodiment of the present invention, wherein neighboring particles being targeted for calculating mutual influence are expanded. 
         [0038]    In a simulation using a computer, since stability of the simulation is degraded as a time step is large, a small time step is maintained, and a moving distance of particles calculated at each time step is limited accordingly. Thus, particles which are adjoining at a current time step are also highly likely to be neighbors each other at a next time step. 
         [0039]    Based on such characteristics, the present invention searches for neighboring particles at a next time step by using neighbor information at a previous time step. When neighbors of a particular particle are searched, first, neighboring particles which had adjoined the particular particle at a previous time step are taken as first targets and mutual influences between the first targets and the particular particle are calculated. As occasion demands, particles which had adjoined the neighboring particles at a further previous time step are taken as second targets and mutual influences between the second targets and the particular particle are calculated. Targets may be expanded in that manner, and the expansion range of targets may be designated by a user as necessary in order to enhance accuracy of the simulation calculation. 
         [0040]      FIG. 3  illustrates a block diagram of an apparatus for searching for neighboring particles by using temporal continuity in accordance with the embodiment of the present invention. 
         [0041]    Referring to  FIG. 3 , the apparatus  100  for searching for neighboring particles includes a neighbor searching unit  110 , a neighbor setting unit  120 , a neighbor information storage unit  130  and a particle location updating unit  140 . 
         [0042]    The neighbor searching unit  110  determines particles to be taken as targets of a neighbor of a current particle (hereinafter, referred to as neighbor target particles). In detail, the neighbor searching unit  110 , when there is no neighbor information of a previous time step or when a preset time has lapsed, first sets neighbor target particles by using a space division scheme or the like. Except the above case, the neighbor searching unit  110  determines neighboring particles selected at a previous time step as the neighbor target particles. If the expansion range of the targets has been designated as a primary range, the neighbor searching unit  110  may determine neighboring particles selected at a previous time step as the neighbor target particles. If the expansion range of the targets has been designated as a secondary or higher range, the neighbor searching unit  110  may determine neighboring particles selected at a previous time step of current neighboring particles, as the neighbor target particles. 
         [0043]    The neighbor setting unit  120  sets neighboring particles based on a calculation result of mutual influences between the current particle and the neighbor target particles. 
         [0044]    The neighbor information storage unit  130  stores indexes of the neighboring particles set by the neighbor setting unit  120  in the current particle. 
         [0045]    The particle location updating unit  140  updates, when the calculation of the mutual influences with respect to all the neighbor target particles is completed, locations and information of the current particle and the neighbor target particles based on the power of influences. 
         [0046]      FIG. 4  illustrates a flow chart for explaining a first example of a method for searching for neighboring particles by using temporal continuity in accordance with the embodiment of the present invention. 
         [0047]    Referring to  FIG. 4 , when a simulation starts, since there is no neighbor information of a previous time step, neighbor target particles of a current particle are first set by using a space division scheme, or the like in step S 201 . Thereafter, mutual influences between the neighbor target particles and the current particle are calculated in step S 203 . If the mutual influence calculation result meets a predetermined neighbor condition in step S 205 , namely, if any of the neighbor target particles are in a sufficiently adjacent location to the current particle, the any of the neighbor target particles are selected as neighboring particles and indexes thereof are stored in the current particle in step S 207 . 
         [0048]    When the calculation of mutual influences with respect to all the neighbor target particles is completed in step S 209 , locations and information of the current particle and the neighbor target particles are updated based on the power of influences in step S 211 . 
         [0049]    Next, in step S 213 , it is determined whether the simulation is completed or not. If the simulation needs to go on, it is determined in step S 215  whether a preset time has lapsed. If the preset time has not lapsed yet, the process goes to a next time step. 
         [0050]    Starting from a second time step, neighbors are expanded based on information of previously selected neighbors and mutual influences with regard to the expanded neighbors are calculated. Namely, the neighboring particles at the previous time step are set as the neighbor target particles in step S 217 , and steps S 203  to S 211  are again performed on the set neighbor target particles. 
         [0051]    Meanwhile, when neighbor information is lost like a case of a particle showing abnormally large movements by a strong power or a splash particle which is out of the surface of water in a fluid, the particle may be missing in a subsequent calculation. This problem may be solved by performing the initial neighbor setting process at preset time intervals. To this end, if it is determined in step S 215  that the preset time has lapsed while neighboring particles are being searched, the process returns to step S 201  to reset the neighbor target particles by using the space division scheme, or the like. 
         [0052]    This neighboring particle searching process is performed until the simulation is completed in step S 213 . 
         [0053]      FIG. 5  illustrates a flow chart for explaining a second example of a method for searching for neighboring particles by using temporal continuity in accordance with the embodiment of the present invention. 
         [0054]    In the second example, it is assumed that an expansion range of neighbor searching targets has been designated by a user. 
         [0055]    Referring to  FIG. 5 , when a simulation starts, since there is no neighbor information of a previous time step, neighbor target particles of a current particle are first set by using a space division scheme, or the like in step S 301 . Thereafter, mutual influences between the neighbor target particles and the current particle are calculated in step S 303 . If the mutual influence calculation result meets a predetermined neighbor condition in step S 305 , namely, if any of the neighbor target particles are in a sufficiently adjacent location to the current particle, the any of the neighbor target particles are selected as neighboring particles and indexes thereof are stored in the current particle in step S 307 . 
         [0056]    When the calculation of mutual influences with respect to all the neighbor target particles is completed in step S 309 , locations and information of the current particle and the neighbor target particles are updated based on the power of influences in step S 311 . 
         [0057]    Next, in step S 313 , it is determined whether the simulation is completed or not. If the simulation needs to go on, it is determined in step S 315  whether a preset time has lapsed. If the preset time has not lapsed yet, the process goes to a next time step. 
         [0058]    In the next time step, a neighbor searching setting condition is checked in step S 317 . The neighbor searching setting condition indicates an expansion range of neighbor searching targets and this determines the accuracy of simulation calculation. When the current neighbor searching corresponds to a primary setting in step S 319 , the neighboring particles at the previous time step are set as the neighbor target particles in step S 321 , likewise as in the first example described above, in order to calculate neighbors at a new time step by utilizing neighbor information at the previous time step. Thereafter, the process returns to step S 303  to calculate mutual influences with regard to the set neighbor target particles. 
         [0059]    Meanwhile, when it is determined in step S 315  that the preset time has lapsed while neighboring particles are being searched, the process returns to step S 301  to reset the neighbor target particles by using the space division scheme, or the like. In this wise, the problem of missing particles due to lost neighbor information can be solved, as described above. 
         [0060]    When the current neighbor searching corresponds to a secondary or higher setting within the neighbor searching setting condition in step S 319 , neighboring particles selected at a previous time step of current neighboring particles are set as the neighbor target particles in step S 323  and the process returns to step S 303 . 
         [0061]    The neighboring particle searching process is performed until the simulation is completed in step S 313 . 
         [0062]    In accordance with the embodiment of the present invention, the simulation performance can be remarkably improved by minimizing the time taken to search neighboring particles which is one of elements requiring much time in a particle-based physical simulation. Further, the accuracy of neighbor searching and the speed of simulation can be adjusted depending on a searching setting condition designated by a user. 
         [0063]    While the invention has been shown and described with respect to the embodiments, it will be understood by those skilled in the art that various changes and modification may be made without departing from the scope of the invention as defined in the following claims.