Jump to content
Search In
  • More options...
Find results that contain...
Find results in...

ZokumBSP development

Recommended Posts

Figured I should post/blog a bit about my ongoing development of ZokumBSP and the proces around it. I'll mostly cover thing that are specific to ZokumBSP, but there will be the occasional post about code and algorithms that can be used in other nodebuilders.

The current release version is 1.0.9. There's a beta version 1.0.10 bundled with Doombuilder X with a few more features.

Share this post

Link to post
Posted (edited)

Node building: An efficient way to find the boundaries of node entries.

The code inherited from ZenNode goes something like this:
Create a new node.
Find a partition line.
Go through all the segs on each side, figure out the maxX, maxY, minX and minY for each side.
Store that into the current node, process child nodes/sub sectors.

The method being run is FindBounds in ZenNode and is mostly called from two spots in CreateNode. In BSP the corresponding method is FindLimits and is also called from a method called CreateNode.

The problem with this approach is that it will have to go through every seg in the map on the first node. Then split it into two parts, and go over all those segs as well one more time. If there's an average depth of 8 in the tree, the initial segs in the map will have to be gone through 8 times.

So I figured I could do it faster by exploiting the fact that the node tree is a tree. One side of a node's boundary box would always be the same as the span of both of that sides of a node's children. It's easier to grasp from a bottoms up approach. If a node has two subsectors as children.
Child one spanning from 0 to 128 in X and from 0 to 128 in Y.
Child two spanning from 128 to 256 in X and from 0 to 384 in Y.

The parent of this node would then have that node span from 0 to 256 in X and 0 to 384 in Y.

So I decided to build a recursive method to iterate through the node tree and set all the boundaries in the complete tree. The Only time I would have to go through a list of segs would be for the sub sectors, since those are the leaves of the tree.

The code I came up with isn't exactly pretty, but it works, and reuses the old FindBounds method. It gets called just after CreateNode is called to make the root node of the node tree. Here's the code:

