logo enkisoftware
Independent game developer making AVOYD
en  fr

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.

Avoyd - an octree streaming bug leaves gaps between node tiles 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.

Avoyd - streaming acne, an early network performance problem 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.

2023
 › Optimising Voxel Meshes for Games Using Blender
 › Implementing a GPU Voxel Octree Path Tracer
 › Avoyd Release Streams and Minecraft Lit Materials
 › Avoyd Beta Stream
2022
 › Isometric Render of a Minecraft Map in Avoyd Voxel Editor
2021
 › Importing Minecraft maps in Avoyd Voxel Editor improved
2020
 › Runtime Compiled C++ Dear ImGui and DirectX11 Tutorial
2019
 › Boxes in Space: procedural generation of abstract worlds in Avoyd
 › Procedural python word generator: making user names out of 4 syllables
 › In-game building
 › Player-deployable turrets in Avoyd
2018
 › Avoyd Game Singleplayer and Coop Multiplayer Test
 › Voxel Editor Evolved
2017
 › Speeding up Runtime Compiled C++ compile times in MSVC with d2cgsummary
 › Multiplayers toxic last hit kill and how to heal it
 › Avoyd Editor Prototype
2016
 › Black triangles and Peter Highspot
 › Colour palettes and lighting
 › Concept art by Rebecca Michalak
2015
 › Internals of a lightweight task scheduler
 › Implementing a lightweight task scheduler
 › Feral Vector
 › Normal generation in the pixel shader
2014
 › Python Google App Engine debugging with PyCharm CE
 › Lighting voxel octrees and procedural texturing
 › Patterns and spheres
 › Python Google App Engine debugging with PyTools
 › Interview
 › Domain masking using Google App Engine
 › Octree streaming - part 4
 › Black triangles and nervous_testpilot
 › Presskit for Google App Engine
 › Octree streaming - part 3
 › Octree streaming - part 2
 ›› Octree streaming 
2013
 › LAN discovery with multiple adapters
 › Playing with material worlds
 › Developer Diary archive
 › Website redesign
 › First Person Editor
 › First Avoyd tech update video
 › Implementing a static website in Google App Engine
 › Multiplayer editing
 › First screenshots
 › Thoughts on gameplay modes
 › Back in 1999
2002
 › ECTS 2002
 › Avoyd Version 1.6.1 out
 › Avoyd Version 1.6 out
2001
 › Biting the bullet
 › Avoyd version 1.5 out
 › Monday Mayhem
 › Avoyd version 1.5 alpha 1 out
 › Avoyd version 1.4 out
 › ECTS 2001
 › Fun with Greek letters
 › Closer just a little closer
 › Back already
 › Artificial Humanity
 › Products and promises
 › Ecommerce
 › Explosions galore
 › Spring fixes
 › Open source and ports to other operating systems
 › Avoyd LAN Demo Version 1.1 is out
 › Thanks for the support
 › Avoyd LAN Demo Ready
 › Game Tech
 › Optimising Voxel Meshes for Games Using Blender
 › Implementing a GPU Voxel Octree Path Tracer
 › Importing Minecraft maps in Avoyd Voxel Editor improved
 › Runtime Compiled C++ Dear ImGui and DirectX11 Tutorial
 › Boxes in Space: procedural generation of abstract worlds in Avoyd
 › Procedural python word generator: making user names out of 4 syllables
 › Speeding up Runtime Compiled C++ compile times in MSVC with d2cgsummary
 › Internals of a lightweight task scheduler
 › Implementing a lightweight task scheduler
 › Normal generation in the pixel shader
 › Lighting voxel octrees and procedural texturing
 › Octree streaming - part 4
 › Octree streaming - part 3
 › Octree streaming - part 2
 ›› Octree streaming 
 › LAN discovery with multiple adapters
 › enkiTS
 › Internals of a lightweight task scheduler
 › Implementing a lightweight task scheduler
 › RCC++
 › Runtime Compiled C++ Dear ImGui and DirectX11 Tutorial
 › Speeding up Runtime Compiled C++ compile times in MSVC with d2cgsummary
 › Web Tech
 › Procedural python word generator: making user names out of 4 syllables
 › Python Google App Engine debugging with PyCharm CE
 › Python Google App Engine debugging with PyTools
 › Domain masking using Google App Engine
 › Presskit for Google App Engine
 › Implementing a static website in Google App Engine
 › Avoyd
 › Implementing a GPU Voxel Octree Path Tracer
 › Avoyd Release Streams and Minecraft Lit Materials
 › Avoyd Beta Stream
 › Isometric Render of a Minecraft Map in Avoyd Voxel Editor
 › Importing Minecraft maps in Avoyd Voxel Editor improved
 › Boxes in Space: procedural generation of abstract worlds in Avoyd
 › In-game building
 › Player-deployable turrets in Avoyd
 › Avoyd Game Singleplayer and Coop Multiplayer Test
 › Voxel Editor Evolved
 › Multiplayers toxic last hit kill and how to heal it
 › Avoyd Editor Prototype
 › Black triangles and Peter Highspot
 › Colour palettes and lighting
 › Concept art by Rebecca Michalak
 › Feral Vector
 › Patterns and spheres
 › Interview
 › Black triangles and nervous_testpilot
 › Playing with material worlds
 › Website redesign
 › First Person Editor
 › First Avoyd tech update video
 › Multiplayer editing
 › First screenshots
 › Thoughts on gameplay modes
 › Back in 1999
 › Avoyd 1999
 › Developer Diary archive
 › Back in 1999
 › ECTS 2002
 › Avoyd Version 1.6.1 out
 › Avoyd Version 1.6 out
 › Biting the bullet
 › Avoyd version 1.5 out
 › Monday Mayhem
 › Avoyd version 1.5 alpha 1 out
 › Avoyd version 1.4 out
 › ECTS 2001
 › Fun with Greek letters
 › Closer just a little closer
 › Back already
 › Artificial Humanity
 › Products and promises
 › Ecommerce
 › Explosions galore
 › Spring fixes
 › Open source and ports to other operating systems
 › Avoyd LAN Demo Version 1.1 is out
 › Thanks for the support
 › Avoyd LAN Demo Ready