Binary space partitioning and reducing CPU/GPU load...

Hey guys,

Got a couple questions for anyone who knows the in's and out's of Doom's binary space partitioning... my understanding is BSP is a system where the engine only renders the sectors you can see in front of you (which makes sense)... so, I have a some maps in my WAD with some very large wide open spaces and a lot of 3D floors/bridges etc... if I have a sector that is in two sections but joined (shift + J in builder) and the two sections are on opposite sides of a large wide area, is it heavier on the CPU/GPU to render that sector in full (both sections) even if I'm looking at only one section of it? Or if I made both sections their own respective sectors does the CPU/GPU load decrease because it's only rendering 1 smaller sector instead?

Basically, what is better for CPU/GPU loading? Fewer massive sectors or more smaller sectors? I'm having some framerate crunching in some of the maps and I think it's because areas behind me are being rendered by the engine because there's a part of those sectors in front of me so it's rendering more than it actually needs to at that moment...

Does this make sense to anyone? Would subdividing these large sectors into smaller pieces speed up the rendering and reduce the framerate issues?

The sectors themselves don't matter to the BSP as they are are broken up into something called "subsectors" anyway. However, in general it's better to not merge disjointed areas into a single sector, for other various technical reasons.

8 minutes ago, Linguica said:

The sectors themselves don't matter to the BSP as they are are broken up into something called "subsectors" anyway. However, in general it's better to not merge disjointed areas into a single sector, for other various technical reasons.

A lot of that comes from trying to maintain symmetry in certain level designs... joining 2 sectors that have the same textures/height/slope etc. on oppsite ends of a large area is much faster in Builder than replicating the second/third/fourth sectors (etc.) individually. If the CPU/GPU is rendering sectors behind my field of view because they're connected to sectors that are IN my field of view then it would make sense to split those joined sectors to their own respective sectors so it's only rendering what im actually looking at... yes? no?

It makes no difference to rendering speed if the sectors are "joined" (the exact same sector) or separate.  That's basically what Linguica was saying.

Also nothing behind you ever gets processed or drawn, it gets rejected fairly quickly (the BSP can help reject big chunks of the level at once).

Big open maps are always prone to slowdown, in any engine.  Add one-sided walls to block stuff from view, or simplify the geometry, those are your two main ways of improving speed.

The sectors you join (or not) in any map builder, are still treated as separate entities for the sake of rendering (subsectors, and in general each sector is split into multiple subsectors). The same goes for e.g. single long linedefs: they will still get split into shorter "segs" for rendering purposes. So, in a sense, each Doom map has two representations: an editor-friendly one, and a rendering-specific one.

44 minutes ago, andrewj said:

Add one-sided walls to block stuff from view, or simplify the geometry, those are your two main ways of improving speed.

Quoting because it's the solution

Cheers for the advice guys :)

Build a proper REJECT map if either are true:

1. You have lots of sectors.
2. You have lots of monsters (say, 500 or more)

This can make a big difference because it eliminates a lot of monster line-of-sight checks.

Actually, that "big difference" rarely sums up to a single millisecond in most cases. Even with large monster-filled maps and Doom's original sight checking algorithm you either need a very slow computer or an extremely large amount of monsters for this to make a difference.

No test I ever made over the last 15 years - and I tested this a lot on various systems with a lot of maps - showed any sign of Reject being the magic weapon some people claim it to be. There's various factors to consider here:

1. REJECT only saves time in cases where a sight check trivially fails. For successful sight checks it saves nothing.

2. Even for failed sight checks its reliability rate is 50% at the very best outside of specially designed cases. The larger the single sectors, the higher the failure rate here.

3. It's rare that all monsters will do a sight check at the same time. This is all a bit randomized and most monsters only perform a significant action every 3 or 4 tics, so even 500 monsters on a map this will mean something around 150 sight checks on average at most.

So, before repeating this claim, please back it with some data.

Anyway, the time spent in sight checking is dwarfed by both actor movement and rendering times outside of deliberately created degenerate cases.

Regarding the original question, yes, for the renderer it hardly matters. It doesn't process sectors but subsectors. But by merging disjoint parts of a map into a single sector the sound propagation will treat those areas as a single entity, allowing sound alerts to skip all natural boundaries.

^^ while it might fall into what you consider pathological/edge cases, the most recent Sunder maps had some performance issues that were greatly alleviated by a reject table. Areas that were 2-3fps and unplayable jumping back up to 35+ with the addition of a reject lump designed to prevent los checks between certain sections of the map (this was in prb+). I also recall getting a significant performance boost on slaughterfest2012_map30, which has thousands of monsters separated into mostly-disconnected areas, so the automated methods for building tables were actually quite effective.

it takes a rare type of map for reject to be valuable, but they do exist.

The operative term being "thousands of monsters". Yes, calculating line of sight is not free, but you really need a huge number of monsters for this to become a problem, with 500 it didn't even put my computer from 15 years ago under pressure.

11 hours ago, Graf Zahl said:

The operative term being "thousands of monsters". Yes, calculating line of sight is not free, but you really need a huge number of monsters for this to become a problem, with 500 it didn't even put my computer from 15 years ago under pressure.

 

Come on, Graf - you've been saying this for years. You're giving out false info, man. In utter-worst case (all zeroes and/or all sectors visible), REJECT still gets used by every port, making it absolutely free to build a proper one, and a 100% waste not to. I've seen the benefits over and over (for both algorithms - my port allows run-time switching of sight-check algorithms). When are milliseconds not valuable? It's computer speed, computer load, number of monsters, and sector spread.

And, it's not 50%. At the start of the majority of maps, the percentage of monsters that can see you trends towards 0%.

Add to that biggest modern factor: unlimited framerate: If you're borderline pushing 2 for 1 frames, that millisecond can throw you back to 35 ms., or even below, which now affects net (co-op) games, causing p2p games to lag, or forcing prediction correction of, yeah, 500+ monsters in server/client monster games. And, if not written perfectly, this is exasperated by unlimited framerate functionality.

Why un-educate people on how to give their maps an extra boost? Programmer to programmer, I am baffled by that concept.

I threw the number '500' out there. That keeps everyone happy on original 1993 equipment, which covers the whole gambit. It's not about milliseconds, it's about having a fun experience every time, via getting a smooth frame rate especially on the epic battle maps.

Fixed the issue by simply subdividing the big sectors into multiple small ones...