Displaylister
Grafikk
Fredrik Danielsen / Student 2002
Å tegne:>Terreng>Displaylister

Display Lister

Hva

Når en lager et 3D terreng ønsker man ofte veldig store terreng med høy oppløsning for god detaljrikdom. Disse kartene krever fort mye av grafikkprosessoren i maskinen fordi antall triangler (bredde*høyde * 2) firedobles når bredden og høyde dobles, dvs at når bredden og høyden dobles fra 128 til 256 øker antall triangler fra 32768 til 131072. Det betyr at hastigheten av rendringen tar lang tid. En måte å speede opp rendringen er bruk av display lister.

En display liste er et sett med openGL kommandoer som har blitt lagret og kompilert for senere bruk. Mange grafikkort lagrer display listene i dedikert minne på en mer optimalisert form en hva er tilfellet ved rendring uten displaylister. Dette kan bidra til økt hastigheten ved rendring.

display

Når en har laget en display liste kan man ikke forandre innholdet i den fordi det ville involvert leting gjennom display listen og utførelse av minnehåndteringen. Det ville ført til økt overhead og tap av optimalisering. Derfor er vi avhengig av at det vi legger i display listen er statisk, noe som passer bra til terreng genereringen vi skal gjøre siden vi ikke skal simulere bevegelser av landoverflaten.

Metodene som er viktige for håndtering av display lister er:

 int glGenLists(int range)

- allokerer range antall ledige display liste index'er. De returnerte index'ene blir merket tomme og brukte, slik at flere kall med glGenLists() ikke returnerer disse index'ene før de blir slettet.

 int glNewList(int list, GLenum mode)

- spesifiserer starten av en display liste. OpenGL rutiner som er kalt etter denne kommandoen (frem til glEndList() blir kalt) blir lagret i displaylisten (uten om noen spesielle OpenGL rutiner som ikke kan bli lagret, disse blir utført med en gang.) List er en ikke 0 positiv integer som unikt identifiserer display listen. De mulige verdiene for mode er GL_COMPILE og GL_COMPILE_AND_EXECUTE. Bruk av GL_COMPILE hindrer kommandoene i å bli utført når de blir plassert i display listen.

 int glEndList()

- markerer slutten av display listen.

 int glCallList(int list)

- eksekverer display listen list. Kommandoene i displaylisten blir eksekvert i den rekkefølgen de ble lagret.

Andre kommandoer relatert til displaylister:

int glIsList(int list)
void glDeleteLists(int list, int range)
void glListBase(int base)

En liten kodesnutt som demonstrerer bruk av displaylister 

public class Terreng extends GLCanvas
{
   //Variabel for lagring av displayliste
   int terreng;

   <klipp bort kode>

   public void init()
   {
      <klipp bort kode>

      //alloker display list index
      terreng = gl.glGenLists(1);
      //Lag display liste
      gl.glNewList(terreng, GL_COMPILE);
         <tegn vertexer, normaler, osv>
      //Display liste ferdig
      gl.glEndList();
   }

   public void display()
   {
      <klipp bort kode>
      //kall liste for opptegning
      gl.glCallList(terreng);
   }
}

Framerate

Som jeg har nevnt tidligere er ikke målet i denne modulen og lage et terreng som tar hensyn til akselerasjon og optimalisering ved rendring. Men jeg kommer likevel til å gå inn på litt enkel teori i denne delen for hvordan kunne øke frameraten noe ganske enkelt.

En måte: rendre bare terrengskjelletet når en beveger kameraet rundt. En vinner endel framerate på dette men ser jo ikke så bra ut.
Hvordan gjøre det: Lag en tilsvarende metode til å tegne ut terrenget som når du skal tegne opp terrenget med tekstur og alt, men velg GL_LINE_STRIP isteden og dropp tekstur. Denne metoden bruker du til å tegne opp når du beveger kameraet, dropp å tegne opp vann og himmel.

En annen måte: Frustum culling.
Tegn opp kun den delen av terrenget som er innenfor kameraets synsvinkel. Terrenget deles opp i like store deler, f.eks. 64x64 kvadrater, og kun de delene som er innenfor kamerat rendres.

frustum

