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

[RestlessRodent]

You do not have to use a linedef as the split line. In theory you can split a map in a way where no split segs are generated, however there are some maps where this will be impossible or will create an extremely lopsided node structure (where most of the nodes are on the same side, which defeats the purpose of having a BSP). Determining the best split line would be a very time consuming operation not to mention that the problem is difficult to begin with algorithmically to do in a short amount of time.

Also based on looking, I do not believe MaxED's map has any split partitions which intercept only vertices and not any lines (in the middle of them).

scifista42 said:

Graf Zahl, I get an impression that you're not even trying to understand the tricks I described in my original post, you merely see my later posts where I reference them, and condemn them as "magic", even though I had described their principle before.

OK, let's face this from a different point of view. I would give you a proof. How minimally complex does a map have to be that you would accept you were wrong if you saw the map partitioned without splitting segs and working properly under vanilla? Would this map suffice? (it has 4 vertices, 6 linedefs, and 3 sectors in total)

From a human perspective such a problem can seem really simple, from a computers perspective it can be really complex. Thus the programmers in us when we see your text demand algorithms and/or mathematical proofs (filled with tons of equations).

Graf Zhal and Linguica's negative response to your "trust me, it will work!" can be thought up as this: You are jumping out of a plane with a parachute. You turn to Graf Zhal and he says "Trust me, it works!" and then you turn to Linguica and he says "Trust me, it will work!". So then you jump out of the plane. After you reach a certain distance you decide to pull the cord on your parachute. The chute does not open. So you try to pull the backup and that does not work either. So eventually you either fall to your death and die or you try to decrease your air speed by spreading your body out and hope you get lucky when you actually hit something or the ground. Chances are that your death is likely.

[Graf Zahl]

andrewj said:

The rendering algorithm which the Build engine uses is a "wall sorter", so I believe the answer is yes.

It does, indeed. And it's the biggest performance bottleneck in the Build engine.
The whole point of the BSP is to AVOID at-runtime sorting of geometry - and it's what makes large open levels possible to begin with.

BSPs have one nice property - and that's, no matter where you start and where you look at - you will always get a perfectly sorted - front to back - list of segs from the same data set.

And I stand by my opinion - that's not possible with the 'subworld' approach, because to cover all eventualities the resulting data needs to be magnitudes larger, and will quickly exceed all memory limits - because you need a different set of data for each place in the map (and most likely also for each direction to look at) and then need some glue on top of it to paste it all together. Because whatever data comes out, without some massive tinkering it does not possess the 'one set fits all' property of a true BSP.

[scifista42]

Graf Zahl said:

Actually, the mere fact that you are running into this problem with such a simple map is saying a lot about the feasibility of the entire approach - if the whole point is to avoid splits, the cost is definitely too high.

True in certain cases, but I believe that in most cases of real reasonably-sized maps, the cost wouldn't be that high and the algorithm be actually beneficial.

I have thought about it again. The simplest example with 3 subworlds would require 6-9 additional nodes in total. 3 nodes for partitioning, 3 nodes for each subworlds, and (possibly) 3 nodes for each complement world.

The triangle example I've posted before would require exactly 9 nodes in total for the entire tree. If you imagine the middle linedefs as thin strips of void (rather than double-sized linedefs), it would make the map non-convex (?) and still require exactly 9 nodes in total for the whole tree:

 
 
               /|\
              / | \
             /  |  \
            /   |   \
           /    |    \
          /     |     \
         /      |      \
        /       |       \
       /      __|__      \
      /    __/     \__    \
     /  __/           \__  \
    /__/                 \__\
   //_______________________\\
 
 

I've also thought of an U-shaped map, which is non-convex and also would require exactly 9 nodes in total:

 
 
    +-----+     +-----+
    |     |     |     |
    |     |     |     |
    |     |     |     |
    |     |     |     |
    |     |     |     |
    |     |     |     |
    |     +-----+     |
    |                 |
    +-----------------+
 
 

Or an U-shaped map with a strip of 2-sided linedefs going along its middle, like below. This structure would require 12 18 nodes in total, which is still low-enough for me to handle:

 
 
    +--+--+     +--+--+
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  +-----+  |  |
    |  +-----------+  |
    +-----------------+
 
 

