Legacy:Node Count

Common confusions about what the term "Node Count" means:

• it's not the number of PathNodes
• it's not the number of brush vertices
• it's not the number of BSP regions
• it's in fact the number of BSP leaf nodes

In other words, a Node is one of the coloured polygons in UnrealEd's Zone / Portal view.

The term is used in two ways:

• the total number of nodes in the map (this is given in the Build window's Stats tab.
• the number of currently visible nodes in game

Example: single cube

A map consisting of a single subtracted cube will have:

• a total poly count of 6 (6 surfaces)
• a total node count of 6 (no surfaces are split)
• and therefore a node:poly ratio of 1.00:1

Reducing Node Count

High node counts require more processing power (to render them all at once) and so can cause your map to play slowly on your machine, and could make it next to unplayable on a lower powered PC, especially if you have any special effects in there like snow or fog.

Semisolid brushes help drastically reduce the node count of a level – but overuse is also a bad idea. The node count in any one area can also be reduced by proper Zoning of your map.

UnrealEd apparently cannot handle more than 65536 BSP nodes. Even if it takes 30 minutes alone to apply all structural brushes to the world, it will crash while handling lights.

---

refactoring in progress...

But the plot thickens. At least one person in the world of Unreal editing, a certain Tarquin, was for a long time under the mistaken impression that a BSP node was a region of space. It's not. That's a region, probably.

Experiments support the hypothesis (see below) that a BSP node is a poly belonging to a region: in other words, one of the ares of colour that is seen in UnrealEd's Zone / Portal view.

---

Current theory is that it's none of the above. See experiment below.

High node counts require more processing power (to render them all at once) and so can cause your map to play slowly on your machine, and could make it next to unplayable on a lower powered PC, especially if you have any special effects in there like snow or fog.

Semisolid brushes help drastically reduce the node count of a level – but overuse is also a bad idea. The node count in any one area can also be reduced by proper Zoning of your map.

Egad, I was about to create a page on Node Count too... :-) I am, however, fairly sure that node count is the number of BSP nodes, not the number of vertices. Tarquin

It would appear everyone was wrong: evidence shows that Node Count is the number of currently visible BSP polys. The Poly/Node ratio is then a measure of how much surfaces are split up by BSP cuts across the map.

(evidence is this: a single cube should be a single BSP region. NodeCount when looking at this is exactly the number of visible polys.)

Question: are the final leaves of the BSP tree regions which own polys, or polys themselves?

If the node count is the number of visible polys in your cube then it would seem that the leaves of the BSP tree reate to the polys themselves rather than the region that relates to the the polys in a single BSP cut.

Yup – Tarquin

Quick Experiment

Build two subtractive boxes:

• 128 x 128 x 256
• 256 x 512 x 256

Put them side by side, so the small box is halfway up the side of the large box.

Look at the Build window's Stats tab, & note the following:

• We have 11 surfaces (entities that are selected in 3D view), since the small box loses one surface entirely
• One surface is a rectangle with a square hole in it. In Zone view this is split into 4 BSP polys.
• Total Nodes is 14. This is not the number of vertices (16) in the map.

Wandering around UEd with "stat FPS" enabled (type into the UnrealEd console) you can see the following:

• Poly count is 11, hence this is simply the number of surfaces. This already surprises me, I'd always figured poly count was the number of BSP polys, not surfaces, and node count was the BSP leafs... arg!
• Node count appears to be the number of BSP polys visible. Try looking at the small box from the big box. The high node count is due to the hollow surface being split.

Question 

Is the node count the total number of BSP nodes used to render the scene? Or is it the total number of leaf nodes used to render the scene? - it sounds like it's the total number of BSP nodes used as you would only expect faces to exist at the tree leafs.

Another experiment

Create an 8 pointed start in the 2D shape editor and extrude it. Place two of them in a reasonably large room such that the flat face lies in the vertical plane (so you can look at it straight on). Now subtract (or clip) the front off of one of the stars you created to create a single polygon on the front face. Then merge all of the faces on the other star.

When you look at the level within the game you will see that the the star with the clipped or subtracted brush has both a reduced node count and a reduced poly count. When you look at the star with the mreged faces you will see that only the poly count has decreased.

This would seem to prove the BSP poly theory as the clip/subtract approach actually alters the wireframe of the star brush rather than simply "pretending" to alter the wireframe. The real question then is - why didn't the BSP merge any of the co-planar faces of the star brush? because it only merges to convex pieces

Tarquin: I haven't tried this in UnrealEd yet, but as far as I know:

• Clipping / Intersecting / BSP code splits concave polys by travelling round and making a cut for each face. For the star, I imagine this could make some cuts that fall midway across a side of the star face. Depends on how the star is made.
• Poly-merging code already has convex pieces to work with. It therefore only has to stick them together in an optimal way to make the smallest number of convex pieces.

