쿼드 트리

Quadtrees
by Jonathan Ferraris
원문 : http://www.gamedev.net/reference/articles/article1303.asp
번역 : conaman(conaman@spirit3d.net)
배경지식과 이론 : 쿼드트리는 무엇인가?
컨슈머 3D 그래픽 카드의 혁명으로 3D게임의 붐의 일어나기 시작했습니다. 이들 대부분은 FPS(first person shooters)장르를 택했고 거기에서 좋은 이유가 있습니다. 그 이유는 실외 환경들과 비교할 때 실내 환경이 훨씬 간단하기 때문입니다. 광대한 야외는 다음 단계로 가는 편리한 계단들이나 그리고 당신의 눈을 막는 문들이나 벽들이 없습니다. 신뢰할 만한 실외 환경이 바로 앞에 다가왔습니다. 포함되어 있는 순수 지오메트리는 굉장합니다. 그리고 이것을 자르는 어떠한 것도 환영받는 작업입니다. 쿼드트리로 들어갑시다.
메모 : 다음 그림은 3D 지형의 top-down 시점입니다. 이 격자는 실제 높이(언덕)는 보이지 않고 우리가 y축 아래로 보는 x/z를 바탕으로 한 지형을 보여줍니다.

그림 1

당신의 지형을 x/z 평면에 펼쳐져 있는 큰 격자로 상상하십시기 바랍니다. 그림 1을 보세요. 여기에 우리는 지형의 오른쪽 아래에 위치한 카메라가 있습니다. 그리고 그 카메라의 뷰잉 절두체(파랑색 삼각형)가 같은 방향에 있는 몇 개의 셀들을 펼치고 있습니다. 그래서 어떠한 최적화를 하기 전에 지형을 그리는 루틴은 이렇게 나타낼 수 있을 것입니다.

for(int ctr=0; ctr<셀의 갯수; ctr++)
{
    DrawCell();
}

(메모 : 한 셀은 단지 지형의 조각인 삼각형의 수를 포함하고 있는 정사각형입니다.) 이것은 매우 휼륭하지만 우리의 지형은 16x16 셀로서 256개의 셀들이 그려지고 있습니다. 이것은 우리의 뷰잉 절두체에 오직 5개의 셀만이 있기 때문에 아주 낭비적입니다! 자! 우리의 첫번째 최적화입니다. 우리는 셀이 뷰잉 절두체안에 놓여 있는지를 보기 위해 각각의 셀들을 테스트 할 것입니다. 그리고 그러하다면 그것을 그릴 것입니다. 자 우리의 코드는 이처럼 작게 보입니다.

for(int ctr=0; ctr<셀의 갯수; ctr++)
{
    if(셀이 절두체 안에 있다면)
        DrawCell();
}

셀이 절두체 안에 있다면 그릴 것입니다. 그렇습니다. 자! 우리는 256개에 반대함으로서 오직 5개의 셀들만을 그리고 있습니다. 그런 조금의 수정된 코드가 251개의 셀들을 그리는 것에서 구해주었습니다. 그렇지만 또다시 그것은 매우 무능합니다. 그림2 를 보십시요.

그림 2

저는 특정한 셀을 파랑색으로 그려놓았습니다. 그래서 그것들로 하여금 바운딩 박스를 만들도록 했습니다. 만약 파랑색 셀들이 절두체 안에 없다면 그 때 우리는 Section A 내부에 있는 셀들이 어느것도 속하지 않는다고 이야기해도 무방합니다. 우리가 만약 파랑색 셀들이 절두체안에 없다는 것을 안다면 Section A 안에 다른 144개를 귀찮아게 테스트 할 이유가 있겠습니까? 그것이 쿼드트리가 시작되는 곳입니다.
쿼드트리는 지형을 취합니다. 그리고 그것을 네 개의 더 작은 조각으로 나눕니다. 그런다음 그 더 작은 조각을 다시 네 개의 더 작은 조각으로 나눕니다. 그리고 그것이 한 세트 크기에 이를때까지 그 작업을 합니다. 조금 혼란할지도 모르겠습니다. 그러나 저는 그림으로 설명하겠습니다. 먼저 우리는 우리의 격자를 가지고 시작합니다. 우리는 지금 격자를 4개의 더작은 조각들로 나누었습니다

