Super Frustums
Beating the Memory Constraints when Managing Very Large Terrains
by Borja Fdez. Gauna

1. Introduction

When managing access to very large terrain extensions it becomes absolutely necessary to tile the terrain so that it can be dynamically loaded/unloaded with a separate thread. That way, the memory size isn´t a limitation any more (it's only a limitation to the terrain that is intended to be rendered in every frame, not to the terrain that can be handled).

Some obvious approaches have been used, but, as far as we know, no approach has been proven to be as efficient as the one we will present here: the super frustum.

We'll discuss in this article three different techniques to decide which terrain zone should be loaded.

1.1. Algorithm evaluation

In order to decide if an algorithm is good or not we've chosen three criteria:

Adaptability to what we really need to be loaded (the view frustum): the better the loaded terrain zone adapts to the view frustum the less memory resources will be needed and the less data will have to be loaded from disk to memory.
Data transfers between disk and memory: for each configuration change, we'd like to transfer the least possible data. This is a very important thing because it will determine the overall speed of the loader thread.
The risk of desynchronizing the loading and the drawing processes. If the loading thread is slower than the movement of the camera, some cells might not be displayed though they could be inside the view frustum.

2. Algorithms

2.1 Rectangular matrix around the viewpoint.

This is the approach described by Renato Bruno Pajarola in "Access to large scale Terrain and Image Databases in Geoinformation Systems", and, as we will prove, it's the worst one in the terms we have described.

The approach is basically to keep loaded in memory all the cells that are less than sizeX in the X axis and sizeY in the Y axis from the cell the viewpoint is in.

Adaptability to the view frustum:
Very poor. It only considers the camera position, not the angles of it, so it implies lots of unused cells in memory.

Leads us to draw only the 15-25% of what is loaded.

Data transfers between disk and memory:
Very high. Every time the camera moves from one cell to another, Xsize or Ysize cells must be loaded.

Risk of desynchronizing the loading and the drawing processes:
Not very high if the load of each cell is fast enough to handle position changes (the camera orientation changes won't give us any problem).

2.2 Rectangular matrix containing the frustum projection on the y=0 plane.

This algorithm is really a variation of the previous one. The limits of the matrix are determined by the points (xmin,ymin) and (xmax,ymax), which are calculated from the cells containing the projections of the frustum's 3 points (although it has 8 points, it can be approximated with 3).

As a little improvement, security borders can be defined in both X and Y axis, to prevent the camera moving faster than the loader thread loads when turning the viewpoint.

Adaptability to the view frustum:
Medium. With no security margins, about 60% of what we have in memory is inside the view frustum.

Data transfers between disk and memory:
It's been reduced to half of what we had with the previous algorithm.

Risk of desynchronizing the loading and the drawing processes:
Higher than the previous one. Orientation changes could produce desynchronization if we don't use appropriate borders.

2.3 Super Frustum

This is in our opinion the optimum solution to the problem we are dealing with.

We will define a Super Frustum as a geometric entity that contains the frustum and that introduces some extra space that gives us an efficient way to pre-fetch terrain tiles.

A Super Frustum can be 2D (defined by a triangle that contains the frustum's 2d projection) or 3D (defined by a pyramid similar to the frustum that contains the 8-point defined view frustum).

This would be a 3D Super Frustum:

The 2D version is not as accurate as the 3D one (some care must be taken with vertical pitch angles) but needs less CPU work. Both can be interesting depending on the particular application.

In both cases, the Super Frustum can be fully parameterized depending on the system we are running on.

Adaptability to the view frustum:
Very high. We can achieve 85% use rates with enough security space.

Data transfers between disk and memory:
Low. It produces more configuration changes, but each one needs to load less cells, balancing the load/unload work

Risk of desynchronizing the loading and the drawing processes:
Low, because the load is very balanced, so every movement produces less loads/unloads.

Discuss this article in the forums

Date this article was posted to GameDev.net: 11/3/2003
(Note that this date does not necessarily correspond to the date the article was written)