Sign in to follow this  
aravind

Which algorithm is more efficient for visibility culling? BSP or OCTree?

Recommended Posts

Hi, I am currently Working in 3D modelling Project..which is like a tool to add/delete the objects(shapes like sphere,retangle etc..) dyanmically by the user. And the Problem is When more number of objects are added(imagine the 2floor house is built in this tool) the rendering speed is damn slow. So i have planned to introduce the BSP algorithm for visibilty culling which is used to render the object that is visible for eyes(view frustrum).I read so many atricles and am confused whether the BSP is efficient for my project or not.. Can anyone have a experience in BSP or any Visibilty culling Algorithms?? if can suggest/assist me to choose the best algorithm for my project.

 

 

Note:

Project is developed in Directx . C#

Yet Now no Visibility Culling algorithm is used .

 

Share this post


Link to post
Share on other sites

I am using an Octree in my prototype and it's working well enough. Here are some high level notes on my implementation:

* I rebuild the whole tree every frame. Yes, it's a bit more expensive than doing an in-place update, but it is a simpler solution. Good enough for a prototype!
* I store every octree region as a bounding box (in XNA, that's just two vector3's, or 24 bytes of memory)
* I only let a node exist if there is actually data inside of it, whether its objects or child nodes.

* In order to figure out what I need to draw, I intersect the camera view frustum against the octree and get a list of intersections. The intersected objects are the only objects I need to draw.
* I maintain a static list of all objects in the octree. Rather than visiting each node recursively and updating objects, I just traverse the master list and update from there (so much more simple).
* Collision detection is pretty straight forward: You only have to test for collision of an object against all objects within its containing node and any child nodes. In a perfectly balanced octree, this runs in O(log base 8 N).


Before you go rushing off to implement an Octree, you should back up a few steps and implement and profiler to measure how long each section of your code takes. What is its actual performance (measured in ticks or microseconds)? This shouldn't take more than 2-3 hours max to implement (compared to days for a good tree implementation from scratch). Once you have a good profiler to measure execution time, you can measure specific sections of your code and identify bottlenecks. It's much more scientific than guesswork. You might be optimizing a problem you don't have... ie, you're rendering hundreds of high res meshes to the screen even if they're really far from the camera, in which case you want to look at a "Level of Detail" switching scheme instead.

Share this post


Link to post
Share on other sites


brute force, just iterate over the set of renderables and cull them against the view frustum. Even better, pack the bounding boxes with handles back to the owner into an array and iterate that much more cache efficient, minimal branching (in fact, you can delay branching till the end in most cases).

 

To backup Washu I can say I've done thesis on view frustum culling and bruteforce method culls 340,000 AABBs in 1 millisecond. If this isn't sufficient you might have different problems.

Share this post


Link to post
Share on other sites

Thanks for your info washu and slayemin...

 

Zoashi kaba.. could u please share the materials or website links about bruteforce method.

Share this post


Link to post
Share on other sites

You can use Sweep and Prune that is commonly used in Physics.

SAP tests can be done with 3 "if" checks.

Updating the the structure is O(1) too.

 

I'm managing a 100k cubes demo in WebGL with 44fps. Without SAP it runs at 7fps only.

Share this post


Link to post
Share on other sites


You can use Sweep and Prune that is commonly used in Physics
I find that debatable, Bullet allows use of a AABB box tree and it quickly provides the same performance of SAP.

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