Original Post
I''ve tried to add a QuadTree to my terrainengine. Before I did this the WHOLE Landscape was drawn, and I had about 3 fps. After I added the quadtree only 16 (of my 256) nodes were drawn but I had less than 1 fps.
Thats not the way it should be ! So what is wrong ?
To figure out if a node is visible, I did the following:
1) I checked if a point of the node is inside my viewing-triangle
2) I checked if a point of the viewing-triangle is inside my node
3) I checked if one border of the node intersects with one of the triangle (12 tests)
If it is visible I check all 4 children. If not I dont ;-) !
I used these three functions:
//------------------------------------------------------------------------------------//
// Name: PointInSquare
// Descr.: Check if P is inside square
//------------------------------------------------------------------------------------//
bool PointInSquare( float px, float py, float ax, float ay, float bx, float by, float cx, float cy, float dx, float dy )
{
if( px > ax && px < bx && py > ay && py < cy )
return true;
else
return false;
} // end PointInSquare
//------------------------------------------------------------------------------------//
// Name: PointInTriangle
// Descr.: Check if P is inside triangle
//------------------------------------------------------------------------------------//
bool PointInTriangle( float px, float py, float ax, float ay, float bx, float by, float cx, float cy )
{
float fAB = (py-ay)*(bx-ax)-(px-ax)*(by-ay);
float fBC = (py-by)*(cx-bx)-(px-bx)*(cy-by);
float fCA = (py-cy)*(ax-cx)-(px-cx)*(ay-cy);
if( fAB*fBC >0 && fBC*fCA >0)
return true;
else
return false;
} // end PointInTriangle
//------------------------------------------------------------------------------------//
// Name: CutAB_CD
// Descr.: Check if two lines intersect
//------------------------------------------------------------------------------------//
bool CutAB_CD( float x1a, float y1a, float x2a, float y2a, float x1b, float y1b, float x2b, float y2b )
{
CVector result;
double r,s;
double denominator = (x2a-x1a)*(y2b-y1b)-(y2a-y1a)*(x2b-x1b);
// If the denominator in above is zero, AB & CD are colinear
if (denominator==0)
return false;
double numeratorR=(y1a-y1b)*(x2b-x1b)-(x1a-x1b)*(y2b-y1b);
// If the numerator above is also zero, AB & CD are collinear.
// If they are collinear, then the segments may be projected to the x-
// or y-axis, and overlap of the projected intervals checked.
r=numeratorR/denominator;
double numeratorS=(y1a-y1b)*(x2a-x1a)-(x1a-x1b)*(y2a-y1a);
s=numeratorS/denominator;
// If 0<=r<=1 & 0<=s<=1, intersection exists
// r<0 or r>1 or s<0 or s>1 line segments do not intersect
if (r<0 || r>1 || s<0 || s>1)
return FALSE;
// Find intersection point
result.x = (float)(x1a + (r*(x2a-x1a)));
result.z = (float)(y1a + (r*(y2a-y1a)));
float length1 = PointDistance( x1a,y1a, x2a,y2a );
float length2 = PointDistance( x1b,y1b, x2b,y2b );
if( PointDistance( x1a,y1a, result.x,result.z ) > length1 )
return false;
if( PointDistance( x2a,y2a, result.x,result.z ) > length1 )
return false;
if( PointDistance( x1b,y1b, result.x,result.z ) > length2 )
return false;
if( PointDistance( x2b,y2b, result.x,result.z ) > length2 )
return false;
return TRUE;
} // end CutAB_CD
I also looked everywhere around the net for some tuts or examples, but found nothing. So I''m asking you:
What could be the problem ?
Is something wrong with these functions ?
Are there any mistakes in my concept ?
Do you know where to find some tuts / examples for using Quadtrees ?
Thank you VERY much, VanKurt (I REALLY NEED YOUR HELP.... ;-( )