Motion in Games

Using natural user interface to interact with digital worlds is becoming commonplace in our daily life, as evidenced by the high demand for Microsoft Kinect since its launch in 2010. However, comparatively little research effort has focused in the past on harnessing these capabilities to create great applications. In this paper, we introduce unified framework for combining natural user interface and physics-based character animation. Our framework takes the form of a continuous controllable space for the combination of the two techniques. We also propose a human-in-the-loop control paradigm which allows a player or performer to sense and act for the character. With the information encapsulated in the human performance, the proposed framework accomplishes its goal in two steps: first, by recognizing and potentially modifying the performance such that it is appropriate for the given scenario; and second, by balancing interactivity and control in order to maintain both physical responsivity to the virtual world and faithfulness to the human performance.

Individualized virtual agents can enhance the user’s perception of a virtual scenario. However, most systems only provide customization for visual features of the characters. In this paper, we describe an approach to individualizing the non-verbal behavior of virtual agents. To this end, we present a software framework which is able to visualize individualized non-verbal behavior. For demonstration purposes, we designed four behavioral profiles that simulate prototypical behaviors for differences in personality and gender. These were then tested in an evaluation study.

In modern games, rendering a massive scene with a large number of animated character is imminent and a very challenging task. In this paper, we present a real-time crowd rendering system on GPUs with a special focus on how to preserve texture appearance in progressive LOD-based mesh simplification algorithms. Our results show that the proposed parallel LOD approach can get up to 5.33 times of speedup compared with the standard pseudo-instancing approach.

We propose a novel Inverse Kinematics based deformation method that introduces flexibility and parameterization to motion graphs without degrading the quality of the synthesized motions. Our method deforms the transitions of a motion graph-like structure by first assigning to each transition a continuous rotational range that guarantees not to exceed the predefined global transition cost threshold. The deformation procedure improves the reachability of motion graphs to precise locations and consequently reduces the time spent during search. Furthermore, our method includes a new motion graph construction method based on geometrical segmentation features, and employs a fast triangulation based search pruning technique that confines the search to a free channel and avoids expensive collision checking. The results obtained by the proposed methods were evaluated and quantified, and they demonstrate significant improvements in comparison with traditional motion graph approaches.

The creation of plausible human animation remains a perennial problem in computer graphics. To construct long animations it is common to stitch together a sequence of motions from a motion database. Typically, this is done in two stages: planning a route and then sampling motions from the database to follow that route. We introduce an environment-aware motion sampling technique that combines the planning and sampling stages. Our observation is that in the traditional approach the route generated in the first stage over-constrains the motion sampling so that it is relatively implausible that a human would follow this animation. We combine the motion sampling and planning and show that we can find shorter and more plausible animations.

This paper describes the real-time modeling of 3D skeletal motion with balancing properties. Our goal is to mimic human responsiveness when external forces are applied to the model. To achieve this we use an inverted pendulum as a basis for achieving a self-balancing model. We demonstrate responsiveness in stepping and posture control via a simplified biped skeletal model using our technique.

Determining injury levels for virtual characters is an important aspect of many games. For characters that are animated using simulated physics, it is possible assess injury levels based on physical properties, such as accelerations and forces. We have constructed a model for injury assessment that relates results from research on human injury response to parameters in physics-based animation systems. We describe a set of different normalized injury measures for individual body parts, which can be combined into a single measure for total injury. Our research includes a user study in which human observers rate the injury levels of physics-based characters falling from varying heights at different orientations. Results show that the correlation between our model output and perceived injury is stronger than the correlation between perceived injury and fall height (0.603 versus 0.466, respectively, with

N

 = 1020 and

p

 < 0.001).

Dexterous physical interactions with virtual creatures are important to bring the fun of playing with animals into arts and entertainment. For reality of interaction, virtual creatures need to react to highly varied user inputs in a variety of ways according to physical and psychological laws. We propose constructing virtual creatures using a physical simulator, sensor/attention models, and physical motion controllers. The physical simulator and motion controllers generate highly varied physically real reactions, while sensor/attention models provide psychologically feasible target selection for motion controllers. Having constructed a virtual creature prototype, we realize communicative physical interactions such as guessing and attracting attention by touching it via a haptic device. We have confirmed the prototype’s effectiveness experimentally.

