Compressing Voxel Data

My first attempt at saving and loading voxel data seems to work reasonably well. It manages to save approx 4 million voxel points in about 64kb which seems reasonable. The compression ratio would decrease as the usefulness of RLE (Run Length Encoding) wanes due to excessive fragmentation. What remains to be done is to only save those blocks that have changed along with the seed. I’m not building never ending minecraft type worlds so i’m dealing with known quantities here. Currently it just saves and loads everything, surprising quickly.

private static readonly long[] HashTable = new long[HSIZE]; // Compresses inputBytes public static byte[] Compress(byte[] inputBytes) { // Starting guess, increase it later if needed int outputByteCountGuess = inputBytes.Length * 2; byte[] tempBuffer = new byte[outputByteCountGuess]; int byteCount = lzf_compress (inputBytes, ref tempBuffer); // If byteCount is 0, then increase buffer and try again while (byteCount == 0) { outputByteCountGuess *=2; tempBuffer = new byte[outputByteCountGuess]; byteCount = lzf_compress (inputBytes, ref tempBuffer); } byte[] outputBytes = new byte[byteCount]; Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount); return outputBytes; } // Decompress outputBytes public static byte[] Decompress(byte[] inputBytes) { // Starting guess, increase it later if needed int outputByteCountGuess = inputBytes.Length * 2; byte[] tempBuffer = new byte[outputByteCountGuess]; int byteCount = lzf_decompress (inputBytes, ref tempBuffer); // If byteCount is 0, then increase buffer and try again while (byteCount == 0) { outputByteCountGuess *=2; tempBuffer = new byte[outputByteCountGuess]; byteCount = lzf_decompress (inputBytes, ref tempBuffer); } byte[] outputBytes = new byte[byteCount]; Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount); return outputBytes; } ///

///Reference to the data to compress ///Reference to a buffer which will contain the compressed data /// The size of the compressed archive in the output buffer public static int lzf_compress(byte[] input, ref byte[] output) { int inputLength = input.Length; int outputLength = output.Length; Array.Clear(HashTable, 0, (int)HSIZE); long hslot; uint iidx = 0; uint oidx = 0; long reference; uint hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); // FRST(in_data, iidx); long off; int lit = 0; for (; 😉 { if (iidx < inputLength – 2) { hval = (hval << 8) | input[iidx + 2]; hslot = ((hval ^ (hval << 5)) >> (int)(((3 * 8 – HLOG)) – hval * 5) & (HSIZE – 1)); reference = HashTable[hslot]; HashTable[hslot] = (long)iidx; if ((off = iidx – reference – 1) < MAX_OFF && iidx + 4 < inputLength && reference > 0 && input[reference + 0] == input[iidx + 0] && input[reference + 1] == input[iidx + 1] && input[reference + 2] == input[iidx + 2] ) { /* match found at *reference++ */ uint len = 2; uint maxlen = (uint)inputLength – iidx – len; maxlen = maxlen > MAX_REF ? MAX_REF : maxlen; if (oidx + lit + 1 + 3 >= outputLength) return 0; do len++; while (len < maxlen && input[reference + len] == input[iidx + len]); if (lit != 0) { output[oidx++] = (byte)(lit – 1); lit = -lit; do output[oidx++] = input[iidx + lit]; while ((++lit) != 0); } len -= 2; iidx++; if (len < 7) { output[oidx++] = (byte)((off >> 8) + (len << 5)); } else { output[oidx++] = (byte)((off >> 8) + (7 << 5)); output[oidx++] = (byte)(len – 7); } output[oidx++] = (byte)off; iidx += len – 1; hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); hval = (hval << 8) | input[iidx + 2]; HashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 – HLOG)) – hval * 5) & (HSIZE – 1))] = iidx; iidx++; hval = (hval << 8) | input[iidx + 2]; HashTable[((hval ^ (hval << 5)) >> (int)(((3 * 8 – HLOG)) – hval * 5) & (HSIZE – 1))] = iidx; iidx++; continue; } } else if (iidx == inputLength) break; /* one more literal byte we must copy */ lit++; iidx++; if (lit == MAX_LIT) { if (oidx + 1 + MAX_LIT >= outputLength) return 0; output[oidx++] = (byte)(MAX_LIT – 1); lit = -lit; do output[oidx++] = input[iidx + lit]; while ((++lit) != 0); } } if (lit != 0) { if (oidx + lit + 1 >= outputLength) return 0; output[oidx++] = (byte)(lit – 1); lit = -lit; do output[oidx++] = input[iidx + lit]; while ((++lit) != 0); } return (int)oidx; } ///

///Reference to the data to decompress ///Reference to a buffer which will contain the decompressed data /// Returns decompressed size public static int lzf_decompress(byte[] input, ref byte[] output) { int inputLength = input.Length; int outputLength = output.Length; uint iidx = 0; uint oidx = 0; do { uint ctrl = input[iidx++]; if (ctrl < (1 << 5)) /* literal run */ { ctrl++; if (oidx + ctrl > outputLength) { //SET_ERRNO (E2BIG); return 0; } do output[oidx++] = input[iidx++]; while ((–ctrl) != 0); } else /* back reference */ { uint len = ctrl >> 5; int reference = (int)(oidx – ((ctrl & 0x1f) << 8) – 1); if (len == 7) len += input[iidx++]; reference -= input[iidx++]; if (oidx + len + 2 > outputLength) { //SET_ERRNO (E2BIG); return 0; } if (reference < 0) { //SET_ERRNO (EINVAL); return 0; } output[oidx++] = output[reference++]; output[oidx++] = output[reference++]; do output[oidx++] = output[reference++]; while ((–len) != 0); } } while (iidx < inputLength); return (int)oidx; } }

One comment

  1. Josh · August 18, 2015

    Hey man its me Again 🙂 just a quick Question im currently Developing a game Called Voxelization ive inputed my Website in the ui box Above if you want to check it out But ..
    Is your engine ever going to be sold or are you working on it for your own personal use ? because whilst the engine im using at the moment is Great it isnt Exactly very good when it comes to performance which kinda sucks … ive noticed alot of things to do with the way you do your engine that look Extremely cool and you have made some Awesome things that i wish i had in my Game such as your lighting and that water you posted a while back! .. i would pay for either Of those two things alone aha.. is it possible you will be doing a tutorial on that water you posted a while back? i have been searching the web for months on some type of tutorial and their is litterally nun .. if you where to do one on that water you would most likely be the first to do it 🙂