Unit Packing

A library for storing unit vectors in a representnation that lends itself to saving space on disk. You can read more on how some of these methods work here.

API

Currently there are 8 implemented methods for packing and unpacking unit vectors.

PackOct32/UnpackOct32
PackOct24/UnpackOct24
PackOct16/UnpackOct16
PackOctQuad16/UnpackOctQuad16
PackOctQuad24/UnpackOctQuad24
PackOctQuad32/UnpackOctQuad32
PackAlg24/UnpackAlg24
PackCoarse24/UnpackCoarse24

Example

package main

import (
	"math/rand"
	"os"

	"github.com/EliCDavis/vector"
	"github.com/recolude/unitpacking/unitpacking"
)

func main() {
	numOfVectors := 10000000
	unitVectors := make([]vector.Vector3, numOfVectors)

	// Generate a bunch of unit vectors
	for i := 0; i < numOfVectors; i++ {
		unitVectors[i] = vector.NewVector3(
			(rand.Float64()*2.0)-1.0,
			(rand.Float64()*2.0)-1.0,
			(rand.Float64()*2.0)-1.0,
		).Normalized()
	}

	out, err := os.Create("example.data")
	if err != nil {
		panic(err)
	}

	// Write out unit vectors in packed format
	for _, unitVector := range unitVectors {
		out.Write(unitpacking.PackOct24(unitVector))
	}
}

Benchmark

To benchmark the different methods, I took a bunch of common 3D models seen in computer graphics and generated both "smooth" and "flat" normals for them and used the normals as the unit vectors. Also one dataset is just 10 million randomly generated unit vectors. I hope the information present here will let you make an informed decision to pick the best method for your use case.

Lowest Error

If what you are looking for is the lowest introduced error from converting between packed format and unpacked, you will want to go with oct32 format. If you can handle a small bit of error in your calculations and speed is not a concern I would go with octquad24.

File Size

Just by adopting one of these packing methods, you will see a cut of over half the space needed to store a unit vector as your datasets grow. The image below is a sums the compressed data from all datasets packed by each method. Baseline represents each unit vector being written out plainly as 3 32bit floats. If you want to reduce the filesize as much as possible, I would pick octquad16, as it has the highest amount of precision for all 16bit methods.

It appears that the alg24 method lends itself to better compressability than oct24 and oct32 methods in some datasets. This might be a more attractive method if introducing some ammount of error to your program is not a problem.

Speed

If your goal is to compress data as fast as possible, I would go with the alg24 method, as it has one of the faster runtimes while having way more precision than coarse24.

Why Would I Ever Bother With Coarse?

Even though coarse24 has the highest average error by far, there are still situations where this method might be what you need:

• You have to read this data in a language other than golang.
  • This method simply writes each float value to a single byte. While this is inefficient, it is simple to implement in other languages that need to read this data.
• You want to sample some random vector component quickly.
  • All other methods take advantage of math/algorithms to represent the data in an efficient format. To get the X,Y, and Z components back you have to re-apply this math/algorithms to get the original data back.
  • If you wanted to get the average value along some axis under the coarse method however, you can easily just sample the byte array immediately.

Hard Data

Resources

• A Survey of Efficient Representations for Independent Unit Vectors
• Alec Jacobson's Common 3D Test Models