How to create awesom accelerators: The Surface Area Heuristic
Motivation
우리는 다양한 컴퓨터 과학 주제들을 위해 가속 자료구조를 쓴다. 예시로, 가장 인접한 이웃 searches or 다 차원의 key queries를 수행하기 위해 kd-tree를 사용한다. ray tracing 프로그램을 위한 accelerators는 잠재성이 있는 ray-triangle intersections의 빠른 선택을 가능하게 한다. 그러나 이것은 왜 필수적인가? brute-force 솔루션은 어떤가?
다음의 예제를 고려해보자 : 우리는 100만개의 삼각형을 가진 많은 폴리곤 메쉬를 렌더링하고 싶어. 게다가, 우리는 그것을 Full-HD (1920 x 1080 픽셀)에 렌더링하고 싶어. accelerators없이, 우리는 각 ray에 대해 백만 번의 교차테스트를 연산해야만 한다. 그래서 만약 우리가 픽셀 당 한 ray만을 쏜다면, 우리는 200조 개의 교차 테스트를 해야한다. 그리고 이것은 reflections에 대한 rays를 심지어 포함하지 않는다.
휴. 그냥 말하자, 많은 연산량이라고!
가속 구조를 도입하여, 우리는 탐색 공간을 더 작은 부분으로 자를 수 있따. 이것은 이진 탐색 트리에서의 탐색과 같다.
그것을 좀 더 격식이 있는 방식으로 표현하자면: n이 가능한 교차 개수라고 하자. n은 복잡한 scenes, meshes, 그리고 높은 품질 설정을 고려할 때 몇 조에 다다른다. 잘 구성된 accelerators는 그러고나서 naive O(n) ray tracing algorithm을 O(log n)의 성능으로 개선시킬 수 있따. 이것은 상호작용할 수 있는 ray tracing을 가능하게 할 수 있다. 왜? 교차 테스트는 복잡한 scenes에서 성능 부담의 95%를 차지하기 때문이다.
우리는 결론지을 수 있다: 똑똑한 자료구조를 만드는 것은 우리의 알고리즘 성능을 급등시킬 것이다라고.
A Bit of History
accelerator creation에 접근하는데 두 가지 흔한 방식들이 있다. 우리는 그 첫 번째 방식을 object subdivision이라고 부른다. 그것은 오브젝트들을 BVH가 수행되는 방식처럼 함께 묶어서 작동한다. 우리는 두 번째 방식을 space subdivision이라고 부른다. 이름이 암시하듯이, 그것은 공간을 부분 공간으로 나누고, 포함된 오브젝트들을 이러한 공간들로 할당한다. 그러한 파티셔닝 주제에 대한 한 구체적인 예제는 kd-tree이다.
분할정복의 정신이 있는 그 알고리즘들은 상대적으로 간단하다. 그러나 각 level에서 한 노드의 가장 좋은 split position을 결정한 어떠한 실용적인 방법이 현재 없다. 그래서 우리는 우리가 어떤 오브젝트들을 그룹지어야 하는지 또는 우리가 공간을 두 개의 다음 노드들로 가장 좋은 성능을 위해 분할할지를 모른다.
그 첫 번째 컴퓨터 그래픽 선구자들은 수동 방식으로 accelerator 내에서 오브젝트들을 선택해야만 했다. 첫 번쨰 automatic creations은 노드들이 중간에서 분리되도록 했다. 다른 방법들은 미리 정의된 tree or hierarchy depth에 도달할 때 subdivision을 중지했었다. 이러한 접근법들은 scene structure에 적응되지 않기 때문에, 그것들은 많은 scenes에서 실패한다. 다른 불확실성은 빌드 속도와 split axis의 선택을 포함한다.
이러한 것들은 그 연구 community가 한 최적의 accelerator를 만드는 것이 NP-hard problem이라고 가정하는 이유들이다. 그래서 우리는 heuristics 또는 cost models로 빠져들어야 한다. 그것과 함께, 우리는 합리적인 성능을 가진 정교한 구조를 구성할 수 있다. Surface Area Heuristic (SAH)가 그 구조원이다.
SAH Concept
우리가 격식이 있는 설명에 들어가기 전에, SAH가 하련느 것을 직관적으로 이해하려 하자. 그 SAH는 많은 삼각형을 가진 작은 노드들에 보상을 준다, 반면에 적은 삼각형을 가진 큰 노드들을 피한다. 다음의 이미지를 고려하자. split position (magenta line)의 무슨 선택이 최상일지를 생각해보자.
너도 추측했듯이, 세 번째 것이다. 너가 맞혔다.
그 첫 번째 이미지는 한 노드를 중간에서 나눈 결과이다. 이것은 괜찮은 것처럼 보이지만, 그렇게 너무 나쁘지 않다. 그러나 ray가 오른쪽 child node를 뚫을 큰 가능성이 있다. 대신에, 그것을 실제로 50:50 상황이다. 만약 우리가 균일하게 분산되고 방향이 있는 rays를 가정한다면, 매초 ray는 거의 모든 삼각형과 교차 테스트를 수행할 필요가 있을 것이다. 매우 기대할만 하지 않다.
두 번째 이미지는 심지어 악화된 상황을 보여준다. median에서 그 노드를 나누는 것은 모든 존재하는 삼각형들의 절반 이상에 대해 한 테스트를 요구하는 두 영역을 만들어냈다.
마지막 이미지는 최적화된 솔루션을 보여준다. SAH는 가능한한 꽉 맞는 대부분의 삼각형에 대한 넓이를 선택한다. 또한, 그것은 그 "값 싼" 왼쪽 노드의 surface area를 증가시켜서 오직 가능한 한 많은 한 단일 삼각형을 테스트 해야 하는 가능성을 보여준다.
SAH Formula
다음 섹션에서, 우리는 SAH의 formal description을 볼 것이다. 나를 따라와라!
MacDonald and Booth가 SAH를 제안했었다. 그것은 node 마다 ㅣ준으로 정의된 split position의 비용을 예측한다. 그 모델은 다음곽 ㅏㅌ이 주장한다:
- C(A, B)는 한 node를 volumes A and B로 분리하는 비용이다.
- t_traversal은 한 내부 노드를 지나는 시간이다.
- p_A와 p_B는 그 ray가 volumes A와 B를 통과할 확률이다.
- N_A와 N_B는 volumes A와 B에 있는 삼각형의 개수이다.
- a_i and b_i는 volumes A와 B에 있는 i번째 삼각형이다.
- t_intersect는 one ray-triangle intersection에 대한 비용이다.
우리는 p_A와 p_B를 다음으로 연산할 수 있다:
- S_C와 S_P는 volumes C와 P의 surface areas이다 (우리는 간단히 한 노드의 모든 sides를 합하여 한 node의 surface area를 연산할 수 있다)
- p(C|P)는 P를 지나가는 한 random ray가 C를 또한 지날 확률이고, C가 다른 convex volume P안에서 convex volume이라고 주어진다고 가정한다.
이러한 정의들은 책 Physically-based Rendering에서 취해진다.
휴. 잠시 좀 더 들어가보자.
이 공식으로, SAH는 한 RAY에 뚫려진 가능성이 높지 않은 tight boxes안에 있는 많은 삼각형들에게 보상을 준다.
우리는 SAH를 다양한 split positions에 대해 연산할 수 있다. 그러고나서, 우리는 가장 낮은 비용을 가진 것을 선택한다. 우리는 삼각형 bounds를 고려하여 가능한 split positions를 받을 수 있다. 또 다른 방법은 binning이다. 그것은 한 축에 대해 선형으로 분산된 위치의 어떤 양을 정의한다.
SAH에 대한 이후의 확장은 텅빈 노드들에 대한 가능한 BONUS를 포함한다. 또한, SAH 가정에 대한 개선점들이 있다, 예를들어 ray가 scene에서 균일하게 분산된다든지.
Back to the Drawing Board
우리는 정식적인 세부사항을 알았으니, 우리의 이전 예제를 다시 고려하자. 우리는 왜 세 번째 옵션이 SAH에 의해서 정말로 가장 좋은 선택인지를 보여줄 것이다. 이 방식으로, 우리는 SAH에 대한 더 좋은 이해를 얻을 것이다.
cost t_traversal = 1, t_intersect = 2라고 가정하자. 그러고나서 우리는 다음을 얻게 된다:
SAH에 따라, 그 알고리즘은 그러고나서 그 세 번째 split position을 고른다, 왜냐하면 그것이 가장 낮은 비용을 가지기 떄문이다.
다음 그림은 heat map visualization을 보여준다. 그것은 traversed nodes의 수와 ray-triangle intersection tests의 개수에 의존하여 한 메쉬를 색칠한다.
Conclusion
잘 구성된 가속 자료구조는 상호작용 가능한 레이 트레이싱 프로그램에 중요하다. 커뮤니티는 최적의 accelerator를 구성하는 것이 NP-hard 문제라고 가정한다. 따라서, heuristics or cost models이 합리적인 시간에 높은 품질의 accelerators를 구성하는데 필수적이다. 이 분야에서 가장 저명한 모델이 SAH이다. 그것은 많은 인접한 삼각형들의 넓이를 최소화하려고 하고, 더 작은 삼각형 그룹의 넓이를 최대화 하려고 한다. 이것은 ray-triangle intersection tests의 확률을 줄인다.
긴 시간 동안, 나는 adaptive 방식으로 accelerators를 어떻게 만드는지 이해하지 않았다. 너가 이 생각을 이해하도록 도울 수 있다는 것을 알게 됐고 희망할 수 있어서 행복했다. 만약 너가 레이 트레이싱과 accleration structures에 대해 좀 더 많은ㅇ 것을 찾길 열망한다면, Physically Based Rendering by Pharr et al을 ㅘㄱ인해라. 그것은 많은 레이 트레이싱을 처리하는 훌륭한 작품이다, acceleration structures를 포함하여. 이 자료의 끝에서, 너는 내가 이 자료에서 사용한 레퍼런스의 리스트를 발견할 것이다.
~
댓글 없음:
댓글 쓰기