MIG '15: Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games

We present a method for automatically generating reduced marker layouts for marker-based optical motion capture of human hand motions. Reducing the number of markers on the hand is important to ensure the generated motions are performed in a natural way and indeed a reduced marker set might be a technical requirement should simultaneous body motion capture also have to be carried out. The employed motion reconstruction method is based on subspace-constrained inverse kinematics, which allows for the recovery of realistic hand movements even from sparse input data. Our marker layout optimization is sensitive to the kinematic structure and the subspace representations of hand articulations utilized in the reconstruction method in order to generate sparse marker configurations that are optimal for solving the constrained inverse kinematics problem. We propose specific quality criteria for reduced marker sets that combine numerical stability with geometric feasibility of the resulting layout. These criteria are combined in an objective function that is minimized using a specialized surface-constrained particle swarm optimization scheme. Our method provides a principled way for determining reduced marker layouts based on subspace representations of hand articulations.

In this paper, we address the problem of sensor-dependent gesture recognition thanks to adaptation procedure. Capturing human movements by a motion capture (MoCap) system provides very accurate data. Unfortunately, such systems are very expensive, unlike recent depth sensors, like Microsoft Kinect, which are much cheaper, but provide lower data quality. Hidden Markov Models (HMMs) are widely used in gesture recognition to learn the dynamics of each gesture class. However, models trained on one type of data can only be used on data of the same type. For this reason, we propose to adapt HMMs trained on Mocap data to a small set of Kinect data using Maximum Likelihood Linear Regression (MLLR) to recognize gestures captured by a Kinect. Results show that using this method, we can achieve a recognition average accuracy of 84.48% using a small set of adaptation data while, using the same set to create new models, we obtain only 72.41% of accuracy.

Many interactive 3D games utilize motion capture for both character animation and user input. These applications require short, meaningful sequences of data. Manually producing these segments of motion capture data is a laborious, time-consuming process that is impractical for real-time applications. We present a method to automatically produce semantic segmentations of general motion capture data by examining the qualitative properties that are intrinsic to all motions, using Laban Movement Analysis (LMA). LMA provides a good compromise between high-level semantic features, which are difficult to extract for general motions, and low-level kinematic features, which often yield unsophisticated segmentations. Our method finds motion sequences which exhibit high output similarity from a collection of neural networks trained with temporal variance. We show that segmentations produced using LMA features are more similar to manual segmentations, both at the frame and the segment level, than several other automatic segmentation methods.

We seek to determine an optimal set of markers for marker-based facial motion capture and animation control. The problem is addressed in two different ways: on the one hand, different sets of empirical markers classically used in computer animation are evaluated; on the other hand, a clustering method that automatically determines optimal marker sets is proposed and compared with the empirical marker sets. To evaluate the quality of a set of markers, we use a blendshape-based synthesis technique that learns the mapping between marker positions and blendshape weights, and we calculate the reconstruction error of various animated sequences created from the considered set of markers in comparison to ground truth data. Our results show that the clustering method outperforms the heuristic approach.

Data-driven motion research requires effective tools to compress, index, retrieve and reconstruct captured motion data. In this paper, we present a novel method to perform these tasks using a deep learning architecture. Our deep autoencoder, a form of artificial neural network, encodes motion segments into "deep signatures". This signature is formed by concatenating signatures for functionally different parts of the body. The deep signature is a highly condensed representation of a motion segment, requiring only 20 bytes, yet still encoding high level motion features. It can be used to produce a very compact representation of a motion database that can be effectively used for motion indexing and retrieval, with a very small memory footprint. Database searches are reduced to low cost binary comparisons of signatures. Motion reconstruction is achieved by fixing a "deep signature" that is missing a section using Gibbs Sampling. We tested both manually and automatically segmented motion databases and our experiments show that extracting the deep signature is fast and scales well with large databases. Given a query motion, similar motion segments can be retrieved at interactive speed with excellent match quality.

