Coordinated Crowd Simulation With Topological Scene Analysis

This paper proposes a new algorithm to produce globally coordinated crowds in an environment with multiple paths and obstacles. Simple greedy crowd control methods easily lead to congestion at bottlenecks within scenes, as the characters do not cooperate with one another. In computer animation, this problem degrades crowd quality especially when ordered behaviour is needed, such as soldiers marching towards a castle. Similarly, in applications such as real‐time strategy games, this often causes player frustration, as the crowd will not move as efficiently as it should. Also, planning of building would usually require visualization of ordered evacuation to maximize the flow. Planning such globally coordinated crowd movement is usually labour intensive. Here, we propose a simple solution that is easy to use and efficient in computation. First, we compute the harmonic field of the environment, taking into account the starting points, goals and obstacles. Based on the field, we represent the topology of the environment using a Reeb Graph, and calculate the maximum capacity for each path in the graph. With the harmonic field and the Reeb Graph, path planning of crowd can be performed using a lightweight algorithm, such that any blocking of one another's paths is minimized. Comparing to previous methods, our system can synthesize globally coordinated crowd with smooth and efficient movement. It also enables control of the crowd with high‐level parameters such as the degree of cooperation and congestion. Finally, the method is scalable to thousands of characters with minimal impact to computation time. It is best applied in interactive crowd synthesis systems such as animation designs and real‐time strategy games.     

Planning interactive task for intelligent characters

Motion planning is an important problem in character animation and interactive simulation. However, few planning methods have considered domain‐specific knowledge that governs the agent's behaviors, and none of them is capable of planning the interactive task in which the agent interacts with the objects in the virtual environment. This paper presents a novel method to plan the interactive task based on Q‐learning for intelligent characters. The approach can be described as a three‐phase framework: data preprocessing phase, controller learning phase, and motion‐synthesis phase. In the data preprocessing phase, we abstract the motion clips as high‐level behaviors and construct the interactive behavior graph (IBG) to define the interactive capabilities of the agent in terms of interactive features. For the controller training phase, with IBG, Q‐learning algorithm is employed to train the control policy in the discrete domain with interactive features. In the motion‐synthesis phase, the optimal motion sequences can be generated by following the policy to accomplish the interactive task finally. The experimental results demonstrate that the uniform framework can generate reasonable and realistic motion sequences to plan interactive task in complex environment. Copyright © 2012 John Wiley & Sons, Ltd.     

Exaggerating Character Motions Using Sub‐Joint Hierarchy

Motion capture cannot generate cartoon‐style animation directly. We emulate the rubber‐like exaggerations common in traditional character animation as a means of converting motion capture data into cartoon‐like movement. We achieve this using trajectory‐based motion exaggeration while allowing the violation of link‐length constraints. We extend this technique to obtain smooth, rubber‐like motion by dividing the original links into shorter sub‐links and computing the positions of joints using Bézier curve interpolation and a mass‐spring simulation. This method is fast enough to be used in real time.     

面向三维动画自动生成的路径规划

全过程计算机辅助自动生成动画技术由中科院陆汝钤院士于上世纪90年代提出,这一技术的目标是将适当的故事以受限自然语言的方式输入计算机,由开始一直到动画的生成,每一步都是在计算机的辅助下完成.在动画生成过程中,如何规划运动对象路径是影响动画效果的重要因素.为此,提出基于动画场景规划信息的路径规划方法,该方法通过预定义的路径定性规划语言PADL描述规划需求,然后通过利用扩展的A*算法规划路径并生成路径定量规划语言PCAL描述的路径,最后采用运动图方法合成路径运动动画.实验表明,该方法能有效地自动生成符合指定要求的路径动画.     

Data‐Driven Crowd Motion Control With Multi‐Touch Gestures

