3.Bounding Volume Hierarchies

이현기·2022년 8월 12일

RayTracing:The-Next-Week

목록 보기

3/9

주의 사항

이 글은 RayTracing:The Next week을 공부하며 작성한 글이다.

모든 사진, 글은 RayTracing:The Next week에서 가지고 왔다.

영어 해석, 이론적으로 틀린 내용이 존재할 경우가 매우 크다. (지적해주시면 감사합니다.)

글을 쓰는 능력이 매우 안좋으니 이해해주세요. 연습 중 입니다.

드디어 Overview에서 말한 이 책에서 말하는 가장 어려운 파트 중 한 가지인 BVH(Bounding Volume Hierarchies)를 공부해보자. 여기에서 사각형과 box를 추가도 해보고 hittable을 수정해서 기존의 Rendering 속도를 빠르게 만들어 준다고 한다.

기대가 됩니다.

Bounding Volume Hierarchies가 무엇일까?

Raytracing의 intersection은 Ray Tracing의 time-bottleneck의 주요한 원인이 된다. 왜냐하면 물체가 많아질 수록 Ray를 판별해야하는 물체가 많아져 계산이 물체의 수와 비례하여 많아진다. 하지만 위의 판별하는 계산은 같은 모델에 대해 매우 반복적인 연산이므로, Binary search의 성질의 logarithmic search를 만들수 있어야 한다. 우리는 같은 모델에서 매우 많은 Ray를 보내고 있기 때문에, 우리는 model들을 정렬을 할 수 있으며 그리고 각각의 Ray Intersection은 sublinear search가 될 수 있다. 흔한 두 가지의 분류 기준은 아래와 같다.
1. divide the space.
2. divide the objects.
책에서는 물체를 나누는 것을 훨씬 쉽고 대부분의 모델에서 실행하기도 빠르다고 설명하고 있다.

Binary Search $\to$ 이진 탐색이라고 자료구조 시간에 배웠던 개념인게 생각이 났다.

이런 BVH의 main Idea는?

BVH의 아이디어는 모든 객체를 완전하게 둘러싸고 있는 volume을 찾는 것이다. 예를 들어서 너가 10개 물체의 bounding sphere를 계산했다고 가정해보자. 만약 어떤 Ray가 bounding sphere를 만나지 못하게 된다면 우리는 10개의 Object와 Ray가 만날 수 없다는 것을 알 수 있다. 또는 어떤 Ray가 Bounding sphere를 만나게 된다면 Bounding sphere안에 10개의 Object 중 하나를 만날 수 있다는 것이 된다. 그래서 책에는 아래와 같이 algorithm을 설명하고 있다.

if (ray hits bounding object)
	return whether ray hits bounded objects
else 
	return false

여기서 우리가 중요하게 생각해야할 부분은 장면이나 volume을 나누지 않고 objects들을 하위 집합으로 나누고 있다는 것이다. 하지만 이런 bounding volume들은 겹칠 수 있는 가능성이 존재한다.

Hierarchies of Bounding Volumes 구성하는 법!

우리는 sub-linear 형태로 만들기 위해서는 bounding volume을 계층적(hierarchical)으로 만들어 주어야 한다. 예를 들어서, 아래의 사진과 같이 두 그룹의 objectse들이 존재한다고 하자.

위의 그림을 보면 red와 blue로 나누어진 것을 확인 할 수 있고 가장 크게 보라색으로 두 그룹을 감싼 것을 확인할 수 있다. 오른쪽 Tree를 보면 계층적으로 더 큰 set으로 구성된 것을 볼 수 있다.
그리고 주의할 점은 Tree에서 left와 right가 특정한 order가 있는 것이 아닌 단순히 보라색 Bounding volume안에 존재하기 때문에 Child node로 된 것이다.
책에서는 아래와 같이 code로 algorithm을 설명하고 있다.

if (hits purple) {
	hit0 = hits blue enclosed objects
    hit1 = hits red enclosed objects
    if (hit0 or hit1) {
    	return true and info of closer hit
    }
}
return false;

Axis-Aligned Bounding Boxes (AABBs)란?

