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

[scifista42]

Linguica said:

How, precisely, are you sorting all the subsectors in this subworld from near to far?

When possible via traditional BSP without intersecting segs, then via traditional BSP. When not, via the recursive algorithm described above. This will recursively reduce size of the world, until individual subsectors can be reached. They always will.

[Linguica]

scifista42 said:

When possible via traditional BSP without intersecting segs, then via traditional BSP. When not, via the recursive algorithm described above. This will recursively reduce size of the world, until individual subsectors can be reached. They always will.

What, this recursive algorithm?

scifista42 said:

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.

Because this is not an answer about HOW you sort these worlds. This is writing on the blackboard "and then a miracle occurs." Remember, you cannot simply sort arbitrary convex regions from near to far by any sort of trivial method, as my triangle example shows.

[scifista42]

What is not clear? How to decide which subworld is the closest to the camera? That's by the "little" BSP tree of "formal subsectors", as described in the OP. How to draw the world? I have just said it! How to sort subworlds? The post you quoted says it as well. You only decide which ONE subworld is the closest, and draw that one. The rest of subworlds (=the complement) will be sorted as a new whole world would, now smaller by the size of the closest subworld.

[Graf Zahl]

Linguica said:

This is writing on the blackboard "and then a miracle occurs."

Agreed. And it still misses the fact that the tree this generates may LOOK like a BSP but actually isn't one!

The details involved here are a lot more tricky and a lot more subtle. Bogos BSPs tend to break in non-obvious ways at non-obvious places in the map.

And last, but not least, the mere concept of an 'always first' branch is ridiculous and implies deliberately placing incorrect data in the structure.

And about this:

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.

You decide - how?
You draw this - how?

Keep in mind that Doom's rendering algorithm always starts from the top, looking at the partition line and stepping down the tree from there. It never tries to 'decide' anything, it just runs through the data without making any assumptions - and it's this precise approach that makes it FAST!

[Graf Zahl]

scifista42 said:

What is not clear? How to decide which subworld is the closest to the camera? That's by the "little" BSP tree of "formal subsectors", as described in the OP. How to draw the world? I have just said it! How to sort subworlds? The post you quoted says it as well. You only decide which ONE subworld is the closest, and draw that one. The rest of subworlds (=the complement) will be sorted as a new whole world would, now smaller by the size of the closest subworld.

No, you haven't said anything.
All you repeat is 'believe my magic, it works, trust me.'

To prove its viability you have to do a lot more, e.g. produce a small graphical mock-up of a level and present (maybe as an animated GIF) how you propose to process the tree.

But whatever, it seems to be important that you need to 'decide' something before starting. And since this seems to be crucial here, we want to know how this is supposed to be done.

[scifista42]

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)

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

[Linguica]

scifista42 said:

What is not clear? How to decide which subworld is the closest to the camera? That's by the "little" BSP tree of "formal subsectors", as described in the OP.

Let's say you have 100 subworlds in your map.

So the first step is to decide which of the 100 subworlds you are in, presumably by a similar if-else structure like the one I gave pseudocode for. I assume that's how the "formal subsectors" thing you propose would work in this case.

Then you draw that subworld by whatever means. Now you have to jump to a new "every subworld but 1" subworld.

Then you go through another big if-else thing to figure out which subworld is closest (although you're not actually INSIDE any of them so it's not quite the same). Then you draw, say, subworld 5.

Then you jump to a special "every subworld but 1 and 5" subworld and go through another if-else... etc.

This is by no means a "little" BSP of formal subsectors. As near as I can tell it is identical to my determination that you basically have to formally list, from any convex area, the near-to-far ordering of every other convex area.

[Graf Zahl]

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.

The more I try to 'understand' what you cooked up the more it convinces me that it's utter hogwash that only makes sense if you believe in it.
Sorry to disappoint you, but there isn't more I cannot say about it. It's a great snake oil sales pitch, but not more.

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)

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

No, that map would not suffice. It should be non-convex at least. With something this simplistic there's little chance to give a counter-proof (which, btw, would just be one camera position and angle where the whole thing breaks down.)

This would be a good start:

+----------+                 +------------------+
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |    /\           |                  |
|          |   /  \          |                  |
|          +--/    \---------+                  |
|            /      \        |                  |
|           /        \       |                  |
|          /          \      |                  |
|         /            \     |                  |
|        /              \    |                  |
|       /                \   |                  |
|      /                  \  |                  |
|     /                    \ |                  |
+-----------------------------------------------+

We don't want to make it too easy.

[scifista42]

