Collision detection with relative screw motion

We introduce a framework for collision detection between a pair of rigid polyhedra. Given the initial and final positions and orientations of two objects, the algorithm determines whether they collide, and if so, when and where. All collisions, including collisions at different times, are computed at once along with properness values that measure the extent to which the collisions are between parts of the objects that properly face each other. This is useful for handling multiple (nearly) concurrent collisions and contact points.The relative motions of the rigid bodies are limited to screw motions. This limitation is not always completely accurate, but we can estimate the error introduced by the assumption.Our implementation uses rasterization to approximate the position and time of the collisions. This allows level-of-detail techniques that provide a tradeoff between accuracy and computational expense.The collision detection algorithms are only approximate, both because of the screw motion assumption and because of the rasterization. However, they can be made robust so as to give consistent information about collisions and to avoid sensitivity to roundoff errors.     

基于FDH包围盒的布料碰撞检测

在布料仿真中,碰撞检测与响应十分复杂,很难同时具备真实感和实时性。针对此问题,采用质点弹簧模型进行建模,基于FDH包围盒提出一种快速的检测基本几何元素间碰撞的方法。通过分析点的位置向量与三角平面的夹角,利用向量内积的性质来判断点与三角形的位置关系,同时进行了相应的碰撞响应处理。实验结果表明,采用该方法进行碰撞检测既保证了模拟的真实性,同时又提高了系统的实时性。     

Adequate motion simulation and collision detection for soccer playing humanoid robots

In this paper a humanoid robot simulator based on the multi-robot simulation framework (MuRoSimF) is presented. Among the unique features of this simulator is the scalability in the level of physical detail in both the robot’s motion and sensing systems. It facilitates the development of control software for humanoid robots which is demonstrated for several scenarios from the RoboCup Humanoid Robot League.Different requirements exist for a humanoid robot simulator. E.g., testing of algorithms for motion control and postural stability require high fidelity of physical motion properties whereas testing of behavior control and role distribution for a robot team requires only a moderate level of detail for real-time simulation of multiple robots. To meet such very different requirements often different simulators are used which makes it necessary to model a robot multiple times and to integrate different simulations with high-level robot control software.MuRoSimF provides the capability of exchanging the simulation algorithms used for each robot transparently, thus allowing a trade-off between computational performance and fidelity of the simulation. It is therefore possible to choose different simulation algorithms which are adequate for the needs of a given simulation experiment, for example, motion simulation of humanoid robots based on kinematical, simplified dynamics or full multi-body system dynamics algorithms. In this paper also the sensor simulation capabilities of MuRoSimF are revised. The methods for motion simulation and collision detection and handling are presented in detail including an algorithm which allows the real-time simulation of the full dynamics of a 21 DOF humanoid robot. Merits and drawbacks of the different algorithms are discussed in the light of different simulation purposes. The simulator performance is measured and illustrated in various examples, including comparison with experiments of a physical humanoid robot.     

Collision detection for moving polyhedra

We consider the collision-detection problem for a three-dimensional solid object moving among polyhedral obstacles. The configuration space for this problem is six-dimensional, and the traditional representation of the space uses three translational parameters and three angles (typically Euler angles). The constraints between the object and obstacles then involve trigonometric functions. We show that a quaternion representation of rotation yields constraints which are purely algebraic in a seven-dimensional space. By simple manipulation, the constraints may be projected down into a six-dimensional space with no increase in complexity. The algebraic form of the constraints greatly simplifies computation of collision points, and allows us to derive an efficient exact intersection test for an object which is translating and rotating among obstacles.     

Collision detection for interactive graphics applications

Collision detection and response are important for interactive graphics applications such as vehicle simulators and virtual reality. Unfortunately, previous collision detection algorithms are too slow for interactive use. The paper presents a new algorithm for rigid or articulated objects that meets performance goals through a form of time critical computing. The algorithm supports progressive refinement, detecting collisions between successively tighter approximations to object surfaces as the application allows it more processing time. The algorithm uses simple four dimensional geometry to approximate motion, and hierarchies of spheres to approximate three dimensional surfaces at multiple resolutions. In a sample application, the algorithm allows interactive performance that is not possible with a good previous algorithm. In particular, the new algorithm provides acceptable accuracy while maintaining a steady and high frame rate, which in some cases improves on the previous algorithm's rate by more than two orders of magnitude     

