08.05

공간분할

넓은 공간 속 많은 Object를 전부 한번에 Rendering 할 수는 없음
안보이는 것은 제외

camera frustum

FOV : 90°
clipping plane : 2 km

종류

BSP(Binary Space Partition)

트리를 순회하는 과정을 통해 공간을 정확하게 그릴 수 있음
실내에서 주로 사용

Reference : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B3%B5%EA%B0%84_%EB%B6%84%ED%95%A0%EB%B2%95

Quad Tree

최대 4개의 노드
3D를 2D로 분할 관리
LOD(Level of Detail) 적용 가능
실외에서 주로 사용

Oct Tree

공간을 8개로 분해
우주같은 3차원 환경에서 주로 사용

K-d Tree

임의의 공간을 2개씩 나누는 구조
분포를 기준으로 나눈다고 했는데 아직은 잘 모르겠음

장점

렌더링 데이터 검출

다수의 Object를 모두 비교할 시간에 공간 단위로 clipping하여 빠른 비교 수행
GPU 최적화

충돌 데이터 검출

충돌은 Object의 근처에서만 발생
다수의 Object간 모두 비교 대신 같은 공간에서의 Object만 충돌 검출
CPU 최적화

Object

일반적으로 부피를 가지는 객체
Object가 어느 Node에 속하는지 결정해야 함

방법

완벽하게 포함되는 노드에 추가

Object를 완벽하게 포함하는 노드에 Object 추가
Node에 걸치는 경우 상위 노드에 추가
단, 경계선 상의 Object는 빠르게 처리되지 않음

걸치는 노드에 모두 추가

완벽하게 Object를 포함할 경우 하위 Node로 이동
경계를 걸치는 모든 Node에 Object 추가
단, 동일 Object를 여러번 Rendering하거나, 검출 과정이 필요

1번 방법 선택

LevelOrder 방식으로 Object를 추가할 Node 검색
PreOrder 방식은 불가능한가?
InOrder, PostOrder의 경우 불필요한 검색이 많이 소요될 수 있음