Abstract
Group animation is a technology that simulates group behavior by computer. It matures with the continuous development of computer graphics. The things that need to be described are expressed in the form of anime, which not only clearly reflects the process of the event, but also shows a more realistic picture, and can also increase the cognitive range of group behavior to a certain extent. Based on the analysis of the advantages and disadvantages of artificial fish swarm algorithm, this paper improves the research on artificial fish swarm algorithm, and it is easy to fall into local optimum, and it is improved by using convergence and divergence behavior in social learning mechanism., to some extent, improve the search performance of the algorithm. Based on the collision detection and avoidance, the improved artificial fish swarm algorithm is used to plan the group behavior path, and the obtained path data is imported into Maya. The tools provided by Maya will be used to establish the characters, 3D scenes and planning. The paths are merged together to get the corresponding group animation effects.
Introduction
The existence of some wonderful group behaviors such as the honey gathering of bee colonies, the migration of bird groups and the foraging of fish schools has made the use of computers to simulate these phenomena, which has become a field with good development prospects in virtual reality technology. To put it simply, group animation is a behavioral expression of a group of individuals with common attributes or characteristics, and an interpretation of the interaction between individuals and individuals in a group and between individuals and the environment. Group animation has become the research object of sociology, computer graphics and architecture with its unique charm. With the continuous improvement of people’s living standards, group animation is also widely used in intelligent environments, group public safety management, visual monitoring, and games and movie animation production [1].
Early anime was evolved from art films. It uses the visual persistence of the human eye, and by shooting and editing one by one, it will gradually change and can clearly reflect the still picture of the continuous dynamic process, and make it move through a certain playing system, that is, the traditional shooting method [11]. With the increasing complexity of group behavior and animation model production, neither the traditional animation production method nor the key frame-based technology can accomplish some specific tasks well and meet the expected requirements. The traditional animation production method is single, the task is large, and it wastes time and manpower [2]. At the same time, character modeling needs to be realized through imagination and creation, and the movement path and behavioral performance of the character require anime artists to consume a lot of time and energy, and the animation effect is not high enough to reflect the authenticity of the real world. To this end, the discovery and use of animation production methods that are relatively simple, efficient, and truly reflect the characteristics of the group have become the focus of many scholars. The group intelligent optimization algorithm is a kind of algorithm proposed by imitating the biological behavior of nature. Such algorithm has certain adaptive ability and intelligence, and can well represent the physical characteristics and social essence of the group. Therefore, the application of intelligent algorithms to group animation has gradually become a new research direction [14–20].
Artificial fish swarm algorithm
The artificial fish swarm algorithm (AFSA) is a group intelligent optimization algorithm proposed by Li Xiaolei and others inspired by the living habits of fish schools. It is based on the fact that in a water area, the place where the fish survives the most is usually the place with the most nutrients in the water, and the global search is achieved by imitating the fish, foraging, clustering and rear-end related behaviors [3]. AFSA has strong global search and fast-tracking change capability, strong robustness, simple and flexible, and is widely used in many fields.
In view of the basic behavioral characteristics of artificial fish, according to the nature of the problem sought, each artificial fish explores its current environmental conditions, and selects an act that optimizes the state of the artificial fish to perform the actual behavior. Finally, Artificial fish are concentrated around several local extremes, and the place where more artificial fish are gathered is generally the area with better value. Therefore, the global extremum can be further judged and obtained. The algorithm diagram of AFSA is shown in Fig. 1.
AFSA algorithm diagram.
Through the analysis of the basic theory of artificial fish swarm algorithm, it can be concluded that the artificial fish swarm algorithm has the following characteristics: 1) The algorithm does not require high initial value selection, and only uses the function value of the target problem, and the operation is simple and flexible. 2) Multiple artificial fish can be searched at the same time, with good parallel processing capability and improved speed of optimization. 3) The algorithm does not require high parameter setting and has a certain ability to quickly track changes. 4) The algorithm has a good ability to jump out of the local extremum and achieve global optimization.
The current state of a virtual artificial fish is X, and Visual is the position of the field of view X V is the position of the viewpoint at a certain time. If the state of the position is due to the current state, it is considered to go further to the current position, that is, to reach the state X next ; X V is not better than the current state, then continue to patrol other locations within the field of view. The more the number of patrols, the more comprehensive the understanding of the state of the field of view, and thus an all-dimensional stereoscopic perception of the surrounding environment, which helps to make corresponding judgments and decisions. Of course, it is not necessary to traverse the environment with multiple states and unlimited state, which allows the artificial fish to have a certain degree of uncertainty in local optimization, which is helpful for finding global optimality.
Where state X = (x1, x2, . . . , x
n
), state X
V
= (x1v, x2v, . . . , x
nv
), the process can be expressed as follows:
Where Rand () functions to produce a random number between 0 and 1; Step is the moving step size.
Since the number of companions in the environment is limited, the state of the companion (such as X1, X2, etc. in Fig. 1) is perceived in the field of view, and the state is adjusted accordingly, and the method is similar to the above formula.
The variable part includes the total number N of artificial fish, the state X = (x1, x2, . . . , x n ) of the artificial fish individual (where x i (i = 1, 2, . . . , n) is the variable to be optimized), the maximum step size of the artificial fish movement, the visual field of the artificial fish Visual, the number of attempts Try number, the crowding factor, and the artificial The distance d ij = |X i - X j | between fish individuals i, j.
The function part includes the food concentration A of the current position of the artificial fish (Y is the objective function value), various behavioral functions of the artificial fish (Prey (foraging behavior), Swarm, rear-end behavior Follow, random behavior Move and the behavior evaluation function Evaluate). Through this package, the state of the artificial fish can be perceived by other companions.
Foraging behavior
This is a basic behavior of artificial fish, that is, an activity that tends to food. It can generally be considered as the tendency to perceive the amount or concentration of food in the water through visual or taste, so the visual concept mentioned above can be Applied to the behavioral behavior description: Let the artificial fish i have a current state of Xi, and randomly select a state Xi within its sensing range.
Where Rand () is a random number between 0 and 1, if it is in the maximization problem, Yi < Y
j
, it goes further in that direction.
Conversely, the state X
j
is re-randomly selected to determine whether the forward condition is satisfied. After the Try number is repeated, if the forward condition is still not satisfied, the step is randomly moved.
In order to avoid the hazards to ensure the survival of the group, the fish will naturally gather together during the movement. Set the current state of the artificial fish to X
i
, and explore the number of partners n
f
and the center position X0 of d
ij
< Visual in the current field. If Yc/n
f
> δY
i
indicates that the partner center has more food and is less crowded, move further toward the partner center position.
The rear-end behavior is a behavior of chasing the adjacent artificial fish with the highest fitness. In the optimization algorithm, it can be understood as the process of advancing to the nearest optimal partner. Let the artificial fish i have a current state of Xi and explore the partner Xj whose maximum value is Yj among the partners in the current neighborhood d
ij
< Visual. If Yj/n
f
> δY
i
, indicating that the state of partner Xj has a higher food concentration and is less crowded around it, go further in the direction of Xj.
The artificial fish randomly selects a state within the field of view and moves in that direction.
On the basis of the above analysis, combined with the social learning mechanism, an improved artificial fish swarm algorithm (IAFSA) is obtained, which applies the convergence and divergence in the social learning mechanism to the AFSA. After quickly finding the local optimal domain, On the one hand, it tends to evolve toward the global optimal direction, and on the other hand, it uses the divergent behavior to move toward the optimal opposite direction to find other possible global optimal values to prevent local optimality. The improved algorithm flow is described as follows: Initialize the fish size Np and the initial position of each artificial fish, as well as the visual parameters Visual, the moving step, the congestion factor δ, the maximum number of trials try number, the maximum evolution algebra ITERMAX and the preset accuracy VTR; Selecting the optimal artificial fish state to be assigned to the bulletin board; Each artificial fish renews its state by foraging, clustering, rear-end and random behavior to form a new fish school; If the preset evolution algebra is reached, the optimal artificial fish state and the corresponding optimal value are updated on the bulletin board, and 5), otherwise 3); Evaluate all individuals in the population, find the optimal solution Xpbest
i
found by each individual so far, and record the best individual among all Xpbest
i
as Xgbest. Update the state of each body by the following formula (9) to generate the first iteration+1 generation population Xiter+1:
If the number of executions of the algorithm reaches the maximum evolution algebra ITERMAX or the optimal objective function value reaches the preset precision VTR, the algorithm ends, outputting Xgbest and its objective function value, otherwise, let iter = iter+1, go to 5).
Maya software introduction
Maya is a full-featured, uniquely crafted 3D animation software from the world’s three largest software development companies. It features an advanced model building system, perfect lighting, materials, rendering technology and vivid motion matching. It has become an important tool in many fields such as TV movie animation, company product display and game visual design. Many of the realistic images in The Lord of the Rings, which we are familiar with, are designed and produced by Maya. The Maya work interface is shown in Fig. 3 below:
Basic flow of fish school algorithm.
Maya work interface.
Maya’s operation is flexible, fast, scalable and adaptable, full-featured, efficient, with a user-friendly interface and rich visual effects, making it a top-level 3D model and animation production software. Maya has a high utilization of computer hardware, and has NURBS modeling capabilities and real professional material lighting effects that are rare in other software. It is a good choice to build 3D scenes with Maya, and introduces the main functions of Maya. It became necessary.
In the animation production process, modeling is the most basic element. Whether it is the establishment of a scene or the drawing of a character, it needs to be based on modeling. Different modeling software has its own modeling method. Maya software mainly includes three modeling methods: polygon modeling (Polygon), surface modeling (NURBS) and subdivision modeling (Subdivide) [4].
Polygon modeling (Polygon)
Polygon modeling is a relatively simple and widely used modeling method in Maya software. It uses polygons as the basic elements to construct a variety of 3D models. A polygon is a closed graph formed by a series of line segments connected in sequence. A polygon is mainly composed of vertices, edges, faces, and texture coordinates (UV). The vertex is the most basic element of the polygon, and it also affects the display result of the polygon model. When a certain vertex on the model is changed, the shape of the corresponding polygon model changes [5].
Surface modeling (NURBS)
Surface modeling, or NURBS modeling, is a popular modeling method in 3D animation software production, which is more suitable for the creation of smooth curved objects. Surface modeling begins with a curve that forms a surface, and then a series of surfaces combine to form a volume model. Among them, the curve is an important tool for the establishment of the NURBS model. The curve can be created directly from the point, or it can be operated by using the feature edge line existing in the software. NURBS curves mainly include CV Curve, EP Curve, Pencil Curve, Arc, and Text. The NURBS surface consists of a large number of curves and control points. The control points are used to control the curvature, direction position and length of the curve to change the shape of the curve to obtain the desired model display effect [6].
Subdivision modeling (Subdivide)
The subdivision surface has certain characteristics. It can be connected arbitrarily, and can be arbitrarily topologically or integrated. There is no need to worry about the continuity and seam on the surface. In addition, the subdivision surface only needs to be in the part. Subdivide the details to minimize unnecessary vertices in the model. The user can right-click on the subdivided object to switch between the element levels to implement the modification of the subdivided object.
3D scene construction
The construction of the scene requires a certain amount of life material and creative realization ability, which will affect the design, construction and final visual effects of the scene. The construction of 3D scenes is roughly through several steps such as model creation, texture mapping, lighting setup, and rendering. In this paper, a three-dimensional scene including buildings, flower beds, lawns, roads, etc. is constructed. The three-dimensional effect of the scene is shown in Fig. 5 below:
Simple polygon model.
3D scene sketch.
Establishment of the basic character model
The establishment of the basic character model is mainly done by using the ball B spline. The ball B-spline includes two parts: the ball B-spline curve and the curved surface. The ball B-spline curve and the surface contain two main operational elements of control vertices and control radii [7]. With the size of the control radius and the coordinates of the control points, the points on the surface of the solid can be obtained according to the given formula, and then the points are connected in turn to form a mesh model. At the same time, the model can be modified accordingly by changing the coordinates of the control point and the size of the control radius. The basic character model is built on the basis of the character skeleton, and the character model is automatically generated by performing corresponding operations on the basic skeleton using the ball B-spline. The specific implementation process is as follows: (1) The skeleton hierarchy is constructed according to the basic human skeleton standard. (2) Use the interpolation method to generate some control vertices on each bone segment to prepare for the ball B-spline construction. (3) Calculate the thickness of each of the four control points for the control vertices that have been interpolated, and then give four control radii according to the thickness data. (4) According to the existing control radius of various parts of the human body and the control vertices, the human body model represented by the ball B-spline is generated [8]. The generated human body model is shown in Fig. 6 below:
Human body model.
The generation of multiple characters is realized by controlling the structural lines of the basic character model, extracting the structural lines of the established human body parts, and recording the relevant position information of the structural lines and control points. Then through the three basic operations of selection, crossover and mutation in the genetic algorithm to change the parameter size of the structural line, the evolution and update of the character model is realized. The specific implementation process is as follows:
(1) Extract the structural line of the established basic character model, and adjust the structural line parameters of different parts to form the initial group. (2) The structure lines and control points of the basic parts such as the head, limbs, and upper body of the person are coded in a certain order. (3) Define the fitness function, and use the crossover and mutation operators in the genetic algorithm to update the structural line parameters of the corresponding parts of the human body. (4) Combine the newly obtained structural parameters of each part into a new structural line to obtain a new human body model.
Path planning
Path planning is an important part of group behavior animation production, and it is also an important factor to reflect the behavior of the whole group. Reasonable and effective path planning method cannot only make group behavior conform to the characteristics of real world, but also improve the efficiency of animation creation of the whole group. Path planning generally refers to finding a collision-free path from the initial state to the target state in an environment with obstacles according to certain evaluation criteria [9].
Whether an object in a virtual scene is in a stationary state or a moving state, there is a collision problem with the moving object. In order to make the virtual environment appear authentic, collision detection between objects in the environment is required. Collision detection is a necessary and classic research problem in the fields of computer graphics, three-dimensional animation simulation, etc., and has been widely concerned by many scholars. Collision detection can also be called contact detection or interference detection. It is used to judge whether there is a collision between objects in the virtual scene. Timely and effective collision detection plays a big role in improving the authenticity of the simulation system.
In order to improve the working efficiency and visual effect of the designed system, in view of the superiority of discrete-directional polyhedral bounding boxes (K-DOPs), the detection algorithm based on the discrete-directional polyhedron bounding box is used to detect the collision between two objects. The K-DOPs bounding box of an object is defined to contain the object, and the normal vectors of all its faces are from a convex hull of a fixed direction set (k vectors), and the intersection detection is completed by detecting whether the projection intervals overlap. If the projection intervals of two K-DOPs in a fixed direction set do not overlap, it means that the two K-DOPs do not intersect; if the two K-DOPs cannot exclude the overlap in all k-direction pairs, Explain that the two FDHs will collide and run the collision avoidance algorithm [10].
Group animation fusion results
A complete group animation generally includes three aspects: the scene, the character and the effect of the character in the scene. After the character and the scene are established, the corresponding group animation effect can be obtained by importing the path data of the character into the scene. MEL (Maya Embedded Language) is a powerful scripting language of Maya. It can be written as MEL script for some repetitive work. It can be used to directly control related features and work processes when authoring with Maya, saving A lot of manual labor to improve work efficiency. The MEL script editor is shown in Fig. 7 below:
MEL script editor.
Use the MEL scripting language that comes with Maya to import the resulting path data into the Maya scene, and then use the animation generation method provided by Maya to get the final group animation results. The animation effect of the resulting clustering behavior is shown in Fig. 8 below:
Clustering behavior map.
Aiming at the shortcomings of artificial fish swarm algorithm, such as poor search accuracy and easy to fall into local optimum, it is improved by chaotic pattern search. The improved algorithm improves the search precision, and the improved algorithm is applied in the path planning of group animation, which improves the group animation. The efficiency of path planning in behavioral production enhances the authenticity of the role movement and lays a good foundation for better research on group animation behavior.