Spatial Hash

Ten Minute Physics - 11 Finding overlaps among thousands of objects blazing fast

모든 입자에 대해 어떤 입자 하나가 다른 입자와 충돌했는지 확인하려면 $O(N^2)$ 걸림.

→ 공간을 격자로 나누고 해당 입자가 속한 칸과 주변 칸에 있는 입자들만 검사 해 $O(N)$ 수준으로 감소

→ 무한히 넓은 공간을 다룰 때에는 격자를 미리 만들기엔 메모리 부족 문제가 발생할 수 있어 유한한 메모리 주소로 매핑하는 해시 테이블을 사용.

Spatial Hashing 작동 원리

1. 격자 좌표 계산(Discretization)

   $x_i = \lfloor x / \text{spacing} \rfloor \space\space\space (recommened \space\space spacing = 2r)$

2. 해시 함수(Hashing)

   • 3차원 좌표를 하나의 숫자(해시 인덱스)로 바꿈.

   h = (xi * 92837111) ^ (yi * 689287499) ^ (zi * 283923481);

   hashIndex = abs(h) % tableSize;

   • 서로 멀리 떨어진 두 격자가 우연히 같은 해시 값을 갖는 해시 충돌(Hash Collision) 발생 가능
     

   → 같은 해시 공간에 들어있는 입자들이 실제로는 멀리 떨어져 있을 수 있지만, 이를 별도로 엄격하게 해결하지 않고 허용함. 이는 이후 단계에서 실제 거리 검사 $(|p_j-p_i| <= d)$를 수행해 무시됨.
   

3. 데이터 구축(Creating the Table)

   • 메모리를 효율적으로 사용하기 위해 Linked List 대신 Dense Array 방식 사용

코드

create(pos) {
	var numObjects = Math.min(pos.length / 3, this.cellEntries.length);

	// determine cell sizes

	this.cellStart.fill(0);
	this.cellEntries.fill(0);

	for (var i = 0; i < numObjects; i++) {
		var h = this.hashPos(pos, i);
		this.cellStart[h]++;
	}

	// determine cells starts

	var start = 0;
	for (var i = 0; i < this.tableSize; i++) {
		start += this.cellStart[i];
		this.cellStart[i] = start;
	}
	this.cellStart[this.tableSize] = start;	// guard

	// fill in objects ids

	for (var i = 0; i < numObjects; i++) {
		var h = this.hashPos(pos, i);
		this.cellStart[h]--;
		this.cellEntries[this.cellStart[h]] = i;
	}
}

• 매 프레임마다 실행되며, $O(N)$으로 정렬 알고리즘 보다 훨씬 빠르기에 효율적임.