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. 

I think it should be possible to have a mesh representation that qbsp can use, probably easiest and best if it ended up that those faces were like 'detail' faces as well and you put caulk brushes like Q3 behind it to block vis and seal the map. It would of course need an extension to the .map file format and cooperation of both the editor and qbsp.

I wonder if there's already something like this in quake 3 (not the spline stuff, but a general mesh)? I'm not familiar with the map format there.

Kinn: does qbsp from tyrutils do any better with this or do you get the same problems there? 

I'm not sure the full technical details, but in Q3, the compiler finds all the .ASE models used by misc_model entities and adds them to the .bsp itself. I'm not sure if the engine actually instances them from an index within the .bsp or if compiler actually converts them to world geometry.

Either way, it doesn't require much from the .map format, since as far as it is concerned, the model a normal entity. The editor just has to support displaying the .ASE supplied to the misc_model entity. 

that experiment is impressive! 

Ok, i did a test to see how TyrBsp coped. I noticed that TyrBsp doesn't support the -group switch, so I had to move all my terrain brushes to worldspawn. When I compiled it, it worked ok with no leaks :}

However, I then tried Bjp's bsp on the same map (after moving all func_group brushes to worldspawn), and that also compiled it with no leaks this time.

With the terrain in a func_group though, Bjp's bsp created a leak (yes, the -group switch was enabled). I can only think that this is to do with that changing the order at which the brushes get processed, and the fact that it is in a func_group isn't actually the problem here, in general (but i'd have to do more tests to confirm).

As a related question - Tyrann, do you plan to support func_group in future?

Vondur - cheers :} It was born out of my frustration with Radiant's crapness when trying to do simply trisoup "heightmap"-type terrain. The original plan was just to do heightmap stuff with tri prisms, but it soon became obvious that I may as well go the full wallop and do the tetrahedron thing for arbitrary meshes.

A little part of me still dies though whenever I look at it in game with r_drawflat 1 enabled. T_T...I wish there was a way of improving that mess. 

You don't need to have a special map format.

Stage 1: Load all brushes into map, group them together and make them a special brush entity like for example "func_mesh"

Stage 2: Add a spawnflag switch "solid" to the "func_mesh" entity. If the mapper does not want the mesh to be solid then create a simple brush mesh behind for collision and map leak testing and mark with a "skip" surface that the compiler understands.

Stage 3: Compiler takes "func_mesh" and treats the set of brushes as detail. If solid, add them directly into the Hull mesh. Make sure the light compiler understands the new entity "func_mesh" and casts shadows on itself and surrounding brushwork.

Stage 0: Allow the compiler to take brushes and validate and check the brushes before. make sure triangles, valid planes etc. Save this checked version in a map format ready for import later.

This pretty much describes the process for creating a misc_model mesh in Q3 using a compiler and light program like q3map2.