검색 상세

GPU를 사용한 효과적인 Kd-Tree 탐색 알고리즘

Efficient Kd-Tree Traversal Algorithm on GPU

초록/요약

광선 추적법은 고품질의 이미지를 얻을 수 있는 전역 조명 렌더링 방법 중의 하나로서, 관찰자의 시점으로부터 샘플링 된 광선을 역추적하며 광원에서 출발한 빛이 물체들과 상호작용 하면서 받는 영향을 계산한다. 광선의 역추적이 재귀적으로 반복될 수 있으므로 반사와 투과 등의 다양한 광학적 효과를 시뮬레이션 할 수 있다. 따라서 실시간 렌더링에 쓰이는 래스터화 방법보다 높은 품질을 얻을 수 있는 장점이 있지만 방법의 특성상 높은 계산 비용이 드는 단점이 있다. 광선 추적법에서 가장 비용이 큰 부분은 광선과 3차원 물체의 충돌검사다. 이러한 특성 때문에 충돌검사의 비용을 줄이기 위한 많은 연구들이 진행 되었으며, 근래에는 효율적인 공간 자료구조로서 kd-tree가 가장 많이 사용되고 있다. 최근 들어 프로그래밍 가능한 GPU의 파이프라인에서의 SIMD, 텍스처 연산 등의 고성능의 특화된 기능들을 사용하여 여러가지 범용 계산을 하고자 하는 연구들이 이루어 지고 있는데, kd-tree 기반의 광선 추적법을 GPU에서 구현하는 것 역시 큰 연구 주제 중 하나이다. 본 논문에서는 이미 제안된 방법들을 하나의 틀에서 구현해 비교 분석하여 그 방법들의 장단점을 정확히 분석한 후, CPU에 비해 제한적이지만 고성능의 특화된 GPU의 기능을 최대로 활용할 수 있도록 향상된 kd-tree 기반 가시성 검사 기법을 제안한다. 또한 렌더링 장면의 특성 등을 고려한 효과적인 kd-tree 형태에 대해 논의 한다.

more

초록/요약

The ray tracing is one of the efficient global illumination algorithms for high quality image. It traces rays from camera position for intensive directions to calculate light-object interreflections. Since the intensive directions mean light, reflection and refraction direction, we can simulate important optical effects with this recursive algorithm. But the ray tracing was not fast enough for realtime application until recently. The bottleneck of this method is a ray-object intersection calculation. Therefore many researches have been focused on improvement of this part. The kd-tree is used by general and efficient structure for ray tracing recently. Specialy the ray-object intersection algorithms using a kd-tree structure have been implemented on a programmable GPU which has multiple cores with high performance SIMD operations. Because of GPUs still works on limited environments, GPU based algorithms must be specialized to maximize a performance using GPU supported features. In this paper, we analyze the existed GPU based kd-tree traversal algorithms and propose a improved method and experimental results. Also the efficient forms of a kd-tree concerned 3D scene structures are discussed.

more

목차

