Tworenas Snapshot 001

So it is finally time! I think I managed to get a very stable minimal version ready that will serve as the foundation of all further snapshots. This doesn't mean it is not buggy. It is probably very buggy and might do anything from displaying these bugs to crashing to resulting in World War III.

So a few things before we get started: you will need Microsoft .NET runtime in order to execute the engine. Probably version 4.0 will do, but I'm not sure how Microsoft packages their distributables: do you get 4.0 from installing 4.5 or is 4.5 an add-on. Anyway, 3 or 3.5 won't do. You also need sadly probably the last version of XNA 4.0 that will ever see the light of day. Finally, you need a computer with a GPU that can handle XNA HiDef profile. In a couple of snapshots I might get around to providing two versions, one for HiDef and one for Reach. And one more thing: currently the engine is optimized to run at 60 FPS or higher. If you are getting lower framerates, physics might not sync up perfectly with this rate and it may seem less smooth to you. I'll try to make smoothness less reliant on framerate in the future.

There is one more important thing to mention: I did not manage to find time to create a configuration dialog, so the engine will run in 720p on high quality settings by default. You can press Alt-Enter to make it fullscreen and you can reduce the quality at runtime, but you'll have to do this every launch. Persistent settings are coming in snapshot 2, at least in the form of an INI file. Vertical synchronization is on by default, so you shouldn't see any framerate higher than your monitor's refresh rate.

BY AGREEING TO DOWNLOAD THIS SOFTWARE, YOU TAKE TOTAL RESPONSIBILITY FOR ANY CONSEQUENCE RESULTING FROM THE USE OR MISUSE OF THE SOFTWARE. I AM NOT TO BE HELD RESPONSIBLE FOR ANY POSSIBLE HARM THAT CAN BE CAUSED BY THE SOFTWARE NOR DO I GUARANTEE THAT IT IS FIT FOR ANY PARTICULAR PURPOSE OR THAT THE INTEGRITY OF THE SOFTWARE WILL BE PRESERVED WHILE BEING TRANSFERRED ON ANY AND ALL MEANS OF COMMUNICATION.

I hope that legal mumbo-jumbo is able to protect me from whatever ill consequence that may arise. Any piece of consumer electronics can break down and it would be a shame if by coincidence that would happen as someone runs the engine. This is very unlikely because it is not that heavy on the system and it should only get lighter.

Link: Snapshot 001

This isn't a permanent location for it. I know that it won't get any downloads so I can safely store it on my Dropbox, but when i think that something will get downloaded, I'll put it somewhere else so my Dropbox won't get clogged up :).

It is just a little bit too early to give you a  full list of controls. With snapshots 2 having more of a user interface, I'll leave snapshot 1 destined for guesswork.

Changelog: 

• Terrain is not longer a singleton. The engine officially supports any number of terrain objects, but for now only uses one.
• Terrain support has been moved 90% to the general purpose library. The library is now 440 KiB of code.
• Created a window creation helper component to make GUI code shorted and a primordial screen system to isolate game screens.

Bugfixes:

• Every single smallish bug I could find and fix.
• B003: Massive memory leaks in the new word manager. Every time you use it to load or generate a new world, some resources remain in use. Eventually you will run out of RAM. Fixed. 

101 – Snapshot 1 almost done

I order to make good progress on the snapshots, I am trying to give each one a theme or some major feature to keep me focused. It is very easy to go all over the place, do a lot there, but end up with nothing to show.

The theme for the first two snapshots (at least) is "a mad scramble to get the basics done". Snapshot 0 in particular was super mad, trying to get a bare minimum of systems working good and giving the engine a major smoothness overhaul. Snapshot 1 shares this theme, with again a major focus on smoothness. I'm not expecting any downloads on the snapshots, each one being more like a personal milestone, but if somebody does download one of the early snapshots, I want them to say "This has barely any features". I don't want them to say "This is an unpolished pile of shit". In the above scenario, that person has above average objectivity, because this is the Internet after all. No mater what quality you achieve, people are going to hate.

What I'm trying to say is that each snapshots needs to have one fairly polished and very smooth feature rather than a bunch of small incremental changes to 5 or more features. For the first two snapshot this feature was the terrain.

And I achieved major speed up on everything related to terrain. The change is so significant like replacing a 3 year old computer with a new modern one.

On top of snapshot 0's changes, I did a ton of new optimizations that resulted in added smoothness. But the major improvement was moving the tangent and binormal calculations over to the GPU. Not having to update these on the CPU has freed up a ton of resources. One small caveat is that the method by which tangents are computed is different, thus the terrain is just a little bit brighter. And I have encountered exactly one visual artifact. This can't be true and I'm sure there a tons of such smaller artifacts, yet this one is the only one I managed to find. Before screenshot:

After:

So the artifact is minor and I kind of like it. Makes the terrain just a little bit less ordered there.

Another thing I changed is the quality levels of rendering. I had a slightly outlandish and somewhat more polarizing shader set in use to render terrain. Initially it was a response to normal mapping not being strong enough, but eventually it got enhanced with a ton of stuff, like spherical harmonics and fancy detail mapping, so it kind of lost its original goal. Also, in the meantime I grew fond of a more traditional look for terrains. So I did a "back to basics" on the shaders, removed some of the bells and whistles and came up with a more comprehensive set of 3 quality levels: low, medium and high. The previous 5 were too much, especially since they defied a simple naming scheme. Quality 4 was not lower in quality as Quality 5, but it was faster. Now low has no normal mapping, medium has normal mapping and high has some extra effects for better contrast.

Low:

Medium:

High:

Now that the world is smooth enough, one question remains? How do you get a world? I could package a small world inside the snapshot. But that is just one world, plus worlds are really big. I can't put out weekly  300+ MiB package. Eventually snapshots will get over 1 GiB and by then I'll need to create an incrementally updating patch system. But I am getting ahead of myself. So I need a way to manage worlds. Introducing, the world manager:

I decided to go with a persistent world set. A world remains in your list until you explicitly delete it. But you can do anything with that world without deleting it, including deleting all the world content, regenerating it, doing major automated editing on it. So there is a major difference between deleting a world and deleting the data inside it. If you delete the world, it is gone for good and without a trace, together with you character, skills and inventory. Deleting the data just gets rid of your maps, so you can adventure on a new set of maps. Your character, inventory and anything that you have acquired remains. It is like moving to a new area of the world. In the future this might even be implemented and a world might have any number of regions.

The world manger can be brought up on its own or when exploring a loaded map and can load a new map asynchronously:

After first creating a world, or after you cleared the data from it, you are given an option to generate a new terrain:

The import option is disabled and not implemented, but it will allow you to load a heightmap bitmap in a number of popular formats in order to create a map. I will add support for normal grayscale bitmaps and also for floating point textures, in raw format of standard ones.

Map generation takes ages so it is good that it is asynchronous. OK, maybe not ages, but it takes a lot of time. My final hopes for this engine includes very complex procedural worlds and that might take up to 20 minutes of generation time for large ones. Currently the generation is slow because diamond-square algorithm is slow. I need to dig up my old Perlin implementation and use MT with it.

The world manager is mostly done, yet feature poor. It will evolve over time.

The main problem right now is that I am having some major memory leak issues.

Anyway, snapshot 1 is mostly done. I need to test it until Monday and maybe I can even get rid of some of the memory leaks. Snapshot 1 is going to buggy as hell, maybe even crash, but it is stable enough given the time frame.

On Monday I'll post again with the download link.

The theme for snapshot 2 is going to be "RPG". Snapshot 2 will introduce the concept of channel rate, mana, overcast, stamina, exhaustion, rest, a fully functioning (but for now quite small) skill tree, player stats and two implemented skills.

Changelog:

• World manager!
• Tangents and binormals are now computed in the vertex shader. This reduced memory consumption and greatly improved terrain editing and loading snappiness. A few minor visual changes resulted from this.
• With the new performance levels, terrain chunk streaming wait time has been reduced 10 times, making streaming far more responsive while keeping walking at all speeds snag free. On very strong computers, the wait time could be reduced, halved or even quartered.
• The number of terrain quality levels have been reduced from 5 to a more manageable and easier to understand 3. These quality levels avoid the more outlandish shaders and give a pretty "standard" look to the terrain.
• Massive speedup of map loading from disk. On my computer, for a 64 square kilometer map, it went down form 2.7 seconds to about 0.5 seconds. Reading floats from disk in C# is slow. Who knew? Still, physics creation in memory was yet not improved and it still takes about 2.5 seconds, so 3 seconds for the first load. After the first load, live streaming kicks in so you don't need to wait for load times.
• Using the above trick and applying it to terrain texturing streaming, I improved chunk stream in time from about 4.0 ms to 3.4.
• The chunk allocator is now capable of pre-initializing the buffers that will be in us, so every time a chunk that was in use before is reused, some computations can be skipped. And with an additional optimization round for those calculations, I reduced the average chunk load time from 3.4 to 2.8 ms.
• Changed the way MSAA is set up. It should give a minor performance gain for all levels of MSAA. If you are just about at the minimum specs to run the game without MSAA, this boost might be enough to allow you to run at around 60 FPS with 2x and rarely 4x MSAA.
• The game window restores mouse position after returning from another window.

Caveats:

• C003: Partially fixed, since stream delay time has been greatly reduced and chunk load speed increased.
• C004: Partially fixed, again by the improvements that helped C003. As a new addition, the streamer is now partially biased towards the camera position and will first try to bring in a set radius around the camera and then proceed to go from corner to corner. The radius is not yet large enough to cover the entire streaming area. Need to be made as big and ten I need to add frustum biasing. Once these two things are done, this caveat is fully solved.

Bugfixes:

• B001: Turning on physics debug information at he same time with SMAA causes render to fail. Only an one pixel thin screen diagonal gets some color rendered. Temporary fix: turn off SMAA when using physics debug information. Fixed. Was rendering the SMAA full screen quad in wireframe because debug physics sets the render mode to wireframe.

Bugs:

• B003: Massive memory leaks in the new word manager. Every time you use it to load or generate a new world, some resources remain in use. Eventually you will run out of RAM.
• B004: Loading a map right after generating one is inexplicably slow. A second load, loading a map generated some while ago or loading after a game restart loads at normal speed.

100 – Announcing "Project Tworenas" and second round of snapshots

Hello there! Long time no see!

Since last time, I've been up to several things, but most of them not related to this project. One thing that was related to this was a pretty successful port to DirectX 9. For now I won't be porting further because I do not want to replace the physics engine.

In order to pick up the pace on this project, I am starting weekly or sometime bi-weekly snapshots. The goal of each snapshot is to add functionality and stability at a fast pace, while minimizing random rewrites (which I am prone to) and trying not to break anything from snapshot to snapshot.

