Implementing Morton ordering for chunked voxel data

We’ve recently been doing some work in PolyVox to switch the ordering of voxel data from linear order to Morton order. This work is now complete, and in this relatively technical post I’m going to highlight a couple of the interesting tricks which we came across while doing it. Hopefully these will be beneficial to other people working on the low-level details of voxel engines.

Like many voxel engines, PolyVox allows volume data to be broken down into a number of ‘chunks’. The primary advantage of this approach is that not all the data has to be loaded into memory at the same time, and we can instead load and unload chunks on demand. Note that this is an implementation detail of the our ‘PagedVolume’ class, and algorithms which operate on the data (mesh extractors, raycasting, etc) are not aware that the data is stored in this way.

The size of each chunk can be specified by the user (with the ideal size depending on a number of factors) but typically contain 32³, 64³, or 128³ voxels. The ‘ordering’ of these voxels refers to the way they are laid out in memory, and two possibilities are shown below for the 2D case. The linear ordering is the easiest to understand and can be traversed with a simple nested for loop, but the Morton ordering brings numerous benefits in terms of locality of reference, ease of downsampling, and increased compressibility.

Linear ordering (left) vs. Morton ordering (right)

Linear ordering (left) vs. Morton ordering (right)

However, the purpose of this blog post is not to explain the benefits of Morton ordering, nor to describe how (x,y,z) positions are mapped to locations on the Morton curve. For this we refer you to the Wikipedia article and the excellent blog posts by Jeroen Baert and Fabian Giesen. Instead, we wish to highlight a couple of optimizations which were useful in our implementation.

Continue reading

Share

Update on Cubiquity for Unreal Engine 4

It’s been a little while since my last update on the progress of integrating Cubiquity with Unreal Engine 4 but plenty has been going on behind the scenes. Since the last video I’ve improved performance, added support for Coloured Cubes terrain, added LOD support, tested large map support and made sure that all of the functionality of Cubiquity is being exposed. A lot of time has just gone into making the code-base more future proof and reducing duplication between the different terrain modes.

Check out the video below to see the new features in motion as well as me just blowing stuff up at the 9:42 mark.

This more or less marks the features I wanted present for the first pre-release, so between now and then I will mostly be working on tidying things up and hopefully adding some initial documentation. I don’t have any ETA on the first release since this is fitting around my full-time job but any information will be posted here and on twitter.

The best place to follow development is the WIP thread on the Unreal Engine Forums.

Share

A new version of Cubiquity for Unity3D is now available

Today we are pleased to announce that a new version of Cubiquity for Unity3D has been released on the asset store. Version 1.2 brings performance and memory gains, adds support for 64-bit architectures, includes faster transfer of mesh data from the native library, and provides experimental heightmap import.

A new example map is included (imported from here).

Our new example map shows a city modeled at a resolution of 512x512x64 voxels which can be destroyed in real-time (complete with physics). Data courtesy of William Rigby and the game ‘Build&Shoot’).

We have improved both performance and memory usage by introducing an octree to reduce the number of mesh chunks which are active at an given time. We’ve combined this with a sophisticated time-stamping system, which allows us to minimize the amount of work required to synchronize our internal representation with Unity’s scene hierarchy. The city map shown above loads in just a few seconds and runs smoothly with destruction and physics enabled.

We have also replaced our ‘ConvertToVDB’ and ‘ConvertToImages’ tools with a single general purpose tool called ‘ProcessVDB’. This provides experimental support for importing heightmaps as terrain volumes – experimental in the sense that it seems to work well but needs some refinements to the workflow.

This map was created using the new (experimental) functionality to import from a heightmap.  It can then be edited as usual to create caves and overhangs.

This map was created using the new functionality to import from a heightmap. Once in the editor the usual sculpting tools can be applied to create caves and overhangs, or to apply materials and textures.

The licensing model hasn’t changed – you can use the system free for non-commercial and evaluation use, or for $200 (per-seat) you can buy a commercial license through the Unity asset store:

For those of you who are waiting on the integration with Unreal Engine 4, I spent some time with Matt over Christmas and saw that the system is indeed progressing nicely. Both the smooth terrain and ‘colored cubes’ volumes are largely working though integrating with the editor and blueprint system is a lot of work. We both have only limited time so there’s not currently a set schedule for the initial release, but keep an eye on the forum thread for the latest updates.

Share

First look at Cubiquity for Unreal Engine 4

As you might have seen if you’re following us on Twitter, I’ve been working hard recently to get Cubiquity working with Unreal Engine 4. Both David and I have long been fans of the Unreal games and the engine and so I’m having great fun diving into the code. I haven’t spend a lot of time on it yet but earlier this week I had the time to push the integration to a point where I can start showing off some features. Take a look at the video below for an overview of the current state.

The aim is to have at least feature equivalence between the UE4 version and the Unity3D version. So far I have only the smooth voxel terrain working and haven’t started on the coloured cubes version yet. There is live editing in the editor preview mode but not yet integrated as an editor tool such as users might be used to after working with UE4’s heightmap terrain features but this is something I will try to get in before the first official release. For the first beta release I want to spend some time neatening up the interface to the engine to make what’s currently available as usable as possible.

I’ll be posting an update here on the blog when there’s code out for people to test but in the meantime follow us on Twitter @VolumesOfFun (or me personally @milliams) or track our updates on the Unreal Engine Forums.

Share

A new version of Cubiquity for Unity3D has been released

It’s been a quiet few months, but we’re happy to say that a new version of Cubiquity has just landed on the asset store. Version 1.1.3 is primarily a bug-fix release but also adds a few new features such as normal mapping of the colored cubes volumes and an example showing how to build and save voxel databases from Unity scripts.

Colored cubes can now have custom diffuse and normal maps applied. Shiny!

We’ve also tidied up a lot of stuff internally, for example all of our PolyVox enhancements have been merged back into the main develop branch and we have overhauled the Cubiquity build system. Perhaps not so exciting for end users but still an important step as development can move a bit more smoothly from here on.

Licensing is the same deal as before – you can use the system free for non-commercial and evaluation use, or for $200 you can buy a commercial license through the Unity asset store:

Looking forwards, the main request has been for larger volume support and better performance with less memory. In other words, we’re going to put some work into optimization and possibly providing some tools (importers, etc.) to help create the larger environments.

We’ll try not to go another three months without posting, and I think the upcoming changes should give us plenty to show off!

Update 3rd Sept 2014: Version 1.1.3 is now out with collision and physics fixes for smooth terrain. The links above have been updated.

Share

Cubiquity for Unity3D is now on the Asset Store!

Hi all, I’m pleased to announce that we’ve just made the first official release of Cubiquity for Unity3D, and that it’s now available to purchase from the asset store. This is a huge milestone for us and comes just over a year after we first showed our work on Unity3D integration.

The asset has been released at the $200 price point which we’ve been throwing around for a while now, and it remains free for non-commercial and evaluation use. Anyone who has been following our regular snapshots will already have a good idea what the system does, but the uninitiated can get the latest free version below:

It’s also worth mentioning that we’ve updated the documentation and placed it online. You can read it here:

And as mentioned previously, if you like the system you can now buy the commercial version at the asset store:

This is really just the start of the journey for Cubiquity and we have plenty of ideas for how we want to further develop the system over the coming months. But that can wait for a future post – for now we’d just like to thank everyone who has spent time testing our system, giving feedback, and providing encouragement. You’ve helped get Cubiquity for Unity3D to where it is today!

Share

New Cubiquity for Unity snapshot with OS X and Linux support

I’m pleased to announce that today we’re releasing a new snapshot of Cubiquity for Unity. This version finally adds support for both OS X and Linux, and also includes a number of smaller improvements regarding stability, user interface and documentation.

Cubiquity for Unity running on OSX

You can download this latest snapshot using the links below (remember to check our YouTube channel for examples of what Cubiquity for Unity can do):

One of the main appeals of Unity is the ability to target multiple platforms from a single code base, and so we’ve always been keen to bring this functionality to Cubiquity as well. The process is more complex than for other Unity assets because Cubiquity is a native code library written in C++, and so it needs to be compiled (by us) for each platform which we want users to be able to target.

