All Right ?

[20090428] 게임속 발자취 남기기 [1]

두더지 — Tue, 28 Apr 2009 14:25:27 GMT

게임속 발자취 남기기 1부

많은 게임유저들은 게임속 세계에서 서로 소통한다. 전쟁, 사냥, 수집등의 기본적인 시스템을 바탕으로 계속적으로 게임속 세계에 참여하려 하고 무언가 남기려 노력한다. 하지만 개발자들은 그러한 배려는 해두지 않았다. "자유도"라는 명목아래 유저 스스로 놀게끔 가꾸어 놓았기 때문이다. 전쟁에서 승리하지만 영광은 길드또는 길드장이 갖는다. (길드 내부적인 이슈는 논외로 하자) 사냥, 수집도 마찬가지다 자기만족이겠지만 결과를 다른사람과 공유하기 어렵다.

얼마전 업데이트된 WOW - 리치킹의 분노 - 에서 업적시스템을 도입했다. 자신이 하는 거의 모든 행동이 기록으로 남는다. 또 이렇게 쌓아 올린 행동(업적)은 점수화 되어지지만 사실 플레이어들과 비교하지 않는이상 어떤이가 우리 서버의 최초로 또는 최다의 업적을 이뤄내고 있는지 또는 이뤄냈는지 알 수 있는 길이 없다.

간단하게 판타지 세계를 예로 들어보자 근위대 기사 하나가 나라의 골칫거리 였던 용을 한마리 잡았다. 왕은 이 기사를 위해 잔치를 열어주고 온 국민에게 이 기사의 용맹함을 알린다. 허나 와우에서 공대 하나가 살타리온을 한번에 잡았다고 축하해주는 일 따위는 없다. 업적으로 잡으면 호칭은 주지만 서로 내가 먼저 달고 싶다 경쟁하는 일 따위는 없다는 말이다.

콘솔에서는 X-BOX 360의 도전과제(PS3의 트로피는 후발주자)는 게임에 좀더 몰입할 수 있도록 하는 좋은 시스템이었지만 아직도 이 업적점수(~~오덕점수라고들 함~~)를 제대로 활용할 수 있는 방법이 사실상 없다.

플레이어들은 무언가 계속 게임속에 남기기 원하고 기록하길 원하고 그것을 다른 플레이어들이 알아주길 원한다. "우리 게임에는 업적(도전과제)들이 있으니 남길 수 있어요"라고 말하겠지만 굉장히 귀찮은 순서로 다른 플레이어와 서로 비교하지 않으면 알아보기 힘들다.

나는 이러한 행동들을 유저가 게임속 발자취를 남긴다라고 정의하기로 했다. 게임 시스템에서는 어떻게 유저들의 발자취를 남겨주고 개발자가 정의한 세계에 표현할 수 있게 해 줄 것인가?

-1부 종료-

발자취 남기기에 대한 고민 부터 풀어보았다 남은건 살붙이지

[C++]기초 예제 만들기 시작 - 구구단 계산기-

두더지 — Mon, 13 Apr 2009 18:08:12 GMT

횟수로 5년만에 학교에 복학해 프로그래밍 공부를 처음부터 다시하고 있다;; 머리가 굳었나 "Hello C"도 출력 못하다가 이것저것 책도 찾아보고 블로그에 남겨두기로 했다. 프로그래밍 하는 기획자가 되자 ~~뿅!

=C++예제 ================================구구단 계산기=====================================090318=

#include

using namespace std;

void main()