We describe a system for animating virtual characters that encompasses many important aspects of character modeling for simulations and games. These include locomotion, facial animation, speech synthesis, reaching/grabbing, and various automated non-verbal behaviors, such as nodding, gesturing and eye saccades. Our system implements aspects of character animation from the research community that yield high levels of realism and control.

In this paper, we show results of controlling a 3D articulated human body model by using a repulsive energy function. The idea is based on the energy-based unfolding and interpolation, which are guaranteed to produce intersection-free movements for closed 2D linkages. Here, we apply those approaches for articulated characters in 3D space. We present the results of two experiments. In the initial experiment, starting from a posture that the body limbs are tangled with each other, the body is controlled to unfold tangles and straighten the limbs by moving the body in the gradient direction of an energy function based on the distance between two arbitrary linkages. In the second experiment, two different postures of limbs being tangled are interpolated by guiding the body using the energy function. We show that intersection free movements can be synthesized even when starting from complex postures that the limbs are intertwined with each other. At the end of the paper, we discuss about the limitations of the method and future possibilities of this approach.

We propose a method of generating avoidance motions. We use a motion graph to generate continuous motions, including both avoidance and other kinds of motions. In the combat of real humans, trained fighters avoid an attack with minimal movement. To realize such avoidance motion, we developed criteria to find an appropriate path (series of edges) in the motion graph. The characters are expected to move their body by only a minimal distance to avoid an attack. We introduced attack, body and avoidance space–time volumes to evaluate this criterion. Each candidate path is evaluated according to the distance between attack and body volumes and the overlap between attack and avoidance volumes. We also introduced a method to control the execution speeds of edges, and thus adjust the timing of avoidance motions. Moreover, to find a path in real time, we developed methods to facilitate the searching process such as the use of grid-based indices to look up candidate paths and GPU-based quick collision detection to cull candidate paths. We tested our approach on an application in which a character avoids incoming balls controlled by a user and demonstrated the effectiveness of our approach.

There are currently a number of animation researchers that focus on simulating virtual crowds, but few are attempting to simulate virtual populations. Virtual crowd simulations tend to depict a large number of agents walking from one location to another as realistically as possible. The virtual humans in these crowds lack higher purpose. They have a virtual existence, but not a virtual life and as such do not reasonably depict a human population. In this paper, we present an agent-based simulation framework for creating virtual populations endowed with social roles. These roles help establish reasons for the existence of each of the virtual humans. They can be used to create a virtual population embodied with purpose.

This paper introduces and motivates the application of parameterization to behavior trees. As a framework, behavior trees are becoming more commonly used for agent controllers in interactive game environments. We describe a way by which behavior trees can be authored for acting upon functions with arguments, as opposed to being limited to nonparametric tasks. We expand upon this idea to provide a method by which a subtree itself can be encapsulated with an exposed parameter interface through a lookup node, which enables code reuse in a manner already exploited by object oriented programming languages. Parameterization also allows us to recast Smart Events (a mechanism for co-opting agents to perform a desired activity) as behavior trees that can act generically upon groups of typed agents. Finally, we introduce a tool called Topiary, which enables the graphically-oriented authoring of behavior trees with this functionality as part of a broader testbed for agent simulation.

Automatic camera systems produce very basic animations for virtual worlds. Users often view environments through two types of cameras: a camera that they control manually, or a very basic automatic camera that follows their character, minimizing occlusions. Real cinematography features much more variety producing more robust stories. Cameras shoot establishing shots, close-ups, tracking shots, and bird’s eye views to enrich a narrative. Camera techniques such as zoom, focus, and depth of field contribute to framing a particular shot. We present an intelligent camera system that automatically positions, pans, tilts, zooms, and tracks events occurring in real-time while obeying traditional standards of cinematography. We design behavior trees that describe how a single intelligent camera might behave from low-level narrative elements assigned by “smart events”. Camera actions are formed by hierarchically arranging behavior sub-trees encapsulating nodes that control specific camera semantics. This approach is more modular and particularly reusable for quickly creating complex camera styles and transitions rather then focusing only on visibility. Additionally, our user interface allows a director to provide further camera instructions, such as prioritizing one event over another, drawing a path for the camera to follow, and adjusting camera settings on the fly. We demonstrate our method by placing multiple intelligent cameras in a complicated world with several events and storylines, and illustrate how to produce a well-shot “documentary” of the events constructed in real-time.

