DGL
https://delphigl.com/forum/

Frustum culling and quad tree problem
https://delphigl.com/forum/viewtopic.php?f=19&t=3180		 Seite 1 von 1
Autor:  BTierens [ Mi Aug 18, 2004 16:42 ]
Betreff des Beitrags:  Frustum culling and quad tree problem
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
Seite 1 von 1 Alle Zeiten sind UTC + 1 Stunde
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/