Node building: Avoid splitting segs?

As I see it, Doom's BSP tree system has 2 main disadvantages:

1. Geometry must remain static - but that's OK, I've already got used to it.
2. Node builder may decide to split any linedef segment it wants to - now this is something that irks me since I've learned about it.

Some maps have very wild and insanely intertwined geometry, thousands of non-orthogonal sectors, 1-pixel angled walls, extremely thin sectors, concave sectors and so on. Node builder splits all sectors into subsectors according to partition lines between nodes, and in this elaborate map, there will be LOTS of nodes and dense thin subsectors. Since each subsector references a range of UNIQUE linedef segments, node builder apparently needs to split every linedef segment on the boundary of subsectors, which means that A LOT of segments will be split. Splitting a segment requires inserting a new vertex. But what if this vertex doesn't match 1-pixel grid? It will be placed slightly off. Which CAN actually cause problems with top-precisely engineered non-orthogonal geometry. The bigger and more elaborate the map is, the bigger is probability of problems occuring (because there will be more subsectors and therefore more segment splits). The mapper can't ABSOLUTELY rely on the assumption that his advanced geometry will appear and work as intended. I consider this system unclean, and it irks me out of principle.

Why do segs need to be split? Why can't different subsectors reference the same segs that they partly touch? What issues would it bring up? I thought the renderer (if altered a little, along with the general structure of subsectors themselves) should be able to cope with it correctly.

I wish there was some kind of alternative node builder that was 100% guaranteed to never split segs. Or at the very least, 100% guaranteed to never insert vertexes that don't lie exactly on a linedef according to 1-pixel grid. Is it really a no-go?

I wouldn't worry about it, all virtual environments rely on some degree of approximation and hackery. So long as your geometry is sufficiently big and chunky, a player is unlikely to notice single unit deviations.

That said, BSPs are known to become increasing inefficent as map complexity rises, which is why detail brushes, imported meshes and portals became a thing.

scifista42 said:

node builder that was 100% guaranteed to never split segs

This is probably impossible. Remember that the node builder has to split the entire "world" into two halves, and then recursively treats each half as its own "world" and splits that in half, until each "world" is a convex area, which is then its own subsector.

So how could you split this in half without splitting a line somewhere?



Right, you can't. The only hope is to try minimize the line splits as much as you can by choosing favorable partition lines, and choose line splits so that your additional vertices are as close to being on the grid as possible.

This is where most of the work in Doom node builders happens - trying to find splits that upset the grid as little as possible.

For example, ZenNode has three algorithms you can choose from:

//----------------------------------------------------------------------------
//  ALGORITHM 1: 'ZenNode Classic'
//    This is the original algorithm used by ZenNode.  It simply attempts
//    to minimize the number of SEGs that are split.  This actually yields
//    very small BSP trees, but usually results in trees that are not well
//    balanced and run deep.
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
//  ALGORITHM 2: 'ZenNode Quality'
//    This is the 2nd algorithm used by ZenNode.  It attempts to keep the
//    resulting BSP tree balanced based on the number of sectors on each side of
//    the partition line in addition to the number of SEGs.  This seems more
//    reasonable since a given SECTOR is usually made up of one or more SSECTORS.
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
//  ALGORITHM 3: 'ZenNode Lite'
//    This is a modified version of the original algorithm used by ZenNode.
//    It uses the same logic for picking the partition, but only looks at the
//    first 30 segs for a valid partition.  If none is found, the search is
//    continued until one is found or all segs have been searched.
//----------------------------------------------------------------------------

Linguica said:

So how could you split this in half without splitting a line somewhere?

Right, you can't.

OK, I understand why partition lines must intersect through some linedefs, but I don't get why segs need to be split into 2 new ones. As I already asked: Why couldn't 2 subsectors reference the same seg that each of them partly touches? Couldn't the renderer be altered to take it into account easily?

scifista42 said:

