Jump to content
  • Advertisement
Sign in to follow this  
rafalk

Octree/Frustrum/LOD/Occlusion Culling

This topic is 4130 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

Hi All, I have few questions about topics described in the subject. For those methods (Octree/Frustrum/LOD/Occlusion Culling) what is the best algorithm at now? The NET has many old docs stuff about algorithms of Octree/Frustum/LOD/Occlusion Culling. But now there are new techniques. Do you know these new algorithms for Frustum/LOD/Occlusion Culling and new structures as octree using by new games? Regards, Rafal

Share this post


Link to post
Share on other sites
Advertisement
rafalk -

I combine all of these techniques - I'm not sure there is a 'best' algorithm out of that set since they all pretty much have completely different uses, however, I think some people may swap out an octree for a kD-tree (a 3D-tree specifically) or something else that suits them.

- Krum

Share this post


Link to post
Share on other sites
Hard to name the best one, since many of them depends of the application and hardware caps. Only for VFC with AABBs could I say that the p-n vertex version is one of the best you can do IMHO.

Share this post


Link to post
Share on other sites
Is kD-tree enough fast for collision detect? I haven't tested kD-tree yet so I'm not familiar with this structure.
Can you describe some names of algorithms which you use for frustum and occlusion culling?
In frustum stage I'm using octree but I'm still searching something more efficient, maybe kD-tree will be enough.

darkelf2k5 you wrote some shortcuts but can you describe this more? :) (I know what AABB means)

Thanks,
Rafal

Share this post


Link to post
Share on other sites
I've used what I call a "loose fitting kd tree" which I prefer over an octree. Why? Well, I split nodes where I want to, instead of requiring binary subdivision. The "loose fitting" part means I don't split triangles - any node's children are guaranteed to fit within the node, but they may overlap (due to border triangles). You can still use them for occlusion query, or anything else where a heirarchy helps out, like frustum culling.

I've not used them for collision query specifically, basically because I've been using commercial physics packages for my collision detection, and they all have specific collision formats that are optimized for query. That said, you could use a kd tree for collision, but even if you do, I would recommend using different geometry for collision versus visual, as the goals of the two types of geometry are usually significantly different.

Share this post


Link to post
Share on other sites
Quote:
Original post by JasonBlochowiak
you could use a kd tree for collision, but even if you do, I would recommend using different geometry for collision versus visual, as the goals of the two types of geometry are usually significantly different.
Can you expand on this and give some details of how a KD-tree might be used differently for visual and collision? Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by JasonBlochowiak
I would recommend using different geometry for collision versus visual, as the goals of the two types of geometry are usually significantly different.


Don't you think that using other type of geometry (k-d tree or something else) is losing memory? Because then I will have trees for visual and other trees for collision detect.

Share this post


Link to post
Share on other sites
Quote:
Original post by rafalk
Quote:
Original post by JasonBlochowiak
I would recommend using different geometry for collision versus visual, as the goals of the two types of geometry are usually significantly different.


Don't you think that using other type of geometry (k-d tree or something else) is losing memory? Because then I will have trees for visual and other trees for collision detect.


Yes, it's likely that this will consume more memory, but give you better performance. As with everything, exactly how this balances out will depend on your data, but I'm generalizing here for most first or third person type games.

In addition to things like wanting curbs to be slopes (for collision) instead of little vertical walls (for visuals), there are other ways in which you'd choose different tesselation for visuals vs. collision. A window might need visual geometric detail to give some depth to it, but it might be unimportant to model that detail in the collision, for example.

You can take a look at how some of the physics packages out there deal with polygon soup collision geometry to get some ideas as to how you might want to approach alternate data layout for collision layers.

Btw, these days texture memory footprint is usually a much bigger deal than either visual or collision geometry.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!