As has been mentioned previously, the current version of Cubiquity is no longer under active development as the focus has shifted to a replacement ‘Cubiquity 2’ system which is being developed outside of the ‘Volumes of Fun’ brand. Although the replacement system is still a long way from being ready, I feel it is time to remove the current version from the Unity Asset Store.

The reason is that I don’t want to encourage people to use a system which I no longer have the time and resources to support, and I think that having the system available on the asset store does exactly this. Cubiquity for Unity3D was developed under Unity 4 and has only limited testing under Unity 5, and as the Unity 5.x series progresses I’m increasingly becoming aware of problems which I don’t have time to investigate.

The system will remain available on BitBucket as it is open source software, but that provides a slightly higher barrier to entry and comes with a warning about the system no longer being developed. I’m expecting that Cubiquity 2 will go on GitHub to avoid any confusion between the two versions, but more on that in the future.

The post Removing Cubiquity from the Unity Asset Store appeared first on Volumes Of Fun.

Voxeliens is a retro-style arcade shooter and is essentially a 3D voxel-based version of Space Invaders. We released the game in 2012, showed it off at the Develop Conference and have had it accepted for Steam Greenlight. However, as mentioned in several previous blog posts, time is no longer on our side and we are re-focusing our efforts on the next version of Cubiquity.

Therefore we have decided to release Voxeliens for free under the MIT license. It now lives on BitBucket alongside PolyVox and Cubiquity (our voxel engines) and prebuilt binaries for Windows are also provided. It should also be possible to built it from source (including on Linux) but this has not been well tested on systems other than our own.

We put a lot of work into Voxeliens so we are pleased to now be able to share it with a much larger audience. Note that we do still have the option of selling it on Steam in the future (the Greenlight campaign remains valid) but it is not clear whether we will due to the setup, testing, and support required. At any rate, we hope you enjoy the game!

The post Voxeliens is now open source appeared first on Volumes Of Fun.

I made the first public release of PolyVox nearly 10 years ago on the Ogre 3D forums. At the time it was just a simple demo to show how voxels and Marching Cubes could be used to create more dynamic environments, but over the years it evolved into a stand-alone library which has been used by several games and our own Cubiquity voxel engine. It’s been a big part of my life for the last 10 years, but as mentioned in previous blog posts I now have less time and am over-committed with the various projects I’m involved in.

Therefore I have decided to officially cease development on PolyVox, though in practice it has not seen much work for the last couple of years. This follows the wrapping up of the current version of Cubiquity last year, and my plan is still to put the majority of my development time into ‘Cubiquity 2’. This will be completely new voxel engine with more limited scope and a focus on research rather than production use (i.e. for the more adventurous!).

More generally, I have some intention of winding down the rest of ‘Volumes of Fun’ over the coming months and breaking Cubiquity 2 into a standalone organisation and/or project on GitHub. But the details of this aren’t really clear yet, and we also need to work out what to do with Voxeliens. For now the existing support channels (e.g. the forums) will remain open and I expect I’ll just provide email support if/when they disappear.

The post Wrapping up PolyVox development to focus on Cubiquity 2 appeared first on Volumes Of Fun.

In our last blog post we laid out a new direction for our Cubiquity voxel engine, including open sourcing the code and shifting the focus towards research for a future Cubiquity version 2. The first part of this is now complete, and the whole technology stack is now available under the MIT license:

• PolyVox: Low-level classes for storing and processing voxel data
• Cubiquity: A higher-level voxel engine built on PolyVox
• Cubiquity for Unity3D: Integration with the Unity game engine
• Cubiquity for Unreal: Integration with the Unreal game engine

The main advantage (as well as freedom!) of this new MIT release is that users can attempt to compile the core Cubiquity library for new platforms whereas we previously only supported Windows, OS X, and Linux. You’ll be own your own here (there are no real build instructions), but we have had reports of it working at least on the iPhone.

There are a few important points to be aware of for those wanting to work with this code base:

For Unity users: We have not uploaded this MIT-licensed version of Cubiquity for Unity3D to the asset store, basically because we don’t want to go through the building/testing/release process again. The asset store version corresponds exactly to the ver1.2.1 release tag, and only differs from master in terms of the readme and the license (Asset Store free license, rather than MIT).

For Unreal users: Be aware that the Unreal version of Cubiquity is really just a proof-of-concept. We did successfully use it for ‘The Peasants are Revolting‘ but it is not production ready and doesn’t work with the latest version of Unreal Engine. We hope to address this for Cubiquity version 2.

However, please do note that the projects above are now largely inactive. As explained previously, the upcoming Cubiquity version 2 will be a complete rewrite which will build on the lessons which have been learned while creating the existing system. Development will take place in a new repository once we have something to show, though at the moment it is very much in the research and prototyping stage.

The post Cubiquity is now fully open source under the MIT license appeared first on Volumes Of Fun.

—– > Update: Cubiquity 2 is now on GitHub here. <—–

When we began working on Cubiquity the main idea was to expose our PolyVox library through a higher-level interface and tools. PolyVox is powerful and flexible, but requires a strong knowledge of C++, templates and computer graphics to use effectively. By wrapping this in Cubiquity and integrating it with Unity/Unreal we were hoping to bring (some of) it’s capabilities to a larger audience.

The project has been a reasonable success, with a lot of interest from the Unity and Unreal communities and even a game launched on Steam using the technology. However, it is also clear that the original vision is simply too large to finish as a personal side project, especially with diminishing amounts of free time and a desire to adjust my work/life balance. This led to use recently releasing the system for free, but further steps need to be taken to actually reduce the scope.

In this blog post I want to outline the areas in which I/we will be cutting back on development, and explain how it will affect existing users. I also want to define a direction for a future ‘Cubiquity 2.0’ such that it is both smaller and also more technically interesting to work on. This means shifting the focus to research rather than delivering a drop-in system, open-sourcing the complete technology stack, and reducing (but not eliminating) the level of integration provided for Unity and Unreal.

Open sourcing the core Cubiquity library

The proposed change of direction is likely to cause some concerns for users who are already working with Cubiquity, and so I hope to partially alleviate these by announcing that we will release the core Cubiquity library as open source. This is also expected to reduce our workload in the following ways:

• End users will become responsible for building and testing the library on the platforms which they wish to support. On the plus side, they may also be able to port the library to new platforms (Android, iOS) which we did not have time for.
• We may remove Cubiquity from the Unity Asset Store and handle distribution only through BitBucket and/or Github. A more developer-focused Cubiquity may not be a good fit for the Asset Store where users expect drop-in solutions.

This applies to both the current version of Cubiquity (which may not see much further development) and also to a future ‘Cubiquity 2.0’ code base (which will likely be a complete rewrite).

Shifting the focus back to research

When we first released PolyVox back in 2006 the idea of using voxels to represent worlds in games was fairly novel. There was some interesting work by the likes of Ken Silverman and Sven Forstman but voxel techniques were not widely used [1]. The arrival of Minecraft changed all of that, and overnight voxels became the new ‘hot thing’.

Fast-forward ten years and it now feels like everyone is developing a voxel engine, and the techniques used within PolyVox and Cubiquity are no longer particularly novel. But there is a lot of interesting research to be done as shown by projects like Atomontage and VoxelQuest, and I’ve actually been working on an interesting prototype of a new (to my knowledge) voxel-rendering algorithm.

I’ll talk more about my ideas in the a future post, but the important point for now is that the difference between implementing new algorithms vs. really making them production ready is at least an order of magnitude. I therefore expect future versions of Cubiquity to be a little more experimental, a little more developer-focused (rather than artist-friendly), and less like the drop-in solution we currently provide on the Unity asset store.

Reducing the scope

I also have some concrete plans to cut a couple of significant features from Cubiquity. However, note that these changes will not directly affect the current codebase. Instead, Cubiquity 2.0 will most likely be a complete rewrite and will be designed without them in place.

No more Marching Cubes terrain

