...let's just say this is a question of "how should the brush be defined for the purposes of editor manipulation?", which I think is the important issue here...

Regardless of how it is stored internally, in terms of user interface, you could try to treat it like a bunch of polygons - and I think WC/Hammer did that, allowing you to pull verts around willy-nilly.

However, this is pointless IMO, because all that means is you are exposing an interface that allows the user to produce an invalid brush. Now you either have to detect and prevent those manipulations - which simply means you might as well just go with Radiant-stype manipulation in the first place, or - in the case of WC/Hammer - go "sod it, let the designer spot the invalid brushes later and fix them himself".

This was basically the reason I ditched Hammer and moved to radiant. 

That's very annoying.

But I don't think its an issue that can ever be properly eliminated just because of the amount of tools and potential upsets in Quake.

We've all seen brushes that have no reason to provoke a leak, or deform weirdly when compiled. And then rebuilding the exact same brush typically solves the issue.

I still use WC for two reasons - the texture locking and general laziness to learn another editor. 

I think it was a good choice by Carmack for reducing user error. As was stated above, a brush formed via clipping planes is, by definition, convex. It has to be - or it's empty, in which case you can discard it.

The errors we see in maps are, I believe, a result of rounding errors and precision problems but the basic idea of how he stored the brushes was actually very smart.

Where it was a poor choice was in texture alignment control. If he stored actual verts, he could have stored actual UV coordinates along with them, and then we'd have some truly beautiful looking Quake maps because you could have real UV tools and make everything perfect. And texture lock would be the default action in level editors, not a specialized feature. 

But by today's standards, it makes operations like vertex editing and rotation very complex to do correctly. It's quite a hassle because the tool chain is not prepared for the brushes that modern editors can produce, even if they are correct.

As a programmer, I have to take care that what the user sees in the editor is actually what QBSP will produce after being converted to the halfspace representation in map files.

Also, the map format has nothing to do with "user error". The user should not have to look at map files. The editing software must take care that the user can only produce correct map files, and the compilers must correctly translate the map file into the representation the engine understands. Ideally, the user should not have to worry about this. And that would be much easier to achieve if you could store vertices in the map files.

The way it is now, the complexity is shifted out of the map files into the editor and the compiler. That's not a good thing. Ideally, the map file format would make it possible for an editor to precisely store in it what the user is seeing in the editor. But since this is not possible with the map file format, the editing software must not let the user create geometry that either cannot be represented in a map file or that cannot be reproduced by the compilers. A very complicated task, I will tell you. 

Hmm, I think by user error what I meant was tool errors. If the map editor can only spit out a set of planes, then it's impossible to feed a concave brush to the QBSP compiler. That sort of idea.

The guy using the software shouldn't have to think about it, I agree. 

He usually has to because no editor completely solves this problem. They produce invalid brushes, micro leaks , drifting vertices etc.

Also the half space format in map files does still allow a number of errors such as duplicate planes, empty brushes and open brushes.

I used to be a fan of the map file format, but writing an editor has killed my love for it. I'd much rather have to deal with bugs that I can reliably fix that with precision errors that keep cropping up all over the place.

Maybe if there was a specification on how vertices are computed from planes things would be better. But all editors and compilers have their own way of doing this. 

Oh please don't get the idea that I'm defending it. I would MUCH rather have verts and UV coordinates and just get on with it. I think the MAP file format made sense to Carmack at the time since his experience with 3D stuff was fairly low at that point but it's far from ideal. 

It's like the decision to planar map everything by default. That works, yes, but it's not as great an aid to level designers as he apparently hoped. You usually end up having to touch almost every face in the map anyway... 

That's why I intend for TrenchBroom to eventually support Valve 220 maps where you can change the texture mapping in any way you like. At least TXQBSP supports this extension. 

Hrm, can someone point me to an example map or two that uses the 220 format? Would like to support this in my qbsp as well. 

e4m1rmx.map here 

That's great, thanks! 

What would be the ramifications of building an entire map out of tetrahedrons where each brush only contributed a single face to the final mesh? 

