[Computer Graphics] Ray-tracing

시작하며

• 이번주제는 Ray-tracing 물리적인 계산을 통해, 사실적인 빛의 표현을 구현하는 것이다. 교수님이 이번학기 끝날즈음에 강의를 하신다셨는데 마지막 주제로 강의를 해주셨다.
• 넷마블2차를 보기전에 강의를 들었는데 대답하는데 꽤 도움이 되었다. 다행..
• 2학기때 남은 학점을 좀 쓸모있게 써보자는 생각으로 쉽게 학점만 채울 수 있는 강의를 선택하지 않고 고급컴퓨터그래픽스, 컴퓨테이션이론을 선택하여 듣게 되었는데,그러기를 잘한것 같다. 두 과목모두 취업준비를 하며 큰 도움이 되고있다.
• 쉬운 길보다는 배우며 살자는 나의 다짐을 다시 확신시켜준 한 학기였던것 같다.
• 많은 일이 있었던 이번학기도 이번주 목요일(기말시험)이면 끝. 유종의 미를 거두자
• 그러니까.. Ray-tracing방법과 실시간 Ray-tracing방법을 알아보자

Physically based rendering

Local illumination

• 관찰기반의 illumination
• 모든빛을 계산하지 않는다.
• local의 예인 phong shading

Physically based illumination

• 물리법칙기반의 illumination
• 정확하나 복잡하다
• 사진으로 찍은듯 하기에 Photorealistic rendering이라고 칭한다.
• 주변환경을 반사, 주위 물체로 인한 그림자 등을 표현할 수 있다.
• 재질의 표현이 가능하여, 대리석과 같은 물체의 투과와 산란에 대한 계산이 진행된다.

계산을 위해 무엇이 필요한가

• 광원, 물체, 눈
• 광원에서 나오는 빛, 물체에서 반사된 빛, 눈에 들어오는 빛 모두 무한대임. 너무많아

광원

• 점광원: 모든방향으로 중앙에서 나옴(현실에서 존재하지 않음)
• 면광원: 형광등, 모니터 화면과 같은 면에서 나오는 빛
• 방향광원: 태양빛과 같이 방향을 가진 광원

물체

• 모양: 모양에 따라 수직벡터가 다르고, 반사의 정도가 다름
• 재질: 빛의색이 변하는 정도.

카메라(눈)

• 렌즈의 특성에 따라 다르게 보여줄수도 있음

사실 Ray-tracing은 비현실적이다

• 광원에서 나온 모든 빛이 물체와 엄청나게 반사되어서 눈으로 들어온 값을 모두 계산하는것은.. 무리..
• 그래서 사용하는 방법이 Ray Casting

Ray-casting