Eye movements are an essential part of non-verbal behavior. Non-player characters (NPCs), as they occur in many games, communicate with the player through dialogues and non-verbal behavior and can have a strong influence on the player experience or even on gameplay. In this paper we propose a procedural model to synthesize the subtleties of eye motions. More specifically, our model adds microsaccadic jitter and pupil unrest both modeled by 1/f or pink noise to the standard main sequence. In a perceptual two-alternative forced-choice (2AFC) experiment we explore the perceived naturalness of different parameters of pink noise by comparing synthesized motions to rendered motion of recorded eye movements at extreme close shot and close shot distances. Our results show that, on average, data-driven motion is perceived as most natural, followed by parameterized pink noise, with motion lacking microsaccadic jitter being consistently selected as the least natural in appearance.

3D scans of human figures have become widely available through online marketplaces and have become relatively easy to acquire using commodity scanning hardware. In addition to static uses of such 3D models, such as 3D printed figurines or rendered 3D still imagery, there are numerous uses for an animated 3D character that uses such 3D scan data. In order to effectively use such models as dynamic 3D characters, the models must be properly rigged before they are animated. In this work, we demonstrate a method to automatically rig a 3D mesh by matching a set of morphable models against the 3D scan. Once the morphable model has been matched against the 3D scan, the skeleton position and skinning attributes are then copied, resulting in a skinning and rigging that is similar in quality to the original hand-rigged model. In addition, the use of a morphable model allows us to reshape and resize the 3D scan according to approximate human proportions. Thus, a human 3D scan can be modified to be taller, shorter, fatter or skinnier. Such manipulations of the 3D scan are useful both for social science research, as well as for visualization for applications such as fitness, body image, plastic surgery and the like.

In the current paper, we present a control method based on muscle synergy extraction and adaptation to drive a human arm in a direct dynamics simulation of an overhead throwing motion. The experimental protocol for synergy extraction and model are first presented, followed by a control method consisting of a series of optimizations to adapt muscle parameters and synergies to match experimental data. Results show that the motion can be accurately reproduced thanks to the muscle synergy extraction and adaptation to the model.

In this paper we describe a novel technique for solving the inverse kinematics problem for human fingers. We derive a closed-form solution that places the fingertips precisely in the desired location by allowing minor deviations in the rotations of the Proximal Interphalangeal and Distal Interphalangeal joints compared to the fixed ratio that is known to exist between them. The obvious advantage is that with our approach there is no need to iterate until the distance between the fingertips and the desired locations is small enough. We show that this method is reliable and exact while showing minimal differences to the finger poses generated by the original closed-form solution. In our experiments we found the positions of the intermediate joints of the finger to deviate only around 1.5 mm in the worst case from those resulting from a numerical approximation of the original closed-form solution. On average the deviation is less than 0.5 millimeter.

We present a novel algorithm to model density-dependent behaviours in crowd simulation. Previous work has shown that density is a key factor in governing how pedestrians adapt their behaviour. This paper specifically examines, through analysis of real pedestrian data, how density affects how agents control their rate of change of bearing angle with respect to one another. We extend upon existing synthetic vision based approaches to local collision avoidance and generate pedestrian trajectories that more faithfully represent how real people avoid each other. Our approach is capable of producing realistic human behaviours, particularly in dense, complex scenarios where the amount of time for agents to make decisions is limited.

In high-density crowds, one can observe torso twists; people rotate their upper body to decrease their width perpendicular to the motion path, in order to squeeze through narrow spaces between other crowd members. In this paper we investigate such behaviour, by recording and analysing dense crowds. Apart from the common approach, where only the position of each person in the crowd is recorded, we also record and analyse the torso orientations. To the best of our knowledge, this has not been done before in the context of dense crowds. We show that the paths chosen by the participants can be predicted by Generalized Voronoi Diagrams based on line segment representations of the participants' torsos, and attest that the medial axis of a capsule-shaped representation of the torso is a good choice for such line segments.

Level of service (LoS) is a standard indicator, widely used in crowd management and urban design, for characterizing the service afforded by environments to crowds of specific densities. However, current LoS indicators are qualitative and rely on expert analysis. Computational approaches for crowd analysis and environment design require robust measures for characterizing the relationship between environments and crowd flow.

