Die Theorie zum Verfahren wie eine Landschaft möglichst optimal in einem 3D Drahtgittermodell aus Dreiecken aufgebaut werden kann haben wir nun beleuchtet. Nun gillt es dies in eine funktionierende PSP Implementierung umzusetzen. Dies wird nun geschehen.Soar-Terrain Klasse

Basierend auf der bereits erstellten Terrain-Klasse die es ermöglicht aus einer PNG-Höhengrafik ein einfaches 3D Dreiecksobjekt zu erstellen, werden wir nun die SOAR Implementierung vornehmen. Dazu legen wir eine neue Klasse an die die genannte erweitert. Entgegen der sonst üblichen Art werde ich hier das komplette Klassen-Headerfile als ganzes zeigen. Auch wenn dies einige Fragen aufwirft. Es lässt sich nur schwer in Teile zerhacken. Die Einzelheiten die PSP speziefisch sind, werden im Rahmen der Implementierung der einzelnen Methoden nochmals kurz erläutert.

/*
 * GuSoarTerrain.h Implementierung einer SOAR basierten Landschaft
 *                 Für die Berechnung des Drahtfitters wird ein LOD Algorythmus verwendet.
 */                 

#ifndef GUSOARTERRAIN_H_
#define GUSOARTERRAIN_H_                 

extern "C"{
#include <pspgu.h>
}
#include "GuTerrain.h"                 

/***************************************************************************************
 * Definition von Macros zur einfachen Arbeit mit dem Index
 ***************************************************************************************/
#define LINEAR_COUNT(n)	          ((1 << ((n) >> 1))+1)*((1 << ((n) >> 1))+1)
#define LINEAR_INDEX(i, j, level) ((i)+(j)+((j)<<(level)))                 

#define I_SW(level)      LINEAR_INDEX(0           , 0, (level))
#define I_SE(level)      LINEAR_INDEX(1 << (level), 0, (level))
#define I_NE(level)      LINEAR_INDEX(1 << (level), 1 << (level), (level))
#define I_NW(level)      LINEAR_INDEX(0, 1 << (level), (level))
#define I_C(level)       LINEAR_INDEX(1 << ((level)-1), 1 << ((level)-1), level)                 

/***************************************************************************************
 * hilfreiche Definitionen um mit dem SOAR Algorythmus arbeiten zu können
 ***************************************************************************************/
#define INDEX_CAPACITY  0x100000 //initiale Anzahl Elemente in der Indexliste
/* SOAR Vertex Definition*/
typedef struct SoarVertex{
	ScePspFVector3 p;	//Position eines Landschaftspunktes im 3D Raum
	unsigned int   color; //Farbwert des Punktes
	float          e;   //Fehlerschwellenwert des Punktes
	float          r;   //Radius des Punktes der auch seine Kinder einschließt
}SoarVertex;                 

/* da der SOAR Algorythmus ausschließlich mit Indexwerten arbeitet hier
 * einen Typen dafür deklarieren
 */
typedef unsigned int SoarVertexId;             

/*
 * Struktur definieren, welche ein Dreieck mit seinen
 * 3 index Werten repräsentiert
 */
typedef struct SoarTriangle {
	SoarVertexId c, l, r; //die 3 Ecken- center, left, right
} SoarTriangle;                 

class ClGuSoarTerrain: public ClGuTerrain {
public:
	ClGuSoarTerrain(const char* heightMapFile);
	virtual ~ClGuSoarTerrain();                 

	/*
	 * Render Methode. Hier wird das Drahtgittermodell basierend
	 * auf den LOD Daten berechnet und dargestellt
	 */
	virtual void render();                 

protected:
	unsigned int soarWidth;
	unsigned short maxLevel; //Maximale Iterationstiefe bei der Teilung der Dreiecke
	SoarVertex* sv; //Liste der SOAR Punkte der Landschaft
	SoarVertexId* index; //SOAR Indexliste
	unsigned int indexCount;
	float errorTol;
	/*
	 * Diese Methoden erzeugen zunächst die SOAR Punkte basierend auf dem höchst möglichen
	 * Detaillierungslevel und berechnet dabei für jeden punkt die für die LOD berechnung
	 * notwendigen Daten
	 */
	virtual void generateMesh();
	virtual void meshLodCompute(SoarVertex* vList, unsigned short levels);
	virtual void vertexLodCompute(SoarVertex* vList,
			                      unsigned short x,    //aktuelle Spalte
			                      unsigned short y,    //aktuelle Zeile
			                      short dx,            // Differenz zur nächten Teilung
			                      short dy,
			                      unsigned int width); //breite des aktuellen Levels minus 1 (0 für das letzte Level)                 

