Saturday, May 26, 2012

A Slow Week

Hey Readers,

It's been a slow week this week. I had the flu over the long weekend and my son picked it up during the week. Now that I've gotten the OSM data rendering, my new goal for the project is to try and get the whole Earth rendering. I've decided to use the SRTM dataset ( found here http://www.cgiar-csi.org/data/elevation/item/45-
srtm-90m-digital-elevation-database-v41) for my coarser elevation data.

To render the data I started implementing Chunked LOD. With chunked LOD the basic idea is to stick chunks of data into a quadtree with only at most a difference on 1 level of depth between each neighbouring node of the quadtree. I managed to get as far as implementing the general quad tree for the current terrain data I have rendering. It really made a huge difference in performance not regenerating all the data every time I moved across chunk boundaries. Even without threading the terrain generation I was getting pretty well realtime performance generating the data. Each node in the quad tree is 32x32 voxels, down to a resolution of about 1 meter x 1 meter for each voxel.

The next plan is to split the data into courser grained chunks. So for every couple entries of depth in the quad tree I'll have a chunk of elevation data to use to generate the terrain. I'd like to take a step back from what I currently have working and actually get the full earth rendering and then try to step through going deeper and deeper into data to the resolution that I'm currently rendering at.

Sorry about the screenshots this week they're not much to look at since it's been a slow week and mostly infrastructure changes. Next week will be much more interesting!

The black lines represent the nodes of the quad tree.

More nodes over the water.



Sunday, May 20, 2012

So Many Places To Go, Nodes To See

Hey Readers,

The past two weeks were all about OSM files. What are OSM files you ask? They're the files exported from Open Street Maps, they contain all the information you need to map out a city. Open Street Maps provide large files broken up by country / province/ state, or you can use one of the API's provided to download a finer grain chunk of data. To get the initial implementation going I downloaded a chunk of data equal to the DEM I'm currently rendering out. The OSM files store the data using the XML format. This means that the files are huuuge for even a small chunk of the earth. For the area I'm currently rendering the OSM file was about 110 MB. 110 MB is was way too big for my current needs.

The OSM files are fairly simple, they're broken up into 3 types of object Nodes, Ways, and Relations. Each of those objects can also have Tags which provide information about what they are. A node is a point in space, ways are made up of nodes, and relations are a collection of ways.

Since I only needed a subset of the data I set about making my own format which could be stored as binary. For the nodes, all I needed was the node id, longitude, and latitude. For the ways all I needed was the way id, and a list of node Ids, I haven't had a need for relations yet so I'm ignoring those and for the tags I'm storing a pair of values, the id of the object the tag belongs to and a hashed version of the string. After saving out all this data the file size went from 110 megs to about 8 megs. In the future if this is still too big there's still a few more tricks I could do to drop the size some more but for now this is very workable.

I spent about a week getting the data saving and loading into the game. The next step was to get the nodes rendering. I started drawing them as debug boxes but the game came to a crawl with a couple hundred boxes being drawn. This was no good! The problem was that my debug drawing was not optimized at all. I set about fixing my debug drawing by batching all the debug boxes together so they could be drawn with a single draw call. Now that I could draw around 2000 nodes without too much impact on the frame rate, the next optimization to make was to only draw the nodes that were visible within a certain radius. Down the road I should hook up frustum culling but for now the simple radius check is enough to get things going. After this I took a stab at getting the ways rendering. This wasn't too tough I just drew a line between all the nodes in each way. Seeing the nodes and ways rendering was exciting it was starting to feel like the world instead of some random landscape.

Next on the agenda is to clean up my terrain mesh subdivisions and  start getting the neighboring DEM's loading so we can get the whole planet rendering.

First shot of nodes rendering

Shot of ways rendering

Another shot of ways rendering

More ways rendering!

Saturday, May 5, 2012

A Whole New World

Wow! It's been a long time since my last blog post, sorry readers it's just been a busy couple weeks. With a baby here it's a lot tougher to find the time to write for the blog. So, there's been some big changes to what I've been working towards with the engine. It all started when a friend of mine was visiting from out of town. He told me he had an idea for a game, usually I don't take much heed in these kind of suggestions but this one got me thinking. What he suggested was that it would be fun to have a racing game based around Google earth. So you could essentially race anywhere in the world. He thought it'd be fun to get the GPS coordinates for his morning commute to work and be able to create a virtual race out of it which he could post the coordinates online and then use it as a race track online.

