A Proximity Query Algorithm For Three-Dimensional DEM Based On Dynamic Octree

The granular materials (such as rock, coal, soil, sandy silt, agricultural products and fertilizer of particles, pills, etc.) exist everywhere in people's daily life and the process of industrial or agricultural production. During the process of agricultural production and grain processing, the mechanical function exists between grain particles and the interspace of grain particles and mechanical parts. In the industry of architecture, there is frictional function between sandy rock and ledges of machines. In the domain of medicine and chemistry, pills and containers also rub mutually. Therefor, the interaction between particles and interaction between particles and mechanical parts is a universal phenomenon. It induces the abrasion between mechanical parts and granular materials and consumption of energy. Whereas, through taking some proper measures, such as mechanical analysis methods, creating mechanical models, analyzing the actual situation and simulating the process of collision between particles and collision between particles and mechanical parts, the performance of mechanical parts can be estimated. By means of the result of estimation, the parameters of machines and the structures of mechanical parts can be optimized. Thereby, the mechanical performance of machines will be improved and the consumption of energy will be decreased. Traditional research patterns of mechanical parts are mainly as follows: Firstly, design the blueprint abide by sophisticated experiences, then do trials and correct errors repeatedly. This kind of iterative developing process based on experiences is time, resource and manpower consuming. But the research and development of Three-Dimensional DEM reformed this kind of traditional pattern of scientific research. By using this software, the working process of mechanical parts of machines could be simulated on a computer, then the performance of the mechanical parts can be assessed. In this way, the modification of mechanical parts can be controlled in the step of design and it can save lots of manpower, resources and energy consumption.The theory basis of the computational simulation software of Three-Dimensional DEM is DEM which is put forward by Cundall in the late 1970s. The basal idea is regarding the large scale of colonies of discrete particles as sets of particles which have given shapes and masses. After endowing the pairs of contacted particles and the pairs of contacted particle and boundary with a certain kind of model of mechanics and some given arguments in the model, the contacted function of pairs of contacted particles and pairs of contacted particle and boundary can be assessed, as well as the mechanical performance of mechanical parts and particles. The DEM obtains the velocity and displacement of each particle through the method of dynamic relaxation analysis, Newton's second laws of motion and iteration based on time steps. Thus it is specially adaptive for settling nonlinear problems. Even if using different contacted models, it can still analyze agglomeration of particles, the process of the unitary material being destroyed, multiphase flows, chemical reactions and the process of transmitting heat. By means of modifying the analytical models of DEM of particles and boundaries, contacted mechanical models and arguments, it can also analyze the contacted functions between different discrete materials and different boundaries and the effects it imposes on the motion of discrete materials. It is no other than these merits that make the theory of DEM become a universal method in the field of studying dynamic problems of discrete colony materials and play an vital role in the following fields. Lithology Engineering and Fluxion of Sand, Transportation, Mixture and Classification of Discrete Materials, Agglomeration and Movement of Particles, Mutual Movement between Soil and Mechanical Parts, Assembly of Chemical Procedure and Mine.The basis of this thesis is the fundamental computational theory of DEM, background of research, advanced experiences and the requirements of design of mechanical parts. It mainly focuses on the process of collision in three-dimensional DEM. Considering the situations that large scale of boundaries take part in the collision process, a new algorithm named"A Proximity query Algorithm for Three-Dimensional DEM Based on Dynamic Octree"is put forward. The previous proximity query algorithms mostly focused on particles and neglected the situations in which boundaries take part in the process of collision. Based on the algorithm of partitioning the computational space into uniform grids, the new algorithm can judge the spacial relations between every gird and particle. Through the process of positioning every particle into a proper grid, the algorithm realized the process of proximity query of particles. The process of proximity query of boundaries is by dint of the octree data structure. Through the process of constructing and searching the octree, every boundary can be positioned into a proper grid, so the process of proximity query of boundaries can be completed. The algorithm mainly focuses on several kinds of common boundaries (basic graphical element), such as sphere, disk plane, sectorial plane, cylinder and cone. Other complicated mechanical parts can always be assembled by these basic graphical elements.The proximity query process of boundaries are mainly as follows: At first, partition the analytical computational space to grids which are the smallest spacial unit and the foliage nodes of a octree. The nodes in the middle layers of the octree are all cubes which are assembled by basal grids. Through searching the octree by layer, we can gradually confirm the exact space which is occupied by a boundary, when search to the bottom layer of the octree, we ultimately realize the process of pitching the boundaries to grids. During the whole process, we shall use different computational methods depending on different graphical elements while determine the relations between different graphical elements and grids. Considering the boundaries comprising holes, troughs or slots, we can treat this kind of boundaries as integrated boundaries in order to simplify the process of proximity query of boundaries.The merits of this algorithm are:①The appearance of this algorithm changed the computation process of proximity query in the three-dimensional application of DEM. The computation process is changed into linear from nonlinear. Also, the complexity of the process of proximity query process of three-dimensional application of DEM is decreased from O(N2) to O(N).②We use the method of constructing a data structure of octree for graphical elements in order to assess the girds which are occupied by these graphical elements. Thereby, the proximity query process for boundaries is realized and the algorithm of collision detection is perfected.③The time consumption of computational process is shorted, moreover, the validity of computational process is improved.In this thesis, theoretical analysis and instantial verification are also supplied. After this step, the algorithm is realized by VC 6.0, and embedded into the three-dimensional application of DEM. Combined with the graphical library of OpenGL, the result of simulation of the algorithm can be demonstrated clearly. Setting the particle number existing in the system as 10000, the algorithm computed several boundaries. The former application and the optimized application (the application embedded with this algorithm) computed these boundaries for 3 times independently. Comparing the time consumption of the two applications, the efficiency of the algorithm is conformed. Through comparing the result of simulation of the two applications, the preciseness of the algorithm is validated.