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

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

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

Python bindings for PolyVox preview

As part of the next release of PolyVox, we’re going to have the first Python bindings available and supported as well as preliminary support for C♯ bindings. This will allow easy integration of voxels into the technologies you’re already using.

History

For a long time now (at least 4 years) we’ve had some form of Python bindings available for PolyVox, created via the SWIG tool. If you were paying attention in those days, you would have seen that the bindings were often broken or even disabled from building completely. This was largely due to the fact that PolyVox was a fast-developing piece of software without a stable API. We didn’t want to slow down the development of new features by having the impedance of also having to update the bindings.

However, since we starting making proper numbered releases (beginning with 0.2.0 last year) the API has settled down and we’re making promises about how much (or little) it will change. This makes it a much more suitable target for building bindings to other languages.

Current status of Python bindings

My main target for the next release of PolyVox (0.3 when it’s out) has been improving and polishing the bindings for Python. In addition to the Python bindings, I have also enabled the building of C♯ bindings for those who would like to try those out too. The Python bindings are better supported however (we have nightly tests run on them, documentation and a demonstration example) and are less liable to change.

If you’re interested in taking a look, then I’ve uploaded a first draft of a section documenting the Python bindings which introduces the bindings and goes through a short code example. That short example is expanded as a full example in the usual example location, PythonExample.py, which renders a blocky sphere to the screen using Python, PyOpenGL and PyGame without a single line of C++ needing to be written.

Voxel sphere rendered by Python

A voxel sphere rendered though PyOpenGL

For example, creating a volume is as simple as

import PolyVoxCore as pv

r = pv.Region(pv.Vector3Dint32_t(0,0,0), pv.Vector3Dint32_t(63,63,63))
vol = pv.SimpleVolumeuint8(r)

You can set the value of any voxel with a single call like:

vol.setVoxelAt(x, y, z, 10)

and you can extract a polygon mesh to be passed to your 3D engine of choice with

mesh = pv.SurfaceMeshPositionMaterialNormal()
extractor = pv.CubicSurfaceExtractorWithNormalsSimpleVolumeuint8(vol, r, mesh)
extractor.execute()

The unusually long names for the classes is an artefact of SWIG being able to represent all the varieties of C++ template instances. You’ll also notice that the API is not very Pythonic at present. I’m trying to get all the functionality working before adding another layer of Pythonicness.

All of the above is already in the develop branch of Git already so feel free to try it out. If you have any question please do ask in the comments below or in the forums.

In a future post I’ll detail some of the technical challenges I’ve faced to get all of PolyVox’s functionality working in both Python and C♯ via SWIG.

Share

A quick update and some new screenshots

I thought I’d write a quick update on where we stand with our various projects as I feel like we’re juggling a dozen things at a time here 🙂 I’ve thrown in some pictures to spice it up a bit, but if you want to see these when they are fresh then be sure to follow us on Twitter.

Cubiquity

Since the first tech demo we have implemented threading in Cubiquity so that surface extraction can be performed in the background. This improves loading times and responsiveness but currently it only works with PolyVox’s SimpleVolume, which limits the amount of volume data we can load at a time. I’ve also done some work overhauling the shaders so that normal mapping is now supported, and hopefully this will get improved further in the future.

Normal mapping the voxels in Cubiquity

PolyVox

The most significant addition to PolyVox is that the LargeVolume class now supports plugable compression code. We’ve also provided an implementation based on the miniz library. This works well for smooth terrain while the existing RLE compressor can be used for cubic ‘Minecraft style’ terrain.

Next up we need to improve the thread safety of the LargeVolume as this has been requested many times, and we’re starting to need it for Cubiquity (as mentioned above).

VolDat

We’ve received some feedback about the format and will do a proper post about this soon. The main issues raised are paging for very large volumes (probably beyond the scope of what we are aiming for here) and also an existing similar format (but it doesn’t make the slice data easy to visualise). We’ve also bee working on some test data sets which we will make available as part of an online archive. A couple of examples are below:

A ‘Build and Shoot’ map loaded into Cubiquity. Source data is here: http://www.buildandshoot.com/viewtopic.php?f=8&t=913

I wrote a program to create a Mandelbulb as these can be very large and still have fine detail. This one is only 512x512x512 though.

Unity3D

I downloaded Unity and had a play with it last weekend. It’s a really cool system, and I can see why it’s got such a big following as it makes development really easy. Integrating Cubiquity is a bit more difficult than I hoped as it turns out that plugin .dlls need to provide a ‘C’ interface (not C++) so we’re having to create a wrapper for Cubiquity. This takes a bit of time but shouldn’t be a big problem over all.

That will do for now – see you next time 🙂

Share

Introducing: Cubiquity

Regular followers of our blog and forums will know that over the last few months we have done a lot of work integrating PolyVox with the Gameplay3D engine. We’ve also mentioned Unity3D and talked about creating a higher level framework to integrate PolyVox with such external game engines. Today we are pleased to officially introduce this technology as ‘Cubiquity’, and provide a very early demonstration of where we are going with it.
Cubiquity is a C++ library which is currently dependant only on PolyVox and which provides higher-level features such as a scene graph, level-of-detail, mesh management, and tools for manipulating volume data. Additionally we have developed ‘Cubiquity for Gameplay3D’ which basically connects Cubiquity to a Gameplay3D scene node so that volumes can be treated as first-class citizens in Gameplay3D. We also have Lua bindings so that Gameplay3D scripts can create and manipulate volume data.

