New Super BSP building algorithm! No seg splits, works for any map, vanilla comp.!

[scifista42]

I believe I finally invented it!

Ahem...

Super BSP, a new Doom BSP building algorithm, guaranteed to work for every map, never split any segs, and produce vanilla compatible nodes that will make the engine render the map properly.

Well, it's only a theory so far - but a thorough explanation ensues right now!


Imagine this part of a map, called PA, with a root node corresponding to it, also called PA. I will be calling it "world" from now on. You want to build a BSP tree for this world without splitting any segs:




If there was a way to split the world in half without intersecting any of the linedefs, you would simply do it, create a new node for each child world, and recursively continue the BSP building algorithm for each of the child worlds.

If there was a way... But in this case, there isn't. So, what to do?

The very first step of Super BSP algorithm (at the beginning, before any BSP building starts at all) is to go through the list of all sectors in the whole map, and for each one, check if it is convex. If the sector is convex, make a subsector on its place. If it isn't convex, add as few as possible "formal" lines to split it into convex subsectors. Each formal line must start in an existing vertice, and end in another existing vertice. Intersections with linedefs (or other formal lines) are NOT allowed. Yes, this should be done at the beginning, without regard to any BSP structure at all.

Back to our world "PA". Let's look how individual subsectors look like inside this world:




The first step of Super BSP alrorithm related to actual node building is to "formally" group the world's subsectors into convex subworlds (as few ones as possible), bounded either by their linedefs, formal lines, or implicit formal lines out of the world's boundaries. At this point, you may also add new formal lines and split subsectors in half, if it would decrease the number of subworlds required to cover the whole world's area. On the following picture, newly added formal lines are drawn as purple:




So, now you have subworlds. Let's give each one a name and a node of the same name, similarly how the whole "PA" world has a name and a root node. Note that even subworlds consisting of a single subsector (like the green one, A4) need to get its own node generated at this point!!!




Here comes the next important step: Build a "formal" BSP tree to divide the world's area into "formal" subsectors, each of them unambiguously belonging to a single subworld. Similarly how in traditional Doom BSP, each subsector belongs to a single sector. Note that the partition lines of this BSP tree may intersect anything as needed, but they don't split segs as they normally would in traditional Doom BSP algorithm. Let's pretend that segs don't exist at this point. You are merely splitting the space.




Why did we do it? Because the BSP tree can be traversed, and the appropriate "formal" subsector closest to the camera can be found during the game's runtime.

Formal subsectors are called "formal" for a reason: They will not be referenced by leaf nodes of the little BSP tree we've just created. Instead, each leaf nodes will reference the "An" node of the respective subworld! So it won't be the formal subsector, but the subworld itself which will be entered after traversal.




Now let's talk about the structure of a subworld. It is NOT an equivalent of a world on the next step of BSP recursion! At least not yet.

Next important step: Generate a "complement" world "Bn" for each subworld "An". Such a "complement" world equals to all subworlds of "PA" combined, excluding subworld "An". As an example, here is a complement world of subworld A1:




Now comes the most clever, most important step:

For each An, generate a node "Xn" and a node "Pn". Then connect An, Xn, Pn and Bn in this structure:




How do you make an "always first" node? Simply define the node's partition line in a way that is guaranteed to return right child first, no matter what, at this point.

So, when the game will run and get to this point of BSP traversal: P1 will be traversed and rendered first (=the subworld closest to the camera). Then the traversal will continue to X1, from which it will continue to traverse and render B1 (the remaining subworlds of the same parent world). Eventually, traversal will continue to PX.

PX?

What is PX? It has not been mentioned yet!

Beware a total recursive mind screw: PX is PA's equivalent to X1 of A1. The world PA itself is equivalent to P1 of A1. Yes, PA also has its complement world, called PB. Here it is:




So, the traversal will continue to the complement of the parent world. And when that one will be rendered, it will continue to its parent's complement world, and then its parent's parent's complement world, etc...

Isn't it insanity?

But it guarantees that the whole map will be traversed before the tree will start climbing back to root. It's an exploit of the fact that Doom's BSP traversing ends when the engine decides that the screen is fully rendered.

Finally, we have a subworld P1 and its (or A1's... it's one and the same) complement B1. How to partition them? By the same recursive algorithm we were using for PA, of course?




Both P1 and B1 are smaller than PA, which guarantees that partitioning is one step closer to completion!

