The Concept of Patches

Central to the landscape system in the Avalanche Engine is the concept of "patches." A patch, in this context, is a two-dimensional spatial container of data.

The size of a patch is always a power of two in both dimensions, its position is always a multiple of its size, and it's aligned to the world axes. The actual content of the patch is what defines its type. We use many different patch types in the engine, such as: stream patches, terrain patches, vegetation patches, etc. Each of these patch types has their specific use and purpose.

We call a collection of N*N patches of the same type a patch map. Usually a patch map is centered on the camera; meaning that if the camera moves, some patches in the patch map has to be destroyed, some has to be created, while some could remain valid.

There can also be hierarchies of patch maps, which we call patch systems. A patch system is a collection of patch maps of the same type, and where each patch map contains the same number of patches, but at a power-of-two size difference between them. This structure is used to represent different levels-of-detail of the same data. We say that patches overlapping in such a hierarchy have a parent/child relation; even though there is no actual connection between them other than that they cover the same area.

Figure 1: A patch system with three levels of patch maps centered on the camera

A central patch manager handles this administration and organization of patches. The patch manager doesn't know the type of the patch; it only sees the patch header and a blob of unknown data. Registered callbacks then deal with the type-specific actions, such as creation and destruction of the patches. This abstraction lets us more easily optimize the core patch handling which is helpful since there can be thousands of various patches in flight at the same time. The patch manager also does other generic work like testing patches against the view frustum, and dealing with memory management.

Data Pipeline

In the Avalanche Engine we use our proprietary editor called JustEdit (clever name, right?) for creating terrain. We don't worry too much about data size at this stage, since we can assume developer workstations with a decent amount of RAM. Therefore we use a raw height map format and a fixed resolution proxy mesh for the terrain in JustEdit, although we vary the resolution based on distance on a per patch basis for performance reasons. The terrain data in JustEdit is split up into editor patches on disc, which can be individually checked in and out from Perforce, so that we can have multiple artists working on the world at the same time.

The created data is then sent through a terrain compiler that optimizes the data format for the specified platform and outputs it as stream patches. This is a quite time-consuming process if done for the entire world, so it's an area subject to constant improvement. For our newest generation of tools we're actually using GPGPU processes to achieve live editing of local areas.

Figure 2: The data pipeline

Streaming

In the Just Cause series, there are no restriction on player movement (other than speed), so we had to organize the runtime data on disk in such a way that it can be efficiently streamed-in, regardless of the direction the player is moving. To achieve this, we split up the entire world in a regular grid of 64 by 64 cells. The world size is 32 by 32 kilometers, thus each cell covers 512 by 512 meters. We call each cell a stream patch, and they contain all the terrain data required to render and physically represent that area. We keep a patch map of 8 by 8 stream patches in memory, centered on the camera.

We wanted to be able to stream the data directly from optical disc, so it was really important to keep the number of seeks required to read the data to a minimum. However, we were in quite good shape when it came to the available disc size and we took advantage of this by actually storing the stream patches twice, both in x/z order and in z/x order. This way only one seek was ever needed to bring in a new row or column of eight stream patches. The maximum speed of travel was then restricted by the data transfer rate of the optical drive.

We ended up capping the maximum allowed speed of movement in the game at 512 meters per second in the horizontal direction, allowing an average data size for each stream patch of about 128kb. I say "average" because the data size for each patch was not fixed. What mattered was how much data there would be in any arbitrary location of 8 by 8 stream patches combined. This allowed us to have occasional patches that contained more than the average amount data, provided that they were surrounded by patches that contain less than the average data size. A pass in the terrain compiler iterate over the world to ensure that the memory budgets holds for every possible position.

The major terrain data categories stored in each stream patch are:

• Terrain textures (materials and normal map)
• Height map and material map (compressed to 16 bit/sample)
• Terrain mesh data