Rocket and I have spent the past month improving the tedious, unintuitive parts of the Sector's Edge UI and exploring a new compelling, rewarding and unique progression system.

The changes in this blog post will be implemented in the Attachment Update, which will be available for testing in our next Public Beta Testing event.

Home

Currently the home screen contains a list of Steam news posts and a dark animated smokey background. While I think the background is cool, it's very gloomy and needs to be livened up:

We recently started working with artist Juan Moreno, who is creating artwork for each of our maps. We love his Ice Station piece and have decided to use it as the background on a brand new home screen, which is divided into the following categories:

• Player ID - shows what the player has achieved. This is customisable and is shown to enemies that they kill in-game
• Progression - reminds the player what they're working on and what's next
• Quick Play - simplifies the server selection process with an option to quickly jump in to a game
• Active Friends - this is a scrollable list of friends that are currently in game
• Party - this shows a list of party invites (if any) and a prompt to create a party
• News and Patch Notes - helps players stay up to date with what's new

Navigation

To increase screen space, I reduced the top navigation bar from 60px to 50px high and removed the 2nd navigation bar row (more details on where this disappeared to below). The social sidebar on the right has been collapsed into the social button (third from the right) as it was consuming horizontal space and clashed with some UI elements.

Now each page has the same amount of screen space as the only persistent element across each page is the top navigation bar.

When clicking the 'Customise' tab, the buttons on the navigation bar are replaced with the customisation buttons, and the breadcrumbs element appears on the left:

The breadcrumbs element displays the navigation tree that the player traversed to reach the current page. Players can then click on 'Home' or 'Loadout List' to go back to a previous page.

Player ID

Featured at the top of the new home page is what we call your Player ID. It's a customisable banner that represents the player and the things they have achieved while playing Sector's Edge.

The old Player ID shows your:

• Name (Vercidium)
• Title (Developer)
• Tag (Aegis Annihilator)
• Level (193)
• Character (Agaman Engineer)

The new Player ID has the following customisation options:

• Allegiance background (far left)
• A single title (below player name)
• Three Feature Slots (center)
• Weapon/character showcase (far right)
• Background style (applies to all elements)

The Tag below the player's Title in the old Player ID has been removed and in it's place Feature Slots have been added. This is where players can display what that they have achieved in game, such as:

• Player statistics (KDR, accuracy, time played, matches won, etc)
• Weapon statistics (grenade kills, rail gun headshots, LMG damage dealt, etc)
• Tasks

Tasks are a new feature that will be added in the Attachment Update. Each task has a unique name and icon that can be displayed in a Feature Slot on the Player ID. More information on Tasks can be found further in this blog post.

Title Selection

The old title/tags UI was overwhelming and difficult to navigate. To improve this, I added a search bar and grouped similar titles together. Hovering over a title will show a description on the left that describes how this title was unlocked, i.e. '100 Rocket Rifle kills'.

Titles that are grouped together will expand when clicking the dropdown arrow next to it, which allows the player to equip others variations of this title that they have unlocked:

The new Player ID customisation also explores backgrounds/styles in more detail:

• Once a player has unlocked a background - e.g. the Fluid background unlocks when reaching a few thousand kills with any weapon - they can then equip it with any combination of titles/showcase/feature slots.
• Players can now also customise the colour of the background effects using hue, saturation and lightness sliders.

Weapon Presets

A common feature request has been the ability to customise weapons differently in each loadout. To address this I implemented weapon presets, which allows players to create a combination of attachments, sights and skins that can be reused across multiple loadouts.

In the example below I am editing my 'Quiet + Removed Stock' preset and hovering over the 'Resonator' barrel attachment, which causes the attachment statistics panel on the left to appear.

The above UI is missing the weapon list from the old UI. This has been separated into a separate weapon list page (notice the breadcrumbs in the above screenshot).

The three tabs (Attachment, Sight and Appearance) refer to additional functionality that expands on the Attachment System from the last beta. If a player wishes to have the same red-dot crosshair style on each of their guns, they can create a red-dot Sight preset and then equip that on each of their weapons.

I'm using allegiance symbols to fill in the dead space and to integrate with the lore, allegiances and manufacturers of the weapons.

Loadouts

The loadout list has been extracted from a simple sidebar into a full-page list, which allows players to easily compare the contents of each loadout.

Crosshair Customisation

This update allows players to customise their crosshair and control what information should be shown around it.

Players can control the colour, opacity, size, radius and thickness of each element on their crosshair.

HUD Customisation

This feature has been requested for a long time and it's finally available! Players can customise these aspects of the  chat, killfeed, minimap and ammo UI:

• Horizontal and vertical edge (i.e. top-left, bottom-right, etc)
• Horizontal and vertical distance from the edge of the screen
• Max height of the chat and killfeed
• Height and width of the minimap

Scoreboard

The scoreboard has received a fresh coat of paint, with a feature that I've wanted for quite a while: a top-player showcase. The top player on each team will have a taller row on the scoreboard to showcase their Player ID.

Salvage Rework

I am planning to replace the canisters in the Salvage game mode with Soltrium meteors that fall from the sky and impact into the ground. You can see these meteors as they fall, so you can predict where they will impact.

Some will impact on the surface and some will inset into the ground a few blocks and leave a small crater. These meteors will be a small sphere of indestructible 'Soltrium rock' blocks (2 or 3 block radius).

Meteors will spawn in groups of 1 or 2 at ~4 minute intervals (will have to balance the interval based on how quickly these meteors end up being depleted).

Rather than simply standing near the meteor, players can place an 'extraction' device on a surface of a meteor block, similar to how C4 is placed.

• This device will extract one point for your team per 10 seconds
• You can destroy enemy extraction devices, but you have to run up to it and melee it. This is because I don't want orb spam to kill the devices
• You can only have one active extraction device at a time. If yours is destroyed, you can re-place it without needing to respawn
• Once an extraction device has depleted a meteor block, it will destroy the block and move itself to a nearby meteor block
• For example, if your team has 12 active extraction devices, your team will be earning 12 points per 10 seconds. 12 is the max since there's 12 people on each team - You will gain personal points each time your extraction device earns a point for your team

Planned benefits:

• Fighting is more spread out across the map, rather than clumped into one point
• Players have the ability to directly contribute to their team by placing their device on a meteor block
• Players have something tangible to defend

Clarifications:

• In maps like Magma Chamber and Crashed Freighter where canisters spawn under cover, the meteors will crash through the terrain until they reach the designated 'spawn point', meaning there will be a gaping hole in the ceiling.
• Players place their extraction devices by running up to an available meteor block face and pressing E
• Meteors will be visible on the minimap
• Friendly and enemy extraction devices will be visible on the minimap

Let me know your thoughts!

No Loading Screens

When a match finishes, players will no longer disconnect and re-connect to the server. Instead, players will be presented with these new screen when the match finishes.

During this time, players can vote for the next map + game mode and continue chatting + viewing stats while the server loads the next map in the background.

Once the map has loaded in, players will not be forced to join straight away. There will be a one minute grace period for players to continue browsing stats before they will be required to spawn in, else get kicked out of the server.

This new process means the server can balance teams based on the results of the previous match, and players no longer need to wait the 40 seconds at the start of the match while the server waits for people to join.

Players who wish to spend more time browsing stats are able to, and players who want less dead-time between matches can jump right in.

Team-based stats will show first, which provide a general overview of how each team performed.

On the Podium tab, you can click on each of the top 5 players to view their Player ID. If you don't land in the top 5, you can see your personal medals in the bottom-left.

On the Weapons tab, you can view your progression towards unlocking weapon Attachment Points and Titles. On the Tasks tab, you can view the progression you've made in Allegiance-specific Tasks.

Tasks

Each new Allegiance comes with 10 Tasks, which are composed of multiple criteria. By completing Tasks, players advance in their Allegiance standing and earn Allegiance-specific rewards:

• New weapons
• New characters
• New skins
• New attachments

For a long time players have been asking for rewards and unlocks that aren't Proton-based, and our goal with the Task + Allegiance system is to create a compelling, rewarding and unique progression system.

Once a player completes a Task, they can display it on their Player ID for all to see.

Each task has a unique icon and are colour-coded to their respective Allegiance. For example the three tasks below are associated with Soltec, Corahk and Irridyne:

Players can view their Allegiance progression and upcoming rewards on their full-page dashboard, accessed by clicking the icon in the top-left:

All mercenaries begin their journey as a Devoid, who pledge to no one but themselves and their personal gain. They are renegades, outlaws and mercenaries. They run the Arena on an undisclosed planet, where players compete to gain Soltrium for themselves. This alludes to questions like 'where is the Arena getting its Soltrium? Who shot down the freighter?'

More information on the 6 new Allegiances will be available soon.

Character Customisation

The character screen has also received an upgrade and allows you to customise more than just your character's skin, but we're not ready to share the details of this just yet...

Audio Raycasting

Verc has been working on combining 3D audio with raytracing to create accurate directional echo, reverb and occlusion effects. Check out the video description for the full details:

The Future

There is a lot more that I would like to pack into this post but I'd rather you experience it yourself when the beta is available.

We have been working closely with Juan Moreno over the past few weeks as we fell in love with his style. We'll share more of his works soon!

Punch Deck is working on 12 new underscoring tracks that will play in-game to build up the atmosphere that we're seeking to create. We also recently started working with poxlstudio, who is creating new SFX for the game:

And lastly, we recently partnered with Dusk Marketing, who will be helping to get this game out there and in the hands of more players. It's about time!

We hope you all have a great Christmas break and enjoy your time with your family and friends. Verc just started his two-week break from his day job and will be powering through his massive to-do list and have the beta ready in a few days.

Thank you all for support and patience, we hope we are building a game that you will love and enjoy and we can't wait to for you to experience the next few updates.

See you at the Sector's Edge!
- Verc and Rocket

This guide that explains how use the Battlefield 2042 Portal Rules Editor to:

• Infect random players 45 seconds after the match starts
• Change player teams on death
• Spawn zombies near humans
• Spawn resupply crates near humans
• End the match when all humans are dead
• Buff zombies over time

Part 1 - Team Management

When the match first starts, we want every player to be a human so they can run around and pick a position they want to defend. Then after 45 seconds elapses we'll infect random players in a loop until there's 8 humans left.

Note that TeamId 1 represents humans, and TeamId 2 represents zombies

When setting up the gamemode, we can't specify a team size of zero for the zombies team, so we need to manually move everyone over to the human team when they first deploy:

This has two conditions:

• The initial infection hasn't happened yet (i.e. there are no zombies)
• The player was placed on the zombies team (this will happen because the gamemode settings say 32v32)

Part 2 - Infecting Random Players

We can use the Wait action to delay this rule from occuring, so that players can run around for 45 seconds at the start of the match before they get infected.

The GetAliveHumans subroutine populates the AliveHumans and AliveHumanCount global variables and will be re-used throughout many of our rules.

In the rule below, we call GetAliveHumans and infect random players until GetAliveHumans is no longer greater than 8. We call GetAliveHumans at the end of the loop as we need to update our global variables after infecting a player.

Once this rule has executed we set InitialInfectionOccured to true so that our other rules can be aware of the fact that we're now in zombieland.

Part 3 - Zombification

This one is pretty simple - when a zombie kills a human, that human should be moved over to the other team.

Note there's a loophole here - if a human kills themself, they will remain a human. We counter that in Part 5

Part 4 - Input Restrictions

If zombies could shoot, the humans would have a tough time surviving. We need to stop zombies from being able to switch weapons, and also ensure they have no ammo just in case there's a glitch that allows them to switch to a gun.

Part 5 - Zombie Spawning

Criteria

This is a more complicated rule. When a zombie spawns we need to ensure:

• They aren't on top of an alive human
• They aren't super far away from all humans

In this rule we'll aim to spawn a zombie at a position where the minimum distance to an alive human is 50 meters, which we can achieve using this process:

• Get a random alive player's position
• Pick a random horizontal direction (random yaw, zero pitch)
• Multiply that direction by 50 meters
• Add that direction to the alive player's position
• Check if this final position is within 49.5 meters of an enemy. If so, we need to pick a new random position. If not, this is a valid spawn position

For example, in the diagram below there are 4 alive humans. The circles around the humans are the area that we should not spawn a zombie, as that's too close.

Player Variables

To start, we'll have this rule structure:

The Condition is present as this should only apply to players who spawn after the initial infection occurs. This rule uses two new player variables:

• Spawned - keep track of whether or not we have successfully spawned this zombie
• SpawnPosition - this will store the random spawn position we will generate

The Maths (or 'Math' for the Americans)

To get the position of a random player, we will use GetPlayerState and PlayerStateVector:

To get a random horizontal vector with length 50, we'll use RandomReal to generate a random number between -π and π (a full circle), then we convert this to a vector using DirectionFromAngles and Multiply it by 50:

Then we'll Add it to the random player's position and store it in the SpawnPosition player variable:

Now that we've generated this position, we need to ensure it's not within 50 meters of any other players:

We do this by looping over all alive humans, checking the distance between SpawnPosition and the human's position, and failing if the distance is less than 49.5:

Note that at the start this sets Spawned to true, then sets Spawned to false if the position is too close to an alive human.

This loop uses a Break operation because there's no point comparing SpawnPosition to humans #2, #3 and #4 if we already know this position is too close to human #1.

The super-long LessThan operator compares the DistanceBetween the alive human's position and the SpawnPosition player variable:

Note that this uses a new player variable called SpawnIndex to loop over the alive humans

The full rule is as follows:

Note that we set the TeamId of the player to 2, so that players who join the match after the initial infection occurs will become zombies, and so that humans who kill themselves will respawn as a zombie.

Part 6 - Resupply

The humans will be using up a lot of ammo defending themselves from these zombies, so every 2 minutes we'll resupply each human's ammo.

We use a while loop here so that the players will receive loadout crates until the match ends.

Part 7 - Winning

The humans win by lasting till the timer runs out, but the zombies can win by killing all alive humans:

To ensure this condition fires, we need to run the GetAliveHumans subroutine to update the global AliveHumanCount variable after every human dies:

We also need to run the subroutine if a human leaves the match:

Part 8 - Optional Buffs

To help balance your game mode you might want to buff zombies when they get a kill, or buff alive humans if a human dies. For example when a zombie kills a human, you can give the zombie +50 max health like so:

Note that we use Max(..., 150) because the default value for ZombieMaxHealth is 0

Another option is to increase zombie max health steadily over 20 minutes. We can do this using the TrackVariableOverTime and WaitUntil actions:

This sets the ZombieMaxHealth to the default value 100, then gradually increases it up to 300 over the next 1200 seconds (20 minutes).

Then in a While loop we:

• set the player's max health
• wait until ZombieMaxHealth - PlayerStateNumber.MaxHealth >= 1

The reason for the WaitUntil action is to avoid spam, as I'm guessing TrackVariableOverTime increases the ZombieMaxHealth value as a decimal value, rather than an integer.

Conclusion

That's all for this guide, if you have any further questions you can ask them in the #portal-builder channel on the Official Battlefield Discord server.

This guide explains how to use the Battlefield 2042 Portal Rule Editor to create new gamemodes and fun gimmicks.

This is a bit different from my usual posts but as some of you may know, Simon and I are huge Battlefield fans. I've been playing around with the Rules Editor for quite some time and created this guide to help you get started.

Last updated 13/11/2021 8:10pm AEDT

Overview

Types

Each Type icon represents a different kind of value:

There is some ambiguity around the 'Element' type, since some operations accept elements related to the player's inventory and some operations accept elements related to the player's soldier, for example:

To see which types are expected by each action and operation, right click it and click Help to view documentation:

Event Rules

The Portal supports a few different types of Events - such as 'On Game Mode Start', 'On Player Death' - which we can attach Actions to.

For example, this rule contains:

• A name - Zombify
• An event - OnPlayerDied
• An action - SetTeamId, which moves the dead player to Team 1

Ongoing Rules

Rules can also be Ongoing, for example this rule will kill a player that's on the ground.

Scope

Ongoing rules have a Scope - either Global, Player or Team - which affects which event payloads can be used within the rule:

Event Payloads

Event payloads - such as  EventPlayer and EventTeam - can only be used with their respective scope. For example, the EventPlayer payload cannot be used in the Global scope:

Variables

You can create variables that store:

• Numbers
• Text
• Players
• Vectors
• Arrays

Variables can be stored globally and accessed anywhere, or you can store variables on a specific player.

To start, click the Variables tab in the bottom-left, and then click Manage Variables at the top:

From here, click New Variable and then select the Player scope:

You can now combine this variable with the Add operation to increase a player's max health by 10 each time they get a kill:

Note that although this Rule doesn't specify the Player scope, we can use the EventPlayer payload here because the event is an OnPlayer... event

Arrays

Arrays are useful for creating collections of players. As an example, let's create an array that contains all players with less than 50 health.

First, we need to create a global variable that will contain these players:

Then, we'll create a subroutine, so we can re-use this code in many different Rules.

This subroutine will filter through all players and create an array of players who have less than 50 health. This array will then be stored in the WeakEnemies global variable.

Let's break it down:

• GetPlayers is an array that contains every player in the match
• The FilteredArray operation checks each player in the GetPlayers array, one at a time
• The CurrentArrayElement represents the single player that FilteredArray is currently checking
• The GetPlayerState block allows us to retrieve the Current Health of the single player that is currently being checked
• Finally, SetVariable stores the result of the FilteredArray operation into the WeakEnemies variable

We can then use this subroutine and variable like so:

Examples

Jump Damage

This Rule will deal 10 damage to all enemies when a player jumps

To start, let's create a subroutine that gets all enemies and stores them in a global array called Enemies:

We can then use the PlayerStateBool expression to check if the player is currently jumping, and if so deal 10 damage to all enemies:

However, this Rule will deal damage to all enemies while a player is jumping, but we want to deal damage when a player jumps. To do this, we'll need to add a new Player variable called Jumped, and set it to true after it deals damage to all enemies:

This will permanently set their Jumped variable to true when they first jump, so we need an extra statement that sets the Jumped variable back to false when they finish jumping:

Juggernaut Landing

This rule will deal 100 damage to all enemies near a player that lands on the ground

To start, we'll create:

• a new global variable called NearEnemies
• a new player variable called OnGround
• a new subroutine called GetNearbyEnemies, which gets all players that are within 3 blocks of the player.

Note that the above FilteredArray operation does not check Team IDs. This is because the expression was too long to get a high-resolution screenshot of, so this rule will damage friendlies as well.

Our rule will then use the new player OnGround variable to track whether a player has just landed on the ground after jumping:

Bonus Kill

Kill an extra random enemy when getting a kill

To start, we'll create:

• a new global variable called AliveEnemies
• a new subroutine called GetAliveEnemies, which gets all enemy players with greater than zero health

Then when a player lands a kill, we call the GetAliveEnemies subroutine to update the AliveEnemies global array, and then kill a random player from AliveEnemies:

Note that we use DealDamage rather than Kill, because DealDamage allows us to attribute this extra damage to the EventPlayer, which is done through the third parameter

Life Link

All players on one team will share the same health pool

This is a more complex one, as we need to:

• accumulate the total health of all players on a team
• divide the total health by the number of players on that team, so we know how much health each player should have
• damage all players on a team by a specific amount so that their health is the same

To start, we'll create these three global variables. TeamHealth would be a team-scoped variable but I don't think EventTeam is working yet.

Then we'll create two subroutines, since this task will require a decent amount of code and it's best to split it up:

To start, the GetTotalTeamHealths subroutine will:

• Reset the Team1Health global variable back to 0
• Loop over every player in the game
• Check if their TeamId is 1

Then, if their TeamId is 1, we need to add the health of this player to the Team1Health global variable:

We do this using the Add operator, which takes two parameters:

• The Team1Health global variable
• The CurrentHealth of the nth player in GetPlayers

The result is then stored back in the Team1Health global variable.

To distribute the total team health among all players, we first divide Team1Health by the number of players in Team 1 to determine how much health each team member should have. This means that Team1Health now holds the average player health, rather than the total team health.

Then we need to either heal or damage each player in Team 1 to ensure they have the same health value:

This assumes that a negative value sent to DealDamage will heal the player

The Subtract operation in the above picture contains these two values, where it will damage the player by the amount PlayerHealth - Team1Health:

For example if Player X has 80 health, and the value of Team1Health is 70, we need to deal 10 damage to Player X.

Lastly, to make this work for both teams, we'll duplicate the above code but instead use the Team2Health global variable with the TeamId 2:

Issues

Currently the EventTeam payload cannot be used. The documentation for it has this example:

Although the Rules Editor states that it's invalid:

Community

If you have some cool ideas or extra questions, head over to the Battlefield Discord server and chat with us in the #portal channel.

Special thanks to Dragory for answering everyone's questions regarding the Rules Editor, as well as for providing a great solution to the Jump Damage rule.

This is a continuation on the original article Particle Optimisations with OpenGL and Multithreading, which details the initial methods used in the particle system in our free to play first person shooter Sector's Edge.

This article details the changes in memory structure, algorithms and shaders that contributed to a performance increase in this particle system.

The source code for this particle system is available on GitHub.

Particle Storage Benchmarks

Particles were initially stored in multiple linked lists as it allowed particles to be added and removed quickly without worrying about array capacity. Based on feedback I received, I measured the time spent in ticks (10000 ticks = 1 millisecond) of adding new particles, accessing particle data and removing particles with different storage types.

Adding Particles

Class and Struct arrays were fastest here since they allow for particles to be pre-allocated and reset in-place, whereas Class and Struct lists were slower since they require allocating a new Particle instance each time.

In an attempt to improve the performance of adding to Class and Struct lists, I kept a separate list of 'disposed particles', which I would copy from rather than allocating a new particle each time. This increased the speed by about 2x, but as seen above it's still much slower than the other methods.

I believe adding to Class and Struct lists were slower than Linked List because of the function call overhead of List<T>.Add(...).

Accessing Particles

The above numbers were measured by accessing each particle in order, which allows for a realistic comparison between Linked Lists and the other methods. In Sector's Edge there isn't a use case for accessing a particle at an arbitrary index, so we don't need to benchmark random access.

Struct Arrays received a slight advantage since they can be accessed by reference with a fixed pointer, however Class List/Array were still slightly faster for reasons I'm unsure of.

Accessing Linked Lists was surprisingly the fastest, which I assume is because it requires no array bounds checks.

Removing Particles

Elements were removed from classes and lists using the swap and pop method, where the nth element is replaced with the last element and the array size is reduced by one.

Removing from Class and Struct lists was the slowest because of the function call overhead of List<T>.RemoveAt(...). Removing from a Struct list was by far the slowest since C# does not allow accessing List elements by reference, meaning the struct gets copied around in memory more than the other storage types.

I was surprised that Linked List did not have the fastest remove operations, since it requires only one operation:

// Remove from the linked list
particle.Next = particle.Next.Next;

// Remove from the struct array
array[n] = array[--arrayLength];

// Remove from the struct list
int removeIndex = list.Count - 1;
list[i] = list[removeIndex];
list.RemoveAt(removeIndex);

Class Array vs Struct Array

Based on the numbers below, I decided to switch to Struct Arrays since the access speed difference is negligible and Struct Arrays can be accessed with fixed pointers, which provides additional benefits in the Sector's Edge engine.

Struct Array Add is 13% faster
Class Array Access is 5% faster
Struct Array Remove is 10% faster

Particle Structure

Since structs are copied around a lot in memory, the size of a Particle needed to be trimmed down. The original Particle class was 152 bytes and had the following composition:

public class OldParticle
{
    public Matrix4F transform; // Matrix4F = struct of 16 floats
    public Vector3 position; // Vector3 = struct of 3 doubles
    public Vector3 velocity;
    public Vector3 rotation;
    public float scale;
    public uint colour;
    public float lifeTime;
    public Particle Next;
}

The new Particle struct is 60 bytes and copies ~2.5x faster than if it remained the same size:

public struct NewParticle
{
    public Vector3F position; // Vector3F = 3 floats
    public Vector3F velocity;
    public Vector3F rotation;
    public float scale;
    public uint colour;
    public int lifetime;
}

The transform variable was stored in the old particle system so that when the particle comes to rest, its transform no longer needed to be recalculated each frame. In the new particle system the percentage of a particle's lifetime where it is actually at rest is so small that it's no longer worth storing this variable in the Particle.

Previously the transform was updated in-place in the Particle and then copied to the mapped OpenGL buffer. In the new particle system we obtain a reference to the struct in shared GPU memory and write to it directly, saving the overhead of copying a Matrix4F struct:

// Obtain a direct reference to the Matrix4F struct in shared GPU memory
ref Matrix4F transform = ref mappedPtr[bufferOffset++];

// Update it directly
transform.M11 = ...
transform.M12 = ...

All Vector3 structs were changed to Vector3F structs to reduce memory usage and all particle-related math was changed from double to float. Double and float operations like addition and multiplication are identical in speed and the reduced precision is not visible to the human eye in-game.

Batch Particle Adds

Previously, the particle system worked with N linked lists, where N is the amount of threads supported by the CPU. This allowed each thread to work separately with its own linked list (note that variables prefixed with t_ are accessed by multiple threads):

Particle[] t_LinkedLists = new Particle[THREAD_COUNT];

Due to the nature of Linked Lists, particles could only be added to one list at a time. With struct arrays, we can now add an entire batch of particles to an array at once.

The particle storage now looks like this:

ParticleStruct[][] t_Particles  = new ParticleStruct[THREAD_COUNT][];

// This tracks how many particles have been added to each array
int[] t_ParticleCount = new int[THREAD_COUNT];

To add a new batch of particles, we must first check there is enough available space in the array:

protected void CheckParticleArraySize(ref Particle[] currentArray, int currentCount, int batchSize)
{
    // Early exit if already at max size
    if (currentCount == Constants.MaxParticlesPerThread)
        return;

    var currentCapacity = currentArray.Length;

    // Calculate the total amount of particles after we add this batch
    int newCount = currentCount + batchSize;

    // If the current array can't hold that many particles
    if (newCount >= currentCapacity)
    {
        // Either double the array size or increase it by 2048
        var newLength = Math.Min(newCount + 2048, newCount * 2);

        // There is no need to ever allocate more memory than the max amount of particles
        newLength = Math.Min(newLength, Constants.MaxParticlesPerThread);
                
        Array.Resize(ref currentArray, newLength);
    }
}

The entire batch of particles is then added to one thread's particle storage:

void AddABatchOfParticles()
{
    int batchSize = 6;

    // Select which thread to add these particles to
    var index = CurrentThreadAddIndex;
            
    // Get references to that thread's particle storage
    ref var currentArray = ref t_Particles[index];
    ref var currentAmount = ref t_ParticleCount[index];
    
    // Check we have enough room in the array to add this batch
    CheckParticleArraySize(ref currentArray, currentAmount, batchSize);
    
    // Add the particles
    for (int i = 0; i < batchSize; i++)
        AddParticle(ref currentArray, ref currentAmount, Vector3F.Zero, Vector3F.Zero, 0, 0, 0);
}

Adding Particles

The slowest part of the old AddParticle(...) function (source code) was that it had to move a Particle from the decayed particle list to the active particle list and then update it. If there were no decayed particles available, a new Particle had to be allocated.

The overhead of copying and allocating new Particles is avoided in the new particle system as it modifies existing memory using the Reset(...) function instead:

void AddParticle(ref Particle[] currentArray, ref int currentCount, in Vector3F position, in Vector3F velocity, in int lifetime, in float scaleMod, in uint colour)
{
	// If the current array exceeds the max amount of particles allowed, replace a random particle
    var index = currentCount > Constants.MaxParticles ? rand.Next(currentCount) : currentCount++;

    currentArray[index].Reset(
            position,
            velocity,
            lifetime,
            scaleMod,
            colour);
}

