Logo
 Universitaet Koblenz-Landau Arbeitsgruppe Computergraphik
Home
 Mitarbeiter
 Kontakt
 Veranstaltungen
 Studienarbeiten
 Jobs
 Publikationen

Freeform - Lightstage

Thorsten Grosch

Wintersemester 2003/2004

[ Übersicht & Beschreibung | Hauptprogramm-Beschreibung | Rekonstruktion der Beleuchtungsrichtung | Voronoi-Diagramm auf der Kugel | Ergebnisbilder ]
blue line

Konstruktion eines Voronoi-Diagramms auf einer Kugel

Aufgabe und Anforderungen

Nachdem die Beleuchtungsrichtungen aus den aufgenommenen Bildern rekonstruiert wurden, ist der letzte Schritt die Wiederbeleuchtung des Objekts. Um das Objekt korrekt neu zu beleuchten, wird das gesamte Licht der oberen Hemisphäre der Environment Map genutzt. Das Licht der Lightmap wird dabei auf die rekonstruierten Lichtrichtungen verteilt. Jedem Pixel der Lightmap wird die Beleuchtungsrichtung zugeordnet, die ihm am nächsten liegt. Dabei wird folgendermaßen vorgegangen:
Jede einzelne rekonstruierte Lichtrichtung wird auf die Hemisphäre der Kugel aufgetragen. Aus dieser Menge von Punkten kann ein Voronoi-Diagramm auf einer Kugel konstruiert werden, indem die Winkel zwischen den Beleuchtungsrichtungen das Distanz-Kriterium sind. Als Ergebnis erhält man für jede Beleuchtungsrichtung eine Voronoi-Zelle, die all das Licht der Environment Map enthält, das der jeweiligen Beleuchtungsrichtung am nächsten liegt. Am Schluß wird das Licht innerhalb jeder Voronoi-Zelle integriert und der resultierende Radiance-Wert wird als Gewicht für das zugehörige Basisbild genutzt. Die Konstruktion des Voronoi-Diagramms auf der Kugel hat dabei die Vorteile, daß sie einerseits von den Parametern der Repräsentation der Environment Map unabhängig ist und andererseits Nachbarschaftsbeziehungen bereitstellt, um die Integration des Lichts in den Voronoi-Zellen zu vereinfachen. Für den Aufbau des Voronoi-Diagramms gibt es im Wesentlichen zwei unterschiedliche Ansätze. Die erste Lösung ist einfach zu implementieren, aber sehr zeitaufwendig in der Ausführung. Die zweite Möglichkeit ist, einen komplexen Algorithmus zu implementieren, der den Zeitaufwand für den Aufbau des Voronoi-Diagramms minimiert.

Voronoi-Diagramm allgemein

Ein Voronoi-Diagramm besteht aus generierenden Punkten, generierten Kanten und Ecken. Die generierenden Punkte (cell points) erzeugen die Ecken (voronoi corner) und die Kanten. Die jeweils zu einem generierendem Punkt zugeordneten Kanten (dies sind im Kugelfall Bögen) bilden ein sogenanntes kugelförmiges Voronoi-Polygon.
Allgemeines Voronoi-Netz

Implementation des einfachen Algorithmus (O(N²))

Der Algorithmus erzeugt ein Bild, welches dieselben Abmessungen (Höhe x Breite) wie die später verwendete Lightprobe hat. Es wird für jeden Pixel des Bildes berechnet, in welche Voronoi-Zelle das jeweilige Pixel fällt. Die x-z-Ebene ist die Bildebene. D.h. für jeden Pixel wird ein Richtungsvektor bestimmt (x, Abstand vom Mittelpunkt, z) und mit allen Richtungsvektoren "verglichen". Dieser Vergleich beeinhaltet die Berechnung des Raumwinkels zu den einzelnen Lichtrichtungen. Ist der kleinste Raumwinkel gefunden, wird das jeweilige Pixel mit einer eineindeutigen Farbe zugehörig zur jeweiligen Lichtrichtung eingefärbt. Dieser Vorgang wird für alle Pixel wiederholt und erzeugt als Ergebnis die Aufsicht auf eine korrekt unterteilte Kugel. Da der Versuchaufbau der FreeFormLightStage nur die obere Hemisphere zulässt, wird hier die Aufsicht auf die obere Hemisphere generiert.

Implementation des komplexen Algorithmus (O(N(log N)))

Vorteil des Algorithmus ist die schrittweise Integration von sogenannten generierenden Punkten (entsprechen den Lichtrichtungen) in das bestehende Voronoi-Diagramm. Dadurch ergibt sich der Vorteil, dass nicht das gesamte Netz auf einmal berrechnet werden, muß sondern nur sich verändernde Teile neu berechnet bzw. hinzugefügt werden.

Voraussetzungen

