Proceedings: GI 2011

Implicit and dynamic trees for high performance rendering

Nathan Andrysco, Xavier Tricoche

Proceedings of Graphics Interface 2011: St. John’s, Newfoundland, Canada, 25 - 27 May 2011, 143-150

  • BibTex

    author = {Andrysco, Nathan and Tricoche, Xavier},
    title = {Implicit and dynamic trees for high performance rendering},
    booktitle = {Proceedings of Graphics Interface 2011},
    series = {GI 2011},
    year = {2011},
    issn = {0713-5424},
    isbn = {978-1-4503-0693-5},
    location = {St. John{\textquoteright}s, Newfoundland, Canada},
    pages = {143--150},
    numpages = {8},
    publisher = {Canadian Human-Computer Communications Society},
    address = {Toronto, Ontario, Canada},


Recent advances in GPU architecture and programmability have enabled the computation of ray casted or ray traced images at interactive frame rates. However, the rapid performance gains of the hardware cannot by themselves address the challenge posed by the steady growth in the geometric and temporal complexity of computer graphics datasets. In this paper we present a novel versatile tree data structure that can accommodate both sparse and dense data sets and is more memory efficient than state-of-the-art representations. A key feature of our data structure for rendering applications is that it fully supports efficient, parallel building. As a result, our implicit tree representation significantly outperforms existing techniques in the rendering of time-varying scenes. We show how this data structure can be extended to encode other classic representations such as BSP-trees and we discuss the high-performance implementation of our general approach on the GPU.