[Article] Review and Comparative Study of Ray Traversal Algorithms on A Modern GPU Architecture

by

본 논문은 WSCG 2014 (홈페이지)에서 공개된 논문이다. 현재 진행하고 있는 과제와 관련되어서 읽고 정리하였다.

Motivation

Ray tracing은 light(빛) 또는 wave(전파)의 진행방향을 파악하는 기술이다. Ray tracing은 보통 screen에 object를 출력 할 때 많이 사용된다. 빛의 시작점 (보통 태양) 등에서 light (ray)가 진행되는 방향을 파악하고 현재 보이는 screen에 총 도달하는 ray의 개수를 파악하여 밝기와 색상을 결정하는 방법이 ray tracing 기술이다 (현재 읽으면서 동작 원리를 공부하는 중인데 대부분이 수학적인 부분이라 이해하기가 조금 어려운 면이 많다). 본 논문에서는 언급하지 않았지만, 빛의 진행 방향을 파악하는 연구와 함께 통신의 wave의 진행방향을 파악하기 위해서 ray tracing 기술을 사용한다. 보통 propagation 모델링이라고도 이야기한다. 그림 1은 그래픽의 ray tracing 기술의 예제이다. 그림 2는 wave의 진행방향을 모델링 하는 ray tracing 기술이다.

ns_attach_image_8231481090583795그림 1: 그래픽의 Ray Tracing 기술

ns_attach_image_8351481090638910그림 2: Wave의 진행방향을 모델링 하는 ray tracing 기술

본 논문에서는 GPU를 사용하여 다양한 ray tracing 방법의 성능을 비교하였다. 총 아래의 총 6가지 방법을 비교하였다. 각 방법은 ray와 object(보통 triangle임)의 intersection을 최소화하여 ray tracing의 전체 성능을 올리는 방법이다. 가장 기본인 Brute-Force Approach의 경우 각 ray를 모든 object와 비교하여 intersection이 발생하는지를 확인한다. 이러한 방법은 object (triangle)의 개수가 늘어날 경우 계산 시간이 급격히 늘어난다 (linearly). 다른 방법들은 아래에 설명하였다.

  1. Brute-Force Approach
  2. Bounding Volume Hierarchy (BVH)
  3. Octree (or Quad-Tree)
  4. Uniform Grid
  5. KD-Tree
  6. Bounding Interval Hierarchy (BIH)

Brute-Force Approach

앞서 설명한 바와 같이 각 ray를 모든 object와 비교하여 intersection이 발생하는지를 확인한다. 보통 수십, 수백만 개의 ray를 생성한다. 이러한 방법은 object (triangle)의 개수가 늘어날 경우 계산 시간이 급격히 늘어난다 (linearly).

Acceleration Structures (AS)

ns_attach_image_8581481093045603그림 3: 논문에서 언급한 5가지 AS

Brute-Force Approach와 달리 ray와 관계가 없는 object (triangle)을 제거하여 성능을 올리는 방법을 AS라고 한다. 본 논문에서는 크게 아래의 5가지 방법을 설명하였다. 그림 3은 아래의 5가지 방법을 간략하게 표현한 그림이다.

  • Bounding Volume Hierarchy (BVH)

가장 오래된 방법론 중의 하나이다. 그림 1 (BVH)와 같이 disjoint set으로 tree를 나누는 형태이다. 각 node의 triangle 개수는 volume에 따라 달라진다 (each internal node stores a tight bounding volume that encloses all primitives it contains). Ray intersection을 확인하기 위해 먼저 ray와 각 node의 volume과 intersection 여부를 테스트한다. 만약 intersection이 발생하면 node의 모든 triangle과 intersection 여부를 다시 확인한다. 만약 그 해당 노드에서 triangle의 intersection이 발생하지 않으면 다른 node는 무시한다.

  • Octree (or Quad-Tree)

공간을 8개로 나누어서 tree를 만드는 형태를 의미한다. 그림 1 (Quad-Tree)는 총 4개의 공간으로 나누었다 (2D라서 8개의 공간으로 나눌 수가 없다). 각 tree의 node는 해당 공간에 포함된 triangle을 모두 child로 가지고 있다. Search 하는 방법은 BVH와 비슷한 것 같다 (논문에 상세히 언급되어 있지 않다. 다른 논문을 검색해볼 필요가 있다).

  • Uniform Grid

