NanoBSP

[andrewj]

NanoBSP is:

• a node builder written by me from scratch
• under a permissive license (MIT)
• easily added into vanilla-ish DOOM ports
• written in C
• only using fixed-point math, no FPU required
• pretty fast
• not as good as a stand-alone node builder
• unable to create polygons for OpenGL
• around 820 lines of code

 

More information here: https://gitlab.com/andwj/nano_bsp

 

Update: I have reworked the code to make it a lot easier to add into a port, since it no longer modifies the node_t and subsector_t structs, so functions like R_PointInSubsector() and R_RenderBSPNode() can work without changes.

Edited December 15, 2023 by andrewj

[fabian]

It's a pity that you had to change some of the basic structs used for rendering, else this could have served as a drop-in for loading maps without nodes. 

[andrewj]

12 hours ago, fabian said:

It's a pity that you had to change some of the basic structs used for rendering, else this could have served as a drop-in for loading maps without nodes. 

 

If this code would be useful for Crispy (etc), I'll definitely look at making it easier to drop-in without major changes to the rest of the engine.

[fabian]

I'm more active in developing Woof than Crispy nowadays, but for sure this code could help. We already support a variety of node formats (most prominently DeepSea and XNOD/ZNOD) but fall flat on the face for maps which do not contain any nodes themselves. It would be nice to be able to load them without any further steps required. 

[andrewj]

Yeah, it does make for a better UX when things "just work".

 

I will begin adapting the code to be more suitable, not sure when, probably next week sometime.

Edited December 14, 2023 by andrewj

[fabian]

That's awesome,  thank you!

[andrewj]

I felt like working on this today, and I'm pretty pleased with how it has turned out.

 

It should more-or-less drop into a code-base, but note that seg_t still needs two additional fields, that was fairly unavoidable.  It should work with the larger indices in Woof, like children[] of node_t , since I use int rather than short, and it will pick up the new NF_SUBSECTOR flag.  But let me know if any issues come up, happy to discuss any aspect of the code :)

[fabian]

Awesome, thank you very much! I'll look into this soon. 

 

One question, though: is this able to handle the trivial "one subsector, no nodes" case yet?

 

Edit: For example, if you save the dummy map from Eureka, it will be a single concave subsector without any nodes. 

Edited December 15, 2023 by fabian

[andrewj]

22 hours ago, fabian said:

One question, though: is this able to handle the trivial "one subsector, no nodes" case yet?

Ahh, that is an important case which I hadn't tested yet, but I just did and it works fine :)

[andrewj]

BTW, I just simplified things a little bit more and removed the "side" field which I added to the seg_t struct. That value was only needed to compute the offset, and can be determined easily enough by looking at the deltas.

[fabian]

I've got it working with only minimal changes required, thank you!

 

It seems to work well for IWAD levels, but crashes for monster maps such as planisf2.wad due to a stack overflow caused by too many recurve calls to `BSP_SubdivideSegs()`. Any ideas?

[andrewj]

I will check it out that wad and see if I can reproduce the problem.

[fabian]

You may want to try my Woof branch for that. The WAD breaks about any vanilla map limit:

 

https://github.com/fabiangreffrath/woof/tree/nanobsp

[andrewj]

1 hour ago, fabian said:

The WAD breaks about any vanilla map limit

Yeah it is quite a "monster" :)

 

Well, the issue is primarily about a loss of accuracy (due to fixed-point math), where one part of the code thinks a seg should be split, but the computed intersection point ends up in a place not really splitting the seg.

 

Will be working more on it tomorrow.....

Edited December 18, 2023 by andrewj

[andrewj]

@fabian The following 7z archive contains an updated nano_bsp.c for Woof! which fixes the infinite loop problem.  It includes the last five commits from my repo (ending with 12ec4f), plus I removed the local copy of R_PointToDist() and instead it calls P_GetOffset() from p_extnodes.c.  The planisf2.wad map is working for me now.

 

nano101.7z

 

BTW, I am glad you support a -bsp option to force generation of nodes, it was something I was thinking of myself.

 

Another BTW, you probably don't need to call the slimetrail fixing function for the XNOD family of nodes, since their vertices (for splits) are already in 16.16 precision.

 

PPS, I get collision problems in planisf2.wad in the NE area of the map, around X=6000 Y=8800 (over quite a large area actually), which must be the blockmap builder, since I tested with the wad built with ajbsp (with XNOD format) and the same thing occurred at that location.

Edited December 20, 2023 by andrewj

[fabian]

That's awesome, thank you! However, even with the latest version that you posted here, loading planisf2.wad still crashes the engine on my system.

[fabian]

Looks like the SECTORS lump for that map isn't located where it's supposed to be. Is that possible?

[fabian]

29 minutes ago, fabian said:

Looks like the SECTORS lump for that map isn't located where it's supposed to be. Is that possible?

 

Indeed! And PrBoom+ even warns about this:

 

Quote

P_SetupLevel: Level wad structure is incomplete. There is no ML_SSECTORS lump.

 

Loading the map in Eureka and saving it again fixes the lump structure and now the map loads with the internal NanoBSP, and this surprisingly fast! Thanks again for your work on this.

 

4 hours ago, andrewj said:

Another BTW, you probably don't need to call the slimetrail fixing function for the XNOD family of nodes, since their vertices (for splits) are already in 16.16 precision.

 

Right, but since other demo compatible source ports also call this function unconditionally, and since it may potentially move vertexes, I'd rather keep it as it is.

 

4 hours ago, andrewj said:

PPS, I get collision problems in planisf2.wad in the NE area of the map, around X=6000 Y=8800 (over quite a large area actually), which must be the blockmap builder, since I tested with the wad built with ajbsp (with XNOD format) and the same thing occurred at that location. 

 

Yes, and yet again PrBoom+ has a hint for us:

 

Quote

P_LoadBlockMap: This map uses a large blockmap which may cause no-clipping bugs. Toggle the "Fix clipping problems in large levels" option in the "Compatibility with common mapping errors" menu in order to activate a fix. That fix won't be applied during demo playback or recording.

 

[andrewj]

14 hours ago, fabian said:

Looks like the SECTORS lump for that map isn't located where it's supposed to be. Is that possible?

As I understand it, it is something old editors used to do, and was usually fixed by the nodes builder.  Eureka and glbsp/ajbsp all have some "lax" logic to detect such levels.  I would assume all source ports would crash and burn with such a case, but I guess ZDoom allowed it at some point.

 

I noticed the ticket for the blockmap issue later on last night, and understand it can't be fixed unconditionally due to demo compatibility.

[fabian]

12 hours ago, andrewj said:

 ZDoom allowed it at some point.

The enemy of all mapping discipline. ;)

[boris]

Planisphere 2 doesn't have the nodes built, so of course the lumps added by a nodebuilder are missing. And GZDoom has ZDBSP built in, so it doesn't care if the lumps created by the nodebuilder are missing, since it'll just build the nodes.

 

Both SLADE and the DB2 family don't have a internal node builder, so they save the maps without nodes and then run the external nodebuilder on them. Imagine if the external nodebuilders required the nodes to exist, so that the lumps are in the correct order. That would be a bit stupid.

[Redneckerz]

Just as a heads up, Woof 14.0.0 now integrates NanoBSP as a drop-in.

 

Congratulations, @andrewj

[mmx]

I was browsing your projects on https://gitlab.com/users/andwj/projects and they are all awesome. thanks for sharing this

[andrewj]

On 4/10/2024 at 1:40 AM, mmx said:

I was browsing your projects on https://gitlab.com/users/andwj/projects and they are all awesome.

Thanks!