02.24

BSP

실내지형, 방 단위의 분해, PVS를 통한 Portal Rendering

Reference : https://en.wikipedia.org/wiki/Potentially_visible_set

절차

1. Map의 전체 Polygon List 정보 보유(골재외의 Accessory Object 제외)
2. 분할할 수 있는 기준점 Polygon(Best Splitter)을 선택 후 앞뒤로 분해

Best Splitter

전후면에 속하는 Polygon의 차가 최소가 되는 면

1개의 면을 선택된 Splitter가 분해할수도 있음

더 이상 분해되지 않을때까지 분할

Best Splitter 조건

Forward-Backward로 분할하는 Polygon의 개수 차가 최소가 되도록 하는 면
단, 만약 BS가 다른 면을 분할해야하는 경우를 최소화하기위해 이 때는 추가적인 가산 처리

예 : $SidedScore = SidedCount * DividedCount$

Leaf Node 조건

모든 Splitter에서 분할할 때, Backward에 아무것도 존재하지 않는 경우

분할 경우의 수

2:1 분할

2개의 선을 분할하는 경우

1:1 분할

면 위에 1개의 점이 존재하고, 1개의 선을 분할하는 경우

0:1 분할

면 위의 점 3개가 존재하는 경우
면 위에 점 2개가 존재하는 경우
면 위에 점 1개가 존재하는 경우
분할하지 않는 경우

면 분리법

평면 Binding 순서에 따라서 Forward Vertex List, Backward Vertex List에 추가
Vertex, Ray-CollisionPoint 순서

BSP에서의 탐색

1점이 BSP Tree의 BS를 기준으로 Foward에 존재하는가 Backward에 존재하는가 점검