UE4 Brush, BSP, PhysX Convex 에 대해

주의 : 공부하면서 정리한 것이라 잘못된 내용이 있을 수 있습니다.

주의 : BSP 알고리즘에 대해 구체적으로 설명을 하지 않습니다. 어느 정도 개념을 알고 있다고 가정합니다.

---

UE4 Brush, BSP, PhysX Convex 에 대해

BSP( Binary Space Partitioning ) 는 둠라는 게임에서 사용된 이후로 매우 유명해졌습니다. 말 그대로 씬을 두 개의 노드로 분할한다는 의미로 이와 관련된 자료는 인터넷에 많이 있으니 검색해 보시기 바랍니다. 이 문서에서는 UE4 에서 어떤 방식으로 BSP 를 이용하는지에 대해서 중점적으로 다룹니다.

기존의 1인칭 슈팅 게임에서는 한정된 자원으로 게임을 만들어야 했기 때문에 메쉬의 사용을 최소화하고 빠르게 위치 및 충돌을 검출하기 위해서 BSP 를 많이 사용했습니다. 특히 얼리얼에서는 CSG( Constructive Solid Geometry ) 라는 개념을 통해 씬을 쉽게 구성할 수 있는 도구를 제공했습니다.

하지만 이제는 예전과는 다르게 1인칭 슈팅 게임들도 복잡한 지오메트리를 사용하게 되고 그에 걸맞게 하드웨어 성능과 공간분할 알고리즘들이 발전하게 되면서 BSP 를 사용하지 않는 추세입니다. 그러나 언리얼에서 여전히 BSP 를 중요하게 사용하는 부분이 있습니다. 바로 Geometry 라 표현되는 개체입니다.

게임을 만들어 보신 분이라면 한 번쯤은 "Trigger Volume" 이라는 액터를 배치해 보신적이 있을 것입니다. 이 트리거 볼륨 액터는 사용자가 어떤 영역에 들어 오고 나가는 것을 알려줍니다.

그림1

하지만 저 계단 위쪽에 들어 왔는지 나갔는지를 판단하려면 매우 복잡한 모양의 트리거 볼륨이 필요합니다. 왼쪽에 있는 "Modes" 툴바의 "Geometry Editing" 항목을 선택하면 이것을 복잡하게 편집할 수 있습니다. "Extrude" 를 기능을 사용해서 멋지게 편집해 봤습니다. 절대 여러 개의 볼륨을 사용한 것이 아닙니다. 하나만으로 만들었습니다.

그림2

이 경우에도 저 볼륨의 영역에 캐릭터가 들어갔다 나갔다 하면 앞에서와 같은 이벤트가 발생하게 됩니다. 

예전에는 BSP 노드에 대한 충돌검사를 수행했습니다. 하지만 UE4 에서는 PhysicsX 를 도입하면서 BSP 노드를 convex 집합으로 바꾸게 됩니다. 이것을 언리얼에서는 "Aggregate Geometry" 라 부르게 됩니다. 

언리얼에서 Volume 은 AVolume 이라는 개체로 표현되며, 이는 ABrush 를 상속합니다.

그림 3

• ABrush 는 기존의 UE3 의 CSG 브러쉬를 대체합니다. "Placement Mode" 에서 "Geometry" 카테고리에 포함됩니다. 여러 개의 액터가 존재하는데 이것은 브러쉬 빌더의 타입을 보여 줍니다. FBspModeModules::StartupModule() 메서드에서는 "Geometry" 카테고리에 이 빌더들을 등록하고 있습니다. 관심이 있으신 분들은 찾아 보시기 바랍니다.
• AVolume 은 ABrush 중에서 볼륨 개체를 추상화하기 위해서 사용됩니다. 기본적으로는 ABrush 의 기능과 동일합니다.
• ABrushShape 은 geometry editing mode 에서 "Lathe" 를 위해 사용된다고 하는데 뭔지 잘 모르겠습니다.

그림 4

어쨌든 ABrush 가 여기에서 다루고자 하는 핵심입니다. ABrush 에서는 폴리곤 데이터를 UModel 개체에 물리 및 렌더링 데이터를 UBrushComponent 를 개체에 저장합니다.

이 문서에서 이야기하고자 하는 핵심 클래스들은 다음과 같습니다. 물론 훨씬 더 많은 자료구조를 포함하고 있지만 주제와 밀접한 클래스들만 정리했습니다.

그림 5

사설이 길었는데요 이제 조금 구체적으로 파 보도록 하겠습니다.

Brush : Polygons & BSP Nodes

---

언리얼에서는 브러쉬는 어떤 메쉬를 생성하기 위한 틀을 의미합니다. 액터로서는 ABrush 로 표현되지만, 실제 폴리곤( 혹은 지오메트리 ) 데이터는 UModel 개체에 포함되어 있습니다. UModel* ABrush::Brush 라고 정의되어 있습니다.

우리가 에디터에서 geometry editing mode 를 켜 놓고 편집을 하게 되면 실제로는 UModel 개체를 수정하게 되는 것입니다. 이것은 브러쉬의 지오메트리를 표현하기 위한 많은 정보들을 포함합니다. 그 중의 핵심이라고 할 수 있는 것은 폴리곤 데이터( FPoly )와 BSP 노드 데이터( FBspNode )입니다.

폴리곤 데이터는 하나의 면( FPlane )을 표현합니다. 물론 범위가 정해져 있으니 점 데이터도 포함하게 됩니다. 예를 들어 큐브는 6 개의 폴리곤과 24 개( 각 노드당 4 개 )의 점으로 구성됩니다. 점을 공유하고 있지는 않더군요. 그런데 점을 하나 수직으로 움직이게 되면 면 하나가 두 개의 삼각형으로 전환됩니다. 이 경우에는 7 개의 폴리곤과 26 개의 점으로 구성됩니다; 5 * 4 + 3 * 2 = 26.

그림 6

여기서 퀴즈입니다. 그림 2 의 폴리곤은 몇 개일까요? 볼륨을 둘러 싸는 가장 바깥쪽 면 개수만 세야 합니다. 답은 댓글에...

편집을 통해 폴리곤 정보가 변경되면 FBSPOps::bspBuild() 라는 메서드가 호출됩니다. 

UE4 에서 BSP 를 구성하는 데 있어 핵심이 되는 파라미터는 "Balance" 입니다. 이는 균형잡힌 이진트리를 만드느냐 아니면 가장 분할( 다른 폴리곤을 자르는 것 )이 적은 이진트리를 만드냐를 결정하게 됩니다. 그것의 pseudo code 는 다음과 같습니다.

for each polygons for each other polyons check relation with other polygons calculate score from relations if score is under max score polygon is best splitter

여기에서 관계라는 것은 front, coplanar, back, split 입니다. 각각의 카운트를 세는거죠. 그리고 점수는 다음과 같이 계산됩니다.

Score = ( 100.0 - float(Balance) ) * Splits + float(Balance) * FMath::Abs( Front - Back );

이 Balance 값은 현재 15 로 하드코딩되어 있습니다( 수정 : 코드 검색하다가 보니 0, 15, 70 인 경우가 있었습니다 ). 예전에는 수치를 받았던거 같은데 UE4 로 오면서 경험적으로 좋은 수치를 설정한 것 같습니다. 

내용을 곱씹어 보면 다른 폴리곤을 많이 쪼갤수록 그리고 Front 와 Back 의 개수 차이가 클수록 점수가 높아집니다. 그런데 Lerp( linear interpolation ) 처럼 Balance 값을 통해 가중치를 조절합니다.

만약 Balance 가 크다면 어떻게 될까요? 100.0 - float(Balance) 의 값이 작아지므로 Front 와 Back 의 차이가 클수록 좋은 점수를 받겠죠. 반대로 Balance 가 작다면 어떻게 될까요? 100 - float(Balance) 의 값이 커지므로 쪼개는 개수가 많아질수록 좋은 점수를 받겠죠. 헷갈리니 예를 들어 보도록 하겠습니다.

그림 7 은 3 이 splitter 로 선택되었을 때의 상황을 가정하고 그린 것입니다. 2 를 2f 와 2b 로 나누지 않은 이유에 대해서는 나중에 알게 될 것입니다. 그림 7 에서 각 폴리곤들의 노멀은 바깥쪽이라고 가정하시고 보시면 됩니다.

그림 7

Balance	1 ( f : 0, b : 4, s : 0 )	2 ( f : 0, b : 4, s : 0 )	3 ( f : 1, b : 2, s : 1 )	4 ( f : 1, b : 2, s : 1 )	5 ( f : 0, b : 4, s : 0 )	Best Splitter Order
15	60	60	90	90	60	1, 2, 5, 3, 4
75	300	300	90	90	300	3, 4, 1, 2, 5

Balance 가 75 인 경우에는 3 이 splitter 로 사용됩니다. 3 이 가장 먼저 splitter 로 사용되며 5f, 5b 가 생성됩니다. 여기에서 의문이 발생할 것입니다. 왜 2 는 쪼개지지 않을까요. 4 가 splitter 로 사용되는 시점에는 3 을 기준으로 front-end 로 분할된 상황이기 때문에 2 는 4 가 쪼갤 수 있는 대상이 아닙니다. 4 는 front 에 있고 2 는 back 에 있습니다. 그러므로 분할은 3 을 splitter 로 사용했을 때 단 한 번만 발생합니다. 최종적으로 리스트에는 1, 2, 3, 4, 5f, 5b 가 존재하게 됩니다.