We describe a model to calculate saliency of objects due to their motions. In a decision-theoretic fashion, perceptually significant objects inside a scene are detected. The work is based on psychological studies and findings on motion perception. By considering motion cues and attributes, we define six motion states. For each object in a scene, an individual saliency value is calculated considering its current motion state and the inhibition of return principle. Furthermore, a global saliency value is considered for each object by covering their relationships with each other and equivalence of their saliency value. The position of the object with highest attention value is predicted as a possible gaze point for each frame in the animation. We conducted several eye-tracking experiments to practically observe the motion-attention related principles in psychology literature. We also performed some final user studies to evaluate our model and its effectiveness.

Many-core architecture has become an emerging and widely adopted platform for parallel computing. Computer animation researches can harness this advance in high performance computing with better understanding of the architecture and careful consideration of several important parallel algorithm design issues, such as computation-to-core mapping, load balancing and algorithm design paradigms. In this paper, we use a set of algorithms in computer animation as the examples to illustrate these issues, and provide possible solutions for handling them. We have shown in our previous research projects that the proposed solutions can greatly enhance the performance of the parallel algorithms.

String-like objects in our daily lives including shoelaces, threads and rubber cords exhibit interesting behaviors such as twisting, tearing and bouncing back when pulled and released. In this paper, we present a method that enables these behaviors in traditional string simulation methods that explicitly represent a string by particles and segments. We offer the following three contributions. First, we introduce a method for handling twisting effects with both uniform and non-uniform torsional rigidities. Second, we propose a method for estimating the tension acting in inextensible objects in order to reproduce tearing and flicking (bouncing back); whereas the tension for an

extensible

object can be easily computed via its stretched length, the length of an

inextensible

object is maintained constant in general, and thus we need a novel approach. Third, we introduce an optimized grid-based collision detection for an efficient computation of collisions. We demonstrate that our method allows visually plausible animations of string-like objects made of various materials and is a fast framework for interactive applications such as games.

Computational cost is one of the major problems in animating smoke. Recently, adaptive grid refinement using octree structure has been proposed, which is a successful method for reducing the computational cost of a detail-preserving fluid simulation. Although octree grid is optimized for details, viewing is not addressed. Smoke distant from the viewing screen which usually has less visual attention and is unnecessary for high-detail simulation can be optimized for speed. However, applying such view-dependent optimization to the octree grid directly may cause animation artifacts and loss in natural fluid behaviours. This paper, we present a method for view-dependent adaptive grid refinement, extending the traditional octree grid by considering the viewing frustum, as well as variation in fluid quantities as criteria for grid refinement. In our method, refinement conditions with adaptive thresholds are proposed to optimize the grid for both view and details. Additionally, our method preserves visual details and fluid behaviours which allows high-detail smoke animations in relatively less amount of computational cost consumption, especially when applied for large scale simulations.

Realistic animation and rendering of the metal shell is an important aspect for movies, video games and other simulators. Usually this is handled by FEM method, which requires extremely high computational cost due to solving the stiffness matrix. We now propose a trick that could smartly avoid the large scale computation required by FEM, and could still generate visually convincing images of metal shell. We do so by first partitioning the shell into k rigid sub-shells that evolve independently during impact, before using a simple spring-mass model is applied between each adjacent vertex to retain continuity of the shell. This technique could produce realistically looking deformed rigid shells in real-time and can easily be integrated in any game engine and physics engine.

