Notes on BSP Cuts

[Hellkeeper]

In the [url=http://wiki.beyondunreal.com/File:Legacy_legaltoon_goblin_bsphole.gif]constant battle against BSP holes and bad geometry[/url], 227 gives us two great tools, one being a better building that causes less problems, but HOMs still come up from time to time. Midway through the building of a map I dedicated several hours to the cleaning up and purification of the geometry I have, and I will share a few notes I have to make, in the way GreatEmerald [url=http://www.oldunreal.com/cgi-bin/yabb2/YaBB.pl?num=1289683089]did some times ago[/url], as I am sure this might help some.

First, a few notes on the geometry itself. [url=http://tvtropes.org/pmwiki/pmwiki.php/Main/AsYouKnow]As you know[/url], geometry is built in UnrealEd through simple text-based tools we know as brushes (you can copy pretty much anything from UnrealEd and paste it into a text editor to see how it works), which is then compiled as real geometry by the engine through the Building process. This is done using the [url=http://wiki.beyondunreal.com/Legacy:BSP]BSP process[/url] : an extensionof the Painter's algorithm (which draws an entire world starting with all the far away stuff to draw close things last, to cover the far away polygons. This way, close objects are drawn over the far away ones, and hide them : you don't see the horizon through a tree : the tree hides it. The BSP compiles a BSP tree which is used to separate at each time what is visible (and needs to be drawn) and what is not (and isn't), so that the engine does not waste time and power drawing unecessary polygons. The result is the compiled geometry of the level in the game, which is compiled from the CSG brushes of UnrealEd.

The building gives you two numbers (in the Stats tab of the Building window).

[img]http://www.oldunreal.com/wiki/images/9/9c/BuildingWindow.png[/img]

The polygon number is the total number of polygons in the map, the Node number is the number of nodes and the ratio is the number of nodes per polys. A node is a BSP leaf. What's a leaf ? Well it's supposed that a leaf is what you see in the Zone/Portal View : each zone is given a colour in UnrealEd, and in each zone, you can see shades of this colour on brushes, cut along clear lines, even on flat surfaces. One polygon with one shade is a leaf, is a node. At least, that's what is [url=http://wiki.beyondunreal.com/Legacy:Node_Count]theorized[/url] through careful research.

The goal is to reduce the number of nodes per polygon : a lower ratio will mean your leaves correspond more to the CSG surfaces of your brushes and create less polygons. During the building process, everything but the surfaces of brushes that are visible in the map are stripped from the geometry and then made into a set of convex shapes. All this is complex suppositions and hearsay. Since we have people here dealing with the entrails of the engine itself, maybe they will contradict points (or the entirety) of what precedes, but the result does not change anyway : reducing the node cout is almost always beneficial, unless you have a perfectly unbalanced geometry and map.

The Zone/Portal view has long been our only tool to chase BSP cuts and holes through the BSP in order to repair the damaged CSG brushes that create them. U227 has a working BSP Cuts view that shows the geometry with shades of red, green, blue and purple to show the BSP Cuts. This is not similar at all to the Zone/Portal view and quite confusing.

[img]http://www.oldunreal.com/wiki/images/1/13/BSPCutView.png[/img]

Because we are used to look at the leaves in the Zone/Portal Viewport, the BSP Cuts, which makes them very hard to see, seems at first completely useless. Because it's not there to show leaves, but cuts. A cut is created where brushes intersect, and the space between cuts is a leaf. This is nothing new.

If you followed me so far, here is the core of the matter.

You may notice that in a map, some cuts seem to go through walls and rooms and spread across the entire map, or large portions of it. This what I will call a Supercut. A supercut is a plague, as it forces the splitting of polygons which could be left alone without any uneccessary splitting, and may cause further problems. When several supercuts intersect, HOMs and BSP Holes are more likely than ever. A Supercut thus increases the number of nodes and polys because of something bad. Something can be an unaligned brush, a brush with a hole, or "diseased" in some way. The BSP Cut view mode makes it very easy to spot them because of colours.

[img]http://www.oldunreal.com/wiki/images/6/65/SuperCut.png[/img]

Here is a picture of DmExar in BSP Cut mode. The map was built and released before I investigated this seriously, and thus shows several crippling problems which I would try to avoid now, including a nice number of supercuts. You can see that the dashed line runs through the entire map, with different colour for the regions above and under it : all surfaces on its way are split.

[img]http://www.oldunreal.com/wiki/images/e/e6/SuperCut2.png[/img]

This other picture shows another spectacular supercut. Supercuts are almost always caused by problematic brushes, but may arise from perfect geometry. This is hard to investigate because Unreal has a nasty habit of producing slightly off-the-grid brush, which you can see by working a brush, then pasting it into notepad and noticing lots of 15.999976 where 16.000000 should be. Moreover, Supercuts like to form along axis on which many brushes are aligned : see the first picture : there's an entire height level that stops there, and many trims, pillars, floors and decorations aligned on this plane.

To investigate supercuts, search for large areas of the map split in two differently-coloured regions. Many cuts are perfectly normal, but colour changes should not be as dramatic and without reason as this.

[img]http://www.oldunreal.com/wiki/images/3/39/SuperCut3.png[/img]

Here, the supercut is runing along the entire map. Not only is it very visible, it runs through all zones and creates two very clear "upper" and "lower" parts, while most cuts stop when hitting another cut, and are limited to a zone or two in some cases. When many brushes are aligned on the same plane, it can be hard to see if the cut is normal or not in the Zone/Portal view. Moreover, some Supercuts are especially annoying, as they disappear in some part of the map, yet are fully effective in other parts of the map : they may go through the entire map, but not affect the floor of one room, making them a bit more difficult to spot. What we have here is a clear case : the cut is a degenerate one which doesn't stop anywhere. There are a couple others, and they can be very well seen by building the map with a giant empty cube entirely disconnected from it : this should be self-explanatory.

[img]http://www.oldunreal.com/wiki/images/9/9c/SuperCut4.png[/img]

Chasing along a supercut, what we are searching for is a brush sharing an entire plane (not edge) with the cut. This can be excruciating in the case of an almost finished map with tons of details, so keep track of your cuts while building. Review such brushes and see if they are not off-grid (in which case, they are doomed : rebuild them) or damaged : again, past them into notepad and see if you have .999999s instead of endless suites of 0s. This is the main sign. The PrePivot may also be a non-round number, which is very uncommon and should be an unmistakable sign.

Very easily found Supercuts are the 45° ones which cut through the map. They are easy to spot because you usually have few such brushes, and finding the ones that cause trouble is easy.

[img]http://www.oldunreal.com/wiki/images/c/c0/SuperCut5.png[/img]

As you fix supercuts, the number of nodes should go down. Some very nasty cuts can really destroy a a map's BSP Tree's balance and kill both performances and your geometry, with holes, HOMs, instant-death areas and invisible polygons (my favourite). Fixing them should purify your tree and geometry, make the node count plunge and slightly decrease your number of polygons, as less and less leaves are needed to create one full poly. Your ratio will go down, which is good : remember, a ratio of 1.50:1 is very nice, and ratio of 2:1 is high, and too far above this will strain the engine and cause errors.

In many cases, fixing such a cut will require fixing a couple of brush, and sometimes lead to a long hunt to find which of the countless brushes aligned on the unwanted supercut causes it to go postal on your map. Some Supercuts are also caused by the accumulation of brushes in one area, when they are aligned on the same plane. If you can change the order of this area, the cut may disappear instantly, which is much less demanding. Some supercuts may also be found by looking at damaged Invisible Collision Hulls. These tend to see their faces turn invisible when cut by a problematic cut or supercut, which makes them easy to spot even in Dynamic Light Mode. A quick tour in Zone/portal will show you where the cut is, and the BSP Cut view will show you how far it spreads.

if fixing supercuts makes your ratio increase, you may have unveiled another Supercut somewhere, which was counteracted by the one you just fixed : bad BSP is a gift that keeps on giving. As you fix more and more, though, your ratio will soon return to a lower value (unless you end up discovering a real abomination). The BSP Cut view will also help you find cuts which, without being supercuts, are large cuts along unneccessarily long planes.

[img]http://www.oldunreal.com/wiki/images/4/4d/NotASuperCut.png[/img]

Fixing these is also a very good idea and should be easier : because they don't spread to the entire map, there are less brushes likely to cause them, and these are usually less damagaed than those creating full-blown supercuts. Finally, because Semi-Solids are another part of the BSP tree : they don't occlude what they hide despite having a collision : solid for the player, non-solid for the engine, that's what a semi-solid is. Because they don't occlude, they are not built by the engine exactly like normal, "solid" geometry, and are thus always displayed in a vividly different colour than the surrounding geometry.

[img]http://www.oldunreal.com/wiki/images/7/74/SemiSolidCut.png[/img]

This is all I have. I hope it can help you. If you have more technical informations, they are welcome too.

[GreatEmerald]

That's interesting. Good idea with the giant cube. I imagine that having an enormous hollow cube that can envelop your whole map could be even better for this.

How did you fix them, aside from fixing rounding errors? Did you have to move any zone portals, transform things permanently, etc.?

And in the SuperCut5 picture, the node with two colours shows up like when two solid polygons share the same space (flickering), right?

This is probably what was wrong in one of Leo's converted maps as well as Unreal's own flyby sequence. Hmm. I didn't think they were that common.

[Hellkeeper]

Fixing these is a pain, because spotting the good brush is the hardest part. Once you have it, however, there's not many things you can do : Quake engines have the HINT brushes which can be used to manually split the BSP. In Unreal, apart from correcting rounding errors, you have a few possibilities : moving the brush if that's possible, but usually you will have to work with brush order. Either propel the brush at the beginning or end of the list, or do that to the entire set of brush of which it is part : in the case of a trim, you can try changing the order of the trim to last, or do this to both the trim, the brush it is placed on and the brushes touching it. Recreating the brush from scratch can also help, because it changes the entire brush in addition to setting it at the end of the list.

In the SuperCut5 picture, the brush is not flickering: the surface show normally and doesn't look bugged at all. However, when a single brush has one face (usually one which is on a different plane from all others) with a sharply contrasting colour, this is usually a sign : in this case, the brushes with the angle all have this, and they are the only brushes perfectly aligned on the plane of the supercut.

[GreatEmerald]

Oh, so that's just a strange form of that surface. I see. But I don't see how this is so different from the other colours, they contrast quite a bit as well.

Interesting idea about brush order, too, but it could cause problems as well (if you send a solid brush to first, its geometry is as good as gone). I wish there was an easier way to fine-tune the brush order...

[Hellkeeper]

Setting an added brush to first makes no sense : at the very least, what you want to do is select the brush itself and the subtracted brush inside which he is, and then make the set first in order. However, I have no idea how the brush order could be more precisely manipulated, apart from displaying a drawing list encompassing the entire brushwork, with a "move up" and "move down" set of commands. In maps with several thousands of brush, this might become hard to use.

The difference in colour is only a sign. What really matters is the extend of the cut. Two different colours is not a problem if the cut is small and stops at the next cut. But if the cut is uneccessarily extended, it will stick out, as there is a sharp contrast between both sides of the cuts, all throughout the map.

Semi-solids, in me experience, are almost always blue or purple though. I don't know why, but they stick out well this way, and this means that a supercut extended to them (which happens) is all the more visible on them. It usually results in half the semi-solid missing immediately after build.

[GreatEmerald]

A better way to tune order would be numerical. A "Change order" option that gives you the real number that the brush is set to. Setting it one higher would make it appear "later", setting it lower would make it appear "earlier". If a group is selected, the changes could be relative (+5 or -5).

[fakeaccount]

I have a  theory for BSP holes. There is a thing in 3D modelling called "T-junction" spot. It happens when an edge of a triangle is linked to the middle of another edge, hence the name. In the image below it is the E point.

[img]http://www.cg.tuwien.ac.at/~msh/vbspdocs/vt_trace.GIF[/img]

http://www.cg.tuwien.ac.at/~msh/vbspdocs/v_tech.html In zoneportal view, open any map, triangles like that happen everywhere.

[img]http://s20.postimg.org/a86cv2xfx/t_junction_fix.png[/img]

Editing the edges of a stair to make all edges link to the same vertex like that should at least reduce the vertex count. Do that everywhere in the map where T-junctions occur, manually tessellate brushe's faces to control the subdivision of concave polygons in convex forms.

http://www.angelmapper.com/gamedev/tutorials/uedmeshes.htm Another example. Do the same tessellation to BSP brushes too.

http://www.hourences.com/tutorials-ue1ue2-bsp/ As hourences said, unreal engine 1 BSP auto occludes everything behind it. Having control of BSP's tessellation should avoid the arbitrary cuts generated by the engine.

[Captain_Clark]

http://www.cg.tuwien.ac.at/~msh/vbspdocs/v_tech.html In zoneportal view, open any map, triangles like that happen everywhere.

[img]http://s20.postimg.org/a86cv2xfx/t_junction_fix.png[/img]

Editing the edges of a stair to make all edges link to the same vertex like that should at least reduce the vertex count. Do that everywhere in the map where T-junctions occur, manually tessellate brushe's faces to control the subdivision of concave polygons in convex forms.

Or you could just make yo stair brushes in the 2D editor

Also, if you move the vertices to the same point, it causes an error...

.......
SZ
.......