Earticle

In large scale game battle scenes or the virtual reality environment, the scale of the collision handling has been getting bigger and the importance of it has been gradually increasing. In order to compare the collision handling algorithms, this paper develops six different benchmark based on the Bullet physics engine. By massive rigid body collision simulations, the number of collision pairs, the CPU utilization, the memory usage, and the computation time are profiled. For the CPU utilization, the Simple algorithm is the best and provides 19.3% less compared to the other algorithms. In terms of the computation time, the Dbvt algorithm is the best and provides 8.85 times speedup than the worst Simple algorithm. The memory usage of the 32bitAxisSweep3 algorithm is the largest and is average 2.57 times more than the other algorithms. The optimal collision handling algorithm can be selected through performance profiling by considering the criteria such as the minimum computation time, the limited computing resources, the collision shapes and the number of rigid bodies.

This paper presents a real-time algorithm for collision detection, collision avoidance and guidance. Three-dimensional point-mass aircraft models are used. For collision detection, conflict probability is calculated by using the Monte-Carlo Simulation. Time at the closest point of approach(CPA) and distance at CPA are needed to determine the collision probability, being compared to certain threshold values. For collision avoidance, one of possible maneuver options is chosen to minimize the collision probability. For guidance to a designated way-point, proportional navigation guidance law is used. Two scenarios on encounter situation are studied to demonstrate the performance of proposed algorithm.

Road facilities such as CCTV poles have potential risk of collision accidents with a car. A collision detection algorithm installed in the facility allows the collision accident to be known remotely. Most collision detection algorithms are operated by simply focusing on whether a collision have occurred, because these methods are used to measure only acceleration data from a 3-axis sensor to detect collision. However, it is difficult to detect other detailed information such as malfunction of the sensor, collision direction and collision strength, because it is not known without witness the accident. Therefore, we proposed enhanced detection algorithm to get the collision direction, and the collision strength from the tilt of the facility after accident using a 9-axis sensor in this paper. In order to confirm the performance of the algorithm, an accuracy evaluation experiment was conducted according to the data measurement cycle and the invocation cycle to an detection algorithm. As a result, the proposed enhanced algorithm confirmed 100% accuracy for 50 weak collisions and 50 strong collisions at the 9-axis data measurement cycle of 10ms and the invocation cycle of 1,000ms. In conclusion, the algorithm proposed is expected to provide more reliable and detailed information than existing algorithm.

본 논문에서는 가상 공간에서 객체와의 상호 작용을 위한 빠른 충돌 감지 방법을 제안하였다. 먼저 메쉬 그룹화 단계에서는, 전체 공간을 일정한 크기의 소공간들로 분할하고, 각각의 소공간에 속하는 메쉬들에 대하여 이들을 모두 포함하는 최소의 기본 입체도형(육면체 혹은 구)의 위치와 크기를 정함으로써 그룹화한다. 충돌 검출 단계에서는, HIP(Haptic Interface Point)가 어떤 그룹을 대표하는 입체도형 내부에 들어 있는지를 검사하여 특정 입체도형과의 충돌이 확인되면 해당 그룹의 메쉬들만을 대상으로 실제 충돌이 일어난 메쉬를 찾는다. 본 논문에서 제안한 방법을 적용한 경우와 적용하지 않은 경우의 연산시간을 측정 및 비교함으로써 제안한 알고리즘의 효용성을 확인하였다.

In this paper, we propose a fast collision detection method for interacting with objects in virtual space. First, in the mesh grouping step, the entire space is divided into small spaces of a predetermined size, and the positions and sizes of the smallest basic stereoscopic shapes (cube or sphere) including all of the meshes belonging to each small space are determined. In the collision detection step, it is checked whether a haptic interface point (HIP) is included in a three-dimensional figure representing a group. When a collision with a specific three-dimensional figure is confirmed, searching is performed only for the meshes in the group to find a mesh on which a possible real collision with HIP occurred. The effectiveness of the proposed algorithm is verified by measuring and comparing the computation time of the proposed method with and without the proposed method.

본 논문에서는 실시간에 강체 운동을 하는 일반적인 모델사이의 효율적인 충돌검사 알고리즘을 제안한다. 기존의 경계볼륨 알고리즘에 계층적 구조를 적용하였다. 이는 볼록한 물체를 위한 보로노이 영역 기반의 충돌검사 알고리즘을 오목한 물체에도 적용할 수 있도록 확장한다. 추가적으로 빠르게 움직이는 물체에 대한 관통을 탐지하기 위해서 물체의 이동 경로에 대한 교차 검사를 진행한다. 구현된 알고리즘은 일반적인 응용에서 기대한 성능 향상을 얻을 수 있다.

본 논문에서는 애니메이션 속도에 무관한 충돌 탐지 알고리즘을 제안한다. 현재까지 개발된 대부분의 충들 탐지 알고리즘들은 점진적(incremental) 알고리즘들로서, 현 시점에서의 가까운 점(근점)을 찾기 위하여 이전 시점의 근점 주위를 먼저 찾는다. 그런데 만일 움직이는 물체가 충돌 반응에 의해서 큰 토크를 받게 된다면 회전 속도가 증가하게 되어, 다음 시점에서의 실제 근점은 현 시점에서의 근점과는 매우 동떨어져 있어 엉뚱한 위치에서 근점을 찾게 되는 단점을 가진다. 그러므로, 최악의 경우에는 각 시점에서 $O(n^2)$, 시간이 소요될 수 있다. 또한 애니메이션 속도에 따라 이러한 점진적 계산 회수가 변하게 되어 전체적인 알고리즘의 소요 시간이 변하게 되는 단점을 가지고 있다. 본 논문에서는 이러한 문제점을 근본적으로 해결하고자 새로운 방법을 제안하고자 한다. 먼저, 기하학 특성을 내포하는 구면 근점 다이아그램을 생성하고, 이를 이용하여 두 물체간의 단일 거리 함수를 생성한다. 충돌 시점을 효율적으로 찾기 위해서 구간 뉴튼 방법을 거리함수에 적용한다.

