An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies

Collision detection tests between objects dominate run time simulation of rigid body animation. Traditionally, hierarchical bounding box tests are used to minimize collision detection time. But the bounding boxes do not take shapes of the objects into account which results in a large number of collision detection tests. We propose an adaptive spatial subdivision of the object space based on octree structure to rectify this problem. We also present a technique for efficiently updating this structure periodically during the simulation.     

3D billiards game with haptic interface

Intuitive human‐computer interaction has been an active research area with the participation of both academic and industrial groups. It is an important technical and psychological element in computer games, digital product design, cybersports, etc. In this paper, we present our work on a 3D billiards game featuring a haptic interface. Most of the existing games available today concentrate on the development of sophisticated physics engines to obtain realistic motion of billiards balls or of sound engines for realistic sound effect. Our focus in this work is on the improved realism on the hitting action of the game with the aid of haptic device. We do so by computing accurate feedback force on the haptic handle, considering the exact point of contact and physically faithful collision response. Also presented is the physically based modeling of the game environment, including the collision interaction among billiards balls, and between the table and billiards balls. As a result, the players can enjoy a more realistic and pleasurable game compared to other existing 3D billiards games. Copyright © 2010 John Wiley & Sons, Ltd.     

Efficient collision detection using a dual OBB-sphere bounding volume hierarchy

We present an efficient algorithm for collision detection between static rigid objects using a dual bounding volume hierarchy which consists of an oriented bounding box (OBB) tree enhanced with bounding spheres. This approach combines the compactness of OBBs and the simplicity of spheres. The majority of distant objects are separated using the simpler sphere tests. The remaining objects are in close proximity, where some separation axes are significantly more effective than others. We select 5 from among the 15 potential separating axes for OBBs. Experimental results show that our algorithm achieves considerable speedup in most cases with respect to the existing OBB algorithms.     

Shape transformation in space-time

We present a method for transforming shapes in a plane. The primary strength of the proposed method is that it can handle scenes containing moving obstacles. We attain a smooth transformation between two given polygonal shapes and ensure that the shape does not collide with any obstacle during the transformation. We minimize a cost function associated with each transformation path that controls its length, smoothness, and collision freedom. Then a population of tentative transformation paths is generated by path planning for an anchor point in the shape. Next, collision detection and shape deformation techniques, applied to keyframes along the paths, minimize the occurrence of collision. Lastly, a genetic algorithm refines the population of transformation paths.     

基于时空相关性碰撞检测算法

在基于层次包围盒碰撞检测算法中,参与相交测试的包围盒的数目会直接影响到碰撞检测的速度.针对这一特点,利用虚拟环境中对象运动的时空相关性对包围盒树进行优化,通过跟踪上一时间点对包围盒树的遍历过程,确定当前时间点的遍历路径,从而有效地减少遍历过程中包围盒相交的次数.实验结果证明,算法能够有效地减少参与测试的包围盒数目,大大提高了碰撞检测的速度.     

Object tracking by energy maximization

We describe a robust algorithm for object tracking in long image sequences which extends the dynamic Hough transform to detect arbitrary shapes undergoing arbitrary affine motion. The proposed tracking algorithm processes the whole image sequence globally. First, the object boundary is represented in lookup-table form, and we then perform an operation that estimates the energy of the motion trajectory in the parameter space. We assign an extra term in our cost function to incorporate smoothness of changes due to rotation or scaling of the object. There is no need for training or initialization, and an efficient implementation can be achieved with coarse-to-fine dynamic programming and pruning. The method is shown to be robust under noise and occlusion and capable of tracking multiple objects.     

虚拟驾驶视景仿真系统中实效性研究

分析了以开发测试汽车电子为目的的虚拟驾驶视景仿真系统的特点,重点探讨虚拟驾驶视景仿真系统中运动车辆与周围环境的碰撞实效性问题,研究并改进了基于OBBTree(Oriented Bounding Box Tree)的层次包围盒碰撞检测算法,最后通过VC++和OSG编程实现该算法的验证。实验证明,使用该算法进行碰撞检测的虚拟驾驶视景仿真系统在实效性方面取得了很好的效果。     

Dual graph partitioning for Bottom-Up BVH construction

