# Crowd Motion Editing Based on Mesh Deformation

Authors: Yong Zhang; Xinyu Zhang; Tao Zhang; Baocai Yin
Journal: International Journal of Digital Multimedia Broadcasting
 (2020)

---

## Abstract

Computer simulation is a significant technology on making great scenes of crowd in the film industry. However, current animation making process of crowd motion requires large manual operations which are time-consuming and inconvenient. To solve the above problem, this paper presents an editing method on the basis of mesh deformation that can rapidly and intuitively edit crowd movement trajectories from the perspective of time and space. The method is applied to directly generate and adjust the crowd movement as well as avoid the crash between crowd and obstacles. As for collisions within the crowd that come along with path modification problem, a time-based solution is put forward to avoid this situation by retaining relative positions of individuals. Moreover, an experiment based on a real venue was performed and the result indicates that the proposed method can not only simplify the editing operations but also improve the efficiency of crowd motion editing.


---

## Body

## 1. Introduction

Computer simulation of crowd movement refers to setting up simulation models depending on crowd motion features in the reality, which means imitating the movement process of a bunch of people in the virtual environment. This technique is so useful that has been widely applied in the field of architecture, transportation safety, computer games, animation, and so on. In terms of film and television production, it can save time and massive money in making collective scenes that involved a large group of people, for instance, the battle scenes. Under the circumstance, it is meaningful to develop the production method of crowd animation, which would improve the productivity and make promotion to the animation industry.Up to now, the making process of crowd animation relies on quantity of manual operations and it is difficult to edit every individual manually in large-scale crowd motion, especially when one’s appearance time needs to be precise or the speed of a certain group of people has to change over time. In addition, the influence on crowd formation and speed brought by editing is hard to eliminate. When adjusting the pace or routes of a small part of people in the group, the speed of the whole crowd often changes in a mutation which looks strange for walking people. Besides, collision matters are likely to occur after editing crowd motion and improper solutions may cause extensive crash among virtual characters. According to previous studies, crowd behavior simulation under different circumstances has been widely researched, such as simulating the crowd rushing to exits in a closed room [1] and establishing an interactive simulation model to imitate human-like behaviors among people as well as their influence to the environment [2]. Furthermore, many researchers paid attention to the calculation efficiency and large-scale crowd visualization. Wong et al. improved a model by combining clustering and spring force to govern individual movement in the virtual environment [3]. With the broad application of neural network, motion rules can be learned from real data so that human walking can be simulated in higher speed [4]. In terms of crowd formation, Hughes [5] considered crowd as flow continuum and continuum models have been set up to capture key features of pedestrian flows [6]. Nevertheless, the editing of crowd animation during the simulation process has been rarely studied. Therefore, this paper is aimed at proposing a method to effectively edit the crowd motion.Inspired by the cage-based editing method by Kwon et al. [7], we adopt concave hull to encircle the crowd and adjust its motion as a whole, which was able to intuitively edit the crowd by dragging characters. Moreover, triangular mesh is used to establish topological relation among characters in the virtual population in order to maintain their relative positions. The modification process relies on the mesh deformation technique proposed by Liu et al. [8]. In addition, according to the editorial way mentioned by Kim et al. [9], this paper divide crowd movement into a spatial part and temporal part to adjust crowd formation and solve collision problems.There are three main contributions of this research:(i)
The proposed method can effectively edit the crowd motion both collectively and individually(ii)
The method is able to retain the formation of the crowd and the relative positions between characters. Moreover, the collision problems between characters/obstacles are handled(iii)
The method is suitable for simulating activities that needed fixed relationships among participants, such as the march-in ceremony and military review


## 2. Related Work

Crowd simulation technology mainly includes modeling and simulation of virtual people’s behaviors, group animation, and visualization of virtual crowd. Many researchers have explored the manners of virtual people. The seminal contribution to the simulation of crowd’s behaviors should be the work of Reynolds [10] in 1987. They thought flock behaviors were the dense interactions of the relatively simple manners of the individuals. In addition, a distributed model was set up to generate the simple individual behaviors and complex flock behaviors evolved from individual behaviors. Reeves [11] proposed a particle system which is a collection of minute particles, modeling irregular fuzzy object. Musse and Thalmann [12] presented a Vi-Crowd model, including a hierarchy of crowds, groups, and individuals. Each level of autonomy had its own behavioral rule, and the complex crowd behaviors were simulated by synthetic effects among all hierarchies, which took sociological aspects into consideration. On the basis of the above model, psychological effects were considered for crowd movement by Pelechano et al. [13]. Moreover, Chenney [14] described a method for representing and designing speed fields by using flow tiles, which realized the minimum impact from the mixture of social and psychological influences.In the field of group animation, which is a branch of crowd simulation, Ji et al. [15] carried out researches on the algorithm of group movement simulation and proposed a method for group calisthenics based on group events. Takahashi et al. [16] presented a spectral-based approach to control the temporal and spatial distribution of individuals by mapping the group formation into the rotation interpolation of Laplace matrix eigenbases. Kovar et al. [17] suggested a novel method based on motion graph which was automatically constructed, and walks can be built on the graph to generate motion. Interactive manipulation of multicharacter animation was initially proposed by Kwon et al. [18]. They used a graph structure to model the spatiotemporal group behaviors of the crowd and employed a mesh-editing algorithm to manipulate the animation interactively. Ulicny et al. [19] put forward the concept of crowdbrush that users could brush in three-dimensional scenes with a brush metaphor, and then the system would generate a crowd in the brushed place. Furthermore, different brush colors form distinct crowd behaviors. Allain et al. [20] applied constraints to control the crowd. Different from other methods, they divided the constraints into macroconstraints and microconstraints. Macroconstraints were used to constrain the macroscopic characteristics of the crowd, for example, the speed field; microconstraints were used to constrain the crowd speed, location, and so on.


## 3. Crowd Motion Editing Based on Mesh Deformation

Crowd scenes are commonly used in animation, but group motion is complicated and difficult to modify. For specific scenes that required large crowd, such us parade and mass choreography, if we could edit people’s movement in a straightforward way, what you see is what you get, it would be a useful method to simulate crowd animation. Therefore, this paper proposed a method that can intuitively edit group motion through mesh deformation, separating the crowd movement depending on spatial and temporal attributes. The method can be divided into three portions which are the establishment of representation model, the spatial track deformation, and the temporal track deformation.The overview of the editing model is shown in Figure1 that is organized by the crowd motion editing method and trajectory deformation model. In Figure 1(a), the lower left corner is the generation process of the spatial track that contributes to form the representation model above. The representation model demonstrates the trajectory situation of the crowd, which can be edited according to spatial and temporal attributes, connecting two methods on the right side of this part. The editing method applied on spatial trajectory calculates new routes of group motion through the trajectory deformation model presented on Figure 1(b), and so does the model apply on the temporal track editing method. Therefore, the trajectory deformation model maintains relative positions of individuals as well as plans new paths. Then, it returns the editing results to the crowd motion editing method and rebuilds the representation model.Figure 1
Architecture overview of the crowd motion editing model.


### 3.1. Representation Model of Temporal and Spatial Track

The path of a virtual character in the crowd simulation is a sequence of the motion clips arranged in a chronological order. In this thesis, the A∗ algorithm [21] is applied to calculate crowd tracks so that the motion clips can be formed by taking sample points on the tracks.As it is displayed in Figure2, every spatial track is composed of a two-dimensional set of points obtained by projecting the motion clips onto the ground. More specifically, consider P1,P2,P3,⋯,PN as the trajectories of the first person to the Nth one accordingly. The ith trace Pi is on behalf of a piecewise curve, and the collection of any point pji∈R2on this curve signifies a sequence of people’s positions in time order. The direction of a certain point pji on the track is represented by local coordinates: pj+1i−pj−1i and Rpj+1i−pj−1i, where R is a 2×2 rotation matrix of angle 90° [9].Figure 2
Crowd trajectories and sampling points.In terms of the temporal attribute of the virtual population shown in Figure3, regard T1,T2,T3,⋯,TN as the temporal tracks of the first N characters, respectively. Each track can be sampled and serialized into a set of one-dimensional points which show one-to-one correspondence to the points on the spatial track. Suppose tji as a point on the time series, then tj+1i−tji is the interval from point pji to pj+1i. Parameter tjiindicates the arrival time of the ith person in the jth place that is in accordance with point pji. By adjusting the time sequence of the crowd, their speed displaying on a part of the space tracks can be changed. As a result, the crowd is able to reach a specific position in a given time.Figure 3
Spatial track and temporal track of each character.


