On building fast kd-trees for ray tracing, and on doing that in O(N log N)
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F06%3A03121478" target="_blank" >RIV/68407700:21230/06:03121478 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On building fast kd-trees for ray tracing, and on doing that in O(N log N)
Original language description
Though a large variety of efficiency structures for ray tracing exist, kd-trees today seem to slowly become the method of choice. In particular, kd-trees built with cost estimation functions such as a surface area heuristic (SAH) seem to be important forreaching high performance. Unfortunately, most algorithms for building such trees have a time complexity of O(N log2 N), or even O(N2). In this paper, we analyze the state of the art in building good kdtrees for ray tracing, and eventually propose an algorithm that builds SAH kd-trees in O(N logN), the theoretical lower bound.
Czech name
Není k dispozici
Czech description
Není k dispozici
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/LC06008" target="_blank" >LC06008: Center of Computer Graphics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of IEEE Symposium on Interactive Ray Tracing 2006
ISBN
1-4244-0693-5
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
61-70
Publisher name
IEEE Computer Society
Place of publication
USA
Event location
Salt Lake City
Event date
Sep 18, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—