Her ser du at kun de svarte firkantene er innenfor kameravinkelen og derfor er det kun de som rendres.

Så lurer du kanskje på hvordan du skal finne ut hvilke firkanter som ligger innefor de 6 sidene av av kameravinkelen:

kamera

Ved hjelp av PROJECTION's matrisen og MODELVIEW matrisen er dette egentlig ganske enkelt. En trenger kun og finne 4x6 koordinater, fire koordinater for hvert av de seks planene. Her er en lang men grei kode som gjør dette og lagrer reultatet i arrayet float[6][4] frustum.

public void extractFrustum()
{

   float   proj[] = new float[16];
   float   modl[] = new float[16];
   float   clip[] = new float[16];
   float   t;


   /* Get the current PROJECTION matrix from OpenGL */
   gl.glGetFloatv( GL_PROJECTION_MATRIX, proj );


   /* Get the current MODELVIEW matrix from OpenGL */
   gl.glGetFloatv( GL_MODELVIEW_MATRIX, modl );


   /* Combine the two matrices (multiply projection by modelview) */
   clip[ 0] = modl[ 0] * proj[ 0] + modl[ 1] * proj[ 4]
      + modl[ 2] * proj[ 8] + modl[ 3] * proj[12];
   clip[ 1] = modl[ 0] * proj[ 1] + modl[ 1] * proj[ 5]
      + modl[ 2] * proj[ 9] + modl[ 3] * proj[13];
   clip[ 2] = modl[ 0] * proj[ 2] + modl[ 1] * proj[ 6]
      + modl[ 2] * proj[10] + modl[ 3] * proj[14];
   clip[ 3] = modl[ 0] * proj[ 3] + modl[ 1] * proj[ 7]
      + modl[ 2] * proj[11] + modl[ 3] * proj[15];


   clip[ 4] = modl[ 4] * proj[ 0] + modl[ 5] * proj[ 4]
      + modl[ 6] * proj[ 8] + modl[ 7] * proj[12];
   clip[ 5] = modl[ 4] * proj[ 1] + modl[ 5] * proj[ 5]
      + modl[ 6] * proj[ 9] + modl[ 7] * proj[13];
   clip[ 6] = modl[ 4] * proj[ 2] + modl[ 5] * proj[ 6]
      + modl[ 6] * proj[10] + modl[ 7] * proj[14];
   clip[ 7] = modl[ 4] * proj[ 3] + modl[ 5] * proj[ 7]
      + modl[ 6] * proj[11] + modl[ 7] * proj[15];


   clip[ 8] = modl[ 8] * proj[ 0] + modl[ 9] * proj[ 4]
      + modl[10] * proj[ 8] + modl[11] * proj[12];
   clip[ 9] = modl[ 8] * proj[ 1] + modl[ 9] * proj[ 5]
      + modl[10] * proj[ 9] + modl[11] * proj[13];
   clip[10] = modl[ 8] * proj[ 2] + modl[ 9] * proj[ 6]
      + modl[10] * proj[10] + modl[11] * proj[14];
   clip[11] = modl[ 8] * proj[ 3] + modl[ 9] * proj[ 7]
      + modl[10] * proj[11] + modl[11] * proj[15];


   clip[12] = modl[12] * proj[ 0] + modl[13] * proj[ 4]
      + modl[14] * proj[ 8] + modl[15] * proj[12];
   clip[13] = modl[12] * proj[ 1] + modl[13] * proj[ 5]
      + modl[14] * proj[ 9] + modl[15] * proj[13];
   clip[14] = modl[12] * proj[ 2] + modl[13] * proj[ 6]
      + modl[14] * proj[10] + modl[15] * proj[14];
   clip[15] = modl[12] * proj[ 3] + modl[13] * proj[ 7]
      + modl[14] * proj[11] + modl[15] * proj[15];


   /* Extract the numbers for the RIGHT plane */
   frustum[0][0] = clip[ 3] - clip[ 0];
   frustum[0][1] = clip[ 7] - clip[ 4];
   frustum[0][2] = clip[11] - clip[ 8];
   frustum[0][3] = clip[15] - clip[12];


   /* Normalize the result */
   t = (float)Math.sqrt( (double)((frustum[0][0] * frustum[0][0])
      + (frustum[0][1] * frustum[0][1])
      + (frustum[0][2] * frustum[0][2]) ));
   frustum[0][0] /= t;
   frustum[0][1] /= t;
   frustum[0][2] /= t;
   frustum[0][3] /= t;


   /* Extract the numbers for the LEFT plane */
   frustum[1][0] = clip[ 3] + clip[ 0];
   frustum[1][1] = clip[ 7] + clip[ 4];
   frustum[1][2] = clip[11] + clip[ 8];
   frustum[1][3] = clip[15] + clip[12];


   /* Normalize the result */
   t = (float)Math.sqrt((double) ((frustum[1][0] * frustum[1][0])
      + (frustum[1][1]) * (frustum[1][1])
      + (frustum[1][2] * frustum[1][2])) );
   frustum[1][0] /= t;
   frustum[1][1] /= t;
   frustum[1][2] /= t;
   frustum[1][3] /= t;


   /* Extract the BOTTOM plane */
   frustum[2][0] = clip[ 3] + clip[ 1];
   frustum[2][1] = clip[ 7] + clip[ 5];
   frustum[2][2] = clip[11] + clip[ 9];
   frustum[2][3] = clip[15] + clip[13];


   /* Normalize the result */
   t = (float)Math.sqrt((double) ((frustum[2][0] * frustum[2][0])
      + (frustum[2][1] * frustum[2][1]) + (frustum[2][2] * frustum[2][2]) ));
   frustum[2][0] /= t;
   frustum[2][1] /= t;
   frustum[2][2] /= t;
   frustum[2][3] /= t;


   /* Extract the TOP plane */
   frustum[3][0] = clip[ 3] - clip[ 1];
   frustum[3][1] = clip[ 7] - clip[ 5];
   frustum[3][2] = clip[11] - clip[ 9];
   frustum[3][3] = clip[15] - clip[13];


   /* Normalize the result */
  t = (float)Math.sqrt((double) (frustum[3][0] * frustum[3][0])
      + (frustum[3][1] * frustum[3][1]) + (frustum[3][2] * frustum[3][2]) );
   frustum[3][0] /= t;
   frustum[3][1] /= t;
   frustum[3][2] /= t;
   frustum[3][3] /= t;


   /* Extract the BACK plane */
   frustum[4][0] = clip[ 3] - clip[ 2];
   frustum[4][1] = clip[ 7] - clip[ 6];
   frustum[4][2] = clip[11] - clip[10];
   frustum[4][3] = clip[15] - clip[14];


   /* Normalize the result */
   t = (float)Math.sqrt((double)( (frustum[4][0] * frustum[4][0])
      + (frustum[4][1] * frustum[4][1]) + (frustum[4][2] * frustum[4][2])) );
   frustum[4][0] /= t;
   frustum[4][1] /= t;
   frustum[4][2] /= t;
   frustum[4][3] /= t;


   /* Extract the FRONT plane */
   frustum[5][0] = clip[ 3] + clip[ 2];
   frustum[5][1] = clip[ 7] + clip[ 6];
   frustum[5][2] = clip[11] + clip[10];
   frustum[5][3] = clip[15] + clip[14];


   /* Normalize the result */
   t = (float)Math.sqrt((double) ((frustum[5][0] * frustum[5][0])
      + (frustum[5][1] * frustum[5][1]) + (frustum[5][2] * frustum[5][2]) ));
   frustum[5][0] /= t;
   frustum[5][1] /= t;
   frustum[5][2] /= t;
   frustum[5][3] /= t;
}

