쿼드트리 알고리즘 최적화를 구현해본다.
이전에 구현한 쿼드트리 알고리즘은 같은 범위를 가진 물체들이 서로 다른 깊이 노드에 배치될 수 있다.
하지만 사분면 영역에 겹치는 다수의 물체가 존재하는 경우 루트 노드에 불필요한 검색이 수행된다.
이를 보완하기 위해서 사분면 영역에 겹치는 경우 어떤 변에 겹치는지를 조사해서 최대한 검색 수를 줄여야 한다.
하지만 위 보완 방법은 검색량을 조금 더 줄일 수 있지만, 확실한 해결 방법이 될 수 없다.
위 문제를 Sticky Planes문제라고 한다.
겹치는 물체를 더 세밀하게 분류하거나 겹치는 물체를 부모 목록에 저장하지 않고 자식목록에 넘기는 방법으로 임시적인 해결을 가능하나, 정적인 물체에만 활용할 수 있다는 단점이 있다.
이를 해결하기 위해 Loose Quadtree 기법을 사용한다.
느슨한 쿼드트리는 각 노드의 실제 범위를 더 크게 설정해서, 노드 간 경계에 걸쳐 있는 오브젝트도 한 곳에만 저장할 수 있도록 만든 구조이다.
물체의 크기로부터 깊이를 먼저 계산한 후,
깊이는 물체의 반지름이 변의 1/4 보다 작은 경우에만 삽입을 결정한다.
루트 노드 영역에서 한 변의 길이가 64인 경우, 물체의 반지름이 16 을 넘으면 루트 노드에 저장하고, 16보다 작으면 첫 번째 깊이에 저장한다.
깊이에 들어가는 최대 반지름의 값을 구하는 공식은 다음과 같다.