그림 3

우리가 그림 3에서 본 것처럼 우리는 지금 지형을 네 개의 조각을 가지게 되었습니다. 우리는 지금 오직 한 셀이라고 불리우는데 까지 네 조각들로 나누기를 계속하는 것이 필요합니다. 그래서 다음 그림에서 우리는 첫번째 조각을 네개의 더 작은 조각들로 나눌 것입니다

그림 4

다시 우리는 한 조각을 네 개의 더 작은 조각들로 나눌 것입니다.

그림 5

그리고 다시, 우리는 한 조각을 네 개의 더 많은 조각들로 나눌 것입니다

그림 6

좋습니다. 우리는 되풀이하며 조각을 나누어 왔습니다. 그리고 그것의 조각들이 오직 넓이와 높이가 한 셀이 되었습니다. 우리는 트리에 조각을 나누는 것을 멈추라는 것을 전달합니다. 그러나 그 다음을 계속합니다. 결국은 전체 트리가 나뉘어 질 것입니다. 그래서 쿼드트리를 생성하기 위해서 우리는 네 개의 부분들로 나누어야 합니다. 그런다음 조각들을 네 조각으로 그런다음 더 작은 조각을 네 조각으로 분리하는 작업을 계속합니다. 우리가 언제 멈추어야 할까요? 특정 크기에 이를 때 멈출 수 있습니다. 그 크기는 조정자입니다. 그래서 당신 스스로 결정해야 합니다. 우리의 예제에서는 16개의 삼각형들(4x4)을 포함하는 각각의 셀을 이야기할 것입니다. 그래서 우리는 조각들이 한 셀 x 한 셀 일 때 멈출 것입니다. 우리는 가는 것을 계속할 수 있지만 하지 않을 것입니다. 제가 당신에게 말하지 않은 한가지는 부모/자식 관계입니다. 각각의 조각( 노드라고 불리는 )은 한 부모( 쪼개어질 노드 )와 네 자식을 가지고 있습니다. 리프(leaf)들은 예외입니다. 리프들은 오직 하나의 부모만을 가지고 있습니다. 리프들은 우리가 허락하는 가장 작은 조각입니다. 우리의 경우에 한 셀 x 한 셀 입니다. 또 다른 예외가 있습니다. 우리가 나누기 전에 우리는 루트(root)를 가지고 있습니다. 그 루트는 부모를 가지지 않습니다. 그러나 규칙처럼 네 개의 자식을 가지고 있습니다. 아직 이해가 되지 않으세요? 예제를 봅시다. 당신은 영향받기 쉬운 사슬 편지( 역자주 : 행운의 편지 같은 종류의 편지를 뜻하는 것 같음 )를 아십니까? 저는 그것을 좋아합니다. 한 사람(루트)이 한 편지를 네 사람(루트의 자식)에게 보냅니다. 그러면 이들 네 사람(노드들)은 사악한 음모자인 같은 부모를 공유합니다. 그 편지에는 "이 편지를 네명 이상의 사람에게 보내라 그러지 않으면 당신은 칠년의 불행, 무한한 나쁜 평판, 등등이 올 것입니다." 라고 쓰여있습니다. 그래서 이들 네 사람 각각은 네명 이상의 사람들에게 편지를 보내기를 계속합니다.
다시 그림 1을 보십시요. 검붉은 색이 루트입니다. 그림 3에서 우리는 루트를 나눕니다. 그리고 루트에 자식들을 할당합니다. 파랑색 선으로 나타나지는 네 개의 정사각형들은 루트 자식입니다. 우리는 그것들을 각각 노드 2, 3, 4, 5로 부를 것입니다. 그림 4에서 우리는 루트의 첫번째 자식(노드 2)을 취했습니다. 그리고 그것을 네 개의 정사각형들로 나누었습니다. 그 정사각형들은 노드의 자식들입니다. 이들 모든 자식들은 루트의 첫번째 자식 또는 노드 2로 불리는 같은 부모들을 공유하고 있습니다. 우리는 이 노드들을 노드 6, 7, 8, 9로 부를 것입니다. 우리는 노드 2의 자식들을 네 개의 정사각형들(노드들)로 나눕니다. 그리고 우리는 이들을 10, 11, 12, 13 이라고 이름 붙일 것입니다. 노드 10-13의 부모는 노드 6입니다. 이것은 그림 5에서 표현되었습니다. 그림 6에서 우리는 노드 10을 나누어서 리프(leaf) 14, 15, 16, 17을 얻었습니다. 그것들이 리프(leaf)들이기 때문에 우리는 그것들을 나누지 않습니다. 돌아가서 다음 노드를 나누는 작업을 계속합니다. 노드 11이 행해지면 12를 하고 그런다음 13을 하고 그런다음 7, 8, 9을 하고 그러다음 3, 4, 5를 합니다. 그러고 나면 우리는 다 행했습니다.
저는 그것이 정말로 먹기위한 들쑥날쑥한 토스트 조각이라는 것을 압니다만( 역자주 : 글 솜씨가 없다는 뜻인 것 같음 ) 그것을 주의깊게 읽으시기 바랍니다. 그런다음 다시 읽으십시요. 만약 여전히 확신이 없다면 웹 주위를 슬쩍 보시기 바랍니다. 그것들이 정확하게 설명되었는지 이해하기 쉽기 때문에 우리는 아마 결국은 알게 될 것입니다. 마지막 필사적인 시도로 당신과 함께 쿼드트리를 사용하는 과정을 따라 걸어갈 것입니다. 그러나 첫번째 좋은 요약을 가지십시요!
쿼드트리는 지형을 네 조각으로 나눈다. 그리고 그 조각들이 특정 크기에 이를 때까지 네 조각으로 나누기를 계속한다. 그리고 나누기를 멈춘다.
쿼드트리는 노드의 바운딩 좌표를 사용해서 작업하니다. 우리 맵이 X축으로 0-16 그리고 Z축으로 0-16으로 되어 있다고 얘기합시다. 그 경우에 전체 맵의 바운딩 좌표는 좌상 = (0, 0, 0 ), 우상 = (16, 0, 0), 좌하 = (0, 0, 16), 우하 = (16, 0, 16)입니다. 우리가 루트 노드를 쪼갤 때 또한 그것의 바운딩 좌표를 쪼갭니다. 그래서 노드 2는 그림 7에서 처럼 바운딩 좌표로 좌상=(0, 0, 0), 우상 = (8, 0, 0), 좌하 = (0, 0, 8), 우하 = (8, 0, 8) 입니다.

