de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

 
 
 
 
DownloadE-Mail
  On fast construction of spatial hierarchies for ray tracing

Havran, V., Herzog, R., & Seidel, H.-P.(2006). On fast construction of spatial hierarchies for ray tracing (MPI-I-2006-4-004). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: http://hdl.handle.net/11858/00-001M-0000-0014-6807-8 Versions-Permalink: http://hdl.handle.net/11858/00-001M-0000-0014-7977-5
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-2006-4-004.ps (beliebiger Volltext), 10MB
Beschreibung:
-
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/postscript / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Havran, Vlastimil1, Autor              
Herzog, Robert1, Autor              
Seidel, Hans-Peter1, Autor              
Affiliations:
1Computer Graphics, MPI for Informatics, Max Planck Society, escidoc:40047              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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 propose a hybrid data structure blending between a spatial kd-tree and bounding volume primitives. We keep our novel hierarchical data structures algorithmically efficient and comparable with kd-trees by the use of 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 that corresponds to sorting based on comparisons, using approximate method based on discretization we propose a new hierarchical data structures with expected $O(N \log\log N)$ time complexity. We also discuss constants behind the construction algorithms of spatial hierarchies that are important in practice. We document the performance of our algorithms by results obtained from the implementation tested on nine different scenes.

Details

einblenden:
ausblenden:
Sprache(n): eng - Englisch
 Datum: 2006
 Publikationsstatus: Im Druck publiziert
 Seiten: 40 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2006-4-004
Reportnr.: MPI-I-2006-4-004
BibTex Citekey: HavranHerzogSeidel2006
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -