How avoid BSP errors?

Tutorials and discussions about Mapping - Introduce your own ones!
Buggie
Godlike
Posts: 2733
Joined: Sat Mar 21, 2020 5:32 am

How avoid BSP errors?

Post by Buggie »

There was a normal map. All was good.
I added an Invisible Collision Hull (in fact a semi-solid brush) in many places to simulate solid decorations.
After that, everything went to hell.
Three points of death have appeared. All of the above added brushes.
I have set build settings as 100/70.
These death points have disappeared. But a new one appeared elsewhere.
Just in the middle of the room.
I'm trying to remove it. Made 4 near-by brushes solid instead of semi-solid.
The point of death is gone.
Another death point appeared in the adjoining room. And HOM.

How does it even work? What is the logic behind all this?

What have I done wrong? How can you avoid this kind of thing?
User avatar
sektor2111
Godlike
Posts: 6410
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: How avoid BSP errors?

Post by sektor2111 »

When I worked at my MonsterHunt map MH-Sk_Godz I was facing some of these issues. Map has separate areas. Those areas I tried to spread them as much as possible because it looks like some of these rooms were doing BSPCuts affecting other areas too. In that other area by adding a semisolid wall or a semisolid box it turned things in garbage. Semisolids are affected by BSPCuts which are passing nearby them or in the same closed space if I'm not mistaking. I spent time moving areas away from cut lines which a previous room was doing. In that moment I did not used too much "Order To Last/First" but... it was about main rooms and their "alignment". BspCut generators as I could figure are coming from those brushes which are having funky vertex values. You told me about errors up to 0.3 which are corrected during build. Let's say that BSPCuts are starting to show up even at smaller errors than 0.3 and sooner or later they will affect semisolids and even non-solids (my lamps were going trashed). The more is added in map the more messed up goes BSP tree if we are accepting BSP Cuts crossing through zones.

My two cents.
Buggie
Godlike
Posts: 2733
Joined: Sat Mar 21, 2020 5:32 am

Re: How avoid BSP errors?

Post by Buggie »

In my understanding, creating a map is such a process when you perform certain actions that entail the expected result.

For example, when you need a pillar, you add a pillar to the map and in the game it looks like a pillar.

And if you add a pillar in the editor and at the output you get death points in random places, then this is not a map creation. What the hell is that.

How can you create anything at all in such conditions, when adding a cube to the map destroys everything to hell?

By the way, Feralidragon strongly insisted that building without a BSP step was wrong. That this is very, very bad.
So that's it. I built the map without this step and there were no death points. Yes, some of polys for the semi-solid brushes are not visible. But this is not fatal. At least players don't die on empty places.
And if a monster dies at the point of death, it does not produce an event. The doors won't open. The map doesn't work.

If other things being equal, I would prefer the map to work, but some planes were not visible on it, than a map on which there are death points and which, in principle, cannot be passed.

This is a word about "correctness".
User avatar
Aspide
Skilled
Posts: 191
Joined: Wed Jun 09, 2021 12:13 am

Re: How avoid BSP errors?

Post by Aspide »

Oh BSP, my worst enemy. I remember the countless times I had to fight invisible walls, disappearing geometry or points of death. I always try to use as little solid brushes as possible, because of the BSP holes and therefore semisolids are my preference for brushes (especially brushes used for decorations). However sometimes semisolids cause more trouble. I think the strategy is to use as many semisolids as possible but transforming them to solid if they cause glitches. Also changing the location of the brush helps a lot, I remember that moving a brush 1 unit saved my map from being splitted in two. :mrgreen:

Also this tutorial by the great Hourences helped me a lot: http://www.hourences.com/tutorials-ue1ue2-bsp/
Somewhere in Nevada...
User avatar
sektor2111
Godlike
Posts: 6410
Joined: Sun May 09, 2010 6:15 pm
Location: On the roof.

Re: How avoid BSP errors?

Post by sektor2111 »

I got it... in other hand, when I did MH-FloorWays map, more entertaining things were there. Map has now a good state without "falling out of world" but... that map is result of build with high level on sliders and all it has processed it's Geometry and Lightning. Whoever is trying to do a full rebuild map is going into a trash state without a game. I did some mistakes at certain brushes and right now because I have a normal map in big parts, I'm not going to waste two months for making it compatible with a normal full build Geometry BSP and Lightning (and Paths - there will be created bugs if people are not knowing how did I simplified paths in 2017).
In "rv2" version I could align textures on pillars using my calculator but... I did the same sort of build for preventing map to get trashed without touching anything at paths, just solving a bit textures. It's pretty much wrong executed with my knowledge from that time and I will accept all complains about that as long as it's entirely my fault. Toggling grid without making sure that selected brush did not get screwed it's a bad practice but... I did not know too much about such things and this is how I screwed up plain build.