### 3.2. Spatial Track Deformation Model Based on Concave Hull

The model is built on the basis of concave hull that encircles the selected crowd’s space/time trajectories represented by Mean Value Coordinates (MVC) [22] with respect to the vertices in the hull (for details, refer to [22]). After generating the hull, Delaunay triangulation is performed to divide the area into numerous triangles and set up a triangular mesh. In consideration of keeping the relative positions among virtual population while editing, triangular meshes are used to establish the topological relationship. Therefore, the position of each individual is taken to form the vertices of the grid and mesh deformation with rigid characteristic [23] is applied to edit the crowd motion. After dragging a single vertex on the hull, the shape of the surrounding area is able to be modified through mesh deformation, changing the motion tracks of the crowd thereby.When the user drags a point on the hull without fixing other points, as is shown in Figure4, the deformation can be calculated by
(1)minvωD2ED+ωF2EFsubjecttoMv^=h,where M is the constraint matrix to remain the dragging point unchanged during the deformation process. ED represents the distortion energy which is used to measure the extent of the mesh deformation. Introduce as-rigid-as-possible deformation energy [23] as
(2)ED=∑t=1T∑i=02citp∧it−p∧i+1t−Rtpit−pi+1t2,where p^it and pit denote the ith vertex of the tth triangle after and before the deformation in the triangular mesh, respectively. Rt represents the rotation estimation matrix from the deformed triangles to the triangles before deformation. EF in the following function is aimed at adding the local effect of deformation:
(3)EF=CTv^−c2,where C is the coefficient matrix. The closer the other points are to the dragging one, the smaller their coefficients are and vice versa. c is the position vector of the vertex before the deformation in the triangular mesh. v^ is the vertex of the concave hull after deformation. Tis an m∗n matrix. m means the number of points on the tracks of the selected part with the addition of n—the vertexes of the concave hull. The first m−n rows of T are the MVC [9] of the points on each track; the last n rows with n columns of the matrix form the n∗n unit matrix:
(4)T=λ11λ21λ12λ22⋯λn1⋯λn2⋮⋮λ1kλ2k⋱⋮⋯λnk1001⋯0⋯00000⋱0⋯1,where k is the number of points on the tracks of the crowd.Figure 4
Dragging effect without fixed points.As for the computation of coefficient matrixC, breadth-first search algorithm in the graph theory is used, namely, considering the mesh as a directed graph. The traversal begins from the dragging vertex and then goes through every layer of points around it. According to the layer combined with the distance from the start point, coefficients can be calculated. The formula of calculating the coefficient is shown below:
(5)coefficienti=αdec−k+βc,where coefficienti is the parameter of the nonstarting node in the mesh; the coefficient of the starting node is 0. α and β are nonzero coefficients. c is the number of points in between the present vertex to the starting node. k is the threshold set in advance, and d is the distance covering from the current node to the starting one. It can be seen from Equation (5) that as c increases, d makes more influence on coefficienti.Based on the results of Equation (1), the closer the points are to the dragging vertex on the mesh, the greater the impact is; however, if the fixed point is far from the dragging vertex during the editing process, it may affect nothing to the points around the fixed point according to Equation (1). Nevertheless, often, it is the case that the mesh deformation is supposed to perform between the dragging point and the fixed point, as is presented in Figure 5. Therefore, Equation (6) is used to deal with the situation with the fixed point:
(6)minvωD2ED+ωS2ESsubjecttoMv^=h.Figure 5
Dragging effect with a fixed point.In order to expand the influence of the dragging point,ES is used to measure the distance variation among the vertexes of the concave hull, which is approximately presented by the change of the components on the X-axis and Y-axis:
(7)ES=Dv^−d2,where D is an n∗n matrix:
(8)D=1−10⋯001−1⋯0⋮⋮⋮⋱⋮100⋯−1After adjusting the tracks of the crowd by means of mesh deformation, the speed of some people in the crowd may become unnaturally fast and slow. This is because the distance between the sampling points on the character’s track varies sharply; however, the time interval between them has not changed. Equation (9) is displayed to solve this problem:
(9)min∆t′^∑i=1M∑j=1Npi,j+1′−pi,j′∆ti,j′−pi,j+1−pi,j∆ti,j2,where pi,j and pi,j′represent the points on the tracks of the crowd before and after the deformation, respectively. ∆t is the time interval between two points on the track before deformation.The solving process of the target equation is demonstrated in Algorithm1.Algorithm 1: Deformation solution process.
Precondition: the user input the threshold.(1) Initialize(i) Calculatecit in Equation (2), where cit is the ratio of the perimeter of the tth triangle to the ith side of this triangle.(ii) E1 =0. E2 =0. The number of iterations: iteration =0.(iii) The vertex of the hull is equal to it before calculation:v^=v.(iv) CalculateEVt of each triangle in the mesh:EVt=p0t−p1tp1t−p2tp2t−p0t.(2) Terminal condition of the algorithm: abs (E1 – E2) <= threshold && iteration >=2Calculation steps(i)While abs (E1 – E2) > threshold || iteration <2:(1) CalculateEV^t according to v^;(2) Compute the rotation estimation matrixRt in Equation (2) of each triangle in the mesh. Let Ct=c0t000c1t000c2t, s,v,d=svdEV∧t′∗Ct∗EVt, Rt=d∗s′;(3) According to the user's demand to solve the target Equation (1) or Equation (7)(4) Save the value of previous target equation. For E1 = E2, the calculation results assigned to E1;(5) Iteration = iteration + 1;end while


### 3.3. Temporal Track Deformation Model Based on Concave Hull

As users are able to drag points on the space track to manipulate crowd tracks, they can also operate the temporal track as well. When crowd tracks are discretely sampled, every sampling point on each track has a corresponding time node which indicates the moment that a character appears at this position. Therefore, it is not the only advantage for modifying the speed in a section of track after adjusting the time node; the time of occurrence at a certain place is also under control. When users drag the corresponding points on temporal tracks, the following equation is applied to adjust these points:(10)minu^ωD′2ED′+ωF′2EF′subjecttoMu^=hwhere ED′ represents the degree of temporal deformation, which is similar toED. EF′ controls the local variation traits of spatial deformation. u^ means the vertexes of the concave hull after deformation. The equation Mu^=h is used to ensure that the fixed points or the dragging points are not changed.
(11)ED′=Du^−d2,(12)EF′=Fu^−p2,where matrix Du^ is the difference vector of two adjacent time nodes and d is the default time interval vector. Fu^ and p denote the time node vector after and before the deformation separately.


## 3.1. Representation Model of Temporal and Spatial Track

The path of a virtual character in the crowd simulation is a sequence of the motion clips arranged in a chronological order. In this thesis, the A∗ algorithm [21] is applied to calculate crowd tracks so that the motion clips can be formed by taking sample points on the tracks.As it is displayed in Figure2, every spatial track is composed of a two-dimensional set of points obtained by projecting the motion clips onto the ground. More specifically, consider P1,P2,P3,⋯,PN as the trajectories of the first person to the Nth one accordingly. The ith trace Pi is on behalf of a piecewise curve, and the collection of any point pji∈R2on this curve signifies a sequence of people’s positions in time order. The direction of a certain point pji on the track is represented by local coordinates: pj+1i−pj−1i and Rpj+1i−pj−1i, where R is a 2×2 rotation matrix of angle 90° [9].Figure 2
Crowd trajectories and sampling points.In terms of the temporal attribute of the virtual population shown in Figure3, regard T1,T2,T3,⋯,TN as the temporal tracks of the first N characters, respectively. Each track can be sampled and serialized into a set of one-dimensional points which show one-to-one correspondence to the points on the spatial track. Suppose tji as a point on the time series, then tj+1i−tji is the interval from point pji to pj+1i. Parameter tjiindicates the arrival time of the ith person in the jth place that is in accordance with point pji. By adjusting the time sequence of the crowd, their speed displaying on a part of the space tracks can be changed. As a result, the crowd is able to reach a specific position in a given time.Figure 3
Spatial track and temporal track of each character.


## 3.2. Spatial Track Deformation Model Based on Concave Hull

