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!


  1. Webgl has its purpose, but I think Google Native Client will be the future of running advanced software on the web. No point in reinventing the paradigm.

  2. I've been very interested in the NaCl project, but it seems that the team has been pretty quiet and the project slow moving. (Maybe I just haven't been looking in the right places.) I think it's kind of a natural convergence point for a lot of the web technologies that we're seeing now, but I get the impression we've got a ways to go yet before it's ready for general use. WebGL is probably only a few months away from a first stable version (The Google guys guessed September in a recent talk). Plus, I question how things like compositing and whatnot will work with the native client, whereas WebGL is designed for that. Not to mention it's just plain fun to play with, limitations and all.

    In the end, I feel like WebGL is a worthwhile endeavor and will likely continue to evolve and thrive even after things like NaCl are stable since they target different areas. (Online gaming will probably skew more towards the native stuff for speed reasons, though.)

  3. Hey,

    Demo does not load in Chrome! :)

  4. Which version of Chrome? I can run it right now with the dev channel (6.0.472.11), and I've seen it run on the beta channels previously.

  5. Hi Toji,

    I am about to push to mozilla-central changes that enforce the requirements of generateMipmap() as per the OpenGL ES 2.0 spec.

    The problem is that it's now rejecting this demo. Could you check if you are actually making an illegal call to generateMipmap(), or if it's just that my code checking that has a bug?

    for the usual restrictions on generateMipmap().

  6. I'll check that out ASAP and let you know what I find. Thanks for the heads up!

  7. These changes have landed, should appear in tonight's build if not in yesterday's.

  8. After some further investigation I believe that I'm sending non-power-of-two textures into the generateMipmap function, which is obviously not allowed by OpenGL ES. So, yes, your code is just fine. I'll see what I can do about fixing the demo later (Quake2 likes funny texture sizes apparently. I may just switch off mipmapping for this demo.)

  9. Indeed, I have made the logging output more precise, and the reason why it's rejected is that it's non-power-of-two.

  10. Okay, I've just turned mipmapping off for now so the demo should run again.(Lightmaps are still filtered, since I know that it's a POT) Admittedly this isn't an optimal solution, but I really don't feel like doing the required resizing code in JS.

  11. It's a bit late to let you know at this point, but the sky texture is stored in the worldspawn entity of the map afaik.

  12. Hey Toji, just read your article as im looking at making a WebGL BSP tree for THREE.js, did you ever find out what format you thought might work best?

  13. This comment has been removed by the author.