Blogs - koonschi

Ambient Occlusion

Ambient occlusion (AO) is a powerful tool when it comes to making games visually appealing. Especially for indies, since you can give plain and simple geometry (like Avorion's) a great sense of depth and make it look more three-dimensional.

For those of you who don't know what ambient occlusion is exactly and how your game can benefit from it, have a look at the following screenshot:

This is an animation of a space station with and without ambient occlusion. It's easy to see that one of the scenes looks "better". You get an impression of depth, of plasticity. Ambient occlusion basically means that objects that are near each other "steal" light from each other, so they appear darker.

To calculate ambient occlusion, from each point on your model, you shoot n (random) rays (here 64) with a fixed length in a semisphere formation and check whether you hit other geometry.

The more rays intersect with other geometry, the darker the point in space. There are more sophisticated approaches that take into account the distance of the intersection point to the ray origin, but in our case we'll just say we hit or we miss. We didn't necessarily need a physically correct approach, we only want something that looks decent.

AO Techniques and our Problem

There are various techniques for achieving ambient occlusion:

Usually you can do it in your 3D editor and bake it into textures like lightmaps, but then it won't work when your scene changes. In Avorion, players build their own ships or get them blown apart, so models change all the time and the texture atlas would have to be huge for decent quality.

Then there's SSAO (screen space ambient occlusion). It basically calculates ambient occlusion each frame based on what you see and the depth of your current screen image. SSAO didn't work either, because it largely depends on your current viewport and I wanted dark parts of spaceships to always be dark. Since SSAO is view-based the occlusion tends to change when you move your camera around.

Minecraft does ambient occlusion by stepping one or more blocks in each grid direction, to find out how many blocks there are and calculates a corresponding occlusion. But I can't step in any grid directions because in Avorion there is no grid.

The Solution

Since Avorion allows arbitrarily scaled blocks, there is no way to predict what shape the model is going to have. Plus the model changes all the time when players extend their ships or get them blown apart. So how do we solve this?

I found that the best way to solve this dilemma was vertex-based ambient occlusion. This way it's baked directly into the model and won't change when the camera moves. The great thing about vertex-based ambient occlusion is that you don't have to apply a blur to the result. Instead, the "blur" comes for free via the interpolations the GPU does between vertices!

That means now we'll be shooting rays from each vertex into the model. In order to get the ray intersections fast we used the bounding volume hierarchies that we had already from our collision model. This way every ray cast has a complexity of O(logn), which is pretty much the best we can get. And we needed the bounding volume hierarchy anyways for collision, so there were no additional costs here.

I did a first take on vertex-based occlusion and it turned out better than I had expected:

In this picture I'm using 64 samples per vertex, counting only hits and misses. It shoots fixed length rays depending on the normal of the vertex. 64 samples had the best tradeoff between performance and quality, above 64 there was nearly no difference in the result, but the performance hit got remarkable.

You can see several artifacts of the vertex-based SSAO model on the right side, where the grey block fades from grey to pitch black, and also in the middle of the space ship where there are blocks that are entirely black. That's be cause the vertices of these blocks are actually inside other blocks, so all sampled rays hit and the occlusion is black.

And there was another problem: Blocks can have any size. Even super large block sides only have 4 vertices to shadow, so if you place a small block in the middle of a large block side, it won't have any shadows because its 4 vertices are simply too far away from any geometry that could cast a shadow.

Okay, how do we solve that? Well, we have to increase the resolution of the models. So: Tesselation! Since we needed the tesselation in the model to calculate the ambient occlusion, and some of our target hardware doesn't have tesselation shaders, we couldn't use a shader. Instead I wrote a quick algorithm that tesselates the sides of the of the blocks like this:

Then we generate the ambient occlusion for the tesselated model based on the previous approach:

Looks pretty good already! You can see that there are dark areas on the big cube around the small cube and the quality around the intersections between the small and the big block is a lot higher. There's even a dark area on the top side of the big cube where the main part of the space ship is.

You can also still see the artifacts of the pitch-black vertices, but it's already a lot better and we finally settled for this approach, since we thought it looked good enough.

Then we one last problem: The ambient occlusion algorithm used random ray directions to collect the samples. Every time a user adds a block to a ship, the ambient occlusion would slightly change and create irritating flickering. We solved this by creating a predefined array of 64 fixed ray directions, so there is no more randomness going on.

Vertex-Based Lighting

The best part about this approach: You can use it backwards for vertex-based local ship lighting! We cast rays from light blocks towards all vertices on other blocks to achieve a sweet local ship light effect.

Performance

The calculations for the ships in the pictures took less than half a second with -O3 on gcc. This includes tesselation, ambient occlusion with 64 samples per vertex and lighting calculations. While for these smaller ships it was blazingly fast, stations with thousands of big blocks can easily take 10 - 15 seconds to compute.

But we never had any illusions about the performance of large stations, so we moved the AO calculations into a separate thread. Now, when as the player gets near a station, the AO calculations are started, and while they're running the plain model is rendered.

Wrap Up

Alright, that's it! I'm sure there are plenty who know already about this stuff, but I still hope some of you guys learned something new today.

Cheers

- Koonschi

Koonschi's Twitter

Avorion Website

Disclaimer: Warning, this will get pretty technical. If you're not familiar with the terminology and computer sciency stuff, you might have trouble understanding.

I have spent a lot of time lately to change the internal model of the game from the Inheritance Model to an Entity-Component Model.

For those of you that don't know what the Inheritance Model is:
In the Inheritance Model basically all object types inherit some behaviour of other, more basic types.So for example in Avorion's model, you have a Ship type and a Craft type. Ship inherits from Craft - this means a Ship can do everything a Craft can. And a Craft inherits from BlockObject (an abstract object that is composed out of blocks, which is, in Avorion, everything except for loot and wormholes). This system can go very deep and usually you have some very basic object at the bottom. In Avorion this would be a basic object Entity, which has nothing but an index and a position. Now every other object would inherit from Entity, like BlockObject, which would then have other objects inheriting from it. So basically you get a hierarchy, which is wonderful, because you only have to code things once and then have them inherit from other objects. But it has one major drawback - it's not very flexible when it comes to adding new properties.

I first ran into problems with the Inheritance Model when I wanted to create ownable asteroids. Factions would be able to own asteroids or even fields, and players should be able to claim asteroids once they found them. The class Asteroid inherited from BlockObject - but the 'owner' property was located in Craft, which also inherited from BlockObject! At the time I hadn't thought about ownable asteroids, and now I had the choice between 3 alternatives:

1. I could implement a second property 'owner', just for the Asteroid class.
   This would be bad style - you don't want to implement the exact same logic twice. Like never. Ever ever. Seriously.
2. Let Asteroid inherit from Craft, which would make every Asteroid a Craft.
   That could make sense in some ways (maybe?), but I decided against it, as it would make asteroids pretty overloaded. Crafts have a lot of other stuff that asteroids simply don't need, like a cargo bay, crew, and some more stuff like engines or controls. Usually this wouldn't be too bad (it would never be used, so the user wouldn't see it, right?), but if you've played Avorion, then you know that there can be thousands of asteroids in just one sector. Having thousands of objects with unnecessary properties floating around, taking up memory, would just be stupid. Plus, it wouldn't keep things simple. You should always keep things as simple as possible.
3. Move the property owner from Craft to BlockObject.
   This would make every BlockObject ownable. While this could also make sense in some situations, I also decided against it. Basically this would mean that over time the BlockObject class would get loaded with properties, whenever I needed a new feature that might fit into some classes but not into others. Which might then be used in some inheriting classes and not in some others. This would be wasting memory again, and the BlockObject class would grow to some super-sized bloat of functionality that would be impossible get right.

Now this is a lot of problems for one quite simple feature. So I decided to heavy-heartedly drop the feature. But this kind of problem kept reappearing.

Fast forward to four months ago, I remembered that a friend of mine had asked me about the Entity-Component Model, and if I used it in my game. At the time I had never heard of it, but then I decided to look it up.
The Entity-Component model takes another approach of creating an architecture for games. Instead of having inheritance, where everything inherits from something else, you have one basic entity model, which only has an index. Then there are component objects, like Position, Velocity and the like. These components are then dynamically added to Entity objects to create game objects. The big advantage is that game objects can be made up of any components the developer would want. At first this seemed a little weird to me, as I had never thought of this before.

But then it hit me - this would be the solution to all those problems I had before! With the new model I could make the 'owner' property a component and then add it to all the game objects I wanted - I could even create some asteroids with an owner and some without! Or wreckages with an owner (where I had the same problem), or wormholes or ...

So what I've been doing over the last couple of months where nothing new came up was this. I restructured the game model of Avorion from an Inheritance Model to an Entity-Component Model. Now I can create new game objects very easily, which means new features will be much faster to implement.

This new model has even more advantages for Avorion:

1. Networking
   Now, that everything is made up of components, networking has been simplified. I can update single components of an entity, whereas before, I could only update an entire entity. When I wanted to update the position of say, a ship, I had to add all the properties of the entity to the update message, which created unnecessary networking overhead. (I know, this could have been solved smarter, but this would have involved writing A LOT of more code.)
2. Saving into database
   Components can be saved into the database more easily than entire entity objects. One table per component - I have yet to find a cleaner solution than this.
3. Separating server and client logic
   I can have components that run only on the server (like for loot or networking) and components that run only on the client (particle effects, sounds, textures, meshes). The solution I had before was pretty ugly and I don't think I want to talk about it a lot (it involved linking specific functions on the client and some on the server, yay c++!).
4. Performance
   And this one is a big one. I can now store all components of the same type in an array, so they're located next to each other in memory. When I update the scene, I first iterate over all position components, then all velocity components, and so on, which maximizes the use of the cache and instruction cache. This boosted up performance by over 1000% for some components!

On the other hand, what struck me pretty hard then, was that I realized that composition isn't a new approach at all and had been around for quite some years. So I felt a little dumb. I might have acquired some skill in coding over the last 10 years, but I realized that I'm still learning. And I learned a lot in these past four months.
So if I haven't bored you to death by now, if you have questions about the Entity-Component Model (maybe because you want to implement one yourself), feel free to PM me.

Oh, and uh, there's gonna be a new feature: Ownable asteroids.

Koonschi on Twitter
Avorion on Facebook
Avorion on IndieDB
Avorion Website