Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section