Eine Voxel-Landschaft beschreibt eine 3 dimensionale Landschaft recht einfach anhand einer 2 dimensionalen Höhenkarte. Die Eigenschaft eines Voxel ist, dass es sich hierbei um ein “volumenbehaftetes” Pixel handelt. Dies bedeutet, dass es nicht nur durch seine Position X und Y und damit seiner Lage im Raum beschrieben wird, sondern auch durch seine Höhe. Dadurch beschreibt ein Voxel einen Quader der immer 1 Pixel breit, 1 Pixel tief und n Pixel hoch ist.
Mit dieser Vorgabe lässt sich eine Landschaft im einfachsten Fall durch ein einfaches Bild beschreiben welches z.Bsp. 256 Farben besitzt. Jeder Bildpunkt beschreibt mit seiner X und seiner Y ganz einfach die Position und der Farbwert die Höhe des Voxel.

Nun kann man über sehr einfache Algorythmen schnell für jeden Voxel im virtuellen Raum berechnen wie dieser auf dem Bildschirm darzustellen ist. Für die Darstellung nehmen wir einen beliebigen Punkt auf der 2D Landschaft als Punkt des Betrachters an der in eine bestimmte Richtung schaut. Dabei ist immer ein bestimmter Teil der Landschaft sichtbar.
Wie der nun sichtbare Teil berechnet werden kann und auf den Bildschirm projiziert werden kann beschreibt das Beispiel von [1] NLS - Nonlinear Solutions das in Visual Basic programmiert wurde. In einem ersten Schritt portiere ich diesen Ansatz in C++ code um diesen dann auf der PSP laufen zu lassen. Einige nette Details dieser Version werden in der ersten Version allerdings weg gelassen um den Einstieg zu vereinfachen….

Als Grundlage dient die folgende Höhenkarte auf der der Betrachter einen beliebigen Standpunkt mit einer frei wählbaren Blickrichtung einnehmen kann:

Die Berechnung der Landschaft geht nun von dem Standpunkt und der Blickrichtung des Betrachters aus. In dem hier genutzten Algorythmus wird eine Art Ray-Tracing (Strahlenverfolgung) benutzt. Das heißt, dass wir vom Standpunkt des Betrachters durch den virtuellen Bildschirm der PSP für jede Spalte des Bildschirmes einen Strahl über die Landschaft legen und diesen Schritt für Schritt “ablaufen” und die Höhenpunkte auf der Karte ermitteln. Trifft der Strahl einen Höhenpunkt, dann müssen wir diesen Zeichnen. Der Strahl wird dabei nicht unendlich weitergelaufen, sondern nur bis zu einer bestimmten Grenze. Die folgenden Bilder sollen dies veranschaulichen:

>

Diese Theorie in ein paar Codezeilen umgesetzt sieht dann folgendermaßen aus:

/*
* Datendeklarationen
*/
struct rayDelta {
long rayDeltaX, rayDeltaY;
} ;
rayDelta preDelta[480];

short posX; // Position X des Betrachters

short posY; // Position Y des Betrachters
long mapData[512][512]; //Höhenwerte der Karte
long mapSize = 512; //breite der Karte


/*
* Ein wenig initialisierung um die Berechnung etwas zu beschleunigen.
*/
void Init( ){
short x;
long rayDeltaX, rayDeltaY;
float hx;
// Initiale Startposition in der Mitte der Karte
posX = mapSize >> 1;
posY = mapSize >> 1;
for (x=0;x<480;x++){
hx = x - 240;
rayDeltaX = ((hx / sqrtf(hx*hx + 400*400))*1024);
rayDeltaY = (400 / sqrtf(hx*hx + 400*400)*1024);
preDelta[x].rayDeltaX = rayDeltaX;
preDelta[x].rayDeltaY = rayDeltaY;
}
}

/*
* Die zentrale Routine welche die Landschaft auf dem Bildschirm darstellt
*/
void Render( ){
int pixelX;
int pixelY;
long voxelX;
long voxelY;
long rayX, rayY;
float rayZ;
long rayDeltaX, rayDeltaY;
float rayDeltaZ;
float slopeDelta;
float voxelScale;
float currentAltitude;
int rayStepCounter;
int stepWidth;
long altitude;
stepWidth = 1;
slopeDelta = 0.05f;
//entlang des Bildschirms von links nach rechsts….
for (pixelX=0; pixelX<480; pixelX++) {
//Setzen der Strahl position
rayX = posX << 10;
rayY = posY << 10;
rayZ = 384;
//setzen von rayDelta
rayDeltaX = preDelta[pixelX].rayDeltaX;
rayDeltaY = preDelta[pixelX].rayDeltaY;
rayDeltaZ = (float)(slopeDelta * -200.0f);
//setzen der Rate für die Voxel-Ermittlung
voxelScale = 0.0f;
//setzen der Startzeile auf dem Bildschirm - von unten nach oben…
pixelY = 271;
//nun den Strahl entlang “laufen”
for (rayStepCounter=0;rayStepCounter<=128;rayStepCounter++) {
//lesen des Voxel von der Karte auf das der Strahl gerade zeigt
voxelX = (rayX >> 10) & (mapSize -1);
voxelY = (rayY >> 10) & (mapSize -1);
//Höhe des Voxel
altitude = mapData[voxelY][voxelX];
currentAltitude = altitude & 255;
//trifft der Strahl den Voxel ?
if (currentAltitude > rayZ) {
// Ja! Wir müssen diesen Voxel zeichnen
//der Voxel wird von unten nach oben gezeichnet
do {
// Punkt im Bildschirm
setPixel(pixelX, pixelY, altitude);
rayDeltaZ += slopeDelta; //erhöhen der Tiefenschrittweite - wegen der Perspective
rayZ += voxelScale; //erhöhen der Strahlposition um die gezeichnete Voxelhöhe
pixelY– ; //nächste Zeile auf dem Bildschirm
if (pixelY <= 1) break;
}while (rayZ < currentAltitude);
}
// einen Schritt auf dem Strahl weiter
rayX += rayDeltaX;
rayY += rayDeltaY;
rayZ += rayDeltaZ;
//erhöhen der Voxel-Rate während wir von vorne nach hinten gehen (Perspektive)
voxelScale += slopeDelta;
}
}
}