In the pursuit of pushing active character control into games, we have deployed a generalized physics-based locomotion control scheme to multiple simulation platforms, including ODE, PhysX, Bullet, and Vortex. We first overview the main characteristics of these physics engines. Then we illustrate the major steps of integrating active character controllers with physics SDKs, together with necessary implementation details. We also evaluate and compare the performance of the locomotion control on different simulation platforms. Note that our work only represents an initial attempt at doing such evaluation, and additional refinement of the methodology and results can still be expected. We release our code online to encourage more follow-up works, as well as more interactions between the research community and the game development community.

In this paper we introduce an approach to high-level parameterisation of captured mesh sequences of actor performance for real-time interactive animation control. High-level parametric control is achieved by non-linear blending between multiple mesh sequences exhibiting variation in a particular movement. For example walking speed is parameterised by blending fast and slow walk sequences. A hybrid non-linear mesh sequence blending approach is introduced to approximate the natural deformation of non-linear interpolation techniques whilst maintaining the real-time performance of linear mesh blending. Quantitative results show that the hybrid approach gives an accurate real-time approximation of offline non-linear deformation. Results are presented for single and multi-dimensional parametric control of walking (speed/direction), jumping (heigh/distance) and reaching (height) from captured mesh sequences. This approach allows continuous real-time control of high-level parameters such as speed and direction whilst maintaining the natural surface dynamics of captured movement.

We present an online algorithm for interactive character animation in realtime. Interactive character animation is to select a sequence of actions that perform well. Each action sequence is evaluated by the sum of discounted costs over a finite horizon. A large number of action sequences are evaluated simultaneously by parallelization of genetic algorithms on GPU. Benefiting from the power of parallel computing on modern GPU, our method produces high quality animations in realtime.

The statistical analysis of multi-agent simulations requires a definitive set of benchmarks that represent the wide spectrum of challenging scenarios that agents encounter in dynamic environments, and a scoring method to objectively quantify the performance of a steering algorithm for a particular scenario. In this paper, we first recognize several limitations in prior evaluation methods. Next, we define a measure of

normalized effort

that penalizes deviation from desired speed, optimal paths, and collisions in a single metric. Finally, we propose a new set of benchmark categories that capture the different situations that agents encounter in dynamic environments and identify truly challenging scenarios for each category. We use our method to objectively evaluate and compare three state of the art steering approaches and one baseline reactive approach. Our proposed scoring mechanism can be used (a) to evaluate a single algorithm on a single scenario, (b) to compare the performance of an algorithm over different benchmarks, and (c) to compare different steering algorithms.

Steering techniques are widely used for navigation of single agents or crowds and flocks. Steerings also have the potential to coordinate movement of human-like agents in very small groups so that the resulting behavior appears socially believable, but this dimension is less explored. Here, we present one such “social” steering, the Walk Along steering for navigating a couple of agents to reach a certain place together. The results of a believability study with 26 human subjects who compared the new steering to the known Leader Following steering in eight different scenarios suggest the superiority of the Walk Along steering in social situations.

Game developers are often faced with very demanding requirements on huge numbers of agents moving naturally through increasingly large and detailed virtual worlds. With the advent of multi-core architectures, new approaches to accelerate expensive pathfinding operations are worth being investigated. Traditional single-processor pathfinding strategies, such as A* and its derivatives, have been long praised for their flexibility. We implemented several parallel versions of such algorithms to analyze their intrinsic behavior, concluding that they either have a large overhead, yield far from optimal paths, do not scale up to many cores, or are cache unfriendly. In this paper we propose

Parallel Ripple Search

, a novel parallel pathfinding algorithm that largely solves these limitations. It utilizes a high-level graph to assign local search areas to CPU cores at ’equidistant’ intervals. These cores then use A* flooding behavior to expand towards each other, yielding good ’guesstimate points’ at border touch on. The process does not rely on expensive parallel programming synchronization locks, but instead relies on the opportunistic use of node collisions among cooperating cores, exploiting the multi-core’s shared memory architecture. As a result, all cores effectively run at full speed until enough way-points are found. We show that this approach is a fast, practical and scalable solution, and that it flexibly handles dynamic obstacles in a natural way.