Ikke bli skremt av at koden er lang og ser stygg ut, det er den samme prosessen som gjentas hele veien nedover, bare med forskjellige klippeplan for de 6 forskjellige planene. Denne koden trengs kun og kalles en gang i display() metoden før en tegner opp objektene en vil ha fram.

En metode for å sjekke om et punkt er innenfor klippeplanet følger her:

pulic boolean cubeInFrustum( float x, float y, float z, float size )
{
   int p;


   for( p = 0; p < 6; p++ )
   {
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size)
         + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size)
         + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size)
         + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size)
         + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size)
         + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size)
         + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size)
         + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         continue;
      if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size)
         + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
         continue;
      return false;
   }
   return true;
}

Oppdelingen av høydekartene (vannet og fjellene) har jeg gjort ved å utvide metoden for opptegningen.

public void drawTerrengDel(int x1, int x2, int y1, int y2)
{
   gl.glEnable(GL_TEXTURE_2D);
   gl.glBindTexture(GL_TEXTURE_2D, groundtext);
   gl.glTexEnvi(GL_TEXTURE_ENV,GL_TEXTURE_ENV_MODE,GL_MODULATE);

   for (int x = x1; x <= x2; x++)
   {
      gl.glBegin(GL_TRIANGLE_STRIP);
      for (int y = y1; y <= y2; y++)
      {
         gl.glNormal3f( normals[x][y][0],
                        normals[x][y][1],
                        normals[x][y][2]);
         gl.glTexCoord2f(texture[x][y][0],texture[x][y][1]);
         gl.glVertex3f( hf.getLength(x,y),
                        hf.getWidth(x, y),
                        hf.getHeight(x, y));
         gl.glTexCoord2f(texture[x+1][y][0], texture[x+1][y][1]);
         gl.glVertex3f( hf.getLength(x+1,y),
                        hf.getWidth(x+1,y),
                        hf.getHeight(x+1,y));

      }
      gl.glEnd();
   }

   gl.glDisable(GL_TEXTURE_2D);
}

