Procedural Compression

Procedural compression is simply storing a piece of geometry as a set of procedural parameters rather than as the final model. While this is not compression in the normal sense of the word, the effects are essentially the same, only with a vastly increased (even arbitrarily large) compression ratio.

The disc spooling bandwidth requirements are thus greatly reduced, allowing us to pack vastly more level geometry into a small percentage of that bandwidth. The trade-off is that artists have reduced flexibility in the models they can represent, since they are constrained to the possible output of the procedural algorithms.

We also trade some CPU resources, since the generation of geometry may require more CPU time than the standard spooling and decompressing of the raw data.

Are these trade-offs worth it? What are the ultimate benefits of using procedural models for level geometry?

To get some real-world numbers to answer this question, I wrote a procedural tree generator and measured how long it took to generate level geometry. (The code used to generate the table and figures shown here can be downloaded here.) I then compared my results to the theoretical peak spooling speeds of various game platforms. The results are summarized in Table 1.

The bandwidth figures shown in Table 1 are peak bandwidth; in reality, actual average bandwidth can be as little as half. Two factors influence these results. First, it's difficult to actually fully utilize the available bandwidth, as the data set tends to be loaded in chunks.

Second, seek-times play a significant role in actual bandwidth utilization. Layout of data on the disc can greatly affect these numbers by causing excessive seeking, especially when data spooling needs to be interweaved with audio spooling.

Hard drive figures are included in the table, too. On a PC, the level data is generally loaded onto the hard drive first, and hard drives generally have a much faster average read rate than optical drives. Unfortunately, we must code for a lowest possible common denominator on the PC. Not so on the PlayStation 3, with a default hard drive which can potentially be used to cache level data.

Note though that the transfer rate of the 2.5-inch drive used isn't astoundingly faster than the peak Blu-ray rate, so many of the same problems still apply even if the hard drive is used for caching. On the Xbox 360, the hard drive is optional, so we have to assume it's not there.

A typical broadband internet rate of 0.3MB per second is shown for comparison. Spooling level geometry over such a slow connection would be very limited. However, if the majority of the level content is procedural, it's quite possible to spool an arbitrarily large world of content over the internet. To a small extent, this is the driving idea behind Will Wright's game Spore.

The tree generator in the code samples is very simple and rather inefficient, using vertex lists rather than indexed vertices. However, it does perform a reasonable amount of computation to generate the model, calculating texture coordinates and vertex normals. No optimization efforts have been made with this code, so the figures given here can be viewed very much as the bottom end for procedural geometry generation, with a more efficient algorithm easily being twice as fast.

Looking at the figures for the Xbox 360, the DVD spooling figure is a maximum of 16MB per second. Again, this is a peak figure, with a sustainable average of perhaps 8MB per second (although standard compression would again bump this up to an effective >16MB per second). Utilizing one of the three CPU cores of the Xbox 360, we should easily be able to generate level geometry at a rate upwards of 300MB per second.

Procedural level geometry is an ideal use of a multi-core system, like the Xbox 360 or PlayStation 3. If the procedural generation is being used essentially as a spooling system, then the geometry generation can be run on a low priority thread, making very effective use of "spare" CPU cycles.