In this paper, the flow-density relationships of environments optimized for flow under various LoS conditions are explored with respect to three state-of-the-art steering algorithms. We optimize environment elements to maximize crowd flow under a range of density conditions corresponding to common LoS categories. We perform an analysis of crowd flow under LoS conditions corresponding to the LoS optimized environments. We then perform an analysis of the crowd flow for these LoS optimized environments across LoS conditions.

The steering algorithm, the number of optimized environment elements, the scenario configuration and the LoS conditions affect the optimal configuration of environment elements. We observe that the critical density of crowd simulators can increase, or shift LoS, due to the optimal placement of pillars. Depending on the steering model and environment benchmark, pillars are configured to produce lanes or form wall-like structures, in an effort to maximize crowd flow. These experiments serve as a precursor to environment optimization and crowd management motivating the need for further study using real and synthetic crowd datasets across a larger representation of environments.

We propose a method to robustly and efficiently compute a navigation mesh for arbitrary and dynamic 3D environments based on curvature. This method addresses a number of known limitations in state-of-the-art techniques to produce navigation meshes that are tightly coupled to the original geometry, incorporate geometric details that are crucial for movement decisions and robustly handle complex surfaces. We integrate the method into a standard navigation and collision-avoidance system to simulate thousands of agents on complex 3D surfaces in real-time.

Current systems for automatic narrative generation lack modularity in their authoring tools as well as the ability to accommodate a human player's interaction with the characters while simultaneously preserving narrative integrity. In this paper, we propose a logical formalism of a story that incorporates an exposition, rising action, climax, falling action, and a story resolution, conforming to the widely established and studied Freytag model of a narrative. Using computational tools, our system is able to automatically synthesize stories that are grounded in narrative theory. These logical representations of stories are transformed into its equivalent Parameterized Behavior Tree (PBT) representation to facilitate an animated discourse of the narrative by leveraging existing character animations tools. Next, we automatically transform these passive narratives into interactive narratives by introducing narrative revision and nudge -- two extensions that preserve narrative integrity while still allowing the player to assume control of any character at any point in the story, and the freedom to experience the story in any way he sees fit. Our results demonstrate the promise of leveraging computational intelligence for automated interactive narrative synthesis while being firmly established in classical narrative theory.

This paper presents a novel algorithm for real-time path-planning in a dynamic environment such as a computer game. We utilize a real-time sampling approach based on the Rapidly Exploring Random Tree (RRT) algorithm that has enjoyed wide success in robotics. More specifically, our algorithm is based on the RRT* and informed RRT* variants. We contribute by introducing an online tree rewiring strategy that allows the tree root to move with the agent without discarding previously sampled paths. Our method also does not have to wait for the tree to be fully built, as tree expansion and taking actions are interleaved. To our knowledge, this is the first real-time variant of RRT*.

We demonstrate our method, dubbed Real-Time RRT* (RT-RRT*), in navigating a maze with moving enemies that the controlled agent is required to avoid within a predefined radius. Our method finds paths to new targets considerably faster when compared to CL-RRT, a previously proposed real-time RRT variant.

We present a new approach for whole-body motion synthesis that is able to generate high-quality motions for challenging mobile-manipulation scenarios. Our approach decouples the problem in specialized locomotion and manipulation skills, and proposes a multi-modal planning scheme that explores the search space of each skill together with the possible transition points between skills. In order to achieve high-quality results the locomotion skill is designed to be fully data-driven, while manipulation skills can be algorithmic or data-driven according to data availability and the complexity of the environment. Our method is able to automatically generate complex motions with precise manipulation targets among obstacles and in coordination with locomotion.

In this paper we propose a method for the interactive detailed cutting of deformable thin sheets. Our method builds on the ability of frame-based simulation to solve for dynamics using very few control frames while embedding highly detailed geometry - here an adaptive mesh that accurately represents the cut boundaries. Our solution relies on a non-manifold grid to compute shape functions that faithfully adapt to the topological changes occurring while cutting. New frames are dynamically inserted to describe new regions. We provide incremental mechanisms for updating simulation data, enabling us to achieve interactive rates. We illustrate our method with examples inspired by the traditional Kirigami artform.

