Method for constructing data structure used for proximate particle search, program for the same, and storage medium for storing program

A method for constructing a data structure used in a proximate particle search that is used by a method executed by a stream processor (GPU:

• a graphics computation processor such as a graphics processing unit) for computing a simulation of a physical object by converting three-dimensional digital image data constructed from data arrays (GPU:
• image data) created in memory used by the processor (GPU:
• video memory) to two-dimensional digital image data, wherein:
• a technique is used for indicating the physical object as numerous particles and determining an existence state of the physical object on the basis of a storage positional relationship between the numerous particles in a three-dimensional image data structure in the memory (GPU:
• video memory);
• a bucket array (GPU:
• texture) included in the three-dimensional image data structure is composed of a bucket in which a memory space created in accordance with a space in which in the physical object occurs is divided, and a particle number assigned to the numerous particles is stored in each of numerous buckets;
• a writing step is provided in which a particle coordinate and the particle number of the particle stored in the bucket are read and written to an array in the memory using scattering operation of the stream processor (GPU:
• a two-dimensional image space using a vertex shader by the graphics computation processor);
• and
• the particle number and particle coordinate of each of the plurality of particles are written one at a time in a kernel (GPU:
• a rendering) for a plurality of cycles of processing in a single time step of a simulation when a plurality of the particles is present in the bucket in the writing step.