결국 Balance 가 15 인 경우와 75 인 경우에는 다음과 같은 이진 트리가 나오게 됩니다.

그림 8

그림 8 에서 보면 leaf 노드에 색이 칠해져 있는 것을 볼 수 있습니다. leaf 노드에 도달했다는 것은 면으로 이루어진 도형이 닫힌거라 생각하시면 됩니다. 

예를 들어 오른쪽 그림의 경우를 봅시다. 평면 3, 1, 2, 5b 에 대해서 어떤 점과의 위치 관계를 구했을 때 모두 backside 라고 하면 녹색 도형 안에 점이 존재한다고 할 수 있습니다. 이것을 BSP Tree Traverse 의 관점에서 보자면 back-leaf 노드에 도달한 것입니다. 

왼쪽 그림의 경우를 봅시다. 만약 front node 가 존재한다면 그쪽으로 concave 가 형성되는 구멍이 뚫려 있다고 보시면 됩니다. 만약 front-leaf 노드에 도달했을 때 폴리곤의 normal 과 점의 관계가 backside 라고 한다면 닫히게 되는 것입니다. 만약 frontside 라고 하면 열린 폴리곤이라는 의미가 됩니다.

PhysX Convex

---

이제 이것을 실제로 사용하기 위해서 PhysX 에 넘겨 줄 필요가 있습니다. 그런데 많은 분들이 알고 계시다시피 물리 엔진들은 concave 를 사용하지 않습니다. 사용한다고 하더라도 내부적으로 이것을 convex 집합으로 바꾸게 됩니다. 이 convex 집합이 바로 Aggregate Geometry 입니다.

BSP 노드들을 Convex 로 바꾸는 작업은 ModelToHullsWorker() 에 의해서 수행됩니다. 여기에서 하는 작업은 별거 없습니다. 그림 8 처럼 concave 를 convex 로 쪼개는 작업을 합니다.

노드를 순회하면서 폴리곤을 수집하다가 leaf 를 만나면 그때까지 수집했던 폴리곤들을 사용해 convex 를 하나 생성합니다. 그런데 여기서 알아야 할 점은 front node 를 만나면 새로운 convex 를 만들기 위해 폴리곤들을 수집하기 시작한다는 것입니다. 아까도 언급했듯이 front node 가 있다는 것은 그쪽으로 뚫려 있다는 이야기이므로 leaf 를 만날 때까지 새로운 폴리곤을 수집해야 합니다.

닫힌 convex 가 완성되면 AddConvexPrim() 이라는 메서드를 호출하게 되는데요, 여기에 위에서 언급했던 폴리곤의 리스트( 즉 plane list )를 넘겨 줍니다. 그 메서드에서는 정확성을 높이기 위해서 vertex snapping 과 같은 작업을 수행하고 FKAggregateGeom 에다가 FKConvexElem 를 추가해 줍니다. 여기까지 하면 PhysX Convex 를 생성할 준비를 마친 것입니다.

실제 PhysX Convex 는 UBodySetup::CreatePhysicsMeshes() 호출을 통해 생성됩니다.

생성된 PhysX Convex 와 Brush Helper 의 모양을 비교해서 보여줬으면 좋겠지만 제가 PhysX Mesh 를 출력할 수 있는 방법을 찾지 못해서 안타깝네요. 

PhysX Capture

---

PhysicsX Visual Debugger ( PVD ) 를 사용해서 씬을 캡쳐할 수 있다는 제보를 받고 시도를 해 봤습니다. 이미 API integration 은 되어 있는 상황이더군요.

UE4 에서는 PvdConnect() 라는 메서드를 통해서 이를 지원합니다. 

에디터 콘솔 명령창에서 "pvd connect" 와 "pvd disconnect" 를 사용해서 활성화/비활성화할 수 있습니다. 실제 적용되는건 play 를 눌렀을 때입니다. 그러므로 play 버튼을 누른 후에 connect 했다가 disconnect 하면 됩니다. 계속 캡쳐되고 있으므로 프레임 디버깅할 것이 아니라면 빨리 disconnect 하세요.

그런데 저는 pvd 연결하면 프로그램이 멈춰버리더군요.... 나중에 방법을 찾으면 캡쳐해서 올리도록 하겠습니다.

추가 : 결국 해결( ? )했습니다. pvd3.exe 가 너무 많이 떠 있어서 그랬던 것 같습니다. 다 지우고 하나만 띄우니 되네요.

좌표계를 UE4 와 일치하는 화면을 보시려면 "Left-Handed", "Z+" 설정하시고 Bounding box 를 "All" 로 하시면 쉽게 확인할 수 있습니다. Convex 별로 physx collision 이 할당된 것을 확인하실 수 있습니다.