News
Code
Pictures
Code
Download
Links
Webmaster
 


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:
Detail01
Detail 1

Detail2
Detail 2

Detail3
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;
}


Quicklinks: [News] - [Pictures]] - [Code] - [Download]] - [Links]
Hosted by www.Geocities.ws

1