🔒 Locked

[quadtrees]

Started by aDasTRa Nov 12, 2001 at 10:14 PM 1 replies 600+ views

Original Post

Nov 12, 2001 at 10:14 PM

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)>

Renus

Nov 13, 2001 at 3:31 AM

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

aDasTRa

Author

aDasTRa

Nov 13, 2001 at 4:09 PM

thanks thomas. that solution is almost...too easy...

...

<(o)>

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.