This paper presents an efficient collision detection algorithm the performance of which is independent of animation speed. Most of the previous collision detection algorithms are incremental and discrete methods, which find out the neighborhood of the extreme vertex at the previous time instance in order to get an extreme vertex at each time instance. However, if an object collides with another one with a high torque, then the angular speed becomes faster. Hence, the candidate by the incremental algorithms may be farther from the real extreme vertex at this time instance. Therefore, the worst time complexity nay be $O(n^2)$, where n is the number of faces. Moreover, the total time complexity of incremental algorithms is dependent on the time step size of animation because a smaller time step yields more frequent evaluation of Euclidean distance. In this paper, we propose a new method to overcome these drawbacks. We construct a spherical extreme vertex diagram on Gauss Sphere, which has geometric properties, and then generate the distance function of a polyhedron and a plane by using this diagram. In order to efficiently compute the exact collision time, we apply the interval Newton method to the distance function.

PC환경에서 슈팅게임 시에 충돌이벤트에 대한 내용과 충돌감지 알고리즘에 대하여 소개하였고, 기존의 사각형 충돌감지 알고리즘 기법에서 단순한 사각형 충돌의 단점을 보완한, 작은 사각형 단위의 충돌 체크 기법을 제안하여 화면디자인과 함께 단순한 슈팅게임을 구현하였다. 실험과 실제 구현한 게임 화면 디자인을 통하여 제안한 알고리즘이 실제 게임에서 적용할 수 있음과 기존의 알고리즘보다 제안한 알고리즘이 우수함을 보였다.

We reviewed the collision event with pc-based shooting games and existing collision detection algorithms. Then we proposed a new collision check technique using a small quadrilateral unit. by which existing quadrilateral collision detection techniques can be made up for. For demonstration we implemented a simple shooting game having its screen output. We proved that the proposed technique can be applied to real computer games by means of showing the experimental results and screen outputs from implemented real games.

A haptic device operated by the user's hand can receive information on position and orientation of the hand and display force and moment generated in the virtual environment to the hand. For realistic haptic display, the detailed information on collision between objects is necessary. In the past, the point-based graphic environment has been used in which the end effector of a haptic device was represented as a point and the interaction of this point with the virtual environment was investigated. In this paper, the shape-based graphic environment is proposed in which the interaction of the shape with the environment is considered to analyze collision or contact more accurately. To this end. the so-called Gilbert-Johnson-Keerthi (GJK) algorithm is adopted to compute collision points and collision instants between two shapes in the 3-D space. The 5- DOF haptic hand controller is used with the GJK algorithm to demonstrate a peg-in-hole operation in the virtual environment in conjunction with a haptic device. It is shown from various experiments that the shape-based representation with the GJK algorithm can provide more realistic haptic display for peg-in-hole operations.

This paper handles self-collision avoidance for a rescue robot with redundant manipulators. In order to detect all available self-collisions in advance, minimum distances between arbitrary robot parts should be monitored in real-time. For the minimum distance estimation, we suggest a modified method from a previous skeleton algorithm which has less computation burden and realize collision avoidance based on a potential function using the proposed algorithm. The resultant command by collision avoidance should not disturb a given primary task, so null-space of joint solution from a CLIK is utilized for collision avoidance by a gradient projection method.

Nowadays, vehicle related researches have been implemented about control, chassis, body and safety but now is to driving comfort, ITS(Intelligent Transportation system) and human factor, etc. As a result of this fact, autonomous vehicle is main research topic over the world but it is still very expensive and unreasonable. In this research, we propose that low costed and abbreviated system which can be applied to vehicle. The real time control and monitoring of longitudinal, lateral, pitching motion is to be solved by system integration and optimization technique. Finally, we show the experimental result about fixed brake range test and acceleration test.

대부분의 자동차 사고는 졸음운전과 같은 운전자의 부주의로 인해 발생한다. 전방 추돌 경보 시스템 (FCWS)은 전방 차량으로부터 추돌 위험을 감지하여 운전자에게 사전에 경고함으로써 사고의 위험을 현저하게 줄여준다. 본 논문은 주행 안전을 위한 저전력 임베디드 기반 FCWS를 소개한다. 단일 카메라로부터 전방 차량에 대해 검출, 추적, 거리를 계산하고 현재 차량의 속도 정보를 통해 충돌시간 (TTC)을 계산한다. 또한 저성능 임베디드 시스템에서 실시간으로 동작하기 위해 높고 낮은 수준의 프로그램 최적화 기법을 소개한다. 이 시스템은 임베디드 시스템에서 사전에 취득해둔 주행 영상을 통해서 테스트 하였다. 최적화 기법을 사용한 결과는 이전에 최적화를 하지 않은 프로세스 보다 실행 시간이 약 170배 향상되었다.

The cause of the majority of vehicle accidents is a safety issue due to the driver's inattention, such as drowsy driving. A forward collision warning system (FCWS) can significantly reduce the number and severity of accidents by detecting the risk of collision with vehicles in front and providing an advanced warning signal to the driver. This paper describes a low power embedded system based FCWS for safety. The algorithm computes time to collision (TTC) through detection, tracking, distance calculation for the vehicle ahead and current vehicle speed information with a single camera. Additionally, in order to operate in real time even in a low-performance embedded system, an optimization technique in the program with high and low levels will be introduced. The system has been tested through the driving video of the vehicle in the embedded system. As a result of using the optimization technique, the execution time was about 170 times faster than that when using the previous non-optimized process.