Lots Of Little Updates

 Hey Readers,

I've spent the last couple weeks wrapping up all of the SRTM stuff. So in my last post I had started working all the data through the SRTMSplitter tool. One thing that I had noticed was odd was that it seemed like my units of data was way off, like all the elevation seemed way too high. I realized after spending some time poking around in the math that nothing was actually off, the reason that the elevation seemed so high was that because we were viewing all of North America at this scale it makes the high's in the terrain seem way higher than when all the data is zoomed in close and becomes spread out over a huge distance. So for the time being to counter this while I'm testing out the different levels I've just scaled back the height values.

I also spent some time getting some better camera controls in. Previously all I had was the ability to look left,right and move the camera forward/back/left/right/up/down. This kind of sucked though when I was trying to view the terrain from really high up. I had to pull the camera way back to see anything. I had already put some code in place for doing this but it seemed my math was slightly off because the view went totally wonky when I started adding the rotation around the x-axis( looking up/down ). To solve the problem I had to rejig the math so that instead of using a 6 degrees of freedom camera system it was more of a first person camera system so the camera can never rotate around the z axis.

With the camera updates out of the way the next thing I thought I'd work on was getting the multi-threading working again with the new terrain tree system. The idea was that I have these builder objects which are passed through the terrain tree and at each node they collect the necessary data to build the voxel data for that node. So I set up a BuilderThread object, how it works was that every frame the main thread queries the builder thread to see if it's ready to accept a new collection of builder objects. If it is ready then the new collection of builder objects is passed to the builder thread. The builder thread then starts building up all the voxel data. Once the thread has finished a flag is set so that the next time the main thread queries, all of the data which needs to be built on the main thread gets fired off and the cycle is complete ready for a new set of data. I had some problems with popping terrain but I just had to re-juggle when I was creating and destroying terrain chunks. Basically what I did was to always keep the parent terrain chunk around so that if we destroy the children we have something to pop back to when we render.

One more thing I had to take care of was splitting the terrain based on the distance of a node from the camera, this is the way chunked lod terrain works. I worked it out as an equation where there's an inverse relationship of the dimensions of a node to the distance from the camera. After a little bit of tweaking the equation I had it working perfectly how I wanted. It was a good thing I had the threading working because with the new splitting there was a lot more terrain splitting going on then the simple quad tree splitting that was going on before.

Now I was running into performance problems again. One of the big issues was a huge amount of overdraw. The problem was that when I first got the voxel terrain sprites working I didn't spend any time getting the skirts of the boxes working properly so every box with a skirt had it's skirt being rendered all the way to 0 m above sea level. It was a super simple fix I just had to tweak my function that was generating each block of terrain so that it was calculating the skirt based on the lowest level neighbour. This gave me a significant performance boost, enough that I could keep going on adding more functionality.

So the last thing I spent some time with was the rendering. I had been spending so much time getting this new functionality in but no time with how the demo was looking. So I spent some time retweaking the fog, the sky color, and the terrain colors so there's more of a gradient and the colors make more sense. I chose yellowish for near sea level, green in the midranges, and white for the highest elevations.

File IO Frustration!

Hey Readers,

It's been a litle while since my last post. I had a hell of a time trying to get my tool working which would split up the SRTM data into custom sized chunks. I should start from the beginning though.

So the first step was downloading all of the SRTM data. The data is stored in archives which are 5 degrees by 5 degrees and 6000x6000 resolution. What I wanted to do was  write a program which could process all of this raw data. Ideally the plan was to split the data into an image pyramid of sorts where at the top we would have 90 degree by 90 degree chunks down to the lowest level being 1 degree by 1 degree. My thought was to store the data in 16 bit 1 channel dds files with a resolution of 1024x1024. I figured that was a good size for GPU consumption. I started writing a program that would make a system call to use winrar to decompress the data into a temp directory and then clean it up afterwards so that I wouldn't have to decompress all the data at once.

The first problem I ran into was that the raw SRTM data was an ascii format. This meant that parsing it took forever. Since I wanted to be able to parse it quickly to convert to different resolutions I needed to write a tool which would do the conversion. So I wrote a quick tool which parsed the ascii file and converted it to binary and then rezipped the archive for more compact storage. This also cut the filesize quite a bit though the zipped archives stayed around the same size. The tool averages the pixels when downsampling by sampling all the possible pixels taht would cover an area and just doing an average. It currently only takes into consideration downsampling, I'd like to add proper upsampling via bicubic filtering in the future.

