3D 프로그래밍을 위한 위밍업 : BSP ( Binary Space Partitioning) , BSP Tree
프로그래밍/3D프로그래밍 2006/06/29 00:543D 프로그래밍을 위한 위밍업 : BSP ( Binary Space Partitioning) Tree
by Xevious7 (2006.6) http://www.xevious7.com
이 글은 저의 복습과 3D 프로그래밍을 입문하는 초보 프로그래머 그리고
복습을 위한 용도로 쓰여진 글입니다.
BSP 는 사실상 컴퓨터공학 , 아니 더 정확히는 컴퓨터 그래픽스를 공부하거나
연구하는 사람에게 있어서는 , 천문학에서의 혜성이나.. 신성이나 아님 소행성이나
이렇게 보아도 될정도로 단골 연구주제중의 하나입니다.
위의 말이 이해가 안된다구요? 갑자기 혜성이라니...
정확한 연도는 기억이 안나지만 90년대에 새로운 신성(Nova)가 발견되었을때
저희 교수님이 한말이 앞으로 천문학자들 몇십년은 저 신성으로 먹고 산다...
라는 말을 했었지요. 우스개 소리지만 과학에 있어서 하나의 이론이라 사건
발견은 수십 또는 수백년에 걸쳐서 연구되기도 한다는 것입니다.
얼마전에 미분과 극한 이라는 포스트에서도 극한이라는 개념이 나오기까지
수학자들이 160년간 연구했다는 것을 생각해보십시요.
(참조글 http://www.xevious7.com/92 미분과 극한)
BSP 개념은 극한과 같은 개념에 비교하자면 소행성 B와 태양과의 비교라고 할까요.
어려울것이 없는 극히 단순한 개념입니다.
BSP 는 이진공간분활 (Binary Space Partitioning)이라는 뜻이며 이진트리의
변형의 트리형태의 자료구조인 BSP Tree를 사용하여 공간을 계속적으로
분활해가는 방법을 말합니다.
BSP Tree는 보통의 자료구조론에서 단골로 나오는
메뉴중 ( 스택, 큐 , 리스트 , 트리) 하나인 트리 자료구조입니다.
보통 트리구조라고 하면 Tree 즉 나무 나무구조라고 생각하면 됩니다.
컴퓨터에서 트리구조는 정말 사방에 깔렸다고 생각할 만큼 빈번하게 쓰여지는
자료구조입니다. 아까 말했던 사인방(스택 , 큐 , 리스트 , 트리)는 사실상
프로그래머라면 머리속에 완벽한 개념과 코드가 살아있어야 합니다.
여담이지만 얼마전에 제 밑에 있는 초보프로그래머에게 몇가지 조언을 해주었습니다.
그 키포인트는 문제해결방법에 대해서 더 많이 공부하라는 것이였습니다.
서점에가서 데이타구조와 알고리즘에 대한 책까지 사주었습니다. (네.. 그래픽 API나 Socket API공부하면서 어떤 목적 프로그램을 짜는 것보다 엄청나게 재미없는 일입니다. 왜 그 재미있는 알고리즘 책들이 하나같이 따분하게쓰여져있는지 이해할 수 없습니다. 요즈음은 수학책도 재미있는 책들이 많이 나오는데말이죠.) 하지만 옆에서 보니 윈도우즈 API를 공부하더군요. 사기라는 것은 중요하기
때문에 특별히 뭐라고 하지 않았지만 좀더 알고리즘 책을 공부했으면 하는 생각이 들었습니다. 누차 말했듯이 API는 API일 뿐입니다. ;;
한마디의 말을 감사히 받아 들일줄 아는 사람이 되어 봅시다.
다시 트리구조로 돌아가봅시다.
나무가 어떻게 생겼죠. 나무 생긴 모양처럼 뿌리로부터 가지들이 쭉 뻗어나고
그 가지에서 다시 작은 가지 형태로 만들어지죠.
그러한 모양처럼 데이타를 개념적으로 그러한 나무모양처럼 저장해서 쓰는
구조를 트리라고 합니다. 내 컴퓨터에서 가장 쉬운 예를 들어 보면
C드라이브 - 디렉토리 - 디렉토리 - 디렉토리.. 형태로 구성되는 파일구조도
하나의 트리구조입니다. 뿌리로 부터 퍼져가는 구조는 다 트리구조인것이죠.
보통 익스플로러는 왼쪽부터 오른쪽으로 펼쳐지게 파일을 나열합니다.
나무를 엎어놓은 모양이죠. 가끔 트리구조를 생각할때면 나무처럼 루트 디렉토리는
밑에 있고 하위 디렉토리는 위로 퍼지는 구조를 생각해보곤 합니다. 아무래도
쓰기 불편하겠죠. ^.^;;
이진트리는 말 그대로 가지가 오직 두개로만 뻗어가는 형태의 트리구조를 말합니다.
BSP Tree는 이 이진트리의 하나 입니다. 그냥 이진트리라고 해도 무관합니다.
왜냐면 이진트리이기 때문입니다. 하지만 모든 이진트리가 BSP Tree가 되는것은
아닙니다. 다시 말하면 집합으로 생각하면 이진트리 > BSP Tree 형태로 BSP Tree는
이진트리에 속하는 것이죠.
BSP Tree는 다음 그림 처럼 만들어지는 이진트리를 말합니다.
[그림 - 위키피디아 참조]
이런 BSP Tree를 이용하여 많은 컴퓨터 그래픽스 연구자들은 여러가지 알고리즘과
이론들을 1969년 부터 현재까지 내놓고 있습니다. 이러한 컴퓨터 그래픽스 관련 알고리즘
과 분야는 보통 사람들이 기대하는 것보다 훨씬 많이 그리고 지속적으로 나오고 있습니다.
왜냐고요.. 그들은 컴퓨터 그래픽스를 연구하는 것이 일이기 때문이죠.
이러한 BSP가 게임프로그래머들 사이에 익숙한 단어가 된것은 ID소프트의 퀘이크
때문이었습니다. 퀘이크는 BSP를 이용해서 3D 월드를 구성하고 (3D월드의 데이타를
BSP트리를 이용하여 저장을 해놓았다는 의미입니다.) 그것을 랜더링하는
형태의 엔진을 사용했기 때문입니다. 게임쪽에서 최초로 응용을 한것이죠.
존 카멕이 인정을 받는 이유는 다른 이유에서가 아니라 느린 하드웨어를 극복하기
위해서 학술적인 논문이라도 찾아서 수십개의 엔진을 디자인 또 디자인 해서 최적을
찾아내는 노력에 있습니다. 다시 말하면 문제해결(빠른 렌더링)을 위해서
알고리즘에 대해서 수없이 생각했다는 것입니다. 커다란 디자인의 승리이지
작은 구현을 위한 함수의 승리가 아닙니다.
사실 BSP는 어려운 개념이 아니기 때문입니다. 같은 도구를 주어도 어떤사람은
훌륭한 조각을 만들지만 어떤사람은 나무하나 자르지 못할 수 있습니다.
얼마나 노력하고 고민하고 그 도구를 이해하려 했는가 라는 것이 중요한것입니다.
퀘이크가 개발될 시기의 그래픽카드들은 현재의 카드와 비교해서 정말 너무나도
느린 하드웨어였습니다. 물론 CPU도 마찬가지죠. 이 당시 은면처리(Hidden Surface Removal) 같은 것을 하드웨어에서 지원하지 못했습니다.
이것을 미카엘 에브리쉬는 VSD라고 표현했습니다.
VSD는 Visual Surface Determination 이라는 뜻의 약자입니다. 보이는면 결정하기라는
뜻입니다.
존 카멕은 월드맵 데이타를 미리계산하여 PVS (Potential Visual Set) 만들었습니다.
즉 Quake의 상의 가능한 뷰포트(Viewport) 각각에 폴리건(Polygon)의 PVS를
만들어 BSP트리에 저장을 해놓고 실제 런타임에서는 BSP트리를 왔다갔다 하며
보여주는 형태의 아이디어를 낸것입니다. 다른 말로 하자면 미리 은면처리가 된
폴리건의 PVS를 왔다갔다 하면서 화면에 뿌리는 것이기 때문에 엄청나게 빠른
속도를 만들어 낼수 있는 것이 되는 것입니다. 단순하지만 이것이 핵심 아이디어
입니다.
정리하자면
문제 : HSR 처리는 너무 느리다.
해결의 포인트 : 미리 은면처리가 계산된 데이타를 사용한다.
알고리즘 구현도구 : BSP Tree
이런 형태입니다. 이것의 구현은 또다른 문제이지만 문제를 단순화하여
핵심을 뽑아내는 작업이야 말로 프로그래밍의 핵심이라고 저는 생각합니다.
그렇지 않고 구현에만 신경쓴다면 100이면 100 항상 같은 프로그램이 나올수
밖에 없고 결국 새로운것을 못 만들어내고 따라가기만 하게 될 것이기 때문입니다.
(구현이 중요하지 않다는 말은 아닙니다. 구현하지 못하면 아무 소용이 없는것이죠
하지만 아이디어만 명확하다면 즉 알고리즘만 명확히 정의되면 구현은 어찌되었든
할 수 있다는 것은 명백한 일입니다.)
한가지 더 BSP에 대해서 알아두어야 할 사항은 현재의 하드웨어에 있어서는
은면처리를 위해서 BSP가 더이상 획기적인 효율을 내지 않습니다.
사실상 더이상 사용할 필요가 없습니다. 하드웨어 가속으로 이루어지기 때문입니다.
하지만 다른부분을 위해서 BSP의 응용은 계속되리라고
봅니다. 자료구조의 응용은 하드웨어의 속도가 빨라지더라도 더 효율적인 것을 위해서
계속 사용되어질 것이기 때문입니다.
PS. 문서를 검색해보니 정말 많은 문서가 존재했습니다. 그중에서도 참조할만한
문서를 링크합니다.
http://en.wikipedia.org/wiki/BSP_tree 이제는 필수인 위키피디아 (느린게단점)
http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf
스웨덴 분인 사뮤엘씨의 bsptree에 대한 자세한 설명과 추가적인 발전알고리즘
http://blog.naver.com/ryanii?Redirect=Log&logNo=20016178758 리안님의 블로그
위 문서의 번역본이 있습니다.