그림 1 (Uniform Grid)와 같이 동일한 크기 공간으로 분배하는 형태이다. 각 공간에 있는 모든 triangle을 검사하는 형태인 것 같다 (이 이상 논문에 언급되어 있지 않다. 다른 논문을 찾아 공부해볼 필요가 있다).

  • KD-Tree

연구자들이 가장 많이 사용하는 방법이다. Axis-aligned plane을 기준으로 공간을 분배한다고 한다 (그림 3 참조) (이게 무슨 말인지 잘 모르겠다. 인터넷을 찾아보면 X, Y 축 등을 기준으로 공간을 분배하는 방법인 것 같다. 그림 4가 Axis-aligned의 의미를 보여주는 그림이다).

ns_attach_image_14081481263232285그림 4: Axis-aligned의 의미

ns_attach_image_14221481263274648그림 5: KD-Tree Search 알고리즘 종류

최소 8개 이상의 tree search (ray-traversal algorithm) 방법이 존재한다고 한다. 그림 5은 5가지의 방법을 보여준다. 각 방법은 다른 논문들에서 따로 소개를 진행하여서 논문에서는 아주 간단히 설명만 하였다.

  • Bounding Interval Hierarchy (BIH)

가장 최근에 소개되었고 앞의 방법 중에 가장 적은 메모리 공간을 사용한다. BVH와 거의 같은 방법이다. BIH의 경우 2개의 axis-aligned planes를 사용한다고 한다. (이 역시 무슨 말인지 잘 모르겠다. 논문에선 2개의 floating point value를 사용하여 triangle을 나눈다고 이야기한다. 이 역시 논문을 조금 더 찾아서 공부가 필요한 부분이다).

Implementation 및 Evaluation 결과

위의 5개 AS를 CUDA를 사용하여 구현하였다. 다양한 종류의 AS를 더 추가로 구현하여 실제 성능을 측정하였다고 한다. 상세한 구현 설명은 거의 없다. 대부분의 구현 방법을 다른 논문을 reference 하여서 정리하는 수준이었다. 결과는 KD Ropes와 BVH (SBVH)가 가장 좋은 ray tracing 성능이 나온다. 그림 6는 AS를 성능별로 나열한 결과이다. 이외 다른 결과들도 KD Ropes가 가장 좋은 ray tracing 성능을 보였다.

ns_attach_image_4591481508779814그림 6: Ray Tracing 결과 비교

아쉬운 점

Survey 논문이다. 결과적으로 상세한 내용보다 큰 형태의 내용만 포함하고 있어서 이해하는 데 어려움이 있다. Ray Tracing의 여러 방법을 알 수 있어서 좋지만 상세한 내용과 detail 한 설명이 없어서 이해하는 데는 다소 어려움이 있다.

중요하다고 판단되는 논문

  • Bounding Volume Hierarchy (BVH)
    • A 3-dimensional Representation for Fast Rendering of Complex Scenes
    • Understanding the Efficiency of Ray Traversal on GPUs Kepler and Fermi Addendum
  • Octree (or Quad-Tree)
    • Space Subdivison for Fast Ray Tracing
    • An Efficient Parametric Algorithm for Octree Traversal
  • Uniform Grid
    • Ray Tracing on a GPU with CUDA – Comparative Study of Three Algorithms
  • KD-Tree
    • Ray Tracing on a GPU with CUDA – Comparative Study of Three Algorithms
    • Stackless KD-tree traversal for high performance GPU ray tracing
  • Bounding Interval Hierarchy (BIH)
    • Instant ray tracing: The bounding interval hierarchy

출처

  1. Review and Comparative Study of Ray Traversal Algorithms on a Modern GPU Architecture (WSCG 2014)
  2. http://blog.vjeux.com/2012/javascript/javascript-ray-tracer.html
  3. http://www.awe-communications.com/Propagation/MIMO/propagationResults.htm

Leave a Comment