Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Fr Jul 18, 2025 00:06

Foren-Übersicht » English » English Programming Forum 		Unbeantwortete Themen | Aktive Themen


Ein neues Thema erstellen Auf das Thema antworten  Seite 1 von 1
  [ 1 Beitrag ] 
  Druckansicht Vorheriges Thema | Nächstes Thema 
Autor Nachricht
BTierens
BeitragVerfasst: Mi Aug 18, 2004 16:42 
Offline
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?


Code:
  1.  
  2. {$MODE DELPHI}
  3. unit QuadTree;
  4.  
  5. {***********************************************************}
  6. {*QuadTree.pas                      date: 30/7/2004        *}
  7. {*author: Bart Tierens              edited: 18/8/2004      *}
  8. {*A quad tree                                              *}
  9. {***********************************************************}
  10. interface
  11.  
  12. uses sclMath,classes,gl,glu,missionLoader,SysUtils;
  13. {
  14. missionLoader.pas contains the rawHeightmap array.
  15. If you have got for example a landscape with 40x40 tiles, rawHeightmap has a length of 41x41=1681.
  16. }
  17.  
  18. type
  19.   TBranch = class
  20.   private
  21.   protected
  22.   public
  23.     constructor create(x,y,groundWidth,groundHeight: integer);
  24.     subBranch1: TBranch;
  25.     subBranch2: TBranch;
  26.     subBranch3: TBranch;
  27.     subBranch4: TBranch;
  28.     cx,cz,cw,ch: integer;
  29.     procedure isInFrustum();
  30.   end;
  31.  
  32. procedure createQuadTree(groundWidth,groundHeight: integer);
  33. procedure calcTilesInFrustum(lvl: integer = 0);
  34.  
  35. var
  36.   root: TBranch;
  37.   tilesInFrustum: Array of TPoint;
  38.   mw: integer;
  39.   mh: integer;
  40.  
  41. implementation
  42.  
  43. //************************************************************************************************
  44. //Create a quad tree
  45. //************************************************************************************************
  46. procedure createQuadTree(groundWidth,groundHeight: integer);
  47. begin
  48.   //create
  49.   mw := groundWidth;
  50.   root := TBranch.create(0,0,groundWidth,groundHeight);
  51. end;
  52.  
  53. constructor TBranch.create(x,y,groundWidth,groundHeight: integer);
  54. begin
  55.   cx := x;
  56.   cz := y;
  57.   cw := groundWidth;
  58.   ch := groundHeight;
  59.   //Create sub Branches
  60.   if(cw <> 1) and (ch <> 1) then
  61.   begin
  62.     {subBranch1:      subBranch2:      subBranch3:      subBranch4:  
  63.     #0               0#               00               00          
  64.     00               00               0#               #0           }
  65.     subBranch1 := TBranch.create(cx,cz,cw div 2,ch div 2);
  66.     subBranch2 := TBranch.create(cx+(cw div 2),cz,cw div 2,ch div 2);
  67.     subBranch3 := TBranch.create(cx+(cw div 2),cz+(ch div 2),cw div 2,ch div 2);
  68.     subBranch4 := TBranch.create(cx,cz+(ch div 2),cw div 2,ch div 2);
  69.   end;
  70. end;
  71.  
  72. //************************************************************************************************
  73. //Is the quad in the frustum
  74. //************************************************************************************************
  75. procedure TBranch.isInFrustum();
  76. var
  77.   counterx,counterz: integer;
  78.   pointList: Array[0..11] of extended;
  79.   tiles: integer;
  80.   counter3: integer;
  81. begin
  82.   pointList[0] := cx;
  83.   pointList[1] := rawHeightmap[((cz*(mw+1))+cx)];
  84.   pointList[2] := cz;
  85.   pointList[3] := cx+cw;
  86.   pointList[4] := rawHeightmap[((cz*(mw+1))+cx+cw)];
  87.   pointList[5] := cz;
  88.   pointList[6] := cx+cw;
  89.   pointList[7] := rawHeightmap[((cz*(mw+1+ch))+cx+cw)];
  90.   pointList[8] := cz+ch;
  91.   pointList[9] := cx;
  92.   pointList[10] := rawHeightmap[((cz*(mw+1+ch))+cx)];
  93.   pointList[11] := cz+ch;
  94.   if(polygonCompletelyInFrustum(4,pointList)) then
  95.   begin
  96.     //Add all tiles to the tilesInFrustum array
  97.     tiles := length(tilesInFrustum);
  98.     counter3 := 0;
  99.     setLength(tilesInFrustum,length(tilesInFrustum)+(cw*ch));
  100.     counterx := cx;
  101.     counterz := cz;
  102.     while(counterz < cz+ch) do
  103.     begin
  104.       while(counterx < cx+cw) do
  105.       begin
  106.         tilesInFrustum[tiles+counter3].x := counterx;
  107.         tilesInFrustum[tiles+counter3].y := counterz;
  108.         inc(counter3);
  109.         inc(counterx);
  110.       end;
  111.       counterx := cx;
  112.       inc(counterz);
  113.     end;
  114.   end
  115.   else
  116.   begin
  117.     if(polygonInFrustum(4,pointList)) then
  118.     begin
  119.       //Check if the branch are in the frustum
  120.       if(cw <> 1) and (ch <> 1) then
  121.       begin
  122.         subBranch1.isInFrustum();
  123.         subBranch2.isInFrustum();
  124.         subBranch3.isInFrustum();
  125.         subBranch4.isInFrustum();
  126.       end
  127.       else
  128.       begin
  129.         setLength(tilesInFrustum,length(tilesInFrustum)+1);
  130.         tilesInFrustum[length(tilesInFrustum)-1].x := cx;
  131.         tilesInFrustum[length(tilesInFrustum)-1].y := cz;
  132.       end;
  133.     end;
  134.   end;
  135. end;
  136.  
  137. //************************************************************************************************
  138. //The calcTilesInFrustum function creates an array of TPoint that contains the positions of the tiles that are in the frustum
  139. //************************************************************************************************
  140. procedure calcTilesInFrustum();
  141. begin
  142.   //Is the root in the frustum?
  143.   setLength(tilesInFrustum,0);
  144.   root.isInFrustum();
  145. end;
  146. end.
  147.  


This is the sclMath unit:
Code:
  1.  
  2. {$MODE FPC}
  3. unit sclMath;
  4.  
  5. {***********************************************************}
  6. {*sclMath                                 date: 26/6/2004  *}
  7. {*author: Bart Tierens                    edited: 26/6/2004*}
  8. {*Frustum culing based on code from                        *}
  9. {*http://www.markmorley.com/opengl/frustumculling.html     *}
  10. {***********************************************************}
  11. interface
  12.  
  13. uses gl,glu,sysUtils;
  14.  
  15. function
  16. procedure ExtractFrustum();
  17. function PointInFrustum(x,y,z: extended): boolean;
  18. function PolygonInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
  19. function PolygonCompletelyInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
  20. var
  21. frustumdata: Array[0..5] of Array[0..3] of extended;
  22.  
  23. implementation
  24.  
  25. //************************************************************************************************
  26. //Extracts the frustum
  27. //************************************************************************************************
  28. procedure ExtractFrustum();
  29. var
  30. proj: Array[0..15] of glfloat;
  31. modl: Array[0..15] of glfloat;
  32. clip: Array[0..15] of extended;
  33. t: extended;
  34. begin
  35.  
  36.     //Get the current PROJECTION matrix from OpenGL
  37.     glGetFloatv(GL_PROJECTION_MATRIX,@proj);
  38.  
  39.     //Get the current MODELVIEW matrix from OpenGL
  40.     glGetFloatv(GL_MODELVIEW_MATRIX,@modl);
  41.  
  42.     //Combine the two matrices (multiply projection by modelview)
  43.     clip[0] := modl[0] * proj[ 0] + modl[ 1] * proj[ 4] + modl[ 2] * proj[ 8] + modl[ 3] * proj[12];
  44.     clip[1] := modl[0] * proj[ 1] + modl[ 1] * proj[ 5] + modl[ 2] * proj[ 9] + modl[ 3] * proj[13];
  45.     clip[2] := modl[0] * proj[ 2] + modl[ 1] * proj[ 6] + modl[ 2] * proj[10] + modl[ 3] * proj[14];
  46.     clip[3] := modl[0] * proj[ 3] + modl[ 1] * proj[ 7] + modl[ 2] * proj[11] + modl[ 3] * proj[15];
  47.  
  48.     clip[ 4] := modl[ 4] * proj[ 0] + modl[ 5] * proj[ 4] + modl[ 6] * proj[ 8] + modl[ 7] * proj[12];
  49.     clip[ 5] := modl[ 4] * proj[ 1] + modl[ 5] * proj[ 5] + modl[ 6] * proj[ 9] + modl[ 7] * proj[13];
  50.     clip[ 6] := modl[ 4] * proj[ 2] + modl[ 5] * proj[ 6] + modl[ 6] * proj[10] + modl[ 7] * proj[14];
  51.     clip[ 7] := modl[ 4] * proj[ 3] + modl[ 5] * proj[ 7] + modl[ 6] * proj[11] + modl[ 7] * proj[15];
  52.  
  53.     clip[ 8] := modl[ 8] * proj[ 0] + modl[ 9] * proj[ 4] + modl[10] * proj[ 8] + modl[11] * proj[12];
  54.     clip[ 9] := modl[ 8] * proj[ 1] + modl[ 9] * proj[ 5] + modl[10] * proj[ 9] + modl[11] * proj[13];
  55.     clip[10] := modl[ 8] * proj[ 2] + modl[ 9] * proj[ 6] + modl[10] * proj[10] + modl[11] * proj[14];
  56.     clip[11] := modl[ 8] * proj[ 3] + modl[ 9] * proj[ 7] + modl[10] * proj[11] + modl[11] * proj[15];
  57.  
  58.     clip[12] := modl[12] * proj[ 0] + modl[13] * proj[ 4] + modl[14] * proj[ 8] + modl[15] * proj[12];
  59.     clip[13] := modl[12] * proj[ 1] + modl[13] * proj[ 5] + modl[14] * proj[ 9] + modl[15] * proj[13];
  60.     clip[14] := modl[12] * proj[ 2] + modl[13] * proj[ 6] + modl[14] * proj[10] + modl[15] * proj[14];
  61.     clip[15] := modl[12] * proj[ 3] + modl[13] * proj[ 7] + modl[14] * proj[11] + modl[15] * proj[15];
  62.  
  63.     //Extract the numbers for the RIGHT plane
  64.     frustumdata[0][0] := clip[ 3] - clip[ 0];
  65.     frustumdata[0][1] := clip[ 7] - clip[ 4];
  66.     frustumdata[0][2] := clip[11] - clip[ 8];
  67.     frustumdata[0][3] := clip[15] - clip[12];
  68.  
  69.     //Normalize the result
  70.     t := sqrt( frustumdata[0][0] * frustumdata[0][0] + frustumdata[0][1] * frustumdata[0][1] + frustumdata[0][2] * frustumdata[0][2] );
  71.     frustumdata[0][0] /= t;
  72.     frustumdata[0][1] /= t;
  73.     frustumdata[0][2] /= t;
  74.     frustumdata[0][3] /= t;
  75.  
  76.     //Extract the numbers for the LEFT plane
  77.     frustumdata[1][0] := clip[ 3] + clip[ 0];
  78.     frustumdata[1][1] := clip[ 7] + clip[ 4];
  79.     frustumdata[1][2] := clip[11] + clip[ 8];
  80.     frustumdata[1][3] := clip[15] + clip[12];
  81.  
  82.     //Normalize the result
  83.     t := sqrt( frustumdata[1][0] * frustumdata[1][0] + frustumdata[1][1] * frustumdata[1][1] + frustumdata[1][2] * frustumdata[1][2] );
  84.     frustumdata[1][0] /= t;
  85.     frustumdata[1][1] /= t;
  86.     frustumdata[1][2] /= t;
  87.     frustumdata[1][3] /= t;
  88.  
  89.     //Extract the BOTTOM plane
  90.     frustumdata[2][0] := clip[ 3] + clip[ 1];
  91.     frustumdata[2][1] := clip[ 7] + clip[ 5];
  92.     frustumdata[2][2] := clip[11] + clip[ 9];
  93.     frustumdata[2][3] := clip[15] + clip[13];
  94.  
  95.     //Normalize the result
  96.     t := sqrt( frustumdata[2][0] * frustumdata[2][0] + frustumdata[2][1] * frustumdata[2][1] + frustumdata[2][2] * frustumdata[2][2] );
  97.     frustumdata[2][0] /= t;
  98.     frustumdata[2][1] /= t;
  99.     frustumdata[2][2] /= t;
  100.     frustumdata[2][3] /= t;
  101.  
  102.     //Extract the TOP plane
  103.     frustumdata[3][0] := clip[ 3] - clip[ 1];
  104.     frustumdata[3][1] := clip[ 7] - clip[ 5];
  105.     frustumdata[3][2] := clip[11] - clip[ 9];
  106.     frustumdata[3][3] := clip[15] - clip[13];
  107.  
  108.     //Normalize the result
  109.     t := sqrt( frustumdata[3][0] * frustumdata[3][0] + frustumdata[3][1] * frustumdata[3][1] + frustumdata[3][2] * frustumdata[3][2] );
  110.     frustumdata[3][0] /= t;
  111.     frustumdata[3][1] /= t;
  112.     frustumdata[3][2] /= t;
  113.     frustumdata[3][3] /= t;
  114.  
  115.     //Extract the FAR plane
  116.     frustumdata[4][0] := clip[ 3] - clip[ 2];
  117.     frustumdata[4][1] := clip[ 7] - clip[ 6];
  118.     frustumdata[4][2] := clip[11] - clip[10];
  119.     frustumdata[4][3] := clip[15] - clip[14];
  120.  
  121.     //Normalize the result
  122.     t := sqrt( frustumdata[4][0] * frustumdata[4][0] + frustumdata[4][1] * frustumdata[4][1] + frustumdata[4][2] * frustumdata[4][2] );
  123.     frustumdata[4][0] /= t;
  124.     frustumdata[4][1] /= t;
  125.     frustumdata[4][2] /= t;
  126.     frustumdata[4][3] /= t;
  127.  
  128.     //Extract the NEAR plane
  129.     frustumdata[5][0] := clip[ 3] + clip[ 2];
  130.     frustumdata[5][1] := clip[ 7] + clip[ 6];
  131.     frustumdata[5][2] := clip[11] + clip[10];
  132.     frustumdata[5][3] := clip[15] + clip[14];
  133.  
  134.     //Normalize the result
  135.     t := sqrt( frustumdata[5][0] * frustumdata[5][0] + frustumdata[5][1] * frustumdata[5][1] + frustumdata[5][2] * frustumdata[5][2] );
  136.     frustumdata[5][0] /= t;
  137.     frustumdata[5][1] /= t;
  138.     frustumdata[5][2] /= t;
  139.     frustumdata[5][3] /= t;
  140. end;
  141.  
  142. //************************************************************************************************
  143. //Returns true if the point is in the frustum
  144. //************************************************************************************************
  145. function PointInFrustum(x,y,z: extended): boolean;
  146. var
  147.   p: integer;
  148. begin
  149.   p := 0;
  150.   while(p < 6) do
  151.   begin
  152.     if((frustumdata[p][0] * x + frustumdata[p][1] * y + frustumdata[p][2] * z + frustumdata[p][3]) <= 0 ) then
  153.     begin
  154.       PointInFrustum := false;
  155.       exit;
  156.     end;
  157.     inc(p);
  158.   end;
  159.   PointInFrustum := true;
  160. end;
  161.  
  162. //************************************************************************************************
  163. //Returns true if the polygon is completely or partially in the frustum
  164. //************************************************************************************************
  165. function PolygonInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
  166. var
  167.   f,p: integer;
  168. begin
  169.    f := 0;
  170.    while(f < 6) do
  171.    begin
  172.       p := 0;
  173.       while(p < numpoints) do
  174.       begin
  175.          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
  176.          break;
  177.          inc(p);
  178.       end;
  179.       if(p = numpoints) then
  180.       begin
  181.         PolygonInFrustum := false;
  182.         exit;
  183.       end;
  184.      inc(f);
  185.    end;
  186.    PolygonInFrustum := true;
  187. end;
  188.  
  189. //************************************************************************************************
  190. //Returns true if the polygon is completely in the frustum
  191. //************************************************************************************************
  192. function PolygonCompletelyInFrustum(numpoints: integer;pointlist: Array of extended): boolean;
  193. var
  194.   p: integer;
  195. begin
  196.   p := 0;
  197.   while(p < numpoints) do
  198.   begin
  199.     if not (pointInFrustum(pointList[p*3],pointList[p*3+1],pointList[p*3+2])) then
  200.     begin
  201.       polygonCompletelyInFrustum := false;
  202.       exit;
  203.     end;
  204.   inc(p);
  205.   end;
  206.   polygonCompletelyInFrustum := true;
  207. end;
  208. end.
  209.  


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
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  Seite 1 von 1
  [ 1 Beitrag ] 
Foren-Übersicht » English » English Programming Forum


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 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.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.011s | 16 Queries | GZIP : On ]