공간을 분할하는 방법의 하나. 특정 조건을 기준으로 임의의 공간을 재귀적으로 4개로 쪼개는 방식. 게임 분야에서는 주로 3D 프로그래밍시 컬링 목적으로 사용되는 듯 하다.
2 서버용 외부지형 정보 처리
하이트맵으로 구성된 외부 지형을 서버에서 처리할 때, 가장 기본적인 방법은 맵에디터에서 나오는 하이트맵을 그대로 이용하는 것이다. 하지만 일반적인 외부 지형에서 각각의 타일마다 높이 편차가 그다지 크지 않다는 점을 생각해봤을 때, 이 방식은 메모리를 너무 많이 먹는다는 단점이 있다.
쿼드트리를 약간 응용하면 메모리를 적게 소모하면서, 타일 방식과 비슷한 효과를 낼 수 있다.
일단 원본 맵 데이터가 필요하다. 맵 데이터에서 특정 간격을 기준으로 높이를 샘플링한다. 예를 들어 하나의 청크가 가로세로 32미터이고, 샘플링을 4미터 간격으로 한다면, 총 64 노드에 대한 높이 정보가 나온다. 이 데이터를 D라고 하자.
D에 포함된 높이 정보의 평균을 구한다. 이 값을 A라고 하자.
D에 포함된 노드들의 높이값 중에서 평균값 A와 특정값 이상 차이가 나는 노드가 있는 경우, D 정보를 4개로 나눠서 다시 2번 과정으로 돌아간다. 모든 노드가 평균값과 비슷한 경우에는 분할을 멈춘다.
이와 같은 방식으로 자료구조를 만들어두면, 굴곡이 심한 곳은 노드의 깊이가 깊어질 것이고, 굴곡이 거의 없는 곳은 노드의 깊이가 얕아지게 된다. 위에서도 말했듯이 일반적인 외부 지형은 굴곡이 심한 경우가 많지 않으므로, 메모리를 상당히 아낄 수 있다.
약간 생각해봐야할 점이, 굴곡이 심한 지역에서 높이값을 알아내고자 하는 경우, 트리 깊숙한 곳까지 들어가는 일이 잦아진다는 점이다. 이 점은 트리 데이터 자체를 선형으로 배열하고, 좌표가 주어졌을 때, 해당하는 노드를 바로 찾을 수 있는 일종의 해쉬함수를 만들면 해결할 수 있다. GPG 2권인가, 3권인가에 나와있다.
![[WWW]](/img/moin-www.gif){kind=small}
Quadtrees 