DGL • Thema anzeigen - Frustum culling and quad tree problem

Frustum culling and quad tree problem

Moderator: DGL-Team

Seite 1 von 1

[ 3 Beiträge ]

Druckansicht

Vorheriges Thema | Nächstes Thema

Autor

Nachricht

BTierens

Betreff des Beitrags: Frustum culling and quad tree problem

Verfasst: Mi Aug 18, 2004 17:04

DGL Member

Registriert: Fr Aug 13, 2004 17:43
Beiträge: 60
Wohnort: Belgien

This is a complex question. I have a tile based landscape with frustum culling and a quad tree. There are tiles that aren't drawn while they should be drawn and I can't find a bug. Can somebody help me?

The first unit is the quadtree unit: http://home.deds.nl/~svg/quadtree.htm

This is the sclMath unit wich contains frustum culling functions:

Code:

 
{$MODE FPC}
unit sclMath;
 
{***********************************************************}
{*sclMath                                 date: 26/6/2004  *}
{*author: Bart Tierens                    edited: 26/6/2004*}
{*Frustum culing based on code from                        *}
{*http://www.markmorley.com/opengl/frustumculling.html     *}
{***********************************************************}
interface
 
uses gl,glu,sysUtils;
 
function
procedure ExtractFrustum();
function PointInFrustum(x,y,z: extended): boolean;
function PolygonInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
function PolygonCompletelyInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
var
frustumdata: Array[0..5] of Array[0..3] of extended;
 
implementation
 
//************************************************************************************************
//Extracts the frustum
//************************************************************************************************
procedure ExtractFrustum();
var
proj: Array[0..15] of glfloat;
modl: Array[0..15] of glfloat;
clip: Array[0..15] of extended;
t: extended;
begin
 
    //Get the current PROJECTION matrix from OpenGL
    glGetFloatv(GL_PROJECTION_MATRIX,@proj);
 
    //Get the current MODELVIEW matrix from OpenGL
    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
    frustumdata[0][0] := clip[ 3] - clip[ 0];
    frustumdata[0][1] := clip[ 7] - clip[ 4];
    frustumdata[0][2] := clip[11] - clip[ 8];
    frustumdata[0][3] := clip[15] - clip[12];
 
    //Normalize the result
    t := sqrt( frustumdata[0][0] * frustumdata[0][0] + frustumdata[0][1] * frustumdata[0][1] + frustumdata[0][2] * frustumdata[0][2] );
    frustumdata[0][0] /= t;
    frustumdata[0][1] /= t;
    frustumdata[0][2] /= t;
    frustumdata[0][3] /= t;
 
    //Extract the numbers for the LEFT plane
    frustumdata[1][0] := clip[ 3] + clip[ 0];
    frustumdata[1][1] := clip[ 7] + clip[ 4];
    frustumdata[1][2] := clip[11] + clip[ 8];
    frustumdata[1][3] := clip[15] + clip[12];
 
    //Normalize the result
    t := sqrt( frustumdata[1][0] * frustumdata[1][0] + frustumdata[1][1] * frustumdata[1][1] + frustumdata[1][2] * frustumdata[1][2] );
    frustumdata[1][0] /= t;
    frustumdata[1][1] /= t;
    frustumdata[1][2] /= t;
    frustumdata[1][3] /= t;
 
    //Extract the BOTTOM plane
    frustumdata[2][0] := clip[ 3] + clip[ 1];
    frustumdata[2][1] := clip[ 7] + clip[ 5];
    frustumdata[2][2] := clip[11] + clip[ 9];
    frustumdata[2][3] := clip[15] + clip[13];
 
    //Normalize the result
    t := sqrt( frustumdata[2][0] * frustumdata[2][0] + frustumdata[2][1] * frustumdata[2][1] + frustumdata[2][2] * frustumdata[2][2] );
    frustumdata[2][0] /= t;
    frustumdata[2][1] /= t;
    frustumdata[2][2] /= t;
    frustumdata[2][3] /= t;
 
    //Extract the TOP plane
    frustumdata[3][0] := clip[ 3] - clip[ 1];
    frustumdata[3][1] := clip[ 7] - clip[ 5];
    frustumdata[3][2] := clip[11] - clip[ 9];
    frustumdata[3][3] := clip[15] - clip[13];
 
    //Normalize the result
    t := sqrt( frustumdata[3][0] * frustumdata[3][0] + frustumdata[3][1] * frustumdata[3][1] + frustumdata[3][2] * frustumdata[3][2] );
    frustumdata[3][0] /= t;
    frustumdata[3][1] /= t;
    frustumdata[3][2] /= t;
    frustumdata[3][3] /= t;
 
    //Extract the FAR plane
    frustumdata[4][0] := clip[ 3] - clip[ 2];
    frustumdata[4][1] := clip[ 7] - clip[ 6];
    frustumdata[4][2] := clip[11] - clip[10];
    frustumdata[4][3] := clip[15] - clip[14];
 
    //Normalize the result
    t := sqrt( frustumdata[4][0] * frustumdata[4][0] + frustumdata[4][1] * frustumdata[4][1] + frustumdata[4][2] * frustumdata[4][2] );
    frustumdata[4][0] /= t;
    frustumdata[4][1] /= t;
    frustumdata[4][2] /= t;
    frustumdata[4][3] /= t;
 
    //Extract the NEAR plane
    frustumdata[5][0] := clip[ 3] + clip[ 2];
    frustumdata[5][1] := clip[ 7] + clip[ 6];
    frustumdata[5][2] := clip[11] + clip[10];
    frustumdata[5][3] := clip[15] + clip[14];
 
    //Normalize the result
    t := sqrt( frustumdata[5][0] * frustumdata[5][0] + frustumdata[5][1] * frustumdata[5][1] + frustumdata[5][2] * frustumdata[5][2] );
    frustumdata[5][0] /= t;
    frustumdata[5][1] /= t;
    frustumdata[5][2] /= t;
    frustumdata[5][3] /= t;
end;
 
//************************************************************************************************
//Returns true if the point is in the frustum
//************************************************************************************************
function PointInFrustum(x,y,z: extended): boolean;
var
  p: integer;
begin
  p := 0;
  while(p < 6) do
  begin
    if((frustumdata[p][0] * x + frustumdata[p][1] * y + frustumdata[p][2] * z + frustumdata[p][3]) <= 0 ) then
    begin
      PointInFrustum := false;
      exit;
    end;
    inc(p);
  end;
  PointInFrustum := true;
end;
 
//************************************************************************************************
//Returns true if the polygon is completely or partially in the frustum
//************************************************************************************************
function PolygonInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
var
  f,p: integer;
begin
   f := 0;
   while(f < 6) do
   begin
      p := 0;
      while(p < numpoints) do
      begin
         if(frustumdata[f][0] * pointlist[p*3] + frustumdata[f][1] * pointlist[(p*3)+1] + frustumdata[f][2] * pointlist[(p*3)+2] + frustumdata[f][3] > 0 ) then
         break;
         inc(p);
      end;
      if(p = numpoints) then
      begin
        PolygonInFrustum := false;
        exit;
      end;
     inc(f);
   end;
   PolygonInFrustum := true;
end;
 
//************************************************************************************************
//Returns true if the polygon is completely in the frustum
//************************************************************************************************
function PolygonCompletelyInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
var
  p: integer;
begin
  p := 0;
  while(p < numpoints) do
  begin
    if not (pointInFrustum(pointList[p*3],pointList[p*3+1],pointList[p*3+2])) then
    begin
      polygonCompletelyInFrustum := false;
      exit;
    end;
  inc(p);
  end;
  polygonCompletelyInFrustum := true;
end;
end.
 

The frustum culling code is a translation from http://web.archive.org/web/20030601123911/http://www.markmorley.com/opengl/frustumculling.html

First I call the createQuadTree procedure and when the camera moves, I call calcTilesInFrustum and draw the tiles returned by this procedure (the data stored in the tilesInFrustum array).

An image to show the problem (see the right and top side):
Bild

Nach oben

Stucuk

Betreff des Beitrags:

Verfasst: Mi Aug 18, 2004 18:06

DGL Member

Registriert: Mi Jul 21, 2004 22:39
Beiträge: 360
Wohnort: UK, Scotland

There is only one difference i can see between ur Frustum and the one im using, with the one im using the normalizing in the "ExtractFrustum" has been commented out.

_________________
Free Map Editor - Game Requirements - Stucuk.Net
-Stu

Nach oben

BTierens

Betreff des Beitrags:

Verfasst: Di Aug 24, 2004 08:07

DGL Member

Registriert: Fr Aug 13, 2004 17:43
Beiträge: 60
Wohnort: Belgien

I've found the bug.
Thanks for your help.

Nach oben

Seite 1 von 1

[ 3 Beiträge ]

Foren-Übersicht » English » English Programming Forum

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 5 Gäste

Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.