	/*
	 * Basierend auf den LOD daten wird hier nun das neue Drahtgittermodell in form einer Index-Liste
	 * aufgebaut
	 */
	virtual void meshRefine(SoarVertex* vList, unsigned short refineLevels, unsigned short visibility);
	virtual SoarVertexId* refineSubMesh(SoarVertexId* idx, SoarVertex* vList, unsigned short level, SoarTriangle* triangle);               

	virtual bool isVertexActive(SoarVertex* vertex);
	/*
	 * Hilfreiche Hilfsmethoden zum Aufbau der Indexliste
	 */
	SoarVertexId* soarIndexBegin(SoarVertexId* iList, SoarVertexId id, bool parity);
	SoarVertexId* soarIndexAppend(SoarVertexId* iList, SoarVertexId id, bool parity);
	unsigned int  soarIndexEnd(SoarVertexId* iList, SoarVertexId id);
};
#endif /* GUSOARTERRAIN_H_ */

Kommen wir nun zur Implementierung. Der Konstruktor wird nur soweit angepasst, dass der Super-Klassen Konstruktor aufgerufen wird. Dieser lädt ja die PNG Datei und stellt die Daten bereit. Es muss hier nur der Speicherplatz für die Aufnahme der Indexliste reserviert und ein Initialer Wert für den Fehlerschwellwertfaktor eingegeben werdenwerden.

/*
 * GuSoarTerrain.cpp
 */         

extern "C"{
#include <malloc.h>
#include <math.h>
#include <pspgu.h>
#include <pspgum.h>
#include <pspctrl.h>
}
#include "GuSoarTerrain.h"
#include "GuLandscapeApp.h"         

ClGuSoarTerrain::ClGuSoarTerrain(const char* heightMapFile)
                :ClGuTerrain(heightMapFile){
	//Erzeugen der Instanz basierend auf der SUperklasse
	//Um die Indexliste aufbauen zu können müssen wir hier den
	//Speicher reservieren. Der maximale Speicherplatz sollte dabei
	//nicht ausgenutzt bzw. überschritten werden.
	this->index = (SoarVertexId*)malloc(INDEX_CAPACITY*sizeof(SoarVertexId));
	errorTol = 64.0f;
}

Der nächste Schritt ist die Erzeugung der Daten des Terrains in der SOAR Vertex struktur. Also auf größter Detaillierungsebene werden die Punkte in einen Puffer gestellt und Ihre LOD Attribute errechnet.

void ClGuSoarTerrain::generateMesh(){
	//Bevor wir die LOD daten bestimmen können, müssen wir das
	//Detaillierungslevel berechnen das dem Allgorythmus zugrundegelegt wird.
	//Das bedeutet im Grunde, wie oft kann das Terrain in 2 hälften geteilt werden.
	unsigned short levels;
	for (levels = 0; ((1u << levels)+1) < this->width;levels++);
	unsigned int n = (1u << levels)+1;
	levels*=2;
	maxLevel=levels;        

	//Basierend auf der Anzahl der Detailierungsebene den Speicherbedarf bestimmen
	unsigned int memory = sizeof(SoarVertex)*LINEAR_COUNT(levels);
	sv = (SoarVertex*)malloc(memory);
	//nun das 2D Arry mit den VertexDaten erzeugen
	for (int y=0;y<height;y++){
		for (int x=0;x<width;x++){
			sv[x+y*n].p.x = this->terrainPoints[x+y*width].x*4;
			sv[x+y*n].p.z = this->terrainPoints[x+y*width].y*4;
			sv[x+y*n].p.y = (this->terrainPoints[x+y*width].height / 4.0f) - 60.0f;
			sv[x+y*n].color = this->terrainPoints[x+y*width].color;
		}
	}        

	//Sollte die Höhenkarte in Ihren Maßen nicht ein potenz von 2 + 1 sein,
 	//dann müssen die Randpunkte bis zu dieser Breite geklont werden um
	//die einfach Funktionsweise beizubehalten.
	if (this->width < n || this->height < n){
		//Werte am rechten Ende kopieren
		for (int y=0;y<height;y++) {
			for (int x=width;x<n;x++){
				sv[x+y*n].p = sv[width-1+y*n].p;
			}
		}
		//Werte am unteren Ende kopieren
		for (int x=0;x<width;x++){
			for (int y=height;y<n;y++){
				sv[x+y*n].p = sv[x+(height-1)*n].p;
			}
		}
		//Übrigen Punkte diagonal kopieren
		for (int y=height;y<n;y++){
			for (int x=width;x<n;x++){
				sv[x+y*n].p = sv[(width-1)+(height-1)*n].p;
			}
		}
	}        

	//Speichern der realen Breite des 2D Landschaftsarrays
	soarWidth = n;
	//Nun können wir die LOD Daten berechnen
	meshLodCompute(sv, levels);
}