The Reset function simply sets each variable in the struct, which was faster than allocating a new struct, i.e. currentArray[index] = new Particle(...)

public void Reset(Vector3F p, Vector3F v, int l, float s, uint c)
{
    position = p;
    velocity = v;
    scale = s;
    colour = c;
    lifetime = l;
}

Updating Particles

After we update a particle (move it, rotate it, check collision with the map), we write its matrix transform directly to shared GPU memory with glMapBuffer. In the old system, this process was as follows:

• frame start
• map the particle buffer
• write to the buffer with multiple Tasks
• wait for all Tasks to finish
• unmap the buffer
• render the particles
• frame end

This meant that each frame there were two bottlenecks:

• waiting for all Tasks to finish
• waiting for the GPU driver to copy the new buffer data to the GPU before rendering

The new system avoids these bottlenecks with a slightly different process:

• frame start
• wait for all Tasks to finish*
• unmap the particle buffer*
• render the particles*
• orphan the buffer
• map the buffer
• write to the buffer with multiple Tasks
• frame end

Stages above that are marked with * do not occur on the very first frame since the particle buffer has not been written to yet.

There are two main differences with the new process:

• the particle buffer is orphaned before writing to it
• the Tasks can continue running once the frame ends, meaning it is likely that there will be little to no time spent waiting for the Tasks to finish when the next frame starts

The reason we orphan the particle buffer is to avoid sync points, which is where the CPU is waiting for the GPU to finish it's current work. This negatively impacts the performance of the game and should be avoided where possible.

A sync point can happen when the CPU attempts to modify a buffer immediately after requesting it to be rendered. An example of this is below, where the Gl.MapBuffer(...) call will wait until the above Gl.DrawArrays(...) function has been processed by the GPU before continuing:

Gl.BindBuffer(BufferTarget.ArrayBuffer, bufferHandle);

Gl.DrawArrays(PrimitiveType.TriangleStrip, 0, currentLength);

var ptr = Gl.MapBuffer(BufferTarget.ArrayBuffer, Gl.READ_WRITE); // SYNC POINT
// Write data to ptr...
Gl.UnmapBuffer(BufferTarget.ArrayBuffer);

Gl.BindBuffer(BufferTarget.ArrayBuffer, 0);

This sync point can be avoided with buffer orphaning, which is where calling Gl.BufferData after Gl.DrawArrays will tell the GPU driver to allocate a new region of memory for this buffer, while still retaining the old region of memory for the prior Gl.DrawArrays call.

We can now write to this new region of memory with Gl.MapBuffer(...) without creating a sync point. Both regions of memory are associated with this single buffer and once that Gl.DrawArrays call is processed by the GPU, the old region of memory is freed.

This is essentially double-buffering, but the GPU driver handles it for us.

The actual process of updating particles is the same as the old system, where the particle buffer is mapped and written to by multiple Tasks.

Trigonometry

The old particle system pre-calculated the sin wave and stored it in an array for faster lookup (source code).

At the time of writing this article, I decided to benchmark these systems again and it seems that optimisations in the .NET runtime mean that Math.Sin(...) is now the fastest method.

Here are the results of calculating 30 million sin and cos values:

Based on these measurements I have switched back to using the base Math.Sin(...) and Math.Cos(...) functions.

Particle Matrix

The old particle system worked with traditional 4x4 matrices, however the values M13, M14, M24, M34 and M44 were never used:

public static Matrix4F OldParticleMatrix(in float scale, in float rotationX, in float rotationZ, in Vector3 position)
{
    // Get the sin and cos values for the X and Z rotation amount
    GetSinAndCosCheap(rotationX, out float sinX, out float cosX);
    GetSinAndCosCheap(rotationZ, out float sinZ, out float cosZ);

    Matrix4F m = Matrix4F.Identity;

    m.M11 = scale * cosZ;
    m.M12 = scale * sinZ;

    m.M21 = -scale * cosX * sinZ;
    m.M22 = scale * cosX * cosZ;
    m.M23 = scale * sinX;

    m.M31 = scale * sinX * sinZ;
    m.M32 = -scale * sinX * cosZ;
    m.M33 = scale * cosX;

    m.M41 = (float)position.X;
    m.M42 = (float)position.Y;
    m.M43 = (float)position.Z;

    return m;
}

The new particle system uses a custom 3x4 Matrix, which stores the same values but without the unused variables.

float a = p.renderScale;

float sX = (float)Math.Sin(p.rotation.X);
float cX = (float)Math.Cos(p.rotation.X);
float sZ = (float)Math.Sin(p.rotation.Z);
float cZ = (float)Math.Cos(p.rotation.Z);

float acZ = a * cZ;
float acX = a * cX;
float asX = a * sX;

// Custom Matrix3x4 that uses less operations in the vertex shader
transform.M11 = acZ;
transform.M12 = -a * sZ;

transform.M13 = acX * sZ;
transform.M14 = acX * cZ;
transform.M21 = -asX;

transform.M22 = asX * sZ;
transform.M23 = acZ * sX;
transform.M24 = acX;

transform.M31 = p.position.X;
transform.M32 = p.position.Y;
transform.M33 = p.position.Z;

I then wrote the full Scale * RotationX * RotationZ * Translation * MVP matrix out on paper and asked my mathematician brother to simplify it down and remove any unnecessary additions and multiplications. This produced the following behemoth in the vertex shader, which improved the frames-per-second of rendering 50,000 particles from the low 130's to the high 140's on my laptop:

uniform mat4 mvp;

layout (location = 0) in vec4 aPosition;
layout (location = 1) in vec4 aColour;
layout (location = 2) in mat4 aTransform;

flat out vec4 colour;

void main()
{
    vec4 a0 = aTransform[0];
    vec4 a1 = aTransform[1];
    vec4 a2 = aTransform[2];

    vec4 b0 = mvp[0];
    vec4 b1 = mvp[1];
    vec4 b2 = mvp[2];
    vec4 b3 = mvp[3];

    vec3 v = aPosition.xyz;

    gl_Position = vec4((a0.x * b0.x)          * v.x + (a0.z * b0.x + a0.w * b1.x + a1.x * b2.x) * v.y + (a1.y * b0.x + a1.w * b2.x)               * v.z + (a2.x * b0.x + a2.z * b2.x + b3.x),
                  (a0.x * b0.y + a0.y * b1.y) * v.x + (a0.z * b0.y + a0.w * b1.y + a1.x * b2.y) * v.y + (a1.y * b0.y + a1.z * b1.y + a1.w * b2.y) * v.z + (a2.x * b0.y + a2.y * b1.y + a2.z * b2.y + b3.y),
                  (a0.x * b0.z + a0.y * b1.z) * v.x + (a0.z * b0.z + a0.w * b1.z + a1.x * b2.z) * v.y + (a1.y * b0.z + a1.z * b1.z + a1.w * b2.z) * v.z + (a2.x * b0.z + a2.y * b1.z + a2.z * b2.z + b3.z),
                  (a0.x * b0.w + a0.y * b1.w) * v.x + (a0.z * b0.w + a0.w * b1.w + a1.x * b2.w) * v.y + (a1.y * b0.w + a1.z * b1.w + a1.w * b2.w) * v.z + (a2.x * b0.w + a2.y * b1.w + a2.z * b2.w + b3.w));
    
    colour = aColour;

}

Particle Model

The old system used a particle cube model with 36 vertices (2 triangles on each face) which was rendered with GL_TRIANGLES.

The new system uses a cube model composed of 14 vertices rendered with GL_TRIANGLE_STRIP, which renders ~2x faster on the GPU than previously. However since each side of the cube now shares two vertices with another side, the normal values are interpolated incorrectly across multiple faces.

This was solved by using the flat out and flat in qualifiers in the vertex and fragment shaders and adjusting the order of normals in the triangle strip so that the provoking vertex is aligned correctly with each face of the cube.

When using flat-shading on output variables, only outputs from the provoking vertex are used; every fragment generated by that primitive gets its input from the output of the provoking vertex - Khronos

Conclusion

With the optimisations detailed in the above sections, the new particle system benefits from:

• reduced memory usage due to smaller structs and vertices
• faster particle creation with batch additions
• faster particle deletion with swap and pop
• faster rendering on the GPU due to less vertices, faster matrix operations
• less time waiting for Tasks to finish
• no OpenGL sync points

You can see the particle system in action in the launch trailer for Sector's Edge, which has now released free to play on Steam!

This article explains the optimisations made to the particle system in Sector's Edge that allow tens of thousands of particles to be ray-marched, buffered and rendered each frame.

Particles in Sector's Edge are small cubes that are created from explosions, block destruction, projectile trails, player damage, rain and other causes. The main features of the particle system are:

• Updating particles across multiple threads
• Ray-marching a voxel map
• Writing directly to GPU memory across multiple threads
• Fast matrix calculations
• Fast creation and destruction of particles

The full source code for this article is available here on GitHub.

Terminology

The following terms are referenced often throughout the article:

• Active Particle - a particle that is rendered and collides with the map
• Particle lifetime - how many milliseconds a particle will be visible for
• Particle decay - the process of a particle's lifetime reducing to zero over time
• Decayed Particle - a particle that has completely decayed and moved to temporary storage for later re-use

Particle Storage Structure

Each thread separately manages its own linked list of particles. As hundreds of particles are created and destroyed each frame, using a linked list allows this to happen quickly.

When a particle is created it is in the active state, meaning it should be rendered and collide with the map. Once a particle's lifetime reaches zero, it has decayed and is moved to a separate linked list. When creating a new active particle, we re-use a decayed particle. This puts less pressure on the C# garbage collector.

const int MAX_THREAD_COUNT = 128;

// For clarity, any variable that is used by multiple threads is prefixed with t_
int t_ActiveParticleCount = new int[MAX_THREAD_COUNT];
Particle[] t_ActiveParticles = new Particle[MAX_THREAD_COUNT];
Particle[] t_DecayedParticles = new Particle[MAX_THREAD_COUNT];

Note the first particle in each linked list will not be rendered and is only used for managing the linked list.

The particle class has the following structure:

public class Particle
{
    // Base particle values
    public Vector3 position;
    public Vector3 velocity;
    public Vector3 rotation;
    public float scale;
    public uint colour;
    
    // As an optimisation, the transform matrix can be precalculated and stored here
    // (explained in the Matrix section below)
    public Matrix4F transform;
    
    // When this value reaches 0, the particle has decayed
    public float lifeTime;

    // The linked list
    public Particle Next;

    public void AddNext(Particle p)
    {
        if (Next == null)
        {
            // Start the linked list
            Next = p;
        }
        else
        {
            // Insert the particle at the start of the linked list
            p.Next = Next;
            Next = p;
        }
    }

    // Remove the particle at the start of the linked list
    public void PopNext()
    {
        Next = Next.Next;
    }
}

We use the ThreadPool to determine how many threads are available and therefore how many linked lists we should use:

void GetThreadCount()
{
    ThreadPool.GetMinThreads(out int count, out _);
    THREAD_COUNT = count;
    THREAD_COUNT_MINUS_ONE = count - 1;
}

int THREAD_COUNT;
int THREAD_COUNT_MINUS_ONE;

Particles must be distributed evenly across all threads, so we use the CurrentThreadAddIndex variable to keep track of which linked list the next particle should be inserted into:

int _ctai;
public int CurrentThreadAddIndex
{
    get
    {
        if (_ctai == THREAD_COUNT_MINUS_ONE)
            _ctai = 0;
        else
            _ctai++;

        return _ctai;
    }
}

When creating a new particle we will attempt to re-use a decayed particle to save time allocating memory:

protected void AddParticle(in Vector3 position, in Vector3 velocity, in float scale, in uint colour, in float lifeTime)
{
    int index = CurrentThreadAddIndex;

    var p = t_DecayedParticles[index].Next;

    // If there are no decayed particles available, allocate a new one
    if (p == null)
    {
        p = new Particle()
        {
            position = position,
            velocity = velocity,
            scale = scale,
            colour = colour,
            lifeTime = lifeTime,
        };
    }
    else
    {
        // Modify an existing decayed particle
        p.position = position;
        p.velocity = velocity;
        p.scale = scale;
        p.colour = colour;
        p.lifeTime = lifeTime;

        // Remove the particle from the decayed linked list
        t_DecayedParticles[index].PopNext();

        // Disconnect the particle from the decayed linked list
        p.Next = null;
    }

    // Add the particle to the current active linked list
    t_ActiveParticles[index].AddNext(p);

    // Keep track of how many particles are in this active linked list
    // so that we can allocate the correct buffer size on the GPU
    t_ActiveParticleCount[index]++;
}

Calculating and Buffering Particle Data

Vertex Data

As all particles share the same cube shape, we can render them using instancing with OpenGL. The base particle vertex has the following structure:

byte PositionX;
byte PositionY;
byte PositionZ;
byte Normal;

Two instance buffers are also used to store the colour (uint) and transformation (mat4) of each particle. The particle's colour is determined when it is created, but its transformation must be recalculated each frame based on its position, rotation and scale.

Calculating Particle Transformations

To calculate the particle's transformation, we have to create a position, rotationX, rotationZ and scale matrix and combine them together. Multiplying four matrices together requires 192 multiplications and 144 additions, however by combining these matrices on paper we have created our own 'Particle Matrix' that requires less operations:

public static Matrix4F ParticleMatrix(in float scale, in float rotationX, in float rotationZ, in Vector3 position)
{
    // Access sin/cos values from an array rather than with Math.Sin(...)
    GetSinAndCosCheap(rotationX, out float sinX, out float cosX);
    GetSinAndCosCheap(rotationZ, out float sinZ, out float cosZ);

    Matrix4F m = Matrix4F.Identity;

    m.M11 = scale * cosZ;
    m.M12 = scale * sinZ;

    m.M21 = -scale * cosX * sinZ;
    m.M22 = scale * cosX * cosZ;
    m.M23 = scale * sinX;

    m.M31 = scale * sinX * sinZ;
    m.M32 = -scale * sinX * cosZ;
    m.M33 = scale * cosX;

    m.M41 = (float)position.X;
    m.M42 = (float)position.Y;
    m.M43 = (float)position.Z;

    return m;
}