Why couldn't 2 subsectors reference the same seg?

The basic operation of the Doom renderer is that it determines the order to draw subsectors in, and then draws all segs associated with each subsector in turn, and because of the way they are set up, it is GUARANTEED that everything will be drawn in proper order. If you had segs shared between subsectors or something, then that guarantee would be broken.

Like... imagine if you have two subsectors:



Where the red line is a linedef you would prefer to not split. So you make a seg associated with the whole line, and have it be part of both subsectors.

The problem is that the subsector, as defined by the segs associated with it, is no longer "convex" - it can have two segs overlapping one another from the player's viewpoint, and not only would this result in overdraw, but there would be no guarantee on the order they are drawn in. If you were viewing from the bottom left, it could draw the blue seg first and then the red seg, and the red seg would get drawn on top of the blue seg and look wrong.

I am of course suggestion that the feature of adding any auto-generated segs should also go out.

However, I was able to imagine an actual example of overlapping drawsegs:

 ================Undivided northern segment==============================
|             .        .          .                                      |
|             .        .          .                                      |
|             .________.          .                                      |
|             |        |          .                                      |
|             |        |          .                                      |
|             | Pillar |          .                                      |
|             |        |          .                                      |
|             |________|          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          . dotted lines are                     |
|             .        .          . implicit partition lines             |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .                                      |
|             .        .          .  X                                   |
|             .        .          .  |___Player who looks north          |
|________________________________________________________________________|

The pillar's segs would be drawn after the northern seg, even though they were supposed to be drawn over the left part of said seg.

This only means that this particular structure of subsectors was unsuitable. But the map could be divided into nodes/subsectors differently since the beginning, then it could work, maybe. Can it be proven that certain map layouts make it IMPOSSIBLE to create a node/subsector structure that would work if segs were never split (and never auto-generated) and instead they could be shared between subsectors?

The only conceivable way to minimize splits does not lie in changing the node builder, but your mapping habits.

Theoretically, a split does not need to happen in cases of completely convex sectors with unbroken interiors, so if every structure was convex without any other breaks in structure inside of them, no segs will be split.

You won't make anything interesting looking, though.

EDIT: Again, THEORETICALLY. The node builder may pick an arbitrary point for the root node (and first split).

MTrop said:

Theoretically, a split does not need to happen in cases of completely convex sectors with unbroken interiors, so if every structure was convex without any other breaks in structure inside of them, no segs will be split.

Unless I've misunderstood you (not sure what you mean by "breaks in structure"), I think it's false. How do you divide this map by partition lines without intersecting/splitting segs?

                                ________                           
                               |        |                          
                       ________|        |                          
                      |        |        |                          
                      |        |________|____                      
                      |        |    |        |                     
                      |________|____|        |                     
                           |        |        |                     
                           |        |________|                     
                           |        |                              
                           |________|                              

scifista42 said:

Unless I've misunderstood you (not sure what you mean by "breaks in structure"), I think it's false. How do you divide this map by partition lines without intersecting/splitting segs?

You can't. It's already too complex. You have a break in your structure directly in the center.

Something like this would be possible to not split:

 _____ _____ _____ _____ 
|     |     |     |     |
|_____|_____|_____|_____|

Boring map, one subsector leaf per sector.

Alright, I think we can agree that this approach is unusable for practical quality mapmaking.

Solution == don't use BSP; change to a portal-based engine. Too bad they don't perform very well for Doom maps :P

What if the segs were split, but without inserting a vertex? The superfluous vertexes would be substituted by references to the respective partition lines themselves. It would allow precise intersection recalculation during runtime with respect to already transformed coordinates in player's space. There would be 4 types of segs: Vertex to vertex; vertex to partition line; partition line to vertex; and partition line to partition line (the last 3 types need to remember reference to their original linedef, too). The renderer would need to distinguish them somehow, but it shouldn't be hard to do. Is there anything theoretically preventing this principle from working? Would it be considerably slower?