If you mean like make an organic-looking mesh in a modelling program and write a converter that spits the mesh out as a .map of tets, well...

...it would generate a gargantuan number of different bsp splitting planes that may or may not cause the the bsp algorithm to take a shit. Also, hull1 and hull2 would likely be awful leaky messes as the tets expand in funky ways. 

from experience of mucking around with this kind of thing myself: Let's say you make a cave system as a triangle mesh in a modelling app and turn it into tetrahedrons.

- The larger the tets are, the less problems you get.
- If all the vertices are grid-snapped, and the chunkier the grid, the less problems you get. I found below grid-16, things pretty much leak 100% of the time. Above that size, things leak maybe only 70% of the time. Why? Not sure but it might be something like: the chunkier the grid, then statistically (over a large mesh) the less different clipping planes there are.

I personally think there is still promise in this approach, but the solution should come via a modified .bsp compiler...

Imagine a compiler that takes a triangle mesh as input. Hull 1 and 2 are found by "pushing" this mesh in a way so the hull 1 and 2 meshes are still nice and clean. Also, without having to treat them as tetrahedron brushes, then you don't have to worry about errors caused by figuring out the unseen faces and clipping them away. By definition, you are going the .bsp compiler a contract that says "there are no faces here that need clipping away, and every face there is, should be visible and in the bsp tree", which should allow you to cut out all manner of error-prone middlemen. 

after tarting around in trenchbroom this morning, I doubt I'll ever need to do it like that.

