효율적인 충돌 검출을 위한 거리 기반 SAP 알고리즘

국문 초록 (Abstract)

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

다국어 초록 (Multilingual Abstract)

The collision processing is one of the essential factors to realize physical principles in the game, and it gives liveliness to the game. The collision processing requires a large amount of operations, and significantly affects the game performance. To address this problem, many studies have been conducted to reduce the operation volume, and the SAP algorithm is being widely used. However, its efficiency is low because it involves repetitive operations. In this study, a distance-based SAP algorithm was proposed to reduce the operation volume for the collision processing and address the problem of the SAP algorithm. A test was conducted to measure the FPS using the simulation program, which was developed with the proposed algorithm. The FPS was 2-33 times higher with the proposed algorithm, which indicated that the efficiency of the collision processing was improved.

참고문헌 (Reference)

1 Daniel S. Coming, "Velocity-Aligned Discrete OrientedPolytopes for Dynamic Collision Detection" 1-12, 2008

2 Tomas Akenine-Moller, "Real-Time Rendering" 정보문화사 2003

3 Christer Ericson, "Real-Time Collision Detection" Morgan Kaufmann 2005

4 Rafael de Sousa Rocha, "Performance Evaluation of a Hybrid Algorithm for Collision Detection in Crowded Interactive Environments" 86-93, 2007

5 Daniel S. Coming, "Kinetic Sweep and Prune for Collision Detection" 2005

6 Zhiwen Yu, "GPCD : Grid-based Predictive Collision Detection for Large-scale Environments in Computer Games" 1025-1028, 2006

7 Dong-Jin Kim, "Fast collision detection among multiple moving spheres" 1-7, 1997

8 Daniel J. Tracy, "Efficient Large-Scale Sweep And Prune Methods with AABB Insertion and Removal" 191-198, 2009

9 Xavier Provot, "Collision and self-collision handling in Cloth model dedicated to design garments"

10 S. Kockara, "Collision Detection: A Survey" 4046-4051, 2007

11 Stefan Gottschalk, "Collision Detection Techniques for 3D Models"