This paper presents a parallel kd-tree traversal algorithm based on the parallel binary radix tree construction scheme proposed by Tero Karras in 2012. In his paper, Tero Karras proposed parallel tree construction algorithm which can maximize the utilization of GPU threads, but implementation and analysis of kd-tree are not fully discussed. This paper aims to fill the gap for the specific kd-tree cases. As an application for the kd-tree traversal method proposed in this paper, the proposed method has been implemented with NVIDIA’s CUDA framework and tested on NVIDIA’s realtime raytracing library, OptiX. As a result, the proposed method can construct tree structures within the requirement for realtime process, but still needs specialized spatial caching data structure like the “primitive tree” for highly detailed meshes to handle spatial queries as fast as to visualize implicit surfaces under OptiX framework. However, the proposed method can be applied to dynamic collision detection and manage scene and object information for game applications thanks to its fast tree construction process. Also, realtime raytracing can be applied to game applications based on this study.

본 연구에서는 단거리 영역 내에서 대상물표의 정확한 위치를 파악하여 물표와의 충돌을 방지하기 위한 시스템을 개발하였다. 이를 위해 먼저 물표를 속도 모델과 가속도 모델로 표현하여 초기위치로부터의 움직임을 프로세스 잡음과 측정 잡음이 있는 상태에서 위치, 속도 및 가속도를 추정하였다. 추정기법으로는 칼만필터를 적용하였고 시뮬레이션을 통해 제안기법의 유용성을 확인하였다. 다음으로는 레이저센서를 적용하여 이동하는 물표와의 거리를 계측할 수 있는 시스템을 제작하여 물표의 이동 정보를 검출하였다. 이동 물표를 대상으로 속도 모델과 가속도 모델을 적용하여 실험을 수행하였고, 각각의 실험을 통해 불연속적인 측정데이터가 필터링을 통해 매끄럽고 연속적인 측정값으로 얻어지는 것을 확인하였다. 또한 물표 데이터의 계측과 디스플레이를 위한 UI를 구축하였으며, 물표가 일정거리 영역이내에 접근했을 경우 시각, 청각적인 경보를 울릴 수 있는 기능을 부가하였다. 본 연구결과를 통해 저가의 장비로 물표 위치의 추정 성능이 뛰어난 시스템을 구축할 수 있었다.

GPU는 메모리 대역폭이 연산 속도를 결정하는 병목 지점이 된다. 즉, GPU 프로그래밍 시에는 불규칙적인 메모리 액세스나 다중 스레드들 사이에서의 서로 다른 명령 실행 분기가 발생하면 속도가 크게 저하되는 문제가 발생한다. 따라서 게임 엔진 충돌 처리용으로 사용되는 kd-tree와 같은 적응형 탐색(adaptive traverse) 기법은, 불규칙적인 메모리 액세스 및 서로 다른 명령 분기로 인해 지금까지 GPU 구조에 적합하지 않은 것으로 인식되어 왔다. 그러나 최근 NVIDIA의 Fermi 아키텍처의 등장과 함께 CPU에서처럼 GPU 다중 프로세서에도 캐시 메모리가 적용되고 있다. 본 논문에서는 이러한 새로운 GPU 아키텍처의 장점을 활용해서 충돌 처리 시간을 크게 줄일 수 있는 GPU 기반 kd-tree를 제안한다. 제안하는 GPU 기반 병렬 kd-tree는 체크 지점 65536 개에서 최근접 삼각형까지의 거리를 찾는 작업이 Fermi 아키텍처(캐시 적용) 기반에서 단일 코어 CPU 기반 kd-tree에 비해 평균 백 만 배 이상(1.0x106) 빨라졌으며, 이전 세대 Tesla 아키텍처(캐시 미적용) 기반 병렬 kd-tree에 비해서도 약 50 배 가까이 빠른 속도를 보였다.