The model is built on the basis of concave hull that encircles the selected crowd’s space/time trajectories represented by Mean Value Coordinates (MVC) [22] with respect to the vertices in the hull (for details, refer to [22]). After generating the hull, Delaunay triangulation is performed to divide the area into numerous triangles and set up a triangular mesh. In consideration of keeping the relative positions among virtual population while editing, triangular meshes are used to establish the topological relationship. Therefore, the position of each individual is taken to form the vertices of the grid and mesh deformation with rigid characteristic [23] is applied to edit the crowd motion. After dragging a single vertex on the hull, the shape of the surrounding area is able to be modified through mesh deformation, changing the motion tracks of the crowd thereby.When the user drags a point on the hull without fixing other points, as is shown in Figure4, the deformation can be calculated by
(1)minvωD2ED+ωF2EFsubjecttoMv^=h,where M is the constraint matrix to remain the dragging point unchanged during the deformation process. ED represents the distortion energy which is used to measure the extent of the mesh deformation. Introduce as-rigid-as-possible deformation energy [23] as
(2)ED=∑t=1T∑i=02citp∧it−p∧i+1t−Rtpit−pi+1t2,where p^it and pit denote the ith vertex of the tth triangle after and before the deformation in the triangular mesh, respectively. Rt represents the rotation estimation matrix from the deformed triangles to the triangles before deformation. EF in the following function is aimed at adding the local effect of deformation:
(3)EF=CTv^−c2,where C is the coefficient matrix. The closer the other points are to the dragging one, the smaller their coefficients are and vice versa. c is the position vector of the vertex before the deformation in the triangular mesh. v^ is the vertex of the concave hull after deformation. Tis an m∗n matrix. m means the number of points on the tracks of the selected part with the addition of n—the vertexes of the concave hull. The first m−n rows of T are the MVC [9] of the points on each track; the last n rows with n columns of the matrix form the n∗n unit matrix:
(4)T=λ11λ21λ12λ22⋯λn1⋯λn2⋮⋮λ1kλ2k⋱⋮⋯λnk1001⋯0⋯00000⋱0⋯1,where k is the number of points on the tracks of the crowd.Figure 4
Dragging effect without fixed points.As for the computation of coefficient matrixC, breadth-first search algorithm in the graph theory is used, namely, considering the mesh as a directed graph. The traversal begins from the dragging vertex and then goes through every layer of points around it. According to the layer combined with the distance from the start point, coefficients can be calculated. The formula of calculating the coefficient is shown below:
(5)coefficienti=αdec−k+βc,where coefficienti is the parameter of the nonstarting node in the mesh; the coefficient of the starting node is 0. α and β are nonzero coefficients. c is the number of points in between the present vertex to the starting node. k is the threshold set in advance, and d is the distance covering from the current node to the starting one. It can be seen from Equation (5) that as c increases, d makes more influence on coefficienti.Based on the results of Equation (1), the closer the points are to the dragging vertex on the mesh, the greater the impact is; however, if the fixed point is far from the dragging vertex during the editing process, it may affect nothing to the points around the fixed point according to Equation (1). Nevertheless, often, it is the case that the mesh deformation is supposed to perform between the dragging point and the fixed point, as is presented in Figure 5. Therefore, Equation (6) is used to deal with the situation with the fixed point:
(6)minvωD2ED+ωS2ESsubjecttoMv^=h.Figure 5
Dragging effect with a fixed point.In order to expand the influence of the dragging point,ES is used to measure the distance variation among the vertexes of the concave hull, which is approximately presented by the change of the components on the X-axis and Y-axis:
(7)ES=Dv^−d2,where D is an n∗n matrix:
(8)D=1−10⋯001−1⋯0⋮⋮⋮⋱⋮100⋯−1After adjusting the tracks of the crowd by means of mesh deformation, the speed of some people in the crowd may become unnaturally fast and slow. This is because the distance between the sampling points on the character’s track varies sharply; however, the time interval between them has not changed. Equation (9) is displayed to solve this problem:
(9)min∆t′^∑i=1M∑j=1Npi,j+1′−pi,j′∆ti,j′−pi,j+1−pi,j∆ti,j2,where pi,j and pi,j′represent the points on the tracks of the crowd before and after the deformation, respectively. ∆t is the time interval between two points on the track before deformation.The solving process of the target equation is demonstrated in Algorithm1.Algorithm 1: Deformation solution process.
Precondition: the user input the threshold.(1) Initialize(i) Calculatecit in Equation (2), where cit is the ratio of the perimeter of the tth triangle to the ith side of this triangle.(ii) E1 =0. E2 =0. The number of iterations: iteration =0.(iii) The vertex of the hull is equal to it before calculation:v^=v.(iv) CalculateEVt of each triangle in the mesh:EVt=p0t−p1tp1t−p2tp2t−p0t.(2) Terminal condition of the algorithm: abs (E1 – E2) <= threshold && iteration >=2Calculation steps(i)While abs (E1 – E2) > threshold || iteration <2:(1) CalculateEV^t according to v^;(2) Compute the rotation estimation matrixRt in Equation (2) of each triangle in the mesh. Let Ct=c0t000c1t000c2t, s,v,d=svdEV∧t′∗Ct∗EVt, Rt=d∗s′;(3) According to the user's demand to solve the target Equation (1) or Equation (7)(4) Save the value of previous target equation. For E1 = E2, the calculation results assigned to E1;(5) Iteration = iteration + 1;end while


## 3.3. Temporal Track Deformation Model Based on Concave Hull

As users are able to drag points on the space track to manipulate crowd tracks, they can also operate the temporal track as well. When crowd tracks are discretely sampled, every sampling point on each track has a corresponding time node which indicates the moment that a character appears at this position. Therefore, it is not the only advantage for modifying the speed in a section of track after adjusting the time node; the time of occurrence at a certain place is also under control. When users drag the corresponding points on temporal tracks, the following equation is applied to adjust these points:(10)minu^ωD′2ED′+ωF′2EF′subjecttoMu^=hwhere ED′ represents the degree of temporal deformation, which is similar toED. EF′ controls the local variation traits of spatial deformation. u^ means the vertexes of the concave hull after deformation. The equation Mu^=h is used to ensure that the fixed points or the dragging points are not changed.
(11)ED′=Du^−d2,(12)EF′=Fu^−p2,where matrix Du^ is the difference vector of two adjacent time nodes and d is the default time interval vector. Fu^ and p denote the time node vector after and before the deformation separately.


## 4. Collision Avoidance Method Based on Space-Time Trajectory Deformation

During the process of crowd motion editing at present, the movement tracks are manually set. However, because of the huge amount of virtual characters involved with complicated routes, it is hard to notice the collisions among the crowd, let alone avoiding the crash by manual adjustment. Thus, collision detection algorithm and collision avoidance algorithm are indispensable, which make a great difference to the crowd animation quality. Therefore, we put up the measures of avoiding the collisions between characters/obstacles.


### 4.1. Collision Avoidance Method among People Based on Space Track Keeping

In view of collision avoidance among characters in the crowd, a method based on space track keeping is proposed—that is, to adjust the time tracks of related people to stagger the collision points. The strategy is shown in Figure6.Figure 6
The collision avoidance strategy based on space track keeping.


#### 4.1.1. Collision Detection

The collision problem of theith character is detected by whether the minimum distances between the ith track and other tracks in the same section are less than the threshold.d in Equation (13) displays the nearest distance between individual i and j:
(13)d=pki+vkit′−pmj−vmjt′2.In order to gain the relevant time information, taked2’s partial with respect to t′ after getting d:
(14)∂d2∂t′=2vki−vmjpki+vkit′−pmj−vmjt′,and then, make ∂d2/∂t′=0 to solve t′. The result is presented in Equations (15) and (16):
(15)t′=pki−pmjvki−vmj,vki≠vmj,(16)t′=0,vki=vki,(17)t=l1,t′+l1<l1t′,l1<t′+l1<l2,l2,t′+l1>l2,where t is the time that two individuals get the shortest distance in different situations. In combination with t′, d, and the speed mentioned in the above functions, the spatial position of collision can be presented, respectively, as pki+t−tki∗vki and pmj+t−tmj∗vmj.The specific algorithm is shown in Algorithm2.Algorithm 2: Collision detection.
(1) Judge whether the tracks of theith and the jth character, which are tki,tk+1i and tmj,tm+1j separately, have intersections.(2) If there is no intersection, turn to Step 5. Or turn to Step 3.(3) Gain the intersectionl1,l2 and use Equation (13) to find the nearest distance between two persons in l1,l2.(4) If the distance is less than the threshold, jump to Step 6.(5)k=k+1. If k is less than the total number of the track sections of the ith pedestrian, turn to Step 1, otherwise turn to Step 7.(6) Record the characters who are going to collide and the corresponding position. Then jump to Step 8.(7)m=m+1. k=0. If m is less than the total number of the track sections of the jth pedestrian, turn to Step 1.(8) end