I would realistically make BSPs for either of these maps without splitting segs, in next days. OR try to explain them, but you'd have to elaborate how I should approach the explaining, because I seem to be failing at that.

[printz]

Some programmer should volunteer to automate this experiment. Writing nodes by hand is too much. I wonder how much computational effort is it to decide how to (1) split concave sectors ideally and (2) cluster subworlds ideally. What to do with unclosed sectors? They can be wild.

Anyway, can this proposed method minimize the number of subsectors (at least inside each subworld)? My project AutoDoom uses nodes, but not for rendering. I wonder if it would make any impact, though. The maps that my nodes are applied to are very dense because they mesh over the real Doom maps, with added complexity.

[Graf Zahl]

printz said:

Anyway, can this proposed method minimize the number of subsectors.

Don't get your hopes up. I'm still convinced that this entire idea is dubious at best and utter nonsense at worst, and I am tending more to the utter nonsense side.

If it works, will it reduce the number of subsectors?
No, definitely not. This will require a lot more nodes and that automatically increases the number of subsectors.

[scifista42]

printz said:

Anyway, can this proposed method minimize the number of subsectors (at least inside each subworld)?

Actually it's not guaranteed. For maps containing mostly convex sectors (or relatively simple non-convex ones), yes, it will minimize number of subsectors. For maps containing mostly very wildly non-convex sectors, not necessarily. Look at the triangle-shaped ASCII art map layout a few posts above. Traditional BSP would split it into 4 subsectors. My method would split it into only 3. Now look at MaxED's map screenshot. Traditional BSP would split it into 3 subsectors. My method would have to split it into 5. (Actually, there is yet another way to make that map out of only 1 subsector in total, as long as the segs are ordered in a certain way inside SEGS lump.)

Graf Zahl said:

This will require a lot more nodes and that automatically increases the number of subsectors.

No, because the "additional" nodes would serve to redirect traversal into the correct parts of the tree, rather than actual partitioning.

[Graf Zahl]

Tell me, how do you plan to determine on which side of a partition line you are, if you 'redirect' to somewhere else in the tree.

This particular bit of information is absolutely crucial for some stuff, e.g. finding a subsector from a coordinate or determining sight via BSP.

[scifista42]

As I've tried to explain before: Each world has its own "little" BSP tree (a proper, normal BSP tree, as you like it) only to determine which of its subworlds (not subsectors!) is the closest to the camera. The engine will traverse this tree and find the subworld. The crucial thing is that this "little BSP tree" will never be climbed back towards root node, because rendering of the whole map will be guaranteed to end sooner that it would happen. That's because the subworld's base node will redirect the BSP to a branch that will first render the subworld itself, then the subworld's complement (=a world with an area fully covering its sibling subworlds), and then (if the parent world itself had a complement world) redirect to a branch of the parent's complement world, and so on recursively. The traversal would technically go deeper and deeper and further from root node, even when it's ("semantically") returning towards root node when going to render the parent complements.

[Graf Zahl]

That doesn't answer the question. Again you manage to say little to nothing with lots of words.

How will you find the proper subsector for a point with an algorithm like:

If (point on front side of node) traverse front node tree
else traverse back node tree

This only works if everything below the node is on the same side of the partition line.
Which also implies that the BSP must be properly defined.
Which implies that there may be no 'redirects' because they by their very definition may lie on the other side of the partition line.

So please, provide a SIMPLE example. I don't even need it in map format, a diagram is fully sufficient and I'm dead certain I can pick it apart in no time.

[scifista42]

Here is a node diagram for the U-shaped map. The map has 8 vertices V1-V8, 3 subsectors S1-S3, and the rendering tree* has 9 nodes, each having a name (for clarity) and a partition line (from Vx to Vy) to decide whether to enter right child or left child. "V1->V1" line always directs traversal to right child first.

*Not a tree by definition of the term, since 2 branches join, but it doesn't matter here.



EDIT: Fixed an error in the diagram, picture updated.

[Linguica]

scifista42 said:

The engine will traverse this tree and find the subworld. The crucial thing is that this "little BSP tree" will never be climbed back towards root node, because rendering of the whole map will be guaranteed to end sooner that it would happen.