Cubiquity currently provides both colored-cubes style voxels and smooth (Marching Cubes) terrain. This was made possible because PolyVox supports user defined voxel types and custom surface extractors, but the two voxel systems still require different shaders and editing tools. Developing both systems in parallel is proving to be a rather large task.

We will therefore drop the Marching Cubes terrain and focus entirely on simple colored voxels, with the intention of making them as small as possible. Atomontage has shown that sufficiently small voxels can produce attractive terrains while also modeling buildings and objects, so I hope that a dedicated terrain renderer will not be needed. It is the generality of such a system which makes it interesting, as well as the ability to convert any existing dataset to this format.

Moving editing tools from Unity/Unreal to a separate application

Cubiquity for Unity allows the users to sculpt and paint terrains inside the Unity editor, and there is also basic support for editing the colored cubes volumes. Cubiquity for Unreal offers some similar features though they are not currently as complete. Overall this requires a lot of duplication of code and effort.

The plan for future versions of Cubiquity is to instead have a separate application which can be used for creating, importing and (possibly) editing volumes, and to turn the Unity and Unreal integration layers into much something much thinner. If users wanted to create in-game editors this could still be achieved via the Cubiquity API, as is the case at the moment.

Reduced focus on the Unity integration

We began working on Cubiquity around 2012, and at the time Unity was taking the indie game development world by storm. It was providing a cheap yet powerful platform and was being used by a huge number of indie games. As we were aiming to sell Cubiquity it made sense to provide an integration layer with Unity. However, from a technical standpoint it was quite a poor fit for a few (related) reasons:

C# .vs C++: Cubiquity is written in C++ but Unity scripts are written in C# (or sometimes a variant of JavaScript). This means we had to write a C interface around Cubiquity and then call that via C#’s P/Invoke magic from Unity.

No plugin support on Unity Free: Plugin support was a Pro-only feature on Unity 4, so we had to resort to some tricks and hacks to get Cubiquity loading properly. This feature is now free in Unity 5 but we haven’t had time to update our scripts to take advantage of it.

Need to compile libraries: Because Cubiquity was provided as a native-code library we have to compile it for every platform we wish to support. So far we have only supported Windows, Linux and OS X, but with both 32 and 64 bit versions that’s already six libraries to build and test.

Platform support: For the reasons outlined above, it has not been practical for us to support all platforms. Mobile has so far been too much work, and webplayer is simply not possible due to the use of native code. This causes some frustration for users who build their game and then find they cannot export to the platform of their choice.

Some of these problems disappear with Unity 5 and our move towards open source, but we are stuck with the C# vs. C++ issue and the need to compile separately for each platform (though we now defer that problem to the user). By contrast, integration with Unreal should be much more straight-forward, and has mostly been held up by lack of time/resources (see below). In this case we would simply be able to drop our Cubiquity C++ files into an Unreal project.

I’m honestly not sure where I’m going with this. Unity is still a massively popular game development platform, and from what I’ve seen it is probably easier to get into than Unreal. I do expect we will still provide some degree of support for it, but with higher technical requirements on the user and less in the way of Unity-specific examples, documentation, builds, etc. But really we’ll just have to see how the next version of Cubiquity develops, and how well the algorithms match with the architecture of Unity.

Increased focus on the Unreal integration (long term)

Our recent work on ‘The Peasants are Revolting‘ was my first exposure to the new Unreal engine, and I was very impressed. Actually my interest in the engine goes back to the original Unreal which really piqued my interest in game development. However, it was only the arrival of UE4 that the engine became accessible to indies, and by this time I had a good couple of years invested into the Unity integration.

The Cubiquity for Unreal integration was therefore handled exclusively by Matt, who has done an amazing job considering the constraints he was under. But (like me) he has a number of real-life commitments, and the task was made more difficult by Cubiquity being closed source. Furthermore, the motivation for integrating Cubiquity with Unreal is not as clear as for the Unity version, because users have the option of just using PolyVox directly (which offers more flexibility and full source access).