Smart Door(SD) is a human friendly power-assisted door system for passenger car doors. It offers comfort and safety to passengers and drivers by supplying additional power. In this study, dynamic system model and the equation of motion derivation are derived. And we propose the disturbance observer based collision detection algorithm for safety when opening the door. A disturbance caused by collision has a fast response compared to a friction, uncertainties and so on. The main idea this study is to estimate a variation of disturbance for stably and effectively detecting a collision. In order to evaluate a performance of collision detection, an experiment set up is constructed. The experimental results validate the usefulness of the proposed collision detection algorithm.

본 논문에서는 3D 그래픽에서 빠르고 정확한 충돌검사(Collision-detection)는 공간에서 표준객체를 중심으로 하는 연구가 많이 이루어져 왔다. H/W를 중심으로 3D그래픽 분야의 놀라운 발달과 다양한 충돌 알고리즘 연구를 통하여 3D 객체의 충돌 속도의 향상뿐만 아니라, 최근에는 사실적인 표현에 깊은 관심을 가지고 있다. 이 논문에서는 기존의 연구되어진 표준 3D 객체의 충돌 알고리즘을 특징을 분석하고, 단순한 계층 구조에서 LOD(Level-of-Detail)를 적용한 유향상자에 가변적 밀도의 알고리즘을 제안한다. 이 알고리즘을 이용하여 공간상에서 LOD 알고리즘을 기반으로 하여, 단순히 거리에 따라서 상세화와 간략화를 적용하는 방법에서 탈피하여 유향상자의 밀도의 알고리즘을 차별적으로 적용하여, 3D객체가 공간상에서 충돌검사의 성능을 향상 시켜, 3D 게임에서 효율적인 렌더링과 사실적인 표현을 제안하여 많은 3D 객체의 실시간을 중요시 하는 3D 게임에서 효율성을 높인다.

본 논문에서는 3D 그래픽에서 빠르고 정확한 충돌검사(collision-detection)는 3D공간에서 표준객체를 중심으로 하는 연구가 많이 이루어져 왔다. 3D그래픽 분야에서 H/W의 놀라운 발달과 다양한 3D그래픽 관련 논문에서 3D객체의 충돌 속도의 성능 향상뿐만 아니라 사실적인 표현에 깊은 관심을 가지고 있다. 3D 그래픽 알고리즘 중에서 표준 3D 객체의 다양한 충돌 알고리즘을 특징을 분석하고, 기존의 3D 객체의 단순한 계층 구조에서 LOD(Level-of-Detail)를 이용한 알고리즘를 제안한다. 이 알고리즘을 이용하여 3D공간상에서 LOD(Level-of-Detail) 알고리즘을 적용시켜서, LOD단계가 높은 (가까운) 곳에서는 객체의 유향상자를 자세히 검사하고, LOD단계가 낮은(먼곳)에 위치한 객체의 유향상자는 간략히 검사를 적용3D객체가 3D 공간상에서 충돌검사의 성능을 향상시키고 3D 그래픽에서 중요한 요소인 3차원 공간상의 효율적인 렌더링과 사실적인 표현을 제안하여 실시간을 중요시 하는 3D 게임에서 사실감과 효율성을 높였다.

This paper studied the collision detection of robot manipulators for safe collaboration in human-robot interaction. Based on sensor-based collision detection, external torque is detached from subtracting robot dynamics. To detect collision using joint torque sensor data, a comparative study was conducted using data-based machine learning algorithm. Data was collected from the actual 3 degree-of-freedom (DOF) robot manipulator, and the data was labeled by threshold and handwork. Using support vector machine (SVM), decision tree and k-nearest neighbors KNN method, we derive the optimal parameters of each algorithm and compare the collision classification performance. The simulation results are analyzed for each method, and we confirmed that by an optimal collision status detection model with high prediction accuracy.

This paper deals with the development and application of control algorithms for series elastic relief robots for rescue operations in harsh environment like disasters or battlefield. The joint controller applied in this paper has a cascade structure combining inner loop for torque control and outer loop for position control. The torque loop contains feedforward and feedback controller and disturbance observer for independent, decentralized joint control. The effect of the elastic component and motor dynamics are treated as the nonlinear disturbance and compensated with the disturbance observer of torque controller. For the collision detection, Band Designed Disturbance Observer is configured to recognize/respond to external disturbance robustly in the continuously changing environment. The controller is applied to a 7-dof series elastic manipulator to evaluate the torque tracking and collision detection/response performance.