It is also time to distance myself even further from the "Dwarves & Holes" project, so it is my pleasure to announce my new project code-named "Tworenas". It is not a new project, just a rename. For months actually I had a "C:\Tworenas" folder with the engine install.

Which brings me to the first issue: the engine is installed there because it can't handle yet loading resources from a changing folder. This and a few other things must still be improved before the first snapshot, so this week I'll consider this one Snapshot 0 and I won't release it. Next week will be Snapshot 1, the first public release.

But what is Tworenas about? It is meant to answer two questions: can you take a 3D game level editor, add some classical RPG mechanics to it and make it fun? And can a physics playground be fun? I already know the answer to the second question. Even in its current limited state, skiing around and checking out the physics interactions can be fun, especially when they surprise you. I remember the first time I walked fast towards a barrel rolling down hill and without desiring it, my character climbed on top of the barrel and before you know it I was "riding" a barrel down hill. But I don't know the answer to the first. That we'll find out in a few dozen snapshots.

Each snapshot will have a changelog posted, even Snaphot 0. Below I will detail the changes from the last video you saw to Snapshot 0. Some snapshots will also get an "engine features" video.

Changelog:

• Terrain uses vertex buffers again by default. For larger terrains, this can speed up terrain rendering by a factor of 3-4. Terrain can now change on the fly between using vertex buffers and arrays on a chunk by chunk basis.
• Terrain has customizable anisotropy for both close and distant chunks. Setting these values low, together with the above mentioned vertex buffers use has greatly increased rendering speed, especially on weaker hardware. It is now possible to have 60+ FPS on Intel HD chips, albeit at low to very low quality settings.
• Natural physics reaction of objects to terrain shape change. When you raise or lower the terrain, objects lying on top of it will shift and slide naturally with the curvature change of the terrain.
• Terrain persistence: the entire terrain is streamed live to the disk when changing it. When loading the same map, all changes will be preserved, together with camera position too. This basically gives you a persistent load/save system. Maps in this engine are different from other games, because you can always edit them on the fly. This means two things: baking of map data is not possible, since baking takes a long time and editing should be done in real time. This means that everything about the maps must be dynamic, from creation to rendering with lighting and all effects. The second thing that is related to saving is that maps are big: a 64 square kilometer map takes up 512 MiB with one height point at each meter. If I were to double the resolution, a single map would take 2 GiB on disk. Such large maps can't be compressed. So in the first versions at least, the engine won't use a traditional quicksave/quickload feature, one in which a new quicksave is a new save on disk. The disk would fill up really fast, plus the engine prides itself in very low loading times. So the engine will use a map based quicksave feature. Anytime you do something to the map, from changing the terrain to dropping a barrel, the map will be saved. There is no going back to a previous save state. This is done in the background, so you don't have to wait for an on screen spinning icon to stop spinning like in a lot of modern games. And saving will be disabled during combat, so if you die you will get back to the point a few milliseconds before the combat started. Snapshot 1 will feature only terrain saving, without clutter saving.
• Major RAM optimization. RAM consumption is a lot better now, but it wouldn't hurt to get it lower. I am investigating Vertex Texture Fetch in order to store terrain data more compactly, but I am yet to figure out a way to compute normals, tangents and binormals based on a bitmap heightmap in the vertex shader. This computation must also be fast enough to be done each frame for large scale terrains that also use a heavy pixel shader.
• To preserve memory, terrain texturing has had each channel reduces from floating point precision to a byte. Currently, I couldn't find any visual difference between the two, indicating that 8 bits/channel are enough.
• Terrain is slowly starting to transition from singleton to multiple terrain object support. Once this is done, some interesting things are planned, like small floating islands.
• Individual terrain vertex updates.
• Added mouse event support. Also used this mouse support to try and fix some of the Neoforce activate/deactivate GUI inconsistencies when going from first camera mode to window interaction with mouse mode.
• Editing a single height point has become much more atomic. In the past the entire chunk needed to be recalculated. Now, smart offset computation algorithms allow one update to result only in a few vertex changes. Unfortunately, this doesn't work yet with tangents. If a tangent change is needed for terrain, the entire chunk must be recalculated.

Caveats:

• C001: Terrain in the engine is chunk based. This means that some editing operations need to update more than one chunk for a singular change. This happens on chunk borders. Editing terrain at chunk borders is slower than in the middle of the chunk. The worse case scenario is a chunk border where four chunks must be updated for a single terrain write operation. Possible solution: some optimizations can still be done to improve this, but the corner case will always be slower.
• C002: Edited chunks change from vertex buffers to vertex arrays in anticipation of further changes. Editing a chunk once is rare, the user will probably do multiple edit operations, so it is a lot faster to not initially recreate the vertex buffers. Currently, the vertex buffers are not recreated after an edit unless you walk so far away from the chunk that it is no longer needed and then you come back. This means that if you continuously edit terrain for long periods of time, increasingly more and more will change from vertex buffers to vertex array, slowing rendering somewhat and eating more RAM. Possible solution: Future snapshots will periodically go over the list of chunks and if a chunk hasn't been edited in the last N seconds, it is probably safe to change it back to a vertex buffer. Temporary solution: this isn't a major issue and is not a memory leak, since the maximal wasted extra RAM from arrays is deterministic and based on map size. If you feel that after minutes/hours rendering has slowed down noticeably and you suspect this is the cause of it, just close the game and reload. Reloading gets rid off all arrays.
• C003: Since large terrains require a lot of streaming power, chunk streaming is spaced out, making sure that not a lot of chunks are streamed back to back. With the addition of terrain texturing persistence, the time to stream a chunk has increased a lot. This is only noticeable on slower computers with slow/full disks. Possible solution: As a first fix I'll space out streaming even more, first streaming in the geometry, taking a few milliseconds break, then streaming in terrain texturing. In the future, streaming will be multithreaded.
• C004: Streaming is currently based on the whole region that needs to be brought in. This means that if you were to teleport to a random part of the map, streaming would start somewhere in your vicinity, but not guaranteed near you. It might take up to 3 second for the terrain under your feet to become visible. It is still there and physics works just fine, only you can't see it. This is not noticeable that much since you can't teleport yet. Possible solution: biasing streaming based on camera distance and frustum intersection, so the first chunk that is streamed in is always the one bellow your feet, then the ones in front of you, finally the ones in the back. Also, if a teleportation spell has a short period in which character control is taken away from you, like a mediation or spell cast animation, chunk streaming spacing can be reduced to zero, streaming in at full disk read speed. Animation plus a fade in/fade out effect should be fast enough to stream in most of the new surroundings so that no loading screens are necessary.