Edge detection and motion detection

This paper presents an integrated theory of edge detection, curvature measurement and motion detection during the earliest stages of visual processing. No assumptions are necessary about the viewed objects or about surface properties and the viewing geometry. New methods are outlined for edge detection, curvature measurement and correspondence matching by successive refinement.     

Collision detection algorithm robust to model uncertainty

With the widespread use of service robots, safety issues regarding human-robot collisions have received increasing attention. The collision detection algorithm, which allows a robot to effectively detect and react against a collision, is considered as one of the most practical solutions for ensuring collision safety. However, these algorithms are often model-based, so it cannot ensure collision safety under payload variations or model uncertainty. In this paper, a novel collision detection algorithm based on torque filtering is proposed to cope with this problem. The torque due to the motion of the robot can be effectively removed using the Butterworth 2nd-order BPF (band pass filter) so that only the torque due to a collision is used for collision detection. This improves the robustness of the algorithm against model uncertainties. The proposed algorithm does not require the use of acceleration data. The performance of the algorithm was experimentally verified.     

Cyclic motion detection for motion based recognition

The motion of a walking person is analyzed by examining cycles in the movement. Cycles are detected using autocorrelation and Fourier transform techniques of the smoothed spatio-temporal curvature function of trajectories created by specific points on the object as it performs cyclic motion. A large impulse in the Fourier magnitude plot indicates the frequency at which cycles are occurring. Both synthetically generated and real walking sequences are analyzed for cyclic motion. The real sequences are then used in a motion based recognition application in which one complete cycle is stored as a model, and a matching process is performed using one cycle of an input trajectory.     

基于碰撞识别的优先级仲裁策略

针对单一信道下可用资源的分配问题,提出了基于碰撞识别的优先级仲裁策略,在研究了曼彻斯特编码特点的基础上,设计了一种新的编码方案,推导了优先级生成的模型,分析了仲裁的效率。仿真结果表明,在采用基于时分复用的MAC协议的前提下,同传统的逐节点询问方式相比,仲裁时间缩短为原来的四分之一。     

基于拓扑层次图的碰撞检测算法

为了提高虚拟环境中碰撞检测的实时性和精确性,提出了一种基于拓扑层次图的碰撞检测方法。利用拓扑结构的连接关系将模型分割成凸集;然后利用凸集较强的适应性和OBB紧密性好的优点构造包围盒的拓扑层次图,提高了剔除不相交包围盒的效率,减少了检测时间;利用智能搜索算法——改进的A*算法搜索潜在碰撞集(PCS),进一步提高相交检测的速度和准确性。实验表明,该算法具有较高的速度和精度,能够满足复杂虚拟环境碰撞检测实时性和精确性的要求。     

A ship motion simulation system

In this article, efficient computational models for ship motions are presented. These models are used to simulate ship movements in real time. Compared with traditional approaches, our method possesses the ability to cope with different ship shapes, engines, and sea conditions without the loss of efficiency. Based on our models, we create a ship motion simulation system for both entertainment and educational applications. Our system assists users to learn the motions of a ship encountering waves, currents, and winds. Users can adjust engine powers, rudders, and other ship facilities via a graphical user interface to create their own ship models. They can also change the environment by altering wave frequencies, wave amplitudes, wave directions, currents, and winds. Therefore, numerous combinations of ships and the environment are generated and the learning becomes more amusing. In our system, a ship is treated as a rigid body floating on the sea surface. Its motions compose of 6 degrees of freedom: pitch, heave, roll, surge, sway, and yaw. These motions are divided into two categories. The first three movements are induced by sea waves, and the last three ones are caused by propellers, rudders, currents, and winds. Based on Newton’s laws and other basic physics motion models, we deduce algorithms to compute the magnitudes of the motions. Our methods can be carried out in real time and possess high fidelity. According to ship theory, the net effects of external forces on the ship hull depend on the ship shape. Therefore, the behaviors of the ship are influenced by its shape. To enhance our physics models, we classify ships into three basic types. They are flat ships, thin ships, and slender ships. Each type of ship is associated with some predefined parameters to specify their characteristics. Users can tune ship behaviors by varying the parameters even though they have only a little knowledge of ship theory.     

