With the increased use of crowd simulation in animation, specification of crowd motion can be very time consuming, requiring a lot of user input. To alleviate this cost, we wish to allow a user to interactively manipulate the many degrees of freedom in a crowd, whilst accounting for the limitation of low-dimensional signals from standard input devices. In this thesis we present two approaches for achieving this: 1) Combining shape deformation methods with a multitouch input device, allowing a user to control the motion of the crowd in dynamic environments, and 2) applying a data-driven approach to learn the mapping between a crowd’s motion and the corresponding user input to enable intuitive control of a crowd. In our first approach, we represent the crowd as a deformable mesh, allowing a user to manipulate it using a multitouch device. The user controls the shape and motion of the crowd by altering the mesh, and the mesh in turn deforms according to the environment. We handle congestion and perturbation by having agents dynamically reassign their goals in the formation using a mass transport solver. Our method allows control of a crowd in a single pass, improving on the time taken by previous, multistage, approaches. We validate our method with a user study, comparing our control algorithm against a common mouse-based controller. We develop a simplified version of motion data patches to model character-environment interactions that are largely ignored in previous crowd research. We design an environment-aware cost metric for the mass transport solver that considers how these interactions affect a character’s ability to track the user’s commands. Experimental results show that our system can produce realistic crowd scenes with minimal, high-level, input signals from the user. In our second approach, we propose that crowd simulation control algorithms inherently impose restrictions on how user input affects the motion of the crowd. To bypass this, we investigate a data-driven approach for creating a direct mapping between low-dimensional user input and the resulting high-dimensional crowd motion. Results show that the crowd motion can be inferred directly from variations in a user’s input signals, providing a user with greater freedom to define the animation.

A common practice in crowd animation is the use of human templates. A human template is a 3D character defined by its mesh, skeletal structure, materials, and textures. A crowd simulation is created by repeatedly instantiating a small set of human templates. For each instance, one texture is randomly chosen from the template’s available texture set, and color and shape variety techniques are applied so that multiple instances of the same template appear different (Thalmann & Musse, 2013). When dealing with very large crowds, it is inevitable to end up with instances that are exactly identical to other instances, as the number of different textures and shape modifications is limited. This poses a problem for crowd animation, as the viewers’ perception of identical characters could significantly decrease the believability of the crowd simulation. A variety of factors could affect viewers’ perception of identical characters, including crowd size, distance of the characters from the camera, background, movement, lighting conditions, etc. The study reported in this paper examined the extent to which the type of locomotion of the crowd characters affects the viewer’s ability to perceive identical instances within a medium size crowd (20 characters). The experiment involved 51 participants and compared the time the participants took to recognize two identical characters in three different locomotion scenarios (i.e. standing, walking, and running). Findings show that the type of locomotion did not have a statistically significant effect on the time subjects took to identify identical characters within the crowd. Hence, results suggest that audience perception of identical characters in a medium size crowd is not affected by the type of movement of the characters.

Les foules sont de plus en plus présentes dans les médias grands publics, comme le cinéma ou les jeux vidéo. Elles permettent de renforcer l'immersion du sujet dans l'environnement qui lui est présenté. Or, la création de mouvement de foule est la plus part du temps basé sur des modèles dures à prendre en main et qui n'offrent pas un contrôle direct sur le mouvement de foule que l'on souhaite créer. Dans cette thèse nous proposons des contributions sous forme de méthodes pour concevoir des mouvements de foules par le biais d'outils interactifs et intuitifs. Dans un premier temps, nous présentons une méthode interactive permettant de concevoir des foules en les déformant comme de l'argile. L'utilisateur peut tirer, compresser et torde la forme global de des foules pour leurs donner la forme qu'il ou elle souhaite. Les personnages qui composent la foule s'adaptent automatiquement à la nouvelle forme imposée par l'utilisateur. Dans un second temps, nous présentons une méthode permettant de peindre les mouvements et la densité de la foule pour la créer. Nous offrons la possibilité à l'utilisateur de créer des foules en peignant une carte de densité en niveau de gris, et une carte de mouvement via des dégradés. Ses cartes de couleurs sont utilisées par notre système pour le transformer en un mouvement de foule, via un algorithme itératif cherchant à optimiser les différentes valeurs des cartes de couleurs. Les foules obtenues par ces méthodes peuvent occupées un espace très large, et sont animées indéfiniment. Contrairement aux méthodes classiques de création de foules qui se basent sur l'ajustement de paramètres de modèles, nos méthodes permettent de concevoir les mouvements de foules en se basant sur des caractéristiques plus hauts niveaux de la foule, comme sa forme globale, ses mouvements internes ou sa densité. Ce qui offre la possibilité de créer du contenu de foule animée de manière simple, rapide et intuitif. / Crowds are increasingly present in audio-visual media, such as movies or video games. They help to strengthen the immersion of the subject in the virtual environment. However, creating crowds is most of the time based on models hard to master and which do not offer a direct control on the motion that you want to create. In this thesis we propose contributions for designing crowd motions through interactive and intuitive tools. Firstly, we present an interactive method for designing the crowds by distorting it like clay. The user can stretch, compress and twist the overall shape of the crowd to give it the shape he or she wishes. The inner characters of the crowd automatically adapt to the new shape imposed by the user. Secondly, we present a method to paint the motion and the density of the crowd to create it. We offer the opportunity to the user to create crowds by painting a grayscale density map and a motion map by gradients. Its colored maps are transformed by our system to crowds, thanks to our iterative algorithm seeking to optimize the different values of colored maps. Crowds obtained by these methods can occupy a very large space and are animated indefinitely. Unlike conventional methods of creating crowds, that are based on the adjustment of model parameters, our methods allow to design crowd motions based on higher level features of the crowd, as its overall shape, its internal movement or density. This offers the possibility to simply, quickly and intuitively create animated crowd contents.

