The Black Sheep Wiki
The Black Sheep Wiki
Search:
Ued2 | BSP, Solid/Semi-solids

The contents of this tutorial were written by those at http://www.birrabrothers.com/drac/dmain.html


BSP concept:

BSP (Binary space partition) is a way to pre-render the geometry visibility and
collision.
This is refered to as the BSP tree and geometry is indexed here to allow the
realtime game engine to faster calculate what you see and collide with.

Without BSP you would simply have to draw all objects and walls ontop of each other,
starting with the ones in the back and end up with the ones in front of
the player/view.
Considering the size and complexity of maps today, this would be too demanding on
CPU/GPU.

By indexing the geometry in a tree, using a root and following sub structures, and
sub structures under there, the engine can easily trace the direction and amount of
structure to draw on the screen.

It is also important to know that this isn’t a perfect solution and glitches,
like BSP holes, must be expected.

To create this BSP-tree, cuts are made to the current geometry to create nodes which
is then added and indexed.

From the screenshots below you can see three images.
The first one show one empty room without any cuts at all.
In the second and third screenshot you can see that the more structure we add
the more cuts are made which is used to calcuate how much of the surrounding
geometry you see at any give position.

If you get a BSP hole you will see that particular area as a black hole and can be
caused by a large number of factors.
This can be too complex brush work, incorrect use of semi/non solids, brushes that
do not fit to grid and so on.

BSP holes and HOM:

BSP holes are caused by incorrect BSP tree and can be seen when you have a black
hole in the map.
HOM (Hall of Mirror) is more an effect than an error. It will look like the last
frame is smeared out.
(It is important to know that HOM might be seen in a BSP hole but because
you have the HOM effect doesn’t mean you have a BSP hole).

A BSP hole is a hole in the wall, it might be both visible and collision.
If it is visible you might be able to see through it and into other parts
of the map.

HOM is caused when you are able to see into nothing.
Nothing means parts of the buildable area that you do not have added/subtracted any
structure yet.
This will happen if you use masked textures or transparency on walls that lead into
the “nothing”.

BSP collision hulls are most often caused when complex brushes or odd
shaped brushes are used.
Not by itself but in the close area considering the cuts that are made.
It can also be caused along with other brushes like semi/non solids and
zone portals.

What happens is that the calculated solid gemotry comes out incorrect creating
invisible collision geometry (or lack of it, causing you to die leaving a crater).
This is also why you must rebuild the map before you play it.

Nodes and Polys:

What is a poly?
A poly is the same as one side of a brush.
Another term that is widely used is face.
To simplify, a solid cube brush have six polys, sides or faces.

Hopefully you understand the basics behind the BSP tree by now so I will
just jump straight into nodes.
For each cut that is made a new surface of the brush is created.
Not a regular poly but a node.
These nodes are then traced and put in the BSP tree.
That is why you get such weird cuts going from the corners of brushes
across other brushes and so on.
This is completely normal.
(If you want to see the BSP cuts you should use the BSP view or zone/portal
view).

By tracing these cuts you are to a certain degree able to eliminate problem
areas and to find brushes that actually cause BSP holes.
It will also give you a good pointer on what you might need to do to fix
exisitng BSP holes.

Lets explorer another aspect of nodes and polys, FPS.
Frames Per Second (FPS) is the amount of frames your computer is able to render
each second. The more the better.
(It should not go above your monitor frequency though, otherwise you get tearing).

This do not have that much to do with BSP itself except for a few very
important points.

  • A large node count or a large poly count is not better than the other but

a balance of them both.

  • A normal map usually go between 200–400 polys for each fame and twice as

many nodes.
(This can be seen typing “stat fps” in the console).

If you were to convert alot of solid geometry to semi-solids you would
increase the poly count but reduce the node count.

A large node count will cause the engine to spend more time tracing the BSP
tree while a large poly count will demand more time to render the screen.

As you can imagine, a balance of the two, around 2 nodes for each poly,
will keep the maps fps to optimal.
(In some detailed area you should even expect a 3 times node count).

CSG and solidity (Construction Solid Geometry and Solidity):

The world is in terms of editing a large solid cube shape.
From this you remove and add mass as you progress in the creation of your
design.

The ways you are able to use brushes are CSG (Construction Solid Geometry)
and solidity.
CSG equals additive or subtractive while solidity refer to solid, semi-solid and
non-solid.
This is the clay you are able to use to shape the world as you like.

A subtractive brush will remove mass inside its frame, while additive add mass.
Solidity can obviously only be assigned to additive brushes.

In the editor the type and state of brush is shown with colors.
A yellow brush is subtractive while a blue brush is additive and solid.
A purple/pink brush is addtive but semi-solid, while a green brush is non-solid.

You will quickly notice that an invisible collision hull is simply a semi-solid.

What kind of brush you use play a fairly important part in how the BSP is built.
(I cannot tell for sure how each object is placed/treated in the BSP tree).

Brush order, First and Last:

When you rebuild, the engine need to re-add (and subtract) all brushes.
This is what order is for.
The first brush will be introduced first and then the next until it reach the last.
In a way you can say it is a simple timeline.

This will prevent chaos considered when what brush should add solid geometry
and when subtracted brushes should remove.

If you have a large room and add a small table in the middle, the large room is
first and the table last. Otherwise the table would be removed by the large room.

This is also used to calculate when brushes should cause cuts to be made and be cut
itself.

This is also important considering semi-solids.
Semi-solids will be best placed last as they do not add cuts but can be cut by
other brushes.

Deintersect / Intersect:

To avoid BSP holes you might want your brushes to fit nicely with the rest
of the geometry.
To accomplish this you most likely need to use deintersect or intersect.

Both will cut parts of the brush to make sure it fit with the rest.
Intersect will remove all parts of the brush that occupy open space, or
areas that has previously been subtracted.
Deintersect do the opposite, remove parts of the brush that exist in solid
area (added).

Actually these two functions have two significant uses.
The first and obvious one is to make brushes fit with each other if primitive
brushes can’t be used.
The second is used to create complex brushes.

None of them will be explained here but I will try to compare it with BSP.

You should know by know that complex brush work will increase the chance of
BSP holes.
Building complex structures using mutiple brushes will more likely result
in BSP holes than one complex brush.
The engine is also able to render one brush faster than many smaller ones.

Suddenly you will think. Why don’t I create the entire map as one huge brush?
Bad idea, very incredibly bad idea.
The entire map would have to be rendered at all times leaving the
BSP tree useless.
In reality a brush should not be too complex because it will consume too much
time being rendered.
I hear and read that brushes should not have more than 500 polys.
I think this is more like any other UED taboos.
Lets put it this way. If your brush is pulling 100+ polys, there is a very
good chance that your brush is way too complex.

Another interesting aspect of creating “complex” brushes and make them fit
nice and tidey into the map is that complex brushes tend to create really
nasty BSP cuts and possible holes, or foundation for BSP holes.
In these situations it is actually better to let more primitive brushes
overlap other brushes than deintersect or intersect them.

Do not deintersect or intersect sheets. They will be “destroyed”.

Topics not added yet:

Semi-Solids
Non-Solids
sheets and Zone Portals
The Grid
Preventing / Fixing BSP Holes

Page last modified on May 31, 2011, at 11:58 AM