Converting/Fixing certain map a la Sektor. Sektor's Stages:
- a quick examination around surfaces for HOMS;
- another examination for BSPCuts;
- a few game sessions hunting invisible collisions and falls into void.
Decision taken: If map has HOMS and a lot of BSPCuts, and 1000+ brushes it's not like Sektor will waste time with that. It's only demonstrating a bad execution and there it will be needed to work at 500+ brushes and NOT only in Editor, or a combined work Editor-NotePad++, export/import align, vertex editing, checking "edited" brush, fixing data if needed, etc.
Buggie
Godlike
Posts: 2733
Joined: Sat Mar 21, 2020 5:32 am

Re: How avoid BSP errors?

Post by Buggie »

Aspide wrote: Tue Sep 21, 2021 7:17 am Also this tutorial by the great Hourences helped me a lot: http://www.hourences.com/tutorials-ue1ue2-bsp/
Haha. There also advice skip BSP build step for avoid problems or solve some problems.

In fact I solve current problem by replace semi-solids by movers, but entire situation not normal.

I suspect in build code exists some errors which cause this. And proper solution is fix this errors rather make small changes and pray for problem gone.
User avatar
Hellkeeper
Inhuman
Posts: 905
Joined: Tue Feb 25, 2014 12:32 pm
Personal rank: Soulless Automaton
Location: France
Contact:

Re: How avoid BSP errors?

Post by Hellkeeper »

Is your invisible collision hill in contact with other geometry? Space it a few units from anything solid, they tend to create artifacts like this.
You must construct additional pylons.
Buggie
Godlike
Posts: 2733
Joined: Sat Mar 21, 2020 5:32 am

Re: How avoid BSP errors?

Post by Buggie »

Yes, some of it - contacts. In fact real issue I solve by replace all this hulls to movers. But this not cancel fact - mapping sometimes screwed by heavy mistakes in build process.

If you want play with map for find reason debug version here: https://github.com/OldUnreal/UnrealTour ... issues/554

I prepare MH-HP2-GrandStaircaseV3_bug2 version for some who play with it.

About your assumption - i try all added brushes goes exactly up for make all of it fly in air. So i check one dead spot. it solved. But on opposite wall appear another which not be before.
Before:
before.jpg
After:
aftrer.jpg
User avatar
Feralidragon
Godlike
Posts: 5493
Joined: Wed Feb 27, 2008 6:24 pm
Personal rank: Work In Progress
Location: Liandri

Re: How avoid BSP errors?

Post by Feralidragon »

I could write entire books at this point about BSP, why the vast majority of the ongoing myths are really just that (myths), and how most BSP issues are fairly simple to fix, how Hourences was completely wrong in most of the BSP issues he highlighted (he knew a lot about design, not that much about the technical side of how BSP works and why problems happen), but considering that in another thread I have already demonstrated through a practical example how all BSP issues from a completely fucked up map were fixed in pretty much 2 steps, and seeing that people are still spreading the same misconceptions, that's an uphill battle I am not willing to participate in anymore.

So I won't even talk about semi-solids and whatnot again (it gets old having to repeat the same all the time), so this time I will talk about something different: geometry errors.

One thing to keep in mind is that, while the BSP builder may indeed have bugs, the BSP (and CSG) algorithms in general work flawlessly on paper (mathematically), but then when it comes to implementing them in the real world in a computer using a binary system of numbers there's a big challenge here when it comes to arithmetic precision.

In other words, these types algorithms will start to break apart if you don't have enough precision for all the types of calculation involved, namely addition, subtraction, multiplication, division, square roots, cosines, etc, etc.

And in any numeric system, be it decimal (base 10) or binary (base 2), or any other, while you can represent any integer of any integer base (2, 10, 16, ...) in any other integer base with full 100% accuracy (you can represent the number 7 in all integer bases accurately), for the fractional part this is a huge problem, that has never been solved, because it can never be solved (it's a math issue), because you can only accurately represent fractions which are combinations of inverse powers of the base itself.

In other words, as an example, in binary (base 2) you can represent something like 0.5 accurately in binary: 0.1, because 0.5 is 2⁻¹.
In the same way you can represent something like 0.75, which is 0.11 in binary, because it's equal to 2⁻¹ + 2⁻² .

However, something seemingly as innocent of a number as 0.2 for example, cannot be ever be represented accurately in binary, ever, because there's no sum of inverse powers of 2 that add up to the equivalent of 0.2, so you can only approximate to it like 0.00110011001100110011 for example, which is close to 0.2, but not actually 0.2 (it's 0.19999980926513671875).

