Culled Surface
Algorithm
Pro:
-
Very fast rendering technique independent of heightmap dimensions
-
Integrated level of detail due to polar coordinates
Contra:
- Distortion close to camera due to polar coordinates
Der große Nachteil bei meiner Methode eine Oberfläche
zu rendern liegt darin, dass bei jedem Zeichenaufruf das komplette
Raster
der Koordinatentripel durchlaufen werden muss egal ob ein Dreieck
gezeichnet
werden muss oder nicht (Stichwort: Frustum Culling). Da ein
quadratisches
Raster verwendet wird, geht die Dimension obendrein noch im Quadrat
ein:
128*128 Bildpunkte des Höhenfeldes ergeben 16384 Gitterpunkte und
32258 zu zeichnende Dreiecke. Nachdem 32000 mal überprüft
worden
ist, ob ein Dreieck im Kegelstumpf (Frustum) der Kamera liegt, werden
erst
die Dreiecke gezeichnet.
Wenn man aber eine Möglichkeit fände nur die
Koordinaten für
Dreiecke auszuwählen, die im Frustum der Kamera liegen,
könnte
man einen erheblichen Geschwindigkeitsfortschritt erreichen. Zudem
könnte
man sich das Frustum Culling für die Oberfläche sparen. Wenn
es obendrein noch gelänge durh Polarkoordinaten eine Art Level of
Detail in Tiefenrichtung einzubauen, hätte man gleich drei Fliegen
mit einer Klappe geschlagen.
In dem folgenden Matlab Programm habe ich versucht diese
drei angesprochenen
Punkte umzusetzen:
| % function
raster(clip_near,clip_far,ntiles,view_angle,alfa,x_cam,y_cam)
% clip_near -
Clipping Ebene nah
% clip_far -
Clipping Ebene
fern
%
ntiles -
Einteilungen
% view_angle -
Blickwinkel bezogen
auf x-Achse
%
alfa
- Öffnungeswinkel des Sichtfensterss
%
x_cam
- x-Position der Kamera auf dem Urrasterr
%
y_cam
- y-Position der Kamera auf dem Urrasterr
%--------------------------------------------------------------------------------------------
function
raster(clip_near,clip_far,ntiles,view_angle,alfa,x_cam,y_cam)
%--------------------------------------------------------------------------------------------
%Feste Größen
für die Berechnung
der Oberflächen-Matrix (Höhenpunkte vergleichbar mit
einem
%Graustufenbild aus Terragen,
oder nach Perlin-Noise).
scale = 10;
dim = 128;
n = 1;
detail = 4;
mat = zeros(dim*2);
for (i=1:detail)
tmp =
interpolated_surface(2^(n+i)+1,dim/(2^(n+i-1)))
.* (1/((i-1)+1)^2*100);
mat = mat + tmp;
end
h=surf(mat)
axis equal
hold on
%Berechnung des
Öffnungswinkels. Der
Öffnungswinkel des Frustums beginnt bei alfa0 und endet
%bei alfa1
alfa0 = view_angle-alfa/2;
alfa1 = view_angle+alfa/2;
%Berechnung des Raterradius
und -winkels
%Der Radius (Raster in
Tiefenrichtung) erhält
eine exponetielle Verteilung, da die Rasterpunkte
%in Tiefenrichtung
größere Abstände
erhalten sollen. In weiter Ferne werden nicht so viele
%Details benötigt.
for (i=1:ntiles)
t(i) = exp(1/ntiles)-exp(i/ntiles);
end
for (i=1:ntiles)
t(i) = t(i)/t(end);
end
for (i=1:ntiles)
r(i) =
clip_near+(t(i)*(clip_far-clip_near));
end
%r =
linspace(clip_near,clip_far,ntiles);
%Die Stützstellen des
Rasters in Breitenrichtung
sind linear verteilt.
alfa = linspace(alfa0,alfa1,ntiles);
%Beginn Schleife in jedem
Renderaufruf---------------
raster_x = [];
raster_y = [];
raster_z = [];
for (i=1:ntiles)
for (j=1:ntiles)
%Transformation in
Polarkoordinaten und "Typecasting"
in Indexwerte der Matrix mat
x = round(x_cam +
r(i)*sin(alfa(j)*pi/180));
y = round(y_cam +
r(i)*cos(alfa(j)*pi/180));
%
raster_x(i,j)
= round(x_cam + scale*(r(i)*sin(alfa(j)*pi/180)));
%
raster_y(i,j)
= round(y_cam + scale*(r(i)*cos(alfa(j)*pi/180)));
raster_x(i,j) = x;
raster_y(i,j) = y;
%Sicherheitsabfragen: Falls die
Indizes ausserhalb
der Matrix mat liegen sollen die
%z-Koordinaten der Matrix 0
sein anderenfalls
die Höhenkoordinate aus mat.
if ((x+1)
>= dim*2 | (y+1) >= dim*2)
raster_z(i,j)
= 0;
elseif (x <=
0
| y <= 0)
raster_z(i,j)
= 0;
else
raster_z(i,j)
= mat(x+1,y+1);
end
end
end
surf(raster_y,raster_x,raster_z);
%Ende Schleife in jedem
Renderaufruf-----------------
colormap jet
hold off
%%Interpolierte
Oberfläche
%--------------------------------------------------------------------------------------------
function mat = interpolated_surface(detail,n)
%--------------------------------------------------------------------------------------------
img = rand(detail);
for (j=1:detail)
x = [];
for (i=1:size(img,1)-1)
img_xy =
cos_interp(i,img(i,j),i+1,img(i+1,j),n);
x = [x;
img_xy(2,:)'];
end
img_i(:,j) = x;
end
for (i=1:size(img_i,1))
y = [];
for (j=1:size(img,2)-1)
img_xy =
cos_interp(j,img_i(i,j),j+1,img_i(i,j+1),n);
y = [y
img_xy(2,:)];
end
img_j(i,:) = y;
end
mat = img_j;
|
Das Ergebnis dieser kleinen Funktion liefert genau das
gewünscht
Ergebnis (die rote Umrandung zeigt den gerenderten Bereich, der Pfeil
ist
die Kameraposition auf der Oberfläche zusammen mit der
Blickrichtung)

Durch die Transformation in Polarkoordinaten erreicht man
eigentlich
einen sehr schönen LOD-Effekt. Zudem muss ich nun nicht mehr durch
das komplette Raster der Höhenkarte laufen, sondern springe direkt
in die Höhenkarte durch die aktuell berechneten Indizes des
Frustums.
In diesem Falle ist die Anzahl der Rasterpunkte der "culled Surface"
64*64.
In jedem Zeichenaufruf werden anstelle von 32258
Schleifendurchläufen
nur 4096 (!) Schleifenaufrufe benötigt - ein Faktor von über
7.
Leider hat de Umsetzung in C++ und OpenGL noch nicht
zufriedenstellend
funktioniert. Im Bild kann man allerdings die Verzerrung in der
Nähe
der Kamera erkennen, sowie die Sicherheitsabfragen in der
Raster-Index-Zuweisungen
(wenn Index ausserhalb der Matrix, dann Höhe 0). Man sieht die
Fläche
von unten. Die Kamera ist auf Höhe 0.

Die folgenden Bilder zeigen die
Umsetzung des Culled Raster Surface Rendering in drei verschiedenen
Detailgrads:

Detail 1

Detail 2

Detail 3
Hier der C++/OpenGL Code:
Header
#ifndef
X_SurfaceH
#define
X_SurfaceH
#include
<math.h>
#include
<stdio.h>
#define
GLUT_DISABLE_ATEXIT_HACK
#include
"glut.h"
#include
"X_IO.h"
#include
"X_Math.h"
#include
"XGraphix.h"
class TSurface{
private:
XIO *io;
float
**mat;
float
scale;
//global scale
value
int nDepth,
nWidth;
//dimension of
culled surface
float
*temp, *r, *phi;
float
**rasterx, **rastery, **rasterz; //raster positions of culled surface
float
**u,**v;
//texture
coordinates
unsigned int texID;
public:
int dimX,
dimZ;
//dimension of
matrix
void
PrepareCulledSurface(int
n1, //# of raster positions in depth
int n2, //# of raster positions in width
float zNear, //near
clipping area
float zFar); //far
clipping area
void
RenderCulledSurface(float fovy, //angle of frustum
float phiCam, //view
angle of camera
float xCam, //x position of camera
float zCam); //z position of camera
float
GetSurfaceHeight(float x, float z);
TSurface(float s);
~TSurface(void);
};
#endif
|
Funktionen
#include "X_Surface.h"
//------------------------------------------------------------------------
TSurface::TSurface(float s){
//------------------------------------------------------------------------
scale = s;
io = new XIO;
io =
XIOReadMatrix(".\\data\\mesh\\surface.txt"); //holds just a matrix
X_BuildTexture(".\\data\\bitmap\\Surface.bmp",texID); //a texture loader
dimX = io->m.row;
dimZ = io->m.col;
mat = new float *[io->m.row];
for (int i=0;i<io->m.row;i++){
mat[i] = new float [io->m.col];
}
for (int i=0;i<io->m.row;i++){
for (int j=0;j<io->m.col;j++){
mat[i][j] = scale *
io->m.mat[i][j];
}
}
}
//------------------------------------------------------------------------
TSurface::~TSurface(void){
//------------------------------------------------------------------------
if (mat) delete [] mat;
if (temp) delete [] temp;
if (r) delete [] r;
if (phi) delete [] phi;
if (rasterx) delete [] rasterx;
if (rastery) delete [] rastery;
if (rasterz) delete [] rasterz;
if (u) delete [] u;
if (v) delete [] v;
}
//------------------------------------------------------------------------
void TSurface::PrepareCulledSurface(int
n1, //# of raster
positions in depth
int n2, //# of raster
positions in width
float zNear, //near clipping area
float zFar){ //far clipping area
//------------------------------------------------------------------------
nDepth = n1;
nWidth = n2;
temp = new float[nDepth];
r = new float[nDepth];
phi = new float[nWidth];
rasterx = new float*[nDepth];
rastery = new float*[nDepth];
rasterz = new float*[nDepth];
u = new float*[nDepth];
v = new float*[nDepth];
for (int i=0;i<nDepth;i++){
rasterx[i] = new float[nWidth];
rastery[i] = new float[nWidth];
rasterz[i] = new float[nWidth];
u[i]
= new float[nWidth];
v[i]
= new float[nWidth];
}
//Radius exponential distribution
for (int i=0;i<nDepth;i++){
temp[i] = 1.0 -
exp((float)i/(float)nDepth);
}
for (int i=0;i<nDepth;i++){
temp[i] /= temp[nDepth-1];
}
for (int i=0;i<nDepth;i++){
r[i] = zNear + (temp[i] * (zFar -
zNear));
}
}
//------------------------------------------------------------------------
void TSurface::RenderCulledSurface(float
fovy, //angle of frustum
float phiCam, //view angle of camera
float xCam, //x position of camera
float zCam){ //z position of camera
//------------------------------------------------------------------------
float phi0, phi1;
int x,z;
float v1[3],v2[3],norm[3];
//Angle linear distribution
phi0 = phiCam-fovy;
phi1 = phiCam+fovy;
for (int i=0;i<nWidth;i++){
phi[i] = phi0 + ((float)i/(float)nWidth
* (phi1 - phi0));
}
//Access the z-values with raster-positions
for (int i=0;i<nDepth;i++){
for (int j=0;j<nWidth;j++){
x = XMARoundi(xCam +
r[i]*sin(phi[j]*M_PI/180.0));
z = XMARoundi(zCam +
r[i]*cos(phi[j]*M_PI/180.0));
u[i][j] =
(float)x/(float)dimX*1.0;
v[i][j] =
(float)z/(float)dimZ*1.0;
rasterx[i][j] =
(float)x;
rasterz[i][j] =
(float)z;
if ((x >= dimX) || (z
>= dimZ)) rastery[i][j] = 0.0;
else if ((x <
0) || (z < 0))
rastery[i][j] = 0.0;
else
rastery[i][j] = mat[x][z];
}
}
glEnable(GL_TEXTURE_2D);
glBindTexture(GL_TEXTURE_2D,texID);
glPushMatrix();
for (int i=0;i<nDepth-1;i++){
glColor3f(1.3-(float)i/(float)nDepth,1.4-(float)i/(float)nDepth,1.0);
glBegin(GL_TRIANGLE_STRIP);
for (int j=0;j<nWidth-1;j++){
v1[0] =
(rasterx[i+1][j]-rasterx[i][j]);
v1[1] =
(rastery[i+1][j]-rastery[i][j]);
v1[2] =
(rasterz[i+1][j]-rasterz[i][j]);
v2[0] =
(rasterx[i][j+1]-rasterx[i][j]);
v2[1] =
(rastery[i][j+1]-rastery[i][j]);
v2[2] =
(rasterz[i][j+1]-rasterz[i][j]);
XMACross(v1,v2,norm);
glNormal3fv(norm);
glTexCoord2f(u[i][j],v[i][j]);
glVertex3f(scale*(xCam-rasterx[i] [j]) ,rastery[i]
[j] ,scale*(zCam-rasterz[i] [j]));
glTexCoord2f(u[i+1][j],v[i+1][j]);
glVertex3f(scale*(xCam-rasterx[i+1][j]) ,rastery[i+1][j]
,scale*(zCam-rasterz[i+1][j]));
}
glEnd();
}
glPopMatrix();
glDisable(GL_TEXTURE_2D);
}
//------------------------------------------------------------------------
float TSurface::GetSurfaceHeight(float x, float z){
//------------------------------------------------------------------------
float y;
int i,j;
i = (int)x;
j = (int)z;
if ((i >= 0 && i < dimX) &&
(j >= 0 && j < dimZ))
y = mat[i][j];
else
y = 0.0;
return y;
}
|
|