#### 4.1.2. Collision Avoidance

The space-time trajectory is the combination of the spatial track and the time track. It can be regarded as a polyline in a three-dimensional space, comprising the spatial position coordinates of the character and the timeline. When the collision occurred, the minimum distance of two segments of the broken lines in this three-dimensional space is less than the threshold. Therefore, enlarging the distance over the threshold is able to prevent the collision.It is illustrated in Figure7 that adjusting the time track can affect the character’s three-dimensional trajectory to change the minimum distance between two lines. The distance, therefore, becomes greater than the threshold with no need to change their spatial locations. This method is suitable for scenes with complex terrain and large crowd density, because it can avoid the collisions in the crowd without worrying about colliding obstacles in the environment.Figure 7
The time of collision avoidance.In order to achieve the above purpose, the scaling factorS and translation coefficient T of time sequence are defined. When characters i and j have a crash, suppose that the crash moment is in the period tki,tk+1i and tmj,tm+1j for two pedestrians separately. After the scaling translation with S and T, the time periods turn to tki∗ai+bi,tk+1i∗ai+bi and tmj∗aj+bj,tm+1j∗aj+bj, respectively. Therefore, the collision can be prevented if previous time periods are replaced with the changed one.The scaling factor and the translation coefficient can be found according to Equation (19), while Equation (18) measures the change of the time before and after the adjustment.
(18)ET=SiTki−tki2+SiTk+1i−tki2+SjTmj−tmj2+SjTm+1j−tm+1j2,(19)fSi,Sj=minSi,SjETdt=distancei,j/vsubjecttog1Si,Sj=ai≥a,g2Si,Sj=aj≥a,g3Si,Sj=SiTki≥0,g4Si,Sj=SiTmj≥0,g5Si,Sj=SiT−SjT2≥dt2dt=distancei,j/v, where Si=aibiT, Tki=tki1, and T=t−l11. dt is the time interval between character i andj, which is estimated as follows:
(20)v=minvi,vjvi,vjdt=distancei,j/v,(21)distancei,j=Dthreshold−pki+t−tki∗vki−pmj−t−tmj∗vmj,(22)dt=distancei,j/v,whereDthreshold means the closest distance between two pedestrians. If the distance between two lines is less thanDthreshold, the collision will happen.Equation (19) is solved on the basis of the Kuhn-Tucker condition, that is, calculating the gradient of ,fSi,Sj, g2Si,Sj, g3Si,Sj, g4Si,Sj, and g5Si,Sj, respectively, to find Si¯ and Sj¯ satisfying Equation (23). The time nodes after adjustment aret¯ki=Si¯Tki, t¯k+1i=Si¯Tk+1i, t¯mj=Sj¯Tmi, t¯m+1j=Sj¯Tm+1j.
(23)∇fSi¯,Sj¯−∑i=15ωi∇giSi¯,Sj¯=0,ωigiSi¯,Sj¯=0,i=1,⋯,5,ωi≥0,i=1,⋯,5.After calculating the related time nodes, it is necessary to adjust the overall time series of the two characters in order to ensure that their speeds do not suddenly become very fast or slow. Considering that the change in speed is continuous, so the time people spent in per unit length is similar, expressed byEDT:
(24)EDT=∑i=1m−1∆ti+1li+1−∆tili2,whereli is the length of the ith segment on the pedestrian track and ∆ti is the time interval of the ith segment.In view of the similarity it should have between the speed before and after,EV is introduced to measure the degree of the speed change as shown in Equation (25). Nevertheless, the time node of the crowd is the only alteration during the whole process of collision avoidance, and therefore, the speed variation can be substituted by time information. Hence, ET is defined to represent the modification on time as well as on speed for the replacement of EV.
(25)EV=∑i=0mv¯i−vi2,(26)ET=∑i=0m∆t¯i−∆ti2,where ∆t¯i is the modified time interval. In the whole changing process, the adjustment of time node is hoped to be as little as possible. As a result, ETP is going to measure the degree of the change of time node as described in
(27)ETP=∑i=0nt¯i−ti2.Associating with Equations (24), (26), and (27), the avoidance method can be demonstrated by an optimization model, as shown in
(28)mint¯α2EDT+β2ET+γ2ETPsubjecttoMS∗t¯=mt,where α,β, and γ are the weight coefficients of EDT, ET, and ETP, respectively. The function of the matrix MS is to filter out the time nodes adjusted by Equation (18), while mt is a column vector consisting of the values of modified time nodes. The purpose of the constraint equation is to keep the time points that have been changed in the collision avoidance process away from changing again when the whole time track is later modified.The specific algorithm of collision avoidance method is shown in Algorithm3.Algorithm 3: Time trajectory deformation algorithm.
Comment:dthreshold is the threshold that users input.(1) Collision detection algorithm is used for any two virtual charactersi and j in the crowd. If no collision happens, end the algorithm; otherwise record the number of the accident segment k and m as well as the closest distance dmin;(2) Solve Equation (20) to estimate the time intervaldt;(3) Use Equations (19) to adjust the kth section of character i and the mth section of character j;(4) Use Equation (28) to adjust the whole time series of character i and j;(5) Jump to Step 1.


### 4.2. Obstacle Avoidance Method Based on Spatial Track Deformation Model

When the crowd pass through a narrow channel as displayed in Figure8, it is easy to collide with obstacles. It is very tedious for animators to manually manipulate virtual characters avoiding obstacles, which consumes a lot of time. The reason of the crash is when the crowd turn at a narrow junction, the maximum width of the crowd is bigger than the width of the intersection, as shown in Figure 9.Figure 8
The crowd through the obstacles.Figure 9
When the width of the population is greater than the width of the intersection.Conditions for the crowd that smoothly pass obstacles can be expressed by the formulaDcrowdwidth>Dobstacle, where Dcrowdwidthcan be calculated by
(29)Dcrowdwidth=maxpi,k−pj,m∙sinθij,pi,k,pj,m∈G,where pi,k and pj,m are the kth position of the ith character and the mth position of the jth character, respectively. G is a collection of characters’ positions at the narrow junction. θij=θji means the angle between the vector and the moving direction. In order to solve this collision problem, a measure integrating mesh deformation and cage-based method proposed by Kim et al. [7] is put forward to adjust the spatial trajectories of the crowd. This measure can restrict virtual characters to a narrow road without crossing obstacles by adjusting the contour of the mesh.As is shown in Figure10, the contours with squares form an enclosing shell of the crowd. Since the shell is always on the periphery of the crowd, when the crowd is crossing the obstacles, the shell also gets through. In other words, if the shell has no intersection with barriers on the route, characters in the shell will not touch the barriers, too.Figure 10
An enclosing shell of characters gets through obstacles.Thus, adjusting the squares on the contour line of the shell to move them out of the obstacles can effectively avoid the crash, so that the crowd will not get through the obstacles. The schematic diagram of adjusting the bounding shell is presented in Figure11, where the squares are the vertices of the shell and the circular points are the mapping points of the vertices inside the obstacles.Figure 11
Adjustment of the bounding shell. (a) Intersections with the cage and an obstacle; (b) map the inside vertexes to the edge of the obstacle; (c) remove the inside points out of the obstacle depending on the mapping direction; (d) result of mesh deformation.As is presented in Figure11, parts (a) to (c) describe the process of detecting whether the enclosing shell passes through the obstacles, calculating the mapping points, and obtaining movement directions, as well as moving the vertexes to the new positions. Part (d) represents the generation of mesh deformation by solving Equation (1) to get the end result. Figure 12 illustrates the overall situation when getting through the narrow road.Figure 12
Adjustment of the vertices on the bounding shell.Mesh deformation is likely to change the trajectories of some characters in the crowd, which may lead to a sudden change in their speeds. Hence, Equation (9) is applied to adjust the speed, so that the movement becomes more realistic.It is probably that the whole structure of original mesh will be influenced after deformation when a part of the mesh has been greatly narrowed down. As a result, the distance between each character is likely to become short and even brings track overlap, which easily causes the collision. Therefore, the collision avoidance method mentioned in Section4.1 is used to solve this problem.


## 4.1. Collision Avoidance Method among People Based on Space Track Keeping

In view of collision avoidance among characters in the crowd, a method based on space track keeping is proposed—that is, to adjust the time tracks of related people to stagger the collision points. The strategy is shown in Figure6.Figure 6
The collision avoidance strategy based on space track keeping.


### 4.1.1. Collision Detection