This particle matrix requires 14 multiplications and runs 5.83x faster than the original matrix multiplications. The two methods were benchmarked by calculating the final transformation matrix for 524288 random scale, rotationX, rotationZ and position values:

Sin and Cos Precalculation

Accessing precalculated sine wave values from an array was found to be 2.07x faster than using Math.Sin(...):

// Decreasing this value will increase the accuracy of the precalculated sine wave
private const float epsilon = 0.001f;

private static float[] sinWave;

// Precalculate the sin wave
public static void InitialiseTrigonometry()
{
    int elements = (int)(Math.PI * 2 / epsilon) + 1;
    sinWave = new float[elements];

    int i = 0;
    for (double a = 0; a <= Math.PI * 2; a += epsilon)
    {
        sinWave[i] = (float)Math.Sin(a);
        i++;
    }
}

Both sine and cosine values can be accessed from this array. Cosine values are accessed from this array by shifting the array access to the right:

private const float minusHalfPI = (float)-Math.PI / 2;
private const float halfPI = (float)Math.PI / 2;
private const float doublePI = (float)Math.PI * 2;

// 1571 = PI / 2 / 0.0001
// 6283 = PI * 2 / 0.0001 (number of elements in the array)
public static void GetSinAndCosCheap(float t, out float sin, out float cos)
{
    if (t < minusHalfPI)
    {
        int access = (int)(-t % doublePI / epsilon);
        sin = -sinWave[access];
        cos = -sinWave[(access + 1571) % 6283];
    }
    else if (t < 0)
    {
        sin = -sinWave[(int)(-t % doublePI / epsilon)];
        cos = sinWave[(int)((t + halfPI) % doublePI / epsilon)];
    }
    else
    {
        int access = (int)(t % doublePI / epsilon);
        sin = sinWave[access];
        cos = sinWave[(access + 1571) % 6283];
    }
}

The two methods were benchmarked by calculating the sine and cosine values for 524288 random numbers in the range -50 to 50:

Buffering Particle Data

Every frame the uint and Matrix4F instance data must be buffered to the GPU for rendering. Originally, this data was stored in memory and sent to the GPU with glSubBufferData(...), however this was found to be 3.3x slower than writing directly to shared GPU memory with glMapBuffer(...). The difference in speed comes from the fact that the original method involved writing to memory twice:

• writing individual values to an array - which has inherit bounds checks
• copying the entire array to shared memory with glSubBufferData(...)

The new method involves getting a pointer to shared memory with glMapBuffer(...) and writing directly to that pointer. The pointer can be shared by multiple threads as they are each writing to a different section of GPU memory.

// Get pointers to both VBO's data
ParticleColourBuffer.Bind();
var cPtrBase = Gl.MapBuffer(BufferTarget.ArrayBuffer, BufferAccess.ReadWrite);
ParticleMatrixBuffer.Bind();
var mPtrBase = Gl.MapBuffer(BufferTarget.ArrayBuffer, BufferAccess.ReadWrite);

unsafe
{
    // Convert IntPtr to actual pointers
    uint* cPtr = (uint*)cPtrBase.ToPointer();
    Matrix4F* mPtr = (Matrix4F*)mPtrBase.ToPointer();

    // Example write
    cPtr[0] = 100;
    mPtr[3] = ModelHelper.ParticleMatrix(...);
}

// Finish writing to both VBO's
ParticleColourBuffer.Bind();
Gl.UnmapBuffer(BufferTarget.ArrayBuffer);
ParticleMatrixBuffer.Bind();
Gl.UnmapBuffer(BufferTarget.ArrayBuffer);

Updating Particles

Checking collision detection with the map, removing decayed particles and updating particle transformation matrices is handled across multiple threads with Tasks. As each thread is writing the colours and transformations of each particle directly to GPU memory, we need to first calculate the pointer offset for each thread.

void UpdateParticles(double elapsed)
{
    int[] pointerOffsets = new int[THREAD_COUNT];
    int particleCount = 0;

    // Calculate the VBO write offset for each thread
    for (int i = 0; i < THREAD_COUNT; i++)
    {
        pointerOffsets[i] = particleCount;
        particleCount += t_ActiveParticleCount[i];
    }

    if (particleCount == 0)
        return;

    // Check there is enough memory allocated for the VBO
    ParticleMatrixBuffer.Expand(particleCount);
    ParticleColourBuffer.Expand(particleCount);

    var tasks = new List<Task>();
    
    ParticleColourBuffer.Bind();
    var cPtrBase = Gl.MapBuffer(BufferTarget.ArrayBuffer, BufferAccess.ReadWrite);
    ParticleMatrixBuffer.Bind();
    var mPtrBase = Gl.MapBuffer(BufferTarget.ArrayBuffer, BufferAccess.ReadWrite);

    unsafe
    {
        uint* cPtr = (uint*)cPtrBase.ToPointer();
        Matrix4F* mPtr = (Matrix4F*)mPtrBase.ToPointer();

        for (int i = 0; i < THREAD_COUNT; i++)
        {
            if (t_ActiveParticles[i].Next != null)
            {
                int index = i;
                int pointerOffset = pointerOffsets[i];
                
                tasks.Add(Task.Run(() => UpdateParticleRange(cPtr, mPtr, index, pointerOffset, elapsed)));
            }
        }
    }

    ParticleColourBuffer.Bind();
    Gl.UnmapBuffer(BufferTarget.ArrayBuffer);
    ParticleMatrixBuffer.Bind();
    Gl.UnmapBuffer(BufferTarget.ArrayBuffer);

    // Wait for all particles to be updated
    Task.WaitAll(tasks.ToArray());
}

We use ray marching to handle particle collision with our voxel map. The voxel ray marching algorithm we use is based on this paper by John Amanatides and Andrew Woo and has been optimised by keeping block lookups within the current working chunk. This algorithm is quite detailed and is explained in our other blog post here.

The UpdateParticleRange(...) function has four stages:

• Precalculate common variables
• Handle decayed particles
• Update particles + ray-marching
• Write particle data to the GPU

The first stage is fairly straightforward and involves precalculating common variables and array accesses that will be used when updating each particle:

unsafe void UpdateParticleRange(uint* cPtr, Matrix4F* mPtr, int index, int bufferOffset, double elapsed)
{
    Particle p = t_ActiveParticles[index];
    Particle q = p.Next;
            
    // Precalculate variables
    double thisGravity = Constants.Gravity * elapsed;
    double scaleMultiplier = Math.Pow(0.9, elapsed / 16d);
    float elapsedF = (float)elapsed;
    float elapsed1500 = elapsedF / 1500;

    // Allocate variables
    bool hit = false;
    Axis axis = Axis.None;
            
    // Dereference array accesses
    ref int particleCount = ref t_ActiveParticleCount[index];
    var temporaryParticles = t_DecayedParticles[index];

    while (q != null)
    {
        // Update particles
        ...
    }
}

To show that a particle is decaying, it will shrink during the last 1.5s of its lifetime. Once it is virtually invisible, we will move it to the decayed linked list. As this particle was included in the total active particle count at the time we were calculating pointer offsets in UpdateParticles(...), we must write Matrix4F.Hidden to the instance buffer to prevent the particle from rendering using a transform value from the last frame.

unsafe void UpdateParticleRange(uint* cPtr, Matrix4F* mPtr, int index, int bufferOffset, double elapsed)
{
    // Part 1
    ...
    
    while (q != null)
    {
        bool shrinking = false;

        // Particles shrink during the last 1.5s of their lifetime
        if (q.lifeTime < 1500)
        {
            q.scale -= elapsed1500;

            // If the particle is virtually invisible, remove it
            if (q.scale < 0.03)
            {
                // Hide the particle
                mPtr[bufferOffset++] = Matrix4F.Hidden;

                // Remove the particle from the active linked list
                p.Next = q.Next;
                q.Next = null;

                // Add the particle to temporary storage
                temporaryParticles.AddNext(q);
                particleCount--;

                // Get the next active particle
                q = p.Next;
                continue;
            }

            shrinking = true;
        }

        // Handle active particles
        ...
    }
}

Handling active particles involves ray-marching the particle and updating its position, velocity, rotation and lifetime.

unsafe void UpdateParticleRange(uint* cPtr, Matrix4F* mPtr, int index, int bufferOffset, double elapsed)
{
    // Part 1
    ...
    
    while (q != null)
    {
        // Part 2
        ...
        
        var elapsedVelocity = q.velocity * elapsed;
        var mag = elapsedVelocity.Magnitude;

        // Only raymarch if the particle is moving
        if (mag > 0.000001)
            map.RayMarch(q.position, elapsedVelocity, mag, ref hit, ref axis);
        else
            hit = false;

        if (hit)
        {
            // Reflect and dampen the particle's velocity based on which axis it collided on
            q.velocity *= Constants.AxisToBounce[(int)axis];
        }
        else if (!map.NoBlock((int)q.position.X, (int)q.position.Y, (int)q.position.Z))
        {
            // Slide to a stop along the ground
            q.velocity.X *= Constants.ParticleSlideDampening;
            q.velocity.Z *= Constants.ParticleSlideDampening;
        }
        else
        {
            q.velocity.Y += thisGravity;
        }

        // Recalculate elapsedVelocity
        elapsedVelocity = q.velocity * elapsed;

        q.rotation -= elapsedVelocity;
        q.lifeTime -= elapsedF;
        
        // Part 4
        ...
    }
}

As an optimisation, particle transformations are only calculated if the particle is shrinking or moving. Quite often particles are at rest on the ground before shrinking, so this optimisation saves us some time.

unsafe void UpdateParticleRange(uint* cPtr, Matrix4F* mPtr, int index, int bufferOffset, double elapsed)
{
    // Part 1
    ...
    
    while (q != null)
    {
        // Part 2 + 3
        ...
        
        // Only update the transform if the particle is shrinking or moving
        if (shrinking || elapsedVelocity.Magnitude > 0.000001)
        {
            q.position += elapsedVelocity;
            q.transform = ModelHelper.ParticleMatrix(q.scale, (float)q.rotation.X, (float)q.rotation.Z, q.position);
        }

        // Write the colour and transformation matrix directly to shared memory
        cPtr[bufferOffset] = q.colour;
        mPtr[bufferOffset++] = q.transform;

        // Advance the linked list
        q = q.Next;
        p = p.Next;
    }
}

Rendering Particles

Since all data has now been buffered to the GPU, rendering particles is quite straightforward:

protected void RenderParticles()
{
    // Each particle VBO and instance VBO shares the same VAO
    // Bind the VAO
    Gl.BindVertexArray(ParticleMatrixBuffer.arrayHandle);

    // Draw the particles
    Gl.DrawArraysInstanced(PrimitiveType.Triangles, 0, 36, TotalParticleCount());

    // Unbind the VAO
    Gl.BindVertexArray(0);
}

The vertex shader is as follows:

#version 330

uniform mat4 mvp;

layout (location = 0) in vec4 aPosition;
layout (location = 1) in vec4 aColour;
layout (location = 2) in mat4 aTransform;

flat out vec4 colour;

void main()
{
    gl_Position = mvp * aTransform * vec4(aPosition.xyz, 1.0);

    colour = aColour;

    int normal = int(aPosition.w);
	
    // Slightly darken the sides of the particle
    if (normal > 3)
        colour *= 0.8;
    else if (normal > 1)
        colour *= 0.9;
}

In this case, the normal is an index that represents the Y+, Y-, X+, X-, Z+ and Z- unit vectors. For advanced lighting, the vec3 normal can be determined using either branching or an array access, however const vec3 arrays have poor performance on some GPUs.

int n = int(aPosition.w);
vec3 normal;

// Option 1 - branching
if (n == 0)
    normal = vec3(0, 1, 0);
else if (n == 1)
    normal = vec3(0, -1, 0);
else if (n == 2)
    normal = vec3(1, 0, 0);
else if (n == 3)
    normal = vec3(-1, 0, 0);
else if (n == 4)
    normal = vec3(0, 0, 1);
else
    normal = vec3(0, 0, -1);
   
// Option 2 - array access
const vec3 NORMALS = ( vec3(0,1,0), vec3(0,-1,0), vec3(1,0,0), vec3(-1,0,0), vec3(0,0,1), vec3(0,0,-1) );
normal = NORMALS[n];

// Rotate the normal
vec3 normal = normalize(mat3(transpose(inverse(aTransform))) * N);

The fragment shader then writes the particle colour to the framebuffer:

#version 330

out vec4 gColor;

flat in vec4 colour;

void main()
{
    gColor = colour;
}

In Practice

On a Ryzen 5 1600 CPU and GTX 960 GPU, the game can handle 33,000 particles before dropping below 60FPS.

The full source code for this article is available here on GitHub.

Every update to the game comes with many hours of testing between my brother and I to check for visual artifacts, bugs and crashes. You can see the particle system in action in our Developer Highlights video below, as well as lots of headshots and lucky shots!

This article explains how we optimised the ray marching algorithm in Sector's Edge that handles collision detection for tens of thousands of particles.

The full source code for this article is available here on GitHub.

Overview

The voxel world is divided into groups of 32 x 32 x 32 blocks, each of which are managed by a separate Chunk class instance. This structure is especially useful for:

• Rendering optimisations, as chunks outside the current viewport can be skipped
• Fast mesh regeneration when blocks in a chunk are changed
• Memory optimisations, as chunks that contain no blocks are left uninitialised

This voxel ray marching algorithm is based on A Fast Voxel Traversal Algorithm for Ray Tracing by John Amanatides and Andrew Woo and has been optimised by keeping block lookups within the current working chunk. As this algorithm is quite long, we will analyse it in sections.

Map Structure