Ved og variere variablene x1 og x2, og y1 og y2 kan jeg bestemme hvilke deler av høydekartet som skal bli tegnet. Første del vil da av x1 = 0 og x2 = 31 og y1 = 0 og y2 = 31, andre del vil ha x1 = 32 og x2 = 61 og y1 = 0 og y2 = 31 osv avhengig av hvor stort høydekartet er. Jeg legger så hver av disse delene inn i en display liste, og før jeg tegner en del av kartet sjekker jeg om denne delen er innenfor kameravinkelen.

Denne metoden generer landskapsdeler og legger dem i displaylister

public int generateTerrengDisplay()
{
   int nr = 1;
   int x = 0;
   int y = 0;
   int end = 0;

   terreng = new int[(SIZE/32)*(SIZE/32)];
   for (int i = 0; i < SIZE/32; i++)
   {
      for(int j = 0; j < SIZE/32; j++)
      {
         terreng[nr-1] = gl.glGenLists(nr);
         gl.glNewList(terreng[nr-1], GL_COMPILE);
            setMaterialGround();
            drawTerrengDel(x,x+31,y, y+31);
         gl.glEndList();
         y += 31;
         nr++;
         }
         x += 31;
         y = 0;
      }
      return nr;
   }
}

Metoden returner et nummer for at oppdelingen av vann skal vite hvilken displayliste id som er den første ledige.

Denne metoden sjekker om midten av en terrengdel i en displayliste er innenfor kameravinkelen. Hvis den er det, tegnes delen opp på skjermen.

int nr = 0;
int x = 0;
int y = 0;
for (int i = 0; i < SIZE/32; i++)
{
   for(int j = 0; j < SIZE/32; j++)
   {
      if (cubeInFrustum(hf.getLength(x+16,y+16),
                        hf.getWidth(x+16, y+16),
                        hf.getHeight(x+16, y+16),
                        32*stride))
      {
         gl.glCallList(terreng[nr]);
      }
      nr++;
      y += 32;
   }
x += 32;
y = 0;
}

P.S. Det er ikke nok med frustum culling alene for å øke framraten betraktelig, fordi hvis man flytter seg langt tilbake på terrenget vil jo flere deler av kartet være innenfor kameravinkelen og frameraten vil synke. En er nokså nødt til å implementere level-of-detail + andre mulige hastighetsøkende metoder viss en vil ha en fullgod framrate. Men det vil jeg ikke gå nærmere inn på her.

  • Terreng.java
Vedlikehold
  • Skrevet av Fredrik Danielsen, student 2002
  • Redaksjonell tilpassing,Børre Stenseth juni 2002
Å tegne:>Terreng>Displaylister
til toppen
WXT 6
Valid HTML5
Valid CSS!