BSP (Binary Space Partition)

http://misofruit.co.kr/seojewoo/programming/project2312.htm

지형 처리 방법

3D게임의 가장 큰 특징은 가상의 공간을 자유롭게 돌아다닐 수 있다는 데서 찾을 수 있다. 따라서 대개 3D 게임은 
굉장히 큰 공간을 배경으로 진행되는 경우가 많다. 그런데, 공간이 커지면 커질수록 동시에 처리해야 하는 데이터의
양도 급증해 컴퓨터가 감당할 수 없을 정도의 부하를 주게 된다. 이러한 이유로 3D게임에는 효율적인 공간 처리방법
들이 연구되고 구현돼 왔지만, 모든 경우를 자유롭게 처리할 수 있는 이상적인 방법은 없고 제작하려는 게임에 가장
적절한 방법을 선택해 구현하는 것이 현명하다. 여기서 소개하는 방법은 가장 널리 사용되고 있으며 효율도 우수하
지만 사전 작업의 시간을 많이 필요로 하므로 정적인 지형의 경우에 알맞다.

BSP

BSP는 Binary Space Partition의 약자로, 말 그대로 이분적인 공간 분할 방법을 의미한다. 큰 지형을 이진트리 형태
호 분석해 노드 정보를 구성하고 이를 참조해 대상 물체를 찾아내는 것이 BSP의 기본 원리로, 유명한 돔에서 사용한
이후로 널리 알려졌다. BSP는 간단하게 다음과 같은 과정으로 실시된다.

(1)모델에 존재하는 면 중 하나를 선택한다. 만약 선택할 면이 없으면 종료한다.

(2)선택한 면의 위에 겹치는 모습의 무한 평면을 상상해 이것으로 공간을 분할한다. 이 때 무한 평면에 걸치는 면이
    있으면 이것은 두 개로 잘라진다.(이미 처리된 면은 생략).

(3)선택한 면의 법선 방향을 앞으로, 반대방향을 뒤로 해서 앞쪽에 있는 면들에 대해 (1)의 과정을 제귀적으로 수행
    한다.

(4)선택한 면의 뒤쪽에 있는 면들에 대해 (1)의 과정을 재귀적으로 수행한다. 이 과정을 실제의 예를 들어 설명해보
    겠다.

<그림 8 >과 같은 지형이 있고, 이것을 BSP를 이용해 <그림9 >처럼 분할해보자.
우선 임의의 한면을 선택한다. 여기서는 10면을 선택한다. 그러면 이것은 최상위 노드에 위치하고, 이 평면을 중심
으로 앞뒤로 분할하게 된다. 면의 앞쪽에 있는 면들은 왼쪽 노드에 속하고, 뒤쪽은 오른쪽 노드가 된다.
이때 분단면이 관통하는 5면은 분할돼 각각 5a/5b로 나눠진다. 이제 분할된 면을 기준으로 (1)의 과정을 반복한다.

이번에는 3면을 선택해 수행한다. 이때 주의할점은 이미 처리된 면이나 부모 노드가 다른 쪽은 대상에서 제외된다는
것이다. 우선 앞 노드에 대해 앞의 과정을 재귀적으로 계속 처리하고 완료하면 다시 최상위의 뒤쪽 노드에 대해서도
같은 식으로 적용한다. 그러면 <그림 10>과 같이 BSP노드 정보가 완성된다.

마지막에 위치한 노드는 최종적으로 존재할 수 있는 노드로서 이 노드의 안쪽에 있으면 지형 내에 존재하는것으로
판단된다. NULL노드에 위치하거나 최종 노드의 바깥쪽에 있으면 지형을 벗어나는 것으로 간주한다. 이제 이러한 
정보를 갖고 임의의 위치나 지형 안에 포함되는지를 검사해보자.

 

<그림 12 >처럼 별표의 위치에 게임의 캐릭터가 존재한다고 가정할 때 BSP노드의 정보를 따라 검색하면, 우선 지
정된 위치는 10면의 뒤쪽 -> 6면의 뒤쪽 -> 9a면의 앞쪽 -> 5b면의 앞쪽이라는 방식으로 도형안에 속해 있음을 알
수 있다. BSP트리 생성의 과정을 C++로 작성하면 다음과 같다.

BspNode * BSP :: Make(Model * pModel )
      //노드 생성
      BspNode *pNode = new BSP_Node( );
      //모델에서 분단면으로 쓸 폴리곤 선택
      Polygon *pPolygon = pModel- >GetPartitionPolygon();
      //더이상 분할할 수 없는 경우
      if ( pPolygon ==NULL ) return node;

      //분단면을 트리 구조에 보존
      pNode -> SetPartitionPlane ( pPolygon );
      //선택한 면으로 모델을 이등분
      Model *pFront, *pBack ;
      pFront = SplitFrontModel (pModel, pPolygon);
      pBack = SplitBackModel (pModel, pPolygon);

      //BSP 트리를 만들기 위해 재귀적으로 분할해 트리에 추가
      pNode->LinkToFront ( Make ( pFront ) );
      pNode->LinkToBack ( Make ( pBack) );

이러한 방식으로 BSP를 이용하면 복잡한 지형도 검사 대상을 획기적으로 줄여 짧은 시간 내에 처리할 수 있고,깊이
정렬이 자동적으로 이뤄져 렌더링 속도가 빨라지는 효과도 누릴 수 있다.