C# - Use "smallest three" compression for transmitting Quaternion rotations in Unity's UNET networking, from 16 bytes to 7 bytes.

QuaternionCompression.cs

// Copyright (c) 2016 StagPoint Software
namespace StagPoint.Networking
{
	using System;

	using UnityEngine;
	using UnityEngine.Networking;

	/// <summary>
	/// Provides some commonly-used functions for transferring compressed data over the network using 
	/// Unity's UNET networking library. 
	/// </summary>
	public static class NetworkingExtensions
	{
		#region Constants and static variables 

		/// <summary>
		/// Used when compressing float values, where the decimal portion of the floating point value
		/// is multiplied by this number prior to storing the result in an Int16. Doing this allows 
		/// us to retain five decimal places, which for many purposes is more than adequate.
		/// </summary>
		private const float FLOAT_PRECISION_MULT = 10000f;

		#endregion 

		#region NetworkReader and NetworkWriter extension methods

		/// <summary>
		/// Writes a compressed Quaternion value to the network stream. This function uses the "smallest three"
		/// method, which is well summarized here: http://gafferongames.com/networked-physics/snapshot-compression/
		/// </summary>
		/// <param name="writer">The stream to write the compressed rotation to.</param>
		/// <param name="rotation">The rotation value to be written to the stream.</param>
		public static void WriteCompressedRotation( this NetworkWriter writer, Quaternion rotation )
		{
			var maxIndex = (byte)0; 
			var maxValue = float.MinValue;
			var sign = 1f;

			// Determine the index of the largest (absolute value) element in the Quaternion.
			// We will transmit only the three smallest elements, and reconstruct the largest
			// element during decoding. 
			for( int i = 0; i < 4; i++ )
			{
				var element = rotation[ i ];
				var abs = Mathf.Abs( rotation[ i ] );
				if( abs > maxValue )
				{
					// We don't need to explicitly transmit the sign bit of the omitted element because you 
					// can make the omitted element always positive by negating the entire quaternion if 
					// the omitted element is negative (in quaternion space (x,y,z,w) and (-x,-y,-z,-w) 
					// represent the same rotation.), but we need to keep track of the sign for use below.
					sign = ( element < 0 ) ? -1 : 1;

					// Keep track of the index of the largest element
					maxIndex = (byte)i;
					maxValue = abs;
				}
			}

			// If the maximum value is approximately 1f (such as Quaternion.identity [0,0,0,1]), then we can 
			// reduce storage even further due to the fact that all other fields must be 0f by definition, so 
			// we only need to send the index of the largest field.
			if( Mathf.Approximately( maxValue, 1f ) )
			{
				// Again, don't need to transmit the sign since in quaternion space (x,y,z,w) and (-x,-y,-z,-w) 
				// represent the same rotation. We only need to send the index of the single element whose value
				// is 1f in order to recreate an equivalent rotation on the receiver.
				writer.Write( maxIndex + 4 );
				return;
			}

			var a = (short)0;
			var b = (short)0;
			var c = (short)0;

			// We multiply the value of each element by QUAT_PRECISION_MULT before converting to 16-bit integer 
			// in order to maintain precision. This is necessary since by definition each of the three smallest 
			// elements are less than 1.0, and the conversion to 16-bit integer would otherwise truncate everything 
			// to the right of the decimal place. This allows us to keep five decimal places.

			if( maxIndex == 0 )
			{
				a = (short)( rotation.y * sign * FLOAT_PRECISION_MULT );
				b = (short)( rotation.z * sign * FLOAT_PRECISION_MULT );
				c = (short)( rotation.w * sign * FLOAT_PRECISION_MULT );
			}
			else if( maxIndex == 1 )
			{
				a = (short)( rotation.x * sign * FLOAT_PRECISION_MULT );
				b = (short)( rotation.z * sign * FLOAT_PRECISION_MULT );
				c = (short)( rotation.w * sign * FLOAT_PRECISION_MULT );
			}
			else if( maxIndex == 2 )
			{
				a = (short)( rotation.x * sign * FLOAT_PRECISION_MULT );
				b = (short)( rotation.y * sign * FLOAT_PRECISION_MULT );
				c = (short)( rotation.w * sign * FLOAT_PRECISION_MULT );
			}
			else
			{
				a = (short)( rotation.x * sign * FLOAT_PRECISION_MULT );
				b = (short)( rotation.y * sign * FLOAT_PRECISION_MULT );
				c = (short)( rotation.z * sign * FLOAT_PRECISION_MULT );
			}

			writer.Write( maxIndex );
			writer.Write( a );
			writer.Write( b );
			writer.Write( c );
		}