Things look brighter in the future though, as Cubiquity will become open source and so the relevant files can simply be dropped into the project. Also, the core technology behind Cubiquity will (probably) be quite different from PolyVox and so they won’t be competing over the same space. I hope to spend some time in the future either assisting Matt or taking over some aspects myself (depending what he wants), but this won’t happen until the core technology is developed.

Conclusion

This has been a difficult post to write because it so drastically changes the direction of a project which has had a lot of time sunk into it. However, it does seem like the right decision to ensure we stay motivated and work towards something achievable, but exactly what that is remains to be seen.

[1] 90’s-style ‘voxel’ terrain as used in Commanche, Delta Force, etc doesn’t count here as it was not really volumetric (no caves, overhangs, etc). It was just raycasting a heightfield, and as far as I can tell the term ‘voxel’ was just used as a marketing gimmick. If anyone has evidence to the contrary then do let me know!

The post Reflections on Cubiquity and finding the path forward appeared first on Volumes Of Fun.

Last weekend David and I took part in our first ‘game jam’ event. As part of Ludum Dare 33 we had 72 hours in which to make a game from scratch (or as close to that as possible) following a prescribed theme. You can find our live-updates that David was posting throughout the weekend on our Ludum Dare page (start from the bottom) but I’ll give a summary here.

If you would like to play the game it’s available from our Ludum Dare page or directly from our website. You can also download the project source.

The weekend

Friday

David arrived at my house on Friday and while waiting on the official start and theme announcement (not until 2:00 Saturday morning) we had to decide on the technology we would use. It came down to a choice between something simple in 2D using HTML5 or Python or making use of Cubiquity in a full 3D game engine like Unity3D or Unreal Engine. While I was apprehensive about the production-readiness of Cubiquity for Unreal Engine we decided that it was worth giving it chance, even just as a test of the system. Also we really wanted to have destructible scenery worked into the game somehow!

Saturday

Saturday morning we woke up to find out the theme this time was ‘you are the monster’. After working through some ideas (hunting Pac-Man as a ghost or a moving-maze labyrinth game) we settled on a simple fantasy-style twin-stick shooter where you kill villagers with fireballs. Choosing the game to make was one of the hardest parts as it’s very easy to get carried away and it’s difficult to have a sense up-front as to the difficulty of some part of the design. Deciding to start from as simple a concept as possible with plenty of scope for adding features along the way definitely turned out to be the right decision as we were able to get a first draft working quickly, knowing that we would have something to ship.

Since we were using Unreal Engine we decided that I would do the programming and David would develop the artwork. I set to work playing with the twin-stick template provided by Unreal Engine and tried to get a handle on how AI and navigation works in UE4 (something I’d never worked with before). The documentation on this was very good though and within a few hours I had a working prototype with enemies moving towards the player, firing arrows.

Meanwhile David had been hard at work getting some assets ready, primarily a first draft of the game level and some character art. All the artwork was done using MagicaVoxel which David had never used before now either.

The monster in MagicaVoxel about 16:00 on Saturday

By the end of Saturday David had most of the in-game props made (including towers and trees) and was starting to get more artistic with the design of the level itself. I however, having got Cubiquity integrated was having a lot of trouble getting it to play along with Unreal’s navigation mesh creation. In the case that we weren’t able to get the two to play nicely within the time limit we devised a potential hack of making the Cubiquity terrain simply visual but non-blocking and recreating the basic collision shapes with Unreal primitives for the navigation system to use.

We went to bed exhausted from a fraught day, not quite as far along as we would have liked but happy with the progress nonetheless.

Sunday

I started Sunday with the aim of getting a complete working first version with as much of the art in as possible and all of the basic features. It was helpful for David to see the art in-game so that he could start iterating and make sure that everything looked correctly scaled against each-other. By mid-afternoon we had a first complete version of the map in the game and an early version of the complete combat process between the peasants and the monster.

First version of the models and scenery in-game about 16:00 on Sunday