Chunks are stored in a three-dimensional array within the Map class, however Blocks are stored in a one-dimensional array in the Chunk for fast lookup:

public class Map
{
    Chunk[,,] chunks;
}

public class Chunk
{
    const int CHUNK_SIZE = 32;
    const int CHUNK_SIZE_SQUARED = 1024;
    const int CHUNK_SIZE_CUBED = 32768;
    Block[] data = new Block[CHUNK_SIZE_CUBED];
}

public struct Block
{
    byte kind;  // e.g. empty, dirt, metal, etc.
}

Blocks within the Chunk are accessed as follows:

int access = j + i * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;
Block b = data[access];

For clarity, i, j and k refer to chunk-relative positions (range 0-31)
and x, y and z refer to map-relative positions (range 0-511)

Ray Marching

The problem with the original ray marching algorithm in Sector's Edge was that it worked with map-relative positions. This meant that every time the algorithm checked if a block existed at a specific position, it had to calculate which chunk the block belonged to and then convert the map-relative position to a chunk-relative position:

const int SHIFT = 5;
const int MASK = 0x1f;
public Block GetBlock(int x, int y, int z)
{
    // Get the chunk the block belongs to
    var c = chunks[x >> SHIFT, y >> SHIFT, z >> SHIFT];

    if (c == null)
        return true;

    // Bitmask to get the chunk-relative position
    return c.data[(y & MASK) +
                  (x & MASK) * CHUNK_SIZE +
                  (z & MASK) * CHUNK_SIZE_SQUARED];
}

The new algorithm obtains a reference to the chunk at the beginning of the function and only updates it when the ray enters a new chunk. This chunk is referred to as the current working chunk.

The second optimisation was to add two exit checks at the beginning of the function that check if the ray starts outside the map, or if the ray begins and ends at the same map-relative position:

• Exit if the ray starts outside the map bounds as there are no blocks to collide with. There will never be a case where the ray starts outside the map and travels towards the centre of the map
• Exit if the start and end position of the ray both lie on the same coordinate on the voxel grid. This check saves a lot of time for particles, as they are often at rest on the top of a block

The RayMarch(...) function parameters are as follows:

• in Vector3 start - the start position of the ray
• Vector3 velocity - the direction of the ray
• in double max - the maximum length that the ray can travel
• ref bool hit - set to true if the ray collides with a solid block
• ref Axis axis - set to either Axis.X, Axis.Y or Axis.Z depending on which block face the ray hit

public void RayMarch(in Vector3 start, Vector3 velocity, in double max, ref bool hit, ref Axis axis)
{
    // Convert the start position to integer voxel coordinates
    int x = (int)start.X;
    int y = (int)start.Y;
    int z = (int)start.Z;

    // If the start coordinate is outside the map, there is nothing to hit.
    if (y < 0 || y >= Constants.MAP_SIZE_Y ||
        x < 0 || x >= Constants.MAP_SIZE_X ||
        z < 0 || z >= Constants.MAP_SIZE_Z)
    {
        hit = false;
        return;
    }
    
    // Determine the index of the current working chunk in the Map by
    // bit-shifting the map-relative block coordinates
    int chunkIndexX = x >> 5;
    int chunkIndexY = y >> 5;
    int chunkIndexZ = z >> 5;

    // Get a reference to the current working chunk
    var c = chunks[chunkIndexX, chunkIndexY, chunkIndexZ];

    // Determine the chunk-relative position of the ray with a bit-mask
    int i = x & 0x1f;
    int j = y & 0x1f;
    int k = z & 0x1f;

    // Calculate the access position of this block in the Chunk's data[] array
    int access = j + i * Constants.CHUNK_SIZE + k * Constants.CHUNK_SIZE_SQUARED;

    // Calculate the end position of the ray
    var end = start + velocity;

    // If the start and end positions of the ray both lie on the same coordinate on the voxel grid
    if (x == (int)end.X && y == (int)end.Y && z == (int)end.Z)
    {
        // The chunk is null if it contains no blocks
        if (c == null)
        {
            hit = false;
        }

        // If the block is empty
        else if (c.data[access].kind == 0)
        {
            hit = false;
        }

        // Else the ray begins and ends within the same non-empty block
        else
        {
            hit = true;
        }
        
        return;
    }
    
    ...
}

After this stage we can confirm that the ray will start and end at different voxel coordinates and therefore a ray march is required. To improve ray marching efficiency, we pre-calculate the following variables:

// These variables are used to determine whether the ray has left the current working chunk.
//  For example when travelling in the negative Y direction,
//  if j == -1 then we have left the current working chunk
int iComparison, jComparison, kComparison;

// When leaving the current working chunk, the chunk-relative position must be reset.
//  For example when travelling in the negative Y direction,
//  j should be reset to CHUNK_SIZE - 1 when entering the new current working chunk
int iReset, jReset, kReset;

// When leaving the current working chunk, the access variable must also be updated.
//  These values store how much to add or subtract from the access, depending on
//  the direction of the ray:
int xAccessReset, yAccessReset, zAccessReset;

// The amount to increase i, j and k in each axis (either 1 or -1)
int iStep, jStep, kStep;

// When incrementing j, the chunk access is simply increased by 1
// When incrementing i, the chunk access is increased by 32 (CHUNK_SIZE)
// When incrementing k, the chunk access is increased by 1024 (CHUNK_SIZE_SQUARED)
// These variables store whether to increase or decrease by the above amounts
int xAccessIncrement, zAccessIncrement;

// The distance to the closest voxel boundary in map units
double xDist, yDist, zDist;

if (velocity.Y > 0)
{
    jStep = 1;
    jComparison = Constants.CHUNK_SIZE;
    jReset = 0;
    yAccessReset = -Constants.CHUNK_SIZE;
    yDist = (y - start.Y + 1);
}
else
{
    jStep = -1;
    jComparison = -1;
    jReset = Constants.CHUNK_SIZE - 1;
    yAccessReset = Constants.CHUNK_SIZE;
    yDist = (start.Y - y);
}

// Same for velocity.X and velocity.Z
...

// This variable stores the current progress throughout the ray march
double t = 0.0;

velocity.Normalize();
double xInverted = Math.Abs(1 / velocity.X);
double yInverted = Math.Abs(1 / velocity.Y);
double zInverted = Math.Abs(1 / velocity.Z);

// Determine the distance to the closest voxel boundary in units of t
//  - These values indicate how far we have to travel along the ray to reach the next voxel
//  - If any component of the direction is perpendicular to an axis, the distance is double.PositiveInfinity
double xDistance = velocity.X == 0 ? double.PositiveInfinity : xInverted * xDist;
double yDistance = velocity.Y == 0 ? double.PositiveInfinity : yInverted * yDist;
double zDistance = velocity.Z == 0 ? double.PositiveInfinity : zInverted * zDist;

The algorithm then runs in a loop until either:

• t has reached the max length of the ray
• a non-empty block is found
• the ray exits the map

while (t <= max)
{
    // Exit when we find a non-empty block
    if (c != null && c.data[access].kind != 0)
    {
        hit = true;
        return;
    }
    
    // Determine the closest voxel boundary
    if (yDistance < xDistance)
    {
        if (yDistance < zDistance)
        {
            // Advance to the closest voxel boundary in the Y direction
            
            // Increment the chunk-relative position and the block access position
            j += jStep;
            access += jStep;

            // Check if we have exited the current working chunk.
            // This means that j is either -1 or 32
            if (j == jComparison)
            {
                // If moving in the positive direction, reset j to 0.
                // If moving in the negative Y direction, reset j to 31
                j = jReset;
                
                // Reset the chunk access
                access += yAccessReset;

                // Calculate the new chunk index
                chunkIndexY += jStep;

                // If the new chunk is outside the map, exit
                if (chunkIndexY < 0 || chunkIndexY >= Constants.CHUNK_AMOUNT_Y)
                {
                    hit = false;
                    return;
                }

                // Get a reference to the new working chunk
                c = chunks[chunkIndexX, chunkIndexY, chunkIndexZ];
            }

            // Update our progress in the ray 
            t = yDistance;
            
            // Set the new distance to the next voxel Y boundary
            yDistance += yInverted;
            
            // For collision purposes we also store the last axis that the ray collided with
            // This allows us to reflect particle velocity on the correct axis
            axis = Axis.Y;
        }
        else
        {
            // Advance to the closest voxel boundary in the Z direction
            ...
        }
    }
    else if (xDistance < zDistance)
    {
        // Advance to the closest voxel boundary in the X direction
        ...
    }
    else
    {    
        // Advance to the closest voxel boundary in the Z direction
        ...
    }
}

Benchmarks

The following benchmarks were run on a Ryzen 5 1600 CPU.

The average particle collision ray march in Sector's Edge travels 1-10 blocks and takes 250 nanoseconds to run. At 60 frames per second, this allows for 64000 rays per frame per thread.

For stress testing, 100,000 rays were cast in random directions across the map. The average ray length was 200-400 blocks and takes 3400 nanoseconds to run. At 60 frames per second, this allows for 4700 rays per frame per thread.

In Practice

The full source code for this article is available here on GitHub.

In Sector's Edge, ray marching is required for particle collisions and hit detection between projectiles and the map. See it in action in our latest video below:

In multiplayer games it is common for players to have high ping times to the game server. This means that the world the player sees is slightly behind what the server sees and this leads to problems with hit detection.

This article explains the lag compensation system used in Sector's Edge that improves hit-detection accuracy for players with high ping time.

The full source code for this system is available on GitHub here.

Terminology

• Tick - a 50 millisecond time span
• Tick Lag - how many Ticks the client is behind the server
• Player - a player-controlled character
• Entity - a moving player, grenade, scanner, etc.
• Record - an object that stores the state of all entities at a certain timestamp
• History - the object that manages lag compensation and stores Records
• Message - a network message sent from the client to the server

Overview

Sector's Edge uses the Lidgren C# networking library, which provides the ping time for each player. Traditionally, we would use this ping time to calculate the player's Tick Lag, however this value can fluctuate and doesn't account for player position smoothing and other factors on the client.

Instead, the server stores a Record every tick (50ms) that contains information about every entity's position and state. The client periodically sends the position of a random moving entity to the server, whether it be a player, grenade, scanner, etc. The server will then use this position to determine the player's Tick Lag.

Records that are older than 400ms are discarded for anti-cheat purposes. Players with > 400ms ping will not benefit from lag compensation.

For example, the server is currently running at Tick 9 and a client states that player K is at position 2.5 (the red dotted line):

The server will then look through its History for player K and determine that the client is currently running at around Tick 7.25. This means that the client has a Tick Lag of 1.75 Ticks (about 88ms ping).

In the case that multiple matching positions are found, the most recent position will be used.

The past 20 Tick Lag values are stored for each Player. To minimise fluctuations, the average value of the Tick Lag history is used when calculating hit detection:

public class Player
{
    const int TICK_TIME = 50;
    const int LAG_HISTORY_MAX = 20;    
    double ping;

    List<double> TickLagHistory = new List<double>();
    double AccumulatedTickLag = 0;

    public void AddTickLag(double d)
    {
        TickLagHistory.Add(d);
        
        AccumulatedTickLag += d;

        if (TickLagHistory.Count > LAG_HISTORY_MAX)
        {
            AccumulatedTickLag -= TickLagHistory[0];
            TickLagHistory.RemoveAt(0);
        }
    }
    
    public double AverageTickLag
    {
        get
        {
            // Use ping as an approximation until TickLagHistory is populated
            if (TickLagHistory.Count < LAG_HISTORY_MAX)
                return ping / TICK_TIME;

            return AccumulatedTickLag / LAG_HISTORY_MAX;
        }
    }
}

It takes 1000ms for TickLagHistory to populate when a player first connects to the server. Until it is populated, the player's ping will be used as an approximation.

Note that List<double> can be replaced with a ring buffer as an optimisation.

System Structure

The structure of the GameServer, Record and the History class are as follows:

public class GameServer
{
    List<Player> Players;
    List<Projectile> Projectiles;
    History history;
    
    Stopwatch tickWatch = new Stopwatch();
    int PresentTick
    {
        get
        {
            return (int)(tickWatch.ElapsedMilliseconds / TICK_TIME);
        }
    }
}

public class Record
{
    public int tick;
    public List<Player> players = new List<Player>();

    // As there are 16 players max, we use a linear lookup
    public Player GetPlayer(byte ID)
    {
        for (int i = 0; i < players.Count; i++)
            if (players[i].ID == ID)
                return players[i];

        return null;
    }
}

public class History
{
    GameServer parent;
    List<Record> records;
        
    // As there are 8 records max, we use a linear lookup
    Record GetRecord(int tick)
    {
        for (int i = 0; i < records.Count; i++)
            if (records[i].tick == tick)
                return records[i];

        return records.Last();
    }
    
    Player GetPlayer(List<Player> players, byte ID) { ... }
    void ProjectileLoop(double tick, Projectile proj) { ... }
}

We also rely on interpolating between two Vector3 values, which is handled in a Helper class:

public static class Helper
{
    public static double Interpolate(double first, double second, double by)
    {
        return first + by * (second - first);
    }

    public static Vector3 Interpolate(in Vector3 first, in Vector3 second, double by)
    {
        double x = Interpolate(first.X, second.X, by);
        double y = Interpolate(first.Y, second.Y, by);
        double z = Interpolate(first.Z, second.Z, by);
        return new Vector3(x, y, z);
    }
}

The Projectile Loop

When the server receives a mouse click message from the client, it simulates the projectile through each Record in the past until it reaches the present Tick. This is called the Projectile Loop.

void HandleMouseDown(Player player)
{
    // Calculate the player's current tick
    double tick = PresentTick - player.AverageTickLag;   
    
    // Create a projectile
    Projectile proj = player.CreateProjectile();    
    
    // Process the projectile
    history.ProjectileLoop(tick, proj);
}

