쿼드트리 컬링

들어가기에 앞서...

역시 남에게 설명할 생각으로 쓴다는건 상당히 어렵네요.

그래도 도움은 확실히 되는 것같습니다.

하루에 한파트 반씩 쓰고 있군요.

이것도 아마 내일이나 다음주 월요일에 올라가겠죠.

코딩을 잘하고 싶습니다.

아직 학생이지만, 최대한 잘하고 싶습니다.

군대를 갔다오면...휴...어떻게 될지는 모르겠지만, 그떄까지 제가 쌓을수 있는 최대한의 실력을 쌓고 싶군요.

그럼 계속 쓰겠습니다.

1. 쿼드트리 컬링이란

쿼드트리 컬링은 앞에서 설명한 절두체 컬링과 쿼드트리를 합한 기술이다. 

우선 노드에 절두체가 포함되어 있는지를 검사(컬링)하고, 그 절두체가 다시 컬링을 하는 방식입니다.

우선 크게 한 뭉터기를 자르고, 자세하게 한 번 더 자른다는 것이다.

여기서 한 가지 기억해야할 것은 쿼드트리에서의 컬링은 전체 노드를 일일히 검사하는 방식이 아니라, '부모노드에 절두체가 포함되지 않는다면 자식노드도 절두체를 포함하지 않게 되기에 부모 노드에 절두체가 포함된 자식노드만 탐색을 하면 된다.'

참고로 우리의 절두체 방식은 경계구 방식이다.

다음은 컬링 과정이다

참고로 붉은 색은 컬링된 부분이다.

이 그림에서는 절두체가 4개의 노드에 포함되어있다. 이를 '완전히 포함된다'라고 표현한다.

하지만, 실제로는 절두체가 몇 개의 노드에 포함되어 있을지는 모르는 일이다.

우리는 이것을 표현할 방법(변수)가 필요하다.

변수를 m_bCull이라고 쓰고 enum을 이용하여 '포함되지 않음(OUT)', '부분적으로 포함됨(PART_IN), '완전히 포함됨(FULL_IN)'이라고 표현하겠다.

2. 절두체 컬링 과정

절두체 컬링 함수는 쿼드 트리의 GenTriIndex 직전에 일어난다.

우선 현재 노드에 절두체가 포함되어 있는지를 검사한다.

위에서 말했던 것처럼 우리는 경계구 방식을 쓴다.

경계구 판정을 위해 필요한 재료가 세 개가 있다.

노드(경계구)의 중심점과 반지름, 절두체 평면이다.

노드의 중심점은 높이맵을 이용해서 얻어낼수 있다.

노드의 중심점 = pHeightMap + m_Center(노드의 중심을 나타내는 값, 2차원 노드)

이 말을 이해하는데 시간이 좀 걸렸다.

높이맵을 저장한 배열인 pHeightMap에 m_Center를 더함으로서 pHeightMap[m_Center]를 참조하는 것과 같다.

그후에 경계구 검사를 한다. 

경계구 검사또한 평면 검사와 같이 평면의 방정식을 사용한다.

D3DXPlaneDotCoord(절두체평면[], 경계구 중심점)   >   radius

이 조건이 참이라면 객체가 절두체에 완전히 포함되지 않은 OUT이 된다.

그러나 모든 절두체평면에 대해서 거짓이라면, 이제 부분적으로 포함된(PART_IN) 것인지, 완전히 포함된(FULL_IN) 것인지를 확인해야한다.

그것은 이제 중심점을 노드의 상하좌우으로 바꾸어 검사하면 된다.

만약에 노드의 상하좌우에대한 검사가 모든 거짓이라면 완전히 포함된(FULL_IN) 것이고, 하나라도 참이라면 부분적으로 포함된(PART_IN) 것이 된다.

자, 이제 한 노드에 대한 검사를 마쳤다. 이제 이것을 재귀적으로 돌려서 모든 노드에대한 컬링을 행하면 된다.

참고자료 : 해골책

ps. 의문점과 태클은 언제나 환영입니다! 댓글로 달아주세요!