This paper proposes a pattern-guided framework for immersed rigid body simulations involving unsteady dynamics of a fully immersed or submerged rigid body in a still flow. Instead of the heavy computation of fluid-body coupling simulations, a novel framework considering different flow effects from the surrounding flow is constructed by parameter estimation of force coefficients. We distinguish the flow effects of the inertial, viscous and turbulent effects to the rigid body. It is difficult to clarify the force coefficients of viscous effect in real flow. In this paper we define the control parameters of viscous forces in rigid body simulator, and propose a energy optimization strategy for determining the time series of control parameters. This strategy is built upon a motion graph of motion patterns and the turbulent kinetic energy. The proposed approach achieves efficient and realistic immersed rigid body simulation results, and these results are relevant to the real-time animations of body-vorticity coupling.

We present a phenomenological model for the real-time simulation of paper tearing and sound. The model uses as input rotations of the hand along with the index and thumb of left and right hands to drive the position and orientation of two regions of a sheet of paper. The motion of the hands produces a cone shaped deformation of the paper and guides the formation and growth of the tear. We create a model for the direction of the tear based on empirical observation, and add detail to the tear with a directed noise model. Furthermore, we present a procedural sound synthesis method to produce tearing sounds during interaction. We show a variety of paper tearing examples and discuss applications and limitations.

When creating real or computer graphics movies, the questions of how to layout elements on the screen, together with how to move the cameras in the scene are crucial to properly conveying the events composing a narrative. Though there is a range of techniques to automatically compute camera paths in virtual environments, none have seriously considered the problem of generating realistic camera motions even for simple scenes. Among possible cinematographic devices, real cinematographers often rely on camera rails to create smooth camera motions which viewers are familiar with. Following this practice, in this paper we propose a method for generating virtual camera rails and computing smooth camera motions on these rails. Our technique analyzes characters motion and user-defined framing properties to compute rough camera motions which are further refined using constrained-optimization techniques. Comparisons with recent techniques demonstrate the benefits of our approach and opens interesting perspectives in terms of creative support tools for animators and cinematographers.

The Sea Is Your Mirror is an artistic interactive experience where surface cerebral electromagnetic waves from a participant wearing an EEG sensor headset are depicted in real-time as ocean waves in an animated 3D environment. The aim of this article is to describe the sea wave model used for the sea state animation and how it is connected to the brain computer interface (BCI). The sea state is animated by the groupy choppy wave model that provides nonlinear sea states with wave groups and asymmetric wave shapes. The BCI maps the temporal spectrum of the electroencephalogram onto the elevation spectrum of the sea surface. The resulting setup enables the participant to fly over a dynamic sea state: a metaphor for conscious and unconscious neurofeedback.

Artists, animation and game designers are in demand for solutions to easily populate large virtual environments with crowds that satisfy desired visual features. This paper presents a method to intuitively populate virtual environments by specifying two key features: localized density, being the amount of agents per unit of surface, and localized flow, being the direction in which agents move through a unit of surface. The technique we propose is also time-independant, meaning that whatever the time in the animation, the resulting crowd satisfies both features. To achieve this, our approach relies on the Crowd Patches model. After discretizing the environment into regular patches and creating a graph that links these patches, an iterative optimization process computes the local changes to apply on each patch (increasing/reducing the number of agents in each patch, updating the directions of agents in the patch) in order to satisfy overall density and flow constraints. A specific stage is then introduced after each iteration to avoid the creation of local loops by using a global pathfinding process. As a result, the method has the capacity of generating large realistic crowds in minutes that endlessly satisfy both user specified densities and flow directions, and is robust to contradictory inputs. At last, to ease the design the method is implemented in an artist-driven tool through a painting interface.

