Happy New Year everyone – I hope everyone reading this had a great end of year break and has a fantastic 2017.
I suspect I’m not alone in that I like to spend a little time over the Christmas break working (in the fun sense of the word) on something a bit different from the day job. This year I took about 4 days out to work on a really simple voxel engine as both the look and constructible / destructible feel of voxels have always appealed to me, perhaps as a result of a childhood playing with Lego. Though bizarrely I’ve never played Minecraft.
The code for the engine along with a couple of demonstrations can, as ever, be found over on GitHub.
I didn’t want to feel like I was writing glue code and so rather than use an existing library I started with a blank C++ file, OpenGL, and an awful lot of ignorance. Now to be fair I do have a reasonable background in C, C++, graphics and systems programming – before this web thing came along I was working with embedded systems and 2d graphics engines using C, C++ and 68000 assembly – but that was back in 1994. I continued as a commercial C++ developer for 4 more years but then found myself working with C# and the first .Net beta via a brief foray with Delphi.
So I was rusty. Very rusty. However I had enthusiasm on my side and persevered until I had a couple of demo’s and some code that I wasn’t too embarrassed to share. The video below is me navigating a voxel “landscape” created using a black and white self portrait as a height map:
First step was some early research and I quickly discovered some really useful resources:
- GLFW – a great library for abstracting away the underlying hardware and OS and getting you a window to draw in
- Glad – OpenGL is a strange, strange, place and chances are you will need to use a “loader” to get access to the full API. This web service makes it really easy.
- GLM – A header only mathematics library based on the OpenGL shader specification
- Learn OpenGL – tutorial series
- OpenGL Tutoral – another OpenGL tutorial series
Being conscious C++ had changed a fair bit since my youthful glory days I also skim read Accelerated C++ and Effective Modern C++. I’ll be returning to the latter and reading it in some more depth as I’m sure my code is still pretty stinky – but it works!
Day 1 – I Know Nothing
Armed with my new found expertise I set myself a goal of generating and rendering a landscape based on Perlin Noise but given I couldn’t yet draw a cube I thought I’d better bootstrap my way up. This first day was the toughest and involved a fair amount of staring at a blank screen, cursing, and feeling extremely thankful for the safety of managed environments. However at the end of the day I managed to get not only a single cube on the screen but a set of voxels arranged into a chunk rendering (a chunk is an organisational concept in a voxel engine – collections of voxels) and you can see that below:
I didn’t yet have any lighting so to help me process what I was looking at I did a simple adjustment of the colours around each vertex.
The next step was to display several chunks together. My first effort at this went… badly. Only one chunk was ever displayed. After spending an hour looking for obscure OpenGL problems I realised I’d done something more basically dumb with C++ (we’ve all copied something we thought we were passing by reference right?), pounded my head into the desk a few times, corrected it and hurrah. 4×4 chunks!
Flush with success wine may have been consumed.
Day 2 – Algorithms and Structures
Sitting at the desk with a slightly groggy head – which the wine had nothing to do with, nothing, not a damn thing – I started to ponder how to arrange and manage chunks. The memory requirements for voxels can be huge. Imagine that each of your voxels takes 16 bytes to store it and that your landscape is a modest sized 1024 voxels wide, 32 voxels high, and 1024 voxels deep – that’s 536,870,912 bytes, better known as 512Mb, of storage needed before you even account for rendering geometry.
It’s clear you’re going to need someway of managing that and for practical usage compressing and/or virtualising it.
I came up with, and by came up with I mean I’d read somewhere and recalled it, the concept of a chunk manager (this came up somewhere in my research), chunk factories (this didn’t come up in my research but seems a logical extension) and a chunk optimiser (not yet implemented!).
The main decision here was how low to go – so to speak. The most optimal route likely involves getting the STL out of the way, pre-allocating memory and organising it in a very specific manner. However that also seemed the route most likely to feel like having your teeth pulled. In the end I decided to go with the path of least resistance and mostly used the std::vector class with pre-allocated sizes where known.
Nothing to see from my efforts yet except the cube still shows but using the new code. Which while not worth a screenshot was a result!
With that out the way I needed a perlin noise generator to implement as part of one of my new fangled chunk factories. I’ve written one before for a lava type effect at some point back when you had to find the algorithm in a book and figure out how to write it yourself. Having no wish to repeat that painful experience I quickly found a great post and gist on GitHub written in C# and converted it to C++.
I hit F5, Visual Studio whirred away for a few seconds, and to my utter amazement my good run of luck continued and I had an ugly but working voxel landscape.
Good times. And good times when you’re on your Christmas break deserve wine.
Day 3 – This Is Far From Light Speed
Without any lighting it was hard to really get a sense of the terrain in the landscape that I could see but before I could do something about that I needed to address some performance issues. Rendering was fine – I was cruising at a vertical refresh locked 60 frames per second. When rendering started. Problem was that even on my 4.5GHz 6700K i7 it took about 90 seconds to generate the voxels and the initial geometry.
Normally I’d advocate measuring before going any further but the issue was self evidently (famous last words…. but not this time) in a fairly narrow section of code so step 1 was a code review which quickly highlighted a moment of stupidity from the previous day: I was calling the perlin noise function 16 times more than I needed to.
I could see from Visual Studio that memory allocation was also sub-optimal as it was occurring on an “as needed” basis but as previously noted I’m favouring clarity and simplicity over gnarly. However Visual Studio was also highlighting another issue – my CPU was only being used at around 15%. The code is single threaded and I’ve got 4 cores capable of supporting 8 threads.
Haha thinks me with my C# head on. This is eminently parallelisable (the clues being in the names “chunk” and perlin noise “function”) and C++ must have a decent task / parallel library by now. Oh yes. Futures. They’ll do it.
Oh boy. Oh boy oh boy. That hurt. Converting the code to use lambda’s and futures was straightforward but then the issues began – turns out there is not yet an equivalent for something like Task.WhenAll in the C++ standard library. I got there in the end after a bit of a deep dive into modern C++ threading concepts (I really didn’t want to use the OS primitives directly as I want to make this multi platform) and solved this with locks and condition_variables.
I’ve tested it on a variety of systems (with different performance characteristics and cores available) and it hasn’t crashed or done anything unpredictable on a variety of different systems but I’m sure there is something wrong with this code so if any C++ experts read this I’d love some pointers.
So now its quicker, about 6 or 7 seconds to generate a respectably sized landscape, but it looks the same and most of the day has gone.
Fortunately adding basic lighting proved much simpler. Simple voxels, cubes, are pretty simple to light as the normals are somewhat obvious and there is plenty of documented examples of using vertex normals inside vertex and fragment shaders to apply the appropriate colouring. A couple of hours later I had ambient, diffuse, and specular lighting up and running and could turn off my dodgy half shading.
A great way to go into New Years Eve and definitely earning of a celebratory brandy. Slightly warmed and in an appropriate glass of course.
Day 4 – This Code Stinks
Old Man Randall (me) fell asleep long before midnight and so I woke up fresh and eager on New Years Day to do some more work. I’d had the brainwave a few days ago to use photographs as the source for landscape height maps using the brightness (whiteness in black and white photographs, calculated perceived brightness in colour photographs) of each pixel to build an appropriately high stack of voxels.
However before I could do anything else the code really needed some work. It had the distinctive whiff of a codebase in which many new things had been tried with little idea of what would work or not. Structure had become scrambled, inconsistencies were everywhere, and commented out attempts at different approaches abound. Not to mention I’d built everything into a single executable with no attempt to separate the engine from it’s usage.
A few hours later and although still not perfect I had something that was workable and set about implementing my voxel photographs starting with black and white. Being a supreme narcissist I selected a photograph of myself from my flickr library and busied myself trying to load it. This proved to be the hardest part – I’d forgotten how painful C++ and libraries without package managers can be (is there a package manager for C++?) with chains of dependencies.
In the end I realised that cimg could load bmp files without any dependencies and implemented a new chunk factory that used that to scan the pixels and create voxels based on their whiteness.
This worked a treat and I captured the video of me moving around the “landscape” that appears at the top of this post.
A great way to finish off and in a burst of enthusiasm I quickly sent the link to my fans. Or fan. By which I mean my mum. No celebratory brandy sadly as structured cycling training has restarted but happiness abounds.
Conclusions and What Next?
A few things struck me throughout this short project that I think are worth collecting and reflecting on:
- The modern Internet truly is a wonderful thing. The last time I was coding in C++ (about 1998) it wasn’t the Internet of today and things were so much harder. It’s an amazing resource.
- The development community is amazing. There are so many people giving their time and expertise away for free in the form of blog posts, articles, and code that unless you’re doing something really on the bleeding edge there is someone, somewhere, who can help you.
- Wow C++ has changed – for the better. It’s still complicated but there’s a lot more available out of the box to help you not make simple mistakes.
- GPUs are incredible number crunching machines. I’m fortunate enough to have a pretty top notch GPU in my desktop (a 980Ti) but the sheer number of computations being performed to render, in 60 fps, some of the scenes I threw at this code is astounding. I knew in theory the capabilities of GPUs but didn’t “feel” it – I’m now interested where I can apply this power elsewhere.
- Iterative approaches are great for tackling something you don’t know much about. I just kept setting myself mini-milestones and evolving the code, not being afraid to do something really badly at first. By setting small milestones you get a series of positive kicks that keeps you motivated through the hard times.
- Coding, particularly when it involves learning, is fun. It really is. I still love it. I’ve been coding for around 34 years now, since I was 6 or 7, and it still gives me an enormous thrill. My passion for it at its core is undiminished.
As for this project and what I might do next. I’ve got a couple of simple projects in mind I’d like to use it with and a small shopping list of things I think will be interesting to implement:
- Mac / *nix support
- General optimisation. I’ve only done the really low hanging fruit so far and there is scope for improvement everywhere.
- Voxel sprite support
- Skybox / fog support
- Paging / virtualisation – with this in mind this is one of the main reasons that scenes are constructed using the chunk factory
- Level of detail support
- Simple physics
Whether or when I’ll get time to do this I’d rather not say, I have a big product launch on the horizon and a React book to write, but I’ve had so much fun that I’m likely to keep tinkering when I can.