Represents 2D Morton Codes by interleaving two 16-bit unsigned integer values into a 32-bit unsigned integer.

Morton2D.cs

// **************************************************
// EXAMPLE USAGE:
//
// // Returns a single value with arguments x and y interleaved
// var code = MortonCode2D.Interleave( 123, 456 );
//
// // Extracts the interleaved values (123 and 456) into integer variables x and y
// MortonCode2D.Deinterleave( code, out int x, out int y )
//
// **************************************************

// See this link for more information: https://en.wikipedia.org/wiki/Z-order_curve

public static class MortonCode2D
{
	/// <summary>
	/// Returns a Morton code interleaving the component-wise difference of the X and Y values from two encodings.
	/// </summary>
	/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint TesseralSubtract( uint z, uint w )
	{
		uint xdiff = ( z & 0x55555555 ) - ( w & 0x55555555 );
		uint ydiff = ( z & 0xAAAAAAAA ) - ( w & 0xAAAAAAAA );

		return ( xdiff & 0x55555555 ) | ( ydiff & 0xAAAAAAAA );
	}

	/// <summary>
	/// Returns a Morton code interleaving the component-wise sum of the X and Y values from two encodings.
	/// </summary>
	/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint ComponentwiseAdd( uint z, uint w )
	{
		uint xsum = ( z | 0xAAAAAAAA ) + ( w & 0x55555555 );
		uint ysum = ( z | 0x55555555 ) + ( w & 0xAAAAAAAA );

		return ( xsum & 0x55555555 ) | ( ysum & 0xAAAAAAAA );
	}

	/// <summary>
	/// Returns a Morton code interleaving the component-wise minimum of the X and Y values from two encodings.
	/// </summary>
	/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint ComponentwiseMin( uint z, uint w ) 
	{
		uint xdiff = ( z & 0x55555555 ) - ( w & 0x55555555 );
		uint ydiff = ( z >> 1 & 0x55555555 ) - ( w >> 1 & 0x55555555 );

		uint maskx = (uint)( (int)xdiff >> 31 );
		uint masky = (uint)( (int)ydiff >> 31 );

		uint xmin = ( maskx & z ) | ( ~maskx & w );
		uint ymin = ( masky & z ) | ( ~masky & w );

		return ( xmin & 0x55555555 ) | ( ymin & 0xAAAAAAAA );
	}

	/// <summary>
	/// Returns a Morton code interleaving the component-wise maximum of the X and Y values from two encodings.
	/// </summary>
	/// <param name="z">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	/// <param name="w">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint ComponentwiseMax( uint z, uint w )
	{
		uint xdiff = ( z & 0x55555555 ) - ( w & 0x55555555 );
		uint ydiff = ( z >> 1 & 0x55555555 ) - ( w >> 1 & 0x55555555 );

		uint maskx = (uint)( (int)xdiff >> 31 );
		uint masky = (uint)( (int)ydiff >> 31 );

		uint xmin = ( ~maskx & z ) | ( maskx & w );
		uint ymin = ( ~masky & z ) | ( masky & w );

		return ( xmin & 0x55555555 ) | ( ymin & 0xAAAAAAAA );
	}

	/// <summary>
	/// Increments the X value in the interleaved Morton code, clamped to <paramref name="maxValue"/>
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint IncrementX_Clamped( uint code, uint maxValue )
	{
		uint xsum = ( ( code | 0xAAAAAAAA ) + 1 ) & 0x55555555;
		uint xdiff = xsum - maxValue;
		uint maskx = (uint)( (int)xdiff << 1 >> 31 );
		uint xsat = ( maskx & xsum ) | ( ~maskx & maxValue );

		return xsat | ( code & 0xAAAAAAAA );
	}

	/// <summary>
	/// Increments the Y value in the interleaved Morton code, clamped to <paramref name="maxValue"/>
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint IncrementY_Clamped( uint code, uint maxValue )
	{
		uint ysum = ( ( code | 0x55555555 ) + 2 ) & 0xAAAAAAAA;
		uint ydiff = ysum - maxValue;
		uint masky = (uint)( (int)ydiff >> 31 );
		uint ysat = ( masky & ysum ) | ( ~masky & maxValue );

		return ysat | ( code & 0x55555555 );
	}

	/// <summary>
	/// Decrements the X value in the interleaved Morton code, clamped to <paramref name="minValue"/>
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint DecrementX_Clamped( uint code, uint minValue )
	{
		uint xsum = ( ( code & 0x55555555 ) - 1 ) & 0x55555555;
		uint xdiff = xsum - minValue;
		uint maskx = (uint)( (int)xdiff << 1 >> 31 );
		uint xsat = ( ~maskx & xsum ) | ( maskx & minValue );

		return xsat | ( code & 0xAAAAAAAA );
	}