The ProjectileLoop function recursively checks the projectile against each Record in its history, starting at the provided tick. If the projectile doesn't collide with anything in each Record, the projectile is moved to the current list of projectiles on the GameServer, which are then updated each frame in real time.

void ProjectileLoop(double tick, Projectile proj)
{
    Record lastRecord = records.Last();
    
    // If we have checked each Record and the projectile is still alive, add it to the present
    if (tick > lastRecord.tick)
    {
        parent.Projectiles.Add(proj);
        return;
    }

    bool repeat = false;

    // If tick is 4.75, we want to interpolate 75% between the two Records
    double interpolation = tick - (int)tick;

    // Interpolate between the most recent Record and the present
    if ((int)tick == lastRecord.tick)
    {
        repeat = ProcessCollision(lastRecord.players, parent.Players, interpolation, proj);
    }

    // Interpolate between two Records
    else 
    {
        var eOld    = GetRecord((int)tick);         // Less recent
        var eRecent = GetRecord((int)tick + 1);     // More recent

        repeat = ProcessCollision(eOld.players, eRecent.players, interpolation, proj);
    }

    // Some projectiles are hitcast, which means they have infinite velocity
    // and therefore we only need to check one frame
    if (proj.IsHitCast)
        return;

    // If the projectile didn't hit anything
    if (repeat)
    {
        // Move the projectile
        proj.Position += proj.Velocity * TICK_TIME;

        // Check the next most recent record
        ProjectileLoop(tick + 1, proj);
    }
}

The player's Tick Lag is not always a whole integer and therefore the ProcessCollision function must interpolate between the player positions stored in two Records for accurate hit detection:

bool ProcessCollision(List<Player> playersOld, List<Player> playersRecent, double interpolation, Projectile proj)
{
    // We don't want to modify the player positions stored in the Record, so we use a new list
    List<Player> playerCopies = new List<Player>();

    foreach (var pOld in playersOld)
    {
        // Create a copy of the player containing only the information
        // we need for collision (position, velocity, crouching, aiming, etc)
        var pCopy = pOld.Copy();

        // Find a player with a matching ID in the more recent Record
        var pRecent = GetPlayer(playersRecent, pOld.ID);

        // If the player hasn't disconnected, interpolate their position
        // between the two ticks for more accurate collision detection
        if (pRecent != null)
            pCopy.position = Interpolate(pOld.position, pRecent.position, interpolation);

        playerCopies.Add(pCopy);
    }

    // Calculate collision, deal damage to the players and map, etc
    // Returns true if the projectile didn't hit anything
    return parent.DoCollision(proj, playerCopies);
}

Note that the parent.DoCollision() function handles collision between projectiles, the voxel map and players. This will be covered in another article.

In Practice

The full source code is available on GitHub here.

See the hit detection in action from the point of view of one of our best snipers:

This article is a continuation from the original article Voxel World Optimisations, which details the initial methods used to increase chunk initialisation time in our destructive first person shooter Sector's Edge.

In the previous article, the benchmark for initialising one chunk was 0.89 milliseconds. This article describes the changes made to reduce this time down to 0.48ms (54% faster).

If any terms used in this article are unfamiliar, please see the original article.

The full source code is available here.

For clarity, i, j and k refer to chunk-relative positions (range 0-31)
and x, y and z refer to global map positions (range 0-511)

Constants

These constants are referenced multiple times throughout the article:

const int EMPTY = 0;
const int CHUNK_SIZE = 32;
const int CHUNK_SIZE_SQUARED = 1024;
const int CHUNK_SIZE_CUBED = 32768;
const int CHUNK_SIZE_MINUS_ONE = 31;
const int CHUNK_SIZE_SHIFTED = 32 << 6;

GenerateMesh

The GenerateMesh function iterates over each block in the chunk, combining faces across multiple blocks where possible to reduce the triangle count of the mesh. The first downfall of the original function is that all 32768 blocks in the data array are checked, when most may be empty.

To reduce the amount of blocks checked, we store two heightmaps for the bottom- and top-most non-empty blocks in each column in the chunk. These arrays are updated each time a block is added or removed from the chunk:

byte[] MinY = new byte[CHUNK_SIZE_SQUARED];
byte[] MaxY = new byte[CHUNK_SIZE_SQUARED];

To make use of this heightmap, we restructure the loop as follows:

int access;

// Z axis
for (int k = 0; k < CHUNK_SIZE; k++)
{
    // X axis
    for (int i = 0; i < CHUNK_SIZE; i++)
    {
        int j =    MinY[i + k * CHUNK_SIZE_SQUARED];
        int topJ = MaxY[i + k * CHUNK_SIZE_SQUARED];
        
        // Y axis
        for (; j < topJ; j++)
        {
            access = i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;
            ref Block b = ref data[access];

            if (b.kind == EMPTY)
                continue;

            CreateRun(ref b, i, j, k, chunkHelper, access);
        }
    }

    // Extend the array if it is nearly full
    if (vertexBuffer.used > vertexBuffer.data.Length - 2048)
        vertexBuffer.Extend(2048);

}```

As the inner-most loop now iterates over the Y axis, we should restructure the way that we store block positions in data[] so that we can access the next highest block in the column by incrementing access by 1:

// Old
int access = i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;

// New
int access = j + i * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;

The next issue is that i * CHUNK_SIZE, k * CHUNK_SIZE_SQUARED and other values within CreateRun() are redundantly calculated many times. Therefore where possible, any value that is calculated multiple times should be stored in a variable in the outer loop and referenced later on. This reduces the amount of multiplications from 65536 down to 1056, and the amount of additions from 197664 down to 135232 (worst case).

The new loop structure is as follows:

// Precalculate the map-relative Y position of the chunk in the map
int chunkY = chunkPosY * CHUNK_SIZE;

// Allocate variables on the stack
int access, heightMapAccess, iCS, kCS2, i1, k1, j, topJ;
bool minXEdge, maxXEdge, minZEdge, maxZEdge;

k1 = 1;

for (int k = 0; k < CHUNK_SIZE; k++, k1++)
{
    // Calculate this once, rather than multiple times in the inner loop
    kCS2 = k * CHUNK_SIZE_SQUARED;

    i1 = 1;
    heightMapAccess = k * CHUNK_SIZE;
    
    // Is the current run on the Z- or Z+ edge of the chunk
    minZEdge = k == 0;
    maxZEdge = k == CHUNK_SIZE_MINUS_ONE;

    for (int i = 0; i < CHUNK_SIZE; i++; i1++)
    {
        // Determine where to start the innermost loop
        j = MinY[heightMapAccess];
        topJ = MaxY[heightMapAccess];
        heightMapAccess++;
        
        // Calculate this once, rather than multiple times in the inner loop
        iCS = i * CHUNK_SIZE;
        
        // Calculate access here and increment it each time in the innermost loop
        access = kCS2 + iCS + j;

        // Is the current run on the X- or X+ edge of the chunk
        minX = i == 0;
        maxX = i == CHUNK_SIZE_MINUS_ONE;

        // X and Z runs search upwards to create runs, so start at the bottom.
        for (; j < topJ; j++, access++)
        {
            ref Block b = ref data[access];

            if (b.kind != EMPTY)
            {
                CreateRun(ref b, i, j,
                          k << 12,
                          i1,
                          k1 << 12,
                          j + chunkY, access,
                          minX, maxX,
                          j == 0, j == CHUNK_SIZE_MINUS_ONE,
                          minZ, maxZ,
                          iCS, kCS2);
            }
        }

        // Extend the array if it is nearly full
        if (vertexBuffer.used > vertexBuffer.data.Length - 2048)
            vertexBuffer.Extend(2048);
    }
}

CreateRun

As the new CreateRun() function has many changes, we will split it into sections. The first difference is the new parameters:

// New CreateRun function
void CreateRun(ref Block b, int i, int j,
               int k,
               int i1,
               int k1,
               int y, int access,
               bool minX, bool maxX,
               bool minY, bool maxY,
               bool minZ, bool maxZ,
               int iCS, int kCS2)
{
    ...
}

• int i, int j - chunk-relative position of the block
• k - chunk-relative position of the block shifted left 12 bits
• int i1 - precalculated i + 1
• int k1 - precalculated (k + 1) << 12
• int y - map-relative y position of the block
• int access - current position in the data[] array
• bool minX, bool maxX - if the current run is on the X edge of the chunk
• bool minY, bool maxY - if the current run is on the Y edge of the chunk
• bool minZ, bool maxZ - if the current run is on the Z edge of the chunk
• int iCS - precalculated i * CHUNK_SIZE
• int kCS2 - precalculated k * CHUNK_SIZE_SQUARED

Precalculating

At the start of the function, we can see the following changes:

• The BlockVertex helper class now has a int[] indexToTextureShifted array, which stores the texture values shifted left 18 bits. Since the texture and health values are the same for each face of the block, they can be bit-shifted and combined here rather than in the AppendQuad() function
• The length variable has been replaced with runFinish, which stores the chunk-relative position of the end of the run

int textureHealth16 = BlockVertex.indexToTextureShifted[b.index] | ((b.health / 16) << 23);
int runFinish;
int accessIncremented = access + 1;
int chunkAccess;
int j1 = j + 1;
int jS = j << 6;
int jS1 = j1 << 6;

Combining Faces

The next part combines faces upwards along the negative X face, with the following changes:

• kCS2 is passed to VisibleFaceXN() so that the function doesn't have to calculate k * CHUNK_SIZE_SQUARED each time
• chunkAccess has the default value of accessIncremented, which is equivalent to
  j + i * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED + 1. This value is then incremented at the end of the loop
• Rather than creating an extra variable q for managing the loop, we can use the runFinish variable. By initialising this variable to j1 << 6 and incrementing it by 64 (1 << 6 == 64), we can save an extra addition and avoid bit-shifts throughout the entire CreateRun() function
• AppendQuad() has been split into three functions AppendQuadX(), AppendQuadY() and AppendQuadZ(), which are specifically for generating X, Y and Z faces
• Int3 structs are no longer passed to AppendQuad(), therefore removing unnecessary memory allocation
• The FaceType enum has been replaced with FaceTypeShifted, which stores the same values shifted left 27 bits

// Left (X-)
if (!chunkHelper.visitXN[access] && VisibleFaceXN(j, access, minX, kCS2))
{
    chunkHelper.visitXN[access] = true;
    chunkAccess = accessIncremented;

    for (runFinish = jS1; length < Constants.ChunkSizeShifted; length += 64)
    {
        if (DifferentBlock(chunkAccess, ref b))
            break;

        chunkHelper.visitXN[chunkAccess++] = true;
    }

    // k1 and k are already shifted
    BlockVertex.AppendQuadX(vertexBuffer, i, jS, length, k1, k, (int)FaceTypeShifted.xn, textureHealth16);
}

AppendQuad

The new AppendQuadX function contains no bit-shifts and fewer or operations:

// Stores the values of the old blockToTexture[] shifted left 18 bits
public static byte[] blockToTextureShifted;
        
public static void AppendQuadX(BlockVertexBuffer buffer, int x,
                               int jBottom, int jTop,
                               int kLeft, int kRight, 
                               int normal, int textureHealth)
{
    // Combine data that is common for each face
    var shared = x             | 
                 textureHealth |
                 normal;

    // Combine the shared data with the Y and Z position of the vertex
    buffer.data[buffer.used] = jTop | kRight | shared;
    buffer.data[buffer.used + 1] = buffer.data[buffer.used + 4] = jBottom | kRight | shared;
    buffer.data[buffer.used + 2] = buffer.data[buffer.used + 3] = jTop | kLeft | shared;
    buffer.data[buffer.used + 5] = jBottom | kKeft | shared;

    buffer.used += 6;
}

Visible Face Checking

The new VisibleFaceXN function uses the precalculated values min and kCS2 and prevents excess faces being produced on the edge of the map:

protected bool VisibleFaceXN(int j, int k, int access, bool min, int kCS2)
{
    // Access directly from a neighbouring chunk
    if (min)
    {
        // If on the edge of the map, don't produce faces
        if (chunkPosX == 0)
            return false;

        if (cXN == null)
            return true;

        return cXN.data[31 * CHUNK_SIZE + j + kCS2].kind == EMPTY;
    }

    // The block to the left can be accessed by subtracting CHUNK_SIZE
    return data[access - CHUNK_SIZE].kind == EMPTY;
}```

Full Source Code

The full source code including OpenGL data buffering and shaders is available here.

See the code in action in our latest video:

Sector's Edge is a first person shooter that takes place in a voxel environment, where the world is composed of millions of destructible cubes. With 16 players per match, the mesh must be regenerated nearly every frame. This is a CPU-intensive process and this article dives into the optimisations that make it possible.

Our two goals for this engine are:

• fast mesh regeneration balanced with low triangle count
• fast vertex processing on the GPU

The second topic will be available in a separate article soon.

The full source code for this article is available here on GitHub.

Update: a new article has been posted that describes the further optimisations made to reduce chunk mesh initialisation time down to 0.48ms.

Map Structure

The map is divided into chunks of 32 x 32 x 32 blocks. Each chunk has its own mesh - a list of triangles - which must be regenerated each time a block is added, removed or damaged. Block data is stored in the following structure:

public class Map
{
    Chunk[,,] chunks;
}

public class Chunk
{
    const int CHUNK_SIZE = 32;
    const int CHUNK_SIZE_SQUARED = 1024;
    const int CHUNK_SIZE_CUBED = 32768;
    Block[] data = new Block[CHUNK_SIZE_CUBED];
}

public struct Block
{
    byte kind;  // Block type, e.g. empty, dirt, metal, etc.
    byte health;
}

Greedy meshing is a popular algorithm for producing a mesh with a low triangle count, however it requires many block comparisons and in our case wasn't regenerating chunks fast enough. In our approach, blocks are combined into runs along the X and Y axis:

To reduce triangle count, a run will not be split if it is covered by a block. Runs are only split if the next block has a different texture or is damaged:

This allows chunk meshes to be regenerated with less block comparisons while still combining faces to reduce the triangle count.

