Example of Minecraft style polygonisation

Good walkthrough of rendering a voxel volume from start to finish in a Minecraft style.

It has the following problems however:

• Single volume, no hierarchy.
• Lack of hierarchy makes polygonisation harder, it must be done in one sweep.
• Lack of hierarchy makes modification harder.
• It performs 2 sweeps of the volume, one to calculate number of primitives, another to create them.
• The C functions don’t compile in MSVC2008.

But it’s a good source of information on lighting and shader implementations.

Grouping Voxels with Hilbert Curves

A friend suggested quite a good idea.

Represent Voxels internally using a Hilbert Curve, the same algorithm XKCD used to display a map of IPv4.

Once you’ve got this, you can perform an RLE compression algorithm to it.

 

This paper discusses using Octrees and Hilbert curves to represent masses of voxel data.

RLE? That’s so yesterday!

Before writing my RLE implementation, a friend sent me a link to the blist package for Python.

I didn’t see anything amazing on the front page. Makes a 5M size list. Sure, whatever.

What the front page fails to say is that creating that 5M size blist is insanely fast. Because it doesn’t blindly allocate memory like a normal Python list would.

The “blist” list type is faster to add / remove than a Python list, and it supports copy-on-write semantics.

So I’m actually going to remove my cryptic RLE encoding and return to normal 3D array semantics using blists!

Creating Voxel Volumes Quicky in Python Part 2

So we created a volume pretty quickly Part 1, we also implemented basic RLE and Position Aware RLE (PARLE).

Read on for a few minor improvements we can make with little effort.

Run Length Encoding in Python

The following code is my implementation of RLE in Python. I’ve included a method to modify values without having to decode the entire value.

Please note that this algorithm is inferior to the RLE with Positioning I posted about here.

Position Aware Run Length Encoding in Python

I mentioned previously wanting to improve the RLE to include position information. I’m sure it’s already got a name, but I’m going to call it Position Aware RLE (PARLE).

Below is the code I’ve written to accomplish this. I’m sure someone can come up with a more concise way of writing it, but this is the best I can do at the moment.

Creating Voxel Volumes Quicky in Python

Creating large chunks of memory is quite tricky in Python because of a number of overheads. I’ve been attempting this myself and have found a fast method to do this which combines a few handy optimisations we would need later on for a Voxel Engine anyway.

Please be aware that the code evolves along the way, so don’t blindly copy and paste the first examples =).

Also, the WordPress theme is cutting of some text. If you copy and paste it, it is still there.

This post is continued in Position Aware RLE, RLE and Part 2.