So this got me thinking, someone must have created something like this before! Sure enough there's a few basic flash games, but not much substantial. So I started digging into what google provides as an API for querying their map data. Unfortunately its very very restricted, so I pretty much immediately threw that out the window. I started digging into open source alternative datasets and this turned into quite a rabbit hole! I found OpenStreetMaps which provides open source maps of the world to do with as you'd like. This gives me all the street data that I'd need to get my project moving but that wasn't enough for me. Given the voxel nature of my engine I wanted elevation data, I wanted to create a virtual voxelated earth!! 

So essentially the game would be a cross of 3 different games. 

Cube World( for the visuals ) http://wollay.blogspot.com
Outterra( earth simulator ) http://outerra.com
Final Lap Twin( for the gameplay ).http://en.wikipedia.org/wiki/Final_Lap_Twin

So the first step was to have a look at the data available from Open Street maps. I downloaded the data for British Columbia and it was huge! 5 gigs of data! It was tough trying to find anything that would open it so the first step was to split it up into some smaller files. I wrote some quick code to split it up and had a look. The data was stored in an xml format so it should compress quite nicely when I convert it to a binary format. Since Tiny XML would choke on this giant file I put the OSM data aside for now and started digging into elevation data, there's a lot of different options. GMTED, SRM, after more digging I found this site http://www.viewfinderpanoramas.org/dem3.html.  It's pretty much the goto place for elevation data.

My goal is 1 meter by 1 meter resolution and the DEM files are roughly 20 meters by 20 meters with a 1 meter resolution on height. My inital attempt was to render the DEM files as voxel sprites. Needless to say trying to render a 1201x1201 * 20 voxel sprite blew up immediately, not enough memory to create the vertex buffer. I figured as much, so my next attempt was to split things up into 128x128 chunks. I was able to get 5 chunks rendering at a time, this wasn't really enough to make this plausible.

So I had to rethink how I was going to render this massive amount of data, thats when I thought to try splitting the data up into a quad-tree structure. So the closest chunks would be at 1m x 1m, next set would be 2mx2m, then 4mx4m and so on and so on. I split the terrain up into 32x32 blocks and this worked great. There was 2 downsides though, memory usage was still way too high and it took about 6 seconds to regenerate all the blocks every time the camera moved to a new chunk.

The first thing to do was to throw the generation into a separate thread. This at least got rid of the massive 6 second hitch everytime things had to be regenerated, but it still meant we had to wait 6 seconds to see the new terrain data. So I had to start optimizing my voxel generation code. This was kind of a win win because it also meant that my regular voxel sprite generation would get the benefits. So I started rejigging how the data was stored and trying to optimize for maximum cache efficiency, this was about a 2 week process that resulted in a drop from 6 seconds to 1 second! This was much more reasonable but it still wasn't quite what I was looking for! I wanted real time generation at most a frame of lag. So I had a goal 33ms generation time, maximum!

This meant it was time to rethink using voxelsprites for the terrain. I created a new class called TerrainVoxelSprite which initially was a duplicate of voxel sprite. I had an idea to speed things up. Since I was using DEM's for the terrain and they're just a height why not just store a set of height values rather than a true chunk of voxel data. Then when rendering, still render everything as boxes so it looks voxelated. Not only does this cut down on memory but it also sped things up consiiiiderably. I decided to cut out the color data out of the vertex, to improve memory usage even more. With a few more optimizations I finally had my 33 ms generation time and I was able to load the entire 1201x1201 dem into memory as voxelated data. But wait you say, it's not really voxels anymore!! True but my plan is that if the user wants to edit a chunk that chunk of data can be swapped out to a voxel sprite without anyone the wiser. With the massive amount of space it would take a loooong time for users to change everything into voxel sprites.

Now that I had things running the way I wanted at the speeds I wanted I could finally spend some time on the shaders. I went to work implementing some initial lighting, applying some color based on height and an initial distance fog implementation. It's not much to look at yet, but it's a start.

So that's kinda the quick gloss over of what I've been up to for the last two months. Moving forward I'll try to go into more detail on the various parts of the new codebase. If you guys have any questions or interest in a particular area of the dev, let me know in the comments!

An early attempt using voxel sprites
Starting to get more terrain loaded, generic colors
Starting to play with colors a bit more
Here's where we're currently at with some lighting and distant fog. A nice shot of all the visible terrain
Another shot, this time down closer to the terrain.