The collision problem of theith character is detected by whether the minimum distances between the ith track and other tracks in the same section are less than the threshold.d in Equation (13) displays the nearest distance between individual i and j:
(13)d=pki+vkit′−pmj−vmjt′2.In order to gain the relevant time information, taked2’s partial with respect to t′ after getting d:
(14)∂d2∂t′=2vki−vmjpki+vkit′−pmj−vmjt′,and then, make ∂d2/∂t′=0 to solve t′. The result is presented in Equations (15) and (16):
(15)t′=pki−pmjvki−vmj,vki≠vmj,(16)t′=0,vki=vki,(17)t=l1,t′+l1<l1t′,l1<t′+l1<l2,l2,t′+l1>l2,where t is the time that two individuals get the shortest distance in different situations. In combination with t′, d, and the speed mentioned in the above functions, the spatial position of collision can be presented, respectively, as pki+t−tki∗vki and pmj+t−tmj∗vmj.The specific algorithm is shown in Algorithm2.Algorithm 2: Collision detection.
(1) Judge whether the tracks of theith and the jth character, which are tki,tk+1i and tmj,tm+1j separately, have intersections.(2) If there is no intersection, turn to Step 5. Or turn to Step 3.(3) Gain the intersectionl1,l2 and use Equation (13) to find the nearest distance between two persons in l1,l2.(4) If the distance is less than the threshold, jump to Step 6.(5)k=k+1. If k is less than the total number of the track sections of the ith pedestrian, turn to Step 1, otherwise turn to Step 7.(6) Record the characters who are going to collide and the corresponding position. Then jump to Step 8.(7)m=m+1. k=0. If m is less than the total number of the track sections of the jth pedestrian, turn to Step 1.(8) end


### 4.1.2. Collision Avoidance

The space-time trajectory is the combination of the spatial track and the time track. It can be regarded as a polyline in a three-dimensional space, comprising the spatial position coordinates of the character and the timeline. When the collision occurred, the minimum distance of two segments of the broken lines in this three-dimensional space is less than the threshold. Therefore, enlarging the distance over the threshold is able to prevent the collision.It is illustrated in Figure7 that adjusting the time track can affect the character’s three-dimensional trajectory to change the minimum distance between two lines. The distance, therefore, becomes greater than the threshold with no need to change their spatial locations. This method is suitable for scenes with complex terrain and large crowd density, because it can avoid the collisions in the crowd without worrying about colliding obstacles in the environment.Figure 7
The time of collision avoidance.In order to achieve the above purpose, the scaling factorS and translation coefficient T of time sequence are defined. When characters i and j have a crash, suppose that the crash moment is in the period tki,tk+1i and tmj,tm+1j for two pedestrians separately. After the scaling translation with S and T, the time periods turn to tki∗ai+bi,tk+1i∗ai+bi and tmj∗aj+bj,tm+1j∗aj+bj, respectively. Therefore, the collision can be prevented if previous time periods are replaced with the changed one.The scaling factor and the translation coefficient can be found according to Equation (19), while Equation (18) measures the change of the time before and after the adjustment.
(18)ET=SiTki−tki2+SiTk+1i−tki2+SjTmj−tmj2+SjTm+1j−tm+1j2,(19)fSi,Sj=minSi,SjETdt=distancei,j/vsubjecttog1Si,Sj=ai≥a,g2Si,Sj=aj≥a,g3Si,Sj=SiTki≥0,g4Si,Sj=SiTmj≥0,g5Si,Sj=SiT−SjT2≥dt2dt=distancei,j/v, where Si=aibiT, Tki=tki1, and T=t−l11. dt is the time interval between character i andj, which is estimated as follows:
(20)v=minvi,vjvi,vjdt=distancei,j/v,(21)distancei,j=Dthreshold−pki+t−tki∗vki−pmj−t−tmj∗vmj,(22)dt=distancei,j/v,whereDthreshold means the closest distance between two pedestrians. If the distance between two lines is less thanDthreshold, the collision will happen.Equation (19) is solved on the basis of the Kuhn-Tucker condition, that is, calculating the gradient of ,fSi,Sj, g2Si,Sj, g3Si,Sj, g4Si,Sj, and g5Si,Sj, respectively, to find Si¯ and Sj¯ satisfying Equation (23). The time nodes after adjustment aret¯ki=Si¯Tki, t¯k+1i=Si¯Tk+1i, t¯mj=Sj¯Tmi, t¯m+1j=Sj¯Tm+1j.
(23)∇fSi¯,Sj¯−∑i=15ωi∇giSi¯,Sj¯=0,ωigiSi¯,Sj¯=0,i=1,⋯,5,ωi≥0,i=1,⋯,5.After calculating the related time nodes, it is necessary to adjust the overall time series of the two characters in order to ensure that their speeds do not suddenly become very fast or slow. Considering that the change in speed is continuous, so the time people spent in per unit length is similar, expressed byEDT:
(24)EDT=∑i=1m−1∆ti+1li+1−∆tili2,whereli is the length of the ith segment on the pedestrian track and ∆ti is the time interval of the ith segment.In view of the similarity it should have between the speed before and after,EV is introduced to measure the degree of the speed change as shown in Equation (25). Nevertheless, the time node of the crowd is the only alteration during the whole process of collision avoidance, and therefore, the speed variation can be substituted by time information. Hence, ET is defined to represent the modification on time as well as on speed for the replacement of EV.
(25)EV=∑i=0mv¯i−vi2,(26)ET=∑i=0m∆t¯i−∆ti2,where ∆t¯i is the modified time interval. In the whole changing process, the adjustment of time node is hoped to be as little as possible. As a result, ETP is going to measure the degree of the change of time node as described in
(27)ETP=∑i=0nt¯i−ti2.Associating with Equations (24), (26), and (27), the avoidance method can be demonstrated by an optimization model, as shown in
(28)mint¯α2EDT+β2ET+γ2ETPsubjecttoMS∗t¯=mt,where α,β, and γ are the weight coefficients of EDT, ET, and ETP, respectively. The function of the matrix MS is to filter out the time nodes adjusted by Equation (18), while mt is a column vector consisting of the values of modified time nodes. The purpose of the constraint equation is to keep the time points that have been changed in the collision avoidance process away from changing again when the whole time track is later modified.The specific algorithm of collision avoidance method is shown in Algorithm3.Algorithm 3: Time trajectory deformation algorithm.
Comment:dthreshold is the threshold that users input.(1) Collision detection algorithm is used for any two virtual charactersi and j in the crowd. If no collision happens, end the algorithm; otherwise record the number of the accident segment k and m as well as the closest distance dmin;(2) Solve Equation (20) to estimate the time intervaldt;(3) Use Equations (19) to adjust the kth section of character i and the mth section of character j;(4) Use Equation (28) to adjust the whole time series of character i and j;(5) Jump to Step 1.


## 4.1.1. Collision Detection

The collision problem of theith character is detected by whether the minimum distances between the ith track and other tracks in the same section are less than the threshold.d in Equation (13) displays the nearest distance between individual i and j:
(13)d=pki+vkit′−pmj−vmjt′2.In order to gain the relevant time information, taked2’s partial with respect to t′ after getting d:
(14)∂d2∂t′=2vki−vmjpki+vkit′−pmj−vmjt′,and then, make ∂d2/∂t′=0 to solve t′. The result is presented in Equations (15) and (16):
(15)t′=pki−pmjvki−vmj,vki≠vmj,(16)t′=0,vki=vki,(17)t=l1,t′+l1<l1t′,l1<t′+l1<l2,l2,t′+l1>l2,where t is the time that two individuals get the shortest distance in different situations. In combination with t′, d, and the speed mentioned in the above functions, the spatial position of collision can be presented, respectively, as pki+t−tki∗vki and pmj+t−tmj∗vmj.The specific algorithm is shown in Algorithm2.Algorithm 2: Collision detection.
(1) Judge whether the tracks of theith and the jth character, which are tki,tk+1i and tmj,tm+1j separately, have intersections.(2) If there is no intersection, turn to Step 5. Or turn to Step 3.(3) Gain the intersectionl1,l2 and use Equation (13) to find the nearest distance between two persons in l1,l2.(4) If the distance is less than the threshold, jump to Step 6.(5)k=k+1. If k is less than the total number of the track sections of the ith pedestrian, turn to Step 1, otherwise turn to Step 7.(6) Record the characters who are going to collide and the corresponding position. Then jump to Step 8.(7)m=m+1. k=0. If m is less than the total number of the track sections of the jth pedestrian, turn to Step 1.(8) end


## 4.1.2. Collision Avoidance