And remember - at any point during the partitioning, if there is a possibility to split the world by a single partition line, like in traditional Doom's BSP, without splitting any segs - do it! Only if there is no possibility, use this insane algorithm. Yes, they can be mixed together!


Conclusion

This algorithm never splits segs, generates no additional vertices, minimum DRAWSEGS (useful for vanilla maps), and works with minimum number of subsectors (at the cost of generating relatively many nodes). This should mean that if the algorithm got incorporated into a real nodebuilder, then nodes built by this nodebuilder will never cause any slime trails, leaking sectors or nodebuilder errors anymore. In theory.

If nobody disproves the theory, I would like to see the nodebuilder happen. If nobody else would do it first, I would do it myself even if it had to take me years, as I lack experience with programming of such "practical" utilities.

On the other hand, if the theory gets disproved, and turns out being "irreparable" by any optimizations... There was at least a chance. But I am currently convinced that there has to be a way to make the principle work.

I welcome any input related to the theory, its validity/invalidity and possible optimizations and implementations.

[Linguica]

[Ganryu]

I will have to read this one over again while making notes. I did, however, find something odd. It looks like A1, A3, A5 and A7 are not convex despite your text pointing out the subworlds are convex.

[scifista42]

Imagine their boundaries extended into the void, where everything is allowed. Then they can be considered convex, and it should suffice, given that their parent world itself is convex in the same sense. If this alone turned out to break the theory, I'd modify it to say that they need to be truly convex. :)

[Soundblock]

scifista42 said:

nodes built by this nodebuilder will never cause any slime trails

Scifista - slayer of all slimes (in theory)!

Seriously, that would be so awesome.

Hope it works!

[jmickle66666666]

Unless I missed it in your (frankly a little obtuse) explanation, but what's the advantage of your proposed bsp tool?

Also noting that the 3rd image you show contains concave "subworlds", not convex like you suggest.

[scifista42]

@jmickle66666666:
1. See the first paragraph of "Conclusion" at the end of the OP. Splitting segs on coordinates which can't be represented as exact binary integer numbers is what had caused various node builder errors since ever, caused slime trails, increased DRAWSEGS, etc, and this algorithm should be immune to all such things.
2. See my previous post.

[jmickle66666666]

Ok, thanks for the pointers.

I suppose my next request is if you could possibly write a much more concise description of how this works (and WHY at every point), to get a much clearer understanding. I've read through this twice and I still feel I'm not understanding it properly, despite experience with nodebuilders.

[scifista42]

I would like to, but I'm not good at explaining, specially explaining something that nobody else has ever explained because it wasn't invented until now. I will try to, but it may take a while, because this very explanation already took me an entire day to prepare. I hope somebody will understand it in the meantime.

[Ganryu]

What kind of a background do you have?

Would it be possible for you to write this down more formally? Ie: Write it in LaTeX and compile to a pdf.

[kb1]

@Linguica: wtff?

All points in a subsector must have a line of sight to all other points within that subsector - that's a requirement. Any split method which accomplishes that should work. A nice BSP will avoid deep depth. And, yeah, slime trails and other oddities occur at splits.

I must admit that I need some "silent time" to study what you've proposed here. The images are good, but I suggest a rigorous, step-by-step test with a small known level, either on paper, or via a program. Your test map drawing can work too, but, an exact algorithm is needed, step by step, with numbered steps, and with human observations converted to steps a program can perform.

Looking at it again, I get lost with the complement creation. What is PB? Is that another part of the existing map? Is that something created exclusively by the node builder?

You know, there's always been "minimize splits" code in nodebuilders. I guess I'm not sure what your steps accomplish (technically) that traditional builders don't. (Not that it's wrong, I just don't get it yet.)

Anyway, if you feel strongly about it, please pursue it more! Even if it doesn't work, it may lead to a new method that's better. I'm sure id Software stopped improving Doom BSP once it was working good enough for their levels.

[VGA]

Well he claims no seg splitting at all.

[Linguica]

I'm not positive, but it sounds like the idea is maybe the same or similar as something I had considered for a split-free BSP tree:

* Divide the world into your ideal convex subsectors along existing vertices
* Group these into larger convex arrangements of subsectors for funsies
* Since each node is just deciding what side of a line you are on, you can determine if you are inside a convex area by testing against each outer boundary surface
* Create a BSP tree that traverses each convex area in turn and, recursively, all the subsectors within each convex area

The problem is sorting the convex areas into the right near-to-far order which is unfortunately ignored here.

For example imagine a level like this. Surely you should be able to just have three subsectors like so:



The problem is, if you are on one part of 3 , the correct ordering would be 3 2 1:



But over in the other side it would be 3 1 2:



So how do you decide? Do you split 3 down the middle? If so you're defeating the purpose though.

You could manually have the node structure test if you were inside 1, 2 or 3, draw that one first, and then do a partition line test to determine which of the other two to draw first I guess, but I feel like this would very quickly become unreasonable when trying to scale it up.

[Linguica]

In the degenerate case you could start out determining precisely which subsector you were in, doing a couple tests to determine which proper ordering of every other subsector you should use from your exact position, and then write that entire exact ordering into the BSP tree. Then rinse and repeat with every other possible ordering and then do this again for every other subsector. This would probably shake out to somewhere in the O(n^2) range, so for a map with 1000 subsectors you could probably get a perfect tree in just a few million nodes, which might weigh in at under a hundred megabytes.

But of course, why not just list the subsectors you can ACTUALLY possibly see from a given subsector? This would work, and gain a lot of that space back. Hooray, we've implemented a Potentially Visible Set in Doom!

[RestlessRodent]

BSP splits the map in half each time (where determine the best result will take quite some time).

I suppose what you are proposing that instead of the traditional algorithm which chooses an existing linedef to be the split line, that instead the convex polygon corners are used instead?

[Linguica]

My musing was sort of a bastardization of the method of visibility determination used in Quake (and many other true-3D games).

In Quake et al, the world is split up with a 3D BSP tree, to the point where the interior volume is made up of a bunch of convex polyhedra, referred to in Quake as "leaves". We can consider these leaves as being basically equivalent to Doom's subsectors. In Quake, each leaf has a precalculated Potentially Visible Set, which tells you which other leaves are possibly visible from the current leaf. Then Quake runs through the BSP tree from the current position, but consults the PVS along the way to see if it should actually examine a given leaf or if it can skip over it.

What I'm saying you could do is to repurpose the BSP tree into a different kind of control structure, with basically two steps. The first step would be to determine which subsector you're in, like:

if(to right of subsector 1 line 1):
    if(to right of subsector 1 line 2):
        if(to right of subsector 1 line 3):
            # we are inside subsector 1
            render_from_subsector_1()
if(to right of subsector 2 line 1):
    if(to right of subsector 2 line 2):
        if(to right of subsector 2 line 3):
            # we are inside subsector 2
            render_from_subsector_2()
# etc...

(This works because you can set the back side of a BSP node to always be skipped over, simply by setting its bounding box to be 0x0. Therefore you can use a BSP node to do an if-else by having the bounding boxes on each side be 0x0; it will go down one side or the other, and when it eventually comes back up to the same node, it won't go down the other side at all.)

Anyways, then from there, you jump to another area of the BSP tree, which is simply a list of all subsectors in the level in order from nearest to farthest from your vantage point. This thereby functions as a combination of a presorted BSP tree and PVS:

render_from_subsector_1():
    render subsector 1;
    render subsector 2;
    render subsector 4;
    render subsector 3;
    # etc...

This would be represented by a constructed series of nodes where it goes down the front side every time until it reaches the bottom, and then works its way back up, with the back side of each node being an actual subsector, and rendering from nearest to farthest as it rises. Adding in logic to choose one of several orderings based on exact position within the subsector is left as an exercise for the reader.

Doing this would result in a ludicrous amount of BSP nodes, but it would at least theoretically work, and would result in a splits-free Doom level. Quake gets away with it because 1) it's still using a normal BSP tree because it doesn't care about splits, and 2) it compresses the PVS heavily. Obviously Doom doesn't have that functionality so to do this method you'd necessarily need a huge amount of redundant or near-redundant data.

[andrewj]

I think the described algorithm (in first post) completely depends on whether the renderer in Vanilla Doom can cope with segs which cross BSP partition lines (segs which are normally split by nodes builders) -- if the renderer does not handle that, there is no way the described algorithm can work.

If the renderer *can* handle it, then it is much simpler to just re-use whole segs in multiple subsectors (instead of splitting them) to get the benefit of no slime trails.

[Linguica]

andrewj said:

I think the described algorithm (in first post) completely depends on whether the renderer in Vanilla Doom can cope with segs which cross BSP partition lines (segs which are normally split by nodes builders) -- if the renderer does not handle that, there is no way the described algorithm can work.

Sure it can - the part of the engine that renders segs doesn't care about the nodes at all.

andrewj said:

If the renderer *can* handle it, then it is much simpler to just re-use whole segs in multiple subsectors (instead of splitting them) to get the benefit of no slime trails.

I don't think this would work out. Imagine a level like such:



If segs 1 and 2 were not split, and both subsectors rendered a combined seg 1+2, I can imagine a case where it renders the seg, and then tries to render the pillar in the middle of the room, only to find that the far portion of the seg is bleeding over the spot where the pillar should be drawn.

[scifista42]

Linguica said:

* Divide the world into your ideal convex subsectors along existing vertices
* Group these into larger convex arrangements of subsectors for funsies
* Since each node is just deciding what side of a line you are on, you can determine if you are inside a convex area by testing against each outer boundary surface
* Create a BSP tree that traverses each convex area in turn and, recursively, all the subsectors within each convex area

The problem is sorting the convex areas into the right near-to-far order which is unfortunately ignored here.

My algorithm solves it!

Traditional BSP rendering works like this:
1. You have a world, and you want to render it.
2. You split the world by a partition line into 2 subworlds.
3. You decide which of the subworlds is closer to the camera.
4. You draw the subworld closer to the camera, treating it as a world on its own, recursively.
5. You draw the subworld further from the camera, treating it as a world on its own, recursively.

My Super BSP rendering works like this:
1. You have a world, and you want to render it.
2. You split the world into N convex subworlds.
3. You decide which subworld is the closest to the camera.
4. You draw the subworld closest to the camera, treating it as a world on its own, recursively.
5. You draw a complement world to this subworld (=all remaining subworlds combined), treating it as a world on its own, recursively!

[RestlessRodent]

scifista42 said:

My algorithm solves it!

Traditional BSP rendering works like this:
1. You have a world, and you want to render it.
2. You split the world by a partition line into 2 subworlds.
3. You decide which of the subworlds is closer to the camera.
4. You draw the subworld closer to the camera, treating it as a world on its own, recursively.
5. You draw the subworld further from the camera, treating it as a world on its own, recursively.

My Super BSP rendering works like this:
1. You have a world, and you want to render it.
2. You split the world into N convex subworlds.
3. You decide which subworld is the closest to the camera.
4. You draw the subworld closest to the camera, treating it as a world on its own, recursively.
5. You draw a complement world to this subworld (=all remaining subworlds combined), treating it as a world on its own, recursively!

Well if you want Vanilla compat and the same NODES format, then the rendering algorithm will be exactly the same as Vanilla Doom.

However as Linguica has stated it may require redundent node structures. This would possibly cause slow down since essentially the NODES structure is a gigantic linked list. There are also limitations to the amount of memory Vanilla Doom can claim (limited to what DPMI can allocate).

Building the most optimal BSP tree would take some time so most node builders go for good enough.

[scifista42]

GhostlyDeath said:

Well if you want Vanilla compat and the same NODES format, then the rendering algorithm will be exactly the same as Vanilla Doom.

It will. My algorithm is designed as implementable with vanilla's BSP traversal rules.

GhostlyDeath said:

However as Linguica has stated it may require redundent node structures. This would possibly cause slow down since essentially the NODES structure is a gigantic linked list. There are also limitations to the amount of memory Vanilla Doom can claim (limited to what DPMI can allocate).

Building the most optimal BSP tree would take some time so most node builders go for good enough.

True, this BSP structure require more nodes in total than traditional BSP structure, traversal may be slower, and generation of the tree would be probably slower too. Those are downsides, sure. But don't forget about the advantages! I think it would be worth to have a node builder that doesn't split segs anyway. Specially smaller maps would perfectly benefit from it.

[RestlessRodent]

There would need to be lots of comparisons on varying hardware to determine if in the game such resulting nodes will be faster.

The simplest map would be basically 2 sectors, whereas on the other end there should be a computer generated map which is based on a fractal which contains polygons of varying sizes which pushes all limits without overflowing visplanes. The two maps would be built using standard node builders then this proposed node builder, and a basic run through the level (with no monsters due to subsector differences) which visits all areas. These two maps would be the control for the most part.

Such a speed test should not be limited to just x86 with a specific CPU.

If this does reach the stage for benchmarking I have various a collection of PowerPC, SPARC, and MIPS systems.

[scifista42]

GhostlyDeath said:

There would need to be lots of comparisons on varying hardware to determine if in the game such resulting nodes will be faster.

I'm 100% sure they will be slower in the game than traditionally made nodes, but shouldn't be that much slower. Similarly for the number of nodes, the number will be bigger, but not at all as much as in O(n^2) range in relation to subsector count as Linguica said. Well, at least not in average case, I guess.