This is why there's a famous example of a seemingly simple calculation that doesn't give the expected result, and which you could try yourself in any programming language using any standard computer, namely: 0.1 + 0.2 .
This calculation should naturally result in the number 0.3, however when performed by a standard computer it actually results in 0.30000000000000004 instead, every single time.

This is also why that when building a system meant to process things like bank transactions, purchases, anything with an assigned monetary value of some kind, since full precision is required, the number is never stored as "1.99" for example but rather as an integer like "199", so both addition and subtraction always works accurately: because 0.1 + 0.2 provides the wrong result, but something like 10 + 20 does the expected result: 30 (which you can then convert back to 0.3).

All of this to say the following: the BSP builder also uses the standard floating point to build all the geometry, do all the cuts, calculate all the polygons, etc, so even if the algorithm itself has no bugs whatsoever, geometry errors may still arise because the results of most numeric operations cannot be accurately represented, and that error accumulates the more calculations are performed over previously calculated values.

Furthermore, things like divisions, cosines and square roots will increase the loss of precision since most resulting numbers cannot be accurately represented in binary (not even in decimal, base 10), so the error resulting from the approximations adds and multiplies along the process, potentially resulting in unexpected results.

This is one of the reasons (there are more) why staying snapped to the grid is a good idea, as well avoiding odd angles and vertices in non-integer positions, because keeping the vertices in positions that can be accurately represented, and using angles that also can be accurately represented, leads to better results in the form calculations resulting in more accurate numbers altogether, which prevents a lot of errors of this kind.

Even if you have 2 surfaces apparently perfectly aligned with each other, if they are off grid then odds are that the surfaces do not have exactly the same surface normal (angle), because the vertices themselves are not positioned in a precise location due to the fractional part of those vertices, which may then result in 2 different very similar cuts for example, when it should have been one.

So take this into account when both building a map, as well as fixing an existing one.

Again, not saying there aren't bugs in the algorithm itself, there might be, but there are plenty of other, maybe stronger, factors at play here that must not be forgotten.
In other words, the algorithm itself could be perfect, but you would still have errors due to these limitations.
Last edited by Feralidragon on Tue Sep 21, 2021 4:22 pm, edited 2 times in total.
Buggie
Godlike
Posts: 2733
Joined: Sat Mar 21, 2020 5:32 am

Re: How avoid BSP errors?

Post by Buggie »

For work with rounding errors ppl invent additional accuracy and rounding. And UE1 mostly aware of this. But possible not in all places.
In any case if in code somewhere check floats by equality it is bug and definitely not flawless / perfect algorithm.

About other speech - ppl want worked map. Maybe make not proper. Anyway it is better from proper but not worked map.
For example CTF-Blice - if you want make map as it must be for tune engine - it is one story. But if you want make playable map - another.
In second case you can use "not-proper" ways for achieve results.

Most mappers interest in practical solution of problems even if it hackish or ad-hoc in some way.
User avatar
Feralidragon
Godlike
Posts: 5493
Joined: Wed Feb 27, 2008 6:24 pm
Personal rank: Work In Progress
Location: Liandri

Re: How avoid BSP errors?

Post by Feralidragon »

I am going to make an actual playable map this time for the contest, so we'll see how that goes. :)

But Blice having terrain (the ground is not flat outside either), and all types of BSP cuts running across the map, should by itself be a good demo of how a seemingly high-node and fairly complex map can be done, and it uses semi-solids quite heavily (literally thousands of brushes), as well movers, etc.

And if you try the Lite version you will see that the performance is actually quite good too (playable at least), because what's actually making the map be completely unplayable is the old FX package effects which the map is filled with, and the Lite version is exactly the same map, but with the effects removed.
For work with rounding errors ppl invent additional accuracy and rounding. And UE1 mostly aware of this. But possible not in all places.
In any case if in code somewhere check floats by equality it is bug and definitely not flawless / perfect algorithm.
No matter which rounding methods you use, you still end up with the same problem: rounding doesn't make anything more accurate, it just solves some very particular proximity problems, like if 2 vectors are too close to one another you could round them to be equal for example with the assumption that they are meant to be equal in that context, however that in itself could be an error because maybe those vectors may be actually meant to not be the same.

The problem is not float equality, is the actual starting float values to begin with, and the posterior error accumulation the calculations create, you cannot really solve that.
Even if you could represent numbers accurately (which you can by using large integers instead), you still have the problem with the algorithms themselves to calculate things like square roots which are not fully precise either: they are precise enough for most applications, but where precision is needed the standard algorithms aren't precise enough, and errors will be noticeable.