Bugixes:

• A ton of smaller bug fixes all around the engine in preparation for snapshot release. From now on, bugs will be given a code so I can track them.

Bugs:

• B001: Turning on physics debug information at he same time with SMAA causes render to fail. Only an one pixel thin screen diagonal gets some color rendered. Temporary fix: turn off SMAA when using physics debug information.
• B002: When skying at high speed, after landing from a high jump the character can rarely get stuck in the terrain. Usually the character will start rising up, slowly getting ejected from the terrain, but sometimes this won't work. Temporary fix: moving the camera around a lot fast while repeatedly pressing jump should free you.

99 – GUI guy

I've been away from town from Friday to Tuesday for a small family reunion and I barely managed to edit and upload this video:

Since the video is so commented I think I don't need to repeat everything in the blog too. Some small enhancements are still to be made (like a file selection dialog), but this is the base of the material editor. Another editor will be used to modify the meshes, assign materials and physics to them and preview them in a small 3D view. A third editor will manage the item lists, defining in game items and assigning meshes and other properties to them.

So let's talk about something else. In the past I used Ruminate for GUI. It is feature poor, slightly buggy and at places ill designed, but small and does the job. Still, a ton of work would be needed to bring this up to par. So I tried Neoforce. Neoforce has itself a ton of problems and I think that fixing them will take just as much time as fixing Ruminate, but Neoforce is much more feature rich. Imagine that you are trying to create a complex and distinct good looking GUI on top of an existing system. You could base it on Windows 3.1 or on Windows Vista. It is not guaranteed, but there is a better chance of getting a better result if you base your widgets on Windows Vista than on 3.1. This is a purely metaphorical example, but you get the idea.

So some problems with Neoforce:

• It is no longer maintained, neither for XNA 3 or 4.
• Getting it to run is a lot harder than necessary. Look at any forum thread and you will see that people have problems getting the damn skins to work. I can't make the skins work on the sample projects included, but I did manage to get them to work in my project.
• There are some problems with making the GUI active/inactive. I am using an imperfect workaround for this right now, but a perfect solution must be found.
• There are issues with focusing. Imagine that you execute two actions with side effects, A and B. If you execute them in this order, B will have a deterministic secondary side effect: a focus change. Now if you add a third action between A and B that touches GUI active state, so A > action > B, A and B will execute their side effect, but the focus change of B is no longer deterministic.
• The event chain order for focus loosing is wrong. If you want to create complex GUI you need to create more events than button presses. Things like actions being taken on edit and focus change are a must. Unfortunately the order Neoforce tigers these in a stupid order, making it impossible to do this.
• Calling Init on all widgets is awkward and stupid.
• There are strange things going on when making widgets larger than their parent.
• Porting this to SharpDX or something will be quite some work.

This is just from the top of my head not having touched Neoforce since Thursday. I'm sure there were more.

As you may know, I am a huge GUI nazi. I worked with GUIs all my life, designing both GUIs and GUI toolkits. I am one of those pretentious assholes who say things like "GUIs are art" and "nyeaaahh". So finding a GUI that satisfies my requirements is pretty hard. If I had time I'd love to fork and fix Neoforce.