The space-time trajectory is the combination of the spatial track and the time track. It can be regarded as a polyline in a three-dimensional space, comprising the spatial position coordinates of the character and the timeline. When the collision occurred, the minimum distance of two segments of the broken lines in this three-dimensional space is less than the threshold. Therefore, enlarging the distance over the threshold is able to prevent the collision.It is illustrated in Figure7 that adjusting the time track can affect the character’s three-dimensional trajectory to change the minimum distance between two lines. The distance, therefore, becomes greater than the threshold with no need to change their spatial locations. This method is suitable for scenes with complex terrain and large crowd density, because it can avoid the collisions in the crowd without worrying about colliding obstacles in the environment.Figure 7
The time of collision avoidance.In order to achieve the above purpose, the scaling factorS and translation coefficient T of time sequence are defined. When characters i and j have a crash, suppose that the crash moment is in the period tki,tk+1i and tmj,tm+1j for two pedestrians separately. After the scaling translation with S and T, the time periods turn to tki∗ai+bi,tk+1i∗ai+bi and tmj∗aj+bj,tm+1j∗aj+bj, respectively. Therefore, the collision can be prevented if previous time periods are replaced with the changed one.The scaling factor and the translation coefficient can be found according to Equation (19), while Equation (18) measures the change of the time before and after the adjustment.
(18)ET=SiTki−tki2+SiTk+1i−tki2+SjTmj−tmj2+SjTm+1j−tm+1j2,(19)fSi,Sj=minSi,SjETdt=distancei,j/vsubjecttog1Si,Sj=ai≥a,g2Si,Sj=aj≥a,g3Si,Sj=SiTki≥0,g4Si,Sj=SiTmj≥0,g5Si,Sj=SiT−SjT2≥dt2dt=distancei,j/v, where Si=aibiT, Tki=tki1, and T=t−l11. dt is the time interval between character i andj, which is estimated as follows:
(20)v=minvi,vjvi,vjdt=distancei,j/v,(21)distancei,j=Dthreshold−pki+t−tki∗vki−pmj−t−tmj∗vmj,(22)dt=distancei,j/v,whereDthreshold means the closest distance between two pedestrians. If the distance between two lines is less thanDthreshold, the collision will happen.Equation (19) is solved on the basis of the Kuhn-Tucker condition, that is, calculating the gradient of ,fSi,Sj, g2Si,Sj, g3Si,Sj, g4Si,Sj, and g5Si,Sj, respectively, to find Si¯ and Sj¯ satisfying Equation (23). The time nodes after adjustment aret¯ki=Si¯Tki, t¯k+1i=Si¯Tk+1i, t¯mj=Sj¯Tmi, t¯m+1j=Sj¯Tm+1j.
(23)∇fSi¯,Sj¯−∑i=15ωi∇giSi¯,Sj¯=0,ωigiSi¯,Sj¯=0,i=1,⋯,5,ωi≥0,i=1,⋯,5.After calculating the related time nodes, it is necessary to adjust the overall time series of the two characters in order to ensure that their speeds do not suddenly become very fast or slow. Considering that the change in speed is continuous, so the time people spent in per unit length is similar, expressed byEDT:
(24)EDT=∑i=1m−1∆ti+1li+1−∆tili2,whereli is the length of the ith segment on the pedestrian track and ∆ti is the time interval of the ith segment.In view of the similarity it should have between the speed before and after,EV is introduced to measure the degree of the speed change as shown in Equation (25). Nevertheless, the time node of the crowd is the only alteration during the whole process of collision avoidance, and therefore, the speed variation can be substituted by time information. Hence, ET is defined to represent the modification on time as well as on speed for the replacement of EV.
(25)EV=∑i=0mv¯i−vi2,(26)ET=∑i=0m∆t¯i−∆ti2,where ∆t¯i is the modified time interval. In the whole changing process, the adjustment of time node is hoped to be as little as possible. As a result, ETP is going to measure the degree of the change of time node as described in
(27)ETP=∑i=0nt¯i−ti2.Associating with Equations (24), (26), and (27), the avoidance method can be demonstrated by an optimization model, as shown in
(28)mint¯α2EDT+β2ET+γ2ETPsubjecttoMS∗t¯=mt,where α,β, and γ are the weight coefficients of EDT, ET, and ETP, respectively. The function of the matrix MS is to filter out the time nodes adjusted by Equation (18), while mt is a column vector consisting of the values of modified time nodes. The purpose of the constraint equation is to keep the time points that have been changed in the collision avoidance process away from changing again when the whole time track is later modified.The specific algorithm of collision avoidance method is shown in Algorithm3.Algorithm 3: Time trajectory deformation algorithm.
Comment:dthreshold is the threshold that users input.(1) Collision detection algorithm is used for any two virtual charactersi and j in the crowd. If no collision happens, end the algorithm; otherwise record the number of the accident segment k and m as well as the closest distance dmin;(2) Solve Equation (20) to estimate the time intervaldt;(3) Use Equations (19) to adjust the kth section of character i and the mth section of character j;(4) Use Equation (28) to adjust the whole time series of character i and j;(5) Jump to Step 1.


## 4.2. Obstacle Avoidance Method Based on Spatial Track Deformation Model

When the crowd pass through a narrow channel as displayed in Figure8, it is easy to collide with obstacles. It is very tedious for animators to manually manipulate virtual characters avoiding obstacles, which consumes a lot of time. The reason of the crash is when the crowd turn at a narrow junction, the maximum width of the crowd is bigger than the width of the intersection, as shown in Figure 9.Figure 8
The crowd through the obstacles.Figure 9
When the width of the population is greater than the width of the intersection.Conditions for the crowd that smoothly pass obstacles can be expressed by the formulaDcrowdwidth>Dobstacle, where Dcrowdwidthcan be calculated by
(29)Dcrowdwidth=maxpi,k−pj,m∙sinθij,pi,k,pj,m∈G,where pi,k and pj,m are the kth position of the ith character and the mth position of the jth character, respectively. G is a collection of characters’ positions at the narrow junction. θij=θji means the angle between the vector and the moving direction. In order to solve this collision problem, a measure integrating mesh deformation and cage-based method proposed by Kim et al. [7] is put forward to adjust the spatial trajectories of the crowd. This measure can restrict virtual characters to a narrow road without crossing obstacles by adjusting the contour of the mesh.As is shown in Figure10, the contours with squares form an enclosing shell of the crowd. Since the shell is always on the periphery of the crowd, when the crowd is crossing the obstacles, the shell also gets through. In other words, if the shell has no intersection with barriers on the route, characters in the shell will not touch the barriers, too.Figure 10
An enclosing shell of characters gets through obstacles.Thus, adjusting the squares on the contour line of the shell to move them out of the obstacles can effectively avoid the crash, so that the crowd will not get through the obstacles. The schematic diagram of adjusting the bounding shell is presented in Figure11, where the squares are the vertices of the shell and the circular points are the mapping points of the vertices inside the obstacles.Figure 11
Adjustment of the bounding shell. (a) Intersections with the cage and an obstacle; (b) map the inside vertexes to the edge of the obstacle; (c) remove the inside points out of the obstacle depending on the mapping direction; (d) result of mesh deformation.As is presented in Figure11, parts (a) to (c) describe the process of detecting whether the enclosing shell passes through the obstacles, calculating the mapping points, and obtaining movement directions, as well as moving the vertexes to the new positions. Part (d) represents the generation of mesh deformation by solving Equation (1) to get the end result. Figure 12 illustrates the overall situation when getting through the narrow road.Figure 12
Adjustment of the vertices on the bounding shell.Mesh deformation is likely to change the trajectories of some characters in the crowd, which may lead to a sudden change in their speeds. Hence, Equation (9) is applied to adjust the speed, so that the movement becomes more realistic.It is probably that the whole structure of original mesh will be influenced after deformation when a part of the mesh has been greatly narrowed down. As a result, the distance between each character is likely to become short and even brings track overlap, which easily causes the collision. Therefore, the collision avoidance method mentioned in Section4.1 is used to solve this problem.


## 5. Experimental Results

To verify the performance of the proposed method, different experiments were designed to simulate the crowd motion according to distinct demands. This section demonstrates experiments on crowd motion editing and collision avoidance. Meanwhile, the practical use of the method has been tested by setting up an editing system for the badminton hall of Beijing University of Technology to imitate the event-holding situation. The experiments were programmed in C++, and OpenSceneGraph was used for rendering scenes. Furthermore, MATLAB was applied to compute the target equations and optimize the solutions. The hardware configuration of the experimental platform is shown in Table1.Table 1
Hardware configuration of the experimental platform.
Configuration and parameters of the hardwareCPU Intel Core i3-2120 3.30 GHzGPUNVIDIA GeForce 405Motherboard Intel H61RAM 4GBHard disk 250 GB SATA


