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!