基于分类遍历的碰撞检测优化算法

针对现有层次树遍历方法的低效率问题,提出了一种基于分类遍历的碰撞检测算法.首先根据两个物体树中节点的平衡因子差值来将所有的物体对进行分类:结构相似的,采用同步下降遍历方法;结构不相似的,采用交换下降遍历方法,这减少了相交测试的次数.然后加入时空相关性和优先级策略优化遍历过程.最后通过实验结果表明,相比基于统一遍历的碰撞检测算法,该算法缩短了相交测试的时间,物体数目越多,快速性优势越显著,大约可以缩减所需时间的1/5.     

基于混合包围盒的碰撞检测算法

提出了一种基于k-dops包围盒与包围球相结合的碰撞检测算法。预处理阶段为几何对象构造包围盒二叉树,其中节点的内层构造k-dops包围盒,节点的外层构造包围球。碰撞检测阶段,首先利用包围球快速排除不可能发生相交的物体,然后利用k-dops包围盒进一步精确地判断物体对是否发生相交。通过与QuickCD算法的性能进行比较,证明了这种混合包围盒能够有效地提高复杂结构几何体之间碰撞检测的效率。     

导弹飞行视景仿真中的碰撞检测算法

针对导弹飞行视景仿真中碰撞检测实时性与精确性的不足,提出了一种优化的混合包围盒碰撞检测算法.该算法在包围盒树的上层使用Sphere,下层使用OBB;将该算法在导弹飞行视景仿真系统中实现后,分别与相交矢量碰撞检测算法、OBB包围盒算法进行对比试验和分析.结果表明,这种混合包围盒算法能够有效地提高导弹飞行视景仿真中碰撞检测的实时性与精确性.     

Large eddy simulation and ALE mesh motion in Rayleigh-Taylor instability simulation

Many large eddy simulation (LES) techniques have been developed for stationary computational meshes. This study applies a single equation LES to Arbitrary Lagrangian-Eulerian (ALE) simulations of Rayleigh-Taylor instability and investigates its effects. Behavior of LES is similar for Eulerian and ALE simulations for the test problem studied. However, the motion of the mesh can be tied to the subgrid scale model in the form of a relaxation weight based on subgrid scale energy. This increases mesh resolution in areas of high subgrid scale energy.     

虚拟装配中基于相对于位置的碰撞干涉检测

对基于虚拟装配的碰撞检测和碰撞干涉问题进行了描述,提出了碰撞干涉检测的相对位置法。实验表明,该方法能够很好地满足虚拟装配系统的实时性和交互性要求。     

Automatic motion detection for surveillance

Automatic motion detection features are able to enhance surveillance efficiency and quality. The aim of this research is to recognize and detect motion automatically around a robot's environment in order to equip a mobile robot for a surveillance task. The required information is based on the input obtained from a charge coupled device (CCD) camera mounted on the mobile robot. As the first step toward achieving the goal, it is necessary to have a stationary mobile robot and moving objects. Experiments in a different environment, such as different movements, size of moving objects, and lighting conditions, have also been conducted. The “adjacent pixels comparison” is the proposed method to detect motion in this experiment. The results have verified that the motion detection experiments operate as expected. This work was presented in part at the 11^th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

一种自适应的运动区域检测算法

提出了一种简单有效的自适应阂值选择机制,并将背景信息嵌入到阈值选择中,提高了阈值选择的准确性。实验结果表明,该算法能在各种环境变化情况下自动得到合适的阈值,提高了运动区域检测的准确性。     

一种运动检测算法研究*

混合高斯背景模型算法被广泛地运用于运动检测中,但是该算法在一些复杂的室外场景下未能有效地反映背景,容易出现误检测。为此提出一种改进的算法,该算法在更新背景模型时对不同的区域采用不同的更新速率,并在进行前景检测时加入一种阈值判断,最后对检测结果进行去噪处理。实验结果表明,改进后的算法能够更好地处理多模态区域,减少前景检测中出现的空洞,避免由于方差过度收敛引起的误检测,从而更精确地实现运动目标分割。