Search In
• More options...
Find results that contain...
Find results in...

# BSP Theory: Why SEG splits are sometimes unavoidable, with proof and fancy drawing!.

## Recommended Posts

Lately there's been some talk on irc and discord about node builders and SEG and SEG splits etc. The main reason for avoiding splitting SEGs is to lower the SEG count and have less than 256 SEGs in view to avoid HOM. A map built without splits could have more detail than one with splits.

Ideas have been tossed around about by transforming a map into all convex subsectors and build the BSP tree from ground up. This simple example proves that such an endavour and all other no-split ideas are impossible to do on all maps. It might be possible on some maps, but most maps will realistically have geometry that makes it impossible to have no splits. Still, fewer splits should be within reach, I have started working on building a special low-split algorithm.

Here is a nice proof that it is impossible to make this simple two-sector map split-free. This is basically a disproof of the hypothesis that all maps can be divided into two halves in such a way that no SEGs are split.

We construct a map with a concave polygon with 4 edges sharing two sides with a threesided polygon.

1. Any line that is on the 'edge' will sort all segs on one side of the line, and is not viable as a dividing line, since it has not divided the SEGs into a left and right side.

2. Lines must go from vertex to vertex, since a line going through any other location, will split a line.
3. The only possible split lines from the 3 outer vertices that go through another vertex that doesn't form an edge, are lines that go through the central vertex.
4. Any line that goes from an outer vertex through the inner vertex, will split one of the sides.

Thus it is proven that it is possible to construct maps where split SEGs are unavoidable and any work done towards split-free bsp trees is futile. At best one can have a really low amount, and that is a worthwhile pursuit.

Nodebuilding is magic wizardry to me, so these informative posts are fascinating to see. I'm excited that you're looking into ways to reduce seg splitting! That will definitely come in handy.

1 minute ago, esselfortium said:

Nodebuilding is magic wizardry to me, so these informative posts are fascinating to see. I'm excited that you're looking into ways to reduce seg splitting! That will definitely come in handy.

Thanks :) I figured a short, small and informative post would make it easier to understand why this happens. If you know why it happens, it's usually easier to avoid or reduce the problem.

If you have a section with HOM in it, if you got any long lines in that area that goes "across" the screen, tell the node builder to not split that line, it might help with reducing the splits in that specific hot-spot. I'll add a linedef type for that in ZokumBSP so that people can easily do it from a map editor as the current way of doing it is a bit cumbersome.

1 hour ago, zokum said:

Thus it is proven that it is possible to construct maps where split SEGs are unavoidable and any work done towards split-free bsp trees is futile.

I am convinced that this is not true if we exploit Doom's existing node structure and traversal algorithm in a way that they weren't intended to be used, but it is still technically possible to use them that way.

The following node structure for your map should suffice to render it correctly:

Explanation: Numbers = subsectors. Colored lines = partition lines. Mark on a line = its right side. Colored node (the lower 2 nodes) = check on which side of the given line the camera is, traverse the branch on that side first, the other branch second. Black node = a node with such a partition line that the check will always determine to traverse the right branch first. Colored node with an X in it (the upper 3 nodes) = a node with bounding boxes of its children reduced to zero, allowing only the branch on the side closer to the player to be entered, preventing the other branch to be entered after the former one is traversed, thanks to how Doom's traversal algorithm works.

Yes, there are multiple references to the same subsectors, "always to the right" nodes, and "one way only" nodes - this doesn't fit the theoretical definition of a BSP tree, but it's implementable in Doom's node structure and leads to the result of rendering the map correctly. Just try to iterate the traversal for any position in the map that the player might be in to verify it.

You still pursue this insanity? Trust me, it doesn't work if things get more complex.

If things get more complex, there's another trick to exploit: Multiple nodes can reference the same node as their child node. So instead of a tree, there will be a directed acyclic graph, functioning the same but being smaller in size, preventing the otherwise-maybe-unavoidable exponential size bloat.

