Effiziente Lösungsverfahren für Sichtbarkeitsprobleme in der realitätsnahen Bildsynthese

Abstract

Eine prinzipielle Schwierigkeit bei der Bildsynthese ist die Sichtbarkeitsbestimmung. Sie nimmt einen grossen Anteil des Rechenaufwands praktisch aller heutigen Verfahren ein. In dieser Dissertation werden Sichtbarkeitsprobleme in anderen Ausprägungen als der üblichen Sichtbarkeit von einem Punkt aus betrachtet, nämlich wie sie etwa beim hierarchischen Radiosity-Verfahren auftreten. Als Hauptproblem wird die Berechnung der Sichtbarkeitsmenge zweier Elemente behandelt. Dieses besteht darin, eine gegebene Szene von Elementen so in eine Datenstruktur vorzuverarbeiten, dass die Sichtbarkeit zwischen zwei disjunkten Elementen a und b (desselben Typs und disjunkt vom Rest der Szene) effizient bestimmt werden kann.

Dieses Problem wird zunächst im Hinblick auf eine worst-case-effiziente, exakte Lösung betrachtet. Auf der Grundlage von Datenstrukturen zur Halbraumanfrage wird eine Lösung präsentiert, die eine Anfrage asymptotisch schneller als durch systematisches Testen, d.h. in sublinearer Zeit in der Szenengrösse, beantwortet und dabei mit nahezu linearem Speicherplatzbedarf auskommt.

Begründet durch die bekannte Beobachtung, dass sich Sichtbarkeitsprobleme trotz ihres unangenehmen Verhaltens im schlechtesten Fall heuristisch gut lösen lassen, konzentriert sich die Arbeit dann auf diesen Aspekt. Als ein Lösungsvorschlag werden zunächst hierarchische Verdeckungsbäume eingeführt. Sie erlauben einen Trade-off zwischen Speicherbedarf und Rechenzeit sowie Exaktheit der Lösung.

Als ganz anderer Zugang wird dann eine Lösung durch Abtastung entwickelt, die sich auch auf andere Anfrageprobleme übertragen lässt. In einem Vorverarbeitungsschritt werden Abtastanfragen zusammen mit ihren Antworten in einer Antwortdatenbank gespeichert. Aus diesen Abtastanfragen werden zur Laufzeit für beliebige Anfragen Antworten (re)konstruiert. Es werden worst-case-Schranken für Laufzeit und Speicherbedarf der Datenstruktur für die Abtastanfragen in Abhängigkeit von einem vorgegebenen Fehler hergeleitet. Dabei werden die zwangsläufig auftretenden Fragen der Stichprobenanfragen und der Komprimierung der Stichprobenantworten behandelt.