But again, not saying that this is the problem you're necessarily having here, I am just saying to not brush it aside and automatically attribute the problem to a "bug" in the builder, because a lot of the errors stem from limitations of both the hardware and used numeric system.

Since you have given a link to a debug version, I can try to take a look into it later on today, see what I can find and fix.
Maybe it's a bug in the builder, maybe not.
User avatar
TankBeef
Masterful
Posts: 586
Joined: Tue Apr 13, 2021 12:56 am

Re: How avoid BSP errors?

Post by TankBeef »

Feralidragon wrote: Tue Sep 21, 2021 3:53 pm I am going to make an actual playable map this time for the contest, so we'll see how that goes. :)
Ok, don't want to derail the thread, but just a tiny comment, cause I saw this.
Hey, Blice is awesome, and very playable map. I don't even consider my laptop "high end", very below average in fact, and well...the timedemo shows about 30-40 fps, but...in practice, I play it all the time, it does not crash, and it is very fun, and beautiful. I play the full version, not the lite, and it works for me. And I use lots of bots. So yes, Blice can be perfectly played, don't be scared. Now, don't you dare put it on a server, cause it will lag guaranteed. :lol2: But for offline play, awesome!!! :tu:
Red_Fist
Godlike
Posts: 2165
Joined: Sun Oct 05, 2008 3:31 am

Re: How avoid BSP errors?

Post by Red_Fist »

"There was a normal map. All was good.
I added an Invisible Collision Hull (in fact a semi-solid brush) in many places to simulate solid decorations.
After that, everything went to hell."

It's been like that for the last 20 years.

The only clue that may be worth observing, is that when UT2004 came out, well I think it was collision hulls-semi-solids, should be touching a subtract, and if you intersect, make a new builder brush from that, then just set the brush, place the brush without intersecting, but touching the subtract.

I use those now for small cube brushes for lights or the simple geometry items, in that way one added cube won't bust up the polys, while looking at the editor BSP view.
Try it if you can, and have all those semi brushes touching a subtract, or resting in an add brush.

It seems to me from fixing maps is that people DON'T intersect and have brushes poking outside of outer wall. So when you intersect you see the large room BSP get chopped up from an add (blue) brush.
So every time I fix something I have to go through areas of maps that had no intersecting.

Now along with that, my theory is, since the semi solids don't create more cuts, , and solids cause cuts.

That BSP holes appear because the map is leaking to the void, in some way, because the semi solid (no cuts) needs a reference surface, and the solid (needs intersecting and de-intersecting and/or not punch through map.) that creates cuts, needs a reference surface.

I also will intersect a subtract brush on those (put-together maps)

Then you get the green brushes colliding with the pink semi's problem. After all that the map becomes more solid and predictable to find the REAL spots that are causing the problem, or, the map will work perfectly, by fixing things like that.

I just feel that if this thing (build map bsp) using all math to calculate the bsp, that things need a reference so it knows where itself came from, as it goes through the process of using each thing to cycle through each brush.
So if the brush isn't really on or in or random cut, it will only calculate crappy mapping that screws up the build.


Also that other map you did, you left the builder box in there, so all of that should have been deleted before !!! talking about any BSP problems. (or fixing bsp)
Binary Space Partitioning
User avatar
Feralidragon
Godlike
Posts: 5493
Joined: Wed Feb 27, 2008 6:24 pm
Personal rank: Work In Progress
Location: Liandri

Re: How avoid BSP errors?

Post by Feralidragon »

There you go, I have fixed the problems in the reported map.
For more details, check here: https://github.com/OldUnreal/UnrealTour ... -924370147

Took me around 10 minutes (debug + fix + testing).
User avatar
Swanky
Adept
Posts: 462
Joined: Sun Mar 16, 2008 9:06 pm
Personal rank: Brush Commander
Location: inside ze bocks
Contact:

Re: How avoid BSP errors?

Post by Swanky »

Feralidragon wrote: Tue Sep 21, 2021 2:40 pm ...long not very interesting monologue...
...I could go to lengths about why I don't care about a rounding issue on a mathematical problem that was left in the engine. As a mapper, you want practical solutions and even if Hourences was wrong in what he perceived, I valued his pointers into the right direction for many years and many, many maps. So you could spend more time iterating on the issue or fix it; as a mapper the problem is most often man-made and the solution often as simple as "build clean, transform your brush or order to last". Doesn't fix everything, granted, but from personal experience most other issues only come into place on big enough maps with many non-conform surfaces (such as terrain maps) where the rounding actually makes a difference (after rounding up / down).
Post Reply