Die Berechnung erfordert eine bestimmt Datenstruktur die auf Dreiernachbarschaften beruht. Es wird davon ausgegangen, dass eine Ecke des Voronoi-Netzes immer genau drei benachbarte Ecken besitzt. Jede dieser Ecken wird aus drei generierenden Punkten erzeugt. Dabei sind die Ecken und die generierenden Punkte folgendermaßen angeordnet:
Orientierung der Ecken und generierenden Punkte
Hierbei sind C die Ecken des Netzes und P die generienden Punkte bzw. Lichtrichtungen. Die generierenden Punkte einer Ecke sind immer entgegen des Urzeigersinns angeordnet. Genauso sind die drei benachbarten Ecken einer Ecke ebenfalls entgegen des Urzeigersinns angegeben. Diese Anordnung führt dazu, dass z.B. P1(erster generierender Punkt der Ecke C) und C1 (erster Nachbar der Ecke C) gegenüber liegen. Ebenso die anderen Paare P und C.

Initialisierung des Algorithmus

Vier der gerade angesprochenen generierenden Punkte werden für die Initialisierung des Voronoi-Netzes benötigt. Dabei schneiden jeweils drei Punkte eine Kugelkappe aus und generieren in dessen Zentrum eine Voronoi-Ecke.
Kugelkappenschnitt
Dieser Vorgang wird wiederholt (bei 4 initial generienden Punkte also 4 mal) und erzeugt so vier initiale Voronoi-Ecken, die miteinander verbunden, das intiale Voronoi-Netz auf der Kugel ergeben. Dieser Vorgang ergibt z.B. folgendes Bild:

Initiales Voronoi-Netz
Mit inital einbeschrieben Tetraeder (gleichmäßige Anordnung der generierenden Punkte) ergibt sich folgendes Bild:
Initiales Voronoi-Netz

Einfügen eines neuen generierenden Punktes

Nach der Initialisierung können die generienden Punkte schrittweise einzeln hinzugefügt werden. Hierbei durchläuft der Algorithmus die folgenen Arbeitsschritte:
  1. Einfügen eines generierenden Punktes (Lichtrichtung auf die Kugeloberfläche skaliert)
  2. Suche nach einer gebrochenen Ecke
  3. Suche nach allen gebrochenen Ecken
  4. Finde alle Kanten, die gebrochenen Ecken und ungebrochene Ecken verbinden. Auf jeder dieser Kanten liegt genau eine neue Ecke
  5. Erzeuge die Kanten des kugelförmigen Polygons P durch verbinden der entsprechenden Eckenpaare
Beim Hinzufügen einer Lichtrichtung werden zwangsläufig einige der bisherigen Voronoi-Ecken (bzw. die zugehörigen Zellen) zerstört und durch neue ersetzt. Diese interessanten Bereiche gilt es zu finden und neue Ecken zu generieren. Hierfür wird ein Kriterium benutzt, welches überprüft, ob eine Ecke durch eine neu hinzugefügte Lichtrichtung gebrochen wird. Der Vorteil des Algorithmus besteht darin, dass alle defekten Ecken direkt benachbart sind, also eine zusammenhängende Menge bilden. Hat man eine defekte Ecke gefunden, sind die eventuell vorhandenen anderen Ecken ohne großen Aufwand auffindbar. Danach werden die neuen Ecken aufgrund weiterer Kriterien generiert, ihnen ihre generierenden Punkte und ihre neuen Nachbarn zugeordnet, sowie an den nicht gebrochenen Ecken die eventuell geänderten Nachbarn aktualisiert. Dadurch sollte immer die oben angegebene Datenstruktur erhalten bleiben.

Fazit

Leider ist es nicht gelungen, den komplexen Algorithmus innerhalb der Zeitvorgabe des Praktikums fehlerfrei zu implementieren. Daher basiert das Voronoi-Daigramm der FreeFormLightStage auf dem einfachen, aber sehr zeitaufwendigen Algorithmus. Die für die Visualisierung benutzten Bilder (mit Falschfarben für die Voronoi-Zellen und Lichtrichtungen als schwarze Punkte) unterscheiden sich von den für die interne Berechnung benutzten nur durch die verwendeten Farben.

FalseColor-Voronoi-Netz TrueColor-Voronoi-Netz

Quellenangabe

  1. On the Construction of the Voronoi Mesh on a Sphere, Jeffrey M. Augenbaum and Charles S. Peskin, Journal of Computational Physics 59, 177-192 (1985)
  2. The Free-form Light Stage, Vincent Masselus, Philip Dutré, Frederik Anrys, Thirteenth Eurographics Workshop on Rendering (2002)
  3. Acquiring the Reflectance Field of a Human Face, Paul Debevec, Tim Hawkins, Chris Tchou, Haarm-Pieter Duiker, Westley Sarokin, Mark Sagar, SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series pages 145-156. ACM SIGGRAPH, Addison-Wesley, July 2000.