Some musings on BSP tree generation

[zokum]

Once in a while I write some rather in-depth stuff on here about some obscure Doom tech thing. This is one of those.

How to improve Doom engine maps BSP tree generation.

This is probably of interests to the people maintaing glbsp, bsp, ajbsp and the new one I saw the other day, VigilantBSP.

A while back I posted the first proof of concept of a vertex pair partition line algorithm. Instead of just considering all the linedefs in a map as partition lines, it would instead try all the possible pairs of vertices. The original line concept is from Abrash Black book, and has the advantage that it also finds out really easily if a sector is convex or not. The amount of data you need to go through is fairly managable. A map with 100 linedefs means one needs to check 100 partition lines, and if a line is unsuitable as a partition line (it is an edge line), it can be flagged to never be suitable. An edge will always be an edge, no matter how much you divde the map.

The main problem with this is that it can create many unnecessary splits and it will not guarantee an optimally built bsp tree.

Writing a good vertex pair algorithm is much harder, but there is a way to get some of the performance of a vertex pair, without all the hassle of going through all of them.

When a partition line splits a seg into two, what one could do is to then check if a better partition line would be found if you would do a partition line that starts in one of the two origin points of the original line, but with the other end as a vertex in the map and you still end up with the same same sorting apart from one or more fewer splits.

If a partition line sorted lindefs 0, 1, 2, 3, and 5 and split 6 into one side and 4,7,8 and split 6 in the other side, a better partition line would be one that split 0, 1, 2, 3 and 5 into one side and 4, 7, 8, and 6 into another side.

I think this has the potential to reduce the splits in a map quite nicely without sacrificing the quality of the partition line, and it shouldn't need that much more cpu power, making it a clear improvement of the algorithms found in conventional bsp tools.

Fewer splits would also lead to better rendering of the maps, allow for more detail and collission detection that matches the rendered world more accurately.

I have always wondered how much more complex the console version maps could have been if the bsp/blockmap tools were better. And even if they weren't any more complex, fewer splits would mean better performance, given that more diagonal lines wouldn't hurt performance too much if that happens.

I do have another slightly more high-level BSP topic I wanna write a post about. Maybe in a few months? Depends on whether this kind of content/posts are well received or not.

PS: I would love for someone to make a new BSP tool from scratch that is more suitable for advanced algorithms. The basic design in Zennode / ZokumBSP isn't all that great for more complex changes.

[zokum]

There are many map builder tools (node builders / bsp generators). The name node builder is really inaccurate since Doom maps traditionally require three different sets of algorithms applied to them to generate the needed data. And of those, only one generates nodes. The ones generating nodes also generate segs and ssectors. I have skipped all the non-vanilla stuff like zdbsp, glbsp etc. There are also specialized tools like RMB just for the reject table.

Are there any important vanilla tools I have missed here?

Current and usable tools usable for production use
BSP: https://doomwiki.org/wiki/BSP_(node_builder)
ZokumBSP: https://doomwiki.org/wiki/ZokumBSP

ZdBSP: https://zdoom.org/wiki/ZDBSP

Newer tools I haven't tested
AJBSP: https://gitlab.com/andwj/ajbsp
VigilantBSP: https://github.com/VigilantDoomer/vigilantbsp

Older tools I haven't tested
DeepBSP: https://doomwiki.org/wiki/DeePBSP

Older, but of historic interest, may have known bugs etc
IdBSP (DoomBSP port) https://www.doomworld.com/files/file/652-idbsp-101-dos-binaries/

ZenNode: https://doomwiki.org/wiki/ZenNode

 

Edited June 27, 2022 by zokum

[Gez]

1 hour ago, zokum said:

I have skipped all the non-vanilla stuff like zdbsp

ZDBSP can generate vanilla nodes too.

[zokum]

2 hours ago, Gez said:

ZDBSP can generate vanilla nodes too.

Cheers, I hadn't thought of that, and since it seems to be original code, this is an interesting use case. Many node builders are based on plain old BSP, I mistakingly assumed ZdBSP was as well. Thanks for the info!