우리는 앞에서 배웠던 모든 원리를 작용시키기 위해서 우리는 나쁘게 나누는 것 보다 좋게 나누는 방법을 찾아야 한다. 그리고 Bounding volume과 교차하는 방법도 찾아야 한다. Ray가 bounding volume과 교차하는 것은 매우 빠르게 이루어져야 한다. 그리고 Bounding volume은 최대한 이쁘고 compact해야 한다.

즉 object size와 거의 비슷하게 bounding이 되어야 한다.

연습으로 가장 많이 사용되는 모델은, 축에 정렬 된 box는 다른 대안들 보다 좋은 작업을 할 수 있다. 그러나 box말고 다른 특이한 design을 만나게 된다면 bounding volume의 모양을 다르게 선택할 수 있어야 한다.

이 책에서는 이제 axis-aligned bounding rectangular parallelepiped(평행 육면체)를 axis-aligned boudning box라고 말한다고 한다. 또는 AABB이다. 우리가 지금 배우는 제목과 동일하다.
모든 method가 AABB와 광선을 교차하는데 사용하고 싶은 모든 방법은 괜찮다. 그리고 우리가 알아야할 것은 그 Ray가 object를 쳤는지에 대한 여부를 알아야 한다. 마지막으로 우리가 그 hit point나 normal이 필요한지 또는 그 object가 우리의 display에 표시하고 싶은 object여서 필요한지 않한지도 알아야 한다.

많은 사람들은 "slab"이라는 method를 사용한다. 이것은 n차원을 가진 AABB가 단지 정렬된 n 축의 간격의 교차점이라는 것에 대한 관측을 기반으로 한다. 종종 "slabs"라고도 불린다. 여기서의 간격은 두 개의 endpoint사이를 뜻한다. 예시로 아래의 사진처럼 $y_1$ 과 $y_0$ 의 사이를 interval이라고 할 수 있다. 그래서 $x$ 도 y처럼 마찬가지로 간격을 정의를 해서 결과적으로 2D AABB로 나타낼 수 있다.

그러면 우리는 이제 Ray가 이 bounding volume을 쳤는지 알아봐야 한다. 즉, 이 간격에 Ray가 들어 왔는지를 살펴보자. 아래의 그림을 보자.

위의 사진을 봤을 때 $t_0, t_1$ 은 Ray의 parameter이고 $x_0, x_1$ 은 방금 말했던 AABB의 간격이라고 보면 된다. 이제 이 가저응ㄹ 바탕으로 3D로 생각을 해보자.

여기에서 $x_0, x_1$ 을 각각 그 점에 위치한 평면이라고 생각을 해보자. 우리는 그래서 Ray를 발사하면 이 평면에 Ray가 만난다고 하면 어떻게 생각할 수 있을까? 우리는 Ray Tracing:In one weeked에서 아래의 식을 $P(t)$ 로 배웠었다. 이걸 사용해보자.

P(t) = A + tb

위의 식에서 우리는 두 개의 식을 알아낼 수 있다.

x_0 = A_x + t_0 b_x \\ x_1 = A_x + t_1 b_x

위의 식을 말로 표현하자면 Ray가 발생했을 때 그때의 값이 $x_0, x_1$ 이라는 것이다. 그러면 이제 그 때의 Ray의 parameter인 t들을 알아낼 수 있다.

t_0 = \frac{x_0 - A_x}{b_x}

식은 한개만 적었지만 $t_1$ 도 비슷하게 구해낼 수 있다. 여기서 우리가 중요하게 보아야 할 것은 $t$ 이다. 예시로 아래의 그림의 상황에서 파란색과 녹색은 모두 interval안에 들어와야 생각할 수 있는 경우이다.

이 그림이 이해가 진짜 안되었다. 3D로 생각을 하지말고 2D로 보게 된다면 파란색 간격 사이에서 ray가 지나갈때 파란색으로 색칠된 것을 확인할 수 있고 녹색도 마찬가지 이다.

그러면 어떻게 Ray Intersection을 AABB와 적용을 할까?

책에서는 바로 pseudocode로 설명하고 있다.

compute(tx0, tx1)
compute(ty0, ty1)
return overlap?((tx0, tx1), (ty0, ty1))

위의 코드에서 설명하는 것은 2D를 기준으로 하는 것이다. 그래서 x와 y만 검사를 하는 것이고 그 interval안에 들어오는 것을 check하는 것이다. 그러면 이제 3D에서는 어떻게 하는지 보자. 간단하게 3D의 z축을 추가해주면 끝이다.

compute(tx0, tx1)
compute(ty0, ty1)
compute(tz0, tz1)
return overlap?((tx0, tx1), (ty0, ty1), (tz0, tz1))

하지만 위의 algorithm에서 우리는 몇 가지의 주의사항이 존재한다.

이쁘지 않게 만든다고 한다. 주의하자.

첫번째로, 만약 계산된 x가 음수라고 가정을 해보자. 그렇게 된다면 X의 interval이 뒤집혀 계산이 된다. 예로 (7, 3)

간격을 구할 때 3 - 7 로 계산이 된다면 -4가 나오기 때문이다.

두번째로, 나눗셈을 할 때 그것은 우리에게 inf를 줄 수도 있다. 그리고 만약 Ray의 origin이 boundary중 하나에만 존재하게 된다면 우리는 NaN 값을 얻게 된다.

위의 주의사항을 현재 많은 Ray Tracing AABB에서는 처리할 수 있는 방법이 제공되어 사용하고 있다. 하지만 이 책에서는 최대한 간단하게 만드는 것을 목표로 두고 있는 것 같다.
그러면 이제 interval을 계산해보자.

t_{x0} = \frac{x_0 - A_x}{b_x} \\ t_{x1} = \frac{x_1 - A_x}{b_x}

아까 배웠던 식을 가지고 왔다. 이걸로 각 $t$ 에 대한 간격을 구할 수 있다. 하지만 우리는 예외를 처리해주어야 한다. 단순하게 t의 값들끼리 빼버리게 된다면 오류가 발생한다. 왜냐하면 $x_0 - A_x =0$ 가 될 수도 있고 아니면 $b_x = 0$ 이면 에러가 나버린다. 또 위에서 음수를 처리해주어야 하기 때문에 아래의 식으로 보완할 수 있다.

t_{x0} = min(\frac{x_0 - A_x}{b_x}, \frac{x_1 - A_x}{b_x}) \\ t_{x1} = max(\frac{x_0 - A_x}{b_x}, \frac{x_1 - A_x}{b_x})

각 계산된 식에서 우리는 min, max를 이용해서 예외를 어느 정도 처리할 수 있지만 $b_x = 0$ 인 상황은 아직 처리하지 못한다. 하지만 책에서는 다시 공부할 것이라고 하고 다음 chapter로 넘어간다고 한다.

이제 우리는 위에서 구한 interval을 가지고 overlap을 구해보자. 아래는 책에서 표시한 algorithm이다. 음수로 인해서 간격이 뒤집히지 않았다고 가정을 한다.

bool overlap(d, D, e, E, f, F) {
	f = max(d, e)
    F = min(D, E)
    return (f < F)
}

주변에 NaN이 있다면, 비교는 false를 반환하므로 grazing case에 관심이 있다면 bounding box에 padding이 있는지 확인해야 한다.

grazing case가 무엇일까? 다른 경우의 수? 방목현상이란?

이론적인 설명은 여기서 마치고 이제 코드를 작성하게 된다.

#ifndef AABB_H
...
class aabb {
	...
    bool hit(const ray& r, double t_min, double t_max) const {
    	for (int a=0; a < 3; a++) {
            ...
            t_min = fmax(t0, t_min);
            t_max = fmin(t1, t_max);
            if (t_max <= t_min)
                return false;
        }
    	return true;
};

위의 코드에서 3축을 계산해서 각 축에 대한 interval을 구하게 된다. 위의 식에서 minimum과 maximum이 가지고 있는 x, y, z를 가지고 ray의 origin을 이용하여 interval을 구하게 된다. 그러면 이제 예시로 첫 번째, x축을 기준으로 해보자. 각 x를 이용하여 그때의 t0와 t1을 구하게 되고 그 t를 비교하면서 범위를 만족하는 지 check를 하는데 여기에서 나온 t_max가 t_min보다 작거나 같게 된다면 Ray가 범위에 들어오지 못한다는 경우가 만족하기 때문에 false를 return하게 된다. 즉, 범위의 부호가 음수가 된다면 hit를 하지 못한 것이다.

역시 어렵다.. 평소 Ray Tracing에서 가장 많이 사용되는 기법이라고 한다. 더 공부해보자..

이현기

안녕하세요!

이전 포스트

2. Motion Blur

다음 포스트