In modern day games, it is often desirable to have many agents navigating intelligently through detailed environments. However, intelligent navigation remains a computationally expensive and complicated problem. In the past, the continuum crowds algorithm demonstrated the value of using a dynamic potential field to guide many agents to a common goal location. However this algorithm is prohibitively resource intensive for real time applications using large and detailed virtual worlds. In this paper, we propose a novel hybrid system that first uses a coarse A* path finding step. This helps to eliminate unnecessary work during the potential field generation by excluding areas of the world from the potential field calculation. Additionally, we show how an optimized potential field solver can be implemented on the GPU using the concepts of persistent threads and inter-block communication. Results show that our system achieves considerable speedups compared to existing path planning systems and that up to 100,000 agents can be simulated and rendered in real time on a mainstream GPU.

Numerous path planning solutions have been proposed to solve the navigation problem in static environments, potentially populated with dynamic obstacles. However, in dynamic environments, moving objects can be used to reach new locations. In this paper, we propose an online planning algorithm for dynamically changing environments with unknown evolution. This method focuses on accessibility and on the use of objects movements to reach a given target. Among other examples, we will show that this algorithm is able to find a path through moving platforms to reach a target located on a surface that is never directly accessible. We will also show that the proposed representation enables several kind of adaptations such as avoiding moving obstacles or adapting the character postures to environmental constraints.

Most current games perform navigation in virtual environments through A* for path finding combined with a local movement algorithm. Navigation Meshes are the most popular approach to combine path finding with local movement. This paper presents a new Automatic Navigation Mesh Generator (ANavMG) that subdivides any polygon representing the environment, with or without holes, into a suboptimal number of convex cells where local movement algorithms can be applied without deadlocks. We introduce the concept of convex relaxation to further reduce the number of cells depending on the flexibility of the local movement algorithm. Finally we show results of the ANavMG and its application to a multi player game.

In this paper we describe a roadmap-based approach for a multi-agent search strategy to clear a building or multi-story environment. This approach utilizes an encoding of the environment in the form of a graph (roadmap) that is used to encode feasible paths through the environment. The roadmap is partitioned into regions, e.g., one per level, and we design region-based search strategies to cover and clear the environment. We can provide certain guarantees within this roadmap-based framework on coverage and the number of agents needed. Our approach can handle complex and realistic environments where many approaches are restricted to simple 2D environments.

In this paper, we address the problem of automatically creating a meaningful spatial representation of 3D virtual environments, suitable for spatial reasoning. We propose a spatial analysis technique that distinguishes indoor, outdoor and covered parts of the environment. It also separates buildings into floors linked by stairs and represent floors as rooms linked by doorsteps. On this basis, we compute a natural hierarchical representation of the environment. We also demonstrate that this representation can be used to handle multi-criterion queries relating to spatial reasoning including zone selection and path planning.

Reconstruction is a key step of the motion capture process. The quality of motion data first results from the quality of raw data. However, it also depends on the motion reconstruction step, especially when raw data suffer markers losses or noise due, for example, to challenging conditions of capture. Labeling is a final and crucial data reconstruction step that enables practical use of motion data (e.g., analysis). The lower the data quality, the more time consuming and tedious the labeling step, because human intervention cannot be avoided: he has to manually indicate markers label each time a loss of the marker in time occurs. In the context of crowd study, we faced such situation when we performed experiments on the locomotion of groups of people. Data reconstruction poses several problems such as markers labeling, interpolation and mean position computation. While Vicon IQ software has difficulties to automatically label markers for the crowd experiment we carried out, we propose a specific method to label our data and estimate participants mean positions with incomplete data.

We present a novel methodology to quantitatively evaluate the synthesized motion generated by a motion-based animation technique. Our quantitative evaluation methodology provides a measure of how well each algorithm synthesizes motion based on their rotational and translational similarities to the ground truth in a motion database. To demonstrate the effectiveness of our methodology, we focus on techniques that combine different motions into a single spliced action where individual motions are performed simultaneously. We implement three splicing algorithms to perform a comparison study based on our quantitative evaluation methodology. The splicing algorithms considered are spatial body alignment, segmentation-based, and naïve DOF replacement. The spatial body alignment adapts the spliced motion according to this joint correlation and, consequently, performs best under our evaluation methodology.

