Boids!

Sebastian Lague의 Coding Adventure: Boids 영상에서 영감을 받아 시작했습니다.

Coral reef 데모 씬

Boid의 움직임 이해하기

Boids는 각 개체가 주변 이웃을 기준으로 움직이면서 새 떼나 물고기 떼의 움직임을 모방하는 알고리즘입니다. 무리 전체의 경로를 지정하지 않아도, 각 개체에 세 규칙을 적용하면 군집의 움직임이 나타납니다.

• Separation: 가까운 이웃에게서 멀어지는 방향을 누적하되, 거리가 가까울수록 큰 가중치 적용
• Alignment: 주변 이웃의 평균 속도를 구해 이동 방향 정렬
• Cohesion: 주변 이웃의 평균 위치를 구해 무리의 중심을 향하는 방향 계산

아래 2D 데모에서 세 규칙을 조절하며 움직임의 차이를 확인할 수 있습니다.

방향을 조향력으로 바꾸기

구한 방향으로 속도를 바로 바꾸면 급격하게 방향을 틀게 됩니다. 각 규칙이 요구하는 목표 속도와 현재 속도의 차이를 조향력으로 사용하고, 그 크기를 제한합니다.

$$\mathbf{s}_k = \operatorname{limit}\!\left(v_{\max}\frac{\mathbf{d}_k}{\|\mathbf{d}_k\|}-\mathbf{v},\ s_{\max}\right)$$

여기서 $\mathbf{d}_k$는 각 규칙에서 구한 방향 벡터, $\mathbf{v}$는 현재 속도입니다. $v_{\max}$는 최대 속도, $s_{\max}$는 규칙별 조향력의 상한이며, limit은 방향을 유지한 채 벡터의 크기를 제한합니다. 위 식은 방향 벡터가 0이 아닌 경우를 나타냅니다.

• 규칙마다 별도의 이웃 탐색 반경 적용
• 해당 반경에 이웃이 없으면 그 규칙의 조향력은 0
• 세 조향력에 각각 가중치를 곱한 뒤 합산
• 경계 밖에서는 안쪽을 향하는 힘을 더하고, 최종 속도에 최대 속도 제한 적용

규칙별 조향력을 제한한 뒤 합산하므로, 합산한 힘의 크기까지 $s_{\max}$로 제한되는 것은 아닙니다.

---

GPU Boids

Unity Graphics Programming Vol.1의 3장 「군집 시뮬레이션의 GPU 구현」을 많이 참고했습니다. 아래의 두 커널 분리, 공유 메모리 활용과 indirect instancing은 책의 샘플을 바탕으로 구현한 부분입니다. (한국어판 본문 56–80쪽)

GPU에 먹이기

Boid마다 다른 모든 개체와 거리를 비교하면 탐색 비용은 $O(N^2)$로 증가합니다. 책의 구현에서는 각 스레드가 Boid 하나를 맡아 이 계산을 병렬로 수행하고, 결과를 GPU에 둔 채 렌더링까지 연결합니다.

1. 초기화: 위치와 속도를 담은 BoidData 배열을 ComputeBuffer에 업로드
2. 조향력 계산: ForceCS에서 현재 위치와 속도를 읽고, 개체별 조향력을 별도 버퍼에 기록
3. 상태 갱신: IntegrateCS에서 조향력을 읽어 속도와 위치 갱신
4. 렌더링: 같은 상태 버퍼를 Material에 연결하고 Graphics.DrawMeshInstancedIndirect()로 그리기

계산 도중 이웃의 상태가 바뀌지 않도록 커널 분리

조향력을 계산하면서 위치까지 갱신하면, 다른 스레드가 읽는 이웃의 상태에 이전 값과 갱신한 값이 섞일 수 있습니다. ForceCS에서는 상태 버퍼를 읽기만 하고, 이후 IntegrateCS를 실행해 상태를 갱신합니다.

• ForceCS: 모든 이웃의 현재 상태를 읽고 자신의 조향력만 기록
• IntegrateCS: 자신의 조향력과 상태를 읽고 자신의 속도와 위치만 갱신
• 속도에 조향력 × deltaTime을 더한 뒤 크기를 제한하고, 갱신한 속도로 위치 이동

두 번째 커널은 다른 개체의 상태를 읽지 않으므로, 위치와 속도 버퍼를 복제하지 않고 같은 버퍼에 결과를 덮어쓸 수 있습니다.

공유 메모리로 이웃 데이터 재사용

같은 스레드 그룹이 검사할 이웃 데이터를 groupshared 메모리에 모아 재사용합니다. 각 스레드가 전역 메모리에서 같은 이웃을 반복해서 읽는 비용을 줄이는 방식입니다.

1. 그룹의 256개 스레드가 이웃 데이터를 하나씩 읽어 공유 메모리에 적재
2. GroupMemoryBarrierWithGroupSync()로 그룹 전체의 적재 완료 대기
3. 각 스레드가 공유된 256개 이웃을 순회하며 세 규칙 계산
4. 그룹 전체의 읽기가 끝난 뒤 다음 256개 이웃으로 교체

공유 메모리를 사용해도 모든 개체를 검사하는 $O(N^2)$ 탐색은 남습니다. 책에서 개선 방향으로 소개한 공간 격자는 현재 GPU 구현에 적용하지 않았습니다. 또한 현재 커널은 개체 수가 스레드 그룹 크기인 256의 배수라는 전제로 동작합니다.

GPU의 상태를 그대로 렌더링에 사용

계산 결과를 매 프레임 CPU로 가져와 개별 Transform에 복사하지 않고, 정점 셰이더에서 직접 읽습니다.

• C#과 HLSL에서 BoidData의 속도, 위치 필드 순서와 크기 일치
• 인스턴스 ID로 해당 Boid의 상태 조회
• 속도 방향에서 yaw와 pitch를 구해 메시 회전, 위치를 이용해 평행 이동
• 메시 인덱스 수와 인스턴스 수를 indirect 인자 버퍼로 전달

마우스로 무리에 개입하기

책의 기본 군집 동작에 마우스 위치를 향해 모이거나 흩어지는 상호작용을 추가했습니다.

• 화면의 마우스 좌표를 시뮬레이션 중심을 지나는 평면 위의 월드 좌표로 변환
• 왼쪽 버튼은 목표점을 향하는 힘, 오른쪽 버튼은 반대 방향의 힘 적용
• IntegrateCS에서 군집 조향력에 마우스 힘을 더해 속도 갱신

GPU Boids 소스 코드

---

Flappy Boids

이렇게 아름다운 보이드를 게임화해보면 어떨까 싶어 프로토타입을 제작해 보았습니다.

벽과 바닥은 Marching Cubes 알고리즘으로 mesh를 생성해 바닷속 바위의 굴곡을 표현했습니다.

하지만 플레이해본 결과 별 재미는 없어서…

물고기 표현에나 쓰는 게 맞지 않나 싶습니다.

끝