Tuesday, October 25, 2011

RAGE, MegaTexture, clipmapping

Recently, id software (of DOOM and Quake fame) released their highly anticipated new title named RAGE. I don't normally write game reviews on this blog, but since I wrote about this game before way back in 2008 – three ... years ... ago! – and because I played through the game I felt like writing some more about how its new "Tech 5" engine works. The game's release was a bit of a disaster on PC (lead developer John Carmack raged out on twitter) because both NVidia and ATI did not deliver promised updates to their video drivers in time, but hey, I play the PlayStation 3 version.

One of the most impressive aspects of the game are its visuals. The outdoor scenes were described as "a moving painting". And indeed, it does look painted, which has mostly to do with the artists that did the graphics. Aside from that, this game is known for the fact that the graphics show no repeating textures. Every location, every object and every little detail has a unique look. The terrain in the game world is composed from a single gigantic and highly detailed texture. This is very special as this is usually not the case with traditional texture mapping, and id software is probably the first to show this off in a game. (Note: RAGE is not their first game to use this technique; in 2007 Quake Wars: Enemy Territory used an earlier version of the same code).

Carmack uses a texture mapping technique in his rendering engine that he calls "mega textures" and "virtual textures". This is not just marketing hype first of all because Carmack is a geeky programmer and not a marketing guy, and secondly because it looks too good to be just marketing hype. I think I have a good impression now of how it works, it's something along these lines.

Traditionally if you want to texture map a cube, you'd have six faces of the cube and you would choose to texture it using six textures, one for each face. Or you could choose to have just one texture, and have it repeat. In games, if you wanted to texture map a large area, you would repeat the texture over and again. When you use a different texture for each face, not only will you be using up texture ids quickly, it will also cost performance. So what Carmack did since the beginning (already in Quake 1) was making a texture map like a sheet of paper, and wrapping it around an object. This way you get a fully textured model, with just one texture per model.