Crowd simulations are attracting increasing attention from both academia and the industry field and are implemented across a vast range of applications, from scientific demonstrations to video games and films. As such, the demand for greater realism in their aesthetics and the amount of agents involved is always growing. A successful crowd simulation must simulate large numbers of pedestrians' behaviours as realistically as possible in real-time. The thesis looks at two important aspects of crowd simulation and real-time animation. First, this thesis introduces a new data structure called Extended Oriented Bounding Box (EOBB) and related methods for fast collision detection and obstacle avoidance in the simulation of crowd motion in virtual environments. The EOBB is extended to contain a region whose size is defined based on the instantaneous velocity vector, thus allowing a bounding volume representation of both geometry and motion. Such a representation is also found to be highly effective in motion planning using the location of vertices of bounding boxes in the immediate neighbourhood of the current crowd member. Second, we present a detailed analysis of the effectiveness of spatial subdivision data structures, specifically for large-scale crowd simulation. For large-scale crowd simulation, computational time for collision detection is huge, and many studies use spatial partitioning data structure to reduce the computational time, depicting their strengths and weaknesses, but few compare multiple methods in an effort to present the best solution. This thesis attempts to address this by implementing and comparing four popular spatial partitioning data structures with the EOBB.

無論在電腦動畫、電玩或電影產業，利用電腦自動產生虛擬人群已逐漸成為不可或缺的要素之一。這些虛擬人群，往往是系統先賦與每個虛擬代理人(agent)基礎智能，然後藉由個體之間的互動法則所自動產生。然而，過去因為普遍未考量真實群體情境中的傳播與互動模式，使得虛擬人群所表現的群體行為與現實情況仍有些差距。因此，我們引用社會心理學文獻，建立一個具有溝通機制的人群模擬平台(IMCrowd)，以期自動產生與現實群眾動態更相似的模擬人群。IMCrowd是多代理人(Multi-agent)基礎的系統，其中每個虛擬代理人都具有區域的感知範圍與自主能力，因此他們能夠自動地與環境中的其它物件互動與反應。由於我們為IMCrowd所建立的溝通模型考量了社會心理學的理論，因此虛擬人群能浮現真實群體動態中的社會互動模式，如情緒傳染與從眾效應。本研究以IMCrowd執行了多種情境下群眾暴動與群眾控制的模擬，藉此展現本系統的應用將不僅可提升群體模擬的真實度，亦可做為社會心理學家研究群體行為的工具。 / Using computer to automatically generate simulated crowd has become a trend in animation, computer game, and film productions. Many of these works were produced by modeling the intelligence of the agents in a crowd and their interactions with other nearby agents and the environment. However, the perceived facts or elicited emotions usually do not propagate in the crowd as they should in the real life. In this work we attempt to build up a communication model to simulate a large variety of crowd behaviors including the course of crowd formation. The proposed crowd simulation system, IMCrowd, has been implemented with a multi-agent system in which each agent has a local perception and autonomous abilities to improvise their actions. The algorithms used in our communication model in IMCrowd are based heavily on sociology research. Therefore, the collective behaviors will emerge out of the social process such as emotion contagion and conformity effect among individual agents. Several elaborate riot simulations and riot control simulations are demonstrated and reported in this thesis as the application examples of IMCrowd. Thus, we claim that IMCrowd may not only benefit on enhancing realism of crowd animation but also be useful in studying crowd behaviors such as panic, gathering, and riots.