Efficient cloth simulation is an important problem for interactive applications that involve virtual humans, such as computer games. A common aspect of many methods that have been developed to simulate cloth is a linear system of equations, which is commonly solved using conjugate gradient or multi-grid approaches. In this paper, we introduce to the computer gaming community a recently proposed preconditioner, the

incomplete Poisson

preconditioner (IPP ), for conjugate gradient solvers. We show that IPP performs as well as the current state-of-the-art preconditioners, while being much more amenable to standard thread-level parallelism. We demonstrate our results on an 8-core Mac Pro and a 32-core Emerald Rigde system.

We present a novel, biomechanically-inspired, kinematic- based, example-driven walking synthesis model. Our model is ideally suited towards interactive applications such as games. It synthesizes motion interactively without

a priori

knowledge of the trajectory. The model is very efficient, producing foot-skate free, smooth motion over a large, continuous range of speeds and while turning, in as little as 5

μ

s. We’ve formulated our model so that an artist has extensive control over how the walking gait manifests itself at all speeds.

This paper is motivated by the objective of improving the realism of real-time simulated crowds by reducing short term collision avoidance through long term anticipation of pedestrian trajectories. For this aim, we choose to reuse outdoor pedestrian trajectories obtained with non-invasive means. This initial step is achieved by analyzing the recordings of multiple synchronized video cameras. In a second off-line stage, we fit as long as possible trajectory segments within predefined paths made of a succession of region goals. The concept of region goal is exploited to enforce the principle of “sufficient satisfaction”: it allows the pedestrians to relax the prescribed trajectory to the traversal of successive region goals. However, even if a fitted trajectory is modified due to collision avoidance, we are still able to make long-term trajectory anticipation and distribute the collision avoidance shift over a long distance.

We introduce a new method that greatly improves the iterative edge length constraint enforcement frequently used in real-time cloth simulation systems for preventing overstretching. Our method is based on the directional enforcement of constraints and on the simultaneous progressive scanning of the cloth edges, starting from fixed vertices and propagating on the direction of gravity. The proposed method successfully detects the meaningful springs to be corrected and ignores the ones that do not have any significance on the overall visual result. The proposed approach is simple and robust and is able to achieve realistic cloth simulations without overstretching, without causing any visual artifacts, and dramatically decreasing the computational cost of the constraint enforcement process.

Motion indexing concerns efficient ways to identify and retrieve motions similar to a query motion from a large set of motions stored in a human motion database. In this paper, we perform the first quantitative evaluation and comparison of motion indexing techniques. We extend PCA-based algorithms for motion segmentation to address the motion indexing problem and perform a survey of the most significant motion indexing techniques in the literature. We implement five different techniques for motion indexing: two principal component analysis (PCA) based methods, a feature-based method, and two dynamic time warping (DTW) based methods. The indexing accuracy is evaluated for all techniques and a quantitative comparison among them is achieved. The two PCA-based techniques have the lowest number of false negatives but, at the same time, they have a large number of false positives (close to 90%). The feature-based and DTW quaternion-based techniques perform better than the PCA-based techniques. While the DTW-3D technique has a small number of false positives, the false negatives are also very few. The Dynamic Time Warping 3D-based technique performed best among all techniques when compared by false positives and false negatives metrics.

In this paper we present a method to detect the three dimensional position and orientation of a Wii Remote with one or more emissive spheres attached to it, providing an input device that has six degrees of freedom. Unlike other systems, our system can focus in different directions surrounding the user, with a high precision, and at a low cost. We describe the way object-, motion- and orientation tracking is done, as well as the applicability of the final product. We further describe how to improve the noisy data that is retrieved from the sensors of the Wii Remote, how to smooth detected positions, and how to extrapolate position and orientation.