# Slow BSP-Tree visibility checking

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

## Recommended Posts

Hi everyone!

I'm currently reworking my culling strategy and I came to a point where I just don't really know of what to do from here.

My current project is to improve the renderer of an older game (Open-World RPG) and it's working very nice so far, just not as fast as it could.

(Using D3D11, C++, if that matters)

This game basically has a static world-mesh and objects stored in a BSP-Tree, so I already have that. The BSP-Tree itself is created around the world-mesh and breaks the world down into little about 5 meter-AABBs of ingame space, which then contain a list of the objects resisting in that leaf.

Also bigger objects may are registered in multiple leafs as all of them are roughly the same size.

That leads me to following approach:

• Walk the BSP-Tree and check visibility to cut of branches
• If gotten to a leaf, iterate over the objects in all lists (Outdoor, Indoor, Small, etc)
• Check a flag if an object has been drawn before (Big-Object issue) and register it in the renderer
• After that, copy all instance-IDs to the GPU, where I remap that ID to a static World-Matrix-List in a structured buffer.

If I initialize everything only once, putting every object into the renderlist, then I can draw my whole world at about 200fps, which is nice. If I enable the culling I am down to ~100fps while not even drawing 1/4 of them.

Using profiling, I have found out that most of the time is spent in the function that iterates through the objectlists of a BSP-Leaf.

It basically only does this, like 5 times for the different lists:

if(nodeDistance < vobOutdoorDist)
{
for(auto it = node->Vobs.begin(); it != node->Vobs.end(); it++)
{
GVobObject* vob = (*it);

{
// Just draw
vob->DrawVob();
vob->SetCollectedFromTreeSearch();
BspDrawnVobs.push_back(vob);
}
}
}


Internally the "DrawVob"-Method only pushes an indexvalue to an std::vector after the first time it has been called. It is still slow when I remove the code inside it completely.

It would be great if someone could tell me how this kind of scene is usually handled efficiently. By the way, it is still slower, even if I completely remove every code in the "DrawVob"-Method, so it's nothing in there causing the slowdown.

##### Share on other sites

Do you keep BspDrawnVobs vector alive between checks, or create it every time you enter leaf node?

Is it vector, and not list?

##### Share on other sites

I made sure this stays allocated. It's a std::vector<GVobObject*>. I think the slow part is actually to call the virtual methods of the objects so they can register their instances, since there are so many of them!

##### Share on other sites
could you please run a profiler and show us the output?
that's more likely leading to an improvement than your guesses and our guesses based on your guesses;)

##### Share on other sites

How many objects in total?

Some micro-optimizations:

Is the distance-test squared or do you do the sqrt? (should be irrelevant but one of those things..)

Is that test done once and applied to all 5 lists, or do you use a separate distance?

Can the lists be combined to one?

Remove the iterator-loop and change to something like first obtaining vobs.data() and iterating with an index. (Probably shouldn't but often does make a difference).

Try changing alreadyCollectedFromTree to something like integerSet.contains(vob ID).. you could start with std::set<int>, though I think that does allocations so you might want to find another one or use an allocator.. unless you already do it like that. Also remove the function-call and make that ID public constant or something.

Does DrawVob have to be virtual, or could it be optimized to like a list of indices or IDs that could be pre-computed on create and/or update-methods unrelated to drawing?

Do 'collectedFromTree' and 'bspDrawnVobs' have to be two lists, or do they share the same information so they could just be the same integer-set?

Maybe show the whole method and not just the part inside the distance-check too..

1. 1
2. 2
Rutin
20
3. 3
khawk
17
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013710
×