All Right ?

[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

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

• hurry up to me!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!111 by 참돔