Friday, June 25, 2010

Quake 2 BSP - Quite possibly the worst format for WebGL ever

So, as hinted at by my last post lately I've been working on a Quake 2 map viewer for WebGL. I'm not as far along with it as I would have liked, but I've decided to stop developing it and move on to other formats/pursuits for various reasons that I'll get into in a bit. I'm sure the majority of you are here just to see the pretty demo, though, so without further ado:

Quake 2 BSP WebGL Demo

(Linkified because trying to scrunch the viewport into the blog would make it difficult to use.)

It's certainly not perfect, but hopefully you guys like it. I would be thrilled to see someone expand on what I've done here... oh wait.

So, let's talk about why I've decided to move on from this project. This bit is gonna get rather long and technical so feel free to ignore it if subjects like binary parsing and lightmap calculations make your eyes glaze over.

I was hoping to get several more features in there like visibility culling and collision detection in there but after a lot of reflection I just don't think it's worth it. Actually, a better place to start may be to look at why I chose to try this particular format in the first place.

I actually started out doing a Doom 3 map parser to compliment my MD5 loader, but quickly abandoned that after seeing how fragmented the levels were (some parts are loaded from the .proc, some from the .map, some need a bit of data from both...) Moving on from there I decided that I wanted to try loading a binary file, mostly because it's not the easiest thing to do in Javascript.

For those of you not familiar with how it works, parsing binary in Javascript means reading your file in as a string, calling 'str.charCodeAt()' and masking by 0xFF to get a particular "byte", and then doing the necessary logic to combine those individual bytes into integers, floats, etc. I wrapped the worst of it away in a simple library so it's not too difficult to use (though it's still a far cry from C/C++) but the theory behind it is painful at best. This is one area that I feel Javascript could really improve, and indeed there are already standards in the works. Let's hope they get here sooner rather than later. Anyway, I ended up being surprised at how well it ended up working in practice (Javascript continually amazes me by not grinding to a halt when I ask it to do strange things), but I can't really recommend this as the way to go for more serious projects. I think I'm going to do an entire post on that subject later.

So having decided to do a binary file I toyed with the idea of doing Quake 3 maps but shied away from that because I wasn't too keen on the idea of doing Bezier curve math at the time and it would require more in the way of effect shaders to get the right look. Quake 2 maps were (I thought) simpler and rendering would take nothing more than a simple lightmap pass, not to mention they were smaller. There was also an educational motivation to the choice: I've done Quake 3 loaders before (In C++), but I'd never worked with Quake 2 maps before so I wanted a chance to familiarize myself with them.

Well, in retrospect I'm still glad for the chance to get to know the format but I don't think I would work with them ever again. I'm sure that many of the design decisions that drove the format made sense back in '97 when hardware rendering was a novel idea, but in todays graphics scene there are some choices on display here that seem pretty ludicrous:

  • Texture coordinates aren't stored directly but are instead derived from the dot product of the vertex position and a texture "axis" plus some offset. I'm certain this is a byproduct of the software renderer, but that doesn't stop it from being a royal pain to work with.
  • Once calculated the Texture coordinates are give in terms of pixels, not the 0..1 scale that the hardware expects. This means that in order to correctly calculate the vertex data you must first pre-load every texture the map uses. That's fine for a local client, but is murder for a web browser that's trying to be nice and asynchronous.
  • To make things more interesting, the texture format is a proprietary one (.wal) It's a simple enough format, basic 8-bit indexed color, but not many tools are available to convert them to something more friendly like .png, so that just means more binary parsing for your script.
  • The lightmaps... oh the lightmaps. This is the straw that broke it for me. The lightmaps used by the map are stored as 24-bit images embedded into the bsp itself, tightly packed and with no individual lightmap being more than 16x16 in size. That's fine, but the bsp format doesn't store the dimensions of the individual maps, just the offset. So you have to calculate the dimensions yourself using some crazy algorithm that involves the minimum and maximum texture coordinates of a face. It's a very finicky process, and the Quake 2 source relies on some of the inherit properties of floats and ints to get it. We have no such luxury in javascript (all numbers are effectively large floats), and as a result I STILL haven't gotten it quite right. Or maybe I have. Minefield looks fine with it, Chrome screws up in certain places. Just goes to show how sensitive this calculation is.
  • Oh, and the lightmaps are all stored separately. One for each. And. Every. Face. So your options are to pack them all into a single texture or render one face per draw call and store several thousand teeny tiny textures. Guess which option I picked?
That's not even looking at things like visibility determination or collision detection. Plus there's several bits that I'm still not sure how to determine. For example: how do you figure out which texture to show for the skybox?

Now, all of these things are annoyances to be sure, but can be worked around. After all, one of the most successful games of all time was built around this format, it can't be THAT bad, right? The real problem here is that these issues make the format almost antagonistic towards a web environment. Yes, Google got it working, but even they mentioned how painful some aspects of the loading were.

So while I had fun putting together this demo I also don't plan to take it any further, simply because if I'm going to put any real effort into a format I want it to be one that can play to WebGL's strengths and not highlight it's weaknesses.

So now a question for the readers: What formats have you seen that WOULD work well in a browser environment and why? I have a few that I want to look at anyway but I'd be delighted to take some suggestions! In the meantime, I'm working on getting glMatrix to 1.0 (which for me means improving things like documentation and unit testing), so expect to see some updates in that area soon!