BSP building
This article is a compilation of informations gathered in an interesting thread by GreatEmerald on the OldUnreal forums about various BSP errors and the process of building/rebuilding geometry in different ways.
Generic Considerations
First, if you don't use build all, but use the three other buttons, you get this on semi-solid brushes:
This is seen in Zone/Portal view while inside a solid brush (in the void). The faces that are not the same colour as the rest of the zone are invisible.
If you check UnrealWiki, you will see that these surfaces are by mistake assigned to a zone other than the one they actually are in, and that zone they are assigned to is not visible to the player. That means that the face in question is never seen by the player, because the engine thinks that the face is irrelevant.
Interestingly, this is solved by doing a BSP rebuild - the part of Rebuild All that you omit when you use the buttons one by one. It appears that the BSP rebuild part is in fact very important for the whole BSP tree - it essentially rebuilds and optimises it, thus things like zoneless polygons get assigned to the right zones. It also solves a lot of performance problems. Another way of solving this problem, if it persists even after a complete rebuild (which should be uncommon), is to select the surface and check the "Force View Zone" flag. The exact purpose of this flag is to set polygons visible when they are erroneously set to nonexistant zones (and it goes hand in hand with the No Bound Reject flag, for when annoying polys won't stop flickering in and out of view). Notice, however, that Force View Zone sometimes has problems and makes affected surfaces unlit.
Another good thing (this is done by a geometry rebuild) is merging coplanar polygons. That is in fact very important for lighting. If you have a complex brush, you get lighting problems since the engine gives up calculating the right lighting for each and every polygon there. In the next image you can see this problem in the upper brush, to the right - the triangle there doesn't get lit correctly since it's not merged with the rest of the face's polygons. The lighting issues on the pillars are similar, but this is harder to correct on surfaces which are not coplanar.
It is also very, very important to merge polygons after everything you do in the 2D shape editor, or getting these light errors + worse performance is guaranteed. Also note that polygons will only be merged if the textures are aligned in a way that they could be merged - that means you need to use Align to Floor/X/Y in order to make them aligned, and only then do a Brush-> Polygons -> Merge. Also, you should merge them before aligning your texture correctly since that just makes it a lot easier - you don't have to select all faces all over again if you accidentally misclick and deselect everything. An easy way to select all those faces is to do a Surface -> Select Surfaces -> Adjacent Coplanars, but beware that selected polygons will include any coplanar polygon, even those not belonging to the same brush. (It would be a really nice feature, though...)
Another thing you may noticed is that the two types of BSP errors seem to be dependent on the brush type. If the brush is semi-solid, you will almost never get HOMs - you will mostly get invisible polygons. It's the opposite for solids - you will almost never get invisible polys, but you will mostly get HOMs. That means that the errors you get with semi-solids are when a polygon is assigned to a wrong zone; the errors with solids are when a polygon is assigned nowhere at all, thus you see the void. This is because semi-solids do not occlude geometry; a non-showing semi-solid polygon will let any polygon behind it visible. A solid brush occludes geometry and splis polygons along its edges to occlude the part of a brush behind it, so a non-showing solid polygon lets the void behind it.
However, it is possible to obtain invisible polygons with solids and HOMs with semi-solids, but these tend to be the results not only of bad brushes, but of a generally bad map (for example, when portals are involved along with regular brushes). However the lighting problems occur for both types of brushes, meaning that there is something wrong in the lightmap.
Apparently, it also helps if you do a Transform Permanently after rotation, vertex editing or brush scaling. There will be less maths to perform by the engine, thus less BSP errors and better performance.
One more note about BSP rebuilding - when you click "Rebuild geometry", the current BSP tree seems to be thrown out the window, that is, you will see polygons assigned to wrong zones again. You must rebuild the BSP tree to get those stray polygons fixed. So it would be a nice feature to have a "BSP [tree] rebuild" button near the others, although you can get a temporary one by simply going to rebuild all options, unchecking everything but BSP and hitting Build/Build all.
BSP parameters
Balance Tree and Minimise Cuts
About the Minimise Cuts/Balance Tree slider - it seems that it affects the way the rebuilder dissects the geometry. Balance tree makes the maximum polygon depth as low as possible, that is, every cut will be as similar in size to other cuts on the same surface as it can be. Minimise cuts, on the other hand, makes the tree disproportional with as many levels as possible.
If you can see one cut, all of its children will also be rendered, but not its parents or its brothers. So simply put, Balance Tree creates more brothers to every smallest cut; Minimise Cuts creates more parents. Since both are not rendered, it shouldn't matter much - the BSP errors you see will simply be put to different shapes, that is, with Balance Tree they will be of medium size, with Minimise Cuts they will be of small and huge size.
Though Minimise Cuts tends to create less nodes all in all, and that means less calculations for the engine, yet bigger nodes. That would mean that you will generally see bigger holes than with Balance Tree; however, Balance Tree can have so many nodes that the engine will give up calculating and will create new holes (in fact, using 100% Balance Tree will create more nodes than without the tree at all!). Thus the default setting is 15/100, which means that your standard BSP hole is quite big, but the performance is good and thus new holes don't usually form.
Portals Cut All and IgnorePortals
About Ignore Portals/Portals Cut All - The Ignore option should make the BSP tree lighter, that means less nodes, faster framerate and less BSP holes; however, if there is a BSP hole on a portal, no matter how small, you're in a world of trouble. The Cut All option should make portals have a bigger priority when cutting geometry, that means BSP holes have a lot smaller chance on forming on them, but the tree gets heavier, you get less framerate, more BSP holes on non-portals and more nodes. The default is 70 since leaking zones is one of the worst things that can happen in a map, and which wreaks havoc on the whole portal generation system (and thus optimisation as a whole).
However, if you select all zone portals and use Order -> To Last, they will get a higher priority naturally, meaning that you will be able to lower the slider there and thus getting better performance and less cuts out of it. You could also experiment with this option - set it to as low as possible while zones aren't leaking yet, and you will get it optimal. In fact, as you can see in the pictures, the node count decreases dramatically if you set the slider to Ignore Portals.
BSP optimisation and BSP tree building
Now a few notes on BSP optimisation. The more BSP optimisation is applied, the less nodes there are, thus the better framerate and less BSP holes. However, it takes longer to build; yet it seems that it takes a long time one way or another, so you should simply stick with optimal (hence why it's the default).
Geometry is the same thing, just without the settings. Leave it on for better results (I get a +0.07:1 node count boost with it on on default settings). Note that BSP and geometry optimisations are different settings (hence unticking Geometry optimisation will allow you to change BSP optimisation settings).
There is also a very interesting thing to notice - rebuilding BSP several times leads to better node count. That's very interesting, because on first BSP rebuild you may get, say, a 1.97:1 ratio, on the second - 1.90:1, on the third - 1.88:1. So if you have a lot of BSP errors, rebuilding BSP several times seems to help; probably because the engine has the old tree there and simply does additional optimisations where it sees fit. Building more than three times gives no more optimisation. It seems to be replicable every time, when tried with the default settings and all optimisations, so that's certainly new and something to consider. Another thing you may notice is that if you rebuild several times without any optimisations, you will actually get worse and worse node ratio!
Rebuilding Geometry together with BSP is exactly the same as clicking the buttons one by one. But generally don't rebuild geometry too much since you'll lose the BSP tree, and if you rebuild the geometry, build BSP once, and three time before release.
Build Visibility Zones means it builds zones. Always keep it checked. It should actually be called "Erase zones" and be unchecked, since building geometry only means it builds zones, too, but building BSP without Build Visibility Zones means zones will be erased (zone count becomes -1!).
So what happens when the tree is not built at all? It seems that the same thing as when you place a light in the world and don't rebuild lighting - it will build something, but it will be very suboptimal. In the picture above you can see that no BSP build makes it like an extreme case of BSP Minimise Cuts & No Optimisation - the depth is insane, and for that kind of depth there are loads of nodes. What does that give you? For one, loads and loads of BSP errors due to the high node count, like the aforementioned surfaces being assigned to wrong zones; low performances, since the cuts are so small you will be able to see the parent of a whole lot of them at any given time.
So, in conclusion, Rebuilding BSP is very important, since it gets rid of a lot of BSP holes. The defaults are good enough, but you can tweak them by getting all zone portals to "last brushes" and setting the zone slider towards Ignore Portals, but you will have to be careful and do several attempts (the best way is to find the right value by halving the percentage and then checking if portals still hold in the editor). If you don't get a lot of BSP holes, set the Minimise Cuts/Balance Tree slider to Minimise Cuts side to gain some extra performance and kill off the remaining BSP holes; if you get a lot of holes, set the slider towards Balance Tree and you will be less likely to notice them, but be careful or you will create more holes by setting it too high. Always use Optimal BSP optimisation and geometry optimisation.
The best result in terms of node ratio that were obtained with this method on the test map was 1.73:1, with 0% on both sliders, full optimisations and rebuilding BSP three times on one Geometry build. That's quite a bit better than 3.04:1 with no optimisations and Balance Tree, though it took quite a bit longer; in fact, three rebuilds took around 20 minutes!
Also, one more thing to note is that if you have a lot of BSP holes, you also probably have really bad performance. They appear only when the engine gives up on the maths. So lower node count = better performance = less BSP errors. This is generally because brushes causing BSP holes are corrupt in some way or insanely complex and their interaction with the surrounding BSP only increases the stress that they cause on the engine.
As an example, Nyleve was rebuild (in a new file, of course), and the results were interesting: the original had a ratio of 1.88:1, after a full rebuild with the defaults it went down to 1.66:1, and no BSP holes, just like in the original. And remember that Nyleve was one of the hardest maps to rebuild properly... So good job on those optimisations! When rebuilt on UEd 2.0 for Unreal Tournament, an invisible polygon was present, but the node count did go down just like in UEd 2.1.