Mesh Generation

The full Chunk class has the following structure:

public class Chunk
{
    const int CHUNK_SIZE = 32;
    const int CHUNK_SIZE_SQUARED = 1024;
    const int CHUNK_SIZE_CUBED = 32768;
    const int EMPTY = 0;
    
    Block[,,] data = new Block[CHUNK_SIZE_CUBED];
    
    // Global map position of this chunk
    public int chunkX, chunkY, chunkZ;
    
    // Each chunk has a reference to the map it is located in, so it can access
    // blocks in other chunks
    Map map;
    
    // Stores vertex data and manages buffering to the GPU
    BlockVertexBuffer vertexBuffer;
    
    // References to neighbouring chunks
    Chunk cXN, cXP, cYN, cYP, cZN, cZP;
    
    public Chunk(int i, int j, int k, Map map)
    {
        chunkX = i * CHUNK_SIZE;
        chunkY = j * CHUNK_SIZE;
        chunkZ = k * CHUNK_SIZE;
        this.map = map;
    }
    
    public void GenerateMesh(...) ...
    void CreateRuns(...) ...
}

For clarity, i, j and k refer to chunk-relative positions (range 0-31)
and x, y and z refer to global map positions (range 0-511)

To start, GenerateMesh gets references to chunk neighbours for quick edge-case block comparisons. It then iterates over each block in the chunk and creates runs.

public void GenerateMesh(ChunkHelper chunkHelper)
{
    // X- neighbouring chunk
    cXN = chunkPosX > 0 ? m.chunks[chunkPosX - 1, chunkPosY, chunkPosZ] : null;

    // X+ neighbouring chunk
    cXP = chunkPosX < Constants.ChunkXAmount - 1 ? m.chunks[chunkPosX + 1, chunkPosY, chunkPosZ] : null;

    // Y- neighbouring chunk
    cYN = chunkPosY > 0 ? m.chunks[chunkPosX, chunkPosY - 1, chunkPosZ] : null;

    // Y+ neighbouring chunk
    cYP = chunkPosY < Constants.ChunkYAmount - 1 ? m.chunks[chunkPosX, chunkPosY + 1, chunkPosZ] : null;

    // Z- neighbouring chunk
    cZN = chunkPosZ > 0 ? m.chunks[chunkPosX, chunkPosY, chunkPosZ - 1] : null;
    
    // Z+ neighbouring chunk
    cZP = chunkPosZ < Constants.ChunkZAmount - 1 ? m.chunks[chunkPosX, chunkPosY, chunkPosZ + 1] : null;
    
    int access;
    // Y axis - start from the bottom and search up
    for (int j = 0; j < CHUNK_SIZE; j++)
    {
        // Z axis
        for (int k = 0; k < CHUNK_SIZE; k++)
        {
            // X axis
            for (int i = 0; i < CHUNK_SIZE; i++)
            {
                access = i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;
                ref Block b = ref data[access];

                if (b.kind == EMPTY)
                    continue;

                CreateRun(ref b, i, j, k, chunkHelper, access);
            }

            // Extend the array if it is nearly full
            if (vertexBuffer.used > vertexBuffer.data.Length - 2048)
                vertexBuffer.Extend(2048);
        }
    }
}

The ChunkHelper class is used to record which faces have been merged, to prevent creating duplicate faces. Each chunk mesh is regenerated on a different thread and one ChunkHelper instance is allocated to each thread.

public class ChunkHelper
{
    public bool[] visitedXN = new bool[CHUNK_SIZE_CUBED];
    public bool[] visitedXP = new bool[CHUNK_SIZE_CUBED];
    public bool[] visitedZN = new bool[CHUNK_SIZE_CUBED];
    public bool[] visitedZP = new bool[CHUNK_SIZE_CUBED];
    public bool[] visitedYN = new bool[CHUNK_SIZE_CUBED];
    public bool[] visitedYP = new bool[CHUNK_SIZE_CUBED];
}

Separate runs are created for each block face orientation (X-, X+, Z-, Z+, Y-, Y+). For each block in the combined face, a flag is set in the respective array in ChunkHelper to indicate it has been merged.

void CreateRun(ref Block b, int i, int j, int k, ChunkHelper chunkHelper, int access)
{
    // Precalculate variables
    int i1 = i + 1;
    int j1 = j + 1;
    int k1 = k + 1;
    byte health16 = (byte)(b.health / 16);
    
    int length = 0;
    int chunkAccess = 0;

    // Left face (X-)
    if (!chunkHelper.visitedXN[access] && VisibleFaceXN(i - 1, j, k))
    {
        // Search upwards to determine run length
        for (int q = j; q < CHUNK_SIZE; q++)
        {
            // Pre-calculate the array lookup as it is used twice
            chunkAccess = i + q * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;
            
            // If we reach a different block or an empty block, end the run
            if (DifferentBlock(chunkAccess, b))
                break;

            // Store that we have visited this block
            chunkHelper.visitedXN[chunkAccess] = true;

            length++;
        }


        if (length > 0)
        {
            // Create a quad and write it directly to the buffer
            BlockVertex.AppendQuad(buffer, new Int3(i, length + j, k1),
                                           new Int3(i, length + j, k),
                                           new Int3(i, j,          k1),
                                           new Int3(i, j,          k), 
                                           (byte)FaceType.xn, b.kind, health16);

            buffer.used += 6;
        }
    }
    
    // Same algorithm for right (X+)
    if (!chunkHelper.visitedXP[access] && VisibleFaceXP(i1, j, k))
    {
        ...
    }

    // Same algorithm for back (Z-)
    ...
    
    // Same algorithm for front (Z+)
    ...
    
    // Same algorithm for bottom (Y-)
    ...

    // Same algorithm for top (Y+)
    ...
}

The VisibleFace functions are used to check whether or not a block is empty. Most comparisons are within the working chunk, so we prioritise accessing block data directly within the chunk if possible.

bool VisibleFaceXN(int i, int j, int k)
{
    // Access directly from a neighbouring chunk
    if (i < 0)
    {
        if (cXN == null)
            return true;

        return cXN.data[31 + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED].kind == EMPTY;
    }

    return data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED].kind == EMPTY;
}

bool VisibleFaceXP(int i, int j, int k)
{
    if (i >= CHUNK_SIZE)
    {
        if (cXP == null)
            return true;

        return cXP.data[0 + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED].kind == EMPTY;
    }

    return data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED].kind == EMPTY;
}

DifferentBlock is used to determine whether a block is different to the current run. Runs do not span across multiple chunks and therefore we do not need bounds checks when accessing the block.

protected bool DifferentBlock(int access, Block current)
{
    // Using a ref variable here increased performance by ~4%
    ref var b = ref data[access];
    return b.kind != current.kind || b.health != current.health;
}

The AppendQuad function creates 6 vertices (two triangles) and writes them directly to the vertex buffer.

public static byte[] blockToTexture;
        
public static void AppendQuad(BlockVertexBuffer buffer, Int3 tl, Int3 tr, Int3 bl, 
                              Int3 br, byte normal, byte kind, byte health)
{
    // Each block kind maps to a texture unit on the GPU
    byte texture = blockToTexture[kind];

    // Each vertex is packed into one uint to reduce GPU memory overhead
    // 18 bits for position XYZ
    // 5 bits for texture unit
    // 4 bits for health
    // 3 bits for normal
    
    // Each vertex in a quad shares the same texture unit, health and normal value
    uint shared = (uint)((texture & 31) << 18 |
                         (health  & 15) << 23 |
                         (normal  & 7)  << 27);

    // Top left vertex
    uint tlv = CombinePosition(tl, shared);
    
    // Top right vertex
    uint trv = CombinePosition(tr, shared);
    
    // Bottom left vertex
    uint blv = CombinePosition(bl, shared);
    
    // Bottom right vertex
    uint brv = CombinePosition(br, shared);

    // Store each vertex directly into the buffer
    buffer.data[buffer.used]     = tlv;
    buffer.data[buffer.used + 1] = blv;
    buffer.data[buffer.used + 2] = trv;
    buffer.data[buffer.used + 3] = trv;
    buffer.data[buffer.used + 4] = blv;
    buffer.data[buffer.used + 5] = brv;
}

// Combine position data with the shared uint
static uint CombinePosition(Int3 pos, uint shared)
{
    return (uint)(shared | 
                 ((uint)pos.X & 63) |
                 ((uint)pos.Y & 63) << 6 |
                 ((uint)pos.Z & 63) << 12);
}

Benchmarking

To test our optimisations, the same map was initialised three times in a row and the time taken to run GenerateMesh for each chunk was recorded. This was done single-threaded to ensure we were only measuring our function, not task scheduling.

Our initial benchmark was:
807 chunks initialised in 4158ms
1 chunk initialised in 5.15ms (average)

After optimisations:
807 chunks initialised in 722ms
1 chunk initialised in 0.89ms (average)

How this 5.7x increase in speed was achieved is outlined below.

Update: a new article has been posted that describes the further optimisations made to reduce chunk mesh initialisation time down to 0.48ms.

Optimisations

Inlining (3% speed increase)

Apart from GenerateMesh, every method is inlined using this MethodImpl attribute:

using [MethodImpl(MethodImplOptions.AggressiveInlining)]
void CreateStrips(...) ...

Pre-Calculating and Ref Locals (5% speed increase)

Every multiplication, addition and memory lookup affects performance, so we pre-calculate the common operations.

For example at the start of the CreateRun function:

protected void CreateStrips(Block b, int i, int j, int k, ChunkHelper chunkHelper, int access)
{
    int i1 = i + 1;
    int j1 = j + 1;
    int k1 = k + 1;
    byte health16 = (byte)(b.health / 16);
    
    ...
}

In the BlockVertex class, we reduced 24 bitwise operations down to 19:

// Old - 24 bitwise operations per quad
static uint toInt(Int3 pos, byte texID, byte health, byte normal)
{
    return (uint)((pos.X  & 63) |
                  (pos.Y  & 63) << 6 |
                  (pos.Z  & 63) << 12 |
                  (texID  & 31) << 18 |
                  (health & 15) << 23 |
                  (normal & 7) << 27);
}

// New - 19 bitwise operations per quad
public static void AppendQuad(...)
{
    var shared = (uint)((t      & 31) << 18 |
                        (health & 15) << 23 |
                        (normal & 7)  << 27);
                        
    uint tlv = CombinePosition(tl, shared);
    uint trv = CombinePosition(tr, shared);
    uint blv = CombinePosition(bl, shared);
    uint brv = CombinePosition(br, shared);
    
    ...                        
}

static uint CombinePosition(Int3 pos, uint shared)
{
    return (uint)(shared | 
                  ((uint)pos.X & 63) |
                  ((uint)pos.Y & 63) << 6 |
                  ((uint)pos.Z & 63) << 12);
}

Ref locals are used where possible to avoid copying structs onto the stack and avoid multiple array lookups:

protected bool DifferentBlock(int i, int j, int k, Block compare)
{
    ref var b = ref data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED];
    return b.kind != compare.kind || b.health != compare.health;
}

Neighbouring Chunks (10% speed increase)

By storing references to neighbouring chunks at the start of GenerateMesh, we saved 32*32 expensive Map.IsNoBlock functions calls on each side of the chunk.

// Old
bool VisibleFace(int i, int j, int k)
{
    // Access from global map coordinates
    if (i < 0 || j < 0 || k < 0 ||
        i >= CHUNK_SIZE || j >= CHUNK_SIZE || k >= CHUNK_SIZE)
    {
        return m.IsNoBlock(i + chunkPosX, j + chunkPosY, k + chunkPos.Z);
    }

    return data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED].kind == EMPTY;
}

// New
bool VisibleFaceXN(int i, int j, int k)
{
    // Access directly from neighbouring chunk
    if (i < 0)
    {
        if (cXN == null)
            return true;

        return cXN.data[31 + j * Constants.ChunkSize + k * Constants.ChunkSizeSquared].kind == EMPTY;
    }

    return data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED].kind == EMPTY;
}

// Same for VisibleFaceXP, VisibleFaceZN, ...
...

Single-Dimensional Arrays (20% speed increase)

Changing the block data array in the Chunk class from a multi-dimensional array to a single-dimensional array provided a noticeable improvement in performance:

// Old
Block[,,] data;
Block b = data[i,j,k];

// New
Block[] data;
Block b = data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED];

The same was done with the ChunkHelper arrays:

// Old
bool[,,] visitedXN = new bool[CHUNK_SIZE, CHUNK_SIZE, CHUNK_SIZE];
bool b = visitedXN[i,j,k];

// New
bool[] visitedXN = new bool[CHUNK_SIZE_CUBED];
bool b = visitedXN[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED];

This performance increase came from the fact that CHUNK_SIZE is a multiple of 2, and therefore the C# compiler could simplify the multiplications to bitshifts:

// Old
data[i, j, k];

// Underlying array access produced by the compiler
data[i + j * data.GetLength(0) + j * data.GetLength(0) * data.GetLength(1)];

// New
data[i + j * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED];

// Simplified array access produced by the compiler
data[i + j << 5 + k << 10];

At times, we are also able to pre-calculate the single-dimensional array lookup, as seen in the CreateRun function:

for (int q = j; q < CHUNK_SIZE; q++)
{
    // Pre-calculate the array lookup as it is used twice
    chunkAccess = i + q * CHUNK_SIZE + k * CHUNK_SIZE_SQUARED;

    if (DifferentBlock(chunkAccess, b))
        break;

    chunkHelper.visitedXN[chunkAccess] = true;
    
    ...
}

Garbage Collection (10% speed increase)

Each array in ChunkHelper must be reset to false before being re-used by another chunk. Initially we were re-allocating a new boolean array, however this put excessive pressure on the garbage collector. Array.Clear was a much better solution and quickly resets the array back to false:

// Old
public void Reset()
{
    visitedXN = new bool[CHUNK_SIZE_CUBED];
    
    // Same for X+, Y-, Y+, Z- and Z+
	...
}

