선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 CUDA를 이용해 지역 메모리에 스택을 구현하였고 그에 맞는 자료구조 및 가속화 방법을 제안하고 있다. 본 논문의 알고리즘은 별도의 coherency를 이용하는 광선패킷이나 특정한 하드웨어에 대한 자료구조를 요구하는 가속화 방법을 쓰지 않고 병렬 처리시에 발생하는 스레드간에 발생하는 빈번한 동기화를 필요로 하지 않는다.
- 일반적으로 kd-tree같은 공간분할 기법이 가장 빠른 성능을 보여주고 있지만 근본적으로 기존 그래픽스 하드웨어에서와 GPGPU 플랫폼에서는 스택(stack)의 지원이 미약하고 병렬처리를 위한 SIMD(Single Instruction Multiple Data) 대응 및 프로그래밍이 어렵기 때문에 GPU를 통해 비교적 거대한 장면에 대해서 kd-tree를 이용하여 실시간으로 광선을 추적하는 것은 많은 한계가 있다. 본 논문은 광선추적의 핵심 모듈인 공간 가속구조와 광선/삼각형 교차검사의 가속을 위하여 CUDA를 이용한 알고리즘을 구현하였다.
제안 방법
- 1차 광선의 경우는 Plücker 검사의 2단계를 모두 진행하여 교차점까지 찾는 과정을 수행하였지만 그림자 광선에 경우에는 쉐이딩이 목적이 아니므로 무게중심 좌표를 돌려줄 필요가 없으므로 간단히 hit에 대한 정보만 돌려주는 것으로 최적화를 수행하였다.
- GPU에서는 각각의 스레드가 광선과 대응하여 독립적으로 교차테스트를 실시하므로 파이프라인에서 병목현상이 일어나지 않도록 하는 것이 중요한데 이를 위해서 추가적으로 분기를 발생시키지 않는 교차테스트를 구현하였다. 만약 잘못된 분기를 통해서 교차테스트가 수행이 된다면 실행의 길이에 따라서 경우에 따라서는 심각한 성능저하를 일으킬 수 있기 때문이다.
- host(CPU)에서는 장면의 계층적 구성과 삼각형 메쉬에 대한 사전 연산을 수행하고 CUDA 텍스쳐 버퍼로 필요한 모든 정보를 device(GPU)에 넘기는 것으로 광선추적이 시작된다. GPU에서는 모든 광원에 대하여 스택 기반의 탐색을 통해 비교적 복잡한 장면을 지원하도록 하였으며 완료된 노드가 참조하는 삼각형에 대하여 효과적인 교차검사를 실시하였다. 1차 광선의 탐색을 시작하고 혹은 그림자를 생성하기 위해 부가적인 계산을 하여 픽셀당 쉐이딩 결과를 획득하는데 이때 반사나 굴절의 효과를 위해 2차 광선이 필요할 수도 있게 된다.
- 각 노드의 정보에 비트 인코딩된 오프셋과 분할 축을 참조하여 해독된 노드의 정보는 광선의 위치와 방향과 함께 사용되어 하향식의 kd-tree 탐색을 진행하게 된다. 광선 세그먼트 [near, far]를 장면의 전체 바운딩 박스에 클리핑 시킨 다음 업데이트를 하면서 왼쪽, 오른쪽 중 어떤 자식노드에 광선이 교차되었는지를 판단하기 위해 탐색구조 안에서 탐색된 노드의 각각에 분할면에 대한 거리(dist)를 계산하여 그 거리를 현재의 광선 세그먼트와 비교하게 된다.
- 각 단말노드에 ‘rope'라고 불리는 6개의 인접노드에 대한 포인터를 별도로 저장한 뒤, 임의의 단말 노드에 대해 교차된 삼각형이 발견되지 않았을 경우 다음의 인접한 노드 중 교차가 발생된 노드부터 재탐색하도록 하였다.
- 각 노드의 정보에 비트 인코딩된 오프셋과 분할 축을 참조하여 해독된 노드의 정보는 광선의 위치와 방향과 함께 사용되어 하향식의 kd-tree 탐색을 진행하게 된다. 광선 세그먼트 [near, far]를 장면의 전체 바운딩 박스에 클리핑 시킨 다음 업데이트를 하면서 왼쪽, 오른쪽 중 어떤 자식노드에 광선이 교차되었는지를 판단하기 위해 탐색구조 안에서 탐색된 노드의 각각에 분할면에 대한 거리(dist)를 계산하여 그 거리를 현재의 광선 세그먼트와 비교하게 된다. 광선 세그먼트가 near보다 작거나 far보다 크게 되면 현재 노드들의 하위 트리는 검색할 필요가 없지만 그렇지 않다면 각 노드를 순서대로 탐색하여야 한다.
- 단말노드의 경우는 전체의 삼각형을 포함하는 인덱스에 대해 4byte를 할당하고 나머지를 각 단말노드당 삼각형의 개수를 저장하도록 하였다. 그리고 탐색 이전에 구축된 트리에 대해서 CUDA에서 조금 더 유용한 array 방식의 접근을 위해서 임의의 하위트리들을 BFS(Breadth First Search) 방식으로 메모리에 연속되게 넣어 트리 전체를 다시 할당했다. 이 방법으로 첫 번째 자식노드를 가리키는 것으로 나머지 자식노드까지 모두 접근할 수 있으므로 캐시 효율을 증가시킬 수 있다.
- 그러나 동적으로 물체가 움직이거나 변형되는 장면에서는 본 논문에서 사용된 사전연산과 트리의 빌드과정이 탐색의 성능에 치중된 관계로 비교적 느리기 때문에 트리의 업데이트의 효율성의 문제가 발생하였다. 따라서 탐색과 갱신이 모두 가벼운 Surface Area Heuristic 기반의 장면 구축 알고리즘 개발 및 GPU 자체에서 kd-tree를 실시간으로 빌드에 대한 연구를 수행하고 있다.
- 또한 다른 노드들을 참조하기 위한 별도의 저장공간이 필요치 않으므로 좀 더 복잡한 장면을 로딩하는 데 수월하게 되며 남는 자원은 GPU에서 좀 더 효율적으로 사용될 수 있게 된다. 또한 광선추적의 대부분의 시간이 소요되는 교차검사의 향상을 위해 최신의 Plücker 검사방법을 GPU에서 최적화하여 사용하여 가속화시킴으로서 기존 알고리즘 조합(스택이 없는 kd-tree + projection 메소드)에 비하여 약 두 배 이상의 성능 향상을 도출하였다.
- 본 논문에서는 CUDA를 이용해 지역 메모리에 스택을 구현하였고 그에 맞는 자료구조 및 가속화 방법을 제안하고 있다. 본 논문의 알고리즘은 별도의 coherency를 이용하는 광선패킷이나 특정한 하드웨어에 대한 자료구조를 요구하는 가속화 방법을 쓰지 않고 병렬 처리시에 발생하는 스레드간에 발생하는 빈번한 동기화를 필요로 하지 않는다. 또한 다른 노드들을 참조하기 위한 별도의 저장공간이 필요치 않으므로 좀 더 복잡한 장면을 로딩하는 데 수월하게 되며 남는 자원은 GPU에서 좀 더 효율적으로 사용될 수 있게 된다.
- 만약 잘못된 분기를 통해서 교차테스트가 수행이 된다면 실행의 길이에 따라서 경우에 따라서는 심각한 성능저하를 일으킬 수 있기 때문이다. 분기를 발생시키지 않도록 하기 위해서 교차가 발생했을 때의 연산과 교차가 발생하지 않았을 때의 연산에 대한 양쪽의 경우를 추가적인 비트 마스크를 사용하여 논리 비트연산으로 제어하여 잘못된 분기를 막아 커널의 coherency를 유지하였다.
- 25GB의 메인메모리와 NVIDIA Gefordce 8800GTX를 사용한 PC에서 이루어졌다. 성능 비교를 위해 기존의 스택이 없는 kd-tree 탐색 알고리즘[3]과 projection 메소드 기반[4]의 교차검사 알고리즘을 직접 구현하여 동일한 조건에서 실험하였다.
- 광선 세그먼트가 near보다 작거나 far보다 크게 되면 현재 노드들의 하위 트리는 검색할 필요가 없지만 그렇지 않다면 각 노드를 순서대로 탐색하여야 한다. 이때 현재 탐색되지 않는 노드에 대한 정보를 push하게 되는데 본 논문에서는 CUDA를 통해 지역메모리에 배열 형식으로 트리의 깊이에 기반한 고정된 사이즈의 읽기/쓰기 가능한 스택을 구현하고 사용하였다. 본 알고리즘은 CPU내에서 수행되는 탐색방법과 매우 비슷하다.
- 제안하는 탐색 방법은 생성 및 구축에 관한 문제는 포함하지 않으므로 본 실험에서는 생성시간에 대한 평가는 실험하지 않았고 이미 구축된 트리에 대한 성능 검사를 실시하였다. 테스트는 1차 광선에 대해 phong 모델의 쉐이딩을 사용하였다.
- 삼각형의 edge의 경우 앞서 버텍스의 경우와 마찬가지로 u와 v의 두 개의 인덱스를 이용하여 e0,e1에 적용하여 4개의 float (eu0,ev0,eu1,ev1)만으로 나타낼 수 있게 된다. 추가적으로 법선의 원소 nu와 nv가 0이 되는 축에 정렬된 삼각형에 대한 플래그를 표시하도록 하여 적응형의 가벼운 간편한 연산을 수행하도록 한다.
대상 데이터
- 광선 추적의 성능 검사에 주로 쓰이는 장면을 포함한 몇가지 장면들에 대한 실험 결과 본 논문에서 제안한 방법이 효과적으로 수행됨을 확인 하였다. 본 실험은 Intel Quadcore 3.2Ghz, 3.25GB의 메인메모리와 NVIDIA Gefordce 8800GTX를 사용한 PC에서 이루어졌다. 성능 비교를 위해 기존의 스택이 없는 kd-tree 탐색 알고리즘[3]과 projection 메소드 기반[4]의 교차검사 알고리즘을 직접 구현하여 동일한 조건에서 실험하였다.
데이터처리
- <표 2>는 최종적인 시스템의 광선추적 수행능력을 각각 CUDA로 구현하여 결과는 10번의 반복을 통한 평균을 제시하였다. 제안된 시스템은 기존 스택이 없는 kd-tree를 이용한 시스템에 비해서 노드 재방문이나 중복된 바운딩 박스의 교차검사를 하지 않는 단순한 구조로 되어있기 때문에 여분의 자원을 더 많은 CUDA 프레임워크 상에서 쓰레드 동시 수행이나 거대 장면의 렌더링을 지원하기 위해 배분할 수 있으므로 가동이 가능한 멀티 프로세서들이 증가됨에 따라서 성능효율 또한 약 두 배 가까이 증대되었다.
이론/모형
- 본 논문은 최근 CPU 기반의 광선/삼각형 교차검사 알고리즘인 Plücker 좌표계 검사 알고리즘[8]을 이용하여 구현하였다.
- 제안하는 탐색 방법은 생성 및 구축에 관한 문제는 포함하지 않으므로 본 실험에서는 생성시간에 대한 평가는 실험하지 않았고 이미 구축된 트리에 대한 성능 검사를 실시하였다. 테스트는 1차 광선에 대해 phong 모델의 쉐이딩을 사용하였다.
성능/효과
- <표 1>과 같이 모든 장면에 대하여 제안된 스택기반의 kd-tree가 그래픽스 하드웨어에 제한된 메모리에 적합한 사용량을 보여주고 있다. 노드들을 압축하지 않는 경우에도 3배 이상의 메모리 절감 효과를 보여주고 있기 때문에 좀 더 복잡한 장면의 로딩을 위해서 본 알고리즘이 좀 더 바람직하다고 볼 수 있다.
- 광선 추적의 성능 검사에 주로 쓰이는 장면을 포함한 몇가지 장면들에 대한 실험 결과 본 논문에서 제안한 방법이 효과적으로 수행됨을 확인 하였다. 본 실험은 Intel Quadcore 3.
- 제안된 시스템은 기존 스택이 없는 kd-tree를 이용한 시스템에 비해서 노드 재방문이나 중복된 바운딩 박스의 교차검사를 하지 않는 단순한 구조로 되어있기 때문에 여분의 자원을 더 많은 CUDA 프레임워크 상에서 쓰레드 동시 수행이나 거대 장면의 렌더링을 지원하기 위해 배분할 수 있으므로 가동이 가능한 멀티 프로세서들이 증가됨에 따라서 성능효율 또한 약 두 배 가까이 증대되었다. 또한 기존의 교차검사에 비하여 Plücker 기반의 교차검사를 수행하였을 때 10-20% 이상의 추가적인 성능의 향상이 있었다.
- <표 2>는 최종적인 시스템의 광선추적 수행능력을 각각 CUDA로 구현하여 결과는 10번의 반복을 통한 평균을 제시하였다. 제안된 시스템은 기존 스택이 없는 kd-tree를 이용한 시스템에 비해서 노드 재방문이나 중복된 바운딩 박스의 교차검사를 하지 않는 단순한 구조로 되어있기 때문에 여분의 자원을 더 많은 CUDA 프레임워크 상에서 쓰레드 동시 수행이나 거대 장면의 렌더링을 지원하기 위해 배분할 수 있으므로 가동이 가능한 멀티 프로세서들이 증가됨에 따라서 성능효율 또한 약 두 배 가까이 증대되었다. 또한 기존의 교차검사에 비하여 Plücker 기반의 교차검사를 수행하였을 때 10-20% 이상의 추가적인 성능의 향상이 있었다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.