Saturday, August 8th, 2009
In 2001 the Vision 3D engine featured large outdoor environments supported by smooth and dynamically deformable terrain. The initial version of this engine was PC only,
but almost eight years later I decided to update the engine to run on mobile devices. At the start of this process I quickly realized that the terrain system
was both a storage and performance hog, and a number of features would need to be dropped.
The most significant cost to contend with was the file size of terrain maps and textures. These files were massive, as they supported very large open worlds with a high degree of detail. Optimizing this content for mobile meant sacrificing a number of features in order to significantly reduce the size of each terrain vertex.
The following table details the initial costs for each vertex:
|Position||12 bytes (3 floats)|
|Texture coordinates||12 bytes (2 floats for UV, 1 for blend weight)|
|Normal vector||12 bytes (3 floats)|
|Bi-tangent vector||12 bytes (3 floats)|
|Vertex index||2 bytes (1 ushort)|
In total, it would cost 50 bytes to store a single terrain vertex. On PC the goal was to reduce load time computation, so the normals, bi-tangents,
and indices were baked into the file rather than computed at runtime.
To make matters worse, terrain maps also consisted of up to 8 detail levels that helped improve rendering performance but increased file size by about 30%. As a result, Vision worlds on the PC were typically between 80 and 120 MB after zip compression, and would need to be reduced by more than an order of magnitude to be viable for mobile.
The first step was to remove support for bump mapping. This feature was simply too costly in terms of rendering performance for mobile hardware at the time,
and it was costing us 12 bytes per vertex.
Next I decided to remove the UV texture coordinates and derive them at runtime based on vertex position. The third texture coordinate, that defined the texture layer blending weight, would be replaced by a simple computation based on the vertex normal. This reduced control for the artists, but everyone on the team was comfortable with the tradeoff.
At this point the vertex storage cost was reduced from 50 bytes to 26 bytes, but this still pushed us far past our total asset budget of 10 MB.
Cutting to the Bone
Getting a bit more serious, the next step was to move vertex indices and normals out of the file and calculate them at load time. After profiling the engine I found
that this would shave an additional 14 bytes off the vertex cost with only a negligible increase in level load times.
I also implemented a new level of detail system that would be fast enough to run at load time, without having to store any additional detail layers in the file. This new system divided the terrain into tiles and constructed geometry levels only for inner vertices. This ensured that neighboring tiles that were rendered at different levels of detail would always stitch together seamlessly. The simplicity of this system, with its incredibly basic interpolation scheme, enabled us to optimize it heavily in code. Overall this system increased our rendering costs by around 3-5% (which we could spare), but decreased our file sizes by an additional 30%.
At this point we had reduced our per-vertex cost to 12 bytes for position, and completely removed any storage costs for geometric levels of detail. Unfortunately we were
still above budget, but were getting close to making ends meet. For the next refactoring pass I updated the terrain file header to include the total area of the terrain.
This, combined with the vertex count and an assumption of even spatial distribution, allowed us to remove the X and Z values from the position vector. At load time these values
were populated simply based on the order of the vertices in the file. This step would have been significantly trickier had we continued to store detail levels in the file,
as they would often contain non-uniformly distributed vertices. However, as we now computed the detail levels at runtime, we were free to decimate the vertex position.
By storing only a height value for position, we had now reached a cost of 4 bytes per vertex. This brought us within striking distance of our budget, but we were still slightly over. The final step was to reduce our height coordinate from a 4 byte float32, to a 2 byte float16. This format was advantageous because of its reduced size and also for its native support on most modern GPUs (and hopefully soon mobile GPUs as well).
Altogether, these changes reduced our vertex cost from 50 bytes down to 2 bytes, and brought our total asset cost for our game to a budget-reasonable 9.9 MB. These changes were mostly the result of catching low hanging fruit – inefficiencies in the terrain file format that were affordable on PC but not on mobile. On first glance the original design enabled greater control for artists and improved rendering performance, but upon deeper inspection we discovered that this flexibility simply wasn't worth the extreme cost in file storage.