DXR(MicrosoftX Raytracing)의 활용이 점점 늘어나고 관심도 늘어가고 있다. DXR 자료는 점점 많아 지고 있는데, 그중에 BVH(Bounding Volume Hierarchy)라는 단어가 흔하게 등장한다. 레이트레이싱 세계에서는 이미 오래전부터 사용되던 구조인데, 래스터라이제이션 세계에서는 생소한 단어다.

여기서는 BVH를 위해 그 조상이 되는 KD Tree를 알아보고, 이어서 BVH가 무엇인지 간단히 알아본다.

가속 구조 (Acceleration Structure)

레이트레이싱의 기본은 광선(레이)이 충돌하는 지점의 삼각형과 삼각형 정보를 알아내는 것이다. 그 다음은 라이팅을 하든 AO를 하든 활용하는 사람 마음이다.

광선과 삼각형이 충돌하는 지점을 알아내는 것 중 가장 간단한 방법은 모든 삼각형을 다 검사해보고 그중 가장 가까운 지점에 대한 정보만을 사용하는 것이다.

물론 이렇게 하는 것은 느리다. 그렇기 때문에 공간 분할(spatial partitioning)을 이용해서 가속 구조를 만들어 사용한다. 대표적으로 사용하는 것이 KD Tree이다.

KD-Tree (k-dimensional Tree)

KD트리는 AABB(Axis-Aligned Bounding Box)를 이용해서 계층적으로 이진트리로 공간을 분할 하는 구조다. AABB라 함은, xyz 축에 수직이거나 평행한 면의 박스만 이용하겠다는 것이다. 이렇게 문제를 단순화하면 광선과 박스의 교차 검사를 굉장히 빠르게 할 수 있다.

위 그림에서는 번호 순서대로 박스와 교차 검사한다. 그리고 박스 안에 삼각형이 있으면 그 삼각형하고 교차 검사를 한다. 이러면 삼각형 교차 검사를 순서대로 할 수 있고, 불필요한 교차 검사는 생략할 수 있다. 이 그림에서는 3번 노란색 박스 안에 있는 삼각형들을 계산한다. 충돌하는 것이 없으므로 트리 탐색을 이어가고, 최종적으로 4번 검은색 박스에서 원하는 결과를 얻는다.

KD-Tree의 장점은 교차 검사 계산이 매우 빠르다는 것이다. 반면, 단점은 생성 시간이 제법 필요하다. 생성 시간은 다른 구조들도 마찬가지이긴 하지만, KD-Tree는 수정도 매우 오래 걸린다. 동적인 물체에 대한 여러 시도가 있었지만 동적인 것들에 대해서는 아래에서 이어서 설명할 BVH를 이용하는 것이 현 추세다.

BVH (Bounding Volume Hierarchy)

KD트리는 박스를 두 조각으로 나누고 그걸로 이진트리의 자식으로 사용한다. 이 방법으로는 내부 데이터가 변경되었을때 변경이 크다. 거의 전체를 다 재생성하는 만큼의 비용이 들때도 많다.

원이 위의 그림에서 아래그림처럼 이동했다고 해보자. 이 경우 왼쪽 박스가 수정되었으므로 오른쪽 박스도 수정되었고 이와 연관된 모든 박스가 다 수정되어야 한다. 업데이트를 해야하는 박스가 많아서 비용이 크다.

BVH도 KD트리처럼 자식이 둘인 것은 맞는데 특정 지점으로 가르지 않고 양쪽이 서로 다른 지점으로 나뉠 수 있다.

위와 같이 빨간색 박스가 수정이 되어도 녹색 박스는 굳이 수정될 필요가 없다.

따라서 어떤 수정사항이 생겨도 최소한으로만 수정을 할 수 있어서 업데이트가 매우 빠르다. 장점이 있으면 단점이 있는 법, KD트리 보다 실시간 성능이 떨어질 수 있다. 자식의 박스가 겹칠 수 있는 만큼 두 박스를 모두 체크해야하는 경우가 생겨서 성능이 떨어진다. 겹치는 박스가 많아지는걸 보고 BVH의 상태가 나빠진다고 하는데, 즉, 동적인 물체의 이동 영역이 넓을 수록 BVH 상태가 나빠질 수 있다. 예를 들어 애니메이션 되는 메시의 경우 사람이 걷거나 뛰는 경우는 크게 나빠지지 않는데, 꼬리나 날개가 달린 캐릭터가 다채로운 움직임을 보여줄 경우 BVH가 쉽게 나빠질 수 있다.

마무리

요약을 해보자.

  • KD트리는 렌더링 성능이 가장 좋지만 동적인 물체에 좋지 않다.
  • BVH는 성능은 좀 떨어지지만, 동적인 물체에 대응이 가능하다.
  • BVH는 KD트리를 포함한다고 볼 수 있다.

일반적으로는 BVH를 쓴다고 말하지만 정적 메시에 대해서는 내부적으로는 KD와 같거나 거의 흡사한 자료구조를 사용할 것이다. DXR에서 BVH를 생성할때는 동적인지 여부를 체크할 수 있다. 즉, 스태틱 메시는 KD트리를 쓸 것이고, 스켈레탈 메시는 BVH를 쓸 것이다. DXR은 이런 오브젝트들을 다시한번 상위로 BVH 트리로 감싸니 계층적으로 효율적으로 처리할 수 있다.

KD트리와 BVH을 이용한 레이트레이싱은 성능 향상을 위해 많은 발전을 이루었다. 여기의 설명이 그렇게 자세하진 않을 수 있는데, 알고리즘 자체가 많이 발전해왔기 때문에 자세하게 설명하자면 제법 길어서 매우 간략하게만 다뤘지만, 간단하게 어떤 방식으로 동작하는지만 알아도 좋을 것이다.

물론 DXR을 직접 구현하기 위해서 BVH를 직접 구현할 필요는 없다. 하지만 GPU가 알아서 다 해주는 래스터라이제이션도 직접 구현해보면 큰 도움이 되듯, 레이트레이싱과 BVH도 직접 구현해보면 큰 도움이 된다. 직접 구현해보지 않더라도 어떻게 동작하는지 알고리즘은 알고 있는 것도 큰 도움이 될 것이다. 좀 더 자세한 알고리즘을 위해서라면 참고문헌에 있는 Ingo Wald의 논문을 참고하면 좋다.

참고 문헌