#40 메뉴 Graphics\Algorithms\BSP Trees and Painter Algorithms에서 bsp.txt +-----------------------------------+ | BSP 트리의 간단한 설명 | +-----------------------------------+ Mark Feldman이 PC-GPE를 위해 작성 e-mail 주소: u914097@student.canberra.edu.au myndale@cairo.anu.edu.au +-------------------------------------------+ | 이 파일은 전체 PC-GPE파일 모음집과 | | 따로 분리되어 배포되는 것을 금합니다. | +-------------------------------------------+ +------------+------------------------------------------------------------ | 포기성명서 | +------------+ 이 파일이 내적으로 포함하고 있거나 사용이 여러분과 여러분의 정신건강, 컴 퓨터, 배우자, 자녀, 애완동물 등 기타 여러분과 여러분의 존재와 관련된 모든 것에 끼치는 영향에 대한 그 어느것도 저는 책임이 없음을 가정합니다. 이 내용 으로 인해 파생될 수 있는 어떤 보증도 제공되지 않습니다. +----------+-------------------------------------------------------------- | BSP 트리 | +----------+ 이진 공간 분할(Binary Space Partition) 트리는 물체의 위치가 고정되어 있고 사용자의 시점 좌표가 변하는 경우에 3차원 화면을 그리는 데 간편합니다.(비행 시뮬레이션이 고전적인 예가 되겠군요.) BSP는 "Painter 알고리즘"의 확장입니다. 페인터 알고리즘은 화면에 뒤에서 앞 으로의 순서대로 다각형(폴리곤) (또는 텍스쳐 맵)을 그림으로써 이루어집니다. 따라서 다각형의 뒷배경이 먼저 그려지고 앞부분이 그다음에 그려지는 것이죠. 그러나 "고전전인" 페인터 알고리즘은 약간의 문제점을 가지고 있습니다.: 1) 다각형이 또다른 다각형을 지나서 통과할 때 다각형이 정확하게 그려지지 않 는다. 2) 다각형이 각 프레임에 그려지는 순서를 계산하기가 어렵고 상당한 많은 계산 을 필요로 한다. 3) 다음과 같은 주기적 겹침(cyclic overlap)의 경우는 처리하지 못한다.: ___ ___ | | | | __| |_____|___|___ | | | | |__| |_____________| | | | | __|___|_____| |___ | | | | |____________| |___| | | | | |___| |___| 이런 경우에는 여러분이 어떤 순서로 다각형을 그리더라도 제대로 된 모습을 아직 볼 수가 없습니다! BSP는 이런 모든 문제들을 해결하는데 도움이 됩니다. 자, 그럼 설명으로 들어가 봅시다. BSP는 화면의 모든 물체의 정렬된 트리를 작성하여 이루어집니다. 우리가 2차원 세계에 살고 있다 생각하고 다음과 같은 화면을 보았다고 합시다.: +------------------------------------+ | | | | | -------------------- | | 선 1 | | \ | | \ | | \ 선 2 | | \ | | \ | | -------- \ | | 선 3 \ | | | +------------------------------------+ ^ 시점 (여기에서는 시점이 원점이라 가정한다.) 이제 만약 우리가 페인터 알고리즘을 사용한다면, 먼저 선1을 그리고 다음 선2 를 그리고 마지막으로 선3을 그릴 것입니다. BSP를 사용하여 우리는 미리 순서 대로 그리고 트리를 만들 수 있습니다. 우선 우리는 임의의 점 가 물체의 2 면에 또는 선위에 있을 것이라고 합시다.(이것은 서로 다른 면으로 간주될 수 있습니다.) 우리가 트리를 작성하면, 선을 얻어서 그것의 한쪽을 왼쪽에 놓고 다른 쪽의 모든 노드(node)를 오른쪽에 놓습니다. 따라서 위의 예제는 다음 트 리를 가지고 감아올리게 됩니다.: 1 / 2 / 3 양자 택일로, 우리는 또 아래와 같은 트리를 가지고 감아올릴 수 있습니다.: 2 / \ 3 1 선2는 머리노드이고 선3은 원점으로서의 선2와 같은면에 있고 선1은 반대편에 있다는 것을 기억하세요. 이제, 저는 여러분이 "하지만 안면에서 걸리면, 선3이 어떻게 머리노드가 될 수 있을까요? 그것의 어떤면이 선2위에 있게되죠? "라고 말하는 것을 듣게 되겠 죠. 그래요. 소년소녀 여러분, 어딘가 끊긴곳이 있어야 하고 이것이 그것입니 다. 여기에서 여러분이 할 일은 선2를 두 개의 선으로 분리해서 각 부분을 선3 에 각면으로 깔끔하게 연결하는 것입니다. 따라서 여러분은 다음과 같은 트리를 얻게 됩니다.: 3 / \ 2a 2b \ 1 선2a와 선2b는 원래의 선2의 분할입니다. 만약 여러분이 그들 *모두*를 화면에 그린다면 전체 선을 그린것처럼 보이게 될 것입니다. 아무튼 여러분이 화면에 그릴때마다 그것의 각 노드를 거쳐야만 하기 때문에 BSP 트리의 균형에 대해서는 걱정하지 않아도 됩니다. 기법은 트리를 연결하는 방법을 구현하는 것이며 따라서 여러분은 적어도 다각형 분할의 *최소* 수를 얻 게 됩니다. 저는 트리에 삽입되는 각각의 다각형을 살펴보고, 만약 그것이 다음 에 삽입되어 최소값을 만드는 하나를 선택한다면 얼마나 많은 분할이 이루어지 는지를 계산함으로써 이것을 다룹니다. 이것은 제 생각엔 매우 느린 접근 방법, O(N^2), 이지만, 대개의 게임에서 여러분이 게임을 개발할 때 한 번 정렬될 뿐 이지 게임 자체에서는 쓰이지 않을 것입니다. 이 개념들을 3차원으로 확대하는 것은 상당히 직선적입니다. 다각형1이 BSP 트 리의 맨위에 있다고 하고 다각형2를 삽입하도록 합시다. 만약 다각형2의 모든 점들이 다각형1의 한면 또는 다른면에 떨어진다고 하면 여러분은 그것을 다각형 2의 왼쪽 또는 오른쪽 노드에 삽입합니다. 만약 어떤 점들이 한면에 떨어지고 나머지가 다른면에 떨어진다면 여러분은 각 다각형이 있는 평면과 이 선을 따라 다각형2를 분할함으로써 형성된 교차점의 선을 그려야만 합니다. 이들 2개의 새 로운 다각형들은 각각 다각형1의 다른 면에 떨어지게 될 것입니다. BSP 트리에서 물체를 그리기 위해 여러분은 최상의 노드로부터 시작하여 여러 분의 시점이 있는 좌표에 물체의 면을 그려나갑니다. 그런다음 *다른* 면을 위 한 노드를 거치고 현재 물체를 그리는 것입니다. 그런다음 시점의 좌표가 있는 면을 위한 노드를 거쳐가는 것입니다.