Footprint Assembly

Footprint Assembly ist ein Algorithmus zum anisotropen Filtern von Texturen. Die Texturverzerrung kann dabei in jeder beliebigen Richtung berechnet werden. Außerdem lässt sich der Algorithmus gut mit Techniken wie MIP-Mapping, bilinearem oder trilinearem Filtern oder auch Integralbildern (Summed Area Tables) kombinieren.

Footprint

Ein Footprint ist die Projektion eines Pixels in das Koordinatensystem der Textur. Es wird angenommen, dass die Textur eine flache Oberfläche bespannt (dies ist bei Dreiecken immer der Fall). Der Footprint ist dann ein konvexes Viereck. Je genauer der Farbwert des Footprints berechnet werden kann, desto besser wird das resultierende Bild. Um Rechenaufwand zu sparen, wird der Footprint beim 'Footprint Assembly' nur angenähert.

Beim Footprint Assembly wird der Footprint vereinfachend als Parallelogramm angenommen. Hierzu wird der Pixelmittelpunkt in die Texturkoordinaten projiziert und gibt den Mittelpunkt des Parallelogramms an. Die Vektoren, die das Pixel entlang der beiden Hauptachsen aufspannen, werden ebenfalls in das Texturkoordinatensystem projiziert. Sie spannen nun das Parallelogramm auf.

Vielfach wird auch das Parallelogramm als Footprint bezeichnet.

Algorithmus

Es wird das Parallelogramm berechnet, das den Footprint annähert. Der Mittelpunkt heiße p.

Der kürzere der beiden Kantenvektoren gibt die Kantenlänge von Quadraten an, aus denen der Footprint berechnet werden soll. Die Quadrate lassen sich mit isotropen Filtern berechnen (meist MIP-Mapping mit bilinearem Filtern). Der längere der beiden Vektoren gibt einen Pfad an, entlang dem die quadratischen Flächen aufsummiert werden sollen.

Die Anzahl $N$ der Quadrate wird durch den Quotienten aus den Vektorlängen des längeren durch den kürzeren Vektor bestimmt und auf die nächste Zweierpotenz gerundet. Die Zweierpotenz ermöglicht ein leichteres Dividieren der Summe mittels Rechts-Shifts. Dann wird ein Schrittvektor $\Delta r$ konstruiert, der sich aus dem längeren Vektor ergibt, wenn man ihn mit ${\frac {1}{N}}$ skaliert. Die Punkte $p_{n}$, an denen abgetastet werden soll, ergeben sich aus $p_{n}=p+{\frac {n}{2}}\cdot \Delta r$ mit $n\in \{\pm 1,\pm 3,...,\pm (N-1)\}$. An diesen Punkten als Mittelpunkt wird jeweils der Farbwert eines der Quadrate berechnet. Die Farbwerte werden summiert und durch die Anzahl $N$ geteilt. Das Ergebnis ist die Annäherung des Footprint-Farbwertes und der Texturwert für das Pixel.

Weblinks

• Uni Frankfurt (PDF-Datei; 13,92 MB)
• A. Schilling, G.Knittel, W. Strasser: Texram, a Smart Memory for Texturing (Google Scholar)
• Patent US6236405B1: System and method for mapping textures onto surfaces of computer-generated objects. Angemeldet am 27. Juni 1997, veröffentlicht am 22. Mai 2001, Anmelder: S3 Graphics Co Ltd, Erfinder: Andreas Schilling, Guenther Knittel (Seite 13, Abschnitt Footprint-Assembly).‌