Cross-Product in 2d

Das Kreuzprodukt im R2 ist mathematisch nicht als Kreuzprodukt definiert. Anders als im R3 ordnet es zwei Vektoren ein Skalar zu. Es ist sehr nützlich um die Orientierung von 3 Punkten zu ermitteln. Hat man 3 Punkte A,B,C gegeben kann man ermitteln ob von A über B nach C ein Links- oder Rechtsknick ist. Das ist gleichbedeutend mit einer Abfolge der Punkte im Uhrzeigersinn (clockwise) oder gegen den Uhrzeigersinn (counter clockwise). Bildet man zwei Differenzvektoren von A zu B (B-A) und von A zu C (C-A), so ist deren Kreuzprodukt (B-A) x (C-A) positiv wenn A, B, C gegen den Uhrzeigersinn angeordnet sind. Ein negatives Kreuzprodukt bedeutet mit dem Uhrzeigersinn. Sind die 3 Punkte kollinear ist das Kreuzprodukt 0.

HLSL Shader in Visual C#

In Visual C++ ist es aber der Version 2012 möglich, das HLSL Shader Kompiliertool fxc.exe direkt für .hlsl Dateien zur Kompilierung innerhalb der IDE zu verwenden. HLSL Dateien, die dem Projekt hinzugefügt wurden können damit bequem automatisch kompiliert werden. In Visual C# funktioniert das bisher leider noch nicht. Um nicht dennoch für jede Shaderkompilierung über die CMD das Tool selbst aufzurufen, gibt es die Möglichkeit fxc.exe als externes Tool in der Visual Studio IDE hinzuzufügen. Das geschieht im Wesentlichen über Tools > Externe Tools. Eine detailierte Beschreibung hierzu bietet: Pixel Shaders and Silverlight, WPF.

Das Tool fxc.exe liegt normalerweise im lokal installierten DirectX SDK – bei mir: C:\Program Files (x86)\Microsoft DirectX SDK (June 2010)\Utilities\bin\x86. Wichtig: Die Argumente des externen Tools sollten wie folgt aussehen (leichte Änderung zum verlinkten Artikel):

/T ps_2_0 /E mainPS /Fo $(ItemDir)$(ItemFileName).ps $(ItemPath)

Die Parameter im Einzelnen: /T gibt das Zielprofil der Kompilierung an. Details bekommt man via fxc.exe /? . Der Einstiegspunkt des Shaders wird über /E angegeben und ist hier auf mainPS festgelegt. Die Ausgabedatei wird mit /Fo spezifiziert. Hier kann man schicke Visual Makros verwenden. In diesem Fall wird die Ausgabedatei gleich der Eingabedatei benannt, landet im selben Verzeichnis, trägt jedoch die Erweiterung ps. Das letzte Argument $(ItemPath) ist die eigentliche Eingabe für das fxc Tool, also die .fx Datei die direkt im Visual Studio kompiliert werden soll.

Normalen in Polygonnetzen

Eine Normale wird generell aus 3 beliebigen Eckpunkten (Vertices) eines Polygons (z.bsp. Dreieck) berechnet und zeigt die Ausrichtung dieses Polygons an. Man bildet die beiden Differenzvektoren zwischen diesen 3 Eckpunkten und errechnet mittels Kreuzprodukt den darauf senkrecht stehenden Vektor – die Normale. Polygone sollten in der Computergraphik immer planar sein, weshalb die Normale für das gesamte Polygon konstant ist.

Hat man den Normalenvektor der Ebene (in welcher das Polygon liegt) berechnet ist die Ausrichtung dieser Normalen wichtig: Eine Ebene teilt den 3dimensionalen Raum in zwei Halbräume und abhängig von den Eingabevektoren für das Kreuzprodukt erhält man eine Normale die in den einen oder in den anderen Halbraum zeigt. Die Normale n zeigt beispielsweise in den Halbraum A und -n zeigt dann in den Halbraum B.
Für die Definition einer mathematischen Ebene ist das völlig egal. Polygone haben jedoch eine sichtbare und eine nicht sichtbare Seite. Die Richtung der Normalen definiert welche Seite sichtbar ist. Dazu sollte einfach folgende Faustregel befolgt werden: Soll ein Polygon vom aktuellen Kamerastandpunkt aus sichtbar sein muss die Normale in die Richtung der Kamera zeigen. Schwammiger kann man das nicht ausdrücken :).

Das Kreuzprodukt bildet mit seinen beiden Operanden und dem resultierenden Normalenvektor ein Rechtssystem. Das bedeutet man kann die Situation mit der Drei-Finger-Regel der rechten Hand veranschaulichen.
Um nun die korrekte Normale (und nicht fälschlich die Inverse) des Polygons zu berechnen, wählt man die 3 Eckpunkte des Polygons gegen den Uhrzeigersinn (CCW counter clock wise) fortlaufend aus und bildet für das Kreuzprodukt die Differenzvektoren ebenfalls in dieser Reihenfolge:

public static Vector3D CalcNormal(Point3D p1, Point3D p2, Point3D p3)
{
	// we assume the points are in ccw order
	// construct two vectors from them (p1-->p2) and (p2-->p3) and make cross product 
	// to get normal pointing in the right direction (in right hand coordinate system)
	Vector3D n = Vector3D.CrossProduct(p2 - p1, p3 - p2);
	n.Normalize();
	return n;
}

Der Drehsinn ob mit oder gegen den Uhrzeigersinn hängt immer vom aktuellen Betrachterstandpunkt ab. Schaue ich auf ein Polygon und wähle Punkte gegen den Uhrzeigersinn folgend aus, erscheinen diese Punkte mit dem Uhrzeigersinn wenn ich von der entgegengesetzten Seite auf das Polygon schaue.

Per face or per vertex?

Mit dem oben beschriebenen Kreuzprodukt erhält man die Normale des gesamten Polygons (analog zur mathematischen Ebene). In einem Polygonnetz, in dem mehrere Flächen an den Vertices zusammenhängen kann es nun aber wichtig sein, die Normalen einzeln an den Vertices zu definieren und damit besser Schattierungsalgorithmen (Gouraud Shading, Phong Shading) nutzen zu können. Dabei ergibt sich die Normale eines Eckpunktes als gewichtete Summe der Normalen aller an diesem Eckpunkt angrenzenden Polygone. Diese Durchschnittsnormale ermöglicht feine Übergänge und die weiche Schattierung kurviger Oberflächen. Den harten Bruch in der Normalenrichtung an zwei benachbarten Polygonkanten eliminiert man damit. Die Vertices werden in diesem Anwendungsfall als shared vertices bezeichnet.

Ausgehend von der reinen Geometrie (ohne definierte Normalen) kann man die gemittelten Normalen jederzeit berechnen. Man benötigt jedoch Adjazenzinformationen des Polygonnetzes um bspw. alle an einem Eckpunkt angrenzenden Polygone zu ermitteln. Wurde die Geometrie importiert und vom 3d Artist sind die Vertex-Normalen bereits vorgegeben ist eine solche Berechnung nicht nötig/sinnvoll.

Neben den curved surfaces, die (trotz diskreter polygonaler Beschreibung) auch curved dargestellt werden sollen, gibt es natürlich Geometrien, bei denen die harten Kanten angrenzender Polygone erhalten bleiben sollen. Einfaches Beispiel: Ein Quader oder Würfel. Mittelt man hier die Normalen für jeden Eckpunkt der 6 Polygone kommt ein rundgelutschtes Gebilde raus. Hier hat tatsächlich jeder Vertex 3 verschiedene Normalenrichtungen, je nachdem zu welcher Fläche er gerade gehört bzw. welches Polygon zum Rendern abgerufen wird. Das Konzept der shared vertices funktioniert hier nicht.
Ich sehe zwei Lösungen für dieses Szenario:

1. Redundanz: Für jedes Polygon des Quaders werden 4 Vertices einzeln definiert, wobei die Normale der Fläche auch für jeden der Vertices gültig ist. Nachteil: Speicheraufwand für zusätzliche Punkte!
2. Indexierung: Vertices und Normalen werden einzeln indexiert um Polygone zu beschreiben. Eine Normale gehört jetzt zum Polygonnetz und nicht mehr direkt zum Vertex. Die Vertices und alle benötigten Normalen werden nur einmal abgelegt (unabhängig voneinander in getrennten Arrays/Listen etc.). Die Beschreibung eines Polygons indexiert dann die benötigten Vertices und Normalen.

OpenGL basiert im Kern immer auf der direkten Zugehörigkeit Vertex zu Normale (ebenso UV Koordinaten). Ein Vertex ist hier als Datenstruktur vorgesehen, die weitere Attribute direkt mit der Position des Vertex speichert. Hier lässt sich also letztendlich die redundante Bereitstellung der Daten nicht vermeiden und Vertices müssen doppelt definiert werden.

Gouraud und Co.

Die schickeren Schattierungsverfahren wie Gouraud und Phong benötigen Normalen an den Eckpunkten eines Polygones. Gouraud wertet dort die Beleuchtungsgleichung aus und interpoliert den Farbwert im Inneren des Polygons. Phong interpoliert die Normalen von den Eckpunkten ausgehend im Inneren und wertet für jeden Pixel einzeln die Beleuchtungsgleichung aus.
Für einen Quader sind hier sogar die Normalen per face ausreichend, da sie ebenfalls für die Eckpunkte gelten. Will man kurvige Flächen darstellen braucht man jedoch gemittelte Normalen für die shared vertices.