// New
public void Reset()
{
    Array.Clear(visitedXN, 0, CHUNK_SIZE_CUBED);
    
    // Same for X+, Y-, Y+, Z- and Z+
    ...
}

Memory (20% speed increase)

Initially, AppendQuad returned an array of 6 uints, which was then copied to a temporary buffer stored in a ChunkHelper. In the GenerateMesh function we would then check if this buffer has exceeded a certain size and copy it to the vertex buffer. This involved a lot of Array.Copy calls.

Instead, AppendQuad is passed the vertex buffer as a parameter and writes to it directly. This removes a lot of expensive Array.Copy functions, however we need to ensure we do not overflow the vertex buffer:

public void GenerateMesh(...)
{
    ...    
    // Extend the array if it is nearly full
    if (vertexBuffer.used > vertexBuffer.data.Length - 2048)
        vertexBuffer.Extend(2048);        
    ...
}
    
// Function inside BlockVertexBuffer:
class BlockVertexBuffer
{
    ...    
    public void Extend(int amount)
    {
        uint[] newData = new uint[data.Length + amount];
        Array.Copy(data, newData, data.Length);
        data = newData;
    }    
    ...
}

Block Access (20% speed increase)

Initially, blocks were only accessed in the map class by their global map positions. We reduced our chunk initialisation time by accessing blocks directly within the chunk where possible.

IsNoBlock is still used and has been optimised using bit shifts and bit masks:

public class Map
{
    Chunk[,,] chunks;
    const byte SHIFT = 5;
    const int MASK = 0x1f;
    const int MAP_SIZE_X = 512;
    const int MAP_SIZE_Y = 160;
    const int MAP_SIZE_Z = 512;
    
    // Returns true if there is no block at this global map position
    public bool IsNoBlock(int x, int y, int z)
    {
        // If it is at the edge of the map, return true
        if (x < 0 || x >= MAP_SIZE_X ||
            y < 0 || y >= MAP_SIZE_Y ||
            z < 0 || z >= MAP_SIZE_Z)
            return true;

        // Chunk accessed quickly using bitwise shifts
        var c = chunks[x >> SHIFT, y >> SHIFT, z >> SHIFT];

        // To lower memory usage, a chunk is null if it has no blocks
        if (c == null)
            return true;

        // Chunk data accessed quickly using bit masks        
        return c.data[(x & MASK) + (y & MASK) * CHUNK_SIZE, (z & MASK) * CHUNK_SIZE_SQUARED].kind == EMPTY;
    }
}

In Practice

This engine was created from scratch for our first person shooter Sector's Edge. We did not use an existing game engine as we desired the ability to fine-tune every aspect of the rendering pipeline. This allows the game to run on older hardware and at rates higher than 60 frames per second.

The full source code for this article is available here on GitHub.

If you have any questions, feel free to reach out to me on our Discord server.

I have also written a breakdown of each stage in the rendering and post-processing pipeline, which is available here.

Each frame seen in a modern game is the combination of many different layers and effects. This article explains each stage of the rendering process in our first person shooter Sector's Edge.

There are a few terms used in this article:

• Buffer - a 2D image that stores either byte or float data for each pixel
• Normal - the XYZ direction that each pixel is facing. For example, the top of your desk is facing upwards and the ceiling is facing downwards
• Camera - the position of the player and the direction they are looking

Stage 1. Physical Rendering

The first stage involves rendering all in-game physical objects to four buffers:

• Colour buffer - stores the RGB value of each pixel
• Depth buffer - stores how far away each pixel is from the camera
• Normal buffer - stores an XYZ normal for each pixel
• Data buffer - stores special data for each pixel (explained below)

Colour Buffer

The colour buffer stores an RGB colour for each pixel on the screen.

Depth Buffer

This one is a bit harder to see, so we've zoomed the image onto the character model.

The depth buffer stores how far away each pixel is from the camera. Darker parts of the image are closer to the camera and lighter parts are further away. These values are used later to calculate the 3D position of each pixel for post-processing effects like lighting.

Normal Buffer

The normal buffer uses RGB values to represent the XYZ direction that each pixel is facing. These values range between -1 and 1 and are used for calculating shading and lighting during post-processing.

In the image above:

• Upwards facing pixels have a Y normal of 1, which is represented as green
• The walls on the right have a Z normal of 1, which is represented as blue
• Black parts of the image represent normals with a negative value, however we can't see them as monitors can only render positive colour values.

Here is another example:

Left-facing (X) pixels have some red colour, pixels facing the camera (Z) have some blue colour and any upwards-facing (Y) pixels have some green colour.

Data Buffer

The data buffer stores two bytes for each pixel that define which post-processing effects will be applied to certain parts of the image.

Three bits in the first byte are used to determine whether the pixel:

• is part of the skybox, therefore no post-processing effects should be applied to these pixels
• is part of the voxel environment, meaning these pixels are affected by SSAO and shadows
• should have bloom effects applied

The second byte stores how reflective the pixel is, for example metal pixels should be more illuminated by lights than dirt.

Stage 2. Shadow Rendering

The scene is rendered again into another 5 depth buffers, each of which store how far away each pixel is from a hypothetical 'sun'. By using 5 buffers we can have higher-quality shadows for the parts of the screen that are closer to the camera.

These buffers are generated from the sun's point of view looking down at the map, each more slightly zoomed than the last:

These buffers are used to darken certain parts of the colour buffer to create the illusion of shadows. This happens after the post-processing stage using some maths involving the values stored in the original depth buffer and the 5 shadow buffers.

Stage 3. Post Processing

Screen Space Ambient Occlusion

The first post-processing effect used is called Screen Space Ambient Occlusion (SSAO), which looks at the XYZ values in the normal buffer to locate crevices between objects.

The output is stored in the red component of the SSAO Buffer and is used to darken certain parts of the image later.

Bloom

Bloom is a post-processing effect that brightens and blurs certain parts of the image, to mimic looking directly at a light in real life.

Pixels that have a bloom bit set in the data buffer mean that they will be copied from the colour buffer to the Bloom Buffer. Once copied, the image is blurred:

Lighting

The average map in Sector's Edge has around 30-60 lights in it, each of which are compared against the depth, normal and reflectivity values of each pixel.

The final colour of each pixel is based on:

• The distance between the pixel and the light (the position of each pixel is calculated using some maths with the depth buffer)
• The pixel's XYZ normal value. Pixels facing away from a light will be illuminated less than pixels facing the light directly
• The reflectivity of each pixel - stored in the second byte of the data buffer - controls how much the pixel's colour will be affected by the light. For example, dirt has a lower reflectivity than metal

Lighting is applied directly to the colour buffer, but for this article we have separated the lighting values into their own buffer:

Stage 4. Putting it all Together

Starting with the colour buffer:

The shadow buffers and SSAO buffer are used to darken certain parts of the image:

Bloom and lighting is added to the image:

Transparent objects are then rendered directly to the final image. This is done last so that glass doesn't modify the depth/normal/data buffers, which would affect the post-processing effects:

And there you have it! All of this must be computed within 16ms to provide smooth gameplay at 60 frames per second. I describe how the game has been optimised to run at much higher frame rates in this article.

We are searching for people to help test Sector's Edge. Download the game for free on our website and let us know what you think on our Discord Server.

This article explains the galaxy generation algorithm showcased in the video below. It is written in C#, rendered with OpenGL and the source code is available here.

At the end of the article you can see how the galaxy is used as the server selection screen in our game Sector’s Edge, as well as some extreme examples.

Galaxy Anatomy

Each galaxy is composed of an axis and multiple arms:

The generation process follows the following stages:

• Arm generation
• Axis generation
• Arm scaling
• Arm bending
• Height variance
• Applying colour
• Creating multiple arm layers

Part 1 - Generating the Arms

The code below produces multiple flat arms and is controlled by the following parameters:

• gravity — pushes points towards the center of the galaxy so that the galaxy will appear brighter and more densely populated towards the center
• galaxySize — controls the radius of the galaxy
• armCount— controls the amount of arms
• armSpread — controls the width of each arm

Vector3 GetPoint()
{
    Vector3 v;
    double armDivisor = Math.PI / armCount;

    while (true)
    {
        // Generate a random normalised point with a weighting
        // towards the center controlled by the gravity variable
        v = NextV3(-1, 1).Normalized() * Math.Pow(Next(0, 1.0), gravity);

        // Some points will not conform to the parameters
        if (random.NextDouble() > conformChance)
            break;

        bool valid = false;

        // Calculate the global angle of the point around the axis
        var d = Math.Atan2(v.X, v.Z);

        // Check if this point lands on an arm
        for (double j = -Math.PI; j <= Math.PI; j += armDivisor)
        {
            // A point lands on an arm if its distance
            // from the start of the arm is less than angle * armDistance
            if (d > j && d < j + armDivisor * armSpread)
            {
                valid = true;
                break;
            }
        }

        if (valid)
            break;
    }
    
    v.Y = 0;
    return v * galaxySize;
}

Part 2 - Generating the Axis

The axis is composed of stars, which are generated in the same manner as the points in the arms. Stars closer to the center of the galaxy are shifted vertically proportional to the beamHeight parameter.

var v = GetPoint();

// Add some variance to each star
v += NextV3(-0.5, 0.5);

// Shift stars vertically as they get closer to the center of the galaxy
var s = beamHeight / v.Magnitude;
v.Y = Next(-s, s);

Stars are rendered as points into a framebuffer and then modified with a Gaussian blur to mimic a diffraction spike.

Part 3 - Arm Scaling

In a generated galaxy, some arms can be longer than others. The diagram below represents a top-down view of the galaxy. Any points that land inside the scaling region are extended further outwards.

θ¹ represents the scalingAngleStart parameter and θ² represents the scalingAngleEnd parameter. Any points that lie within the scaling region are extended outwards proportional to the scalingPower parameter. This calculation is added to the end of the GetPoint() function:

Vector3 GetPoint()
{
    Vector3 v = Vector3.Zero;
    
    // Generate a point
    ...

    // Calculate the global angle of the point around the axis
    var a = Math.Atan2(v.X, v.Z);

    // Calculate the angle of this point inside its quadrant
    var e = Math.Abs(Math.Abs(a) - Math.PI / 2);

    var magnitude = galaxySize;

    // Scale the point outwards if it lands within the scaling region
    if (e > scalingAngleStart && e < scalingAngleEnd)
        magnitude = magnitude * 2 / Math.Pow(e, scalingPower);

    v.X *= magnitude;
    v.Z *= magnitude;     

    v.Y = 0;        
    return v;
}

In the example below, the top and bottom arms land within the scaling region and are extended further outwards:

If scalingAngleEnd is set to PI, all points will land in the scaling zone:

Part 4 - Arm Bending

To bend each arm around the galaxy we apply a matrix transformation to each point. Points further from the center of the galaxy will have a stronger rotation applied to them.

Vector3 GetPoint()
{
    // Generate the point
    ...
    
    // Calculate arm scaling
    ...
    
    // Rotate the point around the galaxy proportional to its magnitude
    v *= Matrix4.CreateRotationY(-v.Magnitude * rotationStrength);
    
    v.Y = 0;
    return v;
}

The images below show the results of changing the rotationStrength parameter. Note these examples have more arms to demonstrate the bending more clearly.

Part 5 - Vertical Variance

By default, the arms generated are flat. By setting the heightMagnitude parameter to a value greater than 0, the vertical position of each point is calculated using a sine wave:

Vector3 position = GetPoint();
position.Y -= heightMagnitude * Math.Sin(position.Magnitude * heightFrequency);

Part 6 - Applying Colour

Each quadrant of the galaxy has its own colour (variables c1, c2, c3 and c4).

Once we have generated a point, its colour is calculated based on its angle and distance from the center of the galaxy.

Vector3 position = GetPoint();
position.Y -= heightMagnitude * Math.Sin(position.Magnitude * heightFrequency);

// Colour each point based on their global angle around the axis
Color blendedColour;
var angle = Math.Atan2(position.X, position.Z);

// c1, c2, c3 and c4 are random colours generated at the start of the program
// Blend the colours of adjacent quadrants together
if (angle < -Math.PI / 2)
    blendedColour = Color.Interpolate(c1, c2, (angle + Math.PI) / (Math.PI / 2));
else if (angle < 0)
    blendedColour = Color.Interpolate(c2, c3, (Math.PI / 2 + angle) / (Math.PI / 2));
else if (angle < Math.PI / 2)
    blendedColour = Color.Interpolate(c3, c4, angle / (Math.PI / 2));
else
    blendedColour = Color.Interpolate(c4, c1, (angle - Math.PI / 2) / (Math.PI / 2));

// maxMagnitude stores the distance of the furthest known point
if (position.Magnitude / maxMagnitude > 1)
    maxMagnitude = position.Magnitude;

// Colours get brighter the closer they are to the center
uint pointColour = Color.Interpolate(Color.Black, Color.Interpolate(Color.White, blendedColour, position.Magnitude / maxMagnitude), 0.8).Value;

Part 7 — Multiple Arm Layers

To add depth to the galaxy, the arm creation process can be repeated multiple times. Every iteration uses a different heightMagnitude to make each arm follow a different vertical path.

// Create multiple layers
for (int o = 0; o < layers; o++)
{
    // Create the arms
    for (int i = 0; i < 100000; i++)
    {
        Vector3 position = GetPoint();
        position.Y -= heightMagnitude * Math.Sin(position.Magnitude * heightFrequency);
        
        // Colour and store each point
        ...
    }

    // Randomise the height magnitude for the next layer
    // so that each layer follows a different path
    heightMagnitude *= random.NextDouble();
    
    // 50% chance that the next layer will be flipped vertically
    if (random.NextDouble() > 0.5)
        heightMagnitude *= -1;
}

In Practice

This side project began while developing the server selection screen for our first person shooter Sector’s Edge, where each map is represented by one of the stars:

Extreme Examples

Below are some extreme examples of galaxies with the parameters that were used to generate them: