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.

Switching RLE Methods

To quickly test the different RLE methods, do the following in your Chunk class.

import <SpecificRLE_Module> as RLE

This will let you quickly switch between standard RLE and advanced RLE implementation, which I’m going to call Position Aware Run Length Encoding, or PARLE =).

Simple things

We set our encoding for each chunk by doing the following:

values = [ 0 for index in xrange( size ) ]
rleValues = RLE.encode( values )
self.rleVoxels.fill( rleValues )

Why are we creating a list of N length just to compress it to a single value?

Let’s fix this.

First, lets add a “fill” method to our RLE.

For our normal RLE:

def fill( rleValues, value, length ):
    del rleValues[ : ]
    rleValues.append( (length, value) )
    return rleValues

The corresponding test:

fill( encoded, 1, 256 )
decoded = decode( encoded )
print encoded
print decoded
assert encoded[ 0 ] == ( 256, 1 )
assert len( decoded ) == 256

For our PARLE with positioning:

def fill( rleValues, value, length ):
    del rleValues[ : ]
    rleValues.append( (length, 0, value) )
    return rleValues

And the corresponding test:

fill( encoded, 1, 256 )
decoded = decode( encoded )
print encoded
print decoded
assert encoded[ 0 ] == ( 256, 0, 1 )
assert len( decoded ) == 256

We can now change our Chunk constructor to do the following:

rleValues = []
RLE.fill( rleValues, 0, size )
self.rleVoxels.fill( rleValues )

Removing our arrays

Why replace 1 dimension of our arrays, when we can replace them all?!

By using RLE, we’re sacrificing initialisation overhead for a small increase in run-time manipulation overhead. Modifying values with arrays is a simple array lookup (albeit with memory coherency problems). But with RLE we have to seek to the correct position and update our values.

I believe this would give a small memory saving because we’re not creating X x Y x Initial RLE bytes. But we would incur a number of performance issues with the constant array resizing and possibly performance issues with accessing and binary searching even larger arrays.

It also means that chunks of size 2048 x 2048 x 2048 overflow a 32-bit integer and cannot be fully accounted for if the entire array is a honey-comb pattern (every voxel a different value than the lost).

For this reason I haven’t attempted to perform this.

Improving our RLE Data Structure

The RLE data structure we used was a simple Python List.

This is pretty bad for a number of reasons.

  1. Searching is not inherent in the structure, we have to do our own binary search.
  2. As we add and remove from the list, the array will resize.
  3. As the array grows, adding and subtracting becomes slower and slower.

I started to look around for different data structures that would be appropriate.

I thought of using a re-balancing Binary tree, but there is no existing one in Python, not really wanting to roll my own, I kept looking.

A friend suggested B-Trees. I’m not personally sure which is better for this purpose.

Advertisements

One Response to “Creating Voxel Volumes Quicky in Python Part 2”

  1. […] Creating Voxel Volumes Quicky in Python Part 2 « Twisted Pair Development Says: 2011/06/10 at 5:43 pm […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: