Archived

This topic is now archived and is closed to further replies.

aDasTRa

[quadtrees]

Recommended Posts

i''ve been trying to code a quadtree lately, but i am a little stuck. i can get the quadtree created alright (using a method very similar to the one in an article on this site). my problem is with actually determining whether the nodes are in the frustrum or not. kind of a fundamental problem ... the problem is the camera will have full freedom; can move along all three axes, and it''s yaw and pitch can change (no roll). my idea for determining the visible nodes was just to ''create'' a polygon that represents the intersection of the ground plane and the field of view. the ground is going to be completely flat. anyways, i would use this intersection polygon to test against the nodes... i just don''t know how to (efficiently) get such a polygon. any one have any suggestions? is there another (easier) way to do this? any sites, or articles, i should check out? fyi i am using ogl w/ c++... thanks <(o)>

Share this post


Link to post
Share on other sites
A fast and simple solution would be:
vectorC is the viewing direction of your camera
vectorN1..4 are the 4 vectors from the camera position to the 4 node edges

One node is now in view if the angle between vectorC and vectorNi is smaller than your FoV angle you defined for your application. The angle can be measured by a simple vector dot product. To prevent performing a cos() for each node in each frame, the cos() factor can be precomputed.
So your final node test will be:

for( i = 1 to 4 )
if( vectorNi * vectorC < const )
then in view

Note that your horizontal FoV is somewhat greater than the vertical FoV by the relation of screenwith to screenheight.



- thomas

Share this post


Link to post
Share on other sites