Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Dynamic Stackless Binary Tree Traversal

Författare

Summary, in English

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.

Publiceringsår

2013

Språk

Engelska

Sidor

38-49

Publikation/Tidskrift/Serie

Journal of Computer Graphics Techniques

Volym

2

Issue

1

Dokumenttyp

Artikel i tidskrift

Förlag

Williams College

Ämne

  • Computer Science

Status

Published

Forskningsgrupp

  • Computer Graphics

ISBN/ISSN/Övrigt

  • ISSN: 2331-7418