It seems I've been getting along great with a workflow that's basically: block out an organic area with big chunky brushes (cubes and whatnot) in Radiant (currently radiant's ortho views still make that my preferred way of laying stuff out quickly and accurately), but then I can now import the rocky bits into trenchbroom - and then proceed to trenchbroom the fuck out of those rocks, and import them back into radiant. Magic. 

Let's turn trenchbroom into a verb.

"Damn, you trenchbroomed the SHIT out of that map..." 

Thanks Kinn.

I was curious about the technical problems that might result from trying to compile maps made excessively out of tetrahedrons. Sleepwalkr and I briefly discussed ways of improving trisouping and I was thinking about having the user create a single triangle and then have the editor generate the rest of the brush basing the final vertex on center of the face and normal of the face and such: https://github.com/kduske/TrenchBroom/issues/316 

I'll post some shots of my experiment in a bit... 

First, I made a mess mesh in Maya. I decided to make a big caverny thing with crazy rocky bridges going everywhere. This is a big-arse cavern:

Outside looking in:
http://i.imgur.com/XmNM8iu.png

Inside:
http://i.imgur.com/FlUqsNh.png

Now, I found through experimentation, that the higher the grid granularity (that the verts of the mesh were snapped to), the less problems bsp seemed to have with it. I found grid 16 seemed a good compromise between minimising bsp pant-soilings, whilst still being a fine enough grid to allow decent shapes to be sculpted.

To enforce the grid, I created some melscript to snap all verts in the mesh to this grid, which I made sure I did before exporting the mesh.

Now the fun part. I had to write a load of code to turn the mesh I exported into a quake .map file. Now, I am fairly lazy and instead of going to the trouble of writing a proper tool to do this, I realised that I spend most of my day tarting about in the Unity3D engine - an engine that already imports meshes and has an API already exposed for me to access and manipulate those meshes.

So I wrote a load of code as a Unity project that processes an imported mesh and writes a quake map file. In essence, I turn all the triangles into tetrahedrons and spit out a .map file. I do a load of misc crap as well like sanity checking the mesh for duped tris, and putting textures on it and stuff.

Now, you can get quite clever with the tetrahedron conversion. The naive approach is simply to write one tet for each triangle. However, it is better to look for groups of triangles that can be combined into a single brush. In many cases you can turn two triangles into a single tetrahedron (let's call these "tri-pairs"), where two faces are visible in the map, and two faces outside (as opposed to one face inside and three faces outside). Beyond single tris and tri-pairs, you can search for even larger groupings of triangles, 3, 4 or more, that can also easily be turned into just one brush. I detected these, but in practice it is so rare to find a valid grouping larger than a tri-pair, that I only bothered in the end to divide the mesh up into tris and tri-pairs.

With the tri-pair you don't need to worry about generating any extra verts, as you will see later. With the single tri, you need to create an extra vert to extrude the back face into a peak of three faces. Getting the position of this is as easy as getting the tri centre and whacking it back a little bit in the normal direction (and i even gridsnapped it after that but dunno if that made a difference as those faces should get stripped away by bsp anyway).

Here is what it looks like once converted and loaded in Radiant:

http://i.imgur.com/fnGtCtn.jpg

Ignore the ugly blue crap - that was a misguided attempt at some sort of waterfall.

Notice there is a tri-pair here that is a single tet with 2 faces in the visible map, and also a single tri with just the one visible face:

http://i.imgur.com/YdiEMYC.jpg

Here is a view from the back, so you can see how the unseen faces are created:

http://i.imgur.com/qNJxZLK.png

Now you can just go ahead and compile the map. Sometimes you get leaks, and sometimes you don't. It's just luck, and has nothing to do with any mistakes in the pipeline up until now - your mesh can be completely watertight, but the bsp algorithm with still find some reason to do a shit.

If the map leaks, find the leak position, then go back to maya and move a vert or two in the affected area slightly - there's no science to this - just move them a bit in any direction, and then grid snap, export, generate map and compile. If it still leaks, go back to maya and repeat the procedure until it no longer leaks. It's just luck, but my investigations found a correlation between chance of leak and grid snap size, which led me to settle on grid 16.

Here is what it looks like in quake. Excuse the ugliness, but I just slapped some lights in there so i could see it. Again, also ignore the retarded waterfall:

http://i.imgur.com/7KFbqeb.jpg

http://i.imgur.com/ElcbLjN.jpg

I'll try to get some code out to you guys at some point. 

clown-vision version of the map, from the outside:

http://i.imgur.com/qluJllO.png 

clown-vision, lol

So that's basically how I had it working in my head. It's bizarre that you were randomly getting leaks though. When I build organic stuff out of tets, I never had any problems with random leaks. I was using grid of 16 as well for it, sometimes even going down to 8.

I'm assuming this was all done with aguirre's txqbsp? 

I never really got my head around the leaks issue - I think they mostly happend in hull 1 and 2, and when you think of how bsp has to expand the brushes, your shell of lovely tets in hull 0 is going to turn into a hideous mess in the higher hulls, and bsp has to deal with it (not very well it seems).

This was why I suggested earlier a theoretical (and much more awesome) approach could be to write a modified bsp compiler that can actually process meshes directly (along with normal brushes), totally avoiding the need to treat them as tets, and makes sure that hull 1 and 2 are nice "expansions" of the original mesh.

From one I understand of bsp - one of the first things it does is find all the unseen faces of a brush and strips them away right? Is it feasible to add in the faces from a mesh at this stage, and then proceed as normal? 

From one I understand of bsp - one of the first things it does is find all the unseen faces of a brush and strips them away right? Is it feasible to add in the faces from a mesh at this stage, and then proceed as normal?

I hope someone versed in QBSP lore will weigh in, it would be interesting to know.

That said, while that makes the most sense, I am trying to think of ways to get this kind of thing done prior to the compilation process.

I wonder if it might have been your editor doing that when it imported and then saved the map? Have you tried loading it up in Trenchbroom, selecting all the world brushes and running the Snap Vertices command on them? 

I wonder if it might have been your editor doing that when it imported and then saved the map? Have you tried loading it up in Trenchbroom, selecting all the world brushes and running the Snap Vertices command on them?

Do you mean "did brush verts that should be snapped get a little bit off grid in the .map file?" Because I can say that they definately didn't - when I wrote the .map file I specified the planes using the actual vertices of the triangle faces, so the plane it writes would be as mathematically close as it can be really. I think however bsp converts the planes from the "3-points" representation in the map file to a "distance from origin and normal" representation which of course introduces floating point errors that sadly I can do bugger all about. I think if the plane is orthogonal, then the distance / normal represenation should be error free, but with a non-ortho plane we're in Wild West territory once bsp has its way with it.