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.... ;-( )

You could do a few speed ups in your test code, such as:

1)test the square of the distance instead of distance (to avoid sqrt)
2)inline your functions
3) return booleans instead of using a contitional (although I would hope the compiler fixes this anyways):
return ( px > ax && px < bx && py > ay && py < cy );
not
if( px > ax && px < bx && py > ay && py < cy )
return true;
else
return false;
4) don''t double or triple compute values like (x2a-x1a), do it once store it and use it again
5) don''t mix float and double, just use float

All of that said, are you sure that its really your checking code that is causing the slow down, and not the logic in your render code? I can''t imagine even if you did all that checking that it would take over 600 milliseconds on a modern computer to check less than 256 nodes. You can profile just the checking portion of your code and see how long it takes -- i''m certainly guessing its a lot less than 2/3 of a second.