DGL
https://delphigl.com/forum/

Frustum culling and quad tree problem
https://delphigl.com/forum/viewtopic.php?f=19&t=3181		 Seite 1 von 1
Autor:  BTierens [ Mi Aug 18, 2004 17:04 ]
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?

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:
  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
Autor:  Stucuk [ Mi Aug 18, 2004 18:06 ]
Betreff des Beitrags: 
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.
Autor:  BTierens [ Di Aug 24, 2004 08:07 ]
Betreff des Beitrags: 
I've found the bug.
Thanks for your help.
Seite 1 von 1 Alle Zeiten sind UTC + 1 Stunde
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/