Engine features 01 (A.K.A. I am really really done with the terrain; fo' reals...)

OK, a little bit latter as promised, here is the first video showing off engine features that are in a near final form:

First time doing any "real" video editing. Took me quite some time and hopefully my productivity and results will improve on future videos.

Since this video is late and I did not stop working meanwhile, I have enough new features for another two similar videos (but probably shorter) that I could record/post even right now. I still need to space out the content on the blog and YouTube, so today I am going the ignore the rest of the features and focus only on terrain.

So let me walk you quickly though the contents of the video. First I show the dynamic quality switching. It might be hard to tell, but every 1-2 seconds I change the quality of the terrain as I am moving around. I am fairly happy with the preset quality levels and any concerns are more stylistic than implementation related. The presets have predictable performance, with higher quality being slower, but unfortunately my terrain is bus capped so I can't get accurate GPU times on the rendering. A future version 2 of the terrain might use again vertex buffers to reduce the CPU time of passing the terrain chunks around, but this is fairly complicated since a complex cache system must be implemented. Terrain is meant to be editable in real time and creating/destroying vertex buffers is too slow for this. So this theoretical caching system should give timers to a chunk. If a chunk has been edited in the last N seconds it is very likely that it will be edited again, so no vertex buffer should be used. A chunk that hasn't been poked in ages should use vertex buffers. And the system should handle fast buffer migration for high speed terrain traversal. Complicated.

Next I show dynamic view distance. Again, every 1-2 seconds I increase view distance, from 7 to 19 (radius). Farther view distance is not really feasible, not because of the far plane, but because the terrain does not support LOD and is also bus capped, so after a point you spend a fixed and far too large time span just passing on blocks. More that it takes the GPU to render them. Version 2 of the terrain should have at least a simple LOD solution to approximately half the resolution of distant blocks, maybe even insert them into the same buffer.

Next is adaptive detail mapping. The engine supports this feature separately for medium and high quality terrain rendering, each with its own settings. By default for medium we have a distance of 700 and for high of 2000, but for the video I lowered it to 100 to show what the effect does. Alternatively there is a super fast variant of the algorithm that does not do anything for pixels outside the radius, instead of the smooth blending. This can boost performance somewhat, but does give a visible circular edge around the character. At a distance of 2000 this edge is only noticeable when you look for it, but by default I use the higher quality blending. Performance be dammed, look good!

Next is a new arrival: day and night cycles! I have a very complicated lighting scheme and making it behave consistently and also transition smoothly from day to night is a real nightmare. I am not 100% happy with the results, but it is a good start. The night is intentionally bright and clear.

And finally we have the personal light source/torch. During the day it over illuminates everything as it should and by night it gives good visibility for close-by objects. It was very hard to find a configuration that did not produce very desaturated/washed out colors on objects. Oh god, dynamic lighting is so hard. I don't like the way the point light illuminated the terrain though. It is unrealistic, with some points creating a wrong illusion of depth and facing. But I'll keep it like this for now.

With version 1 the terrain is finished. I did not show it in this video, but the terrain is still editable in real time, changing the height and texturing. I will try to release the source code of the core of it soon. I won't start working on version 2 of the terrain, which should one day allow for LOD switching and smart vertex buffer usage.

The next engine feature videos will show off the in game material editor and container/character inventory.

With everything going seemingly so well, it is important to mention things that don't work properly.

Number one is point lighting. It is just wrong. I have the feeling that there is somewhere a very basic error that permeates everything and once I find, it will fix everything. I upgraded the normal G-buffer to show normal-map enhanced normals, not just vertex based normals, and this causes the normals to rotate around wildly as objects are rotating. This clearly illustrates that there is a fundamental flaw in normals and the way point lights interpret them. 

Second is physics timing. The calculations I had in the past where wrong. I have fixed it but I'm not sure yet that the values are correct. With real values, physics actually is a huge performance bottleneck (it was before, only the measurements were lying to you). The good news is that I added multi-threaded support for physics and it scales very well with the number of cores, so if you have 2/4 cores instead of one you should notice a good improvement on physics times. The bad news is that I will probably have to scale back the map size. My i7 can handle the huge 64 square kilometer map decently, but slower machines might have a lot of troubles. Maybe even do a lot of small areas that are separated by caves and passages to hide the loading bars and limit the physics to only one region at a time.

Understanding texture compression - 01 - History & overview

I have achieved significant progress on the engine part and even some gameplay, progress that I'll be slowly showing using brand new higher production value videos, but I'm far too lazy to create such a video during the week. I'll try to do a first one during the weekend. Also, I am kind of overworking myself and I should take it easy and make sure not to burn out on development.

In the meantime, I'll write a short series of articles on texture compression. This domain of computer graphics can be incredibly complex and confusing and I'll be writing these articles as I am learning the ropes myself, so please excuse any mistakes I might make or poorly researched information.

So what is texture compression? Before we answer that, let's go more general: since textures are images in a format that is meant for very specific hardware to access (in our case PC GPUs), what is image compression? Traditionally you use image compression to reduce the size of an image when saved on disk. That's it. That's the primary motivation. Current storage oriented hardware is bigger and faster than ever, but you still can't ignore image compression. Back in the day, a 32 bit 640x480 (VGA) image occupied 1.17 MiB, which was quite a lot of memory for the hardware that was available then. A 1920x1080 (1080p) occupies 7.91 MiB. The width is 3 times as high and height is 2.25 times as high, so the area is 6.75 times larger, so if you do the math this makes sense. Today, in early 2013, a Samsung Galaxy 2 is a quite common and still great phone, but definitively last gen. It takes pictures with a resolution of 3264x2448, so a uncompressed picture takes up 30.48 MiB. This would eat up the relatively small on board storage quite quickly. But this doesn't happen because no one uses uncompressed images. The above mentioned images occupy hundreds of KiB or a few MiB based on compression and quality settings. Image compression is even more important in the case of video. Especially with upcoming technology  A 4K 3D video running at 48 FPS that would allow you to see The Hobbit part 3 on your future tech TV would have serious problems today, because it can't fit comfortably on a single optical media and has a bitrate so high that you can't stream it over the Internet (like on Netflix or something).

That was a fully unnecessary and yet too basic overlong introduction. Back to subject. In the case of texture compression  you don't care about the space the file occupies on disk (but you get reduced disk space as a bonus), but instead you care about occupied video memory. But there is an even more important benefit to compression: reduced bandwidth usage and better cache behavior. If you compress your 4 MiB image to 1 MiB, your GPU will access it faster, even if some form of decompression is needed for each individual access.

Taking this into consideration, several things that can be considered compression in general terms are not texture compression. Here are a few important conditions that must be satisfied and behavior the GPU will have:

• Texture compression is GPU oriented, so the GPU must receive the raw compressed data. If you decompress your image on the CPU before sending it to the GPU, you may be using less disk space, but you get no benefit from texture compression.
• The GPU will not decompress and cache the full data once it has received it. Doing that would void the reduced memory consumption and bandwidth advantages. So the GPU stores the texture in the compressed format and uses it like that when sampling.
• Texture decompression must be fast. Since the GPU accesses the raw compressed data when it samples a texture, this process must be fast.
• The GPU needs fast constant time random access to any point of the texture. So streaming compression  where the image must be decompressed in a temporary memory location on accessed until the desired pixel is reached is out of the question.

So it seems that creating such a compression format is no easy task. Something like a simpler JPEG compression can't be used. The scheme must be a lot simpler but still give good compression results. A 10% reduction is size is not good enough to outweigh the cost of decompression.

A long time ago, in a galaxy far away, a company called S3 Graphics that used to produce graphics chips laid the foundation of a compression scheme that is both in use today and was the foundation for other techniques developed in the meantime. They developed the S3 Texture Compression algorithm (S3TC for short) and presumably only their graphics chips could decompress from this format. It was a block based algorithm. The image was split into chunks of 4x4 pixels. There were multiple variants of the method, each suited a different purpose, but the main idea was the same: you would store two key pixels with a high bit depth and the rest would be approximated by storing the difference between the color that was stored and the  key colors, using a low bit depth. This was based on the observation that over small surfaces there is generally a smaller change in color in most images. But why does this give high compression ratio? A 4x4 block has 16 unique pixels, so it would consume 64 bytes. How do you encode 64 bytes in far less bytes, using a algorithm that is fast to decompress? Well you can't. Not unless you use lossy compression. And S3 chose a very lossy scheme. I'll detail all the schemes soon, but for now it is enough to mention that this compression would always result in a fixed compression ratio of 1:8 or 1:4. That's right, the 64 bytes block would be compressed as an 8 byte block. Needless to say, this worked on some images better than others and there are tons of cases where you shouldn't use this compression.

The block structure satisfies nicely the condition of GPU decompression. It has fast constant cost random access because for a coordinate you can easily compute the block location. Decompression is very fast because for a block the decompression algorithm is a fixed set of arithmetic operations without any branching. It also takes advantage of a very common  scenario: when rendering a textured polygon, a texture sample operation will almost always be followed by another texture sample operation for a near by texel (a texel is a texture "pixel"). This meant that decompressing the block and storing the result in cache would greatly improve performance and would have a very low rate of cache misses.

So texture compression seems very advantageous, even with the reduced visual quality. Especially since when it was introduces, video memory was very low. Today you can easily buy a GPU with 2 GiB of on board DDR5 RAM, so memory consumption is less of an issue but memory bandwidth is still as important as ever. Probably even more important as it was, because RAM is falling behind and when compared to the instruction execution speed on modern CPUs/GPUs, memory access is a performance bottleneck.

But what use was this method if it only worked on S3 chips? Especially since S3 is no longer producing such chips? Well, other chips/APIs stated adding reliable support for texture compression and paying royalties to S3. And this is the last thing I'll mention about S3 because I probably got the entire history part messed up and S3 will try an sue me.

OpenGL added support to S3TC starting with version 1.3. They kept the name and supported it with the "EXT_texture_compression_s3tc" API or extension or whatever OpenGL uses in these cases. I am not targeting OpenGL so I won't talk about it anymore. DirectX also adopted the technique starting with DirectX 6.0. Ahhh, I remember DirectX 5.0. It sucked :P! In a move completely atypical for Microsoft, they renamed it to DXT.

DXT came in 5 variants: DXT1, DXT2, DXT3, DXT4 and DXT5! I'll summarize the differences between them in the following table:

Method	Components	Encodes	As	Premultiplied	Bytes
DXT1	3/4	RGB, optional A	RGB(5:6:5), A(0)/A(1)	N/A	8
DXT2	4	RGBA	RGB(5:6:5), explicit A(4)	Yes	16
DXT3	4	RGBA	RGB(5:6:5), explicit A(4)	No	16
DXT4	4	RGBA	RGB(5:6:5), interpolated A(8)	Yes	16
DXT5	4	RGBA	RGB(5:6:5), interpolated A(8)	No	16

I love making HTML tables!

OK, now let's try to understand the table. In part two I will go into a lot of detail regarding the structure and implementation of each method, but really the information in the table is all you need.

DXT1 is the base of all methods and is the simplest, while DXT2-DXT4 are very similar in structure and build upon DXT1. The last column of the table gives the dimension of the block in bytes. Since an uncompressed block takes up 64 bytes, this means that DXT1 provide a 1:8 compression and uses 4bpp (bits per pixel). The rest of the methods provide a compression of 1:4 and use 8bpp. This is why compression gained traction: you are compressing a normally 32 bits per pixel image to 4/8 bits bits per pixel image. In the case of 24 bpp images that don't have an alpha, when compressed with DXT1 the ratio is 1:6.

Now that we understand the basic size difference let's see what we actually encode. Images can have several channels and we traditionally work with images encoded in the RGB format that has 3 channels one for red, one for green and one for blue. These channels use 8 bits normally, but in very specialized graphics processing they can use more. You can also have a fourth channel specifying the transparency of the pixels, the alpha channel.  This fourth 8 bit channel creates the very common RGBA 32bpp pixel format. All DXT format are for channel formats that encode RGBA, with the exception of DXT1, which is either opaque, having an alpha of 100% and encoding only 3 channels, or it can optionally encode RGBA, but the alpha channel of a given pixel can be either 0% (fully transparent) or 100% (fully opaque).

Now that we know what is encoded, the question how is it encoded remains: the fourth row in the table. All DXT methods encode the RGB components in the 5:6:5 format, meaning that green uses 6 bits, while red and blue only 5. DXT1 uses 1 bit for alpha to signal 0%/100%. DXT2 and DXT3 use 4 bits per alpha, while DXT4 and DXT5 use 8 bits. This is where the interesting part starts: since DXT5 uses two times as many bits for alpha then DXT3, it should consume more memory. But if you look at the final column, they both use the same memory. This is because they store alpha differently. DXT2/3 use explicit alpha, each pixel having one 4 bit component to store the value. DXT4/5 use interpolated alpha, using a scheme similar to DXT1 RGB compression: two key alpha values are stored at high bit depths and the rest is interpolated and the difference is stored with low bit depths. So even though DXT5 has more bits per alpha, these values are not explicit. Each pixel does not have its own alpha, but on interpolated value.

Let's skip what premultiplied means for now and give a few key guidelines and observations about these methods and which you should choose.

One key observation is that all 5 methods encode RGB data the same way and provide the same quality. So if you don't care about alpha values, you should always use DXT1 because it as the best compression ratio. This also has a downside: if your DXT1 compressed RGB only image looks like crap with DXT1, you can't switch over to DXT2-5 to get a better quality. The RGB encoding is deterministic across all methods. With one exception. Say you care about alpha, but one bit is enough and you use DXT1: the RGB encoding will look worse that DXT1 without alpha or DXT2-5. The extra alpha encoding reduces the RGB color space. So if your DXT1 looked bad, your DXT1 with alpha will look even worse.

Now let's start caring about alpha. If 1 bit is enough consider DXT1. You will probably need to apply and alpha threshold in the pixel shader to compensate for some unwanted black borders, but it will work. But if the RGB quality drops in a disturbing way by adding the alpha bit, you can consider DXT2-5. Or you must consider DXT2-5 if you need more than 1 bit.

And the rule here is very simple: DXT3 is good at images with sharp alpha changes while DXT5 is good at images with smooth alpha changes, like alpha gradients.

And finally let's address the elephant in the room: premultiplied alpha. DXT2 and DXT4 use premultiplied alpha. This means that the alpha channel is encoded as is (like in DXT3 and DXT5 respectively), but the RGB data is considered to have been premultiplied with the alpha before encoding. So choosing DXT2 over DXT3 changes only the values of the RGB components. In practice it turned out that there was not a lot of use for premultiplied alpha. So little in fact that when the DXT reform occurred  these two methods were left out. So don't sue DXT2/4 unless you have really good reasons for it.

The DXT reform renamed some methods and added a few more to solve some common problems.

DXT, while pretty good, is not 100% general. It gives poor visual results when used with a lot of photographic materials, very detailed textures, smooth gradients, large color variation, diagonal detail, a few very specific images where the blocked encoding aligns very badly with another blocky pattern resulting from the content of the image and... normal maps! Normal maps look absolutely horrible when compressed with DXT and give rise to a typical blocky bump mapping effect. Newer compression method address some of these issues. 

But people are clever! Long before the new methods were created and incorporated into newer consumer level hardware, people came up with ways to fix, at least partially, the shortcomings of DXT.

Let's take normal maps as an example. DXT is generally a 4 channel compression, but not enough bit depth is available for the 3 channels of a normal map that needs very smooth transition between normals that are meant to follow a surface. One clever trick is the so called DXT5n(m) (I'm not 100% sure if DXT5n and DXT5nm are the same format). What is DXT5n? It is DXT5! There are absolutely no differences between the two formats. Except for what you store in them. Instead of writing the 3 components of the normal into the RGB channels of the image, you move the red channel to the alpha  you keep the green in place and fill the now unused red and blue channels with the same color. The alpha and green channels have a higher bit depth thus saving becomes less lossy. Since DXT is based on saving differences from two key colors, filling red and blue with the same value minimizes unnecessary differences and creates better detail precision. The final component of the normal is computed in the pixel shader since normals have a unit length of one. The benefit of texture compression generally outweighs the extra cost of the third component calculation. This is a clever trick that can make more normal compressible with good results than DXT1, which generally fails to give good results. But we are saving only 2 channels in format created for saving 4 channels. This method would greatly benefit from a compression format optimized to store only two channels with greater bit depth than DXT. Foreshadowing!

