MIG '14: Proceedings of the Seventh International Conference on Motion in Games

Full Citation in the ACM Digital Library


Optimization-based computation of locomotion trajectories for crowd patches

Over the past few years, simulating crowds in virtual environments has become an important tool to give life to virtual scenes; be it movies, games, training applications, etc. An important part of crowd simulation is the way that people move from one place to another. This paper concentrates on improving the crowd patches approach proposed by Yersin et al. [Yersin et al. 2009] that aims on efficiently animating ambient crowds in a scene. This method is based on the construction of animation blocks (called patches) concatenated together under some constraints to create larger and richer animations with limited run-time cost. Specifically, an optimization based approach to generate smooth collision free trajectories for crowd patches is proposed. The contributions of this work to the crowd patches framework are threefold; firstly a method to match the end points of trajectories based on the Gale-Shapley algorithm [Gale and Shapley 1962] is proposed that takes into account preferred velocities and space coverage, secondly an improved algorithm for collision avoidance is proposed that gives natural appearance to trajectories and finally a cubic spline approach is used to smooth out generated trajectories. We demonstrate several examples of patches and how they were improved by the proposed method, some limitations and directions for future improvements.

Following behaviors: a model for computing following distances based on prediction

In this paper, we present a new model to simulate following behavior. This model is based on a dynamic following distance that changes according to the follower's speed and to the leader's motion. The following distance is associated with a prediction of the leader's future position to give a following ideal position. We show the resulting following trajectory and detail the importance of the distance variation in different situations. The model is evaluated using real data. We demonstrate the capacity of our model to reproduce macroscopic patterns and show that it is also able to synthesize trajectories similar to real ones. Finally, we compare our results with other following models and point out the improvements.

GPGPU-accelerated construction of high-resolution generalized voronoi diagrams and navigation meshes

This paper presents a GPU-accelerated approach for improving the approximated construction of Generalized Voronoi Diagrams (GVDs). Previous work has shown how to render a GVD onto the GPU framebuffer, and copy it to the CPU for extraction of a high-quality diagram. We improve upon this technique by performing more computations in parallel on the GPU, and reducing the amount of data transferred to the CPU. We also design a multi-tiled construction technique that overcomes hardware limitations and enables much higher rendering resolutions, thus reducing discretization errors. Next, we extend our approach to create an Explicit Corridor Map navigation mesh, which is an efficient data structure for path planning in modern crowd simulation systems. The new implementation allows much faster construction of GVDs and navigation meshes at virtually infinite resolutions.

SESSION: Expression

Facial retargeting using neural networks

Mapping the motion of an actor's face to a virtual model is a difficult but important problem, especially as fully animated characters are becoming more common in games and movies. Many methods have been proposed but most require the source and target to be structurally similar. Optical motion capture markers and blendshape weights are an example of topologically incongruous source and target examples that do not have a simple mapping between one another. In this paper, we created a system capable of determining this mapping through supervised learning of a small training dataset. Radial Basis Function Networks (RBFNs) have been used for retargeting markers to blendshape weights before but to our knowledge Multi-Layer Perceptron Artificial Neural Networks (referred to as ANNs) have not been employed in this way. We hypothesized that ANNs would result in a superior retargeting solution compared to the RBFN, due to their theoretically greater representational power. We implemented a retargeting system using ANNs and RBFNs for comparison. Our results found that both systems produced similar results (figure 1) and in some cases the ANN proved to be more expressive although the ANN was more difficult to work with.

Beyond basic emotions: expressive virtual actors with social attitudes

The purpose of this work is to evaluate the contribution of audio-visual prosody to the perception of complex mental states of virtual actors. We propose that global audio-visual prosodic contours - i.e. melody, rhythm and head movements over the utterance - constitute discriminant features for both the generation and recognition of social attitudes. The hypothesis is tested on an acted corpus of social attitudes in virtual actors and evaluation is done using objective measures and perceptual tests.

Acting the part: the role of gesture on avatar identity

Recent advances in scanning technology have enabled the widespread capture of 3D character models based on human subjects. However, in order to generate a recognizable 3D avatar, the movement and behavior of the human subject should be captured and replicated as well. We present a method of generating a 3D model from a scan, as well as a method to incorporate a subjects style of gesturing into a 3D character. We present a study which shows that 3D characters that used the gestural style as their original human subjects were more recognizable as the original subject than those that don't.