Controlling a crowd using multi‐touch devices appeals to the computer games and animation industries, as such devices provide a high‐dimensional control signal that can effectively define the crowd formation and movement. However, existing works relying on pre‐defined control schemes require the users to learn a scheme that may not be intuitive. We propose a data‐driven gesture‐based crowd control system, in which the control scheme is learned from example gestures provided by different users. In particular, we build a database with pairwise samples of gestures and crowd motions. To effectively generalize the gesture style of different users, such as the use of different numbers of fingers, we propose a set of gesture features for representing a set of hand gesture trajectories. Similarly, to represent crowd motion trajectories of different numbers of characters over time, we propose a set of crowd motion features that are extracted from a Gaussian mixture model. Given a run‐time gesture, our system extracts the K nearest gestures from the database and interpolates the corresponding crowd motions in order to generate the run‐time control. Our system is accurate and efficient, making it suitable for real‐time applications such as real‐time strategy games and interactive animation controls.     

Data‐Driven Shape Interpolation and Morphing Editing

Shape interpolation has many applications in computer graphics such as morphing for computer animation. In this paper, we propose a novel data‐driven mesh interpolation method. We adapt patch‐based linear rotational invariant coordinates to effectively represent deformations of models in a shape collection, and utilize this information to guide the synthesis of interpolated shapes. Unlike previous data‐driven approaches, we use a rotation/translation invariant representation which defines the plausible deformations in a global continuous space. By effectively exploiting the knowledge in the shape space, our method produces realistic interpolation results at interactive rates, outperforming state‐of‐the‐art methods for challenging cases. We further propose a novel approach to interactive editing of shape morphing according to the shape distribution. The user can explore the morphing path and select example models intuitively and adjust the path with simple interactions to edit the morphing sequences. This provides a useful tool to allow users to generate desired morphing with little effort. We demonstrate the effectiveness of our approach using various examples.     

Natural Hairstyle Modeling and Animation

In this paper, we develop a hairstyle modeling and animation technique specifically designed for human hairs, and we report several experimental results. Using simplified cantilever beam model and one-dimensional projective differential equations of angular momenta, we give a practical solution to the problem of enormous complexity. Even though our hair animation algorithm is an approximate solution, it includes all the relevant dynamic elements such as gravity, wind, inertia, air-resistance, hair-to-head, and hair-to-hair friction forces. Collision is an important element that makes a collection of hair strands look like hair. We develop an accurate but efficient hair-to-head and hair-to-hair collision detection and treatment algorithm. The algorithm produces quite realistic results; still it runs at an interactive speed. An interesting contribution of our algorithm is that it unifies hairstyle modeling and animation into a single equation, so that (1) hairstyling can be done under the effects of gravity and other internal or external forces, and (2) original hairstyle is more or less restored even after the initial hair is tangled by the application of external forces or head movements.     

Parallel line integral convolution

Line integral convolution (LIC) is a powerful method for computing directional textures from vector data. LIC textures can be animated, yielding the effect of flowing motion. Both, static images and animation sequences are of great significance in scientific visualization. Although an efficient algorithm for computing static LIC textures is known, the generation of animation sequences still requires a considerable amount of computing time. In this paper we propose an algorithm for computing animation sequences on a massively parallel distributed memory computer. With this technique it becomes possible to utilise animated LIC for interactive vector field visualization. To take advantage of the strong temporal coherence between different frames, parallelization is performed in image space rather than in time. Image space coherence is exploited using a flexible update and communication scheme. In addition algorithmic improvements on LIC are proposed that can be applied to parallel and sequential algorithms as well.     

Cords: geometric curve primitives for modeling contact

Curves are perhaps the most versatile of modeling primitives in computer graphics. They define a rough structure for many surface-generation algorithms and are often fit to meaningful surface features for further shape modeling. Deformable objects such as hair and fur are simulated on finite element curve discretizations. Motion paths for planning and animation applications are tied to underlying curves. In this article we present a geometric curve primitive, known as a cord, which allows for interactive modeling of curves that contact complex geometry.     

Hatching for Motion Picture Production

This paper presents a hatching algorithm which – while also allows for an implementation in real‐time – is integrated into the production pipeline of computer generated motion picture. Motion picture production pipelines impose special functional and quality requirements. From the functional point of view, the stages of modeling, 3D rendering, and compositing form a pipeline without feed‐back, and frames are rendered independently, possibly on different computers. Thus, no temporal data can be shared between them while flicker free animation needs to be generated. Quality requirements can be grasped as that of dual consistency: the generated hatching must consistently follow object movement and deformation, and, at the same time, it should have a consistent pattern and density in image‐space to provide the hand‐crafted look. In order to meet both requirements, we apply a particle based method and develop an image‐space density control mechanism using rejection sampling and low‐discrepancy sequences. We also discuss the decomposition of rendering tasks according to the main stages of the production pipeline and demonstrate how the artist can define the illustration style in a convenient way.     

