Sign in to follow this  

How To Find All Polys Within A Distance To Camera?

Recommended Posts

Hi, I'm an audio developer currently experimenting with audio algorithms in 3D environments (OpenGL). At the moment my "worlds" are very simple, consisting of around 50 polygons. I'd like to see how my algorithms work in more complex worlds (thousands of polygons or more) however I've run into a problem. What I need is a function that returns all polygons with a certain range (say "x") of the user/camera position. One way I thought of doing this was to use a BSP Tree and test each polygon until a point is reached where all polygons are beyond x. As an experiment, I've implemented a 1D BSP Tree (based on the code found in Brackeen's "Developing Games in Java"). I can do a Front-To-Back sort using this tree. However, the sample code sorts the complete list of polygons. What I'd like to do is return the polygons one-at-a-time in nearest-to-furthest order. Something like this: Poly poly = getNextPoly(Poly previousPoly); I imagine that what I really need is a collision test between a circle (defined by radius "x" and centred at the user position) and each polygon. What I don't want to do is test every polygon in the world. What's the best way to do this? Thanks in advance.

Share this post

Link to post
Share on other sites
Sort your polygons into a quadtree/octree. Within each zone in the tree, you can depth-sort the child polygons. Then you can easily write a function that returns all zones within X units of your viewpoint, and you can choose which 'reachable' zones get priority, and only operate on the individual polygons within each prioritized zone.

Share this post

Link to post
Share on other sites
Since you want to get the length between the camera and the polygon, you could just calculate the distance between the camera and the polygon's center.

dist = sqrt( (( camera.x - polyCenter.x ) * ( camera.x - polyCenter.x )) +
(( camera.y - polyCenter.y ) * ( camera.y - polyCenter.y )) +
(( camera.z - polyCenter.z ) * ( camera.z - polyCenter.z )) );

If you don't already have it, you'll need to calculate the center point of your polygon.

// Average out each vertex
for( int i = 0; i < vertCount; ++i )
polyCenter.x += polyPoint[i]->x;
polyCenter.y += polyPoint[i]->y;
polyCenter.z += polyPoint[i]->z;

polyCenter.x /= vertCount;
polyCenter.y /= vertCount;
polyCenter.z /= vertCount;

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this