표면 가시성 휴리스틱 방법을 이용한 KD-트리 구축
KD-Tree Construction Using Surface Visibility Heuristic
- 주제(키워드) 레이트레이싱 , 렌더링 , KD-트리
- 발행기관 서강대학교 일반대학원
- 지도교수 임인성
- 발행년도 2010
- 학위수여년월 2010. 8
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000046216
- 본문언어 한국어
초록/요약
광선 추적은 컴퓨터 그래픽스 분야에서 장면을 사실적으로 렌더링하기 위해 광선 추적법의 중요 요소로서 렌더링에 사용되거나, 포톤 매핑, 경로 추적법 등의 방법 구현에 중요하게 사용된다. 광선 추적법에서 어떤 광선과 교차하는 삼각형을 계산하기 위해, 하나의 광선과 장면의 모든 삼각형들의 교차 계산을 하는 기본적인 광선 추적법은 매우 많은 시간이 소요된다. 따라서 일반적으로는 광선 추적법을 가속화하기 위해 공간을 특정한 가속 구조(acceleration structure)로 구성하여 광선을 추적하는데, KD-트리 구조가 가장 빠르고 가장 널리 쓰인다고 알려져 있다. KD-트리 구조를 구축할 때 각 노드의 면적을 광선이 노드와 교차하는 확률로 사용하여 분할하는 SAH(Surface Area Heuristic) 방법이 가장 널리 쓰이고 있다. 하지만 SAH 방법은 좋은 근사치를 제공하나, 삼각형들이 이루는 장면에 대한 정보를 거의 사용하지 않는다. 본 논문에서는 주위의 삼각형들의 위치 정보를 고려하여 실제 광선이 분포하는 밀도를 보다 정밀하게 예측하여 KD-트리를 구축하는 방법을 제안하여, 렌더링 성능을 높이고자 한다.
more초록/요약
In a field of computer graphics, ray-object intersecion is used as a important element of ray tracing and used in photon mapping, path tracing to render a virtual scene realistically. Intersecion checks between a ray and all objects of the scene to perform ray tracing which is classical method, need exceedingly much time of calculations. To reduce the calculation time, the scene is generally re-constructed as a acceleration structure for which kd-tree structure is well-known structure for most fastest in rendering and used in broadly. SAH method, which is used in constructing kd-tree considering the surface area of the node as the probability of the intersection between the node and rays, are dominantly used in ray tracing area. Although SAH is the fast approximative method in both rendering time and construction time, it almost does not have considering triangles composed in a scene(especially triangles outside the node). This paper proposes the method which computes the probability of intersection between the node and rays more accurately with considering triangles in and out of the node, so that constructs fast kd-tree in rendering time than kd-tree using SAH method.
more