### 5.1. Crowd Motion Editing Results

According to Section3, people’s movement in the crowd is divided into spatial trajectory and temporal trajectory, while the position relationship between each character is recorded by the triangular mesh. Therefore, experiments in this part were conducted based on space and time attributes separately, which is in accordance with the description in Section 3.


#### 5.1.1. Spatial Track Editing Results

In terms of editing the space tracks of the crowd, the experiments are focused on the mesh deformation capacity, the smooth transition problem of trajectory after editing, and the speed mutation. Figure13 demonstrates the process of establishing, choosing, and editing the tracks as well as presents the final routes of characters. Equation (1) is used to calculate the editing result after mesh deformation, which is shown in part (c). It can be noticed that the edge of the crowd, that is, the concave hull, is in a smooth change during the editing.Figure 13
Effect of spatial track editing: (a) the original spatial tracks; (b) triangular meshes consist of spatial tracks and concave hull; (c) deformation effect after dragging the point in red circle along arrow direction; (d) editing result.In addition, the result reflects that partial deformation is caused because of Equation (1). There are two main factors deciding the deformation range brought by the above equation. The first one is the influence on the mesh given by editing. If the final position is far away from the original point, the whole grid will be under great influence, and therefore, the range of influence will be wide according to Equation (2). In order to make sure of the smoothness of the modification, it must be a gradual process that a large range of grid is involved. The second factor is the calculation of coefficient matrix C in Equation (3). The calculation result of Figure 13 is computed by Equation (4) that is set as α=0.01, k=300, and β=0.02. If C increase fast, the influence range will be small.Table2 demonstrates the comparison of two characters’ speeds before and after editing. Because there are many segments on a trajectory, we only choose sections with large speed change. It is displayed in the table that after spatial editing on the crowd, their speeds have been influenced for the distance between each point is modified in some parts of the space tracks while the original time interval is retained. Equation (9) is applied to adjust the characters’ temporal tracks to correct their speeds, and the result shows obvious effect after correction.Table 2
Crowd speed comparison before and after editing.
Character 1Speed before editing100Speed after editing8988878787888990919191Speed after modification1001001009910099100991009999Character 2Speed before editing100Speed after editing9897979997969798959297Speed after modification991009910099100991009910099


#### 5.1.2. Temporal Track Editing Results

As for adjusting the time information, three characters in the crowd were chosen in this experiment. In Figure14(a), we edit the temporal tracks of the bottom three characters to slow down their initial speeds and use Equation (9) to calculate the editing result. Parts (b) and (c) reflect the crowd formation before and after temporal track editing, respectively. It can be seen from the figure that the time modification causes variation on speed and further brings the formation change. In addition, it is shown in part (c) that the edited people remain in their relative positions during proceeding for their speeds are adjusted in an overall way.Figure 14
Effect of temporal track editing: (a) temporal track editing of three characters in the crowd: (b) the original formation of the crowd; (c) editing result.


### 5.2. Collision Avoidance Results

In this section, we concentrate on collision detection as well as avoiding the crash that happens on characters in the virtual environment, which are the foundation of making crowd animation and has direct relation to the animation quality. In the experiment, a standard path was calculated by the A∗ algorithm from the starting point to the end. Then, other walks were generated by copying the standard path in accordance with the number of characters. To observe the effect of methods mentioned in Section 4, a part of the road was narrowed down to create an environment that is prone to accidents.


#### 5.2.1. Collision Avoidance between People and Obstacles

Though the path avoided all of the obstacles during construction, it is likely for the crowd to crash on barriers when they pass a narrow alley. Hence, the mesh deformation method described in Section4.2 is used to avoid characters getting through the obstacles.As shown in Figure15, part (a) is the original mesh of the crowd while part (b) presents the mesh after deformation under the constraint of the concave hull. It is illustrated in part (b) that the whole crowd with the concave hull (the outline consists of yellow points) exactly fills in or is narrower than the road. Because of the restriction from the hull, crowd tracks are bounded outside obstacles and achieve collision avoidance.Figure 15
Collision avoidance between the crowd and obstacles: (a) the mesh generated from crowd getting through the obstacles; (b) mesh deformation application to avoid obstacles.


#### 5.2.2. Collision Avoidance among People

On dealing with the crash between virtual people and the environment, collision within characters is easily involved. For the mesh is constructed from every spatial trajectory, deformation will cause track variation and also influences a character’s speed, proceeding direction, and destination, resulting in crash in high possibility. The red circle in Figure16 reflects the collision.Figure 16
Collisions among people.The measure mentioned in Section4.1 is applied to this problem, and Figure 17 demonstrates the effect after modifying the spatiotemporal trajectories of characters.Figure 17
Collision avoidance among people.For overall adjustment and optimization solution are needed for the crowd track after each modification, the convergence rate is low when a considerable number of people participate, and therefore, the calculation is time-consuming. In order to improve the computational efficiency, the crowd track was compressed before collision detection. After detecting and handling the collision problems, the results calculated on the basis of compressed tracks can be converted to that before compression. Equation (30) is used to transform the result after compression:
(30)tkm=tkm∑j=1nljm∗ΔTim+tk−1m,where tkm and lkm present the kth time point and track segment of the mth character, respectively. Equation (30) informs that the result conversion is actually a process of time allocation in proportion.


### 5.3. An Application Case on Real Stadium

For practical use of the proposed method in Section3 and Section 4, the badminton hall of Beijing University of Technology was mapped to a virtual scene to simulate crowd motion. The scene has nearly 7000 seats, and virtual characters are supposed to walk through the aisles naturally. As it can be seen in Figures 18 and 19, the model imitates the marching process of the crowd when they enter and leave the stadium, and the mesh deformation method with spatial and temporal track adjustment was applied to the movement editing.Figure 18
The editing result when characters pass the center of stadium.Figure 19
The editing result when characters move through the aisles.


## 5.1. Crowd Motion Editing Results

According to Section3, people’s movement in the crowd is divided into spatial trajectory and temporal trajectory, while the position relationship between each character is recorded by the triangular mesh. Therefore, experiments in this part were conducted based on space and time attributes separately, which is in accordance with the description in Section 3.


### 5.1.1. Spatial Track Editing Results

In terms of editing the space tracks of the crowd, the experiments are focused on the mesh deformation capacity, the smooth transition problem of trajectory after editing, and the speed mutation. Figure13 demonstrates the process of establishing, choosing, and editing the tracks as well as presents the final routes of characters. Equation (1) is used to calculate the editing result after mesh deformation, which is shown in part (c). It can be noticed that the edge of the crowd, that is, the concave hull, is in a smooth change during the editing.Figure 13
Effect of spatial track editing: (a) the original spatial tracks; (b) triangular meshes consist of spatial tracks and concave hull; (c) deformation effect after dragging the point in red circle along arrow direction; (d) editing result.In addition, the result reflects that partial deformation is caused because of Equation (1). There are two main factors deciding the deformation range brought by the above equation. The first one is the influence on the mesh given by editing. If the final position is far away from the original point, the whole grid will be under great influence, and therefore, the range of influence will be wide according to Equation (2). In order to make sure of the smoothness of the modification, it must be a gradual process that a large range of grid is involved. The second factor is the calculation of coefficient matrix C in Equation (3). The calculation result of Figure 13 is computed by Equation (4) that is set as α=0.01, k=300, and β=0.02. If C increase fast, the influence range will be small.Table2 demonstrates the comparison of two characters’ speeds before and after editing. Because there are many segments on a trajectory, we only choose sections with large speed change. It is displayed in the table that after spatial editing on the crowd, their speeds have been influenced for the distance between each point is modified in some parts of the space tracks while the original time interval is retained. Equation (9) is applied to adjust the characters’ temporal tracks to correct their speeds, and the result shows obvious effect after correction.Table 2
Crowd speed comparison before and after editing.
Character 1Speed before editing100Speed after editing8988878787888990919191Speed after modification1001001009910099100991009999Character 2Speed before editing100Speed after editing9897979997969798959297Speed after modification991009910099100991009910099


### 5.1.2. Temporal Track Editing Results