Matt kicked off the work a few weeks ago by compiling Cubiquity for Linux. This involved writing some CMake scripts, testing the process of loading dynamic libraries on Linux, and fixing some OpenGL issues. All of this helped lay the foundations for the OS X version, which then required extra tweaks to the the build process and handling of log files. But eventually it came together :-)

We haven’t added any significant new features beyond the improved platform support, but there has been more work on polishing the API and particularly on documenting it. The final release will naturally include API docs and a user manual to get you up to speed quickly, but we’re also hoping the API will be simple enough to be intuitive.

We currently expect that this is that last snapshot which we release before we put Cubiquity on the Asset Store! The end is now really in sight and we hope to be live by the end of this month.

Share

Cubiquity now works on Linux

Well it’s taken me a few weeks of on and off work but I’ve got Cubiquity working on Linux as a Unity3D add-on. You can try it right now from the Git repository and as long as everything works correctly, it will be available in the next official release.

Cubiquity for Unity3D running on Linux

Cubiquity for Unity3D running on Linux

Porting

There are two essential parts to Cubiquity: the core Cubiquity code where all the magic happens and a thin wrapper providing a C interface to allow easy interaction with Unity’s C♯ code. Cubiquity builds heavily upon PolyVox which has been working on Linux for years now so at least we had a good base to work from. Like PolyVox, Cubiquity is written in C++ which makes it easily portable meaning I had to only make a few trivial changes to the code to get it to build. After a few tweaks to the CMake files, we had a libCubiquityC.so file built and ready.

In order to ease installation and avoid library mismatches, we decided that statically linking all that we could was the best option. Luckily, Cubiquity has few 3rd-party dependencies — in fact it only depends on the C++ standard library and two small Boost libraries. Boost was only being used to fill in features which are now part of C++11 and so by increasing our compiler requirement we could remove the Boost usage entirely. Once here it was simple enough to statically link in libstdc++ and avoid and difficult dynamic library requirements.

For testing purposes, David sent me a simple Unity application which had been exported for Linux and used Cubiquity to create a simple terrain. The idea was that I should be able to place the libCubiquityC.so alongside the executable and the Mono runtime would find the library and load the appropriate stuff from inside it. With a bit of tweaking of the C♯ loading script and recompiling the library as 32-bit (because the Unity app I was using was 32-bit) I was able to run the Unity application and have it render a terrain.

As you can see in that last link, the terrain was not rendering properly and so David set to work getting the shaders working correctly and fighting with some tricky Unity bugs and now it all seems to be working well.

What’s next

Getting Cubiquity working on Linux, as well as being an end in itself, is a useful step towards getting it running on OS X. We are compiling it with both GCC and Clang (which is the OS X compiler) to make sure the code stays portable. In the medium-term we’re working towards being able to easily build the library for all our supported platforms from one place and so I’ve been investigating cross-compiling from Linux to both Windows and OS X. I will give a more detailed description of what I’m doing in a future post but we do already have DLLs and DYLIBs building and they are undergoing testing at the moment. Once we’re confident in the Linux build, we will work on testing out OS X support.

Share

Cubiquity progress update – volume transformations and materials

Time for another Cubiquity update! Over the last two months we’ve put a lot of work into polishing and refining Cubiquity in order to make it fit more naturally with the Unity way of doing things. In particular, voxel terrains now behave much more like other Unity objects in that they can be translated, scaled and rotated, and can also participate in transformation hierarchies. See the video below for an example (the moon orbits the Earth while the Earth orbits the sun):

As you can see this adds a lot of flexibility to the system, and it’s really starting to feel like things are being done ‘the right way’. I can imagine the solar system example above could be ‘gamified’ quite nicely, e.g. you could defend a voxel-based Earth from a barrage of voxel-based meteorites. And I’m sure there are plenty of more interesting game concepts which you guys can think up :-)

As well as transforms, the video also shows that the material system is much more flexible now. You can still use the TriplanarTexturing material but it’s really just an example. The ‘planet’ material (used for the Earth in the video above) shows how textures can be applied from a cube map, and we have ideas for other approaches too.

