A question regarding BSP nodes

[printz]

Are the partition lines required to be on top of linedefs? Are they further required to have the same defining coordinates (x, y, dx, dy) as the vertices of those linedefs?

[Maes]

I'm not sure if I understand the question correctly, but the BSP partitions and their lines can be totally independent of how you place your actual linedefs: there may be "BSP cuts" even in void areas in the middle of a sector, where there are no editable linedefs, and BSP splits even when you'd think you have a nice, square room. It all depends on the BSP generator, really. Actual linedefs may be used as guides during node building, but extra vertices and linedefs may be added in order to aid splitting, and even generate non-optimal BSP trees or trees with weird rendering priorities. So no, as a general rule, they don't, and don't count on it.

[printz]

Actually, I think that 2-sided (at least 2-sector) linedefs must be covered by node lines, because node lines are needed to separate subsectors.

[Quasar]

No. Partition lines *could* be chosen arbitrarily. But the typical BSP tree building algorithm is to use the existing primitives and choose partitions from amongst them according to some criteria - for a balanced tree, you would choose primitives which roughly divide the other primitives in half at each level. For a minimal number of splits, you find the primitive which causes other primitives to split the least number of times at each level. It is also possible to use a random selection criterion. Research has shown that selecting a partition at random often builds perfectly good trees and almost always avoids worst-case scenarios.

But, you could indeed build a BSP based on arbitrary partition surfaces that are not derived from the primitives they are classifying. This could in fact be a useful approach for some types of BSP-based algorithms, but I'm not personally aware of what they'd be.

[Maes]

I think it works like this: whenever actual linedefs are encountered during a BSP build, they do induce a BSP split, so in that sense, all linedefs are "fully covered".

However, the BSP builder is free to insert extra dummy linedefs and vertexes into your map in order to normalize the shapes of the SSECTORS structures (subsectors).

But as Quasar said, this is more of a programming/mathematical convenience when implementing node builders: partition lines can be made entirely free-floating with respect to the map's linedefs, but then building an efficient BSP tree will be harder, and the result would probably be suboptimal or even glitchy during rendering (e.g. drawing stuff in the wrong order, needless overdraw, imperfect culling etc.).

[andrewj]

Picking the first N nodes by simply subdividing the map into two (at the midpoint along an axis) is a great way to speed up nodebuilding, since most of the time is spent finding the first few partition lines (evaluating every linedef in a large map).

The Quake 3 nodebuilder divides the map into 1024x1024x1024 cubes before processing the geometry normally (picking faces as partition planes). I think speed is not the only reason it does this, but I can't remember what the other reason is (perhaps keeping the faces under a certain size so their lightmaps will fit).

[printz]

andrewj said:

since most of the time is spent finding the first few partition lines (evaluating every linedef in a large map).

Can't that time be reduced by only looking through the central blockmap cell(s)?

...Actually, looking at default levels, such as E1M2, I see defects in the nodes. There are duplicate nodes with the same partition line on the same region, and there are invalid subsectors (their segs on the wrong side of the mother line). It's complicating my attempt to build a correct subsector connection graph in AutoDoom for some levels. I think there'll be no harm to integrate a modern node-builder into the port, it shouldn't increase the loading times significantly... Or take the possibly smarter way and just correct the current node map at load time :P

Are available modern node-builders guaranteed not to produce such defects?

[Quasar]

printz said:

Can't that time be reduced by only looking through the central blockmap cell(s)?

...Actually, looking at default levels, such as E1M2, I see defects in the nodes. There are duplicate nodes with the same partition line on the same region, and there are invalid subsectors (their segs on the wrong side of the mother line). It's complicating my attempt to build a correct subsector connection graph in AutoDoom for some levels. I think there'll be no harm to integrate a modern node-builder into the port, it shouldn't increase the loading times significantly... Or take the possibly smarter way and just correct the current node map at load time :P

Are available modern node-builders guaranteed not to produce such defects?

*GASP* idbsp was buggy??? No way man!!!! :P

BSP, zdbsp, or ZenNode all generate better nodes. None of them are probably perfect though. What program of that complexity has NO glitches?

[printz]

Quasar said:

What program of that complexity has NO glitches?

Well, finding the optimal tree ought to be a complex job, but actually placing the partitions (especially if it's only on top of linedefs) and stopping at the leafs sounds simple enough not to make any error... There is the round-off-to-integer complication (generating the slime trails at least), but what else...

[Graf Zahl]

Don't underestimate the non-triviality of nodebuilding. If it was all that simple we'd have had the perfect nodebuilder for 18 years.

BTW, in ZDBSP most of the complexity is in the code to select the partition lines.

There's also a lot of fudging in place to prevent micro-segs (below the precision threshold )but that hasn't kept it from screwing up on the on occation - see the polyobject freeze that Randy fixed last week.

[printz]

Which is a better node builder for vanilla Doom/Boom/Eternity, BSP or ZenNode? Or another?

[Graf Zahl]

For vanilla?


Without a doubt Zennode.