While I was writing my ascii to binary converter I came across two facts. One that the srtm data I was using wasn't able to be used in any proprietary software and two that the free to use SRTM data was already in a binary format. I decided to stick with what I've got for now and just make the pipeline flexible enough that I can drop in a different dataset down the road. I wanted to set it up as flexible as I could in case anyone wants to add custom datasets.

Once I had all the data converted to binary I started work on the tool for generating the final DDS files I wanted to use. My first stab at it kinda worked, but it seemed to be reusing the same data for multiple tiles. I started dumping lots of debug text trying to look for where the indexing could be going wrong. I tried clearing out the source data at the beginning of each copy, this got rid of the duplicate tiles but didn't explain why the proper data wasn't coming through. The loading was successful but for some reason when it loaded the data from the file the data just wasn't coming through.

This had me scratching my head, my initial thoughts were that maybe the file wasn't fully unpacked from the zip file when I started loading it or conversly maybe it was being half erased by the cleanup operation of the previous data.  This was a bad week as my 3 month old son was sick so I didn't get any sleep.

After a week of hammering different things trying to get the data to come through I still wasn't any closer to an answer. What a set back! I didn't understand what could be going on. The solution was stupid, it turned out there must be some kind of problem with c style file pointers when opening that many large files in succession. I still don't have an answer for why it wasn't working, I was properly closing the files after I was done with them so it wasn't that. Anyways converting my FILE* to ifstreams did the trick, it immediately started working as I expected aside from a grid of black lines which was just one pixel in width and height that needed to be tacked on to my downsampling .

So now I finally have an earth size dataset at different resolutions. The next step is to change my elevation quad trees to start sampling from the different levels of textures the closer the camera gets to the earth.
 

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.

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!

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.

Now You're Editting With Power

Hey Readers!


What a busy week it's been, I've gotten a ton accomplished. The focus for this week was all on the tools, in particular the tools associated with editing a voxel sprite.

First up was some bug fixes I needed to get out of the way, I cleaned up the grid rendering for each layer in the voxel sprite, it was rendering a couple more lines than it should have been. The other bug fix was to do with the mouse drag selection in tile placing mode, it only worked for a single layer, so I extended the selection box to select all 4 layers. It could still use some improvements though, it only really works for selecting tiles when looking at the level head on.

Next up was figuring out what tools I wanted to add for edit mode. The tools I decided on were as follows:
    Draw Point
    Draw Line
    Draw Circle
    Extrude Layer
    Load From Image
    Extrude Layer by Color
    Switch Grid Axis
    Fill
    Slide Layer Up
    Slider Layer Down
    Toggle Draw/Erase

Once I had an idea of the tools I wanted to build, the next step was to set up a window and some icons for selecting the different tools. So I set about to create a bunch of first pass icons to use. The first batch are sort of monotone, not a lot of detail but they get the job done. I'll have to get a UI artist down the road to clean these up.

Once I had my icons I went to add them to buttons. I ran into a bit of a roadblock here though because I realized that I hadn't set up my buttons so that I could have an image rendered on them. This wasn't a big deal I just added another asset to render on top of the buttons, but I realized that my UISprite object was only set up for scalable UI images where it separates the image into a grid of 9 images so that everything scales nicely. This was overkill for a little button image so I set up a non-scalable render mode for the UISprite that just renders the image as a simple quad.

I also started to hook up the UICopyPastable object I had created the previous week. I hooked it up to the UIEditbox for the trial run, it worked like a charm. It's nice to have copy and paste working now, makes using the edit boxes a little nicer, they still need cursors though.

Alright, that was the first day, on Tuesday I ran into a problem from setting up the copy and paste. I needed to separate out key commands that work for UI elements from Key commands set up for different edit modes. I had been meaning to do this for quite a while, my gameplan was to create groups for keyinput so that I could disable key commands based on group whenever I needed to. This took me the majority of Tuesday, testing included.

