Jump to content
  • Advertisement


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


What's the point of quad/oct/BSP trees

This topic is 6135 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Been readin up a fair bit and am starting to become happy with how to implement these structures, but I''m not entirely sure WHY I''d want to...? - seb

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
say youve got a collision world that has 1000 faces..
you dont want to check every face every frame cause
if you did you be running at like a frame per second.
so you use these structures and algorithms to figure
out where you are faster so that you only need to
check a few faces instead of all of em..

Share this post

Link to post
Share on other sites
Guest Anonymous Poster
A quad or oc tree is a very fast way of finding an object.
at each level with 4 (for a quad tree) boolean check you get ride of 75% of your object.
If you have 1000 objects in your world, and you need to find a specific one, you get ride of 750 with 4 if statment and get ride of another 200 objects at the next level. If you had to go trough a linked list and the object you are looking for is the last one, you will have 1000 check before you find an object...
Talk about SLOW!!! 1000 check per frame....
When would you use that, you will ask,
Well a good example is culling. If you have (again) a 1000 object in a huge world and you only have 10 object in front of the camera. With a algorithm that check if each node of the tree is within the fustrum or not, you parse the tree and find the 10 object that you send to opengl pipe line and not the other.
If you send all object to the pipeline, Opengl has to do it for you and it kills the fps. If you do it with a linked list.... ouch... you need to check every single object....
Same story with ordering transparent object since they have to be drawn in a certain order...
Basically, you can''t do a professinal producte without it....

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!