입자 시뮬레이션에서 디스크의 동적 보로노이 다이어그램과 다른 알고리즘의 실험적 비교

Abstract

다중 입자 시스템의 이벤트 기반 시뮬레이션의 충돌 감지 알고리즘은 시뮬레이션의 효율성을 결정하기 때문에 중요하다. 다양한 충돌 감지 알고리즘 중에서 동적 보로노이다이어그램 (Dynamic Voronoi diagram), 정규 공간분할 (Regular spatial subdivision), 세그먼트 트리 세트 (The set of segment tree)에 기반한 알고리즘들이 잘 알려져 있다. 그러나 세 가지 알고리즘 비교에 대한 자료가 충분하지 않아, 다양한 환경 조건에서 어떤 알고리즘을 선택해야 할지 어려움이 있다. 우리는 2 차원 공간에서 입자의 속도, 반지름 및 디스크 집합의 밀도 조건을 변화시키면서 세 가지 충돌 감지 알고리즘의 성능을 비교 및 평가하고, 적절한 충돌 감지 알고리즘을 선택하기 위한 가이드라인을 제시한다.