[Graf Zahl]

Let's preface this with 'I have no fucking idea how this is supposed to work'...

... but...

I think this throws one of the most fundamental and most important assumptions out of the window which the renderer makes about how nodes are constructed, i.e. that the partition line is absolute, it doesn't split off selected parts of the level, it splits the entire level, or the entire current subset that is still being processed. In other words: It's of paramount importance to trivially decide whether something is on the same side of that line as the viewer or on the back side.

The important thing here is not that split segs may be bad for renderring, far worse is that your segs that cross the partition line may wreak havoc with the clipper - because you no longer have the guarantee that things get processed in proper order. It can easily happen that some extruding seg part gets processed long before the geometry in front does, and then it gets nasty - you have to add some costly checks to the code to detect these stray segs - and that will most likely negate any benefit you may gain - let alone make the entire thing incompatible with existing renderers.

[scifista42]

^ I believe my algorithm solves all of that. Nodes with partition lines intersecting segs will never directly lead into either subsectors or nodes directly representing the subsector structure, they will only lead into "formal" nodes, which then redirect to a BSP tree branch that doesn't have partition lines intersecting segs, barring other "formal" lines.

A few posts above, I made a simple description of the traversal algorithm in 5 ordered points. Don't you agree it would work?

[Graf Zahl]

Actually, I don't think so.

If a seg crosses the partition line, that extruding part can (and will!) be added by the clipper when its subsector is being processed. It doesn't really matter what else is there because once a seg gets added to the clipper, the affected view range is considered 'obstructed', and if later something else gets processed that lies in front of it, that won't be drawn. It's impossible to rule out this case entirely.

A classic BSP can rule this out because due to the strict partitioning it is 100% guaranteed that all segs are being processed in a defined order from front to back.

[scifista42]

Graf Zahl said:

If a seg crosses the partition line, that extruding part can (and will!) be added by the clipper when its subsector is being processed.

Seems like you still haven't understood. No part of any seg will be extruding from the subsector it lies in. Each seg will be fully in 1 subsector, and moreso, the total number of subsectors will be minimal possible for a given map's sector structure. Or well, sometimes only almost minimal possible... but the point about segs is always guaranteed to apply. This algorithm uses several tricks that should sort subsectors into the right order relative to the camera anyway.

[Graf Zahl]

Ok, let's leave the segs out for a moment, because it's apparently not the only issue here. Let's make it short: What you create here is not a BSP. The entire discussion should end here, actually.

The one most crucial assumption during rendering is that wherever the camera is and wherever it points to, it must be 100% assured that at no point in time it may be possible to process some part of the level that's lying behind other parts of the level that haven't been processed yet. NEVER! EVER!

You cannot guarantee this unless each partition is 100% absolute, and you cannot tinker around with this to reduce splits. Splits are a nuisance here that are required to fulfill that all-important rule, that a partition line must strictly divide its set in two subsets with no exceptions. If you are not doing this you no longer have binary space partition and therefore cannot apply the time-saving assumptions that binary space partitioning brings to a renderer.

The problem I see is that you get hung up on the subsectors. Ultimately these are not relevant. A subsector is just the bottommost leaf at the end of the tree that must be convex. That's easy to achieve - but doesn't constitute a BSP.

But I cannot see anywhere on your approach that you ensure that the rules for the nodes are obeyed. You got something that nicely divides into convex subsectors but where's the node hiearchy? How are they ordered? How do you ensure that there are no uncontrolled overlaps? That's not just a means to an end - it also needs to follow certain rules - which you seem to have conveniently thrown out of the window.

[scifista42]

Graf Zahl said:

What you create here is not a BSP.

it also needs to follow certain rules - which you seem to have conveniently thrown out of the window.

It is a BSP, and I haven't thrown those problems out of the window. My algorithm is actually designed to counter them. The OP describes the processes how to build BSP hierarchy for subworlds by "formal subsectors" (for which, unlike normal subsectors, it doesn't matter that segs are intersected, as long as the rest of the rules are followed), and the later post with 5 points describes how to traverse the BSP to always get to the correct ordering and no overlaps.

[Linguica]

scifista42 said:

My algorithm solves it!
[...]
5. You draw a complement world to this subworld (=all remaining subworlds combined), treating it as a world on its own, recursively!

This does not answer the question of how you are sorting this complement world, at all. How, precisely, are you sorting all the subsectors in this subworld from near to far?