The first thing I wanted to get working was the grid axis toggle. This changed the grid within the voxel sprite between the x,y, and z axis. Next I hooked up the point drawing and line drawing I already had in place to the buttons I had set up in the edit toolbox. The first tool I really started working on was the fill tool. This is like the classic paint tool that does a flood fill across a layer. Then I added erase mode toggle which just flips the tools between placing a voxel and erasing a voxel, I made this a toggle so that erase works with all the tools, point, line, circle. Once I had finished the fill tool I figured it'd be a good time to hook all these tools up to mouse clicks, that was a fairly quick change. I also made a note that layer up and layer down weren't going to be that useful so I'm going to combine them and make a layer move tool. The next thing I realized was that I was going to need a file dialog. I came to a crossroads on this one, I knew that it was quite easy to bring up the standard windows dialog, so I had to weigh whether or not it would be worth all the extra time of implementing all the features for my own file dialog. In the end I decided that it was in my best interest to use the standard win32 dialog for now.

Thursday, since I was adding the file dialog I figured it would be a good time to switch tracks and spend some time hooking up the file dialog to things I already had in place. The first one was the main menu so that I could save and load different levels. This led me to realize that I didn't have a clean way to destroy a level. So I had to invest some time into making sure all the memory was properly freed so that I had a clean shutdown, flushing out everything properly. I'm still not 100% I got all the memory cleaned up but at least for now everything is flushing out properly. Since I had a clean shutdown now, I figured I'd add a New Level option to the main menu which just starts you out with a clean slate for building up a level.
 
Friday, with the Tile Edit State code starting to grow I figured it was a good time to separate out some of this code. I moved the code for the Tile Edit State and the Tile Placing State out of the main Editor Game State. All the code had already been in separate classes but it had all been living in the same cpp/h files. This was leading to some compile time issues on my little computer, plus the separation makes everything a lot cleaner. I also added a FileDialogInfo to the creation of the file dialog so I could adjust things like the default file extension and what not when I'm popping up the dialog. I also got to the bottom of a non fatal memory stomp, seems that it was caused by my group changes to the Input Watcher. I still need to dig into that one a bit deeper but it has a band-aid on it for now.


It's amazing sometimes how much you can get completed in one week!

Showing off the new file menu

First look at the new edit toolbox

Toggling the grid axis

Drawing with the line tool

Making a closed box so I can demo the fill tool

Bam, fill tool!

Showing off the erase toggle with the draw point tool

This last one is showing off the palette edit, change the color in the palette and it updates the sprite.

More Cleanup

Hey Readers,

Sorry for the lack of updates, my wife and I just had a baby so I've been off work and therefore not doing any programming on the bus. Lots to update on though!

I added in context objects for all the major systems. This made all of the parameters I was passing into various objects a lot cleaner. Now an object just takes in the necessary contexts and has all the information it needs for construction.

I also cleaned up the movement code in the physics. After all the refactoring I was finding that the collision didn't quite work right. The character would get stuck all the time inside of walls. The trick was to separate out the collision into vertical and horizontal steps and also separate the collision response. Now everything's working great.

After that I decided it was time to start cleaning up all the bus in the editor and refine some of the features that I had stubbed in. The first thing I added was that if an object is selected and the user presses Ctrl-E it switches into the voxel editor mode with that objects voxel sprite.

Then I made some tweaks to the color palette. I set it up so that when the user enters voxel edit mode it loads all of the colors for that voxel sprite into the palette. I also fixed up the rgb sliders, now when the user selects a color the sliders auto adjust to the current color. Previously while they would adjust the color, the positions of the sliders didn't update to the current color.

I also changed the behaviour of saving for voxel sprites. Before when the user would press Ctrl-S it would save the currently edited voxel sprite as Sprite.spark in the base directory. Now it uses the metadata associated with the asset to get the proper filename so that it saves back to the right file. I should have done this ages ago, makes it a lot easier to iterate on art.

Another update was to the mouse raycast code. Before when selecting an object I would just iterate over the entire list of objects and as soon as I came across the first object that intersected with the mouse raycast I would break and make that object the currently selected. The problem with this is that the first object is not necessarily the closest object! So I changed it so that I build up a vector of selected object and then make the closest object to the camera the currently selected object.

The last thing I started putting in is functionality for copy and paste from the windows clipboard. I hooked up the platform specific code and now I'm starting to hook into the frontend code. I've stubbed in a UICopyPastable sprocket which any object that wants copy paste behaviour can use it.