Bounding Volume Hierarchies (BVHs) are essential tools in performing collision detection on three-dimensional information. They reduce the number of expensive calculations required to determine whether or not two geometrical entities collide by using inexpensive calculations to rule out parts of the objects that could not possibly intersect. Quickly producing a high quality BVH is an important aspect of three-dimensional multimedia analysis. As such a powerful optimization, efficient and high quality BVHs are still an active area of research. Herein, the authors present a novel BVH representation that reduces the redundancy in the tree structure by allowing a node to contain an arbitrary number of children, as well as compressing non-unique nodes and combining their children. A new partitioning scheme using a graphical representation of the object is also presented to improve the quality of the generated BVH.     

共线三球链问题的碰撞动力学研究

共线三球链的碰撞动力学问题能够展示多刚体系统碰撞问题的困难之一：非唯一解的问题.本文建立了三球链碰撞的Hertz接触模型,研究对其求解的数值算法,并用有限元模型（FEM）对其进行验证,研究表明：同线性模型比较,采用Hertz接触力模拟小球之间的接触力更接近有限元计算结果;在Hertz接触模型基础上,分析碰撞过程中接触力的变化过程;研究刚度比和质量比对于碰撞结束后各个小球运动状态的影响,并研究了两种刚体模型下碰撞次序假设成立的条件.     

Implementation and analysis of an image-based global illuminationframework for animated environments

We describe a new framework for efficiently computing and storing global illumination effects for complex, animated environments. The new framework allows the rapid generation of sequences representing any arbitrary path in a “view space” within an environment in which both the viewer and objects move. The global illumination is stored as time sequences of range-images at base locations that span the view space. We present algorithms for determining locations for these base images, and the time steps required to adequately capture the effects of object motion. We also present algorithms for computing the global illumination in the base images that exploit spatial and temporal coherence by considering direct and indirect illumination separately. We discuss an initial implementation using the new framework. Results and analysis of our implementation demonstrate the effectiveness of the individual phases of the approach; we conclude with an application of the complete framework to a complex environment that includes object motion     

An Integrated System for Modeling,Animating and Rendering Hair

There are basically four problems to solve in order to produce realistic animated synthetic actors with hair: hair modeling and creation, hair motion, collision detection and hair rendering. This paper describes a complete methodology to solve these basic four problems. We present how hair styles may be designed with our Hair Styler module. Then we survey the animation model and emphasize a method of collision processing. Finally, we explain how hair may be rendered using an extension of a standard ray-tracing program. We also show applications of our synthetic actors with various hair styles and different styles of mustaches and beards.     

Automatic Registration for Articulated Shapes

We present an unsupervised algorithm for aligning a pair of shapes in the presence of significant articulated motion and missing data, while assuming no knowledge of a template, user‐placed markers, segmentation, or the skeletal structure of the shape. We explicitly sample the motion, which gives a priori the set of possible rigid transformations between parts of the shapes. This transforms the problem into a discrete labeling problem, where the goal is to find an optimal assignment of transformations for aligning the shapes. We then apply graph cuts to optimize a novel cost function, which encodes a preference for a consistent motion assignment from both source to target and target to source. We demonstrate the robustness of our method by aligning several synthetic and real‐world datasets.     

Safety assessment of robot trajectories for navigation in uncertain and dynamic environments

This paper presents a probabilistic framework for reasoning about the safety of robot trajectories in dynamic and uncertain environments with imperfect information about the future motion of surrounding objects. For safety assessment, the overall collision probability is used to rank candidate trajectories by considering the probability of colliding with known objects as well as the estimated collision probability beyond the planning horizon. In addition, we introduce a safety assessment cost metric, the probabilistic collision cost, which considers the relative speeds and masses of multiple moving objects in which the robot may possibly collide with. The collision probabilities with other objects are estimated by probabilistic reasoning about their future motion trajectories as well as the ability of the robot to avoid them. The results are integrated into a navigation framework that generates and selects trajectories that strive to maximize safety while minimizing the time to reach a goal location. An example implementation of the proposed framework is applied to simulation scenarios, that explores some of the inherent computational trade-offs.     

Collision-free motion of an articulated kinematic chain in adynamic environment