This is mistaken. The Doom engine has no functionality to "bail out" of a BSP walk in the middle once it determines that the screen has been drawn completely. It will always end up back at the root when it is done.

[scifista42]

So, what does the engine do when it finds out that the screen has been drawn completely? Does it continue traversing the tree and continue trying to draw subsectors? If not, it's practically the same as what I said. The tree will be climbed back to root only after all rendering will be already done.

[Linguica]

scifista42 said:

So, what does the engine do when it finds out that the screen has been drawn completely? Does it continue traversing the tree and continue trying to draw subsectors? If not, it's practically the same as what I said. The tree will be climbed back to root only after all rendering will be already done.

Despite your "if not," assumption, YES it continues trying to draw subsectors. The engine never "finds out" that the screen is drawn completely. It has no conception of this.

[scifista42]

But they won't actually get drawn, right? Because all parts of the screen are already filled, right? If so, traversing them will merely delay end of the rendering, but won't spoil the rendering. Or is this also a wrong assumption?

[Graf Zahl]

Ok. That thing's actually too simple to construct a situation where it definitely may fail because in all 3 cases the origin subsector will already take care of clipping away the obstructed parts so there is no possible chance that a part lying in the back may ever be processed too early. In other words: The map is in a state where your approach is impossible to test.

But it definitely shows one problem that will make it break apart, and it's one of the issues I already pointed out:

You need 9 nodes and subsector leaves in the tree to handle 3 actual subsectors. And you can be dead certain that this number will increase quadratically if the complexity increases. Right now it's 3*3 for 3 subsectors, if we go on with this we might have 100*100=10000 for 100 subsectors and 1000*1000=1000000 for 1000 subsectors. This will become unmanageable quite quickly on this single ground alone. A vanilla compatible BSP can only have 32767 subsectors or nodes so you'd have a hard limit of less than 200 subsectors. That's not much...

scifista42 said:

But they won't actually get drawn, right? Because all parts of the screen are already filled, right? If so, traversing them will merely delay end of the rendering, but won't spoil the rendering. Or is this also a wrong assumption?

It can find out if the back side is obstructed but this is not a reliable check, it's merely a means for optimization.

But since your entire BSP is already twisted and degenerate I wouldn't take the integrity of your node bounding boxes for granted. These are being used here to clip away the back sides.

To make it short: Your approach makes it nearly impossible to define these well, so with that most of the efficiency gets thrown out of the window.

[scifista42]

Graf Zahl said:

The map is in a state where your approach is impossible to test + most of the efficiency gets thrown out of the window.

Cool! Looks like you can't pick the algorithm apart just by seeing the diagram, as you planned. It's a very little progress and you don't wordly admit it, but I'm glad for this progress anyway. I'm fine with taking little steps to convince you, as long as there keeps being some progress. I would of course welcome if you were active about trying to discover how this algorithm could work and even be beneficial in practice, rather than couldn't.

Graf Zahl said:

And you can be dead certain that this number will increase quadratically if the complexity increases.

No, it won't.

Well, it would, if the whole map had to be partitioned by this algorithm only.

But that's not my plan.

Remember that lower iterations of the tree can utilize traditional BSP tree structure. My algorithm is meant to keep splitting the map up to getting it to a state when every subworld can be partitioned via traditional BSP without splitting segs, and then do it. In majority of real maps that don't deliberately try to be "impossible to be partitioned without splitting segs" as much as possible, my algorithm would have to be used just several times in several iterations, and the remaining low nodes would form traditional BSP trees for each subworld. Result: BSP tree with no seg splits, and everything good that follows from the fact.

As a quick proof of the fact that complexity doesn't increase quadratically, I would make you a diagram for the U-shaped map with a strip in the middle. It contains 6 subsectors, and it's going to require 18 nodes to be fully partitioned, not 36 as you would expect. That diagram might also fulfil your request for a map "in a state where the approach is possible to test".

 
 
    +--+--+     +--+--+
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  |     |  |  |
    |  |  +-----+  |  |
    |  +-----------+  |
    +-----------------+
 
 

[Graf Zahl]

scifista42 said:

Cool! Looks like you can't pick the algorithm apart just by seeing the diagram, as you planned. It's a very little progress and you don't wordly admit it, but I'm glad for this progress anyway. I'm fine with taking little steps to convince you, as long as there keeps being some progress. I would of course welcome if you were active about trying to discover how this algorithm could work and even be beneficial in practice, rather than couldn't.
No, it won't.

No, it isn't. Don't get your hopes up. There's just 3 subsectors and they are so closed off that many problems cannot even surface to begin with.

I can easily see how the approach you use can create ordering problems but with everything being closed off by one-sided walls the map simply does not have enough substance to put your idea to the test.

You need something a bit more open and interconnected to get some valid confirmation.

And before we forget it:

How are you going to address the node tree's bounding boxes? This would be crucial for everything to work without each subsector being processed multiple times.

[scifista42]

Graf Zahl said:

I can easily see how the approach you use can create ordering problems but with everything being closed off by one-sided walls the map simply does not have enough substance to put your idea to the test.

You need something a bit more open and interconnected to get some valid confirmation.

If you showed me an example of such map, one that won't take me ages to make a diagram / hex-edited tree for, and waited for me to make it, would it make a good next step to a valid confirmation for you? I think it would. Please pick a suitable map.

Graf Zahl said:

And before we forget it:

How are you going to address the node tree's bounding boxes? This would be crucial for everything to work without each subsector being processed multiple times.

As for bounding boxes: All nodes of each "little BSP tree" (the one splitting world into subworlds) should have bounding boxes to cover the entire area of all subworlds that can potentially be entered from the respective branch of this "little BSP tree". All other nodes should have normal bounding boxes, that means corresponding to the area of the world they actually represent.

As for subsectors being processed multiple times: There will always be a risk that each subsector may be processed multiple times. The structure itself guarantees that it won't happen sooner than the whole map is already rendered. So as I said in a reply to Linguica: It may cause some slowdown, but not break the rendering.

[Graf Zahl]

scifista42 said:

If you showed me an example of such map, one that won't take me ages to make a diagram / hex-edited tree for, and waited for me to make it, would it make a good next step to a valid confirmation for you? I think it would. Please pick a suitable map.

Anything I proposed so far was rejected. How about using MaxED's map from a few pages back? If that's too much I'm sorry but then I consider your approach a proven failure.

As for bounding boxes: All nodes of each "little BSP tree" (the one splitting world into subworlds) should have bounding boxes to cover the entire area of all subworlds that can potentially be entered from the respective branch of this "little BSP tree". All other nodes should have normal bounding boxes, that means corresponding to the area of the world they actually represent.

... and there every thought about efficiency gets thrown out of the window - as expected. You cannot set this up so that all the backsides get skipped and some subsectors will be processed multiple times, meaning all segs in there will be run through the clipper multiple times. As Linguica already said, the engine has no concept of 'having filled the entire screen'. It will run through the entire BSP, skipping some backsides, and processing others, and in the process doing a lot of redundant work. And just in case it may be interesting - the clipper is one of the performance bottlenecks here, you do not want to throw more stuff at it than absolutely necessary.

As for subsectors being processed multiple times: There will always be a risk that each subsector may be processed multiple times. The structure itself guarantees that it won't happen sooner than the whole map is already rendered. So as I said in a reply to Linguica: It may cause some slowdown, but not break the rendering.

Don't be so sure.

But you know what: I think this is going in circles because you never address any of the issues that may be pointed out, they always get dismissed out of hand without any concrete evidence - solely based on some half-baked knowledge of how the renderer works and assuming that your idea is 100% perfect.
Science doesn't work like that. It's not my task to prove you wrong, it's your task to prove beyond any doubt thart you are RIGHT!

[scifista42]

Graf Zahl said:

Anything I proposed so far was rejected. How about using MaxED's map from a few pages back? If that's too much I'm sorry but then I consider your approach a proven failure.

MaxED's map requires only a single node (root), directing to a single subsector, which contains 7 segs in this order:



My approach would be possible too, sure, but why bother with 30 nodes when I can use one? There are no split segs anyway!

Graf Zahl said:

it's your task to prove beyond any doubt thart you are RIGHT!

I know, and I'm trying to. It doesn't seem to be easy, I never had to do anything analogous before, and doing mathematical proofs has always been my weak side (even though I'm fine with most other fields of math I studied at high school), and doing presentations even weaker side. This is why I'm asking for guidance with this proving thing. I really, really think that what I invented may be put to great usage, perhaps after optimization and debugging, and that's why I posted about it so soon after thinking it out (which I believe I did sufficiently to be sure there's something to it, though).

[Linguica]

scifista42 said:

MaxED's map requires only a single node (root), directing to a single subsector, which contains 7 segs in this order:

http://i.imgur.com/wC1sKUc.png

My approach would be possible too, sure, but why bother with 30 nodes when I can use one? There are no split segs anyway!

It might render right, but what about monster logic? Wouldn't a monster on the other side of the pillar try and shoot you anyway, because it was in the same subsector and assumed it had a clear LOS? (I don't actually know the answer to this.)

edit: it actually looks as if P_CheckSight() and its associated functions don't just assume there is a clear line of sight if two things are in the same subsector, which kind of surprises me, actually.

[Linguica]

Here's a curiosity:



One subsector. 8 segs. 0 nodes. Works fine.

http://www.doomworld.com/linguica/hax/donut.wad

[andrewj]

If there are 0 nodes then it won't work in vanilla. Code in vanilla assumes there is a root node.

[Linguica]

andrewj said:

If there are 0 nodes then it won't work in vanilla. Code in vanilla assumes there is a root node.

Vanilla Doom specifically checks if there are 0 nodes and if so just assumes there is a single subsector 0 to be drawn. I could (and indeed did) make a single arbitrary root node that just points to the subsector on both sides, but might as well leave it out.

[andrewj]

Sorry, I don't know where I got that from (was soooooo sure too).

[scifista42]

The nice thing here is that, even if the middle pillar was filled as a 2nd sector, like this:




The map could be partitioned without splitting segs, via only 3 subsectors and 2 nodes, both of which always returning right child first:




The first subsector would render outer segs of the middle sector, the second subsector would render the inner segs of the middle sector, and the third subsector would render the outer segs of the outer sector.

In fact, this structure could be iterated for any number of sectors inside other sectors! First render outer segs of all middle sectors (from the outest one to the innest one), then render inner segs of all middle sectors (from the innest one to the outest one), then finally render the very outest sector's outer segs.

This is also what I'd like to see incorporated in a real nodebuilder, assuming it isn't yet.

[Graf Zahl]

scifista42 said:

This is also what I'd like to see incorporated in a real nodebuilder, assuming it isn't yet.

I don't think it is.
And I don't think that node builders will try this. At least for node builders that are designed to create GL nodes it's rather pointless because GL nodes REQUIRE convex subsectors. (Question: Is there even one node builder still in development that cannot build GL nodes...?)


Another issue here:

If the nodes always return right side first, this will DEFINITELY break R_PointInSubsector which no longer can find the correct one. For this function you need to ensure that any subsector can be reached reliably, otherwise the gameplay may glitch.

[Gez]

scifista42 said:

The nice thing here is that, even if the middle pillar was filled as a 2nd sector, like this:

http://i.imgur.com/CNaZ8up.png


The map could be partitioned without splitting segs, via only 3 subsectors and 2 nodes, both of which always returning right child first:

http://i.imgur.com/z5kETUb.png


The first subsector would render outer segs of the middle sector, the second subsector would render the inner segs of the middle sector, and the third subsector would render the outer segs of the outer sector.

I now understand less about Doom's nodes than I did before.

[Graf Zahl]

Not really. Of course such degenerate node trees require careful seg ordering. If you got a sector with a hole in the middle as a single subsector and the inner linedefs as the first segs, followed by the outer linedefs it should be renderable.

I'm not really so sure about the nested setup. I am fairly convinced that it'll fail at least in R_PointInSubsector.

But seriously, why should anyone bother about those special cases? They cannot really occur in actual maps so optimizing for them seems rather pointless.

[RestlessRodent]

If you break the assumption as it has been for many years that subsectors are convex, then any code which changes that will break. When it comes to bots for example, now you do not have a subsector based navigation mesh and you must create a new one.

Linguica said:

Here's a curiosity:

http://i.imgur.com/5oyBhirl.png

One subsector. 8 segs. 0 nodes. Works fine.

http://www.doomworld.com/linguica/hax/donut.wad

It is time for a new megawad! 1 subsector and 0 nodes! Woo!