From this point on it was ‘simply’ a very large polishing process and working through our feature wishlist, hoping to get as far as destructible terrain. Throughout Sunday afternoon and evening we really found our flow and were both making very good progress. By the end of the day David had mostly finished the game map and I had a working game which, if necessary, we would have been ready to ship.

The full map at the end of the day on Sunday

While we hadn’t got as far on Saturday as I would have liked, I felt that by the end of Sunday we were further along than I had expected. Luckily this gave us a whole day to iterate and tweak and make the game feel less like a tech demo.

Monday

On our last day we were starting to feel the crunch. When you’re counting down the hours you have to start prioritising and so we each started working against a to-do list. David spent a lot of time fleshing out the map and trying to make sure that there’s always something interesting on screen as well as paths to encourage the player to explore. I was working hard to make sure that we had everything in there that made it a polished game such as a HUD, help text, depth-of-field, sound effects and powerups.

Until this point we hadn’t created a full build so I spent an hour or so getting that working and testing it on David’s computer so that he could iterate on the artwork and have it appear directly in-game.

Almost final version of game about 16:00 on Monday

We still didn’t have voxel destruction in-game but soon after lunch David convinced me that I should see if it’s possible to get it to work easily. I’d been putting it off due to potential problems with collision and navigation mesh updates but I decided that to first order I would just do the voxel destruction under an explosion and make collision and navigation ignore it. In the end Cubiquity made this easy and very quickly we had the effect you see in the game. I’m glad David encouraged me to try to get this working as I think it makes a big difference to the feel of the game.

With about an hour to go I realised that while we were recording the player’s score to the screen during the game it was hard to pay attention to it while playing so often you didn’t know what highscore you’d achieved. With less than an hour to go until we would stop development I threw together a highscore system which ended up working very well.

David spent the last hour or two doing things like writing a readme, looking into the submission process, setting up hosting for the game download and making some artwork. In the end we submitted at about 19:00 on Monday.

Final thoughts

Matt

Since I was alone doing the programming there was a lot of pressure to get something working at the beginning. However as soon as we were underway I got into the flow of it and really enjoyed it. I think we were realistic with our scheduling over the weekend with

• Day 1: Prototype of game
• Day 2: Make it into a real game that is theoretically submittable
• Day 3: Polish

Unreal Engine really did make things very easy and it’s great to still be using the engine which I first played with 17 years ago. Making real use of Cubiquity with UE4 showed me the areas where I should focus next, particularly the packaging pipeline and asset management.

The things I’m most proud of are the voxel destruction and the highscore system. They were both very late additions but they’re the main things that have been mentioned on the Ludum Dare review page. They both could have easily been left out but the game would have definitely been worse off without them. This really demonstrates to me the importance of polish in a game and helps justify that final ‘10%’.

David

This Ludum Dare was a really interesting experience for me. Despite being a programmer, I was keen to try my hand at doing art because being a Jack-of-all-trades is very valuable in indie game development. I’ve also been really impressed by some of the things I’ve seen made with MagicaVoxel, so was curious how well I could do, and I’m pretty happy with the result considering my previous voxel art experience was limited to making the enemies in Voxeliens (about 50 voxels each!).

One quadrant of the map loaded in MagicaVoxel

MagicaVoxel is a very cool program and I’d definitely recommend budding voxel artists play around with it for a few hours. There isn’t a lot of documentation though, and most things had to be discovered by trial and error. There are alternatives such as VoxelShop and Qubicle Constructor so I hope to play with those in the future to see how they compare (the main reason for using MagicaVoxel was that we already had a rudimentary importer for it).

Overall I really enjoyed doing voxel art and hope to do more in the future. In the past I have purchased small pieces of voxel art but I don’t think I’ll be doing that again when I can make it myself! This should open up many more options for making future demos in Cubiquity.

The post Our first game jam: Ludum Dare 33 appeared first on Volumes Of Fun.

Just a quick notice for those who have been waiting on news of the Unreal Engine 4 integration of Cubiquity. Today I have released a pre-alpha development preview of the plugin.

