사용자 도구

사이트 도구


kb:quadtree

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

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