그림 7

테스트 1
작업하는 방법은 먼저 루트에서 시작합니다. 그리고 "카메라가 루트의 바운딩 좌표안에 있는가?"라고 이야기 합니다. 만약 어떤 것도 잘못된 것이 없다면 우리는 "예'라고 말합니다. 우리는 카메라가 루트의 자식안에 있다는 것을 압니다. 그래서 지금 우리는 그것들을 테스트합니다. "카메라가 노드 2의 바운딩 좌표안에 있는가?". 대답은 아니오입니다. 그래서 우리는 노드 2는 잊어버릴 수 있습니다. 그리고 그것의 모든 자식들도 잊어버릴 수 있습니다. 지금까지는 우리는 64셀(노드 2에서 리프의 수)을 테스트하는 것을 처리했습니다. 상당히 좋습니다. 상당히 좋습니다.

그림 8

테스트 2
당신이 그림 8에서 볼 수 있었던 것처럼 저는 명확하게 하기 위하여 노드 2와 모든 그의 자식들을 제거했습니다. 다시 한번 우리는 트리를 테스트합니다. "카메라가 노드 3의 바운딩 좌표안에 있습니까?". 다시 우리는 아니오 라고 대답합니다. 그래서 우리는 안전하게 노드 3와 그의 모든 자식들을 잊어버릴 수 있습니다.