{

//For문에사용할int형함수i와입력받을su를선언하였다. su는0값으로초기화

int i, su = 0;

//while문을이용해계속적으로값을받을수있게하였다.

while(1)

{

cout<<"입력하신숫자의구구단을출력합니다: ";

//입력하는값의구구단을출력하기위해su값을입력받는다.

cin>>su;

//if문을사용입력받은su의값이2보다작거나9보다클경우아래메시지를출력한다.

if( su< 2 || su> 9)

{

cout<<"입력하신숫자로는계산을할수없어염"<<endl;

}

else

{

cout<<endl<<"==================="<<su<<"단출력==================="<<endl;

//for문을사용해입력받은su와1부터9까지곱해그결과값을차례로출력하도록했다.

for(i= 1; i< = 9; i++)

cout<<su<<"X"<<i<<"="<<i*su<<endl;

cout<<endl<<"==================="<<su<<"단종료==================="<<endl;

}

===================================================================================================

망할 구구단을 출력하는 C++예제를 짜 봤다. 그동안 회사에서 머리가 녹았는지 이 짧은거 치는데
한시간이 넘도록 고생했다 ㅠㅠ

if, for, while문의 활용과 cin, cout기능을 활용해 보았음 -끝-

방명록

두더지 — Mon, 13 Apr 2009 18:03:32 GMT

리플 ㄱㄱ싱

20090414 회상

두더지 — Mon, 13 Apr 2009 17:52:02 GMT

오늘은 강의가 휴강되어 집에서 지난해 회사에서 사용하던 PC에서 백업한 '내문서' 폴더를 열어 보았다. 아무에게도 보여주지 않았던 컨셉기획서며 유머로 사용하던 사진까지 별의 별게 다 들어 있었고 때문인지 다시 지난해를 회상하게 되었다. 그리고는 깊이 다시 뒤를 돌아 보게 되었다.

나는 붕괴된 어느팀에 소속되어 있던 사원, 사실상 ~~망한게임기획자~~, 온라인 게임에 미련을 못버리고 있는터에 잡은 팀이었기 때문에 아쉬움도 컸을때 같은 회사에 있던 기타 많은 팀에 지원(?)할 수 있는 계기가 있어 주저 없이 FPS제작팀에 문을 두드렸다. 아직도 당시에 면접보던 때를 잊을 수가 없다. 아직은 회사가 크기 전 인지라 사무실은 작고 좁았지만 개발냄새(?)가 풀풀 풍기는 분위기임에 틀림이 없었고 좁다면 좁고 크다면 큰 대회의실에서 1시간 가량 면접을 봤다. '왜 책을 읽지 않느냐?' 라는 질문을 처음 받은 날이었고 그날 이후로 내가 달라진것이 있다면 책을 읽는 습관을 들이게되었다는 것 또한 나는 얼마나 조화로운 사람인가 라는 자기질문에 계속해서 답변하게 만드는 계기가 되었다. 질문중 많은 것들이 생각나진 않지만 몇가지를 적어 보자면

가장 존경하는 기획자는 누구인가? 있다면 왜 그를 존경하는가?
인생에서 정말 잘했다 생각하는 두가지만 이야기 해 보라. 있다면 왜 그러한가?
최근에 읽었던 책중에 가장 인상깊었던 책은? 있다면 왜 그러한가?

등이었다. 1번 물음에 나는 '없다'라고 대답했다. 가장 흔하게 나오는 대답들은 이미 알고 있었지만 대답하고 싶지 않았다. '미야모토 시게루', '윌 라이트', '코지마 히데오'등 뻔한 크리에이터들을 나열해 봤자 나는 그들과 일해보지 않았으며 그들이 어떤 사고를 하고 있었는지 알 수 없다. 단지 그들은 내게 성공한 게임을 만든 사람들일 뿐이었기 때문이었다. 한가지 확실한건 이전 회사에서 느꼈던 것들은 창의적인 사고 보다는 빠른 결과물(성과)를 낼 수 있는 기획서만을 원했기 때문에 내가 혹시나 그들의 창의적 마인드를 존경한다 해서 그들처럼 할 수 있는 것들도 아니었기 때문이었다. 2번 물음은 개인적인 내용이라 일단 생략..

3번 물음에 '죄송합니다 최근에 책을 읽지 않았습니다' 라고 대답했다. 나중에 들은 이야기 였지만 이 질문 하나 때문에 나는 팀에 들어갈 수 없을뻔 했다. 누가 생각해도 감점 요소임에 분명하지만 거짓말은 바로 티가 나므로 사실상 이런질문에 당황하기 보다는 솔직하게 말하는 편이다. 머 어찌되었든 내 기획자로서 시간중 가장 기억에 남을 시간이 이때부터 시작 되었다.

이래저래 바쁘게 보내다 보니 2년이라는 시간이 흘렀다. 몇몇은 팀을 나갔고 많은이들이 새롭게 팀원이 되었다. 나와 맞는 사람 그렇지 않는 사람도 있었지만 어느조직이나 그렇듯 별 대수롭게 생각하지 않았었는데 어느날 부터 왠지 게임이 산으로 가고 있다는 생각이 부쩍 들었다. 조심스럽게 가까운 사람들과 이야기를 나눴을때 확신이 들었다. 흔히들 말하는 '불평 불만의 시간'이 어김없이 찾아왔던 것이다. 사실 이 시기를 슬기롭게 대처하지 못했다. 방대한 정보가 귀에 흘러 들어오고 있었고 때문에 판단력도 흐려지기 시작했다.

개인적으로 스트레스에 굉장히 강하다고 생각했지만 이 기간은 아무래도 잊을 수 없는 개발기억으로 남을것 같다. 1년사이에 얼굴이 팍삭 늙었더라 잘 모르고 있었는데 후배가 보내준 1년전 사진은 지금의 내 모습이 아니었기 때문에 새삼 깨닿게 되었다. 퇴사 3개월 정도 전부터 일하기가 싫었다. 작업은 전부 반복의 연속이었고 때문에 성취감따위는 없었다. '우리'라는 생각을 늘 가지고 왔었지만 이때부터 '나는'이라는 생각이 들어 왔었고 나를 위해 퇴사를 해야겠다고 생각했었다. 결국 큰소리 치고 회사를 그만두었지만 속이 시원하진 않고 오히려 더 찜찜했었다.

그리고 몇개월이 흐른뒤에 그 모습을 다시 회상하고 나니 아쉬운것들이 너무나도 많이 남아 있게 되었다. 조금더 열심히 해볼걸 까지꺼 한번 이겨내 볼걸 하는 별에별 아쉬운 생각들이 많이 났다. 그리고 2007년 여름 다함께 웃으며 단체사진을 찍었던 때가 생각났다. 사람은 그리워 해 본적이 있지만 오늘 처음 팀이 그리워진 하루였다. 몇년뒤에 더 좋은 얼굴로 다시 만나 볼 수 있기를 기원하며 오늘 하루를 마치려고 한다.

PS. 개발 멘토가 되어 주었던 전석환 차장님 그동안 감사했습니다. 그리고 죄송합니다. 형으로써 언제나 나를 잡아주셨던 철기형 동근이형 정말 고맙구요 광호는 프로젝트 5개 남았으니까 그때까지 무럭무럭 자라서 보자~

[BSP] BSP 논문 7, 8, 9, 10장.. etc

두더지 — Wed, 30 Jul 2008 04:47:26 GMT

자료 출처: http://blog.naver.com/ryanii 리안

리안님께 감사드립니다. 블로그 운영이 근래에 되고 있지 않아 따로 감사의 말씀을 전하지 못한점 죄송하구요
좋은 글 잘 보았습니다.

원문 출처: http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf

원문다운로드클릭

BSP Trees and Polygon Removal in Real Time 3D Rendering
-Samuel Ranta-Eskola. 2001.1.19

[Chapter 7]

- Network Optimization Using BSP-trees -

오늘 우리는 컴퓨터 프로세싱과 그래픽 처리 능력에 대해서 대단하다고 생각할 수 있는 한계들을 통과해 왔습니다. 대신 네트워킹에는 여전히 여러 문제들이 존재하며 아직도 많은 유저들은 모뎀을 사용하여 통신하고 있습니다. 멀티플레이어 게임이 가능한 많은 유저를 얻기 위해선 반드시 모뎀 통신으로도 돌아갈 수 있게 설계되어야만 합니다. 다음과 같은 경우를 생각해보면 왜 이것이 문제가 되는지 알 수 있습니다. 15명 정도가 접속할 수 있는 서버를 이용한 멀티플레이어 게임이 있다고 합시다. 그리고 서버는 월드를 초당 20번 업데이트 한다고 합시다. 만약 모든 클라이언트들이 매 업데이트마다 다른 모든 클라이언트들의 정보를 얻으려 한다면 각각의 클라이언트 사이에 매 초당 아주 많은 양의 데이터들이 전송되야함을 뜻합니다. 한 클라이언트가 매 프레임 마다 얼마나 많은 패킷을 받을지 계산하기 위해서 각각의 유저가 매 프레임당 얼마나 많은 양의 정보를 보내는지 알아야 합니다. 만약 최소한으로 생각하여 벡터의 이동이 있다고 했을때, 세 개의 float(4 bytes)으로 이루어진 이동 벡터, 위치 벡터, 회전 벡터가 있다고 할 수 있습니다. 그리고 6바이트 정도의 패킷 오버헤드가 있다고 하겠습니다. 그러면 모든 패킷은 3*3*4+6 = 42 바이트가 됩니다. 이제 모든 클라이언트는 초당 20번씩 다른 클라이언트들에 관한 정보를 얻어야 합니다. 따라서 모든 클라이언트는 매 초마다 20*15*42 = 12600 바이트를 받게 됩니다. 55.6 모뎀은 최적화된 상태에서 초당 55600/8 = 6950 바이트를 받을수 있습니다. (물론 이런 최적 상태는 일어나지 않습니다.) 때문에 모뎀을 사용하는 사용자들에게 명확하게 오버플로우가 되버릴 것입니다. 서버쪽에서도 대역폭이 필요함은 말할 것도 없습니다. 이것으로 많은 양의 비트를 잘라내야할 필요가 있다는 것이 명확해집니다.

여기서 다시 BSP-tree의 구조가 유용하게 됩니다. "보이지 않는 것은 그리지 않는다"의 원리를 기반으로 하는 렌더링과 마친가지로 네트워크 역시 오직 유저로 부터 보이는 오브젝트들만의 정보를 보냄으로써 최적화 될 수 있습니다. 이것은 각각의 유저들에게 보이는 오브젝트들만의 정보를 보내는 포탈 엔진으로 구현할 수 있습니다. 정적인 PVS를 가졌을 때 현재 유저가 위치하는 노드의 리프에서 보일 수 있는 리프들에 속하는 오브젝트의 정보들만 보내는 것입니다. // 서버에서 보낸다는 말 // 좋은 맵에서는 이것으로 상당히 많은 양의 보내져야 하는 데이터들을 줄일 수 있을 겁니다.

Related reading:
[Sweeney, Tim. Unreal Networking Architecture]

[Chapter 8]

- Furture Work -

이 논문에서 나온 여러가지 해법들을 향상 시킬 수 있는 것들이 수만개는 있습니다. 몇 가지 예가 향상된 충돌 알고리즘들인데, 보이지 않는 오브젝트들의 제거와 정적인 PVS를 가지는 포탈 엔진을 만드는 것입니다. 다음은 이 논문에서 언급하지도 구현하지도 않은 것들 입니다.

비록 이 논문에서 제시한 충돌 체크 알고리즘이 만족할 만한 성능을 가진다 하여도, 여전히 보다 좋게할 수 있습니다. 아마도 박스가 오브젝트를 묶는데 더 좋을 것입니다. 경계 박스(bounding box)가 경계 구(bounding sphere)보다 많은 계산을 필요로 하지만 결과는 더 좋게 보일 것입니다.

오브젝트들은 월드상의 기하들보다 복잡하기 마련입니다. 다시말해 보다 많은 폴리곤으로 구성됬다는 것입니다. 따라서 보이지 않는 많은 오브젝트들을 가능한한 많이 제거할수록 좋습니다. 우리의 방법은 보일 수 있는 리프에 있는 모든 오브젝트를 그립니다. 만약에 가려진 오브젝트를 제거하는 빠른 알고리즘이 개발될 수 있다면 성능을 향상시킬 수 있습니다.. 하지만 그냥 화면에 오브젝트들을 그리는 것 보다 값이 싼 오브젝트 제거 알고리즘을 만드는 것은 매우 까다롭습니다.

만약에 정적 PVS를 가지는 포탈 엔진을 만든다면 거울이나 쉬운 오브젝트 제거와 같은 포탈 엔진의 모든 장점을 얻을 수 있지만 그려져야할 섹터를 찾거나 월드의 조명 처리등의 연산을 값싸게 처리할 수 있는 정적인 PVS 힘의 유용성을 포기할 수도 있습니다. // 여기서 원문에 나오는 draw가 무슨 뜻인지 정확히 못찾았는데요. 문맥상 부정적 뜻이라고 생각했습니다. //

예측(prediction)은 멀티플레이어 게임에서 중요한 것입니다. 이것의 목적은 클라이언트들이 가능한 올바른 화면을 가지는 것입니다. 다시 말해 서버와 많이 다르지 않다는 것입니다. 우리의 방법은 단순히 서버가 보내는 위치값을 넣는 것입니다. 이것은 만약 서버로부터 클라이언트가 데이터를 얻는데 200ms 가 걸린다면 클라이언트는 200ms 이전의 월드의 이미지를 가지는 결과를 가져옵니다. 만약에 오브젝트가 이전의 움직임을 바탕으로 지금이나 적어도 서버 데이타 이후에 있을 곳을 예상할 수 있다면 보다 정확한 월드를 볼 수 있습니다.

[Chapter 9]

- Conclusions -

3D 엔진을 만들때 BSP-tree는 매우 많은 이점을 가지는 유용한 구조체입니다. 비록 원래 목적이 폴리곤을 정렬하여 화면에 그들을 올바른 순서대로 그리는 것으로 지금은 무의미하지만 아직 많은 영역에서 그 유용성은 여전합니다. 보다 빠른 충돌 체크라던지 가려진 면의 제거 그리고 네트워크 최적화와 같이 말입니다. 하지만 여전히 향상될 부분들이 많이 존재합니다. 이어지는 내용은 BSP-tree의 장점과 단점입니다.

장점들

- 빠른 충돌 체크. 오브젝트를 리프에 위치시키는 것이 쉽기 때문에 맵의 큰 부분을 쉽게 무시할 수 있습니다. 이렇게 하고나면 오직 리프에 있는 폴리곤들만이 충돌 체크에 필요합니다.

- PVS와 함께하면 맵의 보이지 않는 부분의 제거를 매우 쉽게 처리할 수있습니다.

- 네트워킹을 최적화하는데 이용할 수 있습니다.

- 맵의 조명 계산을 최적화하는데 이용할 수 있습니다.

단점들

- BSP-tree는 오직 정적인 월드에만 적합합니다. 월드에 폴리곤을 추가하거나 제거하는 것이 가능하지만 이를 위해선 BSP-tree부분을 다시 계산해야만 합니다. 메인 BSP-tree와 함께 겹쳐진 로컬 BSP-tree를 사용하는 것도 가능한 최적화 기법이지만 여전히 BSP-tree가 정적인 월드에 보다 잘맞는 것이 사실입니다.

- BSP-tree의 사용을 아주 효과적이게 하려면 PVS나 이와 비슷한 기법들의 추가가 여전히 필요합니다. 그렇지 않으면 아마도 수많은 폴리곤들을 고려해야 할 것입니다. (특히나 큰 맵이라면)

- BSP-tree 기법은 매우 복잡합니다.

BSP-tree는 아마도 게임 산업에서 앞으로 5년에서 10년정도는 계속 존재할 것입니다. 바라건대 누군가가 보다 영리하고 동적이며 BSP-tree가 갖는 이점을 똑같이 가지는 것을 발명할 것을 희망합니다.. BSP-tree의 가장 큰 문제는 그들의 복잡성입니다. 모든 작업이 효율적이기 위해 너무 많은 부분을 필요로 합니다. 따라서 이상적인 해법은 더욱 많이 단순하고 직관적이여 합니다.

BSP-tree의 대안으로 모든 오브젝트가 같은 부모로 부터 파생되는 씬그래프(scene-graph)같은 것이 있을 수 있습니다. 각각의 오브젝트는 자신이 위치하는 곳을 압니다. 모든 오브젝트는 그들이 어떻게 그려져야 하는지, 그들 안에서 충돌이 어떻게 일어나는지, 볼수 있는 이웃이 어떤 것인지 압니다. 이것은 월드를 전부 재구성(re-render)할 필요없이 삽입과 삭제하는 부분을 매우 쉽게 만듭니다. 또한 BSP-tree의 사용으로 일어나는 복잡성을 해결하는 보다 우아한 방법이 될 수 있습니다. 왜냐하면 어떤 오브젝트도 다른 오브젝트의 타입이 무엇인지 알 필요가 없기 때문입니다. 그들은 모두 같은 인터페이스로 구현되며 오직 그 인터페이스만을 통해서 통신할 것입니다.

[APPENDIX]

이것은 개발된 기법들을 사용해서 상용화한 제품의 스크린샷들 입니다.

<그림 - 원문 참고>

[BIBLIOGRAPHY]

<원문 참고>

----------------------------------------------------------------------------------------

퀘이크의 맵파일인 bsp 로딩하는 것을 만들어 보려다가 사실 로딩 자체는 굉장히 쉽다는 걸 알았습니다. 핵심은 바로 디자이너가 그린 맵을 bsp로 만드는 법이더군요. 만드는게 어렵지 일단 만들어진 것을 가져다 보여주는 뷰어는 하루면 뚝딱 만들수 있을거 같았습니다.

그래서 뷰어를 만드는 것 보다 BSP-tree 생성, CSG 처리, Portal, PVS 등등의 생소한 개념들을 아는게 핵심적인거 같아 자료를 한참 찾아봤습니다. 비록 이 논문도 완벽하진 않지만 그래도 제가 궁금해하던 부분을 거의 아우르고 있고 내용도 괜찮다 싶어서 번역해봤습니다.

아쉬운건 오타가 좀 있고 (의사코드에도..) 포탈 생성부분의 설명이 깔끔하지가 못하더군요. 모 그래도 이런 개념들을 처음 잡고 가기에는 괜찮은거 같습니다^^ 완벽하게 이해하지 못한 상태로 번역을 해서 오히려 이해를 방해하지 않나 걱정이네요 =+= 끝~.

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com

[출처] [번역] BSP-tree 논문 : 7~10장, etc|작성자 리안

[BSP] BSP 논문 6장

두더지 — Wed, 30 Jul 2008 04:45:45 GMT

원문 출처: http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf

원문다운로드클릭

BSP Trees and Polygon Removal in Real Time 3D Rendering
-Samuel Ranta-Eskola. 2001.1.19

[Chapter 6]

- Physics in BSP-trees -

BSP-tree에 기반을 두는 3D엔진을 개발할 때 매우 흥미로운 문제들중 하나가 충돌 체크입니다. 이것을 매우 빠르게 처리해야 하지만 그만큼 어려운 것은 아닙니다. FPS게임에서 대부분의 프로세서 타임은 충돌체크를 할때 소비됩니다. 월드를 돌아다니는 오브젝트나 아바타를 생각해 봅시다. (이제부터 아바타도 오브젝트로 생각하겠습니다.) 오브젝트는 기하 요소들과 다른 오브젝트들에 대하여 이들을 통과하진 않는지 혹은 너무 가까이 있지 않은지 따져봐야 합니다. 하나의 아바타나 오브젝트는 이런 체크를 느린 알고리즘을 통해서도 수용할 만한 프레임으로 처리할 수 있습니다. 문제는 여러개의 오브젝트들과 아바타들을 다뤄야만 할때 매우 복잡해 진다는 것입니다. 화면에 월드를 렌더링하는 것은 프렘당 한번만 하면 되지만 충돌 체크는 현재 월드에서 움직이는 오브젝트의 개수에 따라서 프레임당 수백번을 필요로 할지 모릅니다. 따라서 충돌 체크 알고리즘을 매우 빠르게 하는 것은 아주 중요합니다.

충돌을 다루는 알고리즘을 설계하기에 앞서 몇 가지 결정을 할 필요가 있습니다. 오브젝트들은 반드시 하나 또는 그 이상의 간단한 기하 도형들로 캡슐화해야 합니다. 왜냐하면 오브젝트에 있는 모든 폴리곤 하나하나를 다른 모든 것들과 체크하면서 수용할 만한 프레임율을 얻는 것은 불가능 하기 때문입니다. 저는 각각의 오브젝트를 xz평면에서 하나의 반지름과 y축으로 하나의 반지름을 가지는 타원체로 캡슐화하기로 선택했습니다. 만약 여러 개의 도형을 선택한다면 이들이 서로 상호작용하게 만들어야 할 필요가 있는데 이것은 매우 복잡한 문제입니다. 아래 예제는 사람을 캡슐화한 것입니다.

그리고 나서 오브젝트가 어떤 것과 충돌했을 때 무슨 일이 일어날지 결정할 필요가 있습니다. 한 가지는 충돌이 감지되면 움직임을 멈추고 원래의 자리에 머무르게 하는 것입니다. 이것은 벽에서 튕기는 것과 같은 매우 나쁜 행동을 보여줍니다. 아래 그림의 두 이동은 같은 거리를 이동합니다. a의 위치로 이동하는 것은 금지되어 제자리에 머물게 될 것입니다. 그러나 b의 위치로 이동하는 것은 가능합니다. 이는 만약 벽을 따라 움직이게 되면 벽에 매우 가까이 갈수 있다는 것을 의미 합니다. 반면에 벽을 향해 직선으로 움직이는 것은 훨씬 그 이전에 금지될 것입니다. 따라서 오브젝트들은 벽에서 튕겨지게 됩니다.

위의 그림에서 a로 이동하는 것은 허락되지 않지만 b로 이동하는 것은 허락됩니다. 이 아이디어의 또 다른 약점은 오브젝트들이 벽에 붙은 것과 같이 움직일 것이라는 겁니다. 왜냐하면 오브젝트들이 벽을 따라 이동하려 할 수록 벽에 붙게되기 때문입니다.

보다 좋은 방법은 오브젝트들이 벽이나 다른 오브젝트들에 대해서 미끄러지게 처리하는 것입니다. 이것이 비록 덜 효율적인 처리이지만 결과가 많이 부드러울 것입니다. 이것이 제가 선택한 방법입니다.

오브젝트의 이동은 다음과 같이 세 부분으로 나눌 수 있습니다.

1. 다음 위치 계산
2. 충돌 체크
3. 충돌 핸들링

매 프레임 마다 월드에서 움직이는 오브젝트는 이와 같은 단계를 거쳐야 합니다.

- Future Position Calculation -

오브젝트의 원래 위치, 속도, 가속도, 방향, 현재 마찰 계수 그리고 흐른 시간이 주어진 상태에서 오브젝트의 다음 위치를 계산하는 것은 매우 쉬운 부분입니다. 우리는 계산에서 미터와 초단위를 사용하며 오브젝트의 질량은 무시합니다. 모든 오브젝트의 질량이 1임을 가정합니다. 간단히 하기 위해 중력은 항상 아래로 작용하고 힘은 xz평면에서만 작용한다는 것을 가정합니다. 다음 단계들이 오브젝트의 다음 위치를 구하는 우리의 해법입니다.

1. 마찰로 인한 속도 감소를 뺍니다. xz평면위의 가속도에서 마찰 계수(0.0, -1.0)를 뺍니다. 질량이 1임을 가정했기에 더 이상의 계산은 필요하지 않습니다.

Formula:
Acceleration(x,z) -= Friction

2. 사용자로 부터의 힘을 x,z방향의 가속 벡터에 더합니다. 사용자에 의해 더해진 힘과 프레임 시간을 곱하고 x,z 방향의 결과 벡터를 가속 벡터에 더합니다. 질량이 1이라고 생각하므로 힘의 단위는 Newton/kg 입니다.

Formula:
Acceleration(x,z) += Force * Normalize (Direction(x,z))

3. y 방향으로 중력 가속도를 정합니다. 전통적으로 사용되는 중력값은 9.82이나 게임에서 이렇게 하면 추락이 매우 빨라서 재미가 없기 때문에 이보다 낮은 중력값을 사용하는 것이 일반적입니다.

Formula:
Acceleration(y) = -Gravity

4. 이동 벡터에 가속 벡터를 더합니다. 이것은 x,z 방향의 가속에 프레임 타임을 곱한 것을 더하면 됩니다. x,z 방향으로 이동 속도를 제한하는 것은 좋은 생각입니다. 그러면 오브젝트들은 언젠가 최대 속도에 달하게 됩니다. 그렇지 않으면 계속적인 힘의 작용으로 오브젝트의 가속이 무한대로 가게 될 수 있습니다.

Formula:
Movement = Movement + Acceleration * FrameTime

5. 이제 이번 프레임에서의 위치 변경자를 계산해야 합니다. 프레임 타임과 이동 벡터를 곱하면 결과 벡터는 이번 프레임에서 오브젝트가 가야할 거리입니다.

Formula:
Distance = Movement * FrameTime

6. 이제 예상 위치를 계산할 수 있습니다. 현재 위치에 가야될 거리를 더하면 이번 프레임에서 오브젝트가 가야할 좌표가 나옵니다. 이 값은 모든 충돌 체크에 쓰일 것입니다.

Formula:
NewPosition = Position + Distance

자 인제 이 예상 위치가 유효한 위치인지 체크할 시간입니다.

- Collision Detection and Collision Handling -

이것은 BSP-tree 엔진에서 가장 트릭적인 부분입니다. 물리 엔진에서 이 부분을 설계 할때는 몇 가지 고려해야할 것들이 있습니다. 무엇보다도 효율성이 가장 중요한데 이는 이 부분이 프로세서 타임을 대부분 독차지하기 때문입니다. 두번째는 충돌 체크의 정확성으로 매우 중요한 부분입니다. 알고리즘의 효율성을 감소시키지 않고 좋은 정확성을 얻기는 매우 어렵습니다. 따라서 정확성과 효율성 사이에 트레이드오프(trade-off)가 존재하게 됩니다. 충돌 핸들링은 이 만큼 어렵지 않지만 중요한 부분입니다. 왜냐하면 이것이 올바른 "느낌"을 주는 것으로 부족한 핸들링은 어떤 게임이든 보기 안좋게 만들 것입니다.

여기가 BSP-trees의 힘을 보여주는 부분입니다. 대부분의 엔진들은 BSP-tree를 렌더링 속도를 높이기 위한 포탈 엔진들처럼 사용하지 않습니다. 하지만 아직도 대부분의 엔진들은 이런 기하하적 요소와 상관없이 BSP-tree를 만듭니다. 왜냐하면 충돌 체크 계산에서 대단한 이점이 있기 때문입니다. 말하자면 사용자를 BSP-tree에 위치시키는 것은 매우 쌉니다. 이렇게 하고 나서 체크가 필요한 폴리곤은 그 프레임에서 트리를 타고 내려온 오브젝트가 위치한 리프 노드에 있는 폴리곤들 뿐입니다.

BPS-tree에서 또 다른 강점은 원래의 BSP-tree의 설계대로 각각의 리프 노드가 볼록 집합(convex set)인 폴리곤들 가지고 있다는 것입니다. 이는 어떤 순서로든 폴리곤들의 충돌을 체크할 수 있다는 의미입니다. 만약에 우리의 BSP-tree와 같이 볼록 집합이 아니라면 폴리곤들은 뱡항의 순서에 따라서 체크되어야만 합니다. // 정적인 오브젝트들을 추가되면 리프 노드의 폴리곤들이 볼록 집합이라고 할 수 없습니다. 5장에서 언급된 내용. // 우리는 방향값(facing value)이라는 것을 사용하는데 이는 비교되는 오브젝트에 대해 폴리곤이 어떻게 위치해 있는가를 말하는 값입니다. 이 값은 폴리곤의 법선 벡터와 오브젝트의 정규화된(normalized) 이동 벡터를 내적하여 얻을 수 있으며 -1과 1 사이의 값입니다. -1값은 폴리곤이 오브젝트가 이동하려는 방향에 정면을 향해 있다는 것이고 1값은 폴리곤이 오브젝트가 이동하려는 방향과 같은 쪽으로 향해 있다는 것을 의미합니다.

테스트 순서는 가장 작은 방향값을 가지는 폴리곤에서 가장 높은 값을 가진 폴리곤 순서대로 체크합니다. 이어지는 그림들이 왜 이런 순서대로 체크해야만 하는지를 보여줍니다.

위 그림에서 방향값이 작은 폴리곤은 폴리곤1 입니다. 왜냐하면 오브젝트의 이동 벡터와 폴리곤1의 법선벡터와의 내적이 폴리곤2와의 내적값보다 작기 때문입니다. 따라서 만약에 우리가 폴리곤2에 대해 먼저 체크를 한다면 결과는 다음과 같이 됩니다.

위 그림은 폴리곤2와 충돌하지 않는 그림입니다. 최종 위치가 조정되어 그 결과 폴리곤2와 충돌하지 않게 됬습니다. 이 결과는 오브젝트가 폴리곤1을 통과했다는 느낌을 받게 합니다. 만약에 폴리곤1을 먼저 체크한다면 결과는 다음과 같이 됩니다.

20번 그림에서 움직임이 보다 정확하게 조정되었습니다. 이는 폴리곤1과 먼저 체크하여 충돌하지 않게 만들었기 때문입니다. 최종 위치는 조정되어 폴리곤1과 충돌하지 않습니다.

BSP-tree가 오직 볼록 집합들만을 가질때는 같은 노드에 있는 폴리곤들을 이와 같이 정렬시킬 필요가 없습니다. 하지만 여전히 노드들은 그들이 통과된 순서대로 검색되어져야 합니다.

충돌 체크 알고리즘을 더욱 빠르게 하기 위해서, 테스트가 필요한지를 미리 가볍게 테스트하여 많은 양의 폴리곤들을 무시할 수 있습니다. 이것은 사이드 값(side value)이라고 불리는 것을 계산함으로써 이루어집니다. 사이드 값은 오브젝트의 중앙과 폴리곤이 놓인 면과의 거리를 뜻합니다. 다음 그림에서 보다 잘 표현됩니다.

21번 그림에서 점선의 길이가 바로 사이드 값입니다. 폴리곤에서 멀리 떨어져 있을 수록 사이드 값은 커지게 됩니다.

사이드 값이 계산되면 오브젝트가 폴리곤을 통과하게 되는지를 판단할 수 있습니다. 사이드 값을 구하기 위해서는 면 다항식에 오브젝트의 위치를 넣으면 됩니다. 하지만 면 방정식에서 거리값은 더해지는 대신에 빼야합니다. 이런 식으로 우리는 오브젝트와 평면사이의 거리를 얻게 됩니다. 시작과 끝 위치에서의 사이드 값들을 계산하여 오브젝트가 면을 통과하는지 아닌지 알수 있습니다

여기서 문제가 하나 있습니다. 우리가 오브젝트를 하나의 타원체로 선택했기 때문에 폴리곤의 법선 방향으로 오브젝트의 충돌 반지름(collision radius)을 계산해야 합니다. 이를 위해서 폴리곤의 법석 벡터의 x,z 성분은 오브젝트의 xz 충돌 반지름과 곱해지며 폴리곤의 법선 벡터의 y성분은 오브젝트의 y 충돌 반지름과 곱해집니다. 결과 벡터의 길이가 폴리곤과 오브젝트에 대한 충돌 반지름이 됩니다. 다음 그림과 식이 충돌 반지름에 대해 잘 나타내고 있습니다.

위의 그림에서 점선이 폴리곤을 향하는 오브젝트의 효과적인 충돌 반지름입니다. 이 선은 폴리곤과 수직임을 알수 있습니다.

CollisionRadius(Object, Polygon) =
Sqrt( (Object.xzColl * Polygon.Normal.x)^2 +
(Object.yColl * Polygon.Normal.y)^2 +
(Object.xzColl * Polygon.Normal.z)^2 )

자 이제 우리는 오브젝트가 면을 통과하는지 판단할 수 있습니다. 다음의 알고리즘이 이 테스트를 수행하는 것이며 이와 함께 방향이 주어졌을때 오브젝트의 충돌 반지름을 구하는 도우미 함수입니다.

// 제가 충돌 반지름과 사이드 값을 제대로 이해 못한 것일지 모르겠지만 아래 그림만 봐도 알수 있듯이 이 알고리즘에는 헛점이 있는거 같습니다.

파랑색선은 충돌반지름이며 빨간색은 사이드 값에서 충돌반지름을 빼고 남은 거리를 뜻하는데요. 여기서 아래서 위로 이동한 타원체가 폴리곤과 충돌했음에도 위나 아래나 빨간색 거리 값의 부호가 같기 때문에 충돌이 아닌것 으로 판명됩니다. 타원체가 아니라면 구의 중심과 반지름만을 이용해서 면과 충돌 여부를 판단할 수 있는데 타원체이기 때문에 다르게 처리한것은 알겠는데 먼가 처리가 깔끔하게 이해가 안됩니다. =+=

이해되시는분 설명 부탁~ //

PRE-CHECK-COLLISION은 오브젝트가 폴리곤으로 정의되는 면을 통과하는지 판단합니다. 하지만 폴리곤의 영역을 생각하지는 않습니다. 우리는 이 테스트를 통과한 후에 다른 테스트를 해야 합니다. 말하자면 이 테스트는 오브젝트가 폴리곤의 영역안을 통과하는지 여부입니다. 이 테스트는 매우 비싸기 때문에 위의 테스트로 많은 폴리곤들이 무시 될수록 좋습니다. 일단 우리는 오브젝트의 움직임으로 생성되는 실린더안에 폴리곤이 있는지 체크해야 합니다. 그림 23을 봅시다.

위의 그림에서 오브젝트는 시작 위치에서 끝 위치까지 움직입니다. 두 위치는 두 폴리곤에 대해 모두 다른 면에 있습니다. 하지만 오브젝트의 움직임으로 생긴 실린더(그림에서 회색 영역)는 오직 폴리곤1만을 통과합니다.

이 테스트를 수행하기 위해서는 폴리곤에 수직 면들(perpendicular planes)을 계산할 필요가 있습니다. 이들은 폴리곤이 생성될 때 딱 한번만 계산하여 시간을 아낄 수 있습니다. 수직 면들은 폴리곤의 법선과 수직인 법선을 가지며 안쪽을 향하는 면들 입니다. 삼각형의 경우 각 변에 해당하는 3개의 수직 면이 있습니다. 우리는 이것이 어떻게 보이는지 아래 그림으로 그려봤습니다.

각각의 수직 면들은 변의 방향 벡터와 폴리곤의 법선 벡터를 외적하고 결과 벡터를 정규화하여 계산할 수 있습니다. // 수직 면의 법선 벡터를 구하는 것 // 만약에 결과가 바깥쪽을 향하는 법선이 되면 이를 전도 시킵니다. 수직 면의 거리값은 수직 면의 법선 벡터와 변의 한점을 내적하여 구할 수 있습니다. 예를 들어서 p1과 p2 사이의 면을 구한다면 다음과 같습니다.

1. PerPlane.Normal = Normalize (Direction (p1, p2) x Polygon.Normal)
2. if(Perplane.Normal * p3 < 0) invert(PerPlane.Normal)
3. PerPlane.Distance = PerPlane.Normal*p2

만약에 오브젝트가 단순히 하나의 점이라면 이 점이 각각의 수직면에 대해 양의 방향에 있다는 것만 체크하여 오브젝트가 폴리곤 안에 있는지 알 수 있습니다. 하지만 오브젝트는 충돌 반지름을 가지기 때문에 단순히 변을 따라서 생성된 면을 취할 수 없습니다. 우리는 이들을 바깥쪽으로 옮길 필요가 있습니다. 따라서 각각의 수직 면들은 폴리곤의 중심으로부터 충돌 반지름 만큼 바깥쪽으로 이동되는데 이것은 수직 면 다항식의 거리 값을 충돌 반지름 만큼 빼는 것 계산됩니다. 그래도 여전히 한가지 문제가 남는데 다음 그림에서 알 수 있습니다.

이 수직 면들이 너무 큰 영역을 포괄하고 있음이 분명합니다. p1으로 부터 수직 면1과 3이 만나는 곳 까지의 거리가 매우 깁니다. 각각의 코너들 역시 마찬가지 입니다. 이것을 바로잡기 위해서 오브젝트의 위치는 추가적으로 또 다른 세 개의 면에 대해 체크를 필요로 합니다. 위 그림에 수직 면2를 복사해서 p1에 가져다 놓습니다. 그 다음에 이것을 충돌 반지름 만큼 바깥쪽으로 이동시키고 이 평면의 법선을 안쪽으로 향하게 전도 시킵니다. 이것으로 문제를 바로 잡았습니다. 각각에 점들에 대한 면들에 대해 이것을 수행합니다. 그러면 다음과 같은 그림이 됩니다.

위 그림의 회색영역이 오브젝트가 폴리곤 안쪽에 있는지 판단하는 영역이 됩니다. 비록 각각의 코너들로 부터 약간 멀어져 있기에 이 영역이 정확하지는 않지만 결과는 충분히 좋습니다. 정확한 영역을 사용하는 것은 각각의 코너 영역에 무수히 많은 면들을 필요로 하므로 매우 비싸게 됩니다. 아래 그림은 정확한 영역을 나타냅니다.

자 이제 우리는 폴리곤 안에서 충돌이 일어났는지 여부를 알 수 있습니다. 이 알고리즘은 이 뒤로 이어집니다.

Complexity analysis:
이 함수는 런타임에 매우 자주 사용되는 함수이기 때문에 효율성이 무척 중요합니다. 지금으로선 충분히 효율적이지 않는데 이 함수의 복잡도는 라인1 에서 폴리곤들 정렬하는데 걸려있습니다. 퀵 정렬같은 효과적인 정렬 알고리즘을 사용한다면 복잡도는 O(N logN)이 되며 여기서 N은 입력되는 폴리곤 세트가 가지고 있는 폴리곤 개수입니다. 우리는 O(N)에 가까워질 필요가 있습니다. 이 함수는 나중에 재작성 되야만 할 것입니다.

매 프레임마다 GET-COLLIDING-POLYGON함수는 오브젝트가 통과하는 모든 노드들에서 더 이상 충돌하는 폴리곤이 없을때 까지 호출 됩니다.

이제 우리는 오브젝트가 폴리곤과 충돌하는지 여부를 판단할 수 있습니다. 이제는 오브젝트들 서로의 충돌을 다뤄야 합니다. 이것은 아주 간단한 작업이며 약간의 계산으로 이루어집니다. 일단 두 오브젝트의 중앙 사이의 방향 벡터를 계산하고 정규화 합니다. 그리고 나서 두 오브젝트를 위한 충돌 반지름을 방향 벡터를 통해서 계산합니다. 만약 두 오브젝트의 중심 거리가 두 오브젝트의 충돌 반지름을 더한 값보다 적으면 충돌한 것이고 충돌 핸들링 필요한 것입니다. 아래 알고리즘은 두 오브젝트의 충돌했는지 판단하는 것입니다.

OBJECTS-COLLIDE함수는 움직이는 오브젝트가 통과하는 노드에 있는 오브젝트들에 대해서 한번씩 호출 됩니다.

// 이 알고리즘 역시 위에서 말한 것과 같은 헛점이 있을수 있다고 보이는데. 보다시피 두 타원체의 충돌반지름을 더해도 중심 사이의 거리보다 짧기 때문에 충돌이 안된 것으로 처리하나 실제 그림에서 보이듯 두 타원체는 충돌해 있거든요. //

오브젝트와 폴리곤 혹은 오브젝트와 다른 오브젝트의 충돌이 일어났을때 움직이는 오브젝트의 끝 위치는 조정되야 합니다.

폴리곤과 충돌한 경우 끝 위치를 조정하는 것은 다음과 같은 식을 따릅니다.

EndPosition += Polygon.Normal*(CollRadius-EndSideValue)

이 식의 효과는 벽면을 타고 "미끄러지는(slide)" 것입니다. 만약 충돌이 발생할때 마다 처음 위치로 끝 위치를 고치게 되면 벽에 붙어버리는 것과 상반되는 효과입니다.

두 오브젝트 사이의 충돌한 경우 움직이는 오브젝트의 끝 위치를 조정하는 것은 다음의 식을 따릅니다.

EndPosition += Direction * (CollRadius1 + (CollRadius2-Distance))

위에 식에서 Direction은 움직이는 오브젝트의 끝 위치와 다른 오브젝트의 현재 위치 사이의 방향입니다. 이 방향에서 CollRadius1은 움직이는 오브젝트의 충돌 반지름이며 CollRadius2는 다른 오브젝트의 충돌 반지름입니다. Distance는 움직이는 오브젝트의 끝 위치와 다른 오브젝터의 현재 위치 사이의 거리입니다.

위치가 조정되어 움직여진 오브젝트가 이미 충돌체크를 통과한 이전의 폴리곤이나 오브젝트들과 충돌할지도 모릅니다. 그렇기 때문에 매번 충돌이 일어나게 되면 처음 부터 다시 충돌 체크를 해야 합니다. // 다시말해 충돌로 인해 조정된 좌표값으로 다시 처음부터 충돌체크를 해서 충돌이 없어야 체크를 끝낼 수 있다는 말입니다. // 이것은 복잡한 환경에서 매우 비싼 연산입니다. 따라서 반복 체크 횟수에 제한을 걸어두길 추천합니다. 이 숫자 만큼 반복하고 나서도 여전히 충돌이 일어난다면 오브젝트의 시작 위치로 끝 위치를 조정합니다.

매번 충돌 체크마다 노드에 있는 폴리곤들을 방향 값(facing value)으로 정렬하는 것은 많은 시간을 소비하기 때문에 다른 방법이 더 낫습니다. 모든 폴리곤을 체크하는 루프를 매번 순환할때 마다 움직이는 오브젝트와 충돌하는 폴리곤의 방향 값중 가장 작은 값을 기억하게 합니다. 리프에 있는 모든 폴리곤들과 충돌 체크를 할때 충돌이 감지되면 그 폴리곤에 대하여 충돌 핸들링이 일어날 것입니다. 그리고 나서 처음부터 다시 루프가 재시작 될 것입니다. 이렇게 하면 이 장에서 이전 언급한 방향 값에따라 순서대로 충돌 체크를 하게 되는 것입니다. 따라서 재작성한 우리의 GET-COLLIDING-POLYGON 함수는 다음과 같습니다.

Complexity analysis:
인제 우리는 모든 폴리곤에 대하여 한번만 루프를 돌리므로 이 알고리즘의 복잡도는 O(N)이 되고 여기서 N은 입력되는 폴리곤 세트가 가지고 있는 폴리곤 개수입니다.

우리의 경우 반복을 최대 5번으로 했습니다. 하지만 당연히 이것은 씬이 얼마나 복잡한지에 따라 매우 달라질수 있습니다. 씬이 복잡할수록 더 많은 반복이 필요할 겁니다. 이어지는 페이지는 매 프레임마다 모든 오브젝트들을 위한 충돌 루프입니다.

Complexity analysis:
충돌 루프의 복잡도는 O(i n)이며, 여기서 n은 오브젝트가 통과하는 노드에 있는 폴리곤들의 개수이며 i는 반복 회수의 최대값 입니다. (i값은 다양할 수 있음)

여기에는 적어도 한가지 명확한 최적화가 있습니다. 이는 구현하기도 매우 쉽습니다. 그것은 충돌 반지름 계산을 오브젝트-폴리곤 그리고 오브젝트-오브젝트에 대하여 오직 한번만 하는 것입니다. 그러나 우리는 이런 명확한 근거들과 상관없이 최적화되지 않은 방법으로 설명하기로 선택했습니다. 아마도 이 프로세스를 빠르게 할 수 있는 명확한 것들이 더 있을수 있습니다. 그것들은 당신에게 남겨두겠습니다.

Related reading:
[Nuydens, Tom. 3D Engine Column, Delphi3D]
[Magarshak, Greg. Theory and Practice]
[Lin, Ming C. Fast Collision Detection for Interactive games]
[UNC Collide Research Group, Collision Detection]
[Bikker, Jacco. Building a 3D Portal Engine]

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com

[출처] [번역] BSP-tree 논문 : 6장 |작성자 리안

[BSP] BSP 논문 4, 5장

두더지 — Wed, 30 Jul 2008 04:44:28 GMT

원문 출처: http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf

원문다운로드클릭

BSP Trees and Polygon Removal in Real Time 3D Rendering
-Samuel Ranta-Eskola. 2001.1.19

[Chapter 4]

- Radiosity -

// 레디오시티를 공부해 본적이 없어서 번역하는데 애로사항이 있었습니다. 다른 아티클들 읽어보면서 했는데 솔직히 이 부분은 그냥 원문만 보시는게 나을지도^^ //

- BackGround -

레디오시티(radiosity)의 원래 아이디어는 Goral, Torrance, Battaile & Greenberg 이라는 작가들을 통해서 공식화 되었습니다. 그들은 분산 표면(diffuse surface)들 사이에 에너지가 이동되는 것을 시뮬레이션하는 레디오시티를 제안했습니다. 이 면들은 광택나는 면(shiny surfce)들과 달리, 모든 방향으로 같은 양의 빛을 반사합니다. 따라서 이 시뮬레이션의 결과는 관찰자 위치와는 상관없는 결과를 가져오고 이것은 면의 조도(illumination)가 어떤 각도에서 바라보던 간에 같다는 것을 의미합니다. 이것은 맵을 그리기 이전에 딱 한번만 계산하면 되기 때문에 3D게임에 매우 적합하다고 할 수 있습니다.

우리는 아주 간단하게 레디오시티 알고리즘이 어떻게 작동하는지 살펴보고 BSP-tree가 어떻게 이 계산을 최적화하는지에 초점을 맞추겠습니다. 이 알고리즘에 대해 더 알고 싶다면 이 장에서 제안하는 관련 책들을 읽어보기를 권합니다.

레디오시티 알고리즘은 씬의 조명이 부드럽고 자연스럽기 위해서 설계되었습니다. 우리가 만약에 각각의 빛들이 세계로 광선을 보내고 이것이 전혀 반사되지 않는 직선적인 조명모델을 사용한다면 그림자는 매우 날카로울 것이고 물체들은 매우 부자연스럽게 보일 것입니다. 레디오시티 알고리즘을 사용하기 위해서는 월드를 패치(patch)들로 나누어야 합니다. 패치라는 것은 월드의 작은 한 부분을 말합니다. 각각의 패치들은 초기 에너지 등급을 가지고 있습니다. 이 값은 대체로 광체나 반짝이는 벽들 같은 것과 달리 빛을 발산하지 않는다면 0일 것입니다.

월드를 전체에 에너지를 배포시키는 방법은 여러가지가 있습니다. 우리는 반복적(iterative) 레디오시티라고 불리는 방법을 선택했습니다. 이것은 씬에서 보내지지 않은 에너지들 가운데 가장 높은 에너지 등급을 가지는 패치로 부터 에너지를 보내기 시작하고, 그 후에 이 패치의 에너지를 0으로 합니다. 이 과정을 어떤 특정 값 이상인 에너지를 가지는 패치가 존재하지 않을 때까지 반복합니다.

패치i 로부터 다른 패치j로 에너지를 보낼때 다음과 같은 식이 사용됩니다.

<식- 원문 그림 참고>

위의 식에서 factor는 설명이 더 필요합니다.

<식- 원문 그림 참고>

위에서 보는 바와 같이 씬에서 레디오시티의 계산은 매우 비쌉니다. 씬에서 패치의 개수를 N이라고 했을때 O(N^3)의 복잡도를 가집니다. 이는 씬에서 하나의 패치는 적어도 다른 모든 패치들에게 에너지를 보내야 함으로 씬의 모든 폴리곤들을 전부 체크하기 때문입니다.(또한 씬에서 패치의 개수가 폴리곤의 수보다 많다고 가정하는 것이 안전합니다.) factor의 한 부분인 H(가시성)는 계산하기에 가장 비싼 부분입니다. 바로 이 부분에서 BSP-tree의 힘이 발휘되는 것을 보여줄 수 있습니다.

- Radiosity in BSP-trees -

실제 씬의 조명이 계산되기 전에 면들은 패치들로 분할되야만 합니다. 한가지 아이디어는 처음에 어느 정도의 크기를 갖는 패치들에서 시작하여 이 패치들의 에너지가 계산될 때 만약 패치 안에서 에너지의 변화량이 매우 크다면 작은 패치들로 분할하는 것입니다. 시간이 부족하기 때문에 우리는 이 아이디어는 무시했고 더욱 중요하다고 생각한 BSP-tree를 이용한 최적화를 생각했습니다.

패치들을 생성하는 것은 매우 도전적인 문제라고 여겨지지만 이것은 BSP-tree와 상관없고 BSP-tree를 사용할 필요도 없으므로 이것에 대해서는 더 깊이 들어가지 않을 것입니다.

레디오시티의 원래 아이디어는 각각의 빛 소스(light source)가 반드시 하나 이상의 패치들로 생각 되어져야 한다는 것입니다. 우리는 이것을 하는데 다른 방법을 선택했습니다. 각각의 빛 소스는 BSP-tree의 리프들에 저장됩니다. 그리고 첫번째로 각각의 빛이 그들의 에너지를 모든 패치들로 보냅니다. 이것이 끝나게 되면 레디오시티 계산은 끝나게 되고 씬은 보기 매우 좋게 될 것입니다. 그리고 조금 더 보기 좋게 만들기 위해서 우리는 progressive refinement라는 기법을 약간 수정해서 사용합니다. 매번 refinement를 반복할 때 마다 각각의 리프노드에서 가장 높은 에너지를 가지는 패치를 다른 모든 패치에게 에너지를 반사합니다. 이것은 강하게 빛을 받은 패치들로 부터 어두운 패치들에게 에너지가 퍼져나가는 결과를 가져옵니다. 실제로 완벽하게 어두운 것은 없는데 왜냐하면 모든 것이 빛을 어느 정도는 반사하기 때문입니다.

레디오시티의 계산의 비싼 속성 때문에 우리는 이를 조금 더 최적화해야 할 필요가 있습니다. 에너지를 받아야만 하는 패치들을 선택할 때 BSP-tree 생성시 만들어진 PVS를 사용하여 쓸데없이 많은 계산들을 잘라낼 수 있습니다. 광선 추적(ray tracing)은 PVS를 계산할 때와 마찬가지 방법으로 할 수 있습니다. // factor의 한 부분인 H(가시성)를 계산하기 위해선 두 패치 사이에 광선 추적을해야 합니다. 이것이 PVS를 계산할때 이웃한 노드의 샘플 점들을 이용한 것과 같은 방법이라고 이야기 하는 것 같습니다. //

에너지를 배포하는 우리의 알고리즘은 다음과 같습니다.

Complexity analysis:
이것이 계산 비용에 진짜 킬러입니다. 최악의 경우 모든 광선은 씬에 있는 모든 폴리곤들과 체크되어야 합니다. 이 경우 트리의 있는 패치들의 개수가 N일때 O(N^3)의 복잡도를 가집니다. 다행스럽게도 대부분의 경우 우리가 했던 최적화들이 매운 많은 비용을 없앨겁니다. 하지만 얼만큼의 비용이 절약되는지 말하는 것은 거의 불가능한데 이는 트리의 구조에 따라 크게 다르기 때문입니다.

이것으로 BSP-tree의 이점을 유용하게 쓰는 씬은 매우 빠른 라이팅이 가능합니다. 특히나 광선 추적하는 것을 매우 많이 줄여서 일을 완료할 수 있습니다. 왜냐하면 맵 디자이너가 언제든지 렌더링 결과가 충분히 좋아 보인다면 루프를 멈춤으로써 씬의 랜더링을 끝낼지 결정할 수 있기 때문입니다. 어떻게 렌더링이 진행되고 있는지 대략적으로 볼 수 있게 pre-render를 두세번씩 하는 것이 각각의 변화를 비싸게 한번에 모두 렌더링 하는 것 보다 매우 쉽습니다. 아래 스크린샷은 우리의 레디오시티 알고리즘으로 랜더링한 샘플입니다.

위의 이미지는 우리의 방법으로 렌더링 되었습니다. 왼쪽 이미지는 렌더링 되기 전의 씬이고, 오른쪽은 카메라 앞 즈음에 있는 빛으로 렌더링된 씬입니다.

Related reading:
[Saykol, Ediz and Kirimer, Burak. Progressive Refinement of Radiosity]
[Teller, Seth. Application Challenges to Computational Geometry]
[Firebaugh, M. Three-Dimensional Graphics ? Realistic Rendering]
[Nettle, Paul. Radiosity in English]
[Nuydens, Tom. 3D Engine Column, Delphi3D]

[Chapter 5]

- Summary of BSP-tree rendering -

우리는 BSP엔진중에 미리 계산이 필요한 부분들에 대해 설명해왔습니다. 다음 알고리즘은 렌더링을 위해 씬을 BSP-tree로 만드는 알고리즘입니다.

- Complexity -

RENDER-SCENE함수에서 불리는 함수들의 복잡도는 다음과 같습니다.

<표- 원문 그림 참고>

전형적인 경우(Typical case)는 알고리즘이 일반적으로 걸리는 시간을 측정한 것입니다. 하지만 예전에도 언급했듯이 이것은 씬마다 매우 다릅니다. 복잡도에 가장 많은 영향을 미치는 것은 당연히 RADIOSITY이고 최악의 경우 씬을 렌더링하는데 O(n^3)의 복잡도를 갖게 만듭니다.

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com

[출처] [번역] BSP-tree 논문 : 4장, 5장|작성자 리안

[BSP] BSP 논문 3장

두더지 — Wed, 30 Jul 2008 04:42:50 GMT

자료 출처: http://blog.naver.com/ryanii 리안
원문 출처: http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf

원문다운로드클릭

BSP Trees and Polygon Removal in Real Time 3D Rendering
-Samuel Ranta-Eskola. 2001.1.19

[Chapter 3]

- Hidden Surface Removal -

- Background -

게임 산업에서 보이지 않는 것을 제거해야 할 필요성은 계속 존재해 왔으며 앞으로도 계속해서 매우 크게 존재할 것입니다. 비록 그래픽카드가 엄청난 성능을 가지는 오늘날에도 이것은 여전히 사실입니다. 게임을 만들때 목표는 프레임율 입니다. 최소 사양의 시스템에서 30 frames/second 정도는 나와줘야 합니다. 몇 년 전만 해도 텍스쳐가 입혀진 5000개가 넘는 폴리곤을 프레임당 그려야 한다는 것은 매우 많은 양임을 의미했습니다. 오늘날에는 최적화된 조건에서 수백만 개의 폴리곤을 프레임당 그릴 수 있는 그래픽카드들이 시장에 나와있습니다. 그래도 은면을 제거할 필요성은 존재합니다. 왜일까요? 그것은 은면을 제거해서 남은 자원을 그려질 폴리곤에 쓸수 있기 때문입니다. 이것으로 씬을 보다 상세하게 표현할 수 있으며, 게임 비쥬얼을 보다 매력적으로 만들수 있게 됩니다. 문제는 어느 정도나 떨어진 폴리곤들을 제거해야 하는지 입니다. 은면을 제거하기 위해서는 절두체 선별(view frustum culling)과 포탈 렌더링(portal rendering)과 같은 무거운 계산들을 필요로 합니다. 게임에서 AI나 충돌 체크를 하는데 쓰여지게 될 CPU시간들이 위와 같은 계산들을 하기 위해서도 사용되게 됩니다. 따라서 은면을 제거하는 알고리즘을 개발하는 데에는 많은 노력을 필요로 합니다. 가려진 각각의 폴리곤들을 제거하는 게임은 거의 없습니다. 대부분의 게임들은 하나의 가려진 폴리곤의 집합(노드나 객체같은)을 제거하는 것으로 만족합니다. 이것은 폴리곤 하나 하나를 따지지 않으므로 가려진 부분을 제거할 때 약간 더 그려지는 한계를 가진 계산이나 이를 감수하는 것이 맞다는 것을 의미합니다.

FPS 게임을 만들때 은면 제거를 위해서 쓰이는 가장 일반적인 기술은 포탈 렌더링 입니다. 이 기법이 BSP-tree를 필요로 하지 않지만 BSP-tree의 이점을 사용하기에 아주 적합합니다. 우리는 이것을 사용하기로 생각했지만 보다 정적으로 구상하는 것이 BSP-tree 렌더링을 더욱 빠르게 한다고 생각했습니다. 포탈 렌더링은 거울이나 감시 카메라와 같이 좋은 부수적인 효과를 가지지만 우리의 기법들과 함께 사용될 수는 없습니다. 반면에 우리 기법들은 런타임에서 아주 적은 계산만을 필요로 합니다. // 다시말해 포탈 랜더링 기법을 사용하지만 동적으로 구성하지 않기 때문에 포탈 렌더링이 가지는 여러 다른 이점들을 모두 활용할 수는 없다는 이야기 같습니다. //

- Portal Rendering -

월드는 포탈(portal)들을 통해서 연결 되어진 섹터(sector)들로 표현될 수 있습니다. 섹터는 볼록(convex)하며 닫힌(closed) 폴리곤들의 집합입니다. 닫혀있다는 의미는 섹터 안에서 밖으로 선을 그을때 폴리곤을 만나지 않고는 불가능하다는 말입니다. 이것은 각각의 노드들의 빈틈은 포탈 폴리곤으로 채워져야 함을 의미합니다. 포탈 폴리곤들을 위치시키는 것은 수동이나 자동으로 할 수 있습니다. 이미 언급했듯이 하드웨어 가속 Z 버퍼로 인해서 섹터들이 볼록섹터(convex sector)일 필요성은 사라졌으므로 많은 게임 엔진에서 이 원칙은 생략하고 있습니다. 하지만 우리는 과거의 방식이 어떤 식이였는지 설명할 것입니다.

포탈 렌더링의 기본적인 아이디어는 뷰어의 위치에서 절두체를 가지고 씬을 렌더링 할때 절두체가 포탈 폴리곤과 만나게 되면 포탈 폴리곤으로 절두체를 클립(clip)하는 것입니다. 그리고 나서 이웃한 섹터를 렌더링 할때 같은 뷰어의 위치를 기준으로 하지만 절두체는 이전에 클리핑되어 만들어진 새 절두체를 사용하게 됩니다. 이것은 매우 간단하고 재귀 함수에 적합한 접근입니다. 절두체가 정확히 뷰어가 볼 수 있는 공간으로 제한되기 때문에 많은 오브젝트들이 쉽게 선별될 수 있습니다. 아래 그림이 포탈 엔진에서 어떻게 절두체가 클립되는지 보여줍니다.

위의 그림에서 뷰어의 위치는 V이고 최초의 절두체는 F1 입니다. F1이 포탈 폴리곤이 P1과 만나게 되면 클립되어 F2가 됩니다. 그후 F2가 P2,P3 포탈들을 만나서 클립되고 F3과 F4가 됩니다. 포탈 P4와 만나게 되면 F3은 깍여져서 F5가 되고 F4는 깍여져서 F6이 됩니다. 이 프로세스는 재귀함수에 적합합니다.

포탈 렌더링 엔진에서 오브젝트를 선별하기 위해서, 사실 어떤 3D 엔진이라도, 이 프로세스를 보다 빠르게 처리하기 위한 단계들이 있습니다. 첫번째는 오브젝트의 경계구(bounding sphere)를 계산하는 것으로, 경계구라는 것은 오브젝트를 모두 포함하는 가장 작은 구를 뜻합니다. 최선으로 오브젝트 생성시 딱 한번만 경계구를 생성하게 하는 것입니다. 그리고 나서 절두체의 각 면들에 대해서 경계구를 테스트합니다. 경계구가 모든 면들에 대해서 음의 방향에 존재한다면 오브젝트는 보일수 없는 것이고 따라서 그려지지 않습니다. 아래 상황은 선별되어서 그려지지 않는 오브젝트와 이와 달리 그려지는 오브젝트를 보여주고 있습니다.

그림에서 오브젝트1은 절두체의 오른쪽 면을 기준으로 했을 때 양의 방향에 있지만 왼쪽 면을 기준으로 하면 음의 방향에 있으므로 선별됩니다. 반면에 오브젝트2는 왼쪽 면을 기준으로 완전히 양의 방향이고 오른쪽 면을 기준으로 하면 일부분 양의 방향이므로 선별되지 않습니다.

포탈 엔진의 원래 아이디어는 폴리곤들을 클리핑하여 중복해서 그리지 않음으로써 보일 수 있는 지역만 그려지게 하는 것입니다. 오늘날에는 이런 방식은 굉장히 많은 CPU타임을 소모합니다. 하여튼 폴리곤이 씬을 그리는 재귀 함수 안에서 여러 번 나오게 되므로 우리는 이 폴리곤이 그려졌는지의 여부를 알 필요가 있습니다. 이것을 구현하는 좋은 방법은 폴리곤이 그려진 마지막 프레임을 가리키는 프레임 카운터를 폴리곤에 붙이는 것입니다. 그림10의 오른쪽 벽의 경우를 보면 절두체F5 와 F6안에서 그려져야 하고 이 폴리곤들은 이 프레임에서 그려졌는지 아닌지를 여부를 가져야 합니다. 그렇지 않다면 Z버퍼링에 오류가 발생합니다. // 과거 하드웨어 가속 Z버퍼링이 없었을때 포탈 렌더링을 이용하여 폴리곤을 선별시 Z버퍼링을 위하여 프레임 카운터 같은 것이 폴리곤마다 저장되어야 했다는 이야기 입니다. 물론 오늘날에는 전혀 쓸모없는 방식이지요. //

포탈 엔진에서 렌더링을 수행하기 위해 우리는 절두체가 무엇으로 구성되는지 정의할 필요가 있습니다. 절두체는 n개의 면을 가지는 구조이고 각각의 면들의 법선 방향은 절두체 안쪽을 향하며 따라서 절두체 안은 닫혀진 공간이 됩니다. 아래 알고리즘은 한 폴리곤이 절두체 안에 있는지 없는지를 판단하는 것입니다. 여기서 우리는 하나의 면과 하나의 점을 취하는 CALSSIFY_POINT 함수를 사용합니다.

포탈엔진의 렌더링 메인 함수는 다음과 같습니다.

- Placing the portals -

전에도 언급했듯이 포탈 엔진의 큰 문제들 중 하나는 포탈들을 위치 시키는 것입니다. 수동으로 포탈들을 위치시킨다면 맵 디자이너의 능력이 요구되어야함은 말할 것도 없이 시간이 매우 많이 걸리게 됩니다. 다른 여러가지 요소와 더불어 이 시간 역시 다른 곳에서 더 좋게 쓰여질 수 있습니다. 따라서 자동으로 포탈을 위치시키는 좋은 알고리즘이 필요합니다. 제 동료인 Andreas Brinck는 이 문제에 대해 좋은 답을 내놨습니다. 그의 답을 이용하려면 BSP-tree가 이용되야 합니다.

기본 아이디어는 포탈이 반드시 트리를 나누는데 기준이 되었던 폴리곤들로 정의되는 면상에 있는 것입니다. 최초로 생성되는 포탈 폴리곤은 트리에 존재하는 전체 노드들을 포함하고 있는 바운딩 박스를 넘어서는 사각형 폴리곤(four-sided polygon)으로 초기화합니다. 그 다음에 각각의 포탈 폴리곤은 해당 노드의 서브 트리들로 타고 내려갑니다. 포탈 폴리곤이 서브 트리들중 하나의 노드를 통과하게 될때 그 노드에 있는 분할 기준 폴리곤으로 정의 되는 면이 있다면 이것으로 포탈 폴리곤을 클립합니다. 또한 포탈 폴리곤이 리프 노드에 도달하면 리프 노드에 있는 모든 폴리곤들로 클립 됩니다. 포탈 폴리곤이 클립되었다면 그 결과인 두 부분은 트리의 꼭대기로부터 다시 내려오게 됩니다. 만약 포탈 폴리곤이 클리핑 될 필요가 없다면 이 포탈 폴리곤은 현재 방문하고 있는 노드의 서브 트리들로 내려갑니다. 이것이 뜻하는 것은 클립된 부분이 기준 면의 양의 방향이라면 오른쪽 서브 트리로 내려가게 되고 음의 방향이라면 왼쪽 서브 트리로 내려가게 됩니다. 그러나 만약 기준 면과 동일면상에 있다면 양쪽 서브 트리로 모두 내려갑니다.

트리에 모든 포탈들을 위치시키는 알고리즘을 정의하기 위해서 우리는 폴리곤을 어떻게 클립할 것인지 정의해야 합니다. 따라서 우리는 선과 면이 만나서 생기는 점을 리턴하는 INTERSECTION_POINT 함수가 있음을 가정합니다.

인제 우리는 BSP-tree안에 어떻게 포탈들을 분포시킬지 정의할 수 있습니다. 알고리즘은 트리의 루트 노드의 바운딩박스 보다 큰 포탈 폴리곤으로 시작합니다. 우리는 이 함수의 설계를 스웨덴의 DICE에서 일하는 게임 프로그래머 Andreas Brinck로 부터 얻었습니다.

// 아래 예제설명 내용을 보면 리프가 아닌 노드의 분할 기준면을 포탈 폴리곤으로 만든 후, 의사코드에서는 왼쪽 서브트리를 먼저 타게 되는데 오른쪽을 먼저 타야 할거 같습니다. //

Complexity analysis:

이 함수는 분석하기가 매우 복잡하고 또한 설계 역시 우리 것이 아니기 때문에 분석하지 않겠습니다.

의사코드 10번째 줄을 명확히 하려면 노드에 있는 포탈 폴리곤과 다른 폴리곤들 사이의 동일한 면 부분을 제거하는 것을 보여줄 필요가 있습니다. 다음 이미지를 보겠습니다.

그림12에서 포탈 폴리곤은 리프노드에 왔습니다. 진한 회색으로 칠해진 1의 영역은 트리를 내려오는 동안 제거된 부분입니다. 밝은 회색의 2,3,4, 부분은 리프 노드의 폴리곤들과 동일한 면 상에 있기 때문에 제거됩니다. 따라서 5로 표시된 부분만이 포탈로 사용될 부분입니다. // 이 그림에서 방에 문(5번영역)이 하나 있다고 생각하시면 됩니다. 그럼 문으로 뚫린 부분만 포탈 폴리곤이 생성되어야 하겠지요. //

앞 페이지의 알고리즘은 첫 눈에 보기엔 매우 복잡해 보이지만 사실 매우 단순하고 직관적이라고 할 수 있습니다. 끝으로 모든 포탈 폴리곤들은 각각 정확히 두 노드에 존재하게 됩니다. 서로를 볼 수 있는 포탈이 두개 존재 하는 것입니다. 다음 페이지에서 구현된 알고리즘의 예를 들겠습니다.

1. 포탈 폴리곤 1 (s1) 이 노드 n1에 들어갑니다. <원문 그림 참고>
n1에서 포탈 폴리곤은 클리핑되어 맞게 조정되고 중간 부분은 n1 노드에 있는 폴리곤 하나와 동일한 면에 있으므로 제거되게 됩니다. 여기서 p1, p2 이름 지어진 두 포탈 폴리곤을 얻게 됩니다. 이 둘이 s1을 대신합니다.

2. p1 과 p2 가 노드 s2에 들어갑니다.
노드 s2에서 p1은 s2의 양의 방향에 있기 때문에 기준이 되는 폴리곤 s2 와 함께 n2 노드로 들어가게 됩니다. p2는 s2의 음의 방향에 있기 때문에 s2와 함께 s3 노드로 내려가게 됩니다. s2를 가로지르지 않기 때문에 p1,p2를 클리핑할 필요가 없습니다.

3. p1 과 s2가 노드 n2에 들어갑니다. <원문 그림 참고>

n2에서 p1 은 포탈로 받아들여집니다. 따라서 노드 n1에서도 바뀌지 않습니다. p3의 한 부분은 이 노드의 한폴리곤과 동일한 면에 있으므로 제거됩니다. 폴리곤 s2는 s3로 보내지며 이제 p3로 불립니다.

4. p2 와 p3가 노드 s3에 들어갑니다.

// 원문은 p3와 s3가 노드 n3로 들어갑니다 인데 오타 같아서 수정 //
노드s3에서 p2와 p3 둘다 클립되지 않으므로 s3와 함께 내려가게 됩니다. p3와 s3는 노드 n3으로 내려가게 되고 p2와 s3은 s4로 내려가게 됩니다.

5. p3 와 s3가 노드 n3에 들어갑니다. <원문 그림 참고> // 그림 : n2 -> n3 수정필요 //
노드 n3에서 p3는 포탈로 받아들여지고 s3는 이전의 나왔던 이유들과 같은 이유로 일부분을 제거합니다. s3은 이제 p4로 불립니다.

6. p2와 p4가 노드 s4로 들어갑니다.
어떤 클리핑도 필요하지 않습니다. p2와 p4는 s4와 함께 n4로 내려가게 됩니다. 오직 s4 만이 n5로 내려갑니다.

7. p2,p4,s4가 노드 n4로 들어갑니다. <원문 그림 참고>
p2와 p4 노드에 맞추기 위한 것 말고는 클리핑이 필요하지 않습니다. 그러나 s4는 완전이 한 폴리곤과 동일한 면이므로 제거됩니다.

8. n5 노드로 가는 것은 없습니다.
이 노드는 포탈을 가지지 않으므로 어떤 노드들로 부터도 보여질수 없으며 다른 어떤 노드도 볼 수 없습니다.

9. 결과 <원문 그림 참고>
포탈 p1은 n1와 n2에 있습니다.
포탈 p2은 n1와 n4에 있습니다.
포탈 p3은 n2와 n3에 있습니다.
포탈 p4은 n3와 n4에 있습니다.

이것이 상대적으로 좋은 프레임율을 제공하는 단순한 포탈 엔진을 구현하기 위한 전부입니다.

// 이 알고리즘이 직관적이라고 했지만 이해가 쉽지 않았습니다 . 예제 맵으로 차근차근 알고리즘을 따라가면서 생각해보시는게 설명만 보시는 것보다 좋을거 같습니다. //

- Our Solution -

포탈 엔진은 몇 가지 좋은 특징을 가지고 있는 매우 탄력적인 구조입니다. 우리가 시스템을 설계하기 시작했을때 우리는 포탈 엔진으로 돌아가게 하려고 생각했지만 몇 가지 문제점들이 있었습니다. 바로 클리핑이 씬을 그리는 중에 일어 난다는 것이였습니다. 그래서 우리는 더 정적인 방법을 통해서 런타임에서 일어나는 비싼 계산을 피하기로 결정했습니다. 아이디어는 대부분 포탈 엔진과 비슷하지만 런타임시 그려질 필요가 있는 것들의 정보가 맵이 그려지기 전에 미리 계산된다는 점이 다릅니다. BSP-tree의 각각의 리프들은 Potentially Visible Set(PVS)를 생성하게 됩니다. PVS란 현재 리프에서 보여질 수 있는 리프들의 집합입니다. 이것은 렌더링 부분에서만 쓰이는 것이 아닙니다. 레디오시티를 계산할때나 네트워킹의 최적화에서도 쓰이게 됩니다.

PVS는 맵이 그려지기 전에 미리 계산됩니다. 각각 리프에 보여질 가능성이 있는 리프들이 저장됩니다. 씬이 그려져야 할 때 카메라가 위치한 첫번째 리프가 그려지며 다음으로 그 리프의 PVS에 있는 리프들이 그려지게 됩니다. 이것은 당신이 중복된 그리기를 다룰 수 있는 어떤 종류의 알고리즘이 있음을 필요로 합니다. 전에 언급했듯이 오늘날의 그래픽카드는 하드웨어 가속 Z 버퍼를 지원하며 이것으로 충분합니다.

- Calculating the PVS -

PVS를 계산하기 위해서는 리프 안에 어떤 점들이 다른 리프에서 보이는지를 알기 위하여 리프들 사이의 표준 광선 추적(standard ray tracing)이 필요합니다. 각각의 리프들은 약간의 샘플 점들을 가져야 하며 이것들 사이의 가시성이 추적되야만 합니다. 만약에 한 리프의 중앙에 놓여진 점이 다른 리프로 부터 온 시선에 보인다고 생각되려면, 그 시선은 반드시 리프의 입구를 통과해 와야 합니다. 다음 그림으로 이 점을 명확히 알 수 있습니다.

위 그림을 통해서 우리는 한점이 다른 노드에서 부터 보이려면 반드시 해당 노드의 입구를 통과해야 함을 명확히 알 수 있습니다. 이것은 매우 자명한데 왜냐하면 만약에 광선이 다른 어떤 곳을 통과하려 할때 막혀버리면 두 점사이의 가시성은 없기 때문입니다. 따라서 리프의 입구에 샘플 점들을 배치하는 것으로 충분합니다. 아래 설명하는 알고리즘은 BSP-tree에서 어떻게 샘플 점들을 배치하는지 나타냅니다. 이 함수를 위해서 우리는 노드에 점을 배치하기 위한 몇 가지 도우미 함수들이 필요합니다.

* DISTRIBUTE-POINTS (Node)
- 이 함수는 인자로 들어온 노드의 분할 면을 따라서 해당 노드의 바운딩 박스 범위 안에서 일정한 간격으로 점들을 배치합니다. 이 점들의 집합을 리턴합니다. Complexity: O(xy), x 는 바운딩 박스 안에서 분할면의 너비이며 y는 높이 입니다.

* CLEANUP-POINTS (Node, PointSet)
- 점들의 집합에서 이 노드의 폴리곤과 같은 면에 있거나 바운딩 박스의 바깥쪽에 있는 점들을 제거합니다. Complexity: O(np), n은 노드안에 폴리곤의 개수이며 p는 점집합이 가지는 점들의 개수입니다.

// 위에서 어렵게 설명한 포탈 생성 알고리즘과 달리 기준 폴리곤으로 생성되는 면에 점들을 적당히 분포시키는 것은 이해가 쉽습니다. 이것도 포탈 이라는 개념으로 부를 수 있을지 잘 모르겠네요. //

Complexity analysis:
이 함수는 재귀적으로 매번 호출마다 O(np + xy) 정도의 복잡도를 가집니다. ( DISTRIBUTE-POINTS, CLEANUP-POINTS 찹고) 완전한 복잡도를 구하기 위해 다음과 같은 식을 세울 수 있습니다. (우리는 점 집합이 양쪽 트리에 똑같이 분포됨을 가정합니다.)

T(n) = 2T(n/2) + O(np + xy)

Masters Theorem을 사용하면 θ(np + xy) 같은 복잡도를 얻게 됩니다.

이 함수는 트리의 루트 노드와 비어있는 점 집합을 인자로 처음 호출 됩니다. 말하자면 다음과 같은 흐름입니다. 먼저 BSP-tree의 루트노드에 있는 나누기 기준 폴리곤으로 정의 되는 면 상에 점을 배치 합니다. 면은 무한하기 때문에 이것이 무한 개수의 점을 생성하게 됩니다. 그래서 점을 배치하는데 있어 제한이 있어야 합니다. 이 제한이 바로 루트 노드의 바운딩 박스입니다.

그후 점들의 배치가 다 끝나면 양쪽 서브 트리로 내려가게 됩니다. 샘플 점들이 노드에 들어갈때 이들은 두 집합으로 나뉘어집니다. 한 집합은 노드의 분할 기준 면의 양의 방향에 있는 집합이고 나머지는 음의 방향에 있는 집합입니다. 면 상에 위치한 점들은 양쪽 집합에 모두 포함됩니다. 그리고 나서 이 노드의 바운딩 박스를 제한으로 분할 기준 면을 따라서 점들이 생성됩니다. 새롭게 생성된 점들은 양쪽 집합에 모두 포함됩니다. 이제 양의 방향의 점 집합은 오른쪽 서브 트리로 내려가고 음의 방향의 점 집합은 왼쪽 서브 트리로 내려갑니다. 이 프로세스가 점 집합이 리프에 도달할때 까지 반복됩니다. 이런 처리 이후에 리프 노드는 노드의 입구에 배치된 샘플 점들의 집합을 가지게 됩니다.

만약 지금 단계에서 광선 추적을 시행한다면 아마 매우 많은 시간이 걸릴 것입니다. 하지만 만약 서로 연결된 리프들에 대해 알수 있다면 매우 쉬워질 것입니다. 왜냐하면 이것으로 어떤 리프들 사이의 추적은 생략시킬 수 있기 때문입니다. 서로 연결된 리프들을 찾는 것은 매우 쉽습니다. 단순히 서로의 샘플 점 집합을 비교하기만 하면 됩니다. 만약에 두 노드가 한개의 샘플 점이라도 공유한다면 서로 연결되었다고 할수 있는데, 왜냐하면 샘플 점 집합을 배치하는 와중에 점들은 2개의 리프에 속하거나 아니면 아예 속하지 않게 되기 때문입니다. 이제 우리는 서로 연결된 리프들을 알았으니 가시성 추적 알고리즘을 정의 할 수 있습니다. 하지만 일단 도우미 함수들을 정의할 필요가 있습니다.

가시성을 추적하기 위해선 기본적으로 광선 추적을 해야할 필요가 있습니다. BSP-tree는 광선을 추적하기에 매우 좋은 구조입니다. 왜냐하면 아주 적은 비용으로 월드의 큰 부분을 무시할수 있기 때문입니다. 다음 함수의 집합이 우리의 해결책을 위해 필요한 것입니다.

* POLYGON-IS-HIT (Polygon, Ray)
- 광선이 폴리곤과 겹치는지 여부를 리턴합니다.

* RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray)
- 광선이 해당 노드와 그 서브 트리 안의 어떤 것과 겹치는지 여부를 리턴합니다.

* INTERSECTS-SPHERE (Sphere, Ray)
- 광선이 구와 겹치는지 여부를 리턴합니다.

* CREATE-RAY (Point1, Point2)
- 두 점 사이의 광선을 리턴합니다.

RAY-INTERSECTS-SOMETHING-IN-TREE 함수는 위의 함수들 중 가장 재밌는 함수입니다. 왜냐하면 이것은 BSP-tree의 장점들을 보여주기 때문입니다. 이것은 보통의 광선 추적이 어떻게 BSP-tree를 이용하여 최적화 되는지를 보여줍니다. 이 함수는 처음에 트리의 루트 노드를 인자로 하는 재귀 함수입니다. 알고리즘은 다음과 같습니다.

// 이 의사코드는 다음과 같이 수정되야 합니다. //

RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray)
{

if(IS-LEAF(Node))

    {
        for each polygon P in Node
          if(POLYGON-IS-HIT (P, Ray))
              return true;

}

else

{

startSide = CLASSIFY-POINT(Ray.StartPoint, Node.Divider)
endSide = CLASSIFY-POINT(Ray.EndPoint, Node.Divider)

// If the ray spans the splitting plane of this node or if the ray is
// coinciding with the plane, send it down to both children

        if ((startSide = COINCIDING and endSide = COINCIDING) or
            startSide <> endSide and startSide <> COINCIDING and endSide <> COINCIDING)
        {
            if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
                return true

            if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
                return true
        }

        // If the ray is only on the positive side of the splitting plane
        // send the ray down the right child. The or in the if statement is
        // because one of the points might be coinciding with the plane.

        if (startSide = INFRONT or endSide = INFRONT)
            if(RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
                return true

        // If the ray is only on the negative side of the splitting plane
        // send the ray down the right child. The or in the if statement is
        // because one of the points might be coinciding with the plane.

        if (startSide = BEHIND or endSide = BEHIND)
            if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
                return true

}

// There was no intersection anywhere, pass that upwards
return false

}

Complexity analysis:
최악의 경우에 광선이 모든 노드를 방문하게 되고 이는 모든 폴리곤들과 비교됨을 의미합니다. 이것은 O(N)을 말하며 N은 트리에 있는 폴리곤의 개수입니다. 하지만 전형적으로 광선이 모든 노드들을 통과하지는 않으므로 비교되야 하는 폴리곤의 수는 줄어들 수 있습니다. 최선의 경우에 오직 하나의 노드만을 방문하게 되면 O(logN)이 되며 이것은 트리 구조에 영향을 받습니다.

Complexity analysis:
CHECK-VISIBILITY함수는 매우 비싸다고 할수 있습니다. 만약에 리프노드들 사이의 가시성이 없다면 node1의 모든 샘플 점들과 node2의 모든 샘플 점들을 체크해야만 합니다. 최악의 경우에 트리의 모든 폴리곤을 체크해야 하며 따라서 O(s1 s2 p)이라 하겠습니다. s1은 node1의 샘플 점들의 개수이고 s2는 node2의 샘플 점들의 개수이고 p는 트리의 모든 폴리곤의 개수 입니다. 일반적으로 이보다 낫게 O(s1 s2 Log p) 라고 할 수 있는데 이는 트리를 통과하는 광선에 체크가 필요한 폴리곤의 개수가 줄어들기 때문입니다.

만약에 우리가 서로 연결된 리프 노드들을 통해서 이 알고리즘을 최적화하지 않았다면 모든 리프가 서로 서로 체크해야 하므로 O(N^2)이 됩니다. 여기서 N은 트리에 있는 리프 노드의 개수 입니다. 연결된 리프 노드들을 이용하는 전략으로 얼만큼의 속도향상이 있었는지 알기는 매우 어렵습니다. 왜냐하면 맵이 어떤 식으로 생성됬는지에 따라 달라지기 때문입니다. 만약에 모든 리프들이 서로를 볼수 있다면 어떤 최적화도 없습니다. 반면에 하나의 리프가 한 두개 정도의 리프들만 볼 수 있을 경우 많은 최적화가 일어나며 거의 O(N)정도로 낮아집니다.

이렇게 생성된 구조는 매 프레임마다 좋은 맵에서 많은 양의 폴리곤들을 무시할 수있습니다. 좋은 맵이라는 것은 가시성을 생각해서 만들어진 것으로 벽과 같이 시선을 막아주는 오브젝트들이 들어있음을 의미합니다. 만약에 맵이 많은 상세한 오브젝트들을 가진 커다란 하나의 방이라면 우리의 엔진으로는 어떤 폴리곤들도 제거되지 않습니다. 이런 나쁜 경우에서도 폴리곤들을 제거하기 위한 다른 기술이 있습니다. 이 기술은 level of detail (LOD) 이라고 불립니다. (Glossary 참고)

- Static Objects -

하나의 박스 가운데에 구가 놓여진 맵을 생각해 봅시다. 우리가 이 맵으로 BSP-tree를 생성하려 할때 우리는 엄청난 양의 노드를 필요로 하게 되고 많은 폴리곤 분할이 일어나게 됩니다. 왜냐하면 각각의 리프 노드를 구성하는 폴리곤들은 구를 구성하는 각각의 폴리곤들일 것이기 때문입니다. 그래서 만약에 구가 200개 정도의 폴리곤으로 구성되게 되면 이렇게 간단한 씬이라도 200개 정도의 리프를 가지는 BSP-tree로 구성되게 됩니다. 이런 깊이를 (앞의 경우에 깊이는 약 200이 될 것이다.) 가지게 되면 분할과정에서 많은 폴리곤들이 새로 생성되는 것은 말할 것도 없이 런타임에서도 매우 방해의 요소가 됩니다. 따라서 이런 경우를 다룰 수 있는 무엇인가가 필요합니다.

이 문제를 풀기 위해서 맵 디자이너는 맵의 기하학적 요소를 정의하는 오브젝트를 선택합니다. 위의 예제에서는 박스가 이런 오브젝트가 될 수 있습니다. 그리고 나머지 // 구와 같은 // 오브젝트들은 정적 오브젝트(static object) 로 분류합니다. 이런 정적 오브젝트들은 BSP-tree 생성이나 가시성 테스트시 사용되지 않습니다. 그러나 이들 오브젝트는 맵에 조명을 적용할 단계인 경우 그림자를 생성하게 됩니다. 이 정적 오브젝트들은 가시성 테스트가 끝난 BSP-tree에 추가됩니다. 이것은 정적 오브젝트를 이루는 각각의 폴리곤을 트리로 내려보냄으로써 행해집니다. 트리를 타고 내려가는 폴리곤들을 추가하는 방식은 밑의 알고리즘을 통해 설명할 수 있습니다. 다음과 같습니다.

// 위 의사코드는 다음과 같은 수정이 필요합니다. //

if (Value = INFRONT or Value = SPANNING)

-> 수정한다.

if (Value = INFRONT or Value = COINCIDING)

PUSH-POLYGON함수는 트리에 폴리곤을 추가하는 깔끔한 재귀 함수입니다. 이 함수는 정적 오브젝트를 트리에 추가하기 위해서 모든 정적 오브젝트의 모든 폴리곤에 대해서 트리의 루트 노드와 함께 한번씩만 불리게 됩니다.

이 프로세스를 하고 나면 리프들은 더 이상 볼록집합(convex set)이 아닙니다. 이런 이유로 충돌 체크시 몇 가지 문제점이 있을 수 있습니다. 이것은 Physics in BSP-tree 장에서 다루도록 하겠습니다.

Related reading:
[Hoff III, Kenneth E. Faster 3D Game Graphics by Not Drawing What Is Not Seen]
[Tyberghein, Jorrit. The Portal Technique for Real-time 3D Engines]
[Bikker, Jacco. Building a 3D Portal Engine]
[Nuydens, Tom. 3D Engine Column, Delphi3D]
[Chalfin, Alex. Cells and Portals]
[Hoff, Kenny. The Warnock Area Subdivision Algorithm for Hidden Surface Removal]

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com
[출처] [번역] BSP-tree 논문 : 3장|작성자 리안

[BSP] BSP 논문 1,2장

두더지 — Wed, 30 Jul 2008 04:40:31 GMT

자료 출처: http://blog.naver.com/ryanii 리안
원문 출처: http://www.gamedev.net/reference/programming/features/bsptree/bsp.pdf

원문다운로드클릭

BSP Trees and Polygon Removal in Real Time 3D Rendering
-Samuel Ranta-Eskola. 2001.1.19

[Abstract]

BSP-tree는 원래 월드에 있는 폴리곤들을 정렬하기 위해 설계된 알고리즘입니다. 왜냐하면 당시 하드웨어 가속 Z 버퍼가 존재하지 않았고 소프트웨어 Z 버퍼링은 매우 느렸기 때문입니다. 오늘날에 이 용도로는 필요하지 않은데 왜냐하면 하드웨어 가속 z 버퍼가 존재하기 때문입니다. 그 대신에 매우 넓고 다양한 부분의 최적화에 사용되는데 예를 들자면 레디오시티 계산, 월드 드로잉, 충돌 체크, 네트워킹 부분등을 말할 수 있습니다.

우리는 BSP-tree를 사용함으로써 많은 이점을 가질 수 있는 부분들에 대해 설명할 것이며 이것의 구현 프로세스도 알아 볼 것입니다.

결론적으로 말해 BSP-tree는 대부분의 게임엔진에 있어서 매우 유용합니다. BSP-tree가 정적이며 런타임에 수정하는 것이 매우 많은 비용을 필요로 하는 등의 단점들을 포함하고 있음에도 말입니다. 아마도 BSP-tree 알고리즘으로 부터 얻을 수 있는 몇 가지 아이디어들을 통해서 BSP-tree와 같은 이점을 가지는 보다 동적인 구조들을 개발 할 수도 있을 것입니다.

[Table of Contents]

1. Introduction
- Background
- Problem Statement

2. BSP-Trees
- Background
- The BSP algorithm

3. Hidden Surface Removal
- Background
- Portal Rendering
- Placing the Portals
- Our Solution
- Calculating the PVS
- Static Objects

4. Radiosity
- Background
- Radiosity in BSP-trees

5. Summary of BSP-Tree Rendering

6. Physics In BSP-Trees
- Future Position Calculation
- Collision Detection and Collision Handling

7. Network Optimization Using BSP-Trees

8. Future Work

9. Conclusions

10. Appendix

[Glossary]

FPS
- First person shooter, 적들을 없애는 것이 목적인 일인칭 시점의 게임.

MAP : 맵
- 월드의 다각형들을 가지는 객체.

Z-Value : Z 값
- 뷰어의 위치에서 부터 거리에 따라 분류하기 위해 쓰어지는 측정치.

Frame rate : 프레임율
- 매초마다 화면이 갱신되는 횟수. 모니터의 갱신율과는 아무 상관이 없음. 매 초 마다 월드가 그려지는 횟수. 보통 초당 30번의 갱신 이상이 되어야 연속적이라고 느낄 수 있음.

Pre-processing : 선수행, 미리 계산된
- 런타임 전에 계산이 미리 되어있는것. 따라서 런타임시 CPU타임을 다른 것들을 위해서 사용할 수 있음.

Polygon : 다각형
- 많은 수의 정점과 변들로 이루어진 도형. 삼각형,사각형,육가형,오각형등. 어떤 식이든 연결되어진 선으로 닫혀진 것은 다각형이라 할수 있음. 단 모든 정점들이 같은 면에 존재해야 함.

Plane equation : 면 다항식
- 3차원상의 면을 표현하는 다항식. Ax + By + Cz + D. A~D는 상수계수. A~C는 면의 법선벡터 값이고 D는 원점에서 부터 법선벡터 방향으로 면에 이르는 거리.

Node : 노드
- 트리의 부분. 각각의 노드는 왼쪽과 오른쪽의 sub-tree로 구성됨.

PVS
- Potentially Visible Set. 위치가 주어져 있을때 해당 지역으로 부터 보여질 가능성이 있는 objects/polygons/nodes의 집합.

Portal : 포탈
- 연결된 두 노드를 분할하는 공간, 또는 그려질 장면에 대한 거울(?).

Radiosity : 레디오시티
- 게임엔진에서 일반적으로 사용되는 조명모델. 주요 특징은 color-bledding으로 이웃한 벽으로 색깔을 번지게 하는 것.

Avatar : 아바타
- 가상세계의 플레이어를 대신하는 객체.

Client : 클라이언트, 사용자
- 다수의 유저들이 플레이하는 어플리케이션에서 서버에 연결된 유저.

Viewing frustum : 절두체
- 카메라를 위한 뷰 필드. 흔히 카메라를 꼭지점으로하는 피라미드로 여겨짐.

Target system : 최소 사양 시스템
- 게임이 실행될 수 있어야 하는 최소한의 시스템.

Scene : 씬
- 보는 위치와 각도에 따러 그려질 수 있는 이미지에 존재하는 객체들의 집합

LOD
- Level of Detail. 관찰자로 부터의 거리에 따라 상세함을 달리해서 그리는 기법. 씬에서 폴리곤의 개수를 줄이기 위해 사용. 관찰자에 가까울수록 보다 상세히 그려짐.

Bounding box : 경계 박스
- 어떤 객체(점, 다각형, 바운딩박스)의 집합을 모두 포함할 수 있는 최소의 박스. BSP-node의 바운딩 박스라고 이야기 할때는 node에 포함된 모든 폴리곤을 포함하는 최소의 박스를 의미.

[Chapter 1]

- Introduction -

- Background -

Binary Space Partioning-tree는 1969년에 Shumacker등에 의해 소개되었습니다. 오락 상품들을 개발하는데 이 알고리즘은 거의 사용되지 않았지만 90년대 초반 이후로 게임 산업에서 사용되어 퍼포먼스 향상과 보다 상세한 맵의 표현을 가능하게 만들었습니다. 이 기술을 사용한 첫번째 게임은 게임계의 전설적 존재인 John Carmack 과 John Romero가 개발한 Doom 입니다. 이 이후로 거의 모든 FPS 게임에서는 이 기술이 사용되어져 왔습니다.

- Problem Statement -

게임산업의 치열한 경쟁으로 인해서 이 알고리즘을 향상 시킨 많은 작업들이 이미 있었겟지만 그래도 아직 개선할 사항이 있다고 믿습니다. 우리의 주된 초점은 비싼 비용의 계산들을 런타임에서 부터 분리하여 미리 계산함으로써 많은 양의 정보를 가지고 구축된 구조를 런타임에 실행을 가능하게 하는 것입니다. 또한 우리는 이 작업이 BSP-tree의 힘을 사용하고 있는 게임엔진들을 개선시키고 최적화하는데 일조 하기를 바랍니다. 또한 이 논문이 게임 엔진 개발 방법에 대한 튜토리얼이 되는 부수적인 효과도 있을 것입니다.

이 논문에선 다음과 같은 사항을 설명할 것입니다.

- BSP-tree란 무엇인가
- BSP-tree를 어떻게 생성하나
- 장점/단점
- 사용 가능한 비슷한 기술들
- BSP-tree의 유용성
- 기존의 방식과 우리 방식의 차이

이 주제에 대한 연구는 스웨덴의 O3games라 불리는 회사에서 하였습니다.[http://www.o3games.com] 이 연구의 결과는 자매회사인 Cloop Systems의 상품을 개발하는데 사용되었습니다다. 우리는 BSP-tree와 관련된 모든 이점을 사용하게 구현하였습니다. 즉, BSP-tree의 이점을 적용할 수 있는 모든 부분에 대해 구현하였다는 말입니다. 우리의 논의를 뒷받침하기 위해서 우리가 썼던 코드들을 예제로 사용할 것입니다. C++형태의 의사코드를 사용 하였으며 이것이 명확하지 않을 경우 어디서 최적화가 되었는지 설명하기 위해서 알고리즘의 복잡도(complexity)를 분석할 것입니다. 대부분의 그림 예제들은 2D 기반이지만 3D상에 있는거와 같이 생각할 수 있습니다. 논문을 통틀어서 독자가 3D 관련 기본적인 수학과 벡터 대수에 지식을 가지고 있음을 전제로 합니다.

[Chapter 2]

- BSP-Trees -

- Background -

BSP(Binary Space Partioning) tree는 이름에서 말해 주듯 공간을 작은 집합으로 나누는 것입니다. 하드웨어 가속 Z-버퍼가 존재하는 오늘날 이것의 이점은 공간의 한 장소가 보다 적은 데이터를 가짐을 의미합니다. 하지만 90년대 초반에 BSP-tree를 사용하는 이유는 월드상의 폴리곤들을 정렬하기 위해서 인데 이렇게 하여 정렬된 폴리곤을 뒤에서 부터 앞의 순서로 그림으로써 가장 적은 z값을 가지는 폴리곤을 마지막에 그리려고 했기 때문입니다. 이렇게 폴리곤을 정렬해서 가장 가까운 폴리곤을 가장 나중에 그리게 해주는 다른 방법들이 있는데 예를 들자면 Painter's 알고리즘등 입니다. 그러나 BSP-tree 만큼 싸게 실행될 수 없었는데 이유는 맵상의 폴리곤 정렬이 런타임시 계산되는 것이 아니라 미리 계산되기 때문입니다. 사실상 BSP-tree 를 생성하는 알고리즘은 Painter's 알고리즘의 확장입니다. BSP 알고리즘의 원래 설계인 Painter's 알고리즘은 폴리곤을 뒤에서 부터 앞의 순서로 그리도록 작동합니다. 하지만 Painter's 알고리즘에는 몇 가지 중요한 약점이 있습니다.

* 폴리곤이 다른 어떤 폴리곤을 통과하게 되면 제대로 그려지지 않는다.
* 이 알고리즘은 어렵고 또한 각 프레임마다 순서를 계산해야 하므로 비싸다.
* 순환적으로 겹쳐진 폴리곤들의 경우 처리할 수가 없다.

- The BSP Algorithm -

BSP-tree 생성의 원래 아이디어는 전체 씬의 한 부분을 이루는 폴리곤들의 집합을 선택하여 작은 부분 집합으로 나누어 가는 것입니다. 이때 각각의 부분 집합들은 볼록집합(convex set) 이어야 합니다. 볼록집합이란 말은 이 집합의 원소인 각각의 폴리곤들이 서로에 대해 '앞'에 위치해 있음을 의미합니다. 폴리곤1이 폴리곤2의 앞에 위치한다는 것은 폴리곤1을 이루는 각각의 정점들이 폴리곤2로 정의되는 면의 양의 부분에 있거나 면 상에 있을 때를 말합니다. 예를 들어 안쪽을 향해있는 면들로 이루어져 있는 상자는 볼록집합이며, 바깥쪽을 향해 있는 면들로 이루어진 상자는 볼록집합이 아닙니다.

폴리곤의 집합이 볼록집합인지 아닌지 판단하는지에 대해 필요한 함수들은 다음과 같습니다.

POLYGON_INFRONT 함수는 non-symmetric 비교입니다. 이 뜻은 폴리곤2가 폴리곤1의 앞에 있다고 해서 반드시 폴리곤1이 폴리곤2의 앞이 라고 할 수 없다는 것입니다. 다음 그림을 통해서 쉽게 아실수 있습니다.

그림 3에서 폴리곤1은 폴리곤2의 앞에 있습니다. 왜냐하면 p3 과 p4 모두 폴리곤2의 양의 방향에 존재하기 때문입니다. 하지만 폴리곤2는 폴리곤1의 앞에 있지 않습니다. p2가 폴리곤1의 뒤에 있기 때문입니다.

볼록집합의 필요에 대한 생각은 약간 수정이 가능한데 이것은 하드웨어 가속 Z 버퍼를 사용할 수 있을 때는 그렇게 민감하지 않기 때문입니다. 이 장의 마지막에 이 문제에 대해 언급하겠습니다.

BSP-tree 정의에 필요한 구조체들은 다음과 같습니다.

위를 보면 알수 있듯이 폴리곤은 단순히 3개의 점으로 구성됩니다. 그 이유는 하드웨어인 그래픽카드가 삼각형을 그리도록 설계 되있기 때문입니다. 그러나 BSP-tree 를 생성하기 위한 알고리즘은 폴리곤이 몇 개의 점을 가지든지 상관없이 점들이 한 평면상에 존재하기만 한다면 적용할 수 있습니다.

폴리곤 집합을 작은 부분 집합으로 나누는 방법은 여러가지가 있습니다. 예를 들어, 공간에 임의의 한 평면을 정의하여 이 평면에 양의 방향에 있는 폴리곤 집합을 오른쪽 트리로 넣고 음의 방향에 있는 폴리곤 집합을 왼쪽 트리로 넣을 수 있습니다. 문제는 이런 접급 방식으로는 왼쪽,오른쪽 트리의 사이즈를 거의 같게 나누는 평면을 찾기가 매우 힘듭니다. 왜냐면 공간에는 무한의 평면 집합이 존재하기 때문입니다. 따라서 일반적으로 쓰이는 방법은 공간에 있는 폴리곤중에 하나를 선택하여 이 폴리곤으로 정의 되는 면을 기준으로 폴리곤들을 나누는 것입니다.

우리는 한 폴리곤이 다른 폴리곤의 앞에 있는지를 구별해주는 POLYGON_INFRONT 알고리즘을 정의했습니다. 이제는 한 폴리곤이 다른 폴리곤으로 정의되는 면을 분할하는지(spanning)의 여부도 판단할 수 있도록 이 알고리즘을 수정할 필요가 있습니다. 알고리즘은 다음과 같이 정의 될 수 있습니다.

여기서 문제가 하나 생기는데 면을 분할하는 폴리곤일 경우 어떤 부분집합에 들어가야 하는지 선택해야 합니다. BSP-tree 알고리즘은 이럴 경우 폴리곤을 분할하여 두 개로 만들어 처리합니다. 이렇게 함으로써 Painter's 알고리즘이 가지고 있는 두 가지 문제점, 순환해서 겹쳐진 폴리곤 문제와 서로 교차하는 폴리곤 문제를 해결하게 됩니다. 다음 예제는 어떻게 폴리곤을 분할하는지 보여줍니다.

위의 그림에서 폴리곤1을 기준이 되는 폴리곤이며 폴리곤2를 분류대상이 되는 폴리곤입니다. 폴리곤2가 폴리곤1로 정의되는 면을 분할하므로 폴리곤2는 분할될 필요가 있습니다. 그 결과가 오른쪽 그림입니다. 이제 폴리곤2는 완전하게 폴리곤1에 앞에 있으며 폴리곤3은 완전하게 뒤에 있습니다. 폴리곤2와 폴리곤3의 미세한 여백은 단지 그림에서 두 폴리곤을 구분하기 위해 표시한 것입니다. 실제로 나누어진 후의 두 폴리곤은 맞닿아 있습니다.

BSP-tree를 생성할 때 트리의 균형성과 폴리곤 분할 횟수 제한, 이 두가지 중에 어느 것에 중점을 둘지 결정해야 합니다. 트리의 균형성이란 왼쪽 트리의 노드 깊이와 오른쪽 트리의 노드 깊이의 차이가 많지 않아야 함을 의미합니다. (balanced tree) 폴리곤 분할 횟수 제한은 폴리곤 분할로 새롭게 생성되는 폴리곤의 수를 제한한다는 의미입니다. 만약에 BSP-tree 생성중에 너무 많은 수의 폴리곤이 생성된다면 맵을 렌더링하기 위해 그래픽카드는 힘든 시간을 가질 것이며 프레임율은 떨어질 것입니다. 또한 BSP-tree가 비균형적으로 생성되면 탐색할 때 비싼 비용을 요구하게 됩니다. 우리는 보다 균형적인 트리를 얻기 위해서 약간의 폴리곤 분할을 감수하기로 결정했습니다. 하지만 주된 관심사는 폴리곤 분할로 생성되는 새로운 폴리곤의 수를 줄이는데 있습니다. 아래 의사코드는 폴리곤 집합중에 가장 좋은 기준이 되는 폴리곤을 선택하는 방식을 나타냅니다.

Complexity analysis:
while 루프 때문에 이 함수의 실행 범위를 찾는 것은 매우 어렵습니다. 씬의 구조에 따라서 while 루프가 많은 시간을 돌아갈지도 모릅니다. MINRELATIONSCALE 값은 수용할 수 있는 최소 상대치(MinRelation)가 한번의 반복마다 얼만큼 줄어드는지를 뜻하며, 따라서 최소 상대치가 최적의 답을 찾을수 있을 정도로 줄어드는데 어느 정도의 시간이 걸리는지 나타냅니다. // 여기서 상대치라는 표현은 트리의 균형성을 말합니다. 0부터 1사이의 값으로 1에 가까울 수록 보다 균형적이라는 뜻입니다. MINRELATIONSCALE 값이 크면 최소로 요구되는 균형성이 빨리 적어지므로 기준이되는 폴리곤을 보다 빨리 찾게 될 것입니다. //

최악의 경우는 n개의 폴리곤 집합이 볼록집합이 아니면서 최적의 나눔이 한쪽은 1개의 폴리곤을 가지고 다른 한쪽은 n-1개의 폴리곤을 가지게 되는 경우입니다. 이런 경우는 최소 수용 가능 상대치가 1/(n-1) 보다 작을때 가능합니다. 이것은 의사코드의 27번째 라인에서 볼수 있듯이 i를 루프가 반복된 횟수라고 했을때 MinRelation/MINRELATIONSCALE^i < 1/(n-1)인 경우를 의미합니다. 만약에 최초의 MinRelation 값을 1이라고 했다면 (1은 균형성이 가장 좋은 값으로 MinRelation이 가질수 있는 최대값)

MinRelation/MINRELATIONSCALE^i < 1/(n-1)

1/MINRELATIONSCALE^i < 1/(n-1) // MinRelation = 1 //

(n-1)/MINRELATIONSCALE^i < 1 // 양변에 n-1 을 곱함 //

(n-1) < MINRELATIONSCALE^i // 양변에 MINRELATIONSCALE^i 를 곱함 //

LogMINRELATIONSCALE(n-1)< i // 양번에 LogMINRELATIONSCALE 취함 //

여기서 i(루프 반복 횟수)의 최대값은 없습니다. 하지만 i의 값이 최소값에 매우 가까울 것이기 때문에 단순화하여 그 두 값이 같다고 생각할 수 있습니다. 또한 실제적으로 MINRELATIONSCALE값이 항상 2보다 크거나 같다고 가정하게 되면 다음과 같이 됩니다.

LogMINRELATIONSCALE n-1 = i , MINRELATIONSCALE >= 2

i = LogMINRELATIONSCALE(n-1) < Log(n-1) = O(LogN)

while 루프안에서 폴리곤 집합에 대해 두 개의 반복문이 존재합니다. 이것으로 최악의 경우를 따져본다면 O(N^2 LogN)이지만 전형적으로 대부분의 경우 첫번째 반복에서 조건에 맞는 폴리곤이 발견되는 O(N^2)에 가깝습니다.

CHOOSE_DIVIDING_POYGON에 있는 루프가 끝나지 않을 경우가 있을것 처럼 보일지도 모르겠습니다. 하지만 이것은 사실이 아닙니다. 왜냐하면 폴리곤 집합이 볼록집합이 아닐 경우에 두 가지 집합으로 나눌수 있는 폴리곤이 항상 한 개는 존재하기 때문입니다. CHOOSE_DIVIDING_POYGON은 폴리곤 분할 횟수가 가정 적은 폴리곤을 선택합니다. 여기서 집합을 전혀 나누지 않는 폴리곤 선택을 피하기 위해 나누어진 양쪽 트리 크기의 균형성을 나타내는 상대치(Relation) 값이 미리 정의된 최소 상대치(MinRelation) 값보다 반드시 커야만 하는 조건이 있습니다. 이것을 보다 잘 설명하기 위해서 가장 적은 수의 폴리곤 분할을 하는 기준 폴리곤을 선택하는데 무한 루프를 돌거 같은 예제를 들겠습니다.

위의 예제에서 1,6,7,8폴리곤을 기준 폴리곤으로 선택하게 되면 어떤 폴리곤 분할도 하지 않습니다. 반면에 이 기준 폴리곤 이외의 모든 폴리곤들은 기준 폴리곤의 앞에 존재 하게 되며 다음 루프로 넘어가게 됩니다. 하지만 다음 루프에서 역시 1,6,7,8 폴리곤이 다시 선택되게 되어 무한 루프가 발생할 것 처럼 보일 수 있습니다. 사실 1,6,7,8 // 원래 1,2,3,4 인데 오타 같습니다. //폴리곤은 전체 폴리곤 집합을 가질 수 있는 최소볼록집합(convex hull)의 경계선 위에 있습니다. 이 폴리곤들은 기준 폴리곤이 될 수 없는데 왜냐하면 다른 모든 폴리곤들이 양의 방향쪽으로만 있기 때문입니다. 2,3,4,5 폴리곤들중에 기준 폴리곤을 선택하게 되면 한번의 폴리곤 분할이 일어나게 되지만 두 개의 보다 작은 집합들로 나눠지게 됩니다.

또한 폴리곤 분할이 최소로 일어나는 폴리곤을 기준으로 잡는 것이 항상 좋은 선택이 될수 없는 이유는 대부분의 경우 비균형적인 트리를 만들기 때문입니다. 균형적인 트리가 비균형적인 것보다 런타임에서 보다 좋은 성능을 낼 것입니다.

최적의 기준 폴리곤이 선택되면 남은 폴리곤들의 집합은 기준 폴리곤에 의하여 부분 집합으로 나누어지게 됩니다. 그리고 이 기준 폴리곤을 다루는 법은 두 가지가 있습니다.

1. 리프가 많은 트리가 생성될 수 있습니다. 이것이 의미하는 바는 모든 폴리곤들을 리프 노드들에 넣는 것으로 기준 폴리곤 역시 두 개의 트리중 한 쪽에 포함되게 합니다. 우리 예제에서는 기준 폴리곤을 양의 방향쪽에 있다고 정하여 양의 방향 트리에 포함 시킵니다.

2. 다른 방법으로 노드들의 내부에 기준 폴리곤을 저장합니다. 이 방식은 각각의 부분 집합에 대해서 볼록집합(convex set)이 될때까지 반복됩니다.

// 의사코드나 이어지는 그림 예제를 보면 위 두가지 방법 모두를 적용하고 있습니다. //

BSP-tree 를 생성하는 알고리즘은 다음과 같습니다.

Complexity analysis:
CHOOSE_DIVIDING_POLYGON을 호출하는 것은 O(N^2 LogN) 정도의 Complexity를 가지게 되며, 이것이 재귀함수 호출 부분을 뺀 나머지 함수 부분을 좌우하게 됩니다. 만약에 우리가 폴리곤 집합을 나누는 것이 명확히 짝으로 떨어진다고 가정한다면 GENERATE_BSP_TREE 범위를 다음 같이 계산하여 식을 세울수 있게 됩니다.

T(n) = 2T(N/2) + O(N^2 LogN)

Master's Theorem 을 사용하면 O(N^2 logN)을 얻을 수 있습니다. 여기서 N 은 폴리곤 집합 안에 있는 폴리곤들의 개수를 의미합니다.

이어지는 예제는 BSP-tree가 어떻게 생성되는지 보여줍니다. 밑에 구조는 원래의 폴리곤 집합을 보여주며 예제 설명을 쉽게 하기 위해 각각의 폴리곤에 넘버링을 하였습니다. 이 폴리곤 집합이 분할되어 BSP-tree가 되는 것입니다.

알고리즘을 실행하기 위해서는 MINIMUMRELATION 과 MINRELATIONSCALE 상수들을 먼저 정해주어야 합니다. 우리는 이것을 각각 0.8과 2로 잡는 것이 매우 좋은 결과를 낳는 것을 발견했습니다. 그러나 다른 숫자들로 실험할 수도 있습니다. MINIMUMRELATION 값이 클수록 보다 좋은 균형의 트리가 생성되지만 폴리곤 분할 횟수가 증가하게 될 것 입니다.

최초로 주어진 폴리곤 집합은 명확히 볼록집합이 아님을 알수 있고, 따라서 기준 폴리곤을 선택할 수 있습니다. 일단 훑어보게 되면 {1,2,6,22,28} 폴리곤들은 분할 기준이 될수 없음을 알 수 있습니다. 왜냐하면 최소볼록집합의 경계로 포함되기 때문입니다. 그러나 이들을 제외한 나머지 폴리곤들은 모두 기준 폴리곤 후보가 될 수 있습니다. 가장 폴리곤 분할을 적게 하면서 두 부분집합의 사이즈가 최대한 비슷하게 하는 폴리곤으로 16,17을 생각할 수 있습니다. 이들은 한 라인에 존재하며 어떤 폴리곤도 분할하지 않습니다. 또한 이 둘로 나누어진 두 집합의 크기는 음의 방향이 15개 양의 방향이 13개로 거의 같다고 할수 있습니다. 따라서 기준 폴리곤으로 16을 선택하겠습니다. 결과는 다음과 같습니다.

양쪽 부분 집합 모두 볼록집합이 아니므로 각각이 모두 새로운 분할 기준 폴리곤을 정해야 합니다.

왼쪽 부분 집합의 경후 {1,2,6,7}이 최소볼록집합의 경계에 있으므로 기준이 될 수 없습니다. 4, 10 폴리곤의 경우 같은 선상에 있으며 어떤 폴리곤 분할도 하지 않습니다. 그리고 분할 결과 음의 방향이 7개 양의 방향이 8개로 매우 균형적입니다. 폴리곤4를 분할 기준으로 삼겠습니다.

오른쪽의 경우 {16,17,22,23,28} 폴리곤도 위와 마찬가지로 기준이 될 수 없습니다. {18,19,27,26}은 어떤 폴리곤 분할도 하지 않으나 분할된 결과 음의 방향이 3, 양의 방향이 11로 3/11 의 상대치를 가지는데 이것은 최소 상대치보다 작기 때문에 기준이 될 수 없습니다. 따라서 보다 균형적인 결과를 제공하는 다른 폴리곤을 체크해보아야 합니다. {20,21,24,25}의 경우 한번의 폴리곤 분할이 일어나지만 폴리곤21로 분할했을때 가장 균형적인 결과를 가지게 됩니다. 폴리곤22를 한번 분할 시키고 나면 음의 방향이 6개, 양의 방향이 8개가 됩니다.다음 그림은 이 수행 결과를 보여줍니다.

역시 어떤 부분 집합들도 볼록집합이 아니므로 각각의 부분 집합에 이와 같은 알고리즘이 적용되게 됩니다. 결과적으로 다음과 같은 트리가 생성됩니다.

이것이 최적의 답이 아닐지라도 그것에 매우 가까우며 이것을 얻는데 오랜 시간을 필요로 하지 않습니다.

- Drawing the BSP-tree -

자 인제 BSP-tree가 만들어 졌고 트리의 모든 폴리곤들을 빠짐없이 그리는 것은 매우 쉽습니다. 이어지는 알고리즘이 이것을 뜻합니다. 여기서 IS_LEAF라는 함수는 해당 BSP-node 가 리프일 경우 true 를 리턴하고 아니라면 false를 리턴한다고 가정합니다.

// 의사코드에 렌더링 순서가 잘못됬습니다. front의 경우 left 를 먼저 behind의 경우 right를 먼저 그려야 올바르게 z 버퍼링이 됩니다. //

이 방식으로 그릴 경우 스크린에 그려지는 폴리곤 숫자의 감소는 없습니다 때문에 수백 수천개의 폴리곤으로 이루어진 맵의 경우 이것이 좋은 답이 될 수 없습니다. // 단지 back to front 순서로 폴리곤을 그리는 알고리즘입니다. // 어떤 방법으로든 보여질 수 없는 노드들 혹은 보여질 수 없는 폴리곤들 까지도 무시 되어져야 합니다. 이것을 은면 제거(hidden surface removal)라고 합니다. 이것을 구현하는 방법은 여러가지가 있습니다. 다음 장에서 그것들에 대해 설명할 것입니다.

Related reading:
[Sunsted, Tod. 3D computer graphics:

Moving from wire-frame drawings to solid, shaded models]
[Sobey, Anthony. Software Engineering]
[Southwick, Andrew R. Quake Rendering Tutorial]
[Meanie, Mr.. Binary Space Partitioning Trees]
[Royer, Dan. Dan’s Programming Tutorials]
[Feldman, Mark. Introduction to Binary Space Partioning Trees]

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com

[출처] [번역] BSP-tree 논문 : 서문,1장, 2장|작성자 리안

tag : FPS, BSP, World, Level, LevelDesign

[Level Design] 바이오쇼크 "랩쳐"의 탄생

두더지 — Tue, 29 Jul 2008 08:02:22 GMT

현실에 존재하지 않는 장소에 실제로 있음직한 공간을 창조하는 방법은 무엇일까?
Gamasutra는 마이크로소프트의 Gamefest 이벤트에 참석해
2K Marin의 수석 배경 아티스트 Hogarth de la Plante 씨와 수석 디자이너 Jean-Paul LeBreton 씨를 인터뷰하며 바이오쇼크의 수중도시 랩처(Rapture)가 만들어질 때를 회고해보았다.

이 두 사람은 현재 2K Boston에서 장소를 옮겨 2K Australia 에서 '바이오쇼크 2'를 제작하고 있다. (주- 2K Boston/2K Australia는 Take-Two Interactive Software에 인수된 Irrational Games의 새 이름입니다.)
그들은 이번 인터뷰를 통해 어떻게 '바이오쇼크'를 만들었는지를 설명하였다.

De la Plante 씨는 '랩처'를 창조하는 일에 대한 어려움부터 이야기를 시작했다.
"랩처는 실제처럼 만들기 까다로운 특이한 공간이었습니다.
바이오쇼크는 그 스토리와 분위기있는 배경 때문에 비평가들에게 정말로 유명했었죠."

그는 미술(art) 부문과 디자인(설계, design) 부문의 협력이 게임을 성공시킨 핵심 요인이라고 말했다.
그러나 두 부문의 관계에 문제가 없지는 않았다.
"처음에는 의사소통이 무척 어려웠습니다. 하지만 의사소통이야말로 결국 일을 성공시킨 유일한 원인이었죠."

LeBreton 씨가 이에 동의했다.
"바이오쇼크 제작에 있어서 하나의 도전은, 가능한 한 상당히 일찍 몇몇 컷신장면을 만들어 놓기로 결정했다는 것입니다."
그는 이렇게 회고했다.
"그래서 우리가 만드는 배경물에는 '스토리 전달'이라는 목표가 부여되었습니다. 사실은 배경물에는 어떤 목표의식이라는 개념이 없는 경우가 많습니다."

이런 작업은 이따금 어려움을 겪기도 했다.
왜냐하면 랩처라는 수중도시의 특성 때문이다.
"정말로 있음직한 곳을 창조한다는 것은 중요한 일입니다.
처음 일을 시작할 때는 참 이상한 배경이구나 하고 생각할 수 있지만,
그렇다고 그 배경을 자의적으로 만들거 버리거나 바보처럼 보이게 해서는 안됩니다."

바이오쇼크 레벨(level)들의 개발취소된 버전들을 살펴본 후에야,
미술 팀과 디자인 팀은 서로 긴밀히 협력하기 시작했다.
De la Plante 씨의 말이다.
"많은 공간들이 건축적으로 흠이 있다는 사실을 이해시키기란 어려웠습니다.
많은 부분들이 자의적(마음대로) 만들어진 것이었죠.
여기에 왜 발코니가 있느냐. 여기에 왜 도로망이 있느냐, 여기에 왜 내려가는 램프(ramp, 건물 사이를 잇는 경사로)등등...
많은 곳들이 꽤나 랜덤하게 만들어졌었습니다.
그야말로 '자의적'이었죠."

그는 계속 말을 이었다.
"디자인 팀에 있어서도 이것은 나쁜 일이었습니다.
왜냐하면, 우리가 만드는 게임은 세미-논-리니어 게임(semi-non-linear game, 절반쯤은 일직선으로 진행되고 절반쯤은 플레이어가 자유롭게 진행하는 게임)이었기 때문이었습니다.
앞으로 가야할 장소가 어디일지, 그곳엔 무엇이 있을지 만들어가는 일은 참으로 어렵다는 것을 알게 되었죠."

대화의 목적은 바이오쇼크에 숨어있는 "사고의 과정(thought process)이 무엇인지 알아내는 것"이고,
나아가 "공간에 실제로 있음직함(believability)을 부여하는 일의 중요성"을 확립하는 것이다.

역할의 변화

De la Plante 씨가 말을 잇는다.
"저희가 처음 일을 시작할 때는 지금과 무척 달랐습니다.
저는 'Quake' 와 'Half-Life 1' 시절 레벨을 만드는 일부터 시작했습니다.
레벨 디자이너의 역할이란 당시에는 상당히 방대했습니다.
그 공간이 어떻게 보이고, 어떻게 들리고, 어떻게 플레이되는지 하는 모든 창조적인 권한을 단지 한 사람에게 쥐어주는 것과 같았습니다.
한 사람이 다 만들고 보여주는 일이었죠.
또 당시는 디자인(설계) 쪽에만 중점을 두었었습니다.
그런 식으로 쭉 많은 세월이 흘렀죠.
디테일에 한해서는 현재의 10% 정도밖에 되지 않았습니다.

"잘 알려지지 않은 사실인 것 같아 말씀드리는데,
기본적으로 저희는 상당히 '표준적인 언리얼 엔진 개발 과정'으로 게임을 개발하고 있었습니다.
그렇게 바이오쇼크를 개발하던 중 어떤 시점에서, 아마 2006년 초반 쯤이었나 싶은데,
우리 디자인 팀이, BSP 형태로 상당히 러프한 수준이었지만, 랩처 세계의 모든 장소를 만들어내었습니다."

미술담당자는, 디자인 팀이 만들어준, 다소 다듬어지지 않은 당시 디자인 프로세스에 대해 솔직한 반응을 보였습니다.
"그들(디자인 팀)이 이 따위를 만들어 담장 밖으로 던져 주었군.
이걸로는 우주 던젼 같은 스파게티 만찬 밖에 못만들겠네.
이봐요. 미술 담당자들.
이게 기차역이랍니다.
이걸 좀 더 복잡한 기차역으로 만들어 봅시다!"
라며 조크를 했었죠.

그렇게 나온 결과물은, 미로같이 복잡하고 전혀 사람의 손으로 만든 것으로 보이지 않는 희한한 복도들 뿐이었다. (물론 사람의 손으로 만들어진 것처럼 보이려고는 시도했지만)
LeBreton 씨는 그 문제에 대해 이렇게 정리했다.
"이것은 그저 진공 상태(무개념상태)에서 디자인된 것이었습니다. 상당히 좋지 않았죠.
이런 공간은 쉽게 아무렇게나 설계할 수 있습니다.
전혀 심미적인 면도 고려하지 않고, 설계를 밀접하게 생각하지도 않고,
사람들이 이런 공간을 어떻게 다닐지를 생각하지도 않은 결과물이었죠."

De la Plante 씨가 이에 맞장구 치며 말했다.
"그 시점까지 디자인 팀은 미술 팀과 상의도 그리 나누지 않고 모든 레벨을 만들었던 것입니다.
반대로, 미술 팀은 랩처가 어떻게 보일지 자기들만의 프로토타입을 만들던 중이었죠.
우리는 전혀 의사소통이 되지 않았습니다.
두 부서는 각각 이런 생각을 했죠.
'우리만이 이 게임을 어떻게 만들지 아는거야. 쟤네들은 몰라.'"

배경미술 담당 De la Plante씨는 다음과 같은 농담을 던졌다.
"그 일에 대해 우스개 소리를 한마디 하자면,
당시 아티스트(미술담당)들은 모든 디자이너들에 대해서 '주사위나 굴리는 멍청이들(dice-rolling nerds)'이라고 생각했고,
디자이너들은 아티스트들에 대해 '코카인이나 흡입하는 락스타들(coke-snorting rock stars)'라고 생각했었죠."

LeBreton 씨가 한마디 더한다.
"서로 원하던 바를 몰랐던 것은 아니었습니다.
하지만 비전(vision)이 통일되지를 못했죠.
'이것이 바로 바이오쇼크다' 라고 모두가 한자리에 앉아 동의할만한 지점이 없었습니다.
우리는 예전부터 같이 이 일을 해왔습니다.
우리는 각자 임무를 맡았고, 새로운 것을 해보자고 결의했습니다.
자리에 앉아 함께 일을 하면서 두 팀 모두 만족할 수 있는 무언가를 찾아보기로 했죠."

그러자 좀 더 '바이오쇼크'다운 무언가가 나타난 것이다.
LeBreton 씨가 말을 잇는다.
"마침내 우리는 결실을 맺었습니다.
많은 예술적 요소들이 첨가된 가운데, 돌아다닐 수 있는 많은 자유도가 더해진 결실 말이지요.
처음으로 거둔 성공적인 결실이었으며 그제서야 우리는 이렇게 말할 수 있었습니다.
'이것이 바이오쇼크다. 이게 바로 바이오쇼크야. 성공이다.'
당연하게도 이 결과는 두 팀의 협력에서 나온 것이었습니다."

De la Plante 씨가 이에 동의했다.
"JP와 저는 4~5 일 씩 한 자리에 앉아 많은 것들을 만들어냈습니다. 그 일은 정말로 재미있었습니다."

LeBreton 씨가 말을 받는다.
"우리는 마치 음악을 연주하는 것처럼, 건축이란 것을 통해 그 장소에 담겨있는 정신(spirit)을 표현해 나갔습니다.
우리가 만든 건축물을 통해 플레이어들은 그것을 느낄 수 있었을 겁니다."

4 단계 과정을 시작하다

바이오쇼크는 단순한 공식을 따라 단계를 밟아나갔다:
기능(fuction) 다음에는 형태(form)가 나오고, 형태 다음에는 다시 기능이 나온다는 것이다.
De Le Plante 씨가 말한다.
"첫번째 요소는 기능(fuction)입니다.
우리가 가장 우선적으로 생각한 것은 그 공간의 기능이 무엇이냐는 것입니다.
랩처는 실제 도시로 보여야했기 때문에 이것은 중요한 문제였습니다.
우리는 용암동굴이나 램프(ramp) 월드를 만들고 싶지는 않았습니다.
'Olympus Heights'라는 곳을 표현하기 위해서는 고층 아파트 타워가 필요했습니다."

LeBreton 씨의 말이다.
"모든 있음직한 것들을 창조해내는 데에 해당하는 말이기도 한데,
디자인과 네비게이션에 있어서 정말 중요한 것은
보다 일찍 그 장소의 형태를 결정할 수 있다면,
어떤 디자인 원칙을 가지고 더 일을 깊이 진행할 수 있다는 것이죠."

"몰(mall)에 있는 중에 갑자기 화장실에 가고 싶습니다.
그러면 가게를 빠져나와 몰 가운데 길로 나와야 하죠.
2개의 길 중 하나의 길을 택해 가다보니 식당가가 나옵니다.
보통 화장실은 식당가에서는 떨어져있죠.
실제 세계의 건축은 이런 문제들에 대한 생각을 수없이 갖고 있습니다."

"보통의 플레이어라면, 플레이어가 현재 처한 레벨에서 길을 찾고 있을 때,
화장실과 복도를 빠져나오는 길을 찾는 데에는 큰 곤란을 느끼지는 않을 것입니다."
라며 이 디자이너는 말을 마무리했다.

De la Plante 씨가 계속 말을 잇는다.
"공식의 다음 단계는 형태(form)입니다. 이것은 일반적으로 심미적인 고려에 대한 것이지요."

LeBreton 씨가 이 순환관계에 대해 결론을 내어준다.
"세번째 단계는 다시 기능(function)으로의 귀환입니다.
실제 순간순간마다의 기능, 즉 순간순간의 게임플레이 경험,
그리고 그 세세한 모든 디테일들이 어떻게 설치되어야 하는가 하는 것입니다.
아트(art) 이후 통과점으로서의 게임플레이도 아니고 그 반대(게임플레이 이후의 아트)도 아닙니다.
이 둘(아트 + 게임플레이)을 흔들어 섞어놓는 길은,
순간순간의 게임플레이를 레벨 속에 지을 넣을 수 있는 가 하는 것,
그리고 그 순간순간의 게임플레이가 그 레벨을 지탱해주는 다리가 될 수 있는가 하는 것입니다.

"이러한 융합은 많은 FPS 명작 게임들의 디자인에 잘 나타납니다.
플레이어가 엄폐할 수 있는 장소도 필요하고, 적들에게도 숨을 수 있는 장소가 필요합니다.
또 너무 어지럽고 혼란스러운 장소는 필요하지 않죠."

이 수석 아티스트는 그리고나서 다음과 같이 말했다.
"제작과정이 이 시점에 오면, 우리는 앞으로 이동하면서 전체적인 바이오쇼크 레벨의 흐름을 토의하며 점검해봅니다.
이 과정을 소위, 레벨 아키텍트 포지션(the level architect p!osition)의 탄생이라 부릅니다.
이 토의과정에서 너무 오래 지체되는 곳이 있으면 체크를 해 둡니다.
레벨 아키텍트 포지션(the level architect p!osition) 작업이란 것은
디자인(설계) 지식이 부족한 아티스트(미술담당)에 관한 일이기도 하지만,
모든 디자인적인 면을 종합적으로 점검해보는 단계이기도 합니다."

그리고 마지막 네번째 단계는 자주들 말하는 미장센(mise-en-scene)이라는 것이다.
영화용어로서 "set the scene (장면 설정)"을 뜻하는 말이다.

De la Plante 씨는 이렇게 설명했다.
"우리가 만든 공간에서 무슨 일이 일어날까요.
우리는 수중 아파트 타워를 만들었고, 그것이 어떻게 보이고 있는지도 알고,
JP는 게임플레이가 어떤 기능을 할 지도 결정한 상태입니다.
그 다음 우리는 자문을 해 보죠:
플레이어가 이곳에 오기 전에는 무슨 일이 일어난 것일까?

...

이 지점에서부터 바이오쇼크에 생명이 불어넣어지는 것입니다.
미장센을 더 많이 넣은 레벨일 수록, 그곳을 둘러싼 스토리가 더 많이 그 세계를 통해 전달되는 것입니다." 라며 그는 웃으며 말했다.

LeBreton 씨가 이어서 그 설명을 했다.
"우리는 '레벨 아키텍트 포지션' 작업을 정형화했고, 레벨 디자이너 한명씩과 짝을 이루어서 첫째날부터 협력을 해 나갔습니다.
이 일의 목적은, 두 부서(아트, 디자인)이 같은 장면에서 함께 비평하거나 정의할 수 있는 무언가를 찾고, 스테이지의 윤곽 속에서 무언가를 찾아내는 것입니다.
이 단계는 대부분의 하이-레벨 크리에이티브 디자인 단계에서 하는 일입니다.

"레벨 아키텍트(디자이너)와 아티스트가 하나가 되는 게 제일 우선이고 이들은 BSP 작업을 함께 해 나갑니다. 공간에 대한 미술 작업이 다듬어지고 완료되기 위해서는 이 과정이 있어야 합니다. BSP 작업을 해야만 하는 것입니다. 이 과정에서는 변화를 주기가 무척 쉽습니다."
LeBreton 씨는 자랑스럽게 말했다.
"우리가 함께 작업을 했다는 것이 중요합니다."

De la Plante 씨는 작업과정에 대한 설명을 다음과 같이 말하며 결론지었다.
"우리의 작업방법에 있어서 잠재적인 논쟁의 여지가 있는 일은,
제가 앞서 말했던 레벨 제어(level of control)가 디자이너에게는 없다는 것입니다.
저는 순수한 디자이너의 역할로부터 벗어나,
저와 다른 일을 하던 사람들(아티스트)의 역할도 알게 되었고,
그럼으로써 멋진 공간과 플레이하기 좋은 공간을 만들 수 있었습니다.
그들(아티스트)도 역시 저와 마찬가지였고요.
일을 끝내서 행복합니다."

그는 웃으며 말했다.
"그럼으로써 '바이오쇼크' 같은 게임이 탄생한 것이라면,
정말로 훌륭한 절충(타협)이라 할 수 있지 않을까요."

출처: http://www.gamasutra.com/php-bin/news_index.php?story=19536, 루리웹

=================================================================================

Level Design은 딱히 내 전문 분야가 아니다. (전문 분야가 있기나 할까....)
B프로젝트(MMORPG) 초기 초반 마을 구조를 잡고 있을때 문득 머리에 이런
생각들이 들었다.
"내가 World를 만들다간 유저들이 하루종일 뛰기만 하다 언인스톨 할 것만 같다......."

당시 내가 만들면서도 참으로 재미 없는 월드를 구상하고 있었다.
물론 신입이었기 때문에 기본적인 지식도 없었을 뿐더러 열정만 앞서 있었기 때문에 뭐가
그르고 옳은 것인지 분간도 못하던 시기였다.
하지만 내가 만들면 유저는 꼭 언인스톨 할 것이라는 생각에는 뭔가 확고한 마음이 들었었다

근래에 호기심을 자극한 분야였기 때문에 이것저것 자료도 많이 찾아보고 스스로
답을 찾기 위해 머리 싸메며 고민도 해봤다. 우리 게임이 원하는 Level은 익숙하지만
익숙하지 않은 세계를 그려내는것이라 생각 했었고 그것에 대해 표현 하려고 나름대로의
방법으로 여러가지를 시도 해 봤던것 같다.

Jupiter EX 로의 개발 초기에는 많은 한계점을 가지고 있었다. 현재는
개량된 엔진으로 어느정도 F.E.A.R 만의 느낌은 버릴 수 있게 되었고 더욱 온라인에
가까운 모습의 게임으로 변해 주었다. 얼마전 나온 Another Day 에서는 아직 F.E.A.R
느낌이 많이 남아 있어서 왠지 친숙한 느낌마저 들었으니

아 잡소리가 길었다. 아무튼 Level Design 에 관련해 여러가지 보던중 위
"랩쳐"의 탄생 이야기는 내가 깊은 터널속 빛과 같은 느낌으로 다가 왔다. 루리웹에
친절히 번역되어 있었다.(누군지 모르지만 감사)
음...꼭 Level 뿐 아니라 거의 모든 개발 과정에서 그렇겠지만 커뮤니케이션의
중요성을 다시 한번 깨닿게 해 주었다고나 할까 자세한 이야기들은 쓸 수 없으니
일단은 안타깝긴 하군. 우리 Level Design팀에 있어서도 조금더 이야기가 많이
필요하지 않을까 생각한다.

나는 단지 세모만 그렸을 뿐인데 원화가는 초록빛 산을 그리고 모델러는
초록색 수박바를 만들고 있다면 문제지 않을까 위의 "랩쳐"이야기 에서도 비슷한
이야기를 하고 있다. 아 물론 저렇게 심한 지경으로 간다면 크리티컬 이겠지만
아니라서 다행이군. 헌데.........그런데 생각해 보니 나는 Level팀에서 손을 땠다......
....할말이 없군