I believe ZDBSP's extended nodes format (supported in ZDoom, Eternity, and PrBoom-Plus) allows for sub-unit vertex precision in nodebuilding already, which effectively solves the same problem while changing less (if anything) about what the renderer actually needs to do.

scifista42 said:

What if the segs were split, but without inserting a vertex? The superfluous vertexes would be substituted by references to the respective partition lines themselves.

Requires changes to the game engine.

So you may as well use the extended node formats (GL nodes or XNOD) where the vertex precision is good, rather than yet-another-new-node-format.

Yes, but even sub-unit precision is theoretically not perfect, and may not be sufficient on extremely elaborate maps like I've described in the OP. As for requiring changes to the engine, of course that's what I assume would be needed to do.

My intention is to learn about efficient, flawless and 100% reliable algorithms which I'd use elsewhere as a programmer. The efficiency of Doom's software renderer impresses me and I'm fantasizing about creating <something> on similar principles. But for now, I only wanted to discuss ideas with input from experienced people like Doom port programmers. So again, does the runtime-intersecting seg algorithm (the one I've described in my post above) have any major flaw that would disqualify it from usability?

scifista42 said:

Yes, but even sub-unit precision is theoretically not perfect, and may not be sufficient on extremely elaborate maps

If a full fixed-point representation of each vertex like the extended nodes format does is not sufficient for a map, I'm not certain what would be.

Fixed point is really precise, but still theoretically imperfect. If you're splitting a non-orthogonal segment by a non-orthogonal partition line, the vertex will be put slightly off its theoretical perfect position, maximally by 1 smallest fixed point unit. If youre splitting a non-orthogonal segment by multiple non-orthogonal partition lines, the imprecision might theoretically increase with each one. Therefore, maps with extremely wild geometry, relying on extremely thin triangular sectors etc, might theoretically break, specially if you split them near their end points. Even though it rarely happens in practice, I'm looking for an algorithm that would eliminate this danger once for all.

All digital representations are imperfect, even with n number of bits you'll be never be able to store an irrational value.

It's always a question of how small a margin of error do I need to create the illusion.

Defining an arbitrary point as intersection of 2 lines (both guaranteed to have end points snapped to a grid, even if fixed-point grid) should be perfect if you simply reference the lines instead of trying to precalculate the point's exact coordinates in world space.

Even double precision floating points are not perfect. Except for a certain range of integers they are mere approximations and a programmer needs to be aware of that and write code accordingly.

Seems immaterial to me whether you stored the intersection point somehow or compute it "on the fly" -- you cannot escape having an inexact value either way.

EDIT: for example, how do you test (exactly) if a point is on one side of a line (a vital test while building nodes) if that point is defined (stored) as the intersection of two lines? I mean it may well be possible to do that geometrically, though you would still need extensive modifications to the node builder and renderer (and other BSP using subsystems in DOOM) -- I've had to debug node building issues many many times and it wasn't any fun.

The inexact value computed on the fly will be computed already in player's space. It world space, all vertices have coordinates exactly as the mapper put them to his map, which I call perfect. Therefore all pre-placed vertices and lines can be stored perfectly, as opposed to any followingly computed intersecting points. I only want to NOT displace any world coordinates in the slightest after the mapper placed his last (perfect) piece of geometry into the map. Therefore, intersections computed by the node builder and stored as approximate coordinates are a no-go.

scifista42 said:

Defining an arbitrary point as intersection of 2 lines (both guaranteed to have end points snapped to a grid, even if fixed-point grid) should be perfect if you simply reference the lines instead of trying to precalculate the point's exact coordinates in world space.

Tell that to any and all game engine developers who have to deal with z-fighting.

scifista42 said:

...My intention is to learn about efficient, flawless and 100% reliable algorithms which I'd use elsewhere as a programmer...