Ogre HLSL Shader

Man kann nur einen Fragment Shader zum Testen nutzen ohne selbst gebauten Vertex Shader. Das Material dazu kann so aussehen:

material shader/orange
{
technique
{
pass
{
fragment_program_ref shader/orangeFPHLSL
{
}
}
}
}

Das Target MUSS mit rein für jeden Shader. ACHTUNG: Bei Cg/GLSL wird die Eigenschaft profiles genannt statt target. Bei GLSL kann die profiles Angabe auch ganz raus gelassen werden.
ACHTUNG: VertexShader bekommt immer target vs_x_y und PixelShader immer target ps_x_y . z.bsp vs_3_0/ps_3_0 funktioniert gut.

Die Shader Definition …

fragment_program shader/orangeFPHLSL hlsl
{
source orangeshader.hlsl
entry_point main_fp
target ps_2_0
}
… und der Shader:

float4 main_fp() : COLOR
{
return float4(1.0, 0.0, 0.0, 1.0);
}

Wenn es nicht klappt: Die Ogre.log ist dein Freund – schau da rein.

Darauf achten, dass Ogre im richtigen Modus läuft: DirectX für HLSL, OpenGL für GLSL und bei Cg egal.

Kamera Projektion und Umkehrung der Projektion

Eine detaillierte Herleitung der OpenGL Projektionsmatrix für perspektivische und orthografische Projektionen findet man bei Songho.

Zum Verständnis der perspektivischen Projektion finde ich folgende Punkte wichtig.

Die Definition der Kamera erzeugt ein Frustum, ein Volumen, dass alle Punkte beinhaltet, die abgebildet werden können. Standardmäßig wird das Frustum durch die Near und Far Planes sowie den Öffnungswinkel der Kamera definiert. Alles was sich vor der Near Plane befindet (also näher zur Kamera) kann nicht dargestellt werden. Alles was sich hinter der Far Plane befindet wird ebenfalls nicht dargestellt. Die Far Plane legt in Blickrichtung die Grenze fest welche Objekte letztlich in der Ferne noch abgebildet werden sollen.
Die Seitenflächen des Frustums entstehen durch den Bereich der durch den Öffnungswinkel aufgespannt wird. Dabei gibt es sowohl einen Öffnungswinkel in X-Richtung als auch einen Öffnungswinkel in Y-Richtung. Normalerweise wird der Öffnungswinkel in Y-Richtung bei der Definition der Kamera angegeben (FOVy == field of view in y direction). Den Öffnungswinkel in X-Richtung kann man aus dem Seitenverhältnis der Kamera berechnen. Dieses Seitenverhältnis ergibt sich aus dem Verhältnis von Höhe zu Breite (oder umgekehrt, je nach Angabe) der Bildfläche.
Das Frustum einer Kamera kann auch hinreichend durch die Angabe von left, right, bottom, top Parametern definiert werden. Diese Parameter machen den Öffnungswinkel überflüssig müssen jedoch bei einer perspektivischen Kamera für die Near -und Far Plane angegeben werden. Da das aufwändiger ist, wird der Öffnungswinkel als Standardangabe vorgezogen.Alle diese Parameter werden im Kamerakoordinatensystem angegeben.

Die Bildfläche auf der die Abbildung der Kamera erfolgt ist die angegebene Near Plane n. Alle projizierten Bildpunkte erhalten damit die z-Koordinate -n.

Bei der perspektivischen Projektion eines Punktes p(x, y, z) wird p auf den Punkt p'(x‘, y‘, z‘) abgebildet. Der Punkt p‘ liegt auf der definierten Projektionsebene und entsteht im Schnittpunkt eines Strahls gebildet durch den Punkt p und den Koordinatenursprung mit der Projektionsebene. Der Punkt p wird quasi entlang dieses Strahls zum Koordinatenursprung hin bis auf die Projektionsebene verschoben. Die Projektionsebene ist hier generell parallel zur XY-Ebene und hat in rechtshändigen Kamerakoordinatensystemen einen negativen z-Wert. Die Blickrichtung der Kamera verläuft damit entlang der negativen z-Achse.

Die Projektion eines Punktes kann generell durch die Ähnlichkeit von Dreiecken berechnet werden. Durch die definierte Bildebene

Eine typische Projektionsmatrix überführt Punkte aus dem Kamerakoordinatensystem in das Clipping Koordinatensystem. Dieses Koordinatensystem wird gebraucht um effizient entscheiden zu können, ob ein Punkt innerhalb des Frustums liegt oder nicht.