Wanton Hubris

So I decided to take a look at multithreading QBSP since I already set up LIGHT and VIS to do it. In looking at the code, it seems Carmack set it up to fork() the process twice instead of threading the hull building. I assume this is because QBSP uses a ton of global variables which makes threading a major hassle without a lot of code refactoring.

At any rate, this worked straight away on Mac OSX once I enabled that code path. What that means is that ToeTag’s QBSP will build all 3 hulls (small collision, large collision and drawing hulls) simultaneously instead of sequentially. It’s not a huge savings but, hey, it’s something right? It was getting nasty with my remix map which now takes upwards of 30 seconds to QBSP itself. That’s been cut down to about 17 seconds now so I’m happy!

I’ve been to the brink of hell and back and it doesn’t work yet. YET! I am determined, however.

Just to recap what’s been happening here - I’ve been trying to work out the code necessary to allow me to import triangle meshes into ToeTag and then have them successfully compiled into the map. What do I mean by a triangle mesh? For example:

Now, here is that mesh in ToeTag:

So, as you can see, ToeTag can import triangle meshes and use them just like regular brushes.

Now comes the hard part : now what?

Direct Insertion

What I tried first was to modify QBSP to read those triangle meshes from the MAP file and insert them into the BSP file directly. This proved very challenging due to QBSPs reliance on brush data being convex and sealed (meaning, no missing faces). I could get this sort of working but it was never 100% and there were huge problems with collision.

Decomposition

Then I thought that what I would do is figure out a way to break the mesh down into several convex brushes and write those brushes out to the MAP file to simulate the user actually creating them. This seemed nice because it was entirely within ToeTag and QBSP wouldn’t have to change at all.

I built a bunch of code including a routine that created secondary arrays showing me which triangles shared edges with other ones (my main idea was based around walking these edge connections to create convex chunks). This proved to be even more challenging because every time I thought of something I could almost immediately think of a mesh shape that would break it. No, this wouldn’t do either.

SKIP Faces

My latest idea was to extend the idea of SKIP brushes to individual faces. What this would entail would be having ToeTag take every triangle on the mesh and create an entire brush from it (like some of the OBJ utils have done in the past for Quake engines). It would then give the extra faces it created a texture name of SKIP and then QBSP could compile the BSP as normal but then throw away the SKIP faces before actually writing out the BSP.

While it’s somewhat easy to handle SKIP brushes, SKIP faces seems more challenging. I eventually got it to the point of being able to compile and remove the faces but the collision was never right as it was still relying on getting convex data fed to it. It was REALLY close though and was the best shot I had taken so far.

The trouble was the that resulting BSP, even though it had the SKIP faces removed, was so sliced up that it was killing VIS. I had a single room with 2 triangle arches in it and I was looking at a 60 second VIS. Not good. I rebuilt that same room using manually created brushes and VIS took less than a second. So this wasn’t going to fly.

So now what?

Well, now I’m back at the my Decomposition idea but with an entirely different algorithm in mind. It’s deceptively simple in my head so hopefully it will be equally simple to implement. It might work. But I won’t know until I try!

At the very least, I can say that this has been a real challenge for me and I hope that I’ve grown a little as a coder by going through it. The end is in sight. Whether than end entails me throwing in the towel or this idea working remains to be seen. Let’s hope for the latter!

I’ve spent the last week or so trying to convince QBSP to accept raw triangles. This has been challenging to say the least and what’s funny is that it -almost- works. Almost. The problem is that the triangles are not being added into the clipping hulls correctly so they don’t block players, weapon fire or monsters. They do, however, appear in the drawing hull and Quake happily draws them for me.

There are other problems as well like - if the triangle mesh I’m feeding isn’t convex, it doesn’t carve into the existing BSP correctly (convex meshes work fine).

It’s all very shaky and almost-working-y but I think I’m going to take a step back and take another crack at dissecting the mesh myself before saving out the MAP file. What I mean is that I’ll take the imported mesh and break it down into convex shapes and write those out individually to the MAP file.

To that end, I’ve spent the weekend solidifying my CSG and math routines to the point where I’d be tempted to call them “rock solid”. I can’t find any maps now that display artifacts when loaded so that’s a good sign. I would sometimes get stray polygons shooting off into infinity and stuff like that but that all seems to be fixed now and happily working.

I’ll post another update once I’ve had a chance to throw these new math routines at some mesh dissection concepts I have bumping around in my head.

I decided to try something out yesterday. I’m trying to figure out how to get an OBJ file to integrate with ToeTag in a seamless fashion. I had many ideas but then came up with the one that I felt was ideal : have QBSP simply insert those triangles directly into the resulting BSP! Why fool around with trying to create convex shapes from the OBJ file or extruding the polys backwards or other techniques that can get messy?

Well, because the QBSP code is horrifically complicated. Well maybe not for some people but for me, it is. I can’t make heads or tails out of what Carmack is doing in there. Global variables everywhere, obscure variable names, oddly structured function calls - ye gods. So that idea is dead. I thought that I was close at one point as I had it reading the triangles in and I was inserting them into the BSP but lots of stuff was breaking and they weren’t rendering and … well, just forget it.

I’m going to do a more traditional implementation of it now. ToeTag will read the triangulated mesh into the editor, break it down immediately into a set of brushes and then you can work with it freely.

I will offset the pain of this somewhat by implementing a feature that I will call “Quick Groups”. You’ll be able to select a set of brushes, hit CMD+G, and then those brushes will work as a group. If you double click on one, it will select all of the others in the quick group. Any imported triangle meshes will automatically go into their own quick group. Should work well enough I suppose although I really would have liked to have gotten the QBSP solution working. I guess that’ll have to wait until someone who speaks Carmack better than I do can take a look at it.