But normals are not the only thing that can be improved. How about plain RGB images? What do you do when DXT1 (and thus DXT2-5) give poor results, full of artifacts and what not? You use another clever trick! Normal DXT1 is a 4bpp format and we want to get comparable results with greater visual quality. For this we first convert the image to YCbCr format: a luma component followed by blue difference and red difference chroma components. We save the luma in the green channel of DXT1 texture. We encode the Cb and Cr into the alpha and green channels of another texture saved as DXT5. The first texture will already use the same storage space as our entire DXT1 image, that is it will have 4bpp. And we still have a second texture that will be stored at 8bpp, for a total of 12bpp! Not to mention another sampling cost! Not a good idea. The trick here is to down-sample the CbCr texture so that under the new resolution it is effectively 2bpp, giving a total of 6bpp. We can even do another trick, sampling the second image at a lover mip-map level. While the memory consumption is still 6bpp, this will behave more like a 4.5bpp. This improves quality a lot over DXT1 but is still not as great when DXT1 really doesn't like you input image. How great it would be if we could use a format optimized for saving 1 channel images and one for 2 channel images! More foreshadowing!

As you can see, DXT is not that hard to understand and master. The real challenge is to compensate for its weaknesses with all sorts of tricks!

As a final point, let's go over that DXT reform I mentioned earlier. More precisely a DirectX change. Direct X is actually dead. For quite some time now! Out of inertia/misinformation it is still commonly refereed to as DirectX, but what it actually is, the part that is evolving is Direct3D. Initially a sub-API of DirectX, Direct3D is the only rendering part that gets attention. The DirectX SDK hasn't been updated in quite some while, causing some unnecessary panic. How do you get the new versions of Direct3D SDK? Well the Direct3D SDK has been more or less silently incorporated into the Windows SDK. So anyway, Direct3D is evolving, and Direct3D changed a few things in the domain of compression.