void PostFindBounds( wNode *node) {

        // If it's a subSector, calculate from segs!
        // If not, recursively figure it out.

        for (int nodeChild = 0; nodeChild != 2; nodeChild++) {
				// printf("Checking side %d\n", nodeChild);
          		// If a child is a subsector, we can use the segs to get bounds
                if (node->child[nodeChild] & 0x8000) {

                        int subSector = node->child[nodeChild] - 0x8000;

                        // printf(" FindBounds: child: %d, subsector: %d, first: %d, num %d\n", &node->side[nodeChild], subSector, ssectorPool[subSector].first, ssectorPool[subSector].num);

                        FindBounds( &node->side[nodeChild], &segStart [ssectorPool[subSector].first], ssectorPool[subSector].num);

                } else { // The child is another node, we need to figure out it's bounds and then use the bounds
                  		// printf(" PostFind recursive on node %d\n", node->child[nodeChild]);
						PostFindBounds( &nodePool[node->child[nodeChild]]); // recursion

                        // printf("\nBefore: %d, %d, %d, %d\n", node->side[nodeChild].minx, node->side[nodeChild].miny, node->side[nodeChild].maxx, node->side[nodeChild].maxy );

                  		// Check the children's two sides on this side to get this node's side (boundary box)
                        if (nodePool[node->child[nodeChild]].side[0].minx < nodePool[node->child[nodeChild]].side[1].minx) {
                                node->side[nodeChild].minx = nodePool[node->child[nodeChild]].side[0].minx;
                        } else {
                                node->side[nodeChild].minx = nodePool[node->child[nodeChild]].side[1].minx;

                        if (nodePool[node->child[nodeChild]].side[0].miny < nodePool[node->child[nodeChild]].side[1].miny) {
                                node->side[nodeChild].miny = nodePool[node->child[nodeChild]].side[0].miny;
                        } else {
                                node->side[nodeChild].miny = nodePool[node->child[nodeChild]].side[1].miny;

                        if (nodePool[node->child[nodeChild]].side[0].maxx > nodePool[node->child[nodeChild]].side[1].maxx) {
                                node->side[nodeChild].maxx = nodePool[node->child[nodeChild]].side[0].maxx;
                        } else {
                                node->side[nodeChild].maxx = nodePool[node->child[nodeChild]].side[1].maxx;

                        if (nodePool[node->child[nodeChild]].side[0].maxy > nodePool[node->child[nodeChild]].side[1].maxy) {
                                node->side[nodeChild].maxy = nodePool[node->child[nodeChild]].side[0].maxy;
                        } else {
                                node->side[nodeChild].maxy = nodePool[node->child[nodeChild]].side[1].maxy;

                        //printf("After:  %d, %d, %d, %d\n", node->side[nodeChild].minx, node->side[nodeChild].miny, node->side[nodeChild].maxx, node->side[nodeChild].maxy );


Performance wise perf gave me the following data:

Conventional FindBounds approach:
0.12%  zokumbsp  zokumbsp           [.] FindBounds
0.03%  zokumbsp  zokumbsp             [.] PostFindBounds

Roughly 4 times faster. It's not a very heavy part of the node builder process, but there's some nice benefits. This moved complexity out of CreateNode and into a separate post-step, tightening the inner core loop slightly. This is much more important when working on a multi-tree approach. The idea is there to compute the sub trees of two or more partition lines and compare them and pick the best. If boundaries are done inside CreateNode, a large majority of boundary boxes computed would be thrown away. Doing one final pass on the finished tree is a much more elegant solution.

The approach here could probably be used in other nodebuilders, at least the ones that derive from ZenNode and BSP. The reason the printf debugs have before and after lines is that I ran both the in-createnode approach and the post-approach to ensure the data was the same while bug fixing and tweaking.

Share this post

Link to post
Posted (edited)

I haven't updated here in a while, but I haven't been idle. There's a nice thread about an error with bad seg angles causing rendering errors. The best known being the star structure near the exit on map09. I am sure there are other similar errors on other maps. I made a post asking for other places things got screwed up without much of a reply apart from the map09, e1m1 ones and a vague reference to one on map30.

I've been working on a tool to tweak partition lines. If i can get it work manually, I'll eventually include the code into ZokumBSP. As always it will be optional to use it or not. I've named it partition tuning. The goal is to fine tune the partition line to reduce the amount of errors. Reducing errors should result in fewer/or smaller slime trails and other oddities.

The tool can't remove all slime trails, but it _might_ remove some. It should also hopefully allow for a bit of manual tweaking for the perfectionists. A given partition line might have slime trails no matter what, but with proper tuning, we might be able to change where they occur. Having a slime trail in the middle of a nice and important vantage point is a lot more annoying than having one inside a monster closet, dark area or one with similar textures leaking into eachother.

Similar textures would be rendered different if they are at different heights, but it would probably be a lot less jarring.

At the moment the tool can read a bunch of data from command line and compute how wrong the points are compared to the partition line. There might be some clever hacks that could reduce the chance of a slime trail in favor of slightly funky wobbly lines :D I'll see what I come up with. Since it's command line, it could be used manually on any existing map and with any existing node builder.

This is not a very user friendly tool. Don't expect guis or wizards or hand holding.


./partitiontuning 3136 -3072 3990 -5370 3520 -3584 3408 -3432 3136 -3072
Partition data: 3136,-3072 | 3990,-5370
Line from: 3136,-3072 to 7126,-8442
Distance from point #1  ( 3520,-3584) to line: 2.86992630 ! Bad rounding, should have inserted a seg?
Distance from point #2  ( 3408,-3432) to line: 3.62328196 ! Bad rounding, should have inserted a seg?
Distance from point #3  ( 3136,-3072) to line: 0.00000000 - All good!

Thi is just an early version, any automated tuning hasn't been applied.

Share this post

Link to post
Posted (edited)

I've been working on the partition tuning algorithm and here's some test data for e1m1 to try out.

The general idea is to add some of this code to be optionally turned on in zokumbsp. Some authors might prefer their maps to be built in this manner than the standard way. I am a firm believer in giving tools to mappers and let them decide what to should be done with their creations.

This is an early version and fairly hackish, and there might still be improvements to be had. It is incredibly slow due to a fair amount of brute force involved.

Use slade 3 or something similar for this. I chose e1m1 since we all know it and the slime trail near the zig-zag is easy to find. It's not perfect, but it's not half bad I think. Modify the following lumps in doom.wad e1m1.wad (save it as e1m1hax.wad).

162: Partition X: 3272, Partition Y: -3352, Partition X Diff: 4020, Partition Y Diff: -5318.

(non purist tweak below)

437: X: 3455, Y:-3494


438: Angle: -19128
473: Angle: -19176

Note that the angle already stored in those segs are probably a bit off due to the angle bug in DoomBSP. These are merely corrections to make it fit better with the slightly modified inserted vertex. If you're using a different editor than slade and it wants a proper unsigned BAM, just compute 65536 - angle to get the proper numbers. I think the value should probably be recomputed anyway to fix the bug.

This modification doesn't HAVE to have the vertex modified. If you want to be a purist, you should probably go with these values instead:

162: 3277,-3259, 4009,-5304

Edited by zokum

Share this post

Link to post

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