쿼드트리 Terrain 컬링

소개

 

안녕하세요 

 

이번에 보여드릴 최적화 기법은 쿼드트리 자료구조를 이용한 Terrain 컬링 입니다.

 

쿼드 트리를 이용한 Terrain 컬링은 지형의 크기가 매우 클 경우 사용하면 좋은 컬링입니다.

 

지형이 매우 큰 경우 보이지도 않는 지형을 랜더링하게 되면서 많은 값을 소비하게 됩니다.

 

이러한 경우 쿼드트리를 이용하여 지형을 컬링하는 것이 좋습니다.

 

왜 지형의 크기가 작은경우 컬링을 하지 않는가 .. 의문이 들텐데요!!

 

쿼드트리를 이용하여 Terrain을 컬링하는 경우, Terrain 을 구성하는 많은 셀들을(인덱스 삼각형) 순회하며 컬링 되야할 부분가 컬링되지 않을 부분을 구별하고,

 

인덱스들을 모아서 랜더링하는 작업을 해야하는데요. 이 작업에서 많은 값들이 소비 됩니다. 때문에 지형의 크기가 매우 크지 않을 경우에는 오히려 느려집니다.

 

쿼드트리를 사용하기 위해서는 Terrain의 정점의 구성이 (2n + 1) * (2n + 1) 이어야 합니다. (지형을 4등분하여 탐색하기 때문에)

 

그럼 왜 쿼드트리라는 자료를 사용하여 컬링을 할까요 ??

 

지형을 4등분 해가며 줄여갈 경우 최소단위 까지 컬링이 가능하기 때문이다.  지형은 공중에 떠있다는 개념이 없기 때문에 옥트리 보다는 쿼드 트리를 사용합니다. \

 

(비교횟수가 적어짐)

 

 

알고리즘

 

파란색 : 유효한 타일

 

빨간색 : 버려진 타일

 

 

터레인의 인덱스들을 4개의 영역으로 나눠가면서 유효한 범위는 다시 4개의 영역으로 나누어 탐색하고 유효하지 않은 범위는 탐색하지 않는다.

 

(재귀적으로 구현할 경우 쉽게 구현이 가능합니다.)

 

 

 

 

 

 

1. 가장 큰 사각형에 대해 생각해 줍니다.

 

2. 카메라에 사각형(초록색)을 구성하는 4개의 정점들이 들어오는지 조사합니다.

 

3. 4개의 정점 중 하나라도 들어온 녀석은 탐색할 필요가 있습니다. 4개의 정점 모두가 들어오지 않는다면 그 내부에 어떠한 사각형도 카메라에 들어오지 않습니다. 때문에

 

탐색하지 않습니다. 4개의 정점이 모두 들어온다면 내부에 어떠한 녀석들도 다 랜더링 되어야 하기 때문에 인덱스 집합에 넣어주고 탐색을 하지 않습니다.

 

 

1. 유효한 분할된 영역에 대해 처음과 같은 방법으로 탐색해 줍니다.

 

 

 

1. 유효한 분할된 영역에 대해 처음과 같은 방법으로 탐색해 줍니다.

 

 

 

1. 쪼개진 사각형의 크기가 최소단위일(랜더링할 기준) 경우 탐색을 그만하고 그동안 모아놓은 인덱스들을 랜더링 해줍니다.

 

 

모아놓은 인덱스 집합을 랜더링 해줍니다.

 

 

구현후 느낀점

 

1. 터레인의 크기가 상당히 크지 않으면, 사용하지 않는것이 좋습니다.

 

2. 처음에 재귀적으로 구현을 해봤으나, 효율이 좋지 못하여 선형적으로 구현을 해보았습니다. 재귀에 비해 속도가 증가 하였으나 아직도 느렸습니다.

 

3. 최적화를 하기 위해서 유효한 사각형을 계속 render 하는 것이 아닌 인덱스들을 모아서 render를 해주었습니다.

 

4. 인덱스들을 모으기위해 선언한 vector를 매번 클리어 해주고 새로 만드는 작업때문에 개선 되지 않았고, 자체적인 가벼운 vector를 만들어서 사용해주었더니

 

개선이 되었습니다.

 

5. 하늘을 바라 보았을 때 바닥이 랜더링 되지 않게 하기위해 구체를 씌워서 최적화를 하였습니다.