Chain Shape Matching for Simulating Complex Hairstyles

Animations of hair dynamics greatly enrich the visual attractiveness of human characters. Traditional simulation techniques handle hair as clumps or continuum for efficiency; however, the visual quality is limited because they cannot represent the fine‐scale motion of individual hair strands. Although a recent mass‐spring approach tackled the problem of simulating the dynamics of every strand of hair, it required a complicated setting of springs and suffered from high computational cost. In this paper, we base the animation of hair on such a fine‐scale on Lattice Shape Matching (LSM), which has been successfully used for simulating deformable objects. Our method regards each strand of hair as a chain of particles, and computes geometrically derived forces for the chain based on shape matching. Each chain of particles is simulated as an individual strand of hair. Our method can easily handle complex hairstyles such as curly or afro styles in a numerically stable way. While our method is not physically based, our GPU‐based simulator achieves visually plausible animations consisting of several tens of thousands of hair strands at interactive rates.     

Physically Based Deformable Models in Computer Graphics

Physically based deformable models have been widely embraced by the Computer Graphics community. Many problems outlined in a previous survey by Gibson and Mirtich have been addressed, thereby making these models interesting and useful for both offline and real‐time applications, such as motion pictures and video games. In this paper, we present the most significant contributions of the past decade, which produce such impressive and perceivably realistic animations and simulations: finite element/difference/volume methods, mass‐spring systems, mesh‐free methods, coupled particle systems and reduced deformable models‐based on modal analysis. For completeness, we also make a connection to the simulation of other continua, such as fluids, gases and melting objects. Since time integration is inherent to all simulated phenomena, the general notion of time discretization is treated separately, while specifics are left to the respective models. Finally, we discuss areas of application, such as elastoplastic deformation and fracture, cloth and hair animation, virtual surgery simulation, interactive entertainment and fluid/smoke animation, and also suggest areas for future research.     

Easy Generation of Facial Animation Using Motion Graphs

Facial animation is a time‐consuming and cumbersome task that requires years of experience and/or a complex and expensive set‐up. This becomes an issue, especially when animating the multitude of secondary characters required, e.g. in films or video‐games. We address this problem with a novel technique that relies on motion graphs to represent a landmarked database. Separate graphs are created for different facial regions, allowing a reduced memory footprint compared to the original data. The common poses are identified using a Euclidean‐based similarity metric and merged into the same node. This process traditionally requires a manually chosen threshold, however, we simplify it by optimizing for the desired graph compression. Motion synthesis occurs by traversing the graph using Dijkstra's algorithm, and coherent noise is introduced by swapping some path nodes with their neighbours. Expression labels, extracted from the database, provide the control mechanism for animation. We present a way of creating facial animation with reduced input that automatically controls timing and pose detail. Our technique easily fits within video‐game and crowd animation contexts, allowing the characters to be more expressive with less effort. Furthermore, it provides a starting point for content creators aiming to bring more life into their characters.     

Computation of intraprocedural dynamic program slices

Dynamic slicing algorithms are used in interactive applications such as program debugging and testing. Therefore, these algorithms need to be very efficient. In this context, we propose three intraprocedural dynamic slicing algorithms which are more space and time efficient than the existing algorithms. Two of the proposed algorithms compute precise dynamic slices of structured programs using Program Dependence Graph as an intermediate representation. To compute precise dynamic slices of unstructured programs, we introduce the concepts of jump dependence and Unstructured Program Dependence Graph. The third algorithm uses Unstructured Program Dependence Graph as the intermediate program representation, and computes precise dynamic slices of unstructured programs. We show that each of our proposed algorithms is more space and time efficient than the existing algorithms.     

Continuum Traffic Simulation