제1장. 서론 = 1
1.1 연구배경 및 기존 연구 = 1
1.2 본 논문의 기여도 및 구성 = 6
제2장. GPU상에서의 Kd-Tree 탐색법 = 7
2.1 GPU에서의 프로그래밍 모델 = 7
2.2 Kd-Tree 탐색 = 10
2.3 CPU와 GPU의 구조적 차이 = 12
2.4 스택 기반 탐색 방법 = 13
2.5 기존의 GPU 기반 Kd-Tree 탐색 : Foley 등의 방법 = 16
2.5.1 Kd-restart = 16
2.5.2 Kd-backtrack = 17
2.6 기존의 GPU 기반 Kd-Tree 탐색 : 강 등의 방법 = 18
2.6.1 개선된 kd-backtrack = 18
2.7 기존의 GPU 기반 Kd-Tree 탐색 : Horn 등의 방법 = 19
2.7.1 Push-down = 20
2.7.2 Short-stack = 20
2.8 기존의 GPU 기반 Kd-Tree 탐색 : Popov 등의 방법 = 21
2.8.1 로프 방법 = 21
제3장 향상된 GPU Kd-Tree 탐색법 = 23
3.1 향상된 Kd-Tree 탐색법 I : 캐쉬된 스택 방법 = 23
3.2 향상된 Kd-Tree 탐색법 II : 고정 스택 로프 방법 = 27
3.2.1 고정 스택 로프 탐색 알고리즘 = 28
3.2.2 고정 스택 로프 생성 알고리즘 = 30
3.2.3 Kd-Tree 노드 구조 = 34
제4장 실험 결과 = 37
4.1 실험 환경 = 37
4.2 최적화 기법 = 39
4.2.1 텍스쳐 메모리의 활용 = 39
4.2.2 가속된 광선-삼각형 교차 검사 방법 = 40
4.2.3 최적화된 쓰레드 블록 크기 = 43
4.2.4 최적화된 Kd-Tree 생성 = 44
4.3 로프 방법에서의 하향 탐색 방법 비교 = 47
4.4 캐쉬된 스택 방법 실험 결과 = 48
4.5 고정 스택 로프 방법 실험 결과 = 49
4.5.1 메모리 사용량 실험 결과 = 49
4.5.2 탐색 속도 실험 결과 = 51
4.6 광선 응집도에 다른 탐색 속도 결과 = 52
4.6.1 캐쉬된 스택 방법의 실험 결과 = 53
4.6.2 고정 스택 로프 방법의 실험 결과 = 54
4.7 장면 분류에 따른 탐색 속도 결과 = 55
4.8 CPU와의 비교 = 57
제5장 결론 및 향후 연구 = 59
그림차례
2.1 CUDA 하드웨어 모델 = 8
2.2 Kd-tree 예시 = 11
2.3 광선 범위 알고리즘 = 14
2.4 Kd-reastart의 문제점 = 17
2.5 Kd-backtrack의 장점 = 18
2.6 로프 방법 = 21
3.1 캐쉬된 스택의 삽입 연산 = 24
3.2 캐쉬된 스택의 삭제 연산 = 25
3.3 캐쉬된 스택 = 26
3.4 고정 스택 로프 탐색 알고리즘 = 28
3.5 로프 최적화 알고리즘 적용시 차이점 = 30
3.6 로프 최적화 알고리즘의 각 단계 = 33
3.7 8 바이트 크기의 kd-tree 노드 = 35
4.1 본 연구의 실험에 사용된 장면 = 38
4.2 구조체의 택스쳐 사용 = 40
4.3 로프 방법의 광선 범위 기반 하향 탐색 코드 = 47
표차례
4.1 광선-삼각형 교차 방법 = 42
4.2 쓰레드 블록 크기별 캐쉬돈 스택 방법의 속도 = 43
4.3 쓰레드 블록 크기별 고정 스택 로프 방법의 속도 = 44
4.4 로프 방법의 하향 탐색법 비교 = 48
4.5 캐쉬돈 스택 방법의 효과 = 49
4.6 고정 스택 로프의 스택 깊이별 속도 = 50
4.7 로프 방법과 고정 스택 로프 방법 사용시 추가로 필요한 메모리 사용량 비교 = 51
4.8 로프 방법과 고정 스택 로프 방법의 비교 = 52
4.9 캐쉬돈 스택 방법의 광선 응집도에 따른 탐색 속도 = 53
4.10 고정 스택 로프 방법의 광선 응집도에 따른 탐색 속도 = 54
4.11 Kd-restart, Push-down, Short-stack과 제안된 방법의 속도 비교 = 55
4.12 스택 깊이별 스택의 메모리 사용량 = 56
4.13 CPU상의 스택 기반 탐색법과 제안된 방법의 속도 비교 = 57

more