1,721,041 research outputs found
On Streams and Incentives: A Synthesis of Individual and Collective Crowd Motion
No full textWe present a crowd simulation model that combines the advantages of agent-based and flow-based paradigms while only relying on local information. Our model can handle arbitrary and dynamically changing crowd densities, and it enables agents to gradually interpolate between individual and coordinated behavior. Our model can be used with any existing global path planning and local collision-avoidance method. We show that our model reduces the occurrence of deadlocks and yields visually convincing crowd behavior for high-density scenarios while maintaining individual agent behavior at lower densities
Navigation for Characters and Crowds in Complex Virtual Environments
No full textIn a crowd simulation, virtual walking characters need to compute and traverse paths through a virtual environment while avoiding collisions. Simulations of large crowds occur increasingly often in computer games, in which real-time performance is required. Also, there is an increasing demand for crowd simulations of real-world scenarios. For example, crowd simulations can be used to predict dangerous situations during crowded events such as festivals, or to estimate if a sports stadium can be evacuated within a certain amount of time. Thus, path planning and crowd simulation are important research topics. Part I of this gives an overview of these topics and related work. A navigation mesh is an efficient representation of a virtual environment for the purpose of real-time path planning and crowd simulation. When planning a path in a navigation mesh, we actually compute a sequence of regions for the character to move through. Within these regions, the character can compute an indicative route, which it can then follow in real-time while avoiding other moving characters. The rest of this thesis investigates how to use navigation meshes to model and simulate complex scenarios. Part II of this thesis revolves around the navigation mesh itself. It describes: A navigation mesh for efficient path planning for disk-shaped characters of any size in a 2D virtual environment.An extension of this navigation mesh to multi-layered environments, such as buildings with multiple floors connected by staircases. Many algorithms that existed in 2D can be extended to handle multi-layered environments as well.Algorithms for locally updating a navigation mesh when an obstacle appears or disappears during the simulation; for example, imagine a vehicle blocking a street, or a bridge collapsing.A comparative study of various navigation meshes that have been developed in the past decade. It provides a theoretical comparison as well as a practical comparison based on novel quality metrics. In Part III of this thesis, we develop new methods for path planning and crowd simulation in navigation meshes: An algorithm that efficiently recomputes a path after the navigation mesh has been updated locally. This improves the efficiency of crowd simulations in large dynamic environments.An algorithm that maps the current crowd density onto the navigation mesh, such that characters can take this density into account when planning their paths. This algorithm is based on fundamental diagrams that describe the empirically observed relation between crowd density and (typical) walking speeds.A generic five-level framework that describes how crowd simulation software can be structured. We demonstrate an implementation of this framework that can simulate tens of thousands of characters in real-time. Part IV concludes that these algorithms and implementations can be used to efficiently simulate increasingly complex scenarios. The most important topics for future work are the automatic extraction of a multi-layered environment from raw 3D geometry, the extension of characters with sophisticated AI without losing efficiency, and the evaluation of how well a crowd simulation corresponds to real-world behavior
Approximate Translational Building Blocks for Image Decomposition and Synthesis
Full text linkWe introduce approximate translational building blocks for unsupervised image parsing. Such building blocks are frequently appearing copies of image patches that are mapped coherently under translations. We exploit the coherency assumption to find approximate building blocks in noisy and ambiguous image data, using a spectral embedding of co-occurrence patterns. We quantitatively evaluate our method on a large benchmark data set and obtain clear improvements over state-of-the-art methods. We apply our method to texture synthesis by integrating building blocks constraints and their offset statistics into a conventional Markov Random Field model. A user study shows improved retargeting results even if the images are only partially described by a few classes of building blocks
Interactive Character Deformation Using Simplified Elastic Models
No full textThis thesis describes the results of our research into realistic skin and model deformation methods aimed at the field of character deformation and animation. The main contributions lie in the properties of our deformation scheme. Our approach preserves the volume of the deformed object while retaining shape details. Furthermore, we also consider interior dynamics such as muscles, which are key to producing realistic skin deformation. We model skin elasticity either by physically modeling and simulating the musculoskeletal system and the skin, or by minimizing an elastic energy constructed over a representation of the subject surface. We propose a number of simplifications so that we are able to produce plausible elastic deformations at interactive, or even real-time rates. As such, our methods are attractive to real-time graphics applications such as computer games. Based on scattered data interpolation and domain decomposition, we developed a space deformation method that supports localized, smooth, limb deformation changes. This method can be combined with the aforementioned methods for elastic deformation to deform the character skin. Finally, we present a novel rig control that can be easily combined with the elastic deformation methods in order to reduce the man effort of producing a skin animation. The rig control results from a deformation metaphor consisting of point handles that are controlled by the user. Based on this rig control, a new skinning scheme is obtained. Our preliminary results show its effectiveness at expanding the space of deformations provided by skeletal skinning
Geometric Algorithms for Part Orienting and Probing
No full textIn this thesis, detailed solutions are presented to several problems dealing with geometric shape and orientation of an object in the field of robotics and automation. We first have considered a general model for shape variations that allows variation along the entire boundary of an object, both in two and three-dimensional space. Based on this model of shape variation, we have studied the problem of orienting planar parts. We have focused on orienting a planar imperfect part with pushing by placing a single friction-less line like jaw in different orientations. We then have shown how the family of possible parts defined by this model can be simultaneously oriented into the smallest possible interval of final orientations after applying a bounded predetermined number of pushes. We have considered the same model and investigated the locus of the center of mass for parts with shape variation. We have considered parts with uniform mass distribution and bounded the location of the center of mass for both two and three-dimensional cases. Pose statistics is a fundamental topic related to part orienting. We have considered a family of 3D objects whose initial pose is uniformly random. We assumed that the object falls onto a flat surface in presence of gravity under quasi-static conditions. We defined a type of geometric eccentricity and showed that 3D eccentric objects with high probability rest at a pose, which is close to a specific plane or specific line. In this work, we also investigated a novel type of geometric probing. The goal is to interactively determine geometric shape and orientation of an unknown objects by using special measurements. We have defined a type of proximity probing which returns the distance to the boundary of the object in question. This work has concentrated on the case where the object is a convex polygon P in the plane. The goal is to find an upper bound on the number of measurements required to exactly determine P. We have proposed an algorithm that the number of requiring probes is linear in the number of vertices. Furthermore, our method is computationally very efficient, requiring only constant computation time per probe, for a total linear time complexity. We also considered the same task of using these proximity probes to identify P, but from a finite set of convex polygons. We presented an algorithm achieving this and bound the number of probes
Robust balance shift control with posture optimization
No full textIn 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
Game-Changing: Fast Dynamic Updates in a Flexible Navigation Mesh
No full textGames and simulations frequently model scenarios where obstacles move, appear, and disappear in an environment. A city environment changes as new buildings and roads are constructed, and routes can become partially blocked by small obstacles many times in a typical day. This paper studies the effect of using local updates to repair only the affected regions of a navigation mesh in response to a change in the environment. The techniques are inspired by incremental methods for Voronoi diagrams. The main novelty of this paper is that we show how to maintain a 2D or 2.5D navigation mesh in an environment that contains dynamic polygonal obstacles. Experiments show that local updates are fast enough to permit real-time updates of the navigation mesh
- …
