게임 충돌 처리 및 실시간 레이트레이싱을 위한 OptiX 실시간 광선추적 프레임워크 상의 Binary Radix Tree 기반 병렬 kd Tree 구현 및 분석
Implementation and Analysis of Parallel kd-Tree Based on Binary Radix Tree with OptiX Realtime Raytracing Framework for Collision Detection and Realtime Raytracing
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
This paper presents a parallel kd-tree traversal algorithm based on the parallel binary radix tree constructionscheme proposed by Tero Karras in 2012. In his paper, Tero Karras proposed parallel tree construction algorithmwhich can maximize the utilization of GPU threads, but implementation and analysis of kd-tree are not fullydiscussed. 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 beenimplemented with NVIDIA’s CUDA framework and tested on NVIDIA’s realtime raytracing library, OptiX. Asa result, the proposed method can construct tree structures within the requirement for realtime process, but stillneeds specialized spatial caching data structure like the “primitive tree” for highly detailed meshes to handlespatial queries as fast as to visualize implicit surfaces under OptiX framework. However, the proposed methodcan be applied to dynamic collision detection and manage scene and object information for game applicationsthanks to its fast tree construction process. Also, realtime raytracing can be applied to game applications basedon this study.
Abstract
This paper presents a parallel kd-tree traversal algorithm based on the parallel binary radix tree constructionscheme proposed by Tero Karras in 2012. In his paper, Tero Karras proposed parallel tree construction algorithmwhich can maximize the utilization of GPU threads, but implementation and analysis of kd-tree are not fullydiscussed. 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 beenimplemented with NVIDIA’s CUDA framework and tested on NVIDIA’s realtime raytracing library, OptiX. Asa result, the proposed method can construct tree structures within the requirement for realtime process, but stillneeds specialized spatial caching data structure like the “primitive tree” for highly detailed meshes to handlespatial queries as fast as to visualize implicit surfaces under OptiX framework. However, the proposed methodcan be applied to dynamic collision detection and manage scene and object information for game applicationsthanks to its fast tree construction process. Also, realtime raytracing can be applied to game applications basedon this study.
참고문헌 (16)
- Bentley J. L., "Multidimensional Binary Search Trees Used for Associative Searching", Communications of the ACM, 18(9), pp.509~517 (1975)
- 박태정, "GPU 기반 kd-tree를 이용한 병렬 충돌 처리 기법", 한국컴퓨터게임학회논문지, 25(2), pp.195~203 (2012), (사)한국컴퓨터게임학회[DOI]
- 이승욱, "감성 온라인 게임을 위한 구름 생성 시스템", 한국컴퓨터게임학회논문지, 26(1), pp.21~27 (2013), (사)한국컴퓨터게임학회
- 박태정, "게임 오브젝트 Polygon Soup 모델의 근사화 및 보간을 위한 고속 병렬 GPU 적분형 MLS 연산", 한국컴퓨터게임학회논문지, 25(1), pp.179~192 (2012), (사)한국컴퓨터게임학회[DOI]
- Tero Karras, "Maximizing Parallelism in the Construction of BVHs, Octrees, and K-d Trees", Proceedings of the Fourth ACM SIGGRAPH, 2012, 33~37
- Taejung Park, "Interactive Ray-tracing Based on OptiX to Visualize Signed Distance Fields", Proceedings on 2013 International Workshops on Multimedia, pp.149~152 (2013)
- Kun Zhou, "Real-Time KD-Tree Construction on Graphics Hardware", ACM Transactions on Graphics, 26(5) (2008)
- Fuchang Liu, "Exact and Adaptive Signed Distance Fields Computation for Rigid and Deformable Models on GPUs", IEEE Transactions on Visualization and Computer Graphics, 20(5), pp.714~725 (2014)
- "NVIDIA OptiX"[URL]
- John C. Hart, "Sphere Tracing: A Geometric Method for the Antialiased Ray Tracing of Implicit Surfaces", The Visual Computer, 12(10), pp.527~545 (1996)
- A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, "G. M. Morton", IBM, ~, pp.IBM Technical Report (1966)
- Kirill Garanzha, "Simpler and Faster HLBVH with Work Queues", High Performance Graphics 2011, pp.59~64 (2011)
- Kun Zhou, "Dataparallel Octrees for Surface Reconstruction", IEEE Transactions on Visualization and Computer Graphics, 17(5), pp.669~681 (2011)
- David J. MacDonald, "Heuristics for ray tracing using space subdivision", The Visual Computer, 6(3), pp.153~166 (1990)
- Sungho Lee, "Primitive Trees for Precomputed Distance Queries", Computer Graphics Forum, 32(2), pp.419~428 (2013)
- 박태정, "Primal Tree의 공간 분할 샘플링 분석 및 구현", 디지털컨텐츠학회논문지, 15(3), pp.347~355 (2014), 한국디지털콘텐츠학회[DOI]