Creating Voxel Volumes Quicky in Python Part 2
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 =).
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.
- Searching is not inherent in the structure, we have to do our own binary search.
- As we add and remove from the list, the array will resize.
- 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.