• search hit 3 of 4
Back to Result List

The Line Space - a Directional Data Structure for Ray Tracing Acceleration

  • Ray tracing acceleration through dedicated data structures has long been an important topic in computer graphics. In general, two different approaches are proposed: spatial and directional acceleration structures. The thesis at hand presents an innovative combined approach of these two areas, which enables a further acceleration of the tracing process of rays. State-of-the-art spatial data structures are used as base structures and enhanced by precomputed directional visibility information based on a sophisticated abstraction concept of shafts within an original structure, the Line Space. In the course of the work, novel approaches for the precomputed visibility information are proposed: a binary value that indicates whether a shaft is empty or non-empty as well as a single candidate approximating the actual surface as a representative candidate. It is shown how the binary value is used in a simple but effective empty space skipping technique, which allows a performance gain in ray tracing of up to 40% compared to the pure base data structure, regardless of the spatial structure that is actually used. In addition, it is shown that this binary visibility information provides a fast technique for calculating soft shadows and ambient occlusion based on blocker approximations. Although the results contain a certain inaccuracy error, which is also presented and discussed, it is shown that a further tracing acceleration of up to 300% compared to the base structure is achieved. As an extension of this approach, the representative candidate precomputation is demonstrated, which is used to accelerate the indirect lighting computation, resulting in a significant performance gain at the expense of image errors. Finally, techniques based on two-stage structures and a usage heuristic are proposed and evaluated. These reduce memory consumption and approximation errors while maintaining the performance gain and also enabling further possibilities with object instancing and rigid transformations. All performance and memory values as well as the approximation errors are measured, presented and discussed. Overall, the Line Space is shown to result in a considerate improvement in ray tracing performance at the cost of higher memory consumption and possible approximation errors. The presented findings thus demonstrate the capability of the combined approach and enable further possibilities for future work.
  • Die Raytracing-Beschleunigung durch dedizierte Datenstrukturen ist schon lange ein wichtiges Thema der Computergrafik. Im Allgemeinen werden dafür zwei unterschiedliche Ansätze vorgeschlagen: räumliche und richtungsbezogene Beschleunigungsstrukturen. Die vorliegende Arbeit stellt einen innovativen kombinierten Ansatz dieser beiden Bereiche vor, welcher weitere Beschleunigung der Strahlenverfolgung ermöglicht. Dazu werden moderne räumliche Datenstrukturen als Basisstrukturen verwendet und um vorberechnete gerichtete Sichtbarkeitsinformationen auf Basis von Schächten innerhalb einer originellen Struktur, dem Line Space, ergänzt. Im Laufe der Arbeit werden neuartige Ansätze für die vorberechneten Sichtbarkeitsinformationen vorgeschlagen: ein binärer Wert, der angibt, ob ein Schacht leer oder gefüllt ist, sowie ein einzelner Vertreter, der als repräsentativer Kandidat die tatsächliche Oberfläche approximiert. Es wird gezeigt, wie der binäre Wert nachweislich in einer einfachen, aber effektiven Leerraumüberspringungs-Technik (Empty Space Skipping) genutzt wird, welche unabhängig von der tatsächlich verwendeten räumlichen Basisdatenstruktur einen Leistungsgewinn beim Raytracing von bis zu 40% ermöglicht. Darüber hinaus wird gezeigt, dass diese binären Sichtbarkeitsinformationen eine schnelle Technik zur Berechnung von weichen Schatten und Umgebungsverdeckung auf der Grundlage von Blockerapproximationen ergeben. Obwohl die Ergebnisse einen gewissen Ungenauigkeitsfehler enthalten, welcher auch dargestellt und diskutiert wird, zeigt sich, dass eine weitere Traversierungsbeschleunigung von bis zu 300% gegenüber der Basisstruktur erreicht wird. Als Erweiterung zu diesem Ansatz wird die repräsentative Kandidatenvorberechnung demonstriert, welche verwendet wird, um die indirekte Lichtberechnung durch die Integration von kaum wahrnehmbaren Bildfehlern signifikant zu beschleunigen. Schließlich werden Techniken vorgeschlagen und bewertet, die auf zweistufigen Strukturen und einer Nutzungsheuristik basieren. Diese reduzieren den Speicherverbrauch und die Approximationsfehler bei Aufrechterhaltung des Geschwindigkeitsgewinns und ermöglichen zusätzlich weitere Möglichkeiten mit Objektinstanziierungen und starren Transformationen. Alle Beschleunigungs- und Speicherwerte sowie die Näherungsfehler werden gemessen, dargestellt und diskutiert. Insgesamt zeigt sich, dass durch den Line Space eine deutliche Erhöhung der Raytracing Leistung auf Kosten eines höheren Speicherverbrauchs und möglicher Annäherungsfehler erreicht wird. Die vorgestellten Ergebnisse zeigen damit die Leistungsfähigkeit des kombinierten Ansatzes und eröffnen weitere Möglichkeiten für zukünftige Arbeiten.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Kevin Keul
URN:urn:nbn:de:kola-21812
Referee:Stefan Müller, Thorsten Grosch
Advisor:Stefan Müller
Document Type:Doctoral Thesis
Language:English
Date of completion:2021/03/22
Date of publication:2021/03/22
Publishing institution:Universität Koblenz, Universitätsbibliothek
Granting institution:Universität Koblenz, Fachbereich 4
Date of final exam:2020/12/04
Release Date:2021/03/22
Tag:Acceleration Structures; Computer Graphics; Line Space; Raytracing
Number of pages:vii, 170
Institutes:Fachbereich 4 / Institut für Computervisualistik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
BKL-Classification:54 Informatik / 54.62 Datenstrukturen
54 Informatik / 54.73 Computergraphik
Licence (German):License LogoEs gilt das deutsche Urheberrecht: § 53 UrhG