Rethinking NPC intelligence: a new reputation system

Creating more believable Non-Player Characters (NPCs) is a significant challenge for video game researchers and industry designers alike. While researchers explore a myriad of solutions, one somewhat forgotten solution area is NPC reputation systems. In this paper, we describe a redefined reputation system for NPC characters that allows for more realistic and dynamic social relationships. Our reputation system focuses on an agent's ability to remember and share observed behavior of other actors in the world. With this knowledge, NPCs can predict behavior of other actors, react according to their own subjective opinion, and exhibit more believable behavior to further immerse the player in the game world.

SESSION: Human motion 1

Trade-offs between responsiveness and naturalness for player characters

Real-time animation controllers are fundamental for animating characters in response to player input. However, the design of such controllers requires making trade-offs between the naturalness of the character's motions and the promptness of the character's response. In this paper, we investigate the effects of such tradeoffs on the players' enjoyment, control, satisfaction, and opinion of the character in a simple platform game. In our first experiment, we compare three controllers having the same responsiveness, but varying levels of naturalness. In the second experiment, we compare three controllers having increasing realism but at the expense of decreased responsiveness. Not surprisingly, our least responsive controller negatively affects players' performance and perceived ability to control the character. However, we also find that players are most satisfied with their own performance using our least natural controller, in which the character moves around the environment in a static pose; that differences in animation can significantly alter players' enjoyment with responsiveness being equal; and that players do not report increased motion quality with our most natural controller, despite viewers outside of a game context rating the same controller as significantly more natural than our other conditions.

Anticipatory balance control

A hallmark of many skilled motions is the anticipatory nature of the balance-related adjustments that happen in preparation for the expected evolution of forces during the motion. This can shape simulated and animated motions in subtle-but-important ways, help lend physical credence to the motion, and help signal the character's intent. In this paper, we investigate how center of mass reference trajectories (CMRTs) can be learned in order to achieve anticipatory balance control with a state-of-the-art reactive balancing system. This enables the design of physics-based motion simulations that involve fast pose transitions as well as force-based interactions with the environment, such as punches, pushes, and catching heavy objects. We demonstrate the results on planar human models, and show that CMRTs can generalize across parameterized versions of a motion. We illustrate that they are also effective at conveying a mismatch between a character's expectations and reality, e.g., thinking that an object is heavier than it is.

SESSION: Path following

Computing high-quality paths in weighted regions

The Weighted Region Problem is defined as the problem of finding a cost-optimal path in a weighted planar polygonal subdivision. Searching for paths on a grid representation of the scene is fast and easy to implement. However, grid representations do not capture the exact geometry of the scene. Hence, grid paths can be inaccurate or might not even exist at all. Methods that work on an exact representation of the scene can approximate an optimal path up to an arbitrarily small ε-error. However, these methods are computationally inefficient and thus not well-suited for real-time applications. In this paper, we analyze the quality of optimal paths on a 8-neighbor-grid. We prove that the costs of such a path in a scene with weighted regions can be arbitrarily high in the general case. If all regions are aligned with the grid, we prove that the costs are at most (4+[EQUATION]) times the costs of an optimal path. In addition, we present a new hybrid method called Vertex-based Pruning (VBP). VBP computes paths that are ε-optimal inside a pruned subset of the scene. Experiments show that VBP paths can be computed at interactive rates, and are thus well-suited as an input for advanced path-following strategies in robotics, crowd simulation or gaming applications.

Motion planning with rigid-body dynamics for generalized traveling salesman tours

This paper pursues multi-goal motion planning, where the overall set of goals is divided into k groups and the virtual agent needs to visit at least one goal per group. We have developed a combined task and motion-planning approach which can work with ground and aerial vehicles whose motions are simulated by differential equations or by physics-based game engines. The proposed approach is based on a hybrid search, where the expansion of a motion tree in the continuous state space is guided by heuristic costs and generalized traveling salesman tours computed over a discrete abstraction. The discrete abstraction is obtained via a probabilistic roadmap constructed over a low-dimensional configuration space resulting from a simplified problem setting. By capturing the connectivity of the free configuration space and connecting the goals, the roadmap provides generalized traveling salesman tours that effectively guide the motion-tree expansion. Experiments demonstrate that the approach not only improves previous methodologies in terms of runtime and solution length but also that it is scalable with respect to both the number of goals and groups.

Computing shortest path maps with GPU shaders

We present in this paper a new GPU-based approach to compute Shortest Path Maps (SPMs) from a source point in a polygonal domain. Our method takes advantage of GPU polygon rasterization with shader programming. After encoding the SPM in the frame buffer, globally shortest paths are efficiently computed in time proportional to the number of vertices in the path, and length queries are computed in constant time. We have evaluated our method in multiple environments and our results show a significant speedup in comparison to previous approaches.

Prediction in social path following

Path following in games mostly focuses on avoiding collisions with dynamic physical objects that appear along a chosen path to a given destination. Some work also attempts to humanize the abstract path returned by a path finding algorithm through methods like smoothing. Games typically do not consider social factors during path following, even though many depict social environments. Social path following considers the social environment in particular, carving a trajectory that reflects awareness of other human beings and their social activities. This includes awareness of territories that have social significance but no concrete physical form, such as the space between those having a conversation. This paper describes work that extends a state-of-the-art predictive method for path following with social awareness, predicting and avoiding social collisions. The work builds on a platform for social simulation, which already models social territoriality and gaze behavior. The results appear promising and highlight the importance of perceiving and dealing with the social space along with the physical one.

SESSION: Camera control

Narrative-driven camera control for cinematic replay of computer games

This paper presents a system that generates cinematic replays for dialogue-based 3D video games. The system exploits the narrative and geometric information present in these games and automatically computes camera framings and edits to build a coherent cinematic replay of the gaming session. We propose a novel importance-driven approach to cinematic replay. Rather than relying on actions performed by characters to drive the cinematography (as in idiom-based approaches), we rely on the importance of characters in the narrative. We first devise a mechanism to compute the varying importance of the characters. We then map importances of characters with different camera specifications, and propose a novel technique that (i) automatically computes camera positions satisfying given specifications, and (ii) provides smooth camera motions when transitioning between different specifications. We demonstrate the features of our system by implementing three camera behaviors (one for master shots, one for shots on the player character, and one for reverse shots). We present results obtained by interfacing our system with a full-fledged serious game (Nothing for Dinner) containing several hours of 3D animated content.

Physical rig for first-person, look-at cameras in video games

This paper proposes a physics based model to simulate a reactive camera that is capable of both high-quality tracking of moving target objects and producing plausible response interactively to a variety of game scenarios. The virtual physical rig consists of a motorized pan-tilt head that is controlled to meet desired target look-at directions as well as an active suspension system that stabilizes the camera assembly against disturbances. To showcase its differences with other camera systems, we contrast our physically based technique with other direct (kinematic) computed methods from industry standard techniques.


Influence of animated reality mixing techniques on user experience

We investigate the influence of motion effects in the domain of mobile Augmented Reality (AR) games on user experience and task performance. The work focuses on evaluating responses to a selection of synthesized camera oriented reality mixing techniques for AR, such as motion blur, defocus blur, latency and lighting responsiveness. In our cross section of experiments, we observe that these measures have a significant impact on perceived realism, where aesthetic quality is valued. However, lower latency records the strongest correlation with improved subjective enjoyment, satisfaction, and realism, and objective scoring performance. We conclude that the reality mixing techniques employed are not significant in the overall user experience of a mobile AR game, except where harmonious or convincing blended AR image quality is consciously desired by the participants.

Molecular tetris: crowdsourcing molecular docking using path-planning and haptic devices

Many biological processes, including immune recognition, enzyme catalysis, and molecular signaling, which is still an open problem in biological sciences. We present Molecular Tetris, a game in which a player can explore the binding between a protein receptor and ligand. This exploration is similar to the game Tetris with atomic forces guiding best fits between shapes. This game will be utilized for crowdsourced haptic-guided motion planning. Haptic touch devices enable users to feel the interactions of two molecules as they move the ligand into an appropriate binding site on the receptor. We demonstrate the method on a critical piece of human immune response, ligand binding to a Major Histocompatibility Complex (MHC) molecule. Through multiple runs by our users, we construct a global roadmap that finds low energy paths to molecular docking sites. These paths are comparable to a highly-biased roadmap generated by Gaussian sampling around the known bound state. Our users are able to find low energy paths with both a specialized force-feedback device and a commodity game console controller.

