Gkdtree: A group-based parallel update kd-tree for interactive ray tracing

Yoon Sig Kang, Jae Ho Nah, Woo Chan Park, Sung Bong Yang

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


This paper proposes a new group-based acceleration data structure called gkDtree for interactive ray tracing of dynamic scenes. The main idea of the gkDtree is to construct the acceleration structure with a multi-level hierarchy, and to integrate a parallelization approach to result in a faster update and a more efficient tree traversal. A gkDtree can be viewed as a set of kd-trees, each of which is a local acceleration structure corresponding to a group. For a gkDtree, a scene is divided into several groups based on a scene graph. The local acceleration structure of each group involving only dynamic primitives is rebuilt. To achieve higher parallelization, dependencies among groups in different levels are removed before rebuilding occurs in parallel. To enhance the scalability of parallelization, a simple and fast load-balancing scheme is introduced. Furthermore, we apply a variety of accurate SAH (surface area heuristic) algorithms into tree generation for both static and dynamic groups. The experimental results show that a gkDtree has a real-time update performance. It has an update performance that is up to 166 times faster than a kd-tree for our test scenes in a six-core hardware system environment. Furthermore, the results also show that tree traversal performance of a gkDtree is competitive with that of a kd-tree.

Original languageEnglish
Pages (from-to)166-175
Number of pages10
JournalJournal of Systems Architecture
Issue number3
Publication statusPublished - 2013 Mar

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture


Dive into the research topics of 'Gkdtree: A group-based parallel update kd-tree for interactive ray tracing'. Together they form a unique fingerprint.

Cite this