본 논문은 공간분할에 기초한 무리 짓기 알고리즘에서 적절한 분할의 크기를 제시한다. 이것은 공간분할에 기초한 무리 짓기의 알고리즘의 성능이 에이전트의 수, 이웃 에이전트들의 수뿐만 아니라 분할의 크기에도 의존하기 때문이 다. 에이전트 수 및 이웃 에이전트들의 수는 게임 환경에 의하여 고정되는 반면, 분할의 크기는 게임 환경에 관계없이 선택될 수 있기 때문에 최적화가 가능하다. 이를 위하여, 공간분할에 기초한 무리 짓기 알고리즘의 성능은 시간 복잡 도 및 실험적 방법을 통하여 다양한 분할의 크기에 따라 분석되었다. 분석 결과는 대부분의 3D 환경에서 분할의 크기 가 에이전트의수 일 때 좋은 성능을 얻을 수 있음을 보였다.

본 논문은 컴퓨터 애니메이션에서 많이 활용되는 자동 에이전트에 대한 무리 짓기의 설계 및 구현에 관한 연구이다. 잘 알려진 무리 짓기의 방법을 공개용 게임 엔진인 오우거 게임 엔진에 설계 및 구현하였다. 공개용 게임 엔진에구현함으로써 실험용이 아닌 실제 상황에서 무리 짓기의 성능을 측정하고 분석할 수 있었다. 또한 이웃 에이전트를 제한하는 쿼리 반경을 조정함으로써 무리 짓기의 다양한 형태를 관찰할 수 있었고, 이는 향후 무리 짓기의 애니메이션에서 무리의 형태 제어 기법으로 활용될 수 있다.

무리 짓기는 대규모 무리의 사실적인 시뮬레이션으로 게임이나 컴퓨터 그래픽에서 자주 사용된다. 이러한 대규모 무리의 실시간 시뮬레이션은 계산 집약적 작업이기 때문에 효율적인 알고리즘에 대한 많은 연구들이 있었다. 본 논문에서는 기존의 효율적인 무리 짓기 알고리즘이 불필요한 계산을 포함하고 있다는 사실은 실험적으로 찾아내고, 간단한 휴리스틱으로 이러한 단점을 개선하는 새로운 알고리즘을 제안한다. 제안된 방법의 성능을 평가하기 위하여 많은 실험을 수행하였다. 실험의 결과는 제안하는 알고리즘이 기존의 효율적인 알고리즘에 비하여 평균 약 21%정도 성능을 개선한다는 것을 보였다.

논문은 GPU를 이용한 무리 짓기에 대한 병렬 알고리즘을 제안한다. 이를 위하여 GPU의 병렬처리 구조로 CUDA를 사용하였으며, 그것의 특성 및 제한 요소들을 분석하였다. 이의 특성 및 제한 요소를 기초로 무리 짓기에서 가장 많은 비용을 요구하는 이웃 에이전트들을 찾는 것을 병렬화 함으로써 성능을 개선하였다. 제안된 알고리즘을 GTX 285상에서 구현하였고, 그것의 성능을 실험적으로 기존의 공간분할 알고리즘과 비교하였다. 비교의 결과는 제안된 알고리즘이 실행 시간 관점에서 최대 9배 정도 우수하다는 것을 보였다.

논문에서는 무리 짓기에 대한 공간분할 방법의 성능을 개선하는 알고리즘을 제안한다. 핵심 개념은 무리 속에서 움직이는 개체인 보이드가 지속적으로 자신의 방향과 위치를 변경시키나 자신의 다음 방향의 결정에 영향을 주는 k개의 가장 가까운 이웃인 kNN은 자주 바뀌지 않는다는 사실을 이용하여 성능을 개선하는 것이다. 본 논문에서 이전의 kNN을 이용하여 새로운 kNN이 변경되었는지를 판별하는 방법이 제안되었고, 제안된 방법의 정당성은 정리를 통하여 증명되었다. 제안된 방법은 구현되었으며, 기존의 공간분할 방법과 성능이 비교되었다. 비교 결과로부터 제안된 알고리즘이 초당 프레임 수 관점에서 기존의 알고리즘보다 약 30% 개선 효과를 주는 것을 알 수 있었다.

본 논문에서는 임의적으로 움직이고 미리 정해진 위치가 없는 보이드들의 효율적인 무리짓기 대한 알고리즘을 제안한다. 하나의 보이드에 대하여 근사적으로 kNN을 찾고 행위특성의 값을 계산함으로써 제안하는 알고리즘은 기존의 공간 분할 알고리즘을 개선한다. 이를 위하여, 본 논문은 보이드들의 한 그룹에 대하여 평균 방향과 위치를 갖는 대표 보이드를 정의하여 사용한다. 제안하는 알고리즘은 구현되었으며 기존의 알고리즘과 실험적으로 비교되었다. 실험적 비교 결과로부터 제안하는 알고리즘이 기존의 알고리즘에 비하여 초당 렌더링 프레임 수 관점에서 약 -5~130%까지의 개선 효과가 있음을 알 수 있었다.