SESSION: Human motion 2

Coupling cloth and rigid bodies for dexterous manipulation

This paper introduces a new simulation technique to enable detailed dexterous manipulation of cloth. Without reimplementation or substantial modification, existing cloth simulators can only be used to approximate limited interaction between cloth and rigid bodies due to the incorrect computation of contact forces. For example, a simple scenario of two fingers pinching a piece of cloth often results in the cloth slipping out of the hand. Our technique provides a simple solution to cloth-rigid coupling using existing cloth and rigid body simulators as-is. We develop a light-weight interface so that the rigid body and cloth simulators communicate on a demand-driven manner to achieve two main goals: allow the rigid bodies to impart friction forces to the cloth and avoid unsolvable collision situations between the rigid bodies and the cloth. We demonstrate a set of basic manipulation skills including gripping, pinching, and pressing, that are frequently seen in daily activities such as dressing and folding clothes.

Generating hand motion from body motion using key hand poses

In this paper, we propose a method to generate hand motion from full-body motion. We assume that hand pose can be estimated from full-body pose. We use a support vector machine (SVM) to choose one of four key hand poses based on the full-body pose. The training model is constructed from a number of full-body motions with manually specified hand-pose keyframes. The output pose is synthesized to include the generated continuous hand motion. Since our method does not require future poses, it is valid for both on-line and off-line animation. Our experimental results show that our model is applicable to a wide range of motions.

SESSION: Optimization and physics

Characterizing and optimizing game level difficulty

Balancing the interactions between game level design and intended player experience is a difficult and time consuming process. Automating aspects of this process with respect to user-defined constraints has beneficial implications for game designers. A change in level layout may affect the available routes and subsequent player interactions for a number of agents within the level. Small changes in the placement of game elements may lead to significant changes in terms of the challenge experienced by the player on the path to their goal. Estimating the effect of this change requires that the designer take into account new paths of all interacting agents and how these may affect the player. As the number of these agents grow to crowd size, estimating the effect of these changes becomes grows difficult. We present a user-in-the-loop framework for tackling this task by optimizing enemy agent settings and the placement of game elements that affect the flow of agents within the level, with respect to estimated difficulty. Using static path analysis we estimate difficulty based on agent interactions with the player. To exemplify the usefulness of the framework, we show that small changes in level layout lead to significant changes in game difficulty, and optimizations with respect to the characterization of difficulty can be used to attain desired difficulty levels.

Automatic depiction of onomatopoeia in animation considering physical phenomena

This paper presents a method that enables the estimation and depiction of onomatopoeia in computer-generated animation based on physical parameters. Onomatopoeia is used to enhance physical characteristics and movement, and enables users to understand animation more intuitively. We experiment with onomatopoeia depiction in scenes within the animation process. To quantify onomatopoeia, we employ Komatsu's [2012] assumption, i.e., onomatopoeia can be expressed by n-dimensional vector. We also propose phonetic symbol vectors based on the correspondence of phonetic symbols to the impressions of onomatopoeia using a questionnaire-based investigation. Furthermore, we verify the positioning of onomatopoeia in animated scenes. The algorithms directly combine phonetic symbols to estimate optimum onomatopoeia. They use a view-dependent Gaussian function to display onomatopoeias in animated scenes. Our method successfully recommends optimum onomatopoeias using only physical parameters, so that even amateur animators can easily create onomatopoeia animation.

Multi-layer skin simulation with adaptive constraints

We present an approach for physics based simulation of the wrinkling of multi-layer skin with heterogeneous material properties. Each layer of skin is simulated with an adaptive mesh, with the different layers coupled via constraints that only permit wrinkle deformation at wavelengths that match the physical properties of the multi-layer model. We use texture maps to define varying elasticity and thickness of the skin layers, and design our constraints as continuous functions, which we discretize at run time to match the changing adaptive mesh topology. In our examples, we use blend shapes to drive the bottom layer, and we present a variety of examples of simulations that demonstrate small wrinkles on top of larger wrinkles, which is a typical pattern seen on human skin. Finally, we show that our physics-based wrinkles can be used in the automatic creation of wrinkle maps, allowing the visual details of our high resolution simulations to be produced at real time speeds.