Die nächste Methode berechnet nun für alle Punkte der Landschaft die LOD Daten.

void ClGuSoarTerrain::meshLodCompute(SoarVertex *vList, unsigned short  levels){
	/*
	 * Der Fehlerschwellenwert und der Umspannende Radius werden Schritt für Schritt
	 * von unten nach oben berechnet. Die Annahme ist dabei, dass vertexList ein
	 * 2D Array repräsentiert  abgelegt als einfache Liste. Für die Berechnung der
	 * LOD-Daten gehen wir von einem sogenannten Quad-Tree Mechanismus aus.
	 */
	unsigned int   maxWidth = (1u << (levels >> 1));
	unsigned int maxWidthHalf = maxWidth >> 1;     

	unsigned short i,j,s;
	short          a,b,c;     

	for (a = c = 1, b = 2, s = 0;(unsigned)a != maxWidth; a = c = b, b*=2, s = maxWidth){
		/*
		 * zuerst den "black" QuadTree betrachten.
		 * Punkte sind hier die "x" im folgende Schema
		 *
		 * o x o o
		 * x o x o
		 * o x o o
		 * o o o o
		 */
		for (j=a;j<maxWidth;j+=b){
			for (i=0;i<=maxWidth;i+=b){
				//Berechne LOD daten für diese Punkte
				vertexLodCompute(vList,i,j,0,a,s);
				vertexLodCompute(vList,j,i,a,0,s);
			}
		}     

		/*
		 * im zweiten Schritt den "white" QuadTree
		 *
		 * x o x o
		 * o o o o
		 * x o x o
		 * o o o o
		 */
		for (j=a;j<maxWidth;c=-c,j+=b){
			for(i=a;i<maxWidth;c=-c,i+=b){
				//Berechne LOD daten für diesen Punkt
				vertexLodCompute(vList,i,j,a,c,maxWidth);
			}
		}     

	}     

	//Nun haben wir alle LOD daten berechnet. Um sicherzustellen, dass bestimmte Fixpunkte nich
	//weg optimiert werden, diese auf "Unendliche"-Werte setzen
	vList[0].e = vList[maxWidth].e = vList[maxWidth*soarWidth].e = vList[maxWidth+maxWidth*soarWidth].e = vList[maxWidthHalf+maxWidthHalf*soarWidth].e = 99999999.9f;
	vList[0].r = vList[maxWidth].r = vList[maxWidth*soarWidth].r = vList[maxWidth+maxWidth*soarWidth].r = vList[maxWidthHalf+maxWidthHalf*soarWidth].r = 99999999.9f;
}

Die eben gezeigte Methode ruft nun die eigentliche Berechnungsroutine für den Fehlerschwellenwert etc. auf.