From one programmer to another, HAHAHAHAHAHAHAHAHAHAHAHAHAAAA!


There are always strengths and weaknesses to every type of algorithm for every purpose in every program environment, implementation, and specification. The real discipline is figuring out what those are per algorithm.

But you should completely abandon your quest for error-less calculation. You will always be hindered by numeric representation depending on its system interpretation, methods of calculation, and the size allocated for values. You working with computers, and will always be bound to some kind of limit, be it space or time. Increased precision means less space and more calculation time, different interpretation and size means potential loss of precision.

I'm afraid you are more or less bound to reality, Mr. Fista, whether you like it or not, and if you refuse to accept the bounds in which you need to work, you will not succeed in whatever you seek to do. You are better off arguing in reality, not what you wish reality was.

Thanks, MTrop, I understood, and I believe that finding balance is what I'm actually trying to do. The rendering algorithm needs imprecision to increase speed, I get it, and I'm OK with that. But, the map "pre-processing" (node building) algorithm doesn't need to be fast, and therefore I'm not comfortable with the fact that it's imprecise, and generates misplaced global vertices that can (albeit rarely) cause problems, sometimes before the map is even launched.

I've re-read the Seg wiki page and I've noticed that each seg already references its linedef and also offset from the beginning of the linedef from the left side. If it's that simple, why wouldn't it also store its offset from the end of the linedef from the right side? Each seg would be defined as a linedef + 2 offsets, instead of referencing a fixed start + end vertices. Node builder wouldn't have to add any (potentially imprecise) vertices to split the segments. When rendering a seg, the renderer would actually try to draw the whole linedef, but cut off columns beyond the seg's offsets.

No misplaced global vertices - that means no cascade-effect imprecision when splitting segs, specially if it happened close to their end points. I think it's a progress. Only the seg offset values remain imprecise. I would extend them to fixed point values, because they will be no longer needed to determine texture offset if the renderer tried to draw the whole linedef anyway. They will still be imprecise, I know. But it will only manifest during rendering, it will not affect real geometry. And then there's another advantage: The seg's angle will always copy the linedef's angle. Imprecise vertices would possibly change the angle slightly, but offsets will never. It relies on updating the wall rendering algorithm to straightly take a linedef and draw a certain part of it, rather than drawing a separate entity (seg) with its own geometrical end points.

So I'm asking: Would this algorithm be comparably fast and reliable to Doom's actual one? Or is there any catch?

It can be done, and it can be done efficiently. But, eventually, your going to alias on a pixel boundary. Pixels are placed on integer boundaries, because they're pixels, transferred from an integer video memory thru the integer video card, to a pixel-based monitor (unless you use a CRT, with scanlines, but arbitrary beam columns, though the hardware will still place them on integer locations with raster rendering).

The point I'm trying to make is that, if you are precise enough to choose a specific pixel (or one of it's aliases), you can't really do better than that. Having said that, yes, the original nodes are improved with an extended floating-point representation. But, what's the concern about extra vertices? (I might be missing something.) Are you concerned with reducing complexity, or raw lump size, or number of struct array elements?

I suggest mocking your idea up, and evaluating it empirically. Have a way to toggle between one method and the other, if feasible. Test it along these lines:

1. Choose maps of high complexity, especially with lots of thin detail.
2. Try maps with known slime trails.
3. ...wobbly walls and floors
4. Test for raw render speed, always using specific view positions and angles.
5. Test with areas that have "sticky" walls, where DoomGuy appears to get stuck, running alongside a smooth wall.
6. As you test, check wall, floor, and ceiling joints for "sparkles", "wiggles", etc.

I have a feeling that a lot of these subtle, but strange map problems are caused by the node build process, so, you may be onto something. But the real question to ask is, can the problems with those maps be fixed by using a good standard node build, or must we change to your new method (or another more precise way), to gain enough precision to make a difference. And, how much difference can been noticed?