It renamed DXT1 as BC1, DXT3 as BC2 and DXT5 as BC3. DXT2 and DXT4 were left out because of their low use.

From DirectX 6 to DirectX/Direct3D 10 new formats were introduces by different manufacturers. 3Dc+/ATI1 was created and is a block format very similar to DXT but it only encodes 1 channel. 3Dc/ATI2 encodes using a similar method 2 channels. ATI1 became BC4 and ATI2 became BC5. Using BC5 for the normals encoding trick described a few paragraphs above gives the best quality compressed normal maps available and BC4 and BC5 can be used for the two image YCbCr trick again with great results. 

Direct3D 11 added BC6 and BC7, two formats what are very complicated  but when used correctly the give extremely good results. Better than BC4/5. I will ignore them, especially since XNA is Direct3D 9.

So let's summarize in a new table:

Method	Components	Encodes	As	Old name	Bytes
BC1	3/4	RGB, optional A	RGB(5:6:5), A(0)/A(1)	DXT1	8
BC2	4	RGBA	RGB(5:6:5), explicit A(4)	DXT3	16
BC3	4	RGBA	RGB(5:6:5), interpolated A(8)	DXT5	16
BC4	1	1 channel	(8)	ATI1/3Dc+	8
BC5	2	2 channels	(8:8)	ATI2/3Dc	16