void ClGuSoarTerrain::vertexLodCompute(SoarVertex *vList, unsigned short  x, unsigned short  y, short  dx, short  dy, unsigned int width){
// LOD Daten für diesen Vertex berechnen
	SoarVertex* current = &vList[x+soarWidth*y];
	SoarVertex* topLeft = &vList[x-dx + (y-dy)*soarWidth];
	SoarVertex* bottomRight = &vList[x+dx + (y+dy)*soarWidth];   

	/*
	 * Berechnung der Fehlerschwellenwertes. Er ist die Differenz zwischen der Höhe des
	 * aktuellen Punktes und der Berechneten Höhe der Halbstrecke der 2 Eckpunkte
	 * Der initiale Radius den ein Vertex umspannt is 0
	 */
	current->e = fabsf(current->p.y - (0.5f * (topLeft->p.y + bottomRight->p.y)));   

	/*
	 * Wenn der aktuelle Vertex nicht der höchsten Detailierungseben entspricht
	 * (Leaf-Node), dann den Fehlerwert und den Radius so berechnen, dass dieser die
	 * darunterliegende Vertexe berücksichtigt.
	 * Der Radius muss dabei groß genug sein um alle Kinder zu umspannen.
	 */
	if (width){
		/*
		 * Prüfen der Kinder des aktuellen Vertex. (+dx, +dy) und (-dx, -dy) liefern uns die Eckpunkte
		 * des "Vater"-Dreiecks auf dessen halbierter Seite der aktuelle Punkt liegt.
		 * durch "Rotation" der Punkte um gedachte 45° kommen wir zu den jeweiligen
		 * Kindern.
		 */
		int tdy = (dx+dy) / 2; //1. Kinderecke tdx, tdy
		int tdx = dx-tdy;
		int edges = 4; //4 Kinder
		do {
			//Prüfen ob die Kinder ausserhalb des Randes liegen
			if ((x!=0 || tdx >= 0) && (x!=width || tdx <= 0) &&
				(y!=0 || tdy >= 0) && (y!=width || tdy <= 0)){   

				SoarVertex* child = &vList[x+tdx+(y+tdy)*soarWidth];
				current->e = current->e > child->e? current->e:child->e;   

				//Radius ist der Abstand vom Punkt zum Kind
				float dist;
				dist = (current->p.x - child->p.x)*(current->p.x - child->p.x);
				dist+= (current->p.y - child->p.y)*(current->p.y - child->p.y);
				dist+= (current->p.z - child->p.z)*(current->p.z - child->p.z);
				dist = sqrtf(dist) + child->r;   

				current->r = current->r > dist?current->r:dist;   

				//nun "rotieren" dx/dy um 90° um zur nächsten Ecke zu gelangen
				//tdx' = -tdy
				//tdy' = +tdx
				tdy+=tdx;
				tdx-=tdy;
				tdy+=tdx;
			}
		} while(--edges); //für alle 4 Ecken...   

	}
}

Die bis hier dargestellten Methoden bilden Quasi den Pre-Processing Teil ab. Hier werden die Normalen Daten einer 2D Höhenkarte genutzt und um LOD Daten angereichert. Dieser gesammte Teil kann auch noch zusätzlich ausgelagert werden, so dass diese Berechnung Beispielsweise in einem “normalen” PC Programm stattfindet und eine Datei erzeugt die dann von der PSP nur noch geladen wird. Das hat den Vorteil, dass die doch recht Zeitintensive Vorberechnung der Daten nicht auf der PSP stattfindet und damit die Ladezeiten für ein Level/Spiel verkürzt.
Der nächste Teil wird sich nun um die Berechnung des Drahtgitters widmen, bei dem der SOAR Allgorythmus zur Anwendung kommt. Diese Berechnung findet im Grunde jedesmal statt, wenn die Landschaft neu auf dem Bildschirm dargestellt werden soll.

Das SOAR Refinement

Wir starten mit der Unterteilung unseres Gebietes in 4 Dreiecke und geben diese einzeln in das Refinement:

void ClGuSoarTerrain::meshRefine(SoarVertex *vList, unsigned short refineLevels, unsigned short visibility){
	SoarVertexId* idx;  

	//Das Refinement liefert ein Indexliste. Der erste Eintrag ist die erste Ecke
	unsigned short nextLevel = refineLevels >> 1;
	idx = soarIndexBegin(index, I_SW(nextLevel), true);
	//Das erste Dreieck
	SoarTriangle tri;
	tri.c = I_C(nextLevel);
	tri.l = I_SW(nextLevel);
	tri.r = I_SE(nextLevel);
	//Das erste Dreieck an das Refinement übergeben
	idx = refineSubMesh(idx, vList, refineLevels - 1, &tri);
	//nun die nächste Ecke an den Index ran
	idx = soarIndexAppend(idx, I_SE(nextLevel), false);
	//das zweite Dreieck
	tri.l = I_SE(nextLevel);
	tri.r = I_NE(nextLevel);
	//Refinement des zweiten Dreiecks
	idx = refineSubMesh(idx, vList, refineLevels - 1 , &tri);  

	//Nun die nächste Ecke zum Index dazu
	idx = soarIndexAppend(idx, I_NE(nextLevel), false);
	//Das dritte Dreieck definieren
	tri.l = I_NE(nextLevel);
	tri.r = I_NW(nextLevel);
	//Auch dieses wird nun unterteilt
	idx = refineSubMesh(idx, vList, refineLevels - 1 , &tri);  

	//Nun die 4. Ecke in die Indexliste
	idx = soarIndexAppend(idx, I_NW(nextLevel), false);
	//Und das 4. und letzte Dreieck gebildet
	tri.l = I_NW(nextLevel);
	tri.r = I_SW(nextLevel);
	//Refinement des selbigen
	idx = refineSubMesh(idx, vList, refineLevels - 1 , &tri);  

	//Zum schluss den Startpunkt wieder zur Indexliste dazu
	indexCount = soarIndexEnd(idx, I_SW(nextLevel));
}

