Dieses Tutorial ist für Leute gedacht die, die ersten Gehversuche in der 3D Programmierung gemacht haben. Es beschreibt nicht unbedingt die Portal Technik (Verweise zu guten Tutorials darüber am Ende des Tutorials) sondern die Implementierung solcher. Ein Source Code für eine fertige Portal Engine + eines Exporters für Flexporter© liegt bei. Um diesem Tutorial folgen zu können, sollte man Kenntnisse in C++, 3D Mathematik und einer Grafik API haben.
Basics of Portal Rendering
Diesen Part will ich nicht allzu lang machen. Es gibt schon 1000nde Tutorials die das beschreiben (Verweise zu guten Tutorials darüber am Ende des Tutorials). Und das Konzept dahinter ist wirklich nicht schwer. In einer Portal Engine beschreibt man sein Level in Sectoren. Sectoren sind am optimalsten Räume. Diese Sektoren sind mit Portals verbunden. Beim Übergang von einem Sektor zum anderen Sektor sollten 2 Portals vorhanden sein, eins was zum Sektor A zeigt und eins was aus Sektor B sichtbar ist. Dieser Effekt ist später fürs View Frustrum clipping wichtig.
Dieses Level zeigt 3 Räume (Raum1, Gang, Raum2). Alle sind mit Portals verbunden. Es gibt insgesamt 4 Portals.
Our Portal Based Engine
Die Struktur in einer Engine um solche Daten halten zu können sollte in etwa so aussehen:
Class Sector
{
struct portal
{
Vertex* Vertices;
Int NumVertices;
Int PointingSector.
};
Vertex* Vertices;
Int NumVertices;
Portal* Portals;
Int NumPortals;
Int TravNum;
Static Int AllTravNum;
};
Ich habe zu diesem Tutorial ein sehr einfaches File Format geschrieben was gute Resultate bringen sollte. Am Ende des Tutorials steht genauer beschrieben wie diese Datei aufgebaut ist. Die Struktur im Beispielcode kommt der Struktur sehr nahe.
Man sieht klar, dass das Level in Sectoren aufgebaut ist. Alle Sectoren haben Vertices und Portale als Variablen. Die Vertices beschreiben die Geometrie des Levels. Die Portale beschreiben um Grunde auch nur Vertices und einen „Link“ in einen anderen Sector. Die Variablen TravNum und AllTravNum spielen gleich eine wichtige Rolle und ich werde darauf jetzt noch nicht eingehen.
Nun haben wir diese Daten in unserer Engine. Jetzt kommt es zum darstellen unseres Levels. Als erstes wollen wir herausfinden was sichtbar ist und was nicht. Unser Visibility Determinaion Code sieht so aus:
Int SectorTheCameraIsIn = getSectorId( CameraLocation );
If ( SectorTheCameraIsIn != -1 )
{
ViewFrustrum OurFrustrum = ViewFrustrum( FOV, WIDTH, HEIGHT, CameraLocation );
Sector* SectorCameraIsIn = getSector( SectorTheCameraIsIn );
PortalRecurse( SectorCameraIsIn, OurFrustrum );
}
else
{
TraverseAll( );
}
So, der wichtige Teil ist eigentlich nur PortalRecurse( … ). Diese Funktion geht vom Sector in dem wir drin sind und überprüft die verknüpften Sectoren ob diese sichtbar sind. Falls ja, wird die gleiche Prozedur mit den Sichtbaren Sectoren wiederholt.
PortalRecurse( Sector*CurrSector, FviewFrustrum& ViewFrustrum, bool bFirst )
{
DrawThisSector( );
If( bFirst )
{
Sector::AllTravNum++;
}
CurrSector->TravNum = Sector::AllTravNum;
For( alle Portals )
{
Sector* PointingSector = getSector( Portal.PointingTo );
If( PointingSector->TravNum == Sector::AllTravNum )
Continue;
If ( ViewFrustum.ClipVerts( Portal.Vertices, NeueVerts ) == Visible )
{
PortalRecurse( PointingSector, ViewFrustrum( ViewFrustrum.getLoc(), NeueVerts ) );
}
}
}
Die Portal Recursing Funktion malt erst mal den sichtbaren Sector und testet dann alle Portale auf Sichtbarkeit. Falls ein Portal sichtbar ist gucken wir ob der Sector, wo dieses Portal hinzeigt, schon verwendet wird. Falls nicht, erstellen wir eine neue View Frustum und überprüfen dann im nächsten Sector mit der gleichen Funktion ob dort wieder etwas sichtbar ist...
Jetzt gehen wir näher auf die Punkte ein. Der erste Schritt ist herauszufinden in welchem Sector wir uns gerade befinden.
In which Sector are we?
Dort gibt es sehr viele verschiedene Methoden. Die meisten fangen aber mit dem gleichen Schritt an: Da Sectoren alle eine Bounding Box besitzen können wir einfach die Position der Camera oder des Spielers gegen die Bounding Box testen und gucken ob wir außerhalb oder in der Bounding Box sind. Da dieser Bounding Box Test aber nicht immer 100% funktioniert und das Herausfinden in welchem Raum man wirklich ist relativ Mathe intensiv ist, habe ich lange drüber nachgedacht wie man das ganze optimieren kann. Mein bester Gedanke war, beim Laden vom Level herauszufinden in welchem Raum das Objekt ist und dann nach jedem Passieren eines Portals den Sector Index zu aktualisieren.
INFO: In der Beispiel Engine wird nur ein simpler Bounding Box Test durchgeführt.
Der nächste Punkt im Code ist das erstellen der View Frustum aus der View Matrix (Camera).
How to create a View Frustum out of an View Matrix
Eigentlich sollte dieser Punkt jedem klar sein. Der noch nicht weiß wie man eine solche View Frustum erstellt guckt am besten in seinen Lieblingsforen. Dort sind einige Threads die das erklären. Eine Suche mit Google reicht auch aus.
Jetzt kommt der Hauptpart: Das durchgehen der Sectoren.
How to do a Traversal right
Das Grundprinzip der Funktion sollte oben aus dem Pseudocode klar geworden sein. Ich gehe aber trotzdem noch auf einige Punkte genauer ein. DrawThisSector() steht einfach für das malen des Sectors. Das heisst jeder Sector der in dieser Funktion aufgerufen wird, wird auch gemalt. Um sicherzustellen das Sectoren nicht mehrmals oder es eine Endlosschleife gibt habe ich noch 2 Variablen für das Durchgehen der Funktion deklariert. Das wäre einmal TravNum und AllTravNum. Wie der Name schon sagt ist TravNum eine Variable für jeden Sector und AllTravNum eine Variable für alle Sectoren. Bei jedem Durchgang des Tests wird die globale Traversal Nummer erhöht und alle Sectoren werden dieser angepasst. So kann ich zum späteren Zeitpunkt gucken ob der Sector in diesem Durchgang schon benutzt wurde. Der nächste Punkt sollte klar sein. Um alle Ausgänge des Raumes zu testen gehen wir alle Portale durch. Jetzt kommt der etwas komplexere Teil und auch schon der Höhepunkt im ganzen Portal Rendering Part. Wir passen die View Frustum dem Portal an:
Gelb + Grün = Original View Frustum; Grün = Frustum nach Portal Clipping
Der gelbe und Grüne bereich umfasst die View Frustum der View Matrix (Camera). Nach dem Clippen gegen das Portal besteht nur noch der Grüne bereich. Nun, wie clippt man nun die View Frustum. Dieser Vorgang ist nicht allzu schwer aber auch nicht ganz einfach. Was wir machen ist: Wir testen alle Polygone gegen die Planes der View Frustum und bekommen dann eine Liste von Polygonen/Points die in der Frustum sind, zudem erstellen wir beim Clippen neue Polygone wo das Portal die Planes schneidet. So bekommen wir im Beispiel oben die Polygone an der oberen Seite zurück und es werden am Grünen unteren Rand neue erstellt. So haben wir schon genau den Umfang der View Frustum an dieser Stelle. Um jetzt daraus ein neues View Frustum zu erstellen nehmen wir nur noch die Position des Objektes und bilden daraus auf jeder Seite eine Plane. Der letzte Schritt ist jetzt nur noch die gleiche Traversal Funktion für den nächsten Raum mit der neuen View Frustum aufzurufen.
Das war es schon.... deine erste Portal Engine ist fertig.
Epilogue
Ich wollte noch so einige Sachen los werden. Das ist mein erstes Tutorial also seid lieb zu mir =). Für Kritik, Anregungen, Verbesserungen bin ich sehr dankbar. Ich selber habe das Portal Thema durch das Buch Advanced 3D Game Programming using DirectX gelernt und habe auch einige Programm strukturen dannach gerichtet. Mir haben aber noch andere Seiten geholfen das ganze zu verstehen und es einzubauen. Falls ihr noch Fragen usw. habt schreibt mir bitte eine Email an: lutz_hoeren@gmx.net
Thanks to
Ich möchte mich bei einigen Leuten bedanken. Die Leute die hier genannt werden sind wirklich hilfsbereit und haben sich diesen Dank wirklich verdient. Als erstes Danke ich Joscha „Yoshi“ Metze der mir wohl so einige Bugs entfernt hat und mich immer Unterstützt bei dem was ich mache. Zudem Danke ich Phantom, Besux und norebo für die Hilfe bei dem ganzen Projekt.
References:
Portal Tutorials:
http://www.fairyengine.com/articles/portals.htm -> © Fairy Engine
http://polygone.flipcode.com/tut_portal.htm -> © Tobias Johansson
PortalEngine.zip
File Format
Number of Sectors ( int )
Number of Objects ( int )
For( Number of Sectors )
{
Number of Vertices (WORD)
Number of Triangles (WORD)
Number of Render Structs (WORD)
Number of Portals
For( Number of Vertices )
{
x,y,z,tu,tv (5 * float)
}
For( Number of Triangles )
{
Indices ( 3 * word )
Texture ( 80 * char )
}
For( Number of Render Structs )
{
Number of Indices (WORD)
Texture ( 80 * char )
}
For( Number of Portals )
{
Number of Vertices (WORD)
Pointing Cell ( INT )
For( Number of Vertices )
{
x,y,z (float*3)
}
}
}
For( Number of Objects )
{
Number of Vertices (WORD)
Number of Triangles (WORD)
Number of Render Structs (WORD)
Position (float*3)
Rotation (float*4)
Sector Index (int)
For( Number of Vertices )
{
x,y,z,tu,tv (float*5)
}
For( Number of Triangles )
{
Indices ( 3 * word )
Texture ( 80 * char )
}
For( Number of Render Structs )
{
Number of Indices (WORD)
Texture ( 80 * char )
}
}