Actually setting the material is also more natural now. We’ve introduced ‘VolumeRenderer’ and ‘VolumeCollider’ components which are conceptually similar to their mesh-based cousins, and so the material can be set just by changing the ‘material’ property of the ‘VolumeRenderer’ component. There’s still some work to do with these but it’s starting to take shape.

Sounds great, but when is the release?!
We were originally hoping to be on the asset store by the end of last year, and we’re clearly behind in that regard. This isn’t due to any particular problem or road block – it’s just a case of everything taking a bit longer than expected. But that’s why we put out these snapshots, so that you guys can see the progress and start playing with the system.

As it currently stands, we expect to put out one more snapshot in about a month, and then release at least the free version of Cubiquity on the asset store about a month after that. It’s not clear if the paid version will go live at the same time – we may have a testing period with just the free version available. At any rate the paid version won’t be very far behind.

Of course, being on the Asset Store is really just the start… we have many interesting plans for the future of this system :-)

Share

Plans for PolyVox in 2014

The last year has seen a heavy focus on Cubiquity-related news but PolyVox has also been moving along in the background. Here’s a few examples of things we have added over the last year:

  • Volume wrap modes (out-of-bounds voxel access can now clamp, repeat, border, etc).
  • Improved error handling and logging system, and also timers for performance analysis.
  • Pluggable compression and paging support for the LargeVolume class.

None the less, with Cubiquity in the foreground we want to ensure PolyVox does not stagnate, and this Christmas has provided chance for Matt and I to sit down and discuss how to achieve this.

It has become increasingly clear to me that the effort involved in developing a mature open source project is significantly greater than developing a young private project. For example, within Cubiquity I will routinely add, delete, rename, or refactor large swathes of code, safe in the knowledge that I am the only person affected, and that I can roll back large architectural changes without having to justify it to anybody.

In principle PolyVox should be the same – the license clearly states that it’s provided ‘as is’. But in practice there is at least some degree of moral obligation to consider backwards compatibility, communicate significant changes, update the documentation, update the language bindings, test on multiple compilers, etc. This adds a degree of inertia to the project which reduces enthusiasm for making changes, especially in light of having less free time than was previously available.

So, how are we going to fix this? Basically we are planning a few things:

Stop worrying (too much) about API stability: I recently added support for wrap modes and bounds checks when accessing voxels outside of the volume, but this would have changed the interface to the ‘getVoxelAt()’ functions. Therefore I left these functions as they were and added new ‘getVoxel()’ functions. It’s technically backwards compatible, but is also confusing, error-prone, and adds more code to test. In the future we’ll just change things when we feel they need to change.

Embrace C++11 and drop support for older compilers: Matt has long been an advocate of embracing C++11 within PolyVox, and previously we said it would be used after the next stable release. Instead we will start using it now wherever we feel it makes sense. This will result in older versions of Visual Studio being unsupported, and I would guess that VS2012 would become the required version of Windows.

Cut down the amount of code in PolyVox: Some of this will come from the C++11 support – for example we can remove the Boost fallbacks and compiler detection from CMake, replace PolyVox::Array with std::array, etc. Also, the numerous volume, block, and array classes overlap too much in terms of functionality, so we will make some reductions here. We may also strip out the built-in compression code and just let users implement this with an external library.

Simplify build system: We’ll probably drop support for building PolyVox as a dynamic (shared) library, as it’s really not clear that it makes sense when PolyVox is almost entirely header files. We may go header only if we decide it makes sense, as this would then remove the need for people to build PolyVox at all.

Note that we are no longer planning to release a new stable version before commencing work on the above. This may have some impact on users who are trying to keep up with the latest version in Git, but practically speaking the changes are going to be spread out over many months. We’ll also try to keep the develop branch in a relatively stable state and continue to run nightly tests, etc.

PolyVox is still a key piece of software for us as it provides the foundation for Cubiquity, so we do hope these changes help keep it moving forward and allow us to add some of the new features we’ve been thinking about.

Share