The video below shows some of the features which are present in the tech demo. Cubiquity supports both cubic (hence the name!) and smooth voxel terrain but only the cubic terrain is being shown at the moment. The terrain in the video has a resolution of 512x512x256 voxels which are displayed as coloured cubes. A LOD system allows these cubes to be grouped together into larger cubes as they move into the distance. The terrain is fully dynamic and can be edited in real time (but note that lighting is baked in to this data set).

As mentioned, we have bindings to Lua which have allowed the whole tech demo to be driven by a simple script. This handles input, drives the rendering loop, and also exposes the entire Gameplay3D API meaning that (in theory) you can take this tech demo and build a game on it. In practice you might want to wait for a more mature version 😉

You can download the tech demo at the link below. Please remember this is a very early version and, amoung other problems, whole system is currently running on a single thread. This causes pauses/hiccups when the terrain is being modified. The initial loading of the terrain is also slow and may take a minute of so.

Download: http://www.volumesoffun.com/downloads/Cubiquity/CubiquityTechDemo_ver_0_1.zip

We do not currently expect Cubiquity to be free, and will probably be targeting the professional indie market with it. Hopefully this will provide a way to support the development of PolyVox (which is also directly benefiting from the development of Cubiquity). That said, it is likely that we will continue to provide free tech demos which can be scripted to make your own games. We’re really still working out the details here.

I think there will probably be a lot of questions about all this, so ask away in the comments. Eventually we’ll get some proper information available on the website.

Share

Level-of-detail for cubic-style terrain with PolyVox

I just thought I’d post an update about some tests I did which worked out a lot better than I once expected. The idea here is to perform LOD for cubic-style meshes simply by downsampling the volume, such that in the distance a group of eight cubes is replaced by a single cube.

In the past I’ve said this wouldn’t work well as the transition would be too visually jarring, but recently I’ve seen a couple of screenshots from voxel engines which do indeed take this approach. I also talked about it with Matt over Christmas, and hacked together a test implementation last night.

The screenshots below start at full resolution and then gradually bring the LOD cut-off distance forward until all parts of the terrain are at the lower LOD. The transition is much less noticeable than I thought, and it practice it would also be much further from the camera.

This has all been implemented within our new framework built on PolyVox and Gameplay3D. Hopefully we’ll be able to provide a demo of this framework in the near future.

Share

PolyVox 0.2.1 released

As a late Christmas present to you all we’ve just released version 0.2.1 of PolyVox. This is a bug fix release to PolyVox 0.2.0.

This release includes the following bug fixes:

  • A compilation error on VS2008 (commit)
  • One of the sampler peek functions would check in the wrong direction before moving (commit)
  • SimpleVolume and LargeVolume had a problem with negative positions (commit, commit)
  • The LowPassFilter test was using the wrong kernel size (commit)

Apart from those bug fixes there are no new features and so should be completely safe to upgrade to.

You can get the details for downloading the source from the PolyVox download page or download directly from these links:

If you’re following us on Git, the 0.2.1 is now what is represented on the master branch.

Share

New home for PolyVox git repo

The source code for PolyVox is now located at BitBucket rather than its previous home on Gitorious. There are a few reasons we wanted to move hosting provider. Primarily we wanted an easier way of keeping track of planned features without messy email threads between David and myself and better bug tracking than our current forum-based method.

BitBucket offered everything we needed and since we were already using it for its unlimited private repos, it made sense to move PolyVox there too.

While we will be using the issue tracker to keep track of features and bugs, we will keep using the forum for most discussions. Feel free so submit any simple/small bugs to the tracker directly e.g. for compile errors etc.

To switch your local clone to follow the new repo on the command line just do the following:

# First check where you're currently pointing
$ git remote -v
origin  git://gitorious.org/polyvox/polyvox.git (fetch)

# Change the 'origin' remote's URL
$ git remote set-url origin https://bitbucket.org/volumesoffun/polyvox.git

# Now, it should look like
$ git remote -v
origin  https://bitbucket.org/volumesoffun/polyvox.git (fetch)

Otherwise, you can just use your GUI tool to change the repo URL to be https://bitbucket.org/volumesoffun/polyvox.git. You should now be able to carry on doing git pull as if nothing had changed.

Share

PolyVox version 0.2 released

We’re pleased to announce that a new version of PolyVox is released today. This release brings a number of improvements to both the library itself and also to our development process. Looking at the library first, the main changes include:

  • Enhanced control over the surface extractors, which allows them to execute on more voxel types (including primitive types)  and also provides more control over the way in which triangles are generated during the extraction process.
  • Much improved documentation, including an expanded manual and API docs. These are still work-in-progress and will be developed further in future releases.
  • Some restructuring of code, particularly the unclassing of raycasting and ambient occlusion functionality. Again this is something we expect to see more of in the future.
  • Lots of warnings and fixes to the unit tests. We use CDash for monitoring the quality of our software and it’s all green for the first time that I can remember.

Some refactoring has made the surface extractors much more flexible.

Additionally, there have been a number of improvements to the build system and development process which were largely spearheaded by Matt. These include:

  • A switch to Git flow for our development process, in order to keep the Git repository in a more stable state and to facilitate collaboration. As a result this is our first release with a proper version number.
  • Improvements to the CMake build system to better detect which optional dependencies are available and to configure the build appropriately.
  • A bash script to automate the process of performing a release.
  • The use of CMake folders to improve navigation in the Visual Studio solution.

Instructions and links for downloading the latest release can be found on the download page. You should also checkout the changelog for more details on the new features, and do come by the forums if you have any questions or problems with this latest release.

Enjoy!

Share