A star shape isn't much suited to merging – again, much depends on the shape of the star, and possibly the order in which it was drawn in 2D (I think the way the shape is made out of triangles initially depends on side split order). Clipping/Intersecting may manage more merging in this case.

I tried clipping the star shape I built. Rather than having the wireframe change shape, the wireframe simply got thinner when I performed the clip. Ofcourse, this might have been a problem with the way I clipped it - I tend not to use the clipping tool much as on my old system it would tend to cause the editor to crash. Seems fine on the new one though so I might use it more.

A look at the motivation for Node Count and Node:Poly ratios (SuicideMissions{CLR}'s Theory)

The idea is to minimize the number of nodes traversed in the BSP tree. Due to the Binary/Logarithmic nature of BSP trees, the more balanced the tree is, the fewer node traversals will be required to reach the leaf nodes (BSP polys actually rendered). The leaf nodes represent (more or less) the actual BSP polys rendered at runtime. In this pic below, the visible BSP polys to a player are circled in red. In addition, the nodes which must be traversed are red. Notice that as trees become more unwieldy and less balanced, the traversed nodes goes up in proportion to leaf nodes (actual polys rendered). Count them! Imagine how much worse a large tree would be with many more of these unsightly unbalances!

And that number 2 (as in 2:1) sounds suspiciously related to the BINARY/Logarithmic nature of BSP trees. A well balanced tree will have approximately a 2:1 ratio of traversal vs. leaves. Try it! Count nodes and leaves in those trees below! A 2:1 ratio gives you the most leaves for the fewest traversals possible for any non-trival tree. It happens when the tree is balanced.

How do we do this? By making sure that in any given space of our level, there are not a bunch of BSP polys bunched up in one area. The more evenly spread out the BSP polys (shown in BSP cut view of the perspective window), the more balanced the tree, and the closer to 2:1 node:poly ratio, and the more effecient the map.

When you need more detail in a paritcular spot of your map, like a torch on the wall, then you use Semisolid brushes since they are not BSP based and will therefore not cause BSP cuts and clumps of leaves on the tree. (They do not even effect the tree structure).

Damn: That poly/node ratio seems to have little impact on map's performance. In my maps changing the bsp cuts slider to get a ratio of 2:1 / 1,99:1 / 2,01:1 would cause my maps to run 1 - 7 fps slower. On the other way around, aggressive bsp cuts setting would cause a strange boost of (laughts) 5fps or so. A map can become unaplayable if it's huge, even with low poly counts. I've found that by playing in various servers, maps that need a lot of memory and are huge cause the server to be on full load and prone to crash when there is too much action going on. Not only that but I've seen a map run twice as fast after the server admin complained about cpu overuse, forcing the map author to split the map in two.

I did a quick search in google and found that 65536 is the same node limit in quake / hl engine, sounds like BSP trees are limited to 16 bits something somewhere.

Ops... ISn't it 65535? If i'm not mistaken computers start counting from 0.

You are correct in that they start from 0, but you are misunderstanding: The index of the first node would be 0, and the index of the last node would be 65535, but the actual number of nodes doesn't change when 0-indexing, it's still 65536.

ProjectX: Ayone know the recommended poly/node count for maps to be playable on most machines?

Ironblayde: Check the Polycount page for some good figures to shoot for. As to the node:poly ratio, I've heard that 2:1 is a good figure to keep in mind. It won't be the end of the world if you go over this a bit, though. Many of the retail UT maps are closer to 2.5 or 2.6. Not sure about UT2003.

Aphex I believe the node count isn't just the leaf nodes, but all the nodes in the tree. At each node is a 3-d plane eqn that subdivides 3d space, its two children representing the space either side of that plane.

Just to make things a bit more complicated, your node count may change just by rebuilding the map with no changes to anything, suggesting it isn't a simple mapping to polygons, but an adaptive process with feedback (i.e. it uses the current bsp as input to the build process!) that probably arbitrarily chooses the first spatial subdivision.

I remember some epic person saying some time ago that it's best to have all your large brushes at the beginning of the CSG list, with detail brushes nearer the end for optimal BSP building...

T-1 I have a question: Wouldn't fog speed up rendering rather than slow it down? IIRC stuff behind fog is occluded.

GTD-Carthage: Though this is not really part of the debate, I thought maybe I could add the fact that converting high-poly brushes into movers will vastly (and cleverly) reduce the node count?

WhirlWindWabbit: As far as I know, GTD-Carthage is correct. But, as you are all aware, Unreal engine 1 has some difficulties rendering a lot of movers in a small area or just rendering complex movers. Moreover, if you use too much movers, even simple ones, your map is prone to "losing" the movers when you play the game. They are simply not rendered. So, in my opinion, movers act sort of like static meshes do in the new Unreal engines as they do not effect the BSP tree, but due to the buggy nature of movers - including incorrect display of lighting on its surface - using movers to replace geometry should be used sparingly.

• Legacy:Node Count/MergingDebate.