MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Havran, Vlastimil
Herzog, Robert
Seidel, Hans-Peter		dblp
dblp
dblp
Not MPG Author(s):
Havran, Vlastimil
Editor(s):
Wald, Ingo
Parker, Steven G.		dblp
dblp
Not MPII Editor(s):
Wald, Ingo
Parker, Steven G.
BibTeX cite key*:
HavranRT2006
Title, Booktitle
Title*:
On the Fast Construction of Spatial Hierarchies for Ray Tracing
Booktitle*:
Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Salt Lake City, UT, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
18 September 2006
Event End Date:
20 September 2006
Publisher
Name*:
IEEE
URL:
Address*:
Piscataway, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
September
Pages:









71-80
Year*:
2006
VG Wort Pages:
ISBN/ISSN:
1-4244-0693-5
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
In this paper we address the problem of fast construction of spatial
hierarchies for ray tracing with applications in animated environments
including non-rigid animations. We discuss properties of currently
used techniques with $O(N \log N)$ construction time for kd-trees and
bounding volume hierarchies. Further, we will propose a hybrid data structure blending a spatial kd-tree with bounding volume
primitives. We will keep our novel hierarchical data structures
algorithmically efficient and comparable with kd-trees by using a cost model based on surface area heuristics. Although the time
complexity $O(N \log N)$ is a lower bound required for construction of any spatial hierarchy, which corresponds to sorting based on comparisons, using an approximate method based on space discretization, we propose a new hierarchical data structures with expected $O(N \log\log N)$ time complexity. We also discuss the constants behind the construction algorithms of spatial hierarchies that are important in practice. We document
the performance of our algorithms by results obtained from nine different scenes.
URL for the Abstract:
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=4061530&arnumber=4061548&count=30&index=16
Keywords:
Ray Shooting, Ray Tracing, Animation, Time Complexity, Hierarchical Data Structures, Spatial Sorting, Approximate Algorithms
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Computer Graphics Group
External Affiliations:
Czech Technical University in Prague, Czech Republic
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{HavranRT2006,
AUTHOR = {Havran, Vlastimil and Herzog, Robert and Seidel, Hans-Peter},
 EDITOR = {Wald, Ingo and Parker, Steven G.},
 TITLE = {On the Fast Construction of Spatial Hierarchies for Ray Tracing},
 BOOKTITLE = {Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing},
 PUBLISHER = {IEEE},
 YEAR = {2006},
 PAGES = {








71--80
},
 ADDRESS = {Salt Lake City, UT, USA},
 MONTH = {September},
 ISBN = {1-4244-0693-5},
}

Entry last modified by Christine Kiesel, 03/03/2007
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Robert Herzog		Created
11/23/2006 05:23:08 PM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Conny Liegl
Robert Herzog
Robert Herzog
Edit Dates
03.03.2007 09:24:13
01/10/2007 12:11:23 PM
11/23/2006 05:26:50 PM
11/23/2006 05:23:08 PM