Spheres are widely used in computer graphics and robotics since they are simple and effective to model a variety of objects. To prevent spheres from overlapping, interactions among them should be considered. An important issue of interactions is to minimize the number of collision checks.
This dissertation presents an event-driven approach that efficiently detects collisions among multiple ballistic spheres moving in the 3D space. Adopting a hierarchical uniform space subdivision scheme, we are able to trace the trajectories of spheres and their time-varying spatial distribution. We identify three types of events to detect the sequence of all collisions during our simulation: collision, entering, and leaving. The first type of events is due to actual collisions, and the other two types occur when spheres move from subspace to subspace in the space.
Tracing all such events in the order of their occurring times, we are able to avoid fixed time step simulation. When the size of the largest sphere is bounded by a constant multiple of that of the smallest, it takes $O(\bar{n}_{c}logn + \bar{n}_{e}logn)$ time with O(n) space after O(n logn) time preprocessing to simulate n moving spheres, where $\bar{n}_c$ and $\bar{n}_e$ are the number of actual collisions and that of entering and leaving events during the simulation, respectively. Since $\bar{n}_e$ depends on the size of subspaces, we modify the collision model from kinetic theory for molecular gas to determine the subspace sizes for the space subdivision scheme, that minimize simulation time. Experimental results show that collision detection can be done in linear time in n over a large range.
구는 모양이 단순하고 다양한 종류의 물체들을 모델링하기에 효과적이기 때문에 컴퓨터 그래픽스나 로보틱스 등에서 많이 사용된다. 구들이 서로 겹치는 상황을 피하기 위해서 구들 사이의 상호 작용을 고려해야만 한다. 상호 영향을 고려할 때 중요한 점은 계산시간을 줄이기 위하여 충돌 검사 횟수를 최소화하는 것이다.
이 논문은 3차원 공간에서 중력의 영향을 받으면서 움직이는 많은 구들 사이의 충돌 검사를 효율적으로 수행하는 사건 기반 접근 방법을 제시한다. 계층적 균일 공간 분할 기법을 사용하여 구들의 궤적과 시간에 따라 변하는 공간상의 구 분포를 추적한다. 이를 위하여 시뮬레이션 시간동안 발생하는 세 가지 사건인 충돌, 진입, 그리고 이탈 사건을 찾아낸다. 충돌 사건은 실재 충돌에 의한 것이고, 나머지 두 사건은 구가 균일 공간 분할 기법에 의해 만들어진 공간상의 부공간에서 다른 부공간으로 이동할 때 발생한다.
발생시간순으로 모든 사건들을 찾아냄으로써, 고정된 시간 간격을 두고 매 시간마다 충돌을 검사하는 방법을 피할 수 있다. 가장 큰 구의 크기가 가장 작은 구 크기의 상수배일때, 시뮬레이션은 O(n) 기억공간과 O(n log n) 전처리 과정을 거친 후, $O(\bar{n}_{c}logn+\bar{n}_{e}logn)$ 시간에 수행된다. 여기서, $n_c$와 $n_e$는 각각 충돌 사건과 진입/이탈 사건이 발생하는 횟수이다. $n_e$는 부공간의 크기와 관련이 있으므로 분자 가스의 충돌을 모델링하는 방법을 이용하여 시뮬레이션 시간을 예측하는 모델을 세우고 계산시간을 최소화하도록 하는 부공간의 크기를 구한다. 실험결과는 많은 구에 대해서 선형시간에 충돌을 검사할 수 있음을 보여준다.
