Collision detection is critical for applications that handle spatial interactions among objects. In many applications, such as computer games, crowd simulations, and particle systems, it is often the case that either a user is allowed to move an object at his/her will, or an object moves under rules that are hard to describe by exact mathematical formulae. Thus, the trajectory of the object is not easily known in advance.
In this dissertation, we present a new algorithm that efficiently detects the collisions among spheres moving with unknown trajectories. Given the maximum magnitude of acceleration of a sphere, we represent its bounding volume, called a time-varying bound, as a moving sphere of variable radius. We check the collision between two spheres when their time-varying bounds collide with each other. Because of the compact representation of these bounds, we can generalize the event-driven approach [20] for collision detection among moving spheres to this more demanding case. This event-driven approach [20], however, is inefficient in handling the spheres in contact. For a pair of spheres in contact, it repeatedly checks the collision between the spheres. We enhance the efficiency of the proposed event-driven approach by handling the spheres in contact. We excessively reduce the number of collision checks among time-varying bounds by avoiding any collision checks between time-varying bounds while their original spheres touch each other and move in the same velocity. The proposed algorithm shows interactive performance in detecting the collisions among thousands of moving spheres with unknown trajectories, without any help from hardware.
Based on the proposed event-driven approach, we simulate group behaviors. The complex behaviors of a group evolve from the interactions among the members of the group. We approximate every member as its bounding sphere and calculate the time-varying bound. When two time-varying bounds for a pair of members collide, the members adjust themselves to their possible collision in future. As they are getting closer, their time-varying bounds collide more frequently. Accordingly, the members are getting ready to the collision by changing their behaviors gradually in accordance with the collisions between their time-varying bounds. While moving toward their goals, the members contribute these local variations to the characteristics of a global group behavior. The event-driven approach is a new group behavioral model, which allows the members to be highly sensitive to their surrounding environment.
충돌 검색은 물체들간의 공간적 상호 작용을 다루는 응용 분야에서 매우 중요하다. 컴퓨터 게임, 군중 시뮬레이션, 입자 시스템과 같은 여러 응용 분야에서는 사용자가 물체를 직접 움직이거나, 물체가 명확한 수식으로 표현되기 어려운 규칙에 따라 움직이는 경우가 종종 있다. 따라서, 물체의 경로를 미리 알기가 쉽지 않다.
본 학위 논문에서는 경로가 알려지지 않은 움직이는 구들 사이의 충돌을 효율적으로 검색하는 알고리즘을 제안한다. 주어진 구의 최대 가속도 값을 이용하여, 구의 한계 공간 (bounding volume)을 반지름이 변하면서 움직이는 구로 표현하고, 이를 시간-변환 한계(time-varying bound)라 칭하였다. 두 구의 시간-변환 한계가 충돌할 때, 구들 사이의 충돌을 검사한다. 한계 공간을 간결한 구로 표현하였기 때문에, 움직이는 구들 사이의 충돌을 검색하는 사건-기반 접근법 (event-driven approach)[20]을 이용하여 시간-변환 한계들간의 충돌을 검색할 수 있다. 그러나, 사건-기반 접근법은[20] 접촉하고 있는 구들간의 충돌을 반복적으로 검색하여 비효율적이다. 본 논문에서는 접촉하고 있는 구를 처리하여 사건-기반 접근법의 효율을 높였다. 두 개의 구가 접촉하고 있는 동안에는, 그들의 시간-변환 한계들간의 충돌을 검색하지 않으므로써, 충돌 검사 횟수를 많이 줄일 수 있었다. 제시된 방법은 경로가 알려지지 않은 수천개의 움직이는 구들간의 충돌을 효율적으로 검색한다.
제시된 사건-기반 접근법을 기반으로 하여, 집단 행동을 시뮬레이트하였다. 한 집단의 전체적인 모습은 집단을 이루는 구성원들간의 상호 작용에 의해 연출된다. 본 논문에서는 각 구성원을 한계 구(bounding sphere)로 표현하고, 이들의 시간-변환 한계를 생성한다. 두 구성원의 시간-변환 한계가 충돌하면, 두 구성원들은 앞으로 발생할 수 있는 그들간의 충돌을 피하기 위하여, 행동을 조정하게 된다. 두 구성원이 가까와 질 수록 그들의 시간-변환 한계는 더 자주 충돌하게 된다. 따라서, 시간-변환 한계의 충돌에 따라 구성원들은 자신의 행동을 점진적으로 변화하여 그들간의 충돌에 대비한다. 이러한 구성원의 행동 변화들이 모여 전체적인 집단의 행동의 특징을 나타낸다. 본 논문에서 제시한 사건-기반 접근법은 각 구성원이 주위 환경에 높은 반응을 보이도록하는 새로운 집단 행동 모델링 방법이다.
