Earticle

초록

영어

This paper presents a parallel kd-tree traversal algorithm based on the parallel binary radix tree construction scheme proposed by Tero Karras in 2012. In his paper, Tero Karras proposed parallel tree construction algorithm which can maximize the utilization of GPU threads, but implementation and analysis of kd-tree are not fully discussed. This paper aims to fill the gap for the specific kd-tree cases. As an application for the kd-tree traversal method proposed in this paper, the proposed method has been implemented with NVIDIA’s CUDA framework and tested on NVIDIA’s realtime raytracing library, OptiX. As a result, the proposed method can construct tree structures within the requirement for realtime process, but still needs specialized spatial caching data structure like the “primitive tree” for highly detailed meshes to handle spatial queries as fast as to visualize implicit surfaces under OptiX framework. However, the proposed method can be applied to dynamic collision detection and manage scene and object information for game applications thanks to its fast tree construction process. Also, realtime raytracing can be applied to game applications based on this study.

목차

ABSTRACT
 1. 서론
 2. 기존 연구
  2.1 GPU 기반 병렬 kd-tree 구현
  2.2 Morton 코드
  2.3 GPU 기반 실시간 레이트레이싱
 3. Binary Radix Tree 기반 kd-Tree구현
  3.1 GPU 기반 병렬 binary radix tree
  3.2 binary radix tree의 kd-tree로서의 활용
  3.3 OptiX 기반 구현 및 기존 kd-tree와 비교
 4. 결과 및 논의
 5. 결론
 참고문헌

키워드

저자

• 박태정 [ Taejung Park | Department of Digital Media, Duksung Women’s University ] Correspondence to

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  컴퓨터게임및콘텐츠논문지(구 한국컴퓨터게임학회논문지) [Journal of Computer Games and Contents]

• 간기

  월간

• pISSN

  3091-7409

• eISSN

  3092-3638

• 수록기간

  2002~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 691 DDC 793