As for adjusting the time information, three characters in the crowd were chosen in this experiment. In Figure14(a), we edit the temporal tracks of the bottom three characters to slow down their initial speeds and use Equation (9) to calculate the editing result. Parts (b) and (c) reflect the crowd formation before and after temporal track editing, respectively. It can be seen from the figure that the time modification causes variation on speed and further brings the formation change. In addition, it is shown in part (c) that the edited people remain in their relative positions during proceeding for their speeds are adjusted in an overall way.Figure 14
Effect of temporal track editing: (a) temporal track editing of three characters in the crowd: (b) the original formation of the crowd; (c) editing result.


## 5.1.1. Spatial Track Editing Results

In terms of editing the space tracks of the crowd, the experiments are focused on the mesh deformation capacity, the smooth transition problem of trajectory after editing, and the speed mutation. Figure13 demonstrates the process of establishing, choosing, and editing the tracks as well as presents the final routes of characters. Equation (1) is used to calculate the editing result after mesh deformation, which is shown in part (c). It can be noticed that the edge of the crowd, that is, the concave hull, is in a smooth change during the editing.Figure 13
Effect of spatial track editing: (a) the original spatial tracks; (b) triangular meshes consist of spatial tracks and concave hull; (c) deformation effect after dragging the point in red circle along arrow direction; (d) editing result.In addition, the result reflects that partial deformation is caused because of Equation (1). There are two main factors deciding the deformation range brought by the above equation. The first one is the influence on the mesh given by editing. If the final position is far away from the original point, the whole grid will be under great influence, and therefore, the range of influence will be wide according to Equation (2). In order to make sure of the smoothness of the modification, it must be a gradual process that a large range of grid is involved. The second factor is the calculation of coefficient matrix C in Equation (3). The calculation result of Figure 13 is computed by Equation (4) that is set as α=0.01, k=300, and β=0.02. If C increase fast, the influence range will be small.Table2 demonstrates the comparison of two characters’ speeds before and after editing. Because there are many segments on a trajectory, we only choose sections with large speed change. It is displayed in the table that after spatial editing on the crowd, their speeds have been influenced for the distance between each point is modified in some parts of the space tracks while the original time interval is retained. Equation (9) is applied to adjust the characters’ temporal tracks to correct their speeds, and the result shows obvious effect after correction.Table 2
Crowd speed comparison before and after editing.
Character 1Speed before editing100Speed after editing8988878787888990919191Speed after modification1001001009910099100991009999Character 2Speed before editing100Speed after editing9897979997969798959297Speed after modification991009910099100991009910099


## 5.1.2. Temporal Track Editing Results

As for adjusting the time information, three characters in the crowd were chosen in this experiment. In Figure14(a), we edit the temporal tracks of the bottom three characters to slow down their initial speeds and use Equation (9) to calculate the editing result. Parts (b) and (c) reflect the crowd formation before and after temporal track editing, respectively. It can be seen from the figure that the time modification causes variation on speed and further brings the formation change. In addition, it is shown in part (c) that the edited people remain in their relative positions during proceeding for their speeds are adjusted in an overall way.Figure 14
Effect of temporal track editing: (a) temporal track editing of three characters in the crowd: (b) the original formation of the crowd; (c) editing result.


## 5.2. Collision Avoidance Results

In this section, we concentrate on collision detection as well as avoiding the crash that happens on characters in the virtual environment, which are the foundation of making crowd animation and has direct relation to the animation quality. In the experiment, a standard path was calculated by the A∗ algorithm from the starting point to the end. Then, other walks were generated by copying the standard path in accordance with the number of characters. To observe the effect of methods mentioned in Section 4, a part of the road was narrowed down to create an environment that is prone to accidents.


### 5.2.1. Collision Avoidance between People and Obstacles

Though the path avoided all of the obstacles during construction, it is likely for the crowd to crash on barriers when they pass a narrow alley. Hence, the mesh deformation method described in Section4.2 is used to avoid characters getting through the obstacles.As shown in Figure15, part (a) is the original mesh of the crowd while part (b) presents the mesh after deformation under the constraint of the concave hull. It is illustrated in part (b) that the whole crowd with the concave hull (the outline consists of yellow points) exactly fills in or is narrower than the road. Because of the restriction from the hull, crowd tracks are bounded outside obstacles and achieve collision avoidance.Figure 15
Collision avoidance between the crowd and obstacles: (a) the mesh generated from crowd getting through the obstacles; (b) mesh deformation application to avoid obstacles.


### 5.2.2. Collision Avoidance among People

On dealing with the crash between virtual people and the environment, collision within characters is easily involved. For the mesh is constructed from every spatial trajectory, deformation will cause track variation and also influences a character’s speed, proceeding direction, and destination, resulting in crash in high possibility. The red circle in Figure16 reflects the collision.Figure 16
Collisions among people.The measure mentioned in Section4.1 is applied to this problem, and Figure 17 demonstrates the effect after modifying the spatiotemporal trajectories of characters.Figure 17
Collision avoidance among people.For overall adjustment and optimization solution are needed for the crowd track after each modification, the convergence rate is low when a considerable number of people participate, and therefore, the calculation is time-consuming. In order to improve the computational efficiency, the crowd track was compressed before collision detection. After detecting and handling the collision problems, the results calculated on the basis of compressed tracks can be converted to that before compression. Equation (30) is used to transform the result after compression:
(30)tkm=tkm∑j=1nljm∗ΔTim+tk−1m,where tkm and lkm present the kth time point and track segment of the mth character, respectively. Equation (30) informs that the result conversion is actually a process of time allocation in proportion.


## 5.2.1. Collision Avoidance between People and Obstacles

Though the path avoided all of the obstacles during construction, it is likely for the crowd to crash on barriers when they pass a narrow alley. Hence, the mesh deformation method described in Section4.2 is used to avoid characters getting through the obstacles.As shown in Figure15, part (a) is the original mesh of the crowd while part (b) presents the mesh after deformation under the constraint of the concave hull. It is illustrated in part (b) that the whole crowd with the concave hull (the outline consists of yellow points) exactly fills in or is narrower than the road. Because of the restriction from the hull, crowd tracks are bounded outside obstacles and achieve collision avoidance.Figure 15
Collision avoidance between the crowd and obstacles: (a) the mesh generated from crowd getting through the obstacles; (b) mesh deformation application to avoid obstacles.


## 5.2.2. Collision Avoidance among People

On dealing with the crash between virtual people and the environment, collision within characters is easily involved. For the mesh is constructed from every spatial trajectory, deformation will cause track variation and also influences a character’s speed, proceeding direction, and destination, resulting in crash in high possibility. The red circle in Figure16 reflects the collision.Figure 16
Collisions among people.The measure mentioned in Section4.1 is applied to this problem, and Figure 17 demonstrates the effect after modifying the spatiotemporal trajectories of characters.Figure 17
Collision avoidance among people.For overall adjustment and optimization solution are needed for the crowd track after each modification, the convergence rate is low when a considerable number of people participate, and therefore, the calculation is time-consuming. In order to improve the computational efficiency, the crowd track was compressed before collision detection. After detecting and handling the collision problems, the results calculated on the basis of compressed tracks can be converted to that before compression. Equation (30) is used to transform the result after compression:
(30)tkm=tkm∑j=1nljm∗ΔTim+tk−1m,where tkm and lkm present the kth time point and track segment of the mth character, respectively. Equation (30) informs that the result conversion is actually a process of time allocation in proportion.


## 5.3. An Application Case on Real Stadium

For practical use of the proposed method in Section3 and Section 4, the badminton hall of Beijing University of Technology was mapped to a virtual scene to simulate crowd motion. The scene has nearly 7000 seats, and virtual characters are supposed to walk through the aisles naturally. As it can be seen in Figures 18 and 19, the model imitates the marching process of the crowd when they enter and leave the stadium, and the mesh deformation method with spatial and temporal track adjustment was applied to the movement editing.Figure 18
The editing result when characters pass the center of stadium.Figure 19
The editing result when characters move through the aisles.


## 6. Conclusions and Future Work

This paper put forward a crowd motion editing method that can be applied on crowd animation and simulation. The method is able to retain the relative positions of people, which is suitable for activities that needed fixed orientation relationships among participants, such as the march-in ceremony and military review. Meanwhile, this mesh deformation-based method directly edits the crowd by dragging the mouse, which is easier to operate and improves the simulation productivity.Nevertheless, there is still room for promotion. Because of large amount of data involved in the editing process, future studies can focus on the enhancement of computational efficiency. In addition, the proposed collision avoidance method is time-based, and therefore, combining collision problems with spatial attributes is worth studying in the future.



---

*Source: 3634054-2020-12-08.xml*