Development is happening on GitHub under our new GitHub organisation. If you want to keep up-to-date with the latest developments, that’s the place to be. For information about how to test out the plugin, see the post on the Unreal Engine forums.

Do note that this is still a very early release which while functional is quite rough around the edges. Expect bugs and missing features but do let me know on the Unreal Engine forum post if you give it a try or of there are features want.

The post Development preview of Cubiquity for UE4 appeared first on Volumes Of Fun.

Well we’ve got some exciting news today – we’re pleased to announce that Cubiquity for Unity3D is now available for free! It has always been free for non-commercial and evaluation use, but we are removing this restriction so that you can use the system for commercial purposes too. This is effective immediately, and you can download Cubiquity for Unity3D via the asset store or from BitBucket.

Cubiquity let’s you create natural voxel terrains and edit them in real time, or build your worlds from millions of tiny colored cubes.

So what has led to this decision? Well, there are a number of factors at play here:

Time restrictions: Over the last year we have spent a lot of time developing Cubiquity for Unity, but I anticipate time being less plentiful in the future. I’ve just accepted a new job as a senior software engineer, expect to be moving house in the coming year, and we have also had Voxeliens be accepted onto Steam. With less time available for development and support I don’t feel comfortable charging money for the system.

Research aims: There is a huge difference between a research-oriented project and a commercial one. Selling Cubiquity for Unity3D means a lot of work has to go into the workflow, documentation, support, and other tasks which are frankly not much fun. I’d rather shift the focus and spend more time developing cool features and demos, or doing more general voxel research.

Increase number of users: Getting paid for developing Cubiquity for Unity3D definitely has it advantages, but I can honestly say that the satisfaction of seeing someone else use your system is far more rewarding. We really hope that going free can further increase adoption and that we’ll see more games building on Cubiquity.

So what’s the catch?

There isn’t really a catch, but users should be aware that the core Cubiquity library remains closed source. A precompiled version of this Cubiquity library is shipped with Cubiquity for Unity3D and you can use this mostly as you please (see asset store terms and conditions) but you don’t have the source code to build it yourself. You do however have the C# scripts and shader code which integrate this library with Unity.

We do still have further opportunities to generate revenue from Cubiquity by charging for source code licenses, charging for additional platforms (e.g. mobile), or offering contract services. I don’t yet know if we’ll pursue any of these but there are no short-term plans to do so.

What about Unreal Engine 4 (UE4)?

In principle none of the above should affect Cubiquity for UE4. Matt is still working on this though again he is limited to his spare time. The pricing and distribution model for Cubiquity for UE4 may or may not match the Unity version – we simply haven’t decided this yet.

Support

All support for Cubiquity for Unity3D will be handled through our existing thread on the Unity forums. There is also a board on our own Volumes of Fun forum, but we encourage users to use the Unity thread where possible as it boosts the visibility of the system and shows an active community. Please avoid sending email or private messages unless the content really needs to be private, as we try to keep communication open where possible.

Anyway, we hope you enjoy playing with Cubiquity for Unity3D and look forward to seeing what you create!

The post Cubiquity for Unity3D is now free! appeared first on Volumes Of Fun.

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)

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.

Morton index calculation

Jeroen Baert did some extensive tests on the most performant way to determine Morton curve positions from a 3D input position. The conclusion was that it is fastest to make use of a lookup table rather than perform a series of bitwise operations – a perhaps surprising result given the relative cost of processor cycles vs. memory access on modern hardware.

We tested both approaches and were able to verify Jeroen’s original findings. Compared to using a simple linear index for the 3D position, computing and accessing a Morton index took roughly four times as long. By comparison, using the lookup table only took about 40% longer than the linear index, clearly showing the benefits of this approach. None-the-less, a 40% increase in voxel access time is a significant price to pay even given the other advantages of the Morton ordering, and it is here that we make our first useful observation.

Jeroen is working in the context of SVO rendering and is using very large volumes. His function to map a 3D position to on the Morton curve looks as follows:

inline uint64_t mortonEncode_LUT(unsigned int x, unsigned int y, unsigned int z)
{
    uint64_t answer = 0;
    answer =    morton256_z[(z >> 16) & 0xFF ] | // we start by shifting the third byte, since we only look at the first 21 bits
                morton256_y[(y >> 16) & 0xFF ] |
                morton256_x[(x >> 16) & 0xFF ];
    answer = answer << 48 | morton256_z[(z >> 8) & 0xFF ] | // shifting second byte
                morton256_y[(y >> 8) & 0xFF ] |
                morton256_x[(x >> 8) & 0xFF ];
    answer = answer << 24 |
                morton256_z[(z) & 0xFF ] | // first byte
                morton256_y[(y) & 0xFF ] |
                morton256_x[(x) & 0xFF ];
    return answer;
}

The variables ‘morton256_x’, ‘morton256_y’, and ‘morton256_z’ are the lookup tables, and each stores 256 entries (enough to perform the mapping for a single byte) due to the impracticality of having an entry in the lookup table for every possible value of the unsigned int inputs. Construction of the full Morton key is therefore done by using these lookup tables repeatedly to process each byte of the input, and them combining them with more bitwise operations.

For our purposes the size of each chunk is actually very limited, and setting a hard limit of 256^3 seems reasonable. The actual volume can of course be much larger, consisting of many of these chunks. Therefore we apply this hard limit and reduce the above code to just three lookups which are OR’d:

template <typename VoxelType>
VoxelType PagedVolume<VoxelType>::Chunk::getVoxel(uint32_t uXPos, uint32_t uYPos, uint32_t uZPos) const
{
    uint32_t index = morton256_x[uXPos] | morton256_y[uYPos] | morton256_z[uZPos];
    return m_tData[index];
}

With this change the calculation of the position on the Morton curve is about 1-2% faster than with the linear version, though with such a small improvement it is hard to be sure. At least, we are not paying any extra access cost for the benefits which Morton ordering provides.

Fast neighbourhood access

As well as ensuring that random access to any voxel is as fast as possible, it is also important to consider realistic access patterns. In the context of voxel engines this typically means providing fast access to a given voxel’s neighbours as this is often required for tasks such as filtering, normal estimation, and surface extraction.

Access to such neighbours is trivial with a simple linear ordering. For a given position (x,y,z), if we want to access position (x+1,y,z) then we know it is simply the next voxel in memory. There is no need to work out which chunk it is in (disregarding edge cases here) nor to perform the index calculations. In PolyVox we provide ‘peek…()’ functions to retrieve a neighbour of our current voxel, and so an older (linear) version of PolyVox peeked one voxel in the x direction as follows:

template <typename VoxelType>
VoxelType PagedVolume<VoxelType>::Sampler::peekVoxel1px0py0pz(void) const
{
    if(CAN_GO_POS_X(this->mXPosInVolume) )
    {
        return *(mCurrentVoxel + 1);
    }
    return this->mVolume->getVoxel(this->mXPosInVolume+1,this->mYPosInVolume,this->mZPosInVolume);
}

Note that the ‘CAN_GO_POS_X’ macro was just to ensure we were not on a chunk boundary, because if we were then our clever trick didn’t apply and we fell back on a regular call to getVoxel(). Peeking in multiple directions was more complex but the same principle applied:

template <typename VoxelType>
VoxelType PagedVolume<VoxelType>::Sampler::peekVoxel1px1py1pz(void) const
{
    if(CAN_GO_POS_X(this->mXPosInVolume) && CAN_GO_POS_Y(this->mYPosInVolume) && CAN_GO_POS_Z(this->mZPosInVolume) )
    {
        return *(mCurrentVoxel + 1 + this->mVolume->m_uChunkSideLength + this->mVolume->m_uChunkSideLength*this->mVolume->m_uChunkSideLength);
    }
    return this->mVolume->getVoxel(this->mXPosInVolume+1,this->mYPosInVolume+1,this->mZPosInVolume+1);
}

However, the situation becomes more complex when Morton ordering is applied. In this case, the neighbouring voxel in the x direction is not simply next to the current voxel in memory, and things get even harder when peeking in multiple directions at once. We did not find much information on how to handle this correctly, which is why we decided to present our solution here.