Strain limiting for clustered shape matching

In this paper, we advocate explicit symplectic Euler integration and strain limiting in a shape matching simulation framework. The resulting approach resembles not only previous work on shape matching and strain limiting, but also the recently popular position-based dynamics. However, unlike this previous work, our approach reduces to explicit integration under small strains, but remains stable in the presence of non-linearities.

POSTER SESSION: Poster abstracts

Agent script generation using descriptive text documents

When designing games, artists exert large efforts to create visually compelling scenes. Work such as WordsEye [Coyne and Sproat 2001] can assist artists by parsing natural language texts into static scenes. Complementary to this endeavour is the population of that environment by simulation authors. Adding agents to an environment with plausible behaviors is a time consuming process, as most require individual scripts to control their behavior. This generally degrades variability, as scripts are re-used. In order to assist in creating commands and scenes for virtual actors, we propose a method that can create scripts for agents to plausibly act within a virtual environment. This work is inspired by [Ma 2006], which provides an action to a virtual agent from a single sentence. However, our method works for several agents over longer periods of time.

Deformation, parameterization and analysis of a single locomotion cycle

We present preliminary results of a framework that can synthesize parameterized locomotion with controllable quality from simple deformations over a single step cycle. Our approach enforces feet constraints per phase in order to appropriately perform motion deformation operations, resulting in a generative and controllable model that maintains the style of the input motion. The method is lightweight and has quantifiable motion quality related to the amount of deformation used. It only requires a single cycle of locomotion. An analysis of the deformation is presented with the quantification of the valid portion of the deformed motion space, informing on the parameterization coverage of the deformable motion cycle.

Design and evaluation of a sketch-based gesture animation tool

Hand gestures are one of the most important components of nonverbal communication, conveying both affective and pragmatic information. They involve the path the hand takes through space, the orientation of the hand and the shape of the hand over time, the latter defined by the angles of the finger joints. Being able to rapidly produce gesture animation is important for two distinct tasks. First, it is important for authoring animations when characters are in conversation, a very common task. Second, there is a growing set of animation tools that are designed to create motion for characters that can gesture autonomously in interactive settings and games [Thiebaux et al. 2008; Heloir and Kipp 2009; van Welbergen et al. 2010; Neff et al. 2008]. These tools generally rely on libraries of gesture animations and it is important to be able to generate large numbers of such animations quickly and at low cost in order to build libraries for particular characters and tasks. This paper presents a tool designed to achieve both goals.

How do stylistic motions differ numerically from neutral ones?

Viewers effortlessly decouple action from style for human motion. Regardless of whether style refers to the subtle differences between individuals (John Wayne's walk versus Charlie Chaplin's walk) or to the manner in which the same action is expressed (such as a sad walk versus a nervous walk), the core intent of an action is readily recognizable.

Physics based virtual cutting using j-integral method for gaming applications

Powerful graphic cards have enabled the game engine developers to add deformable assets. Many games require the players to cut/chop/slash game assets. To render interaction of deformable assets with sharp weapons they use pre-defined fracture patterns. These pre-defined fracture patterns are used to break/cut objects and the use of physics is limited due to computational costs of the virtual cutting process. In this work, we present a low cost solution for performing physics based virtual cutting on deformable assets. Our aim is to provide a highly tunable physics based virtual cutting algorithm on GPU to meet the varying needs of a game engine.

Process optimization based on motion capture for videogames assets

In recent years the motion capture techniques have been perfecting, to independent and investigative level worldwide, including new hardware with greater possibilities and new software that allows to use that hardware, thus each of them presents a specialized laboratory for data manipulation. With the advent of the Kinect device developed by Microsoft, the field of motion capture has benefited because this is a device released for all age groups, which aims to recognize the human motion. The main problem with Kinect device, occurs when the user's body is perpendicular to this, confusing position data and showing incorrect positions of bones (occlusion problems in a single visual plane).

(Reverse) k-nearest neighbors for moving objects

We introduce a new, simple method for answering reverse and nearest neighbor queries for moving objects, e.g., mobile players in a multiplayer game, where a trajectory is known to the system for each object, at least in the short-term. See [Rahmati 2014].