We present a novel method for the synthesis and animation of realistic traffic flows on large‐scale road networks. Our technique is based on a continuum model of traffic flow we extend to correctly handle lane changes and merges, as well as traffic behaviors due to changes in speed limit. We demonstrate how our method can be applied to the animation of many vehicles in a large‐scale traffic network at interactive rates and show that our method can simulate believable traffic flows on publicly‐available, real‐world road data. We furthermore demonstrate the scalability of this technique on many‐core systems.     

HairControl: A Tracking Solution for Directable Hair Simulation

We present a method for adding artistic control to physics‐based hair simulation. Taking as input an animation of a coarse set of guide hairs, we constrain a subsequent higher‐resolution simulation of detail hairs to follow the input motion in a spatially‐averaged sense. The resulting high‐resolution motion adheres to the artistic intent, but is enhanced with detailed deformations and dynamics generated by physics‐based simulation. The technical core of our approach is formed by a set of tracking constraints, requiring the center of mass of a given subset of detail hair to maintain its position relative to a reference point on the corresponding guide hair. As a crucial element of our formulation, we introduce the concept of dynamically‐changing constraint targets that allow reference points to slide along the guide hairs to provide sufficient flexibility for natural deformations. We furthermore propose to regularize the null space of the tracking constraints based on variance minimization, effectively controlling the amount of spread in the hair. We demonstrate the ability of our tracking solver to generate directable yet natural hair motion on a set of targeted experiments and show its application to production‐level animations.     

Animated 3D Line Drawings with Temporal Coherence

Producing traditional animation is a laborious task where the key drawings are first drawn by artists and thereafter inbetween drawings are created, whether it is by hand or computer‐assisted. Auto‐inbetweening of these 2D key drawings by computer is a non‐trivial task as 3D depths are missing. An alternate approach is to generate all the drawings by extracting lines directly from animated 3D models frame by frame, concatenating and rendering them together into an animation. However, animation quality generated using this straightforward method bears two problems. Firstly, the animation contains unsatisfactory visual artifacts such as line flickering and popping. This is especially pronounced when the lines are extracted using high‐order derivatives, such as ridges and valleys, from 3D models represented in triangle meshes. Secondly, there is a lack of temporal continuity as each drawing is generated without taking its neighboring drawings into consideration. In this paper, we propose an improved approach over the straightforward method by transferring extracted 3D line drawings of each frame into individual 3D lines and processing them along the time domain. Our objective is to minimize the visual artifacts and incorporate temporal relationship of individual lines throughout the entire animation sequence. This is achieved by creating correspondent trajectory of each line from each frame and applying global optimization on each trajectory. To realize this target, we present a fully automatic novel approach, which consists of (1) a line matching algorithm, (2) an optimizing algorithm, taking into account both the variations of numbers and lengths of 3D lines in each frame, and (3) a robust tracing method for transferring collections of line segments extracted from the 3D models into individual lines. We evaluate our approach on several animated model sequences to demonstrate its effectiveness in producing line drawing animations with temporal coherence.     

远程教学课件中动画技术的研究与实现

首先介绍了远程教育中采用动画课件的作用与意义,分析比较了使用Flash来开发远程网络教学动画课件的特点和优势,重点对交互式动画技术进行了研究,并以《数据结构》课程的算法动画课件制作为例介绍其开发过程及相关问题。     

Fast iterative refinement of articulated solid dynamics

A new dynamics algorithm for articulated solid animation is presented. It provides enhancements of computational efficiency and accuracy control with respect to previous solutions. Iterative refinement allows us to perform interactive animations which could be only computed off-line using previous methods. The efficiency results from managing two sets of constraints associated with the kinematic graph, and proceeding in two steps. First, the acyclic constraints are solved in linear time. An iterative process then reduces the closed-loop errors while maintaining the acyclic constraints. This allows the user to efficiently trade off accuracy for computation time. We analyze the complexity and investigate practical efficiency compared with other approaches. In contrast with previous research, we present a single method which is computationally efficient for acyclic bodies as well as for mesh-like bodies. The accuracy control is provided by the iterative improvement performed by the algorithm and also from the existence of two constraint priority levels induced by the method. Used in conjunction with a robust integration scheme, this new algorithm allows the interactive animation of scenes containing a few thousand geometric constraints, including closed loops. It has been successfully applied to real-time simulations