The naive approach is to take the Morton position for our current voxel and reverse the encoding process to obtain the original (x,y,z) position. This can then be modified by adding or subtracting the desired offset to the desired component(s), and the resulting 3D position can then be re-encoded into an index on the Morton curve. Clearly this involves quite a lot of processing.

It is possible to directly combine (‘add’?) two Morton positions as alluded to by this StackOverflow answer. However, this is still relatively expensive and again requires some significant bit-shifting. Update: Fabian Giesen has a much more detailed coverage (and more efficient version) of this approach – see the comments and also Texture tiling and swizzling.

At this point Matt made a useful observation. As he states there, “for a given (x,y,z) which has a Morton position p; if we want to peek at (x+1,y,z) then the amount by which p must increase, Δp, is dependent only on x and is independent of y and z. This same logic holds for peeking in y and z”. In other words, we can make use of three more lookup tables (for x, y, and z) which store the offset for moving a single voxel in each direction.

Such lookup tables can be generated by a simple program such as this (based on this code) which computes the offset between different pairs of adjacent x, y and z positions. The size of the lookup table needs to be at least as large as the largest chunk size we wish to support, though smaller chunk sizes are also supported by this as the elements of a smaller table are a subset of the elements of the large table.

In PolyVox we are making use of three 256 element tables allowing us to support chunks of up to 256^3 voxels. The table for moving/peeking one voxel in the x direction is:

static const std::array<int32_t, 256> deltaX =
{
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 28087,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 224695,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 28087,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 1797559,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 28087,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 224695,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 28087,
    1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1, 3511, 1, 7, 1, 55, 1, 7, 1, 439, 1, 7, 1, 55, 1, 7, 1
};

and you can find the other tables in the PolyVox source here. We also define a few macros to make using the tables easier:

...
#define POS_X_DELTA (deltaX[this->m_uXPosInChunk])
...

With this is place, the Morton version of our function for peeking one voxel in the x direction becomes as simple as:

template <typename VoxelType>
VoxelType PagedVolume<VoxelType>::Sampler::peekVoxel1px0py0pz(void) const
{
    if (CAN_GO_POS_X(this->m_uXPosInChunk))
    {
        return *(mCurrentVoxel + POS_X_DELTA);
    }
    return this->mVolume->getVoxel(this->mXPosInVolume+1,this->mYPosInVolume,this->mZPosInVolume);
}

and for peeking multiple directions at once:

template <typename VoxelType>
VoxelType PagedVolume<VoxelType>::Sampler::peekVoxel1px1py1pz(void) const
{
    if (CAN_GO_POS_X(this->m_uXPosInChunk) && CAN_GO_POS_Y(this->m_uYPosInChunk) && CAN_GO_POS_Z(this->m_uZPosInChunk))
    {
        return *(mCurrentVoxel + POS_X_DELTA + POS_Y_DELTA + POS_Z_DELTA);
    }
    return this->mVolume->getVoxel(this->mXPosInVolume+1,this->mYPosInVolume+1,this->mZPosInVolume+1);
}

Conclusion

We have found that Morton ordering works well for storing voxel data in chunks inside PolyVox. While we can’t be sure that computing a Morton position is quite as fast as computing a linear position, we can say that the improved memory access time at least makes up for this due to the improved cache locality. Benefits such as improved compression and easier downsampling are then essentially free.

If you are interested in any of our work above then you can check out the PolyVox code in BitBucket (currently you need the develop branch) and look at the PagedVolume*.h/inl files. If you want to see the discussion and tests which led to the conclusions above then you can have a read of our thread in the issue tracker.

In the future we intend to have a few more of these posts covering the low-level details of PolyVox and Cubiquity, so stay tuned!

The post Implementing Morton ordering for chunked voxel data appeared first on Volumes Of Fun.

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.

The post Update on Cubiquity for Unreal Engine 4 appeared first on Volumes Of Fun.