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. 

Sock: if you want to represent your mesh using the verticies and not planes in the map file, then a new format will be needed. I think this is what the others are getting at.

Kinn: Adding func_group support right now. 

Now that I think about it, three point plane definitions... are triangles. *facepalm*

So it could look just like the current map format, although the semantics would be completely different inside a "func_mesh" entity.
I.e. a compiler that was not aware of the special meaning of func_mesh would barf due to the wierd structure of the "brushes" contained within. 

It would just create planes and then recompute the vertices from those, with all the errors inherent in that process.

An aware compiler would just skip this computation and take the vertices from the plane points. 

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

So this still requires us to create a collection of tetrahedron brushes (or whatever) to represent this "mesh"?

I suppose this would work if all the unseen faces of the "mesh" brushes are flagged with a special texture that tells the compiler to discard them immediately. Then, the compiler will have a proper mesh of just the visible faces as a starting point, equivalent to as if it had just loaded in, say, an external .ase mesh. 

So it could look just like the current map format, although the semantics would be completely different inside a "func_mesh" entity.
I.e. a compiler that was not aware of the special meaning of func_mesh would barf due to the wierd structure of the "brushes" contained within.

Sounds perfect, all the brushes would be contained within the entity definition inside of the map file. So it can safely be ignored by editors/compilers that do not understand.

So this still requires us to create a collection of tetrahedron brushes (or whatever) to represent this "mesh"?

This is where a stage 0 would be needed. A compiler would have to triangulate all surfaces and then convert all marked surfaces into a tetrahedron mesh and save it as a map file. All of the back faces should be marked with something like terrainskip.

Another solution is to create the terrain from brushes and mark all non-visible sides with the terrainskip that the compiler can get rid of later.

The ultimate benefit of this system would be that the terrain brushes are treated like detail, they can be solid/clip and can cast / receive shadows. 

An example work flow:

* create terrain brushes (rough shapes)
* Group brushes into a func_mesh entity
* Use Trenchbroom to vertex edit the brushes
* Mark all backside surfaces with terrainskip
* Change spawnflags to suit application (solid/shadows)
* Pre-compile the brushes into a special mesh (faster)
* Or create mesh at compiler runtime (slower)

It would be good to have a pre-compile stage of the terrain brushes as this will speed up the final compile of a map.

Also could we have a compiler feature that has AI clipping? Brush surfaces that can be included in the later clip hulls but are invisible normally. 

Please let me think about how this would best be supported in TrenchBroom. Preferably, the method of creating a mesh would be compatible to creating Quake 3 meshes, because that would make it easier for me to add Quake 3 support. 

Surely the benefit of meshes is that you use a dedicated tool like Maya to model them (which is designed specifically for this kind of work), and don't have to worry about buggering about with tetrahedrons and manually flagging backfaces to be culled and whatnot?