Yeah, this is no longer a BSP tree, it's like you say an acyclical graph. My point still stands for a tree, but a different data structure that is more like a location finder graph might work.

It reminded me of how gps works by narrowing down your location from various data points and then figuring out your position and what is around you :)

21 minutes ago, zokum said:

Yeah, this is no longer a BSP tree, it's like you say an acyclical graph. My point still stands for a tree, but a different data structure that is more like a location finder graph might work.

However, note that this "different data structure" is representable in Doom's nodes as they exist, without any need to modify the engine. Regardless of semantics, this concept should be applicable to actually construct seg-split-free nodes for any Doom map, and these nodes will be functional in existing engines including vanilla. Then it might not be futile at all to try making a node builder that would generate that kind of nodes.

Edited by scifista42

I wonder if your tree can be considered the bastard child of a ternary-like tree. I think we could say that we are grouping SEGs into left, right or both sides. Any SEG that is on both lines of the partition line is instead put into both child nodes, to be handled later. Thus we're avoiding all splits and instead have 'duplicate' entries several places in the child nodes, and the same partition lines are used in several places in the tree, but with different children.

I could wrong here, but would this be an ok explanation of the type of sorting we see here. I'd like a good formal and rigid description that makes writing an algorithm possible.

12 hours ago, zokum said:

I wonder if your tree can be considered the bastard child of a ternary-like tree. I think we could say that we are grouping SEGs into left, right or both sides.

Nope, it's more complicated than that. Here is how I'd describe the (unoptimized) construction algorithm:

function partitionMap(map M):

1. G := map geometry of M

2. N := new "metanode", which will contain either a node or a subsector, assigned later

3. partitionPart(G,N) - after this call, N will be the root of a fully realized node tree that covers the whole map

function partitionPart(geometry G,node N):

1. if G is a single convex shape: N := new subsector(G), return

2. if G can be split into 2 subgeometries G1 and G2 by a partition line P that doesn't intersect any segs in G: N1 := new metanode, N2 := new metanode, N := new node(P,N1,N2), partitionPart(G1,N1), partitionPart(G2,N2), return

3. split G into K subgeometries G[1], G[2], ..., G[K], where K is an as small as possible integer, each subgeometry is convex (void areas don't matter), and the boundaries between the subgeometries don't intersect any segs in G (this is always possible, at worst by splitting the whole map into individual subsectors, but for efficiency reasons, a minimal K should be sought)

4. for J := 1 to K: A[J] := new metanode, B[J] := new metanode, X[J] := new node(Y,A[J],B[J]), where Y is a partition line always traversing the first node first, second node second

5. construct a "decision tree" originating from node N and ultimately leading into nodes X[J], J := 1 to K, assigning any point inside G to a subgeometry G[J] in which it is (and its corresponding node X[J]), each inner node of the "decision tree" should have bounding boxes of its children reduced to zero in order to prevent traversal to the side further from the camera after the side closer to the camera is traversed

6. for J := 1 to K: partitionPart(G[J],A[J]), partitionPart(G\G[J],B[J]) - where "G\G[J]" is all of G excluding G[J]

Optimization should be possible by (bottom-up) "merging" identical subtrees by directing multiple nodes into the same node as their child node, or replacing the command "partitionPart(G\G[J],B[J])" with a specialized function that doesn't forget the already found subgeometries of G and therefore can reuse the already constructed nodes X to direct the "decision trees" of B nodes into.

Edited by scifista42

It's hella nice to see some seg optimization going on. Dealing with seg overflows has always been the most maddening part of vanilla mapping for me, since drawing a new line can add anywhere from 1 to six trillion segs depending on the size, angle, surrounding geometry, phase of the moon, and the average temperature in Geneva, Switzerland. Anything which simplifies this landscape is an A+ in my book.

I just added a summary of the node/seg stuff done for all maps when using ZenNode. This makes it much easier to run new code over a large data set and see if it is an optimization or not. I am working on some very minor splits-algorithm optimizations.