Physics-based animation is an increasingly studied subject of computer animation because it allows natural interactions with the virtual environment. Though some existing motion controllers can handle the simulation of interactions between a character and a liquid, only few methods focus on the simulation of the locomotion of immersed bipeds. In this paper, we present a control strategy capable of simulating partially immersed gaits. The impact of the liquid on the character's motion is modeled through simple hydrodynamics. To produce natural looking animations, we design a controller allowing the combination of multiple gait styles, the conservation of balance through intelligent foot placement and precise control of the character's speed. We determine the optimal parameters for the controller by using an optimization process. This optimization is repeated for several scenarios where the character has to walk across a volume of liquid parametrized by its height. Our controller produces natural looking gaits while being capable of online adaptation to the variation of liquid height, to the modification of the liquid density and viscosity and to the variation of the required character's speed.

In this paper we present a control framework which creates robust and natural balance shifting behaviours during standing. Given high-level features such as the position of the center of mass projection and the foot configurations, a kinematic posture satisfying these features is synthesized using online optimization. The physics-based control framework of the system calculates internal joint torques that enable tracking the optimized posture together with balance and pelvis control. Our system results in a very stable pose regardless of the position of the COM projection within the foot support polygon. This is achieved using an online knee bending and hip joint position optimization scheme. Moreover, we improve the robustness of the character under external perturbations by an arm control strategy that regulates the body's angular momentum. The capabilities of the system are demonstrated under different scenarios. The proposed framework doesn't include equations of motions or inverse dynamics. The simulations run in real-time on a standard modern PC without needing any preprocessing like offline parameter optimization. As a result, our system is suitable for commercial real-time graphics applications such as games.

We propose a type of relationship descriptor based on carpet unrolling that computes the joint positions of a character based on the sum of relative vectors originating from a local coordinate system embedded on the surface of a carpet. Given a terrain that a character is to walk over, the carpet is unrolled over the surface of the terrain. The carpet adapts to the geometry of the terrain and curves according to the trajectory of the character. Because trajectories of the body parts are computed as a weighted sum of the relative vectors, the character can smoothly adapt to the elevation of the terrain and the horizontal curves of the carpet. The carpet relationship descriptors are easy to parallelize and hundreds of characters can be animated in real-time by making use of the GPUs. This makes it applicable to real-time applications such as computer games.

In this paper, we address clustering and collision detection in the clustered shape matching simulation framework for deformable bodies. Our clustering algorithm is "fuzzy," meaning that it gives particles weighted membership in clusters. These weights are a significant extension to the basic clustered shape matching framework as they are used to divide particle mass among the clusters. We explore several weighting schemes and demonstrate that the choice of weighting scheme gives artists additional control over material behavior. Furthermore, by design our clustering algorithm yields spherical clusters, which not only results in sparse weight vectors, but also exceptionally efficient collision geometry. We further enhance this simple collision proxy by intersecting with half-spaces to allow for even better, yet still simple and computationally efficient, collision proxies. The resulting approach is fast, versatile, and simple to implement.

We present a fast contact determination scheme for intersecting deformable solids with detailed surface geometry. Given a high resolution closed surface mesh we automatically build a coarse embedding tetrahedralization and a partitioned representation of the surface in a preprocess. During simulation, the contact determination algorithm finds all intersecting pairs of deformed triangles using a memory-efficient barycentric bounding volume hierarchy, connects them into potentially disjoint intersection curves and performs a topological flood process on the exact intersection surfaces to discover a minimal set of contact points. A unique contact normal is computed for each contact volume, based on a continuous definition of surface normals, and used to find contact point correspondences suitable for contact treatment. The algorithm is strongly output-sensitive and we demonstrate robust contact determination at 60 frames per second for a pair of objects with 100K triangles in shallow intersecting contact.

