Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Dynamic Stackless Binary Tree Traversal

Barringer, Rasmus LU and Akenine-Möller, Tomas LU (2013) In Journal of Computer Graphics Techniques 2(1). p.38-49
Abstract
A fundamental part of many computer algorithms involves traversing a binary tree. One notable example is traversing a space-partitioning acceleration structure when computing ray-traced images. Traditionally, the traversal requires a stack to be temporarily stored for each ray, which results in both additional storage and memory-bandwidth usage. We present a novel algorithm for traversing a binary tree that does not require a stack and, unlike previous approaches, works with dynamic descent direction without restarting. Our algorithm will visit exactly the same sequence of nodes as a stack-based counterpart with extremely low computational overhead. No additional memory accesses are made for implicit binary trees. For sparse trees, parent... (More)
A fundamental part of many computer algorithms involves traversing a binary tree. One notable example is traversing a space-partitioning acceleration structure when computing ray-traced images. Traditionally, the traversal requires a stack to be temporarily stored for each ray, which results in both additional storage and memory-bandwidth usage. We present a novel algorithm for traversing a binary tree that does not require a stack and, unlike previous approaches, works with dynamic descent direction without restarting. Our algorithm will visit exactly the same sequence of nodes as a stack-based counterpart with extremely low computational overhead. No additional memory accesses are made for implicit binary trees. For sparse trees, parent links are used to backtrack the shortest path. We evaluate our algorithm using a ray tracer with a bounding volume hierarchy for which source code is supplied. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Journal of Computer Graphics Techniques
volume
2
issue
1
pages
38 - 49
publisher
Williams College
ISSN
2331-7418
language
English
LU publication?
yes
id
3a78e9ca-c92b-4847-935b-d69f58823b13 (old id 3567814)
alternative location
http://jcgt.org/published/0002/01/03/
date added to LUP
2016-04-01 14:25:28
date last changed
2021-05-05 21:46:36
@article{3a78e9ca-c92b-4847-935b-d69f58823b13,
  abstract     = {{A fundamental part of many computer algorithms involves traversing a binary tree. One notable example is traversing a space-partitioning acceleration structure when computing ray-traced images. Traditionally, the traversal requires a stack to be temporarily stored for each ray, which results in both additional storage and memory-bandwidth usage. We present a novel algorithm for traversing a binary tree that does not require a stack and, unlike previous approaches, works with dynamic descent direction without restarting. Our algorithm will visit exactly the same sequence of nodes as a stack-based counterpart with extremely low computational overhead. No additional memory accesses are made for implicit binary trees. For sparse trees, parent links are used to backtrack the shortest path. We evaluate our algorithm using a ray tracer with a bounding volume hierarchy for which source code is supplied.}},
  author       = {{Barringer, Rasmus and Akenine-Möller, Tomas}},
  issn         = {{2331-7418}},
  language     = {{eng}},
  number       = {{1}},
  pages        = {{38--49}},
  publisher    = {{Williams College}},
  series       = {{Journal of Computer Graphics Techniques}},
  title        = {{Dynamic Stackless Binary Tree Traversal}},
  url          = {{http://jcgt.org/published/0002/01/03/}},
  volume       = {{2}},
  year         = {{2013}},
}