@Linguica: Not exactly. Bear in mind that although the complement world was delimited as the amalgamation of certain subworlds of a parent world, the complement world can be split into different subworlds when it becomes a world on its own to be recursively partitioned. Thanks to the fact that the complement world is already smaller than the parent world, splitting the complement world into its own subworlds will be more simple than splitting its parent was. And then even more simple in the next iteration. The subworld traversal within a complement world is not the same as consecutive traversal of particular subworlds that constituted the complement world in the first place.

[scifista42]

Graf Zahl said:

This would be a good start:

+----------+                 +------------------+
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |    /\           |                  |
|          |   /  \          |                  |
|          +--/    \---------+                  |
|            /      \        |                  |
|           /        \       |                  |
|          /          \      |                  |
|         /            \     |                  |
|        /              \    |                  |
|       /                \   |                  |
|      /                  \  |                  |
|     /                    \ |                  |
+-----------------------------------------------+

We don't want to make it too easy.

Actually, this map can be partitioned with traditional BSP without splitting segs. Here is the required subsector structure:

+----------+                 +------------------+
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |    /\           |                  |
|          |   /  \          |                  |
|          +--/    \---------+                  |
|         /  /      \        |                  |
|        /  /        \       |                  |
|       /  /          \      |                  |
|     /   /            \     |                  |
|    /   /              \    |                  |
|  /    /                \   |                  |
| /    /                  \  |                  |
|/    /                    \ |                  |
+-----------------------------------------------+

The first partition line would go along one side of the triangle. The rest would be easy.

[Linguica]

I give up. You are not addressing my questions, just saying, "it'll work, trust me."

I'm not saying your idea is impossible, since like I outlined, in the worst case you could construct a giant structure listing every sorting of visible subsectors from every possible viewpoint. What I am saying, however, is that this is massively impractical, and you're not addressing anything about that at all.

[Graf Zahl]

scifista42 said:

Actually, this map can be partitioned with traditional BSP without splitting segs. Here is the required subsector structure:

+----------+                 +------------------+
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |                 |                  |
|          |    /\           |                  |
|          |   /  \          |                  |
|          +--/    \---------+                  |
|         /  /      \        |                  |
|        /  /        \       |                  |
|       /  /          \      |                  |
|     /   /            \     |                  |
|    /   /              \    |                  |
|  /    /                \   |                  |
| /    /                  \  |                  |
|/    /                    \ |                  |
+-----------------------------------------------+

The first partition line would go along one side of the triangle. The rest would be easy.

I do not want to have this split by traditional BSP, I'd like you to use this map to explain your approach.

But I concur with Linguica. You talk a lot but refuse to address the issues that get pointed out. 'Trust me, it works' is not enough.

[scifista42]

Graf Zahl said:

I do not want to have this split by traditional BSP, I'd like you to use this map to explain your approach.

My approach is: Whenever possible (without splitting segs), use traditional BSP to split the world. When not, split it via my algorithm. To make a true proof, you need a map where it's not possible. To make it possible for me to realize in a reasonable time (because all I can do is hex editing SEGS/SSECTORS/NODES), please come up with a reasonably simple map.

Also, I did try to address issues that got pointed out, both by immediate answers and by referencing respective parts of the OP. I'm sorry that I can't word it out in a way comprehensible for other people than myself. I'd really like to. If you could guide me how exactly I could explain it comprehensibly, I would surely try to.

[Graf Zahl]

scifista42 said:

My approach is: Whenever possible (without splitting segs), use traditional BSP to split the world. When not, split it via my algorithm. To make a true proof, you need a map where it's not possible. To make it possible for me to realize in a reasonable time (because all I can do is hex editing SEGS/SSECTORS/NODES), please come up with a reasonably simple map.

I don't care how you do it - but you have to prove that your algorithm actually WORKS!
Which I do not believe.
But since you are all theories with nothing concrete to point to it's difficult to tear it apart. What I want to see is some map on which you explain in detail how the nodes structure will look like with the proposed algorithm. Unless you do that there's really no point to discuss this any further, because a theory is just that - without proof it has no value.

Also, I did try to address issues that got pointed out, both by immediate answers and by referencing respective parts of the OP.

Yes, you responded - by referring to the stuff that was questioned. Sorry, that's not enough.

This has been going on for several posts now but we are still at the same point, a lengthy and convoluted description of a revolutionary algorithm but absolutely nothing to look at except rosy theories.

[scifista42]

I agree, providing a proof would be a good way to demonstrate the theory and continue the discussion. Hence I'm asking once again: Give me a SIMPLE map that we can ALL agree it's impossible to partition without splitting segs via traditional BSP. Then I will manually (via hex editing) assemble nodes for the map without splitting segs, and provide a working wad. I would prefer if I could merely explain the steps before the actual hex editing, but it looks like I can't, so I will just make the proof instead.