This article really didn't turn out the way I planned, but I'll go with it anyway. Part two will go into more detail regarding BC1-5.

98 – Terrain? More like ter-done! Am I right??!

I think I finally finished with the base of the terrain texturing!

I refactored the terrain shaders, using a very modular approach  with tons of function calls and a clean design. I sure hope that the shader compiler is really good. If not, a final version of the shader might have to be written someday that flattens out the implementation and uses all manner of optimizations.

I also started using branching heavily. I am using both good and bad kind of branching. The good one relies on constants passed to the pixel shader body and I am pretty sure the compiler does compile time evaluation of the constants and removes unnecessary branches from the code. The bad kind of branching is the use of run-time "if"s in shaders. GPU really don't love branching. Pixels are evaluated in a clustered fashion and branches can cause the entire cluster to wait for a sync. This can be mitigated if there is a high probability that all the parallel shaders executed for the cluster will take the same path. I done some testing and the results are inconclusive, maybe tending to go a little bit toward having lower performance if I use branching, even thought the body of the branch that is skipped is more expensive.

Using these methods I created two shader implementations, one very basic for the low quality and one that handles higher quality rendering. These are further parameterized with compile time flags to create all variants that I need. I also managed to greatly optimize the implementation, giving a 10-15 FPS increase on weak hardware. On strong hardware I can't tell, because currently I am bus capped.

I also implemented adaptive detail mapping, allowing you to specify a radius for detail mapping. Medium quality setting use this, not for the performance, but because it reduces repeating patterns in terrain somewhat. On high I am not using it because the small performance gain is not worth it when compared to the quality loss. It is a high quality setting for a reason.

The final step was to do something about the view distance. I determined that the landscape looks the best when I use a very distant and aggressive fog. The farther the fog start is, the larger the terrain seems. The fog is exponential and does a good job (but not a perfect one) of hiding polygons entering though the far plane. This small pop-in is so minor that you won't notice it unless you are really looking for it.

One thing that I need to dos till is make the view distance adjustable at run-time.

Using all the above I finished my hardest task: out of the dozens of permutations, choose only 5 quality settings. This was ridiculously hard because all were tough compromises. Just now I changed the spherical harmonics computation just like that and I'm not sure which one I like better. Anyway, there are 3 quality settings: low, medium and high. You can also choose to have enhance the harmonics for better quality, but this does not work for low quality, thus giving 5 quality levels instead of 6. I am fairly happy with these setting. I also made sure that they have comparable color warmness and intensity, but some minor differences are present.

Here is a video showing a 64 square kilometer map with small view distance at maximum terrain quality, large item density using 8xMSAA and SMAA while the character is running at very high speed traversing the map not quite diagonally (I wanted to go from corner to corner but I messed up :) ):

Now that the terrain shaders are finished (I hope) I need to add day and night cycles to it and see about those lights.

For the rest of the post let me entertain you with some very interesting shader variants I managed to produce:

These are not photoshoped or using any other textures than the one from the video. Just a shader variant that produces strange colors a more wet look:

If I ever need an alien looking landscape  I know where to start. I did not manage to produce workable shaders out of this method because the output is too noisy and weird in lot of places. It also has pretty bad temporal aliasing.