		/// <summary>
		/// Reads a compressed rotation value from the network stream. This value must have been previously written
		/// with WriteCompressedRotation() in order to be properly decompressed.
		/// </summary>
		/// <param name="reader">The network stream to read the compressed rotation value from.</param>
		/// <returns>Returns the uncompressed rotation value as a Quaternion.</returns>
		public static Quaternion ReadCompressedRotation( this NetworkReader reader )
		{
			// Read the index of the omitted field from the stream.
			var maxIndex = reader.ReadByte();

			// Values between 4 and 7 indicate that only the index of the single field whose value is 1f was
			// sent, and (maxIndex - 4) is the correct index for that field.
			if( maxIndex >= 4 && maxIndex <= 7 )
			{
				var x = ( maxIndex == 4 ) ? 1f : 0f;
				var y = ( maxIndex == 5 ) ? 1f : 0f;
				var z = ( maxIndex == 6 ) ? 1f : 0f;
				var w = ( maxIndex == 7 ) ? 1f : 0f;

				return new Quaternion( x, y, z, w );
			}

			// Read the other three fields and derive the value of the omitted field
			var a = (float)reader.ReadInt16() / FLOAT_PRECISION_MULT;
			var b = (float)reader.ReadInt16() / FLOAT_PRECISION_MULT;
			var c = (float)reader.ReadInt16() / FLOAT_PRECISION_MULT;
			var d = Mathf.Sqrt( 1f - ( a * a + b * b + c * c ) );

			if( maxIndex == 0 )
				return new Quaternion( d, a, b, c );
			else if( maxIndex == 1 )
				return new Quaternion( a, d, b, c );
			else if( maxIndex == 2 )
				return new Quaternion( a, b, d, c );

			return new Quaternion( a, b, c, d );
		}

		#endregion 
	}
}

FYI if this is used with lots of other writes, and reads, you need to ensure that the same amount of data is written and read. So line 69 needs to have its values wrapped and converted to byte, as that is what is read on the other side.

writer.Write( (byte)(maxIndex + 4) );

I was getting very rare and strange indexOutOfRange errors due to this.

Isn't this a bad idea when sending TONS of quaternions over time? all those mult/div operations... hmm.. Save data but kill the server practicability style?

@hyakugei - I think I see what you mean. I've been using a heavily refactored version of this code internally lately so that slipped by me, thanks.

@Leodau - It seems to work pretty well for us. I guess the best thing would be to benchmark both ways and check the results for yourself. In our case the added math operations are not significant enough to cause any problems whatsoever, but the reduction in bandwidth was pretty significant.

@Leodau I think you underestimate the speed of modern FPUs. FWIW I did a simple arithmetic test. Let's examine this from two ends: the sending side (the server), and the receiving side (the client). Note that for all tests I perform the test 10 times in a row and measure each time to ensure stable timing. They were performed on a 3.5GHz CPU.

On the sending side, as best as I can tell you're working with six multiples - for three elements, element * sign * precision. Performing these operations 100,000 times in a row took about 1ms. That's 100,000 quaternions on the sending side with no noticeable performance impact - which is a pretty impressive number of quaternions.

On the receiving side, we introduce three divides and a square root on top of three multiplies. Performing these operations, again 100,000 times in a row, yielded 4ms. It's a lot slower, but I'd point out that if your client is getting 100,000 quaternions you've got much bigger architectural problems (at that many quaternions, you'd be absolutely slamming your available network bandwidth).

You should replace the float->short cast and instead use Mathf.RoundToInt().
Using that, and editing the method to instead compress down to 5 bytes / rotation, I got the average compression error down to 0.005 degrees.

Oh, nice. I'll look into that when I have the chance, thanks.

I see no code updates from the comments here... is there a version with all the suggested fixes and changes?

Since I no longer use Unity, and all internal version updates have been largely forgotten, there are likely never going to be any additional updates.

If anyone else has an updated version posted somewhere that they'd like to let us know about, I'd be happy to redirect people to it.