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. 

I was going to suggest using the snap vertice command in TB. It sorted out some leaks on my WIP map (which was causing some crazy weirdness in both DirectQ and RMQ but not Fitzquake or GLpro)... 

The verts in my cavern map are definately grid-snapped - I can tell by opening up the map and looking at the plane coords (which are just the 3 points of the triangle face) 

It also split some invalid faces on my map. I'm not sure how it works, but it magic'd away all my problems. 

It works as if you were to move every vertex to the closest point where all coordinates are integers. When a vertex is moved like this, all incident faces are split into triangles like in the vertex editing mode. Afterwards, all faces are merged again. That's why it will also correct invalid faces of brushes.

I doubt that this is Kinn's problem though. I would suppose that it is related to imprecision when QBSP generates the vertices from the planes. Depending on how the planes are arranged (geometrically) and in which order they are used to cut other faces, the generated vertices can be off even if all plane points are integer.

TrenchBroom's snapping won't help in this case either. This is a problem inherent in how QBSP generates vertices from planes. 

Ah, right sorry. It's still weird to me that the vertices don't actually exist.