Octree streaming

Doug Binks - 12 Jan 2014

The original Avoyd stored the internal voxel representation of its game world as a standard 3D array. At the time this provided a good trade off between performance and memory for the size of levels we required for a multiplayer PvP game with a fully modifiable environment. In the new version we wanted to increase the size of worlds we could handle, whilst maintaining large view distances.

Our second technology update video shows off how the voxel octree streaming gives rapid loading over the internet.

Many voxel-to-polygon style games handle this by dividing the world up into fixed sized volumes, often called chunks. This works well, and is a fairly simple evolution from a standard 3D array. Chunks can be streamed from disk and from the server to the client, so memory consumption and network bandwidth can be handled in a similar fashion, simplifying code. A drawback of this approach is that both clients and server either have the chunk data, or they don't - so a player typically sees geometry popping up around them as they travel. A good overview of some schemes can be found here but beware the conclusions, as the author compares a 579 line optimized interval tree with a 44 line naive octree.

Since Avoyd is a full six degrees of freedom game, the lack of symmetry can easily lead to players becoming lost. Distance shapes can aid with navigation, so implementing a form of level-of-detail (LOD) rendering was an important requirement. Octrees provide not only a fairly efficient storage container for spatial data, but we can naively use the structure to calculate LOD geometry. Implementation details can get fairly involved if you want a cache and memory allocation efficient structure, and implementing fast access iterators and ray casts involve some complexity, but the basics are fairly simple.

An octree is a tree structure which contains a set of data called nodes, where each node can have up to eight child nodes, and so on recursively. A node may have no child nodes, in which case it's known as a leaf node. Avoyd uses a regular octree where nodes have the same width, height and depth. If a given node is of size L^3, then its child nodes are of size (L/2)^3.

Figure 1: An off-by-one bug in the octree streaming ended up leaving gaps between node tiles.

Avoyd's octree streaming system works by sending portions of the octree to the client on demand, after seeding the top levels. The streamed data includes a special flag for nodes which have missing data below them. When the voxel to polygon geometry pipeline (which runs asynchronously on the CPU using a task system) encounters a missing node it adds it to a list of requests which are then ordered by distance from the player. Every frame the client checks this list and sends a given number to the server, ensuring that the total outstanding requests are kept within a certain threshold to help ensure bandwidth isn't eaten up by old requests. If the player moves, we want want to request data in the new area now rather than be forced to wait for old data to arrive due to limited bandwidth.

Since the renderer generates geometry using an LOD scheme which only traverses the octree to the depth required for the detail we want to render with at a given distance, the requests are LOD aware - the client won't ask for data it can't use. This is similar in principle to virtual texturing techniques. A request lists the entity ID it's for (Avoyd supports multiple worlds, and currently all entities such as the player avatars use octree voxel model), the position of the node and the node depth. Naturally these can be compressed in some fashion, but for now they're sent naively. The server then creates a new octree data set starting at the node of the request and parsing down, then serialises this to the network to send to the client.

The network and disk serialisation schemes are currently slightly different. Avoyd's octrees use a series of fixed sized blocks of data where all node pointers are actually indexes to the block and position within a block. These can thus be trivially serialised to disk, though I compress using the excellent LZ4 library. For network serialisation I don't send empty nodes, nor block indexes for the current block. Material Ids for leaves are also ordered together, as are material amounts (in Avoyd each voxel stores a given amount of material). This aids compression significantly, again using LZ4. More can be done to compress the data, but this works well enough for now.

Once some bugs had been fixed (see figure 1) early experiments showed that using a fixed depth traversal was inefficient. I was initially sending only octrees of only 5-6 deep nodes, and frequently these trees had few branches so were very small and inefficient to transmit given the overhead of requests and their return headers. I added code to count the approximate byte size of the tree and only stop once we'd hit a minimum threshold, which improved things greatly but left me with a problem I'll call streaming acne.

Figure 2: Streaming acne was an early network performance problem once the basic algorithm was working. Here the close pink/white blocks are missing nodes awaiting data from the server.

Streaming acne is where multiple small regions typically 2 voxels wide of the geometry have not yet been loaded. Found in complex regions, these are large numbers of disconnected missing nodes which can't be transmitted as one continuous tree. At first I thought about a scheme to compress the requests and returned data, but a quick hack fixed the problem - I simply prevent the streaming from sending the last few levels of the octree unless it can send them all, using a simple heuristic based on the approximate number of bytes. Although this results in a larger visible pop in the geometry appearing from the server, it reduces network overheads along with the client side CPU processing needed to generate the vertex data for rendering.

I'm really happy with the result. Not only can we now support large worlds with long view distances over the network, players can get into a game in a few seconds with no noticeable lag to other players when they join. Although the streaming is fairly visible for the first minute or two, playing on a networked client quickly becomes very similar to playing locally on the server.

previous

next

Octree streaming

Octree Streaming - part 2

previous

top

next

› Latest

› All

› Game Tech

› enkiTS

› RCC++

› Web Tech

› Avoyd

› Avoyd 1999

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2002