In this paper, we propose a new collision detection algorithm for human-robot collaboration. We use an IMU sensor located at the tip of the manipulator and the kinematic behavior of the manipulator to detect the unexpected collision between the robotic manipulator and environment. Unlike other method, the developed algorithm uses only the kinematic relationship between the manipulator joint and the end effector. Therefore, the collision estimation signal is not affected by the error of the dynamics model. The proposed collision detection algorithm detects the collision by comparing the estimated acceleration of the end effector derived from the position, velocity and acceleration trajectories of the robot joints with the actual acceleration measured by the sensor. In simulation, we compare the performance of our method with the conventional Residual Observer (ROB). Our method is less sensitive to the load variation because of the independency on the dynamic modeling of the manipulator.

Human-robot co-operation becomes increasingly frequent due to the widespread use of service robots. However, during such co-operation, robots have a high chance of colliding with humans, which may result in serious injury. Thus, many solutions were proposed to ensure collision safety, and among them, collision detection algorithms are regarded as one of the most practical solutions. They allow a robot to quickly detect a collision so that the robot can perform a proper reaction to minimize the impact. However, conventional collision detection algorithms required the precise model of a robot, which is difficult to obtain and is subjected to change. Also, expensive sensors, such as torque sensors, are often required. In this study, we propose a novel collision detection algorithm which only requires motor encoders. It detects collisions by monitoring the high-pass filtered version of the velocity error. The proposed algorithm can be easily implemented to any robots, and its performance was verified through various tests.

충돌 처리는 게임의 물리 법칙을 구현하기 위하여 매우 중요한 요소 중의 하나이며, 게임을 생동감 있게 하기 위한 과정이다. 충돌 처리는 매우 많은 연산이 필요하기 때문에 게임 성능에 중대한 영향을 미친다. 이를 해결하기 위해서 연산량을 줄이는 방식의 연구가 많이 진행되었고, 대표적으로 SAP 알고리즘이 많이 사용되고 있으나 반복되는 연산이 있어 효율성이 떨어진다. 본 논문에서는 충돌 처리의 연산량을 줄이고 SAP 알고리즘의 문제점을 해결하기 위하여, 거리기반 SAP 알고리즘을 새롭게 제안한다. 본 논문에서 제안한 알고리즘으로 만든 시뮬레이션 프로그램을 이용하여 FPS를 측정하는 실험을 진행한 결과, 제안한 알고리즘을 사용하는 경우가 사용하지 않는 경우에 비해서 FPS가 약 2~33배 높았기 때문에 충돌 처리의 효율이 향상되었다고 판단할 수 있었다.

Effective tools which can alleviate the complexity and computational load problem in collision-free motion planning for multi-agent system have steadily been demanded in robotics field. To reduce the complexity, the extended collision map (ECM) which adopts decoupled approach and prioritization is already proposed. In ECM, the collision regions which represent the potential collision of robots are calculated using the computational power; the complexity problem is not resolved completely. In this paper, we propose a mathematical analysis of the extended collision map; as a result, we formulate the collision region as an equation with 5–8 variables. For mathematical analysis, we introduce realistic assumptions as follows; the paths of robots can be approximated to a straight line or an arc and the robots move with uniform velocity or constant acceleration near the intersection between paths. Our result reduces the computational complexity in comparison with the previous result without losing optimality, because we use simple but exact equations of the collision regions. This result can be widely applicable to coordinated multi-agent motion planning.

Collision is a brief dynamic event consisting of the close approach of two or more objects or particles resulting in an abrupt change of momentum or exchange of energy because of interaction. Collisions play very important role in computer graphics, computer games and animations fields. Collisions can supply active interaction between cyberspace and real world and give much interests for making nice games so reasonable collision detection algorithms are needed. Collision detection algorithms should satisfy being fast and accuracy. In this paper, we survey the 2D collision detection algorithms between geometric models. We present several methods and system available for collision detection.