	/// <summary>
	/// Decrements the Y value in the interleaved Morton code, clamped to <paramref name="minValue"/>
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint DecrementY_Clamped( uint code, uint minValue )
	{
		uint ysum = ( ( code & 0xAAAAAAAA ) - 2 ) & 0xAAAAAAAA;
		uint ydiff = ysum - minValue;
		uint masky = (uint)( (int)ydiff >> 31 );
		uint ysat = ( ~masky & ysum ) | ( masky & minValue );

		return ysat | ( code & 0x55555555 );
	}

	/// <summary>
	/// Increments the X value in the interleaved Morton code
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint IncrementX( uint code )
	{
		uint xsum = ( code | 0xAAAAAAAA ) + 1;
		return ( xsum & 0x55555555 ) | ( code & 0xAAAAAAAA );
	}

	/// <summary>
	/// Increments the Y value in the interleaved Morton code
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint IncrementY( uint code )
	{
		uint ysum = ( code | 0x55555555 ) + 2;
		return ( ysum & 0xAAAAAAAA ) | ( code & 0x55555555 );
	}

	/// <summary>
	/// Decrements the X value in the interleaved Morton code
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint DecrementX( uint code )
	{
		uint xsum = ( code & 0x55555555 ) - 1;
		return ( xsum & 0x55555555 ) | ( code & 0xAAAAAAAA );
	}

	/// <summary>
	/// Decrements the Y value in the interleaved Morton code
	/// </summary>
	/// <param name="code">A Morton code interleaving a 16-bit unsigned X and Y value</param>
	public static uint DecrementY( uint code )
	{
		uint ysum = ( code & 0xAAAAAAAA ) - 2;
		return ( ysum & 0xAAAAAAAA ) | ( code & 0x55555555 );
	}
	
	/// <summary>
	/// Returns the interleaved values stored in both the odd and even bits of <paramref name="code"/>.
	/// </summary>
	/// <param name="code">An interleaved value, presumably returned from a prior call to <see cref="Interleave(int, int)"/></param>
	/// <param name="x">Will contain the value stored in the odd bits of the interleaved value</param>
	/// <param name="y">Will contain the value stored in the even bits of the interleaved value</param>
	public static void Deinterleave( uint code, out uint x, out uint y )
	{
		x = Deinterleave( code );
		y = Deinterleave( code >> 1 );
	}

	/// <summary>
	/// Deinterleave the interleaved value and return the value stored in the odd bits. 
	/// Call this function with (code >> 1) to return the value stored in the even bits. 
	/// </summary>
	/// <param name="code"></param>
	/// <returns>Returns the value stored in the odd bits of <paramref name="code"/></returns>
	public static uint Deinterleave( uint code )
	{
		// http://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton

		code = code & 0x55555555;
		code = ( code | ( code >> 1 ) ) & 0x33333333;
		code = ( code | ( code >> 2 ) ) & 0x0F0F0F0F;
		code = ( code | ( code >> 4 ) ) & 0x00FF00FF;
		code = ( code | ( code >> 8 ) ) & 0x0000FFFF;

		return code;
	}

	/// <summary>
	/// Interleave lower 16 bits of x and y, so the bits of x are in the even positions and bits from y in the odd.
	/// </summary>
	/// <param name="x">A positive integer value between 0 and 65536</param>
	/// <param name="y">A positive integer value between 0 and 65536</param>
	/// <returns>A Morton Code with the values of X and Y interleaved into a single Integer value.</returns>
	public static uint Interleave( uint x, uint y )
	{
		// http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

		// See this post for interleaving 32-bit numbers into 64-bit result, and interesting comparisons with SIMD versions
		// https://lemire.me/blog/2018/01/08/how-fast-can-you-bit-interleave-32-bit-integers/


		x = ( x | ( x << 8 ) ) & 0x00FF00FF;
		x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
		x = ( x | ( x << 2 ) ) & 0x33333333;
		x = ( x | ( x << 1 ) ) & 0x55555555;

		y = ( y | ( y << 8 ) ) & 0x00FF00FF;
		y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
		y = ( y | ( y << 2 ) ) & 0x33333333;
		y = ( y | ( y << 1 ) ) & 0x55555555;

		uint z = x | ( y << 1 );

		return z;
	}
}