In this paper, we present an efficient method for detecting collisions and self-collisions on articulated models deformed by Position Based Skinning. Position Based Skinning is a real-time skinning method, which produces believable skin deformations, and avoids artifacts such as the well-known "candy-wrapper" effect and joint-bulging. The proposed method employs spatial hashing with a uniform grid to detect collisions and self collisions. All the mesh primitives are mapped to a hash table, where only primitives mapped to the same hash index indicate a possible collision and need to be tested for intersections. Being based on spatial hashing, our method requires neither expensive set-up nor complex data structures and is hence suitable for articulated characters with deformable soft tissues. We exploit the skeletal nature of the deformation to only update the hash table when required. The resulting algorithm is simple to implement and fast enough for real-time applications. We demonstrate the efficiency of our method on various animation examples. A quantitative experiment is also presented to evaluate our method.

Appearance and animation realism of virtual characters in games, movies or other VR applications has been shown to affect audiences levels of acceptance and engagement with these characters. However, when a virtual character is representing us in VR setup, the level of engagement might also depend on the levels of perceived ownership and sense of control (agency) we feel towards this virtual character. In this study, we used advanced face-tracking technology in order to map real-time tracking data of participants' head and eye movements, as well as facial expressions on virtual faces with different appearance realism characteristics (realistic or cartoon-like) and different levels of animation realism (complete or reduced facial movements). Our results suggest that virtual faces are perceived as more appealing when higher levels of animation realism are provided through real-time tracking. Moreover, high-levels of face-ownership and agency can be induced through synchronous mapping of the face tracking on the virtual face. In this study, we provide valuable insights for future games that use face tracking as an input.

We present a novel method for real-time stylized rendering in video games. Recent advances in painterly character authoring and rendering allow artists to create characters represented by 3D geometry as well as 3D paint strokes embedded on and around that geometry. The resulting 3D paintings are rendered in screen space using special-purpose offline rendering algorithms to achieve a unique painterly style. While providing novel styles for offline rendering, existing techniques do not support real-time applications. In this paper, we propose a method to interactively render these complex 3D paintings with a focus on character animation in video games. After observing that off-surface paint strokes can be interpreted as volumetric data in the proximity of 3D meshes, we review existing volumetric texture techniques and show that they are not adapted to paint strokes, which can be sparse and have a significant structure that should be preserved. We propose a method based on fin textures in which mesh edges are extended orthogonally off the surface and textured to replicate the results of the custom offline rendering method. Our algorithm uses a per-pixel normal calculation in order to fade in fin textures along boundary views. Our results demonstrate real-time performance using a commodity game engine while maintaining a painterly style comparable to offline methods.

We present HeapCraft: an open-source suite of interactive data exploration and visualization tools that allows researchers, server administrators and game designers to analyze and potentially influence player behavior in Minecraft. Our framework includes a telemetry system, several tools for visualizing and representing the collected data, and tools for modifying the game experience in controlled ways. Measures that we use to quantify and visualize player behavior and collaboration have been derived from a large data set containing 3451 player-hours from 908 players and 43 different servers. HeapCraft has been demonstrated on a variety of tasks including player behavior classification, as well as quantifying and improving collaboration of players on Minecraft servers. HeapCraft is freely available and serves to democratize game analytics for the Minecraft community at large.

We introduce DeReEs-4V, an algorithm that receives two separate RGBD video streams and automatically produces a unified scene through RGBD registration in a few seconds. The motivation behind the solution presented here is to allow game players to place the depth-sensing cameras at arbitrary locations to capture any scene where there is some partial overlap between the parts of the scene captured by the sensors. A typical way to combine partially overlapping views from multiple cameras is through visual calibration using external markers within the field of view of both cameras. Calibration can be time consuming and may require fine tuning, interrupting gameplay. If the cameras are even slightly moved or bumped into, the calibration process typically needs to be repeated from scratch. In this article we demonstrate how RGBD registration can be used to automatically find a 3D viewing transformation to match the view of one camera with respect to the other without calibration while the system is running. To validate this approach, a comparison of our method against standard checkerboard target calibration is provided, with a thorough examination of the system performance under different scenarios. The system presented supports any application that might benefit from a wider operational field-of-view video capture. Our results show that the system is robust to camera movements while simultaneously capturing and registering live point clouds from two depth-sensing cameras.