A method for the collision avoidance of an articulated kinematic chain in a dynamic environment is presented. The inverse kinematic solution is used to get the configuration of the chain for a given position of any part of the chain. The calculation of collision-free motion is based on the local information about the motion. Intermediate positions are used to get the new motion path of the chain. The movement of environmental objects during the collision detection and the generation of new motions are considered. This generalizes the method for arbitrarily configured kinematic chains and for a dynamic environment. Its implementation for the motion planning of robot manipulators in an offline programming system is briefly described     

Range Scan Registration Using Reduced Deformable Models

We present an unsupervised method for registering range scans of deforming, articulated shapes. The key idea is to model the motion of the underlying object using a reduced deformable model. We use a linear skinning model for its simplicity and represent the weight functions on a regular grid localized to the surface geometry. This decouples the deformation model from the surface representation and allows us to deal with the severe occlusion and missing data that is inherent in range scan data. We formulate the registration problem using an objective function that enforces close alignment of the 3D data and includes an intuitive notion of joints. This leads to an optimization problem that we solve using an efficient EM-type algorithm. With our algorithm we obtain smooth deformations that accurately register pairs of range scans with significant motion and occlusion. The main advantages of our approach are that it does not require user specified markers, a template, nor manual segmentation of the surface geometry into rigid parts.     

Minimizing probable collision pairs searched in interactive animation authoring

Animation authoring involves an author’s interaction with a scene, resulting in varying scene complexity for a given animation sequence. In such a varying environment, detection and prediction of collision in minimal time and with high accuracy is a challenge. This paper proposes using the bounding volume-based space subdivision mechanism to reduce search space for an object pair collision search. This data structure is enhanced using a direction-based spatial hash table, which predicts collision between static and dynamic objects. These techniques are shown to work in conjunction with existing search space reduction methods. The event of collision is accurately detected using known methods, such as kinetic data structures. Simulation results show that for a scene with 10000 objects with varying dynamic objects (10–90%), the method finds probable collision-pairs with 95–99% accuracy.     

虚拟漫游中的碰撞检测问题的解决方法

碰撞检测是虚拟漫游中的关键技术。在进行虚拟漫游时,为了避免观察者飞人地下或穿墙而过等不真实情况的发生,就需要进行碰撞检测。解决虚拟漫游中碰撞检测问题的一种方法是：将场景中运动的观察者转化为一个视点,场景中的物体表面剖分成三角形,运动的观察者与静态的虚拟场景之间的碰撞检测问题,就转化为点与三角形之问的碰撞检测问题;此方法的优化方法是对场景中的三角形进行过滤,以减少不必要的计算。文中给出了此方法的具体算法及其优化方法。     

Hierarchical part-type segmentation using voxel-based curve skeletons

We present an effective framework for segmenting 3D shapes into meaningful components using the curve skeleton. Our algorithm identifies a number of critical points on the efficiently computed curve skeleton, either fully automatically as the junctions of the curve skeleton, or based on user input. We use these points to construct a partitioning of the object surface using geodesics. Because the segmentation is based on the curve skeleton, it intrinsically reflects the shape symmetry and articulation, and can handle shapes with tunnels. We describe a voxel-based implementation of our method which is robust and noise resistant, able to handle shapes of complex articulation and topology, produces smooth segment borders, and delivers hierarchical level-of-detail segmentations. We demonstrate the framework on various real-world 3D shapes. Additionally, we discuss the use of both curve and surface skeletons to produce part-type and patch-type, respectively, segmentations of 3D shapes.     

Modeling with Time and Events in Computer Animation

In this paper, we present a general, systematic and consistent treatment of time and events for computer animation. We first formalize the concepts of events and create a time primitive called an event unit. We then present a succession of organization schemes to compose event units for generating complex motion sequences. We present a directed graph representation for the organization of time and events that suggests the form of an event-based time programming language. Details of implementation of a general event simulation system are given. Our approach provides a clean partitioning for the problem of motion design, a hierarchical scheme to compose motion behaviors from time primitives and a programming model for organizing animation. Traditional methods of kinematic controls and key frame interpolation are special cases of our general scheme. In addition, our treatment of events can be combined with kinematics, dynamics or constraint-based systems to generate powerful motion modeling systems.