Das eigentliche Berechnen der Indexliste basierend auf einem Dreieck wird nun in der folgenden Methode durchgeführt. Ob ein Dreieck dabei erneut unterteilt werden muss/darf, wird dabei in einer separaten Methode geprüft.

/*
 * Unterteilen eines Dreiecks. Rückgabewert ist der Zeiger auf den letzten Eintrag in der aktuellen
 * Indexliste
 */
SoarVertexId *ClGuSoarTerrain::refineSubMesh(SoarVertexId *idx, SoarVertex *vList, unsigned short level, SoarTriangle *triangle){ 

	SoarVertexId* nIdx = idx;
	SoarVertexId bisec;
	// aktuelles Dreieck teilen
	// erstmal prüfen ob dies möglich ist
	bool refine = (level != 0);
	if (refine){
		bisec = (triangle->l + triangle->r) >> 1;
		//prüfen ob der Punkt der bei der Teilung entsteht aktiv ist
		//also anhand der Fehlerschwellwerte das Dreieck teilen darf
		refine = isVertexActive(vList+bisec);
	} 

	if (refine){
		//Teilung darf durchgeführt werden, die beiden neuen Dreiecke
		//weiderum teilen
		SoarTriangle newTri;
		newTri.c = bisec;
		newTri.l = triangle->l;
		newTri.r = triangle->c;
		nIdx = refineSubMesh(nIdx, vList,level -1, &newTri);
	}
	nIdx = this->soarIndexAppend(nIdx, triangle->c, level & 1);
	if (refine){
		//refine the new right triangle
		SoarTriangle newTri;
		newTri.c = bisec;
		newTri.l = triangle->c;
		newTri.r = triangle->r;
		nIdx = refineSubMesh(nIdx, vList,level -1, &newTri);
	} 

	return nIdx;
} 

/*
 * Prüfung ob ein Vertex anhand seiner LOD daten aktiv ist
 */
bool ClGuSoarTerrain::isVertexActive(SoarVertex *vertex){
	//wenn der schwellenwert einen bestimmten Wert übersteigt
	//ist der Vertex aktiv
	float threshold = errorTol*vertex->e + vertex->r;
	threshold*=threshold;
	return (threshold > 10000.0f);
}

Zum Abschluß fehlt nur noch der Einblick in die Methoden die die Indexliste aufbauen. Diese werden nun im folgenden gezeigt. Da hin und wieder die Richtung der Dreiecke getauscht werden muss, müssen wir beim Indexaufbau immer wieder mal “unsichtbare” Dreiecke einfügen. Um diesen Wechsel zu vereinfachen wird neben dem letzten Indexpunkt auch immer die aktuelle “Richtung” des Dreieckes mitgespeichert.

/*
 * Der Index wird mit dem ersten Punkt gestartet. Dieser wird 2 mal hinzugefügt. Beim
 * Rendern kann dieser getrost übersprungen werden, ist für den Indexaufbau aber wichtig
 */
SoarVertexId *ClGuSoarTerrain::soarIndexBegin(SoarVertexId *iList, SoarVertexId id, bool parity)
{
	SoarVertexId* nextI = iList;
	*nextI++ = id;
	*nextI++ = id; 

	//Zum einfachen wechseln der "Richtung" die Ausrichtung hinter dem letzten Index
	//codieren
	*nextI = (SoarVertexId)parity;
	return nextI;
} 

SoarVertexId *ClGuSoarTerrain::soarIndexAppend(SoarVertexId *iList, SoarVertexId id, bool parity)
{
	SoarVertexId* nextI = iList;
	//ein neuer Index zur Liste hinzu.
	//bei einem "Richtungswechsel" muss vor-vorletzte Vertex nochmal dazu
	SoarVertexId tail = iList[-2];
	SoarVertexId head = iList[-1];
	bool lastParity = (bool)iList[0]; 

	if (id != tail && id != head){
		if (lastParity == parity){
			*nextI++ = tail;
		}
		*nextI++ = id;
		*nextI = (SoarVertexId)parity;
	}
	return nextI;
} 

unsigned int ClGuSoarTerrain::soarIndexEnd(SoarVertexId *iList, SoarVertexId id)
{
	// Wenn der letzte Indexeintrag geschrieben wurde, kann die "Länge" der Liste bestimmt werden
	// und wird entprechend zurück geliefert
	SoarVertexId* nextI = iList;
	*nextI++ = id;
	return (unsigned int)(nextI - this->index);
}