1. Somebody (other than me) please provide a simple map.
2. Everybody will agree the map can't be partitioned without splitting segs.
3. I will agree that the map is simple enough to take me reasonably short time to build BSP for.
4. I will make the BSP without splitting segs and post the wad.
5. You will play the map in vanilla and it will render properly.
6. You will open the wad in SLADE3 and verify that there are no seg splits.

Please.

[Graf Zahl]

I suggest taking E2M9, cutting out the right half, only using the star shaped cave area. It's only one sector but sufficiently non-convex to be strong enough proof.

[scifista42]

No it isn't, it can be partitioned with traditional BSP without splitting segs, too. Hint: The first 2 partition lines should go horizontally, one slightly above the center and one slightly below the center. Each of the resulting 3 subworlds should be split by 2 vertical partition lines, one slightly on the left from the center and one on the right from it. The rest will be easy.

[Graf Zahl]

Are you deliberately evading the issue?

The mere fact that it can be done differently shouldn't prevent you from using it to demonstrate your approach.

[scifista42]

I just want the proof to be a proper proof, so that I won't have to manually make another one later. I don't exactly enjoy hex-editing, but I want to proof my theory. So I want to already take a map impossible to partition otherwise then via my algorithm.

[Graf Zahl]

I don't care how. By all means, add something to the map that makes a tradiditonal BSP impossible. I just want to have something to look at so I can understand your idea.

[scifista42]

How about this? Would you get convinced by seeing this map partitioned without splitting segs?

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

EDIT: Bad example, it can be partitioned traditionally without seg splits too (by cutting off corners first). I will soon come up with something actual, though.

EDIT2: I have it - this should be good.

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

EDIT3: But too elaborate for me to do. :(

[Marnetmar]

SEG HEIL!

[Graf Zahl]

Ok, once again:

I am not interested in seeing proof that you can partition a map without linedef splits, I want to see a concrete example of how you propose to construct a BSP. You do not need a map that can't be split traditionally for that.

[MaxED]

How about this one:

[scifista42]

Graf Zahl: Okay, I accept that. Now I would like to go the simplest possible way about this, to save me of too much work with hex editor, but you rejected my simplest triangle map as not proof-worthy enough. You should propose or at least acclaim the particular map layout that you would consider proof-worthy, before I start working on it, please.

Thanks, MaxED. Would MaxED's layout suffice as a proof to you, Graf Zahl? To me it would, but please express yourself.

EDIT: By the way, this very layout is also possible to partition without splitting any segs and without my algorithm, but I will omit the fact and build the tree according to my algorithm anyway, if you approve the layout as proof-worthy.

EDIT2: Ahh, it's going to be so much of an uncomfortable feeling to me, knowing that this very map can work as a single subsector with the middle segs drawn first, but no, I will need to make an elaborate BSP for it instead. It sucks, but if it suffices for you as a proof, I would do it.

[Graf Zahl]

The least the map needs is being non-convex.
MaxED's proposal looks ok for a first attempt.

[scifista42]

It will require 7 segs, 5 subsectors and 14 nodes in total. That is 496 bytes for me to write in a hex editor by hand. And it's not even necessary, because the map can be partitioned using only a single node and single subsector via traditional algorithm... I'm not pleased at all, but fine, I'm going to try it in the next days.

EDIT: Crap, I have just realized that I forgot to count the nodes of complement worlds, so it will be even more nodes than 14 in this case...

EDIT2: I have thought it out, and this really is one of the worst case scenarios, resulting in many additional nodes.

[scifista42]

As I said, worst case scenario, many additional nodes. It's going to require over 30 nodes in total, damnit. I don't want to do this thing as first proof, it's too tedious to make by hand.

I want an example that would split the world to only 3 subworlds, each of which being either a subsector or at least divisible by traditional BSP further on.

I will make up such a layout later, or I'd welcome if somebody provided a (non-convex) map according to description in the paragraph above, because that's what would be easy to make.

[Graf Zahl]

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. (and that's still provided that it'll work at all.)

[andrewj]

I think the main question here is : assuming all linedefs in the level become a single seg (for each side) which are never split, can they be organised via the BSP tree so they are always drawn in the proper order which ensures correct rendering?

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

Now I don't know precisely how to solve that problem, perhaps the original post here does solve it, and I suspect that the solution will use so many nodes to be infeasible for real-world use, but it is an interesting idea none-the-less,