그림 9

테스트 3
그렇게 우리는 계속합니다. "카메라가 노드 4의 바운딩 좌표안에 있습니까?". 놀랍게도 아니오, 대답은 아니오입니다. 노드 5를 테스트할 시간이 되었습니다.

그림 10

테스트 4
시간이 되었습니다. 노드 5의 바운딩 좌표안에 카메라가 있습니다. 그래서 우리는 그것의 자식들을 테스트 할 것입니다. 저는 명확하게 하기 위해서 노드 5의 네 자식들 A, B, C, D라고 이름 붙였습니다. 노드 5의 첫번째 자식을 테스트할 시간이 되었습니다. "카메라가 모드 A의 바운딩 좌표안에 있습니까?" 그림 10에서 보이는 것처럼 우리는 그렇지 않은 것을 볼 수 있습니다. 그래서 우리는 노드 A와 그의 자식들을 잊어버릴 수 있습니다.

그림 11

테스트 5
자! 노드 5의 두번째 자식을 테스트 합시다. "카메라가 노드 B의 바운딩 박스 안에 있습니까?" 그림 11에서 보는 것처럼 우리는 그렇지 않다는 것을 볼 수있습니다. 그래서 우리는 노드 B와 그의 자식들을 잊어버릴 수 있습니다.

그림 12

테스트 6
그렇습니다. 노드 5의 세번째 자식인 노드 C를 테스트 합시다. "카메라가 노드 C의 바운딩 좌표안에 있습니까?". 물론 아닙니다. 그러니깐 전적으로 노드 C를 제거합시다

그림 13

테스트 7
맞습니다. 카메라는 노드 D에 있어야만 합니다. "카메라가 노드 D의 바운딩 좌표안에 있습니까?". 마지막으로 "예, 그렇습니다.". 그럼 우리 모두가 해야할 것은 노드 D의 모든 자식들을 테스트하는 것입니다. (투덜투덜!) 응~ 저는 여기서 멈추길 원합니다. 운동하는 것처럼 휴식하는 것을 생각합시다. :) 당신 아는것처럼 보여지고 있는 5개의 셀의 결과물을 얻기 위해서 16개 이상의 테스트해야 합니다. 테스트의 총합을 계산해 봅시다. 7 + 16 = 23. 우리는 256번을 23번으로 반들었습니다. ( 루트는 테스트 할 가치가 없으므로 실제로는 22번. 카메라는 루트안에 놓여있어야만 합니다. 그렇지 않으면 아무것도 보여지는 것이 없습니다. ) 쿼드트리를 가지고 우리는 모든 셀/리프를 테스트하는 전에 테스트 방법의 거의 11.6%만으로 같은 작업을 했습니다. 이제 당신은 쿼드트리 이론에 관해 견고한 이해를 가져야만 합니다. 그래서 당신의 코딩에 가벼운 신발을 놓으십시요. 왜냐하면 당신이 그것을 만들게 될 것이기 때문입니다. 우리가 적당히 이야기하게 될 것을 요약할 것입니다.
쿼드트리는 단번에 큰 지형 덩어리를 버리기 위해 사용된다. 만약 사과가 나무의 잎위에 있다면 사과가 있기에는 당치도 않은 곳의 가지를 치는 것은 모든 잎위를 보는 것에서 당신을 구해 줄 것이다.

ㅇ 해골책 쿼드 드리
- 쿼드트리란 자료구조의 하나인 트리( tree)의 일종으로 자식노드가 4개인 트리를 말한다.
- 쿼드 트리의 분할 과정