Terrain data is like a gaint object. Using geomipmapping you can have a single highly detailed mesh for the terrain, while still being able to render it efficiently and having level of detail (LOD) with respect to viewing distance. (NB. What is also possible is that they tricked the level of detail using multiple terrain maps, each with a little less detail, but this doesn't matter in respect to texturing the terrain).
To texture the terrain, a giant texture map with a resolution of something like 64000x64000 is used. It is impossible to load this texture into memory all at once, so it loads only tiles. Each tile is 4096x4096 pixels. For geometry that is further in the distance, a lower resolution texture is chosen (like mipmapping).
I don't know if RAGE employs this, but it is possible to do a dynamic in-between level of detail by blending the higher resolution texture with a lower res texture. My guess is that this would cost too much performance, but I really don't know.

Carmack mentions using tiles of 4096x4096 on the PS3. Note that the PS3 has five year old hardware by now, but also note that 4096x4096 is still a lot. For example, 1080p "full HD" is only a fraction of that.
Modern PCs have larger video memory than the PS3 so RAGE should look even better on PC, but there is a bandwidth problem with loading the data from disk that gets in the way, so not everything is sunshine on the PC.
4K by 4K amounts to 16 megapixels per texture. Take 24 bits per pixel and you're up to 48 megabytes of memory per texture. This may not sound like a lot of data, but it takes more than half a second to load 48 megabytes from a hard drive.
Now compare the 5 year old PS3 hardware to a modern PC, and notice how the PC has much more memory, much more graphics memory and much more processing power, but both are limited in maximum performance by the same speed of the hard drive.

To speed up loading times, textures are compressed. Compression has the disadvantage that it takes processing power to decompress the textures when they are loaded. You can choose to use hardware compression, in which case the GPU has to decompress the texture. The problem with this is that the GPU will be busy, while it already was busy doing renderings. Another thing is that there are better and faster compression codes available for CPU ... in RAGE, a CPU thread is used to decompress the texture data.

In addition to mega textures, Carmack uses a technique he calls "virtual textures". I guess it works like a demand paging system; whenever a texture is needed because it is going to be displayed on screen, it needs to be loaded into the video texture memory.
The texture may be loaded from a core memory buffer (cache), or from a memory mapped file (disk cache), or lastly from the source media, the BluRay DVD player. Of course, loading off DVD is slow and that's when you see "texture pop-in" artifacts.
This technique is also called texture streaming because it is constantly loading texture data as you move around and look around the world.

60 Hertz refresh rate
The game is promoted for its 60 Hz refresh rate. Many games use 30 Hz. Experienced gamers say they can easily tell the difference, as 60 Hz games feel a lot faster and snappier. Just try to remember Quake 3 Arena when it ran an yer ole 100 MHz 486, as opposed to Quake 3 Arena on modern hardware — the game is much more action packed now because everything reacts faster on a higher frame rate.
RAGE feels fast at times indeed. It is an achievement to write a game that leans so heavily on graphics and have a frame rate of 60 Hz. Where does all this speed come from? For one thing, RAGE doesn't do multi-texturing. Why would it, if all textured space looks unique anyway? All the graffiti on the walls have already been "burned in" by the artists. All that hard work was already done during preprocessing. Other things that are known to have been tricked are lighting and shadows. It's a game, as long as it looks good, it is good enough — no need to pull off compute-intensive raytracing-style mathematics for no apparent reason.

Carmack is a very good 3D graphics programmer but he sure did not come up with these ideas all by himself. He does do his homework very good, apparently.

In the legendary game DOOM he popularized the use of BSP trees to efficiently render indoor environments. Use of BSP trees in computer graphics had been researched for many years by then, but it was a research paper published in 1991 that first described how gain lots of performance by using the BSP trees to draw a scene in a (then) unusual way: from the front to the back.

The mega texturing technique sounds an awful lot, no, exactly like clipmapping, a technique thought up by SGI researchers and published in 1998 in their paper titled “The Clipmap: A Virtual Mipmap”. You can read the full paper here.
Another term for clipmapping is the use of cliptextures.

Surprisingly, the paper also mentions a frame rate of 60 Hz. The 60 Hz frame rate is tied to the hardware limits of a high end graphics machine from around 1998, which does make you wonder if modern hardware could pull this off at 30 Hz too.

Carmack is not a bad guy and he knows where he came from; every now and then id software release the source code to their old engines for the sake of teaching students how to create 3D game engines.

The Game
RAGE is a fun game, but I have the feeling that they tried to make a game more in the likes of Red Dead Redemption, and too bad for them, Rockstar beat them. Unlike RAGE, Red Dead is a truly open world game and it is very different from the shooter genre. RAGE is a good shooter when compared to Quake, but it's not as frantic as shooters like Crysis or Killzone.

Maybe id software should give a shot at going back to their underground roots and produce a fairly simple, but large enough game that is pure brute and blunt fun rather than working for ages on producing a Hollywood blockbuster type of game. Take the Super Turbo Turkey Puncher for example. That was cool, and not because it was a mini game. It was simple and it was fun, and I wish I had it as a separate game. It would be killer on iPhone, I'm sure.

Remember DOOM and how it would get your adrenaline pumping. Halls full of imps to slaughter. The clicking sound as you picked up the shotguns left behind by enemies was so addictive. The monsters would moan and howl in pain as you were gunning them down.
Trent Reznor of NIN once phrased it like this: “the we don't give a shit attitude, it really struck a chord”.

Sunday, October 23, 2011

Exceptional conditions: adding exceptions in standard C

An important aspect of programming is error handling. A program is running, all is well, and then ... oh no! All of a sudden a condition occurs that was not supposed to happen, or at least the programmer wished it would not happen. A program usually checks the most common errors and may retry, work around, or simply abort the operation depending on how hard to resolve this error is.

There are software error conditions and there are hardware errors. Hardware errors are represented by software error codes. There are different ways in which an error condition is given to an application when it comes to programming:
  • error return value from a function
  • library reports error: in standard C, check errno
  • UNIX signal received
  • an exception was thrown or raised
Easiest to understand and use is the first one; if the return value of a function has a certain value (error code), then it signifies an error and the application should act accordingly. The application programmer himself must choose what error codes to use for error conditions.

The second case describes how the standard C library reports errors; the library functions return zero on success and -1 on error. To get more information about what error occurred, examine the error code in errno. Note, errno is not a normal variable but a function that returns a thread-safe errno value. All errno values are predefined by the operating system. The errno values are (either translated or directly propagated) return codes from the operating system's system calls.

UNIX signals may be sent by the (UNIX) operating system to signify certain conditions. These conditions vary from SIGALRM (a timer expired) to hard errors like SIGSEGV (segment violation, which is illegal memory access) and SIGBUS (bus error). Signals are handled by the process itself, but the signal handler is run in a different context. This means that the normal program flow is interrupted and continues after the signal handler has finished executing. A signal can even interrupt a system call, after which the system call will report the errno value EINTR (system call was interrupted). Signal handlers may be hooked by the application, but an application can not define its own signal numbers. The signal numbers are predefined by the operating system.

Exceptions are exceptional conditions that may be thrown or raised. An application may catch an exception, in which it will resume operation at the point where it first tried to do the operation. Because it involves stack unwinding and jumping through code, exceptions generally require special language support. Moreover, exceptions generally have a specific syntax in the form of try { ... } catch(Exception) { ... } or try: ... except Exception: .... Exceptions are a key aspect of the Java and Python programming languages, in which it is common use to throw exceptions for error conditions. In C++ exceptions exist but it is more left to the programmer whether to use them extensively or stick with error codes. In Objective-C exceptions exist but they are not commonly used.

Exceptions do not exist in standard C, but I thought it would be fun to add them. How do you add a language feature that is completely absent from C? Well, you can emulate them. In fact, I stole this neat idea from Objective-C; in Objective-C the NSException is implemented using setjmp()/longjmp(). Without using any macros to define try and catch, I came up with the following:
if (!catchException(exception_number)) {
... try some code ...

throwException(exception_number, "descriptive message");

} else {
printf("caught exception! %s\n", caughtExceptionMsg());
In this code, catchException() really sets up a try block. What it does behind the screens is creating an Exception object containing a jmp_buf and pushing it onto an exception watching stack. The code that actually catches the Exception is really in throwException(), which examines the stack to see if we want to catch the thrown exception at all. When it finds the corresponding Exception object, it cleans up the stack and jumps back to the initial starting point of the try block. If the exception is not being caught, print a message about the uncaught exception and abort the program.
If the exception does not occur, you are left with an object on the exception watching stack, which is why you need to explicitly call endException() to clean up the stack. Other languages do this implicitly.

This way we have added exceptions to standard C. There is a huge caveat to using exceptions correctly: as your program is able to jump back and forth through large pieces of code, you have to be extra careful not to leak memory. You can't have everything, but if you have something like an AutoReleasePool then this may help a great deal.