• Ray-tracing과 반대로 화면에서부터 시작하여 광원으로 간다.
• 화면의 pixel마다 100만개 이상의 광원을 쏜다
• Rendering Equation을 계산하면, x'부터 x까지의 빛의 양을 계산할 수 있다.
• 예를들면, x까지 오는 빛을 계산하기 위해, x'에서 오는 빛의 양을 계산하려면, 공기의 매질에 따라 거리제곱의 반비례하여 계산할 수 있다. 그러려면 x'의 빛의 양이 필요한데, 이 빛의 양을 계산하려면, 다른곳(x")에서 x'까지 오는 빛의 양을 계산하여 모두 더해줘야한다.
• 이 꼬리의 꼬리를 무는 재귀적인 계산을 몇번까지 더 할것인가에 따라 퀄리티가 달라진다.

• 이 계산은 광원의 개수, 종류에 따라 달라짐. 따라서 적절히 샘플링하는것이 중요.

Surface Scattering

두가지 반사가 있다.
1. BRDP: 표면에서 모두 반사되는 것
2. BSDF: BRDP(표면반사) + BRDF(투과되는 빛)
3. BDDRDF: sub surface scattering
BSDF는 계산하기 어렵기 때문에, 모든방향에서 어떤 모습을 다 캡쳐해두고 사용하는 방식을 많이 사용한다고 한다.

Ray Propagation

• 물체와의 교점을 어떻게 찾고, 수많은 ray를 어떻게 줄일까?

Lighting

어떻게 풀까?
1. Radiosity: 빛이 나가는 경로를 면단위로 잘라서 보기. 면이 움직이지 않고, 광원이 고정되어있을경우 적합.
2. Ray tracing: Monte Carlo방법, 랜덤함 방법으로 많은 ray를 랜덤하게 쏜다.

Cornell Box를 이용해서 test해보자면,

1. Surface Color
   각 면의 색만을 표시, 하나의 물체는 색이 같다면 같은색을 가진다.
2. Diffuse Reflection
   정반사만을 고려하면, 물체에서 반사되어 광원으로 도착하지 않는다면, 그림자색. 도착하면, 거리의제곱에 반비례하여 색이 정해진다.
3. Shadows
   이제 다른 물체를 고려한다. 다른물체에 닿는다면, 바로 그림자색. 광원에 도착하면 거리제곱에 반비례한 색 결정
4. Soft Shadows
   점광원에서 면광원으로 교체하면 구현가능. 원래 점광원이었다면 하나의 목적지에 다다르지 못하면 그림자가 되는데, 면광원일경우 목적지의 범위가 넓어지므로, 그림자의 일부는 물체의 색과 그림자색의 중간으로 표시되며 부드러운 그림자가 표현가능하다.
5. Indirect Illumination
   Radiosity방법을 사용. 면을 일정하게 나눠서 반사를함.
   물체가 움직인다면, 면을 다시 나눠야하기때문에 비효율적
6. Glossy Materials
   Caustics: 빛이 물체의 내부로 투과되고 굴절되어 생기는 밝은 부분
7. Turing Test
   인공지능에서만 보던 튜링테스트를 여기서?
   실제 Cornell Box를 구성하여 찍은 사진과 렌더링된 결과를 비교하여 뭐가 실제인지 비교해보는 테스트

Materials

• Material 만들기
  ambient, diffuse, specular, shine을 조절하여 여러 재질을 만들 수 있음
  매트함, 반질반질함, 토기의 느낌 모두 가능
• self-shadowing
  이미지를 그냥 붙인 Material보다 self-shadow가 들어간 texture는 shadow가 명확하고 울퉁불퉁한 표면의 표현이 더 잘 나타난다.
• Translucency
  불투명한 표면이면, 일부가 내부로 투과되며, 그림자가 생기는 부분이 부분적으로 밝아지며 부드럽게 표현됨
• 부식효과
  비를 맞으며 대리석의 색이 변하거나, 동이 초록색으로 녹이스는것을 시뮬레이션하기도함
• Face
  부분마다 특상이 다름(맨질하거나, 울퉁불퉁하거나...)
• Hair
  가닥수가 많으면 시뮬레이션이 각각 어려우니, 묶음 단위로 표현하곤한
• Somke
  volume으로 표현하고, 빛이 들어온 경우 흡수또는 반사하는 특성을 이용하여 시뮬레이션
• 구름, 기상효과(비, 눈)

Ray Tracing

Classic Ray Tracing

• 빛의 특성을 이렇게 정의합니다.

1. 빛은 직선으로 움직인다.
2. 빛의 만남으로 방해가 생기지 않는다
3. 광원에서 눈으로 온다

간단한 구현(local)

• 하나의 픽셀당 하나의 ray 발생
• 처음 만나는 점이 광원이라면 광원
• 도중에 만나는 물체가 없다면, 물체색
• 도중에 만나는 물체가 있다면, 그림자색
  => 그림자는 생기는데, soft shadow없음, 간접광없음, 면광원 안됨

더 나은 구현(Reculsive)

• 재귀적인 방법을 이용하여, 굴절(Refraction), 반사(Reflection) 계산
• Reculsive의 횟수에 따라 달라지는데,
  0. 0번 반사시(ray보내서 광원 아니면 그림자색) 모두 그림자색
  1. 1번 반사시, 다른 물체 하나를 거쳐 보여지는 모습을 볼 수 있음
  2. 2번 반사시, 2번거쳐온 결과를 볼 수 있음
  3. 5번이 가장 적절하다고함
  4. 5번과 별다른 차이가 없음 약간의 빛의 세기 차이가 보이긴함

Ray-tracing Architecture

• 미안하다 이거보여주려고 어그로 끌었다. 라고 하시는것 같았던 교수님.

1. Sampler를 통해 광원의 위치 1000개정도로 축소한다.
2. Camera에서 Ray를 생성한다(픽셀당 약 100만개)
3. 교점을 구한다. 반사된 빛을 계산한다.(발산)
4. 반사된 빛을 합하여 반사되는 색을 구한다(수렴)
5. Film의 특성을 적용하기도 한다.
6. 3번에서 광원의 위치를 만나게 되거나 배경으로 나아가면 결과값을 출력한다.
   => 이러한 구조를 가지는데, Sample은 어떻게하고, 교점은 어떻게 쉽게 구할까?
   => 이걸 실시간으로 하려면 어떻게 해야할까? 라는 고민을 가지게 되는것.

원래대로 하면?

• 물체의 개수 * 빛의 개수 만큼의 계산이 필요함.

Primitives

• 형상, 재질과, 방출하는 빛
• 이걸 다 어떻게 줄일까?

줄이는 방법?

• Faster Intersection: 빠르게 교점을 구해야해
• Fewer Rays: 빛을 줄여야해. 너무많아
• Generalized Rays: 일반화한 빛(Beam, Cone, Pencil tracing)

Faster Intersection

1. 가장 가까운 교점을 찾는 알고리즘이 있음.
   씬의 모든 물체에 대해 교점이 생기는지 계산해야함

2. Partition the objects
   Bounding volume -묶어-> Bounding volume hierarchies(BVH)

3. Partition the space
   Flat: Uniform grid(균일하게 나눠서 ray와 만나는 공간만 계산)
   Hierarchical: Octree, Kd-Tree(물체가 있는 곳만 나누기)

하나씩 설명

Bounding Volume

물체를 둘러싸는 가장 단순한 primitive생성
ray가 Bounding Volume과 만나면, 내부를 검사해봄. 만나지않으면 pass~

1. Bounding Sphere
   원점을 잘 선택해야함. 잘 선택해서 반지름을 최소화하자.
   장점: 교점을 구하기가 매우 쉬움(sphere방정식 이용), 물체가 회전해도 바뀌지않음, 만들기 빠름
   단점: 빈부분이 너무 많아. tight하지 못함
   • Central을 잘 잡는 법: 가까운것들끼리 sphere을 만들고 가까운 sphere를 merge해 나가면 어느새 bounding sphere완성.
2. Axis-Aligned Bounding Box(AABB)
   x, y 또는 z축이 있는 box. 물체에 가장 tight한 box 만들기
   • ray와 교점찾기: 각 축에 대해 near, far을 가져서 near, near, far, far인경우, 교점이 있는것
   • 장점: BS에 비해 단순하고 교점찾는것도 쉽다.
   • 단점: 물체가 회전할시 변경됨, 아직 빈공간이 많음(BS보다는 적음)
3. Oriented Bounding Box(OBB)
   회전시 같이 돌아가는 AABB
   가장 적합한 Bounding Box를 만들어둔다.
   각 점에 대해 중심점을 찾는 방법도 있지만, 물체의 중심선을 찾아 구하는 방법이 단순하여 많이사용된다함.
   • 내부에 sphere을 만들어서 그 중심을 이으면 중심선 완성. 각 sphere을 감싸는 BB를 만들고 그걸 다 감싸는 BB를 만들면 완성
   • ray와 교점찾기: AABB와 비슷하나, x와 y축이 아니라, 일반 직선의 방정식을 풀면됨
   • 장점: AABB보다 tight. 정확한 구현은 어려우나, 대강구해도 AABB보다 더 나은 성능
   • 단점: 쉽지만 교점구하는것이 AABB보다 복잡. OBB를 구하기도 좀 어렵. 단, 한번만 구하면 됨
4. Bounding Volume Hierarchies(BVH)
   • BV로 이뤄진 Tree. BV의 개수가 많은경우 BVH가 필요함
   • Bottom up: 물체하나씩 만들고 가까운것끼리 묶는방식. 빨리 가능
   • Top down: 전체를 묶고 나눠가는 방식. 물체가 많고 겹친부분이 많으면 어렵. 듬성듬성일때 좋음
     OBB를 만들 때, Top down으로 쪼개서 만들기도함
   • 언제만들어?: 물체단위로 만들고, 움직인다면 새로 만들어야함.
   • 전처리시간에: BVH를 만들어놓기
   • 실시간으로: 움직이면 BVH를 수정해
     => 실시간으로 BVH를 어떻게 수정하고 움직이며 유지할것인지가 문제임.
5. crush된 BV찾기
   • root는 전체를 감싸는 BV. ray와 겹치면 자식노드를 탐색
   • BFS,DFS중 DFS를 사용. 빨리 끝낼 수 있다.
   • 물체와의 교점이 BV의 교점보다 앞에있으면, 더이상 계산안함(BV가 겹치지 않는 경우)
   • BV가 너무 많거나 겹치는 경우 잘 안됨.

Partition the space

1. Uniform Grid
   • x, y, z개로 균일하게 나눔.
   • grid의 size가 중요함. 너무크면 의미없음. 너무 작으면 빈 cell이 많아져.
   • 그래서 BV의 길이의 평균으로 cell을 잡는것이 좋다고함
   • 각 cell마다 list가 들어감. 물체1 들어있다. 물체2 들어있다 이런식으로 쭉 있음
   • ray가 지나는 cell만 검사하면됨. cell구할 때 x, y, z축을 기울기를 이용해서 움직여보면 됨
   • 각 cell을 검사할 때 물체에 대한 검사를 하면서 물체의 교점이 있는지 검사. 검사후에는 검사가 끝난 물체라는 표시를 bool자료형으로 해주곤한다함.
   • 장점: 빠르게 만들기가능. 메모리 효과적인 분포. 탐색이 쉬움
   • 단점: 빈곳이 많음. cell size를 구하기 어려움. No adaptativity(물체가 없는곳도 잘 나눠버림)
2. Viewing Frustum
   • grid를 전체에 대해 나누는게 아니라 Viwing Frustum을 나눔.
3. Optimizing the Uniform Grid
   • Uniform grid는 물체가 없는곳도 촘촘하게 나눠버려서 문제다. 이를 보완하기위해 물체가있는곳만 나눠보려 한다.
   1. Rectilinear Grid: 물체가 있는 x, y, z만 촘촘하게 나누기
   2. Embedded Grid: 물체가있는 grid만 촘촘하게 나누기
   3. Octree: 물체가 있는 부분만 촘촘하게 나누기
4. Octree
   • 물체가 있다면, 깍두기 썰듯 8개씩 나누기.
   • Top down 방식을 사용. 물체가 둘 있으면 나눠!. 하나면 더이상 나누지 않음
   • 단, 물체가 없는부분도 나누어진다는 단점이 있기도함
   • Ray Traversal: 지나가는 node의 child를 탐색. 겹치지 않으면 다음. 다음. 겹치면 그 child로 또 내려감. Reculsive하다.
   • 장점: Adaptivity, 메모리 효율
   • 단점: Ray Traversal이 비교적 복잡, 나눠가는게 정해져있어서 비효율, 메모리가 순차적이 아니라 흩어짐
5. K-d Tree
   • Hyperplane을 이용하여, 일정하게 나눠야한다는 단점 보완
   • 일단 중앙을 나누고, 각 부분을 적절히 나누고, 나누고, 나눠서 cell당 물체가 하나씩 있도록하기
   • Ray Traversal: 찾아내는 과정이 조금 더 복잡함. Reculsive
   • Non-Reculsive Traversal: backtracking을 하지않고, stack과 배열메모리를 사용한 for loop를 통해 친척노드를 찾아가는 방식. Reculsive를 쓸수없는 shader에서 유용함
   • 장점: Adaptivity(물체가 많으면 촘촘하게), 빠른 ray Traversal
   • 단점: 만드는과정이 복잡함.

얼마나 효과가 있는가

• 속도: BVH는 O(nlogn)시간. (balanced Tree이기 때문) uniform grid는 O(n)시간
• 메모리: 트리는 O(n), uniform grid는 O(x* y*z)
• 빠른계산: 계층구조인경우 O(logn)으로 탐색가능. O(1)상수시간에 접근도 가능
• 물체가 계속 움직여서 계층구조가 계속 변화한다? => BVH 안좋음
• 물체가 고